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/JustAGuyFromGermany]

The easiest way to think about this topic is to take what is now called the "multiverse view" to set theory: The axioms of set theory are similar to the axioms of groups or topological spaces or something similar - they can have many different instantiations (also called models in set theory), all of which satisfy the axioms (and all provable consequences of those axioms) but they may also differ in statements which are not provable from the axioms.

A statement like the Collatz conjecture being undecidable simply means that there are at least two models: One in which the Collatz conjecture is true, i.e. all natural numbers in that model satisfy the conjecture, and also one in which it is false, i.e. at least one natural number of that other model does not satisfy the conjecture. Just like "xy=yx is not decidable from the group axioms" simply means that there is at least one group which is and one group which isn't commutative.

It is important to note that there is no such thing as "the" natural numbers across all models. There is of course only one such thing in each model, but there should be no expectation that the natural numbers of one model behave the same as the natural numbers of some other model. Just like you wouldn't expect say the centre of one group to be in any way similar to the centre of a different group.

That's basically the whole point of Gödel's incompleteness theorem: Models of set theory can have different natural numbers that can have different arithmetic properties, including what kind of equations have solutions and which don't. And "X is a proof of Y" is just a very, very, very complicated arithmetic equation that may or may not have solutions depending on which model you look at.

To be more precise. You state:

it seems that any counterexample [to the Collatz conjecture] would be constructive (it’s just a natural number!), and hence, if CC is undecidable, such a counterexample cannot exist.

That's not true. If the Collatz conjecture is undecidable, then the natural numbers (inside some model where CC is false) which are counterexamples are exactly not constructive, i.e. they cannot be written as 1+1+1+...+1 with any absolute number of ones. Your own argument shows that: The same string of symbols would define a natural number in any model, including those in which CC is true. And the whole calculation that CC is false for this number would also consist of an absolute number of symbols, which would therefore also be applicable to any other model, including those in which CC is true. Therefore, there cannot be such a finite string.

What we have proven is: The models of set theory in which CC is false (if there are such models) have very weird models of N which do not look at all like the natural numbers of our meta-theory; they are non-standard models of Peano arithmetic and the counterexamples are non-standard natural numbers. The thing is: The model does not know that! From inside the model the counterexample looks like a completely ordinary natural number. It satisfies all properties that ZFC can prove about natural numbers after all. It just doesn't satisfy some of the statements that ZFC cannot prove (like CC in our assumption).

[u/Lehatan → u/JustAGuyFromGermany]

This is a pretty mind blowing answer. What would a weird model of N look like? Can we “write down” an example of a weird model of N? Or is this fundamentally out of grasp?

[u/__mintIceCream → u/Lehatan]

The example I was shown is a result of the compactness theorem, which you can look up as well, it is very cool and awesome.

The idea is that alongside the (first order) peano axioms, we add in an axiom that declares the existence of an infinite element c (we technically need to add infinite axioms saying that c>0, c>1, c>2, etc. for all the usual naturals, and this is where compactness comes in), and then you can examine the consequences because c satisfies all the peano axioms and is thus also a natural number so everything about natural numbers apply. A couple of them:

• c has a successor, and since its not zero c also has a predecessor, so there is a copy of the integers Z around c (the model now looks like N followed by Z)
• c+c cannot be reached via successors of c, since c is infinite, similarly n*c for any n (the model now looks like N followed by N copies of Z)
• c is either even or odd, so we can either divide either c or c+1 by 2, meaning we can fit c/2, c/4, c/8 etc before c and all of those are also unreachable from each other (the model now looks like N followed by Z copies of Z)
• you can add all the inbetween points too by taking averages and whatnot, and we now have N followed by the rational numbers Q; but each point of Q is replaced by a copy of Z.
• theres probably more this is all we got to

I think this is a good example of the multiverse view, its very obviously not the usual model of natural numbers, and just using the peano axioms you cannot tell the difference between this and the usual one. But its (probably, i havent tried) easy ("easy") enough to construct it in zfc

edit to add: this is the same one as the one described by u/JustAGuyFromGermany choose your favorite exposition

