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

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/Waste-Ship2563 → u/__mintIceCream]

This is strange, I know e.g. in type theory naturals are defined inductively via two constructors, 0: N and succ: N -> N, your example sounds like including a third constructor c: N. But then it seems like this isn't a model of the natural numbers.

Edit: I think I get the idea. In standard models of ZFC, the proposition "∃ c, (0 < c) ⋀ (1 < c) ⋀ ... " is false, but there are nonstandard models in which it's true.

[u/JustAGuyFromGermany → u/Waste-Ship2563]

In type theory, N is defined as the "universal" or "smallest" type with these two properties, i.e. it is explicitly defined as the standard model in a second-order fashion. The construction above is only about the first order Peano axioms.