Decidability and "truth value"

It is true that if a statement is undecidable (i.e., not provable one way or the other, in a given deductive system), then there are models in which it is true and models in which it is false. This is not, however, the only way to interpret "whether the truth value of the statement is well-defined". In the case of $\mathbb{N}$, in particular, it is common to believe that there are the "actual" natural numbers $0, 1, 2, 3, \ldots$, and all other models of arithmetic are fake, or nonstandard models. In this sense, we believe the following: every statement about the natural numbers is either true or false. (This is true even in mathematical logic, where for example we talk about properties of the "standard" and "nonstandard" models of $\mathbb{N}$.)

Godel's theorem, however, can be interpreted as calling into question this very assertion! After all, if we can never precisely describe the set of natural numbers $\mathbb{N}$ -- not in PA, nor in ZFC, nor in any other (recursively axiomatizable) theory -- then is there really only one $\mathbb{N}$ that exists? Does it really make sense to say that every statement about the natural numbers is either true or false?

Some would say yes, and some would say no. It's a philosophical matter, because the question is whether you believe that there is an ideal mathematical universe out there beyond what we can ever formalize. That is the controversy that Wikipedia is talking about in this paragraph.


Let's take as an example the Gödel sentence G for (first-order) PA which is undecidable in PA. It is also true, for it asserts that a (Gödel number of a) proof of itself does not exist, and indeed that number/proof does not exist.

And yet the completeness theorem says that since PA+$\lnot$G is consistent, it has a model, i.e. some interpretation of first-order arithmetic has G false.

So is G true or false or neither? It's true as a literal statement about numbers, and yet it's clear that there are models of PA which go either way. All this second part is really telling us is that there are models of PA in which some false statements about numbers are true. The axioms of PA are not enough to uniquely specify a model of arithmetic. These other models do indeed exist and are referred to as nonstandard models of PA. The model of PA we know in love -- where the universe is $\mathbb N$ and the symbols $0,$ $S,$ $+$ in the language of arithmetic have their usual interpretations -- is called the standard model of PA.

The key here is that we have a particular model we are referring to when we say something's true. Things get a bit dicier in, say, ZFC set theory, where there's no agreed upon "correct" model that defines "set theoretical truth."


I think that sentence is not 100% precise but was intended to mean:

Undecidability of a sentence over a deductive system is merely whether or not that system proves or disproves the sentence, and is a purely syntactic matter (at least if you believe in the classical properties of finite strings from a finite alphabet). This has nothing to do with semantic truth of the sentence independent of the deductive system. In the case of the natural numbers, we may believe that they can be embedded into the physical world via encoding as finite strings, in which case every arithmetical sentence has a well-defined truth value. In other cases, such as ZFC set theory, there is no known physical embedding, and hence there is reason to not believe that every sentence over ZFC has a well-defined truth value, and so it is more controversial.

Also, even if every sentence over a system has a well-defined truth value (not ill-specified), it does not imply that we can ever know that truth value even in principle. For example, even if 'true natural numbers' have a physical embedding, it may not be possible for us to determine the truth-value of some arithmetical sentence.

Furthermore, I would add the following.

Firstly, if we believe that the notion of provability is well-defined, we must also believe that every $Σ_1$-sentence has a well-defined truth value. But then it is natural to believe that every arithmetical sentence has a well-defined truth value too, as follows. A $Π_2$-sentence asserts the truth of $P(n)$ for every natural $n$, where $P$ is some $Σ_1$-sentence. Since $P(n)$ has a well-defined truth value for every natural $n$ (on substituting the term representing $n$ for the parameter in $P$), we have that either all are true or at least one is false, and so the original $Π_2$-sentence has a well-defined truth value as well. Of course, this is a philosophical argument, so one may dispute it, but the initial assumption that every $Σ_1$-sentence has a well-defined truth value is a far bigger jump than from that to all arithmetical sentences. See this post on building blocks for related details.

Secondly, there is no purely mathematical way to pin down the natural numbers, as can be seen from the existence of non-standard models of any recursive deductive system for them. It is also impossible to use second-order PA to pin them down, because the categoricity is relative to the meta-system. As further explained in this post, any mathematical justification for the natural numbers is necessarily circular, and it seems that there is not even any physical justification that there is an exact real-world embedding of a model of PA, despite its incredible accuracy at human scales.

Thirdly, even if we assume the existence of 'the true model' $N$ of PA, it does not help us to even determine 'the true subcollections' of $N$. Note that every first-order theory (including ZFC) will if consistent have a countable model. So any first-order theory $T$ that axiomatizes the subcollections of $N$ will have a countable model, but very weak assumptions force us to also accept that within any model of $T$ the subcollections of $N$ are uncountable. This can be stated very concretely via pair-encoding as "$\neg \exists X ⊆ N\ \forall Y ⊆ N\ \exists c \in N\ \forall k \in N\ ( k \in Y ⇔ pair(c,k) \in X )$", where $pair$ is any reasonable coding function on $N$. If such $X$ existed, let $Z = \{ k : k \in N \land pair(k,k) \notin X \}$, which construction is permitted in almost any foundational system, so for every $c \in N$ we have $c \in Z ⇔ pair(c,c) \in X$ by the defining property of $X$ but $c \in Z ⇔ pair(c,c) \notin X$ by definition of $Z$, and hence contradiction.

Fourthly, even if we assume the existence of 'the true model' of ZFC, it cannot be itself an object (set) in the model itself, despite being like a set, due to the axiom of foundation. More precisely, if we define "model" within ZFC, we can show that any (set) model of ZFC does not have itself as an element. This problem does not go away if we consider 'class' models of ZFC, because such models only have sets as elements. This is one possible reason why it is very controversial to assume that it makes sense to assume the existence of a 'true model' of ZFC.

Fifthly, concerning determining the truth-value of arithmetical sentences even if there exists a real-world embedding of naturals, it can be argued that we can in principle determine the truth value of true $Σ_1$-sentences, because eventually we will find a witness. But we cannot computably verify the truth value of false $Σ_1$-sentences, otherwise we can solve the halting problem. Worse still, even if we can somehow determine the truth value of all $Σ_n$-sentences, it does not imply that we can do the same for $Σ_{n+1}$-sentences, since the halting problem relativized to the $n$-th Turing jump cannot be solved by having a truth oracle for all $Σ_n$-sentences. This is briefly sketched in this related post.