6
$\begingroup$

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.

$\endgroup$
5
  • 3
    $\begingroup$ NO. Undecidable does not mean that there are statements lacking truth value, but only that, in the cotext of a well-specified formal system, we have no algorithm to mechanically sort out the true statements from the false ones. $\endgroup$ – Mauro ALLEGRANZA Jan 21 '18 at 8:38
  • 2
    $\begingroup$ Regarding Post's tautology theorem, you have to note that it holds for propositional logic, which is decidable: see the truth table method. $\endgroup$ – Mauro ALLEGRANZA Jan 21 '18 at 8:42
  • $\begingroup$ Regarding G's Th for first-order logic, it asserts that a valid formula is provable. This does not violate the undecidability of FOL simply because we have no algorithm (like truth table) to know in advance if a formula is valid or not. $\endgroup$ – Mauro ALLEGRANZA Jan 21 '18 at 8:45
  • 1
    $\begingroup$ You can see also how-is-first-order-logic-complete-but-not-decidable as well as why-is-propositional-logic-decidable. $\endgroup$ – Mauro ALLEGRANZA Jan 21 '18 at 12:01
  • 1
    $\begingroup$ One should keep in mind that materials for laypersons are often rather imprecise about the subtler issues of logic, and through retelling by people who don't know the precise interpretations such descriptions often become riddled with errors; e.g. in the way that comparisons between "countable number of formulas" and "uncountable number of reals" often trip over Skolem's paradox. $\endgroup$ – user14972 Jan 21 '18 at 12:12
5
$\begingroup$

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

$\endgroup$
21
  • 1
    $\begingroup$ @6005 I certainly agree that ZFC doesn't resolve much here, and I didn't mean to insinuate that it did. It's not clear to me how it would, even if your very valid specific objection were invalid. Will delete that middle sentence. Regarding the second point I'm no expert, but I think opinions vary on this (multiverse, etc). Even so, the qualifier "agreed upon" seems pertinent. $\endgroup$ – spaceisdarkgreen Jan 21 '18 at 5:48
  • 2
    $\begingroup$ @Seub 1. G has no proof, by Godel's theorem. Thus the proof does not exist. 2. I don't think they are saying that. I was claiming that there is a "correct" model of arithmetic and arithmetical truth is well-defined (this is, I think, most peoples' belief but not philosophically bulletproof). There is certainly not generally a "correct" model of a given system of axioms any more than there's a "correct" group in group theory (your geometry example also works). $\endgroup$ – spaceisdarkgreen Jan 21 '18 at 16:02
  • 1
    $\begingroup$ @Seub But we oftentimes write down axioms imagining we're specifying a given model, like Euclid was trying to specify Euclidean geometry. In this case, an undecidable statement means we have not fully specified it. In some systems (where Godel holds) we will never achieve our goal of pinning down every truth value by specifying axioms in a computable fashion. Whether or not that means those truth values do not exist and our more elaborate arguments and impressions that we had a model were in fact bunk is the object of controversy here. $\endgroup$ – spaceisdarkgreen Jan 21 '18 at 16:09
  • 1
    $\begingroup$ @Seub Well when we make statements like 'this diophantine equation has a solution' or 'the continuum hypothesis is true', what do you imagine we're saying? (And also, I refer you User21820's first point that when we talk about statements having proofs in formal systems we are implicitly asserting some kind of absolute truth, at least for $\Sigma_1$ sentences of arithmetic.) $\endgroup$ – spaceisdarkgreen Jan 21 '18 at 16:29
  • 1
    $\begingroup$ @Seub I think what I meant about "what true means" didn't get across. I was saying "true" typically means "true in some specified model," not "true in every model of some specified formal system." I don't understand how one can conflate these as in "some/every." (And I'll check your reference on the theorem... I just assumed cause of "tautology.") I don't have time for extended discussion right now but if this continues later we can certainly go into chat. $\endgroup$ – spaceisdarkgreen Jan 21 '18 at 22:21
10
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ I am still not very satisfied with this. Talking about "the actual natural numbers" or "the actual algebraically closed fields of characteristic zero", does not make sense in the setting we are discussing, which is mathematical logic (but this very setting does allow to talk about truth value in a precise sense). $\endgroup$ – Seub Jan 21 '18 at 15:02
  • $\begingroup$ I edited my question to address this in a little more detail. $\endgroup$ – Seub Jan 21 '18 at 15:36
  • $\begingroup$ @Seub The answer is not about there being a "preferred model" for every theory -- but there is a preferred model for some theories, like PA, and that is standard in mathematical logic. I think you're missing the point of the answer. $\endgroup$ – 6005 Jan 21 '18 at 17:03
  • $\begingroup$ The phrase "the actual algebraically closed fields of characteristic zero" is nonsense. That is not at all the same as the case of natural numbers, where there really is one object that we want to write axioms for, and the only problem is we can't actually nail that object down. $\endgroup$ – 6005 Jan 21 '18 at 17:03
  • $\begingroup$ If you are serious about your objection than you must disagree with the terminology "standard model" of the natural numbers. But this would make your position very radical. Please let me know if you have any further questions. (I also apologize for deleting and editing these comments.) $\endgroup$ – 6005 Jan 21 '18 at 17:05
4
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Thank you for your answer but I don't feel it adresses my question very directly. The notion of "true world" or "physical world" does not have a place in mathematical logic. But models do, and tautologies do, and these address the notion of "truth value". $\endgroup$ – Seub Jan 21 '18 at 15:08
  • $\begingroup$ I edited my question to address this in a little more detail. $\endgroup$ – Seub Jan 21 '18 at 15:36
  • 1
    $\begingroup$ @Seub: Well it is clear that you do not have the sufficient mathematical background to understand my answer, which is why you did not see why it directly answers your question. In particular, my very first point already states clearly that it is meaningless to talk about provability unless you already believe in a real-world embedding of a model of PA. My second point links to a post detailing why it is foolish to discard the real-world motivation for the axioms of PA, even if it does not exact real-world interpretation. $\endgroup$ – user21820 Jan 21 '18 at 16:04
  • $\begingroup$ @Seub: If you have questions, simply ask, instead of telling me what has a place in logic. I already clearly distinguished in my post between mathematical and physical justification, and I can tell you I know very well what is and what is not mathematical. Furthermore, my second point makes clear that the categoricity of second-order PA is relative to the meta-system, so it is misleading to think it pins down anything at all. $\endgroup$ – user21820 Jan 21 '18 at 16:07
2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ While true, I don't think this addresses the question. $\endgroup$ – 6005 Jan 21 '18 at 5:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.