[u/Lehatan → u/__mintIceCream]

Seeing this example I come to the conclusion that Peano arithmetic is too stupid if it cannot distinguish between these two things. Surely then we should use more axioms when making statements about N

[u/__mintIceCream → u/Lehatan]

It's kind of the opposite, in a sense; the axioms we are looking for to be able to do arithmetic are too powerful. The point of Godel's (first?) incompleteness theorem is that (dependent on some reasonable conditions) even if we add axioms to disallow any specific models we don't like, if it can still do arithmetic as we know it, there will always be some non-standard model in addition to The One True Model.

[u/JustAGuyFromGermany → u/Lehatan]

Well, on the other hand they are powerful enough to do arithmetic ;-)

And indeed, it is a bit of "choose one" here. That's the point of Gödel's incompleteness theorem. As soon as your axioms are powerful enough to do a fair bit of arithmetic (you don't need all of Peano) you already get incompleteness. There are other axioms that are not affected by incompleteness phenomenon and do indeed have unique models, but you can't do much arithmetic with them.

[u/Lehatan → u/JustAGuyFromGermany]

Oh wow! This along side the answer from [u/__mintIceCream](u/__mintIceCream) put a lot of pieces into order in my head.

[u/GoldenMuscleGod → u/Lehatan]

Here is what might also be a helpful piece: there is a theory called “primitive recursive arithmetic.” It is expressive enough to be able to make pretty much any concrete claim like “this algorithm will be in this state after this many steps” where each “this” is something explicitly named. And it is powerful enough to resolve any concrete question you might ask of it in its language.

However it is not expressive enough to say things like “this computation eventually halts” - it can say it does/doesn’t halt in n steps, and it can prove it one way or the other for any concretely given n. But what if n is a variable? Well then obviously if it halts in n steps depends on what n is, so in general we should not be surprised we cannot prove or disprove it.

Now sometimes you might be able to prove “this computation doesn’t halt in n steps” where n is a variable. We understand this must mean it never halts (since we assumed nothing about n’s value) but we cannot treat that statement as saying that: if we assume the computation doesn’t halt in n steps in order to do a direct proof then we have only assumed something about a particular unspecified n, not for all n.

Similarly we cannot say “this computation eventually halts” we can only say things like “this computation halts in 50,000 steps” or whatever for any other number. But of course “this computation halts in 50,000 steps” does not mean the same thing as “this computation eventually halts” - the first claim is stronger and more explicit.

The idea of theories like Peano arithmetic is we want to expand the language to be more expressive so we can say certain things are true of all numbers or of some number, or of all computations or of some computations, without having to name them so concretely. So we add quantifiers. This is very useful, but it is exactly this step in allowing expanded meaning that forces us to have statements we cannot work with as concretely - because they are less concrete.

We want \forall n Pn to be true exactly when Pk is true for every natural number k, this can be taken as a part of a definition of what \forall means. But can we have that \forall n Pn is provable exactly when Pk is provable for every natural number k? Reflecting on this might make you realize this is a lot to ask of a theory, and in fact we can’t make it work for any nice theory. So it is exactly the inclusion of this type of meaning that makes the statements less “concrete” in at least some ways.

[u/Lehatan → u/GoldenMuscleGod]

Thank you, this was very helpful too. This seems to pin down exactly where the loss of ‘concreteness’ happens in the formalism.

[u/GoldenMuscleGod → u/Lehatan]

If you want to explore the logic of this idea of “concreteness” you might want to consider looking into intuitionistic logic and constructive theories. It can take a while to get used to not accidentally using the law of the excluded middle when you reason but it’s actually not so weird as you might think. If you look up Gödel’s Dialectica interpretation of Heyting Arithmetic (the intuitionistic analog of Peano Arithmetic) it might give a lot of insight, although some practice with intuitionistic propositional logic might be necessary to be able to follow it.

[u/Opposite-Friend7275 → u/Lehatan]

Nobody can distinguish between those things. It’s like trying to decide if the universe we live in is infinite, or, a larger version of infinite. With finite means that cannot be decided.