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.
16
u/JustAGuyFromGermany 5d ago
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:
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).