Can ‘concrete’ statements be undecidable?
Let me preface by saying that, while I’m a mathematician, I am not a logician. I’m simply curious about the field. This post is about things that have always bugged me about undecidability.
I’ll take the Collatz conjecture (CC) as an example. Suppose the CC is undecidable in ZFC. Then, if we believe ZFC is consistent, we cannot find a counterexample. If we did, this would contradict it being undecidable. This is strange to me: we would have a statement for which we can’t show its truth while knowing we cannot find a counterexample.
Compare this with the continuum hypothesis (CH), the statement people usually refer to as example of undecidable statement. If we choose it to be true, we know there is a subset S of the real numbers which has cardinality between countable and the continuum. CH being undecidable implies that if we believe ZFC is consistent, we will not stumble into such an S by construction (say with schema specification, etc.). If we did, this would contradict ZFC. But that’s ok, because not every subset of the reals can necessarily be obtained ‘constructively’ through schema specification etc. (I am being informal here, but I believe there is a formal way to say this). So us not being able to produce a counterexample of CH does not mean that one cannot exist.
To me, this seems like a different flavour to CC. There, it seems that any counterexample would be constructive (it’s just a natural number!), and hence, if CC is undecidable, such a counterexample cannot exist.
I informally define ‘concrete’ statements are ones which are about ‘constructive’ objects. Thus any counterexample to a ‘concrete’ statement would be constructive, and hence undecidability of a ‘concrete’ statement would ‘say’ that no such counterexample exists (otherwise we would be able to construct it!).
I am left with the question: should we expect ‘concrete’ statements, such as CC, to be decidable? Maybe there is a formal answer to this question, by formalising what a ‘concrete’ statement is, and showing that such statements are decidable. Though, to me, this seems unlikely to be possible, by Gödel.
Moreover Gödel’s incompleteness theorem holds just under Peano Arithmetic, and so it seems to be saying there is a priori no difference between a statement about the natural numbers such as CC and a statement about cardinalities such as CH. But my intuition cannot help but telling me these are of different nature. Am I wrong to assume this?
A more general version of my question is, why as mathematicians do we expect the questions we are working on to be decidable? We get a sense that a proof or counterexample exists, and it seems that outside of certain ‘non-constructive’ parts of mathematics, we never run into such issues.
54
u/shuai_bear 5d ago edited 4d ago
It might help to distinguish the different kinds of undecidability/independence and how the independence phenomenon happens with different undecidable statements:
CH: this is independent of ZFC as you know, proven that we can't disprove it false (Godel constructed a minimal universe of sets where 2^(N_0) = N_1, that is consistent with ZFC) and proven that we can't prove it true (Cohen showed that by forcing, we can enlarge the continuum as much as we want up to Aleph_omega edit - any cardinal of uncountable cofinality, thanks RIyehDreams showing we can create a universe that disagrees with CH but is also consistent with ZFC). CH is independent, but not an example of a true but unprovable arithmetical statement in the flavor of Godel's incompleteness theorem.
CH to me is similar to the parallel postulate of geometry. Both are structural statements where the truth of the statement not being captured by the axioms is not an example of independence of Godel's 1st theorem (true/unprovable arithmetical statements), but a consequence of the axioms under-constraining the theory, allowing multiple and equally valid mathematical universes to exist side by side.
You mentioned Collatz, but let me point out another arithmetical statement we know to be true in arithmetic but unprovable in PA - Goodstein's theorem, which is a statement about fast-growing sequences of natural numbers that asserts all such sequences eventually terminate. Turns out, Goodstein's theorem is unprovable in PA because it requires transfinite induction on epsilon_0, and PA cannot handle that. This is a "concrete" arithmetic-centered statement that was proven to be true but unprovable in PA - ZFC can prove it true, being 'stronger' than PA, but PA cannot because otherwise it would be equivalent to proving the consistency of PA (Gentzen) which Godel's 2nd theorem says we cannot do. ZFC however can prove Cons(PA), and indeed can handle transfinite induction on epsilon_0 which is why it can prove this arithmetic statement but PA cannot, even though PA can express it.
Turns out, since Goodstein's theorem is independent, by Godel's completeness theorem (not incompleteness) there is a non-standard model of arithmetic where the theorem is false. The very rough intuition is that the tail ends of long sequences of natural numbers don't 'behave' in a way that aligns with arithmetic as we know it, but otherwise it is consistent that there is a non-standard model of arithmetic where you have PA's axioms + negation of Goodstein's theorem. So there can be a counter example to this true but unprovable (in PA) statement, just the example is not a natural number from the standard model. In a stronger theory like ZFC however, Goodstein's theorem is true and provably so.
With Collatz, either it's concretely false, and we can find a concrete counterexample, or it's truly independent - and there might be a non-standard model of natural numbers where CC fails, but that we have shown that PA or ZFC cannot prove nor disprove it.
Another example of a seemingly 'concrete' unporvable truth is the solutions to Diophantine equations - a polynomial equation with integer coefficients for which it is impossible to prove whether or not integer solutions exist within a given formal system like ZFC or PA, even though a definitive true answer exists.
It turns out, that proving integer solutions exist for Diophantine equations is equivalent to proving the Halting problem, so despite it looking like a seeming like a natural statement about numbers, much like Goodstein's theorem, a form of self-reference or consistency comes to play. Indeed, many of these true but unprovable statements have a hidden Godelian mechanism to them because of the connection of the structure of the statement to the relative theory that's expressing it. Goodstein's theorem = proving Cons(PA), solution to Diophantine equations = solving Halting problem, etc. and there are other algebraic/topological formulations of independent statements that have this same hidden Godelian mechanism behind them.
All this said, we use the term 'independent' pretty broadly, but understanding how independence arises in the first place, and what being independent really means relative to a theory helps to unravel the logic behind it all. There's more nuance/formalization to it, but I see independent statements like CH and Parallel Postulate in a different category to independent (true but unprovable) statements like Goodstein's Theorem or Diophantine equation solutions.
I don't know if this answered your question completely, but hopefully it helped in some way. I'm no logician myself either, but like you I had this mismatch in my intuition and understanding of the independence phenomenon until trying to understand the mechanism that causes independence in the first place, and the different kinds of independence you see in those different classes of statements.