Can ‘concrete’ statements be undecidable?

[u/Lehatan]

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.

[u/shuai_bear]

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.

[u/Lehatan → u/shuai_bear]

Thank you, this was helpful. A lot of things for me to digest, but the idea that there are different ways in which a statement may be undecidable seems crucial, and not something I’ve thought about before.

I still struggle to understand the intuition for the ‘non-standard’ models of PA in which ZFC-provable statements about natural numbers are false.

Edit: based on your and others’ answers on this thread, I am coming to the conclusion that PA is too weak to describe the natural numbers

[u/GoldenMuscleGod → u/Lehatan]

A non-standard model of PA basically has all the natural numbers, but it also has more “infinite” numbers that are larger than all of them but still act like other numbers.

Here is what I think is a good way to build intuition: take PA - or any other theory, you can even take the full set of all true sentences in Th(N) if you want (even though this set is not recursively axiomatizable) - and add to it a new constant symbol c and add the infinite list of axioms axiom c=/=0, c=/=1, c=/=2, etc for each natural number - this is an infinite set of new axioms, we do not add the axiom “for all n, c=/=n” which would be inconsistent since we could substitute c for n.

This theory is consistent: any proof is finitely long and can only cite finitely many axioms, so just pick some number c that isn’t barred from being by the axioms used and say it is that, showing no proof can yield an inconsistency. You can think of this like a game where I choose c and you can ask me questions about it and I say “yes” or “no” and you try to figure out what c is, but I am allowed to “cheat” and change my mind about what c is as long as all my previously given answers remain true. It turns out you can never pin me down to a specific value of c if I am clever enough.

So what would a model of this theory look like? Well it has all the natural numbers, and c must be larger than all of them (since you can list them going up and I have to say it’s larger to keep from being pinned down to a smaller set). It’s also going to have a bunch of things like c-16, or c/2, or c^(2), or floor(log c) or “the number of distinct prime factors in c”. All of these except possibly the last will also be larger than every natural number. On the last, I could have a model where c is prime, or where it is a (nonstandard) power of 2, or where c is divisible by every standard prime.

[u/shuai_bear → u/Lehatan]

intuition for the ‘non-standard’ models of PA in which ZFC-provable statements about natural numbers are false.

GoldenMuscleGod has a great detailed comment about how it works - think of c in their comment as a non-standard integer. Nonstandard integers are able to exist in a model that is consistent with PA (one property is that it is larger than any standard natural number), because PA is too lax and doesn't have enough rules/'strength' preventing their existence unlike ZFC.

And when we plug in these nonstandard integers to Goodstein's algorithm, it produces an infinitely long descending chain of ordinals / sequence - some sequences will never terminate with these nonstandard inputs. This cannot happen when epsilon_0 is well-founded (it can't happen in ZFC), but it can happen in a weaker theory like PA.

And for some model theory intuition, think whether the perspective is external or internal relative to the model - outside of PA, say from ZFC we know Goodstein's theorem being false is false. But inside of it, PA is "naive" in a sense because it can't detect anything wrong with Goodstein's theorem being false, agreeing/being consistent with both either the truth of falsehood of it.

 PA is too weak to describe the natural numbers

Yes in the sense that the proof-theoretic ordinal (think of it as the supremum of ordinals that can be proven to be well-founded in a theory) of ZFC is much higher than PA (how much we don't really know), but enough that it can handle a proof that would only require transfinite induction on said ordinal.

However, note that ZFC also cannot capture the full truth of natural numbers. No theory can (a theory that is consistent, and recursively enumerable - otherwise just take the set of all true statements of arithmetic and call that a theory). While ZFC may be stronger than PA, it too is subject to incompleteness and you get a whole other class of problems that are true but unprovable in ZFC.

[u/yoshiK → u/Lehatan]

Löwenheim–Skolem tells us that if a set of sentences has a infinite model, it has models of every infinite cardinality. So that implies that any theory of the natural numbers has non-standard models. However you are probably thinking about the elemental model of PA. So if you have two models of PA a, b, then both contain a zero and a successor function s_a , s_b (this is just PA) and we can find the isomorphism of two subsets where f: 0_a |-> 0_b and s_a ⁿ (0_a) |-> s_b ⁿ (0_b) so that tells us that models of PA are "the natural numbers" and some additional bits.