Decidability and "truth value"

Question

One can read in the Wikipedia page for "Gödel's incompleteness theorems":

Undecidability of a statement in a particular deductive system does not, in and of itself, address the question of whether the truth value of the statement is well-defined, or whether it can be determined by other means. Undecidability only implies that the particular deductive system being considered does not prove the truth or falsity of the statement. Whether there exist so-called "absolutely undecidable" statements, whose truth value can never be known or is ill-specified, is a controversial point in the philosophy of mathematics.

NB: The same text appears in the Wikipedia page for "Undecidable Problem".

I don't understand this. It seems to me that there are a couple of theorems in mathematical logic which, on the contrary, very clearly explain the relation between the undecidability of a statement and its "truth value": depending on the meaning of "truth value", I am thinking about Post's tautology theorem and Gödel's completeness theorem.

Am I missing something? And what does Wikipedia mean by "absolutely undecidable"?

Let me elaborate in a little bit for clarity. My understanding is that by the completeness theorem, a statement is undecidable if and only if there exist models in which it is true and other models in which it is false. Moreover (or alternatively), by the tautology theorem of Post, a statement is undecidable if and only if there exist some truth valuations for which it is true and others for which it is false. In any case, the conclusion, it seems to me, is simply that a statement is undecidable if and only if its truth value is not defined (it can be "chosen" true or false arbitrarily).

---

EDIT. Let me add a couple of observations after reading the answers of 6005, user21820, and spaceisdarkgreen, which are not entirely satisfactory to me. These answers are defending Wikipedia's text by interpreting the meaning of "truth value" relatively to some kind of correct model or worse, the physical world. Neither of these notions have a place in mathematical logic, it seems to me. When talking about natural numbers, we may like to think there is a correct model, but it would be silly to assume that there is a "preferred universe" for every theory.

For example, take Euclid's 5 axioms for geometry, remove axiom #5 (the "parallel postulate") so that you're left with only the first 4 axioms (you get "absolute geometry"). Both the Euclidean plane and the hyperbolic plane are models for this theory. Is one of the two the "correct model"? Clearly no, since we got rid of the fifth axiom that would discriminate between the two.

So at this point I still find that Wikipedia's assertion about "truth value" is still irrelevant.

Answer 1

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."

Answer 2

Undecidable is undecidable under certain deductive system. Decidable means that it is a theorem or its negation is a theorem, understood in a very specific sense. A theorem here is the final line of a list of statements such that each one of them is

• an axiom
• a theorem already proved (I know this sounds kind of circular, just trying to give an idea)
• the result of applying modus ponens or a few other logic rules to previous lines of the list.

If the number of axioms is finite or enumerable, it is "easy" to think about all such possible lists. The question is: every possible predicate will be a theorem or its negation will be a theorem? Or are there properties that you can enunciate but are not theorems and their negations aren't theorems either? That's all that incompleteness means, at least from a purely syntactic point of view.

Regarding your observation, the phrasing of the paragraph you quote I wouldn't say is wrong but it does get a little confusing, since there are results about undecidability (like Gödel's incompleteness theorem) which DO address the truth value issue: it presents us with a proposition which is undecidable in the previous sense, but nevertheless is true (and so has a well defined truth-value).

The quote says something like "undecidability does not address the question of wether the truth value is well defined", and well... No: "undecidability" doesn't; Gödel, perhaps. =S

For sure that paragraph can and should be improved. You can never exagerate on the level of precission of your language when you write about these issues.

Answer 3

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.

Answer 4

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.