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

This is the reply to the question OP is asking I think. The confusing thing is this: if RH is undecidable, then it is true. The proof is that if it were false, there would be a counterexample, and checking that there is a counterexample is a finite computation (via for example the Lagarias equivalence).

But how could then one take the negation of RH and add it as an axiom while maintaining consistency? The point is that then we're saying that there is a non-standard counterexample (but our theory is too weak to see that it's non-standard).

Note that CC is much less concrete than RH, since there is no way to check in finite time that a given integer is a Collatz counterexample (and indeed the undecidable variants of Collatz build on this by encoding the halting problem into such a computation).

This kind of behavior is encoded in the arithmetic hierarchy.

[u/cuervamellori → u/ventricule]

Is this a fair interpretation: when I say "all the nontrivial zeros lie on the critical line", what I really mean is "all the, you know, standard nontrivial zeros, using the smallest model of zfc, the one we all know and love, all those zeros, lie on the critical line", but there's no way to make that statement in the language of zfc.

Whenever I say RH, I mean that second one in my head, which is why it's so hard to deal with sentences like "RH might be undecideable in zfc", because that's talking about the first one.

I assume it's correct say "RH is definitely either true or false in the standard (smallest) model of zfc"? And presumably there could be some set of axioms that we could add to zfc that would be strong enough to constrain all the allowable models to those in which RH is true (one such axiom of course would be "RH is true") or false, but we don't have any pleasing such set of axioms.

(Obviously all this in a world where RH actually is independent of ZFC which we don't know)

[u/Sproxify → u/cuervamellori]

there aren't any additional "exotic" zeroes of the riemann zeta function given by allowing more extravagant set theory stuff. it's a sufficiently concrete object for that not to be an issue.

[u/cuervamellori → u/Sproxify]

Is that equivalent to asserting that RH is not independent of ZFC?

[u/Sproxify → u/cuervamellori]

no, it still could be independent. you could think of it as being like zfc "knows" all the zeroes of zeta, but might not be able to prove a universal statement about all of them at once.

[u/cuervamellori → u/Sproxify]

My understanding is surface level but if it's independent, shouldn't there be a model where it's false?

Or is it more that RH can't actually be expressed in first order logic, and saying it's independent of ZFC isn't actually well formed?

[u/Sproxify → u/cuervamellori]

my understanding of all the model theory stuff is also entirely surface level but I'm certain you're right that if it's independent then there's a model where it's false and a model where it's true.

assuming for a second that "our" Riemann hypothesis is true but independent ZFC, then I wouldn't think of that as a model where our zeta function has secret addition. I don't know how I would think about it because I'm not knowledgeable enough in this domain to have a strong intuition for what it means in this case. I suppose that is in line with how you phrased it originally then, but I still feel it must be different than the sense in which ZFC has extra sets that you can't construct in ZF for example.

but what I meant more so when I said you can't find additional zeroes, and I realize now I can't make it precise, is that in my intuition you can't add stronger axioms to the theory that would allow you to describe more zeroes of zeta that even plausibly could be there in "our" sense. Because ZFC already proves there's a computable procedure for finding all the zeroes (up to a neighborhood), and there's also computable processes described by ZFC which half iff Riemann is false.

So the model that believes the conjecture is false probably must be understood as something like the countable model of ZFC where the proven statement of uncountability somehow means something different internally in that model.

[u/cuervamellori → u/Sproxify]

Well, luckily for us, it seems there are proofs that RH is decidable in ZFC, so we don't have to worry :)

[u/Sproxify → u/cuervamellori]

well, no, it could still be independent. we can describe a turing machine that would half iff RH is false, and prove that in ZFC, but if the conjecture is corect, so that it never halts, then there may not be a proof of that in ZFC. but if the conjecture it wrong, and it does halt, then that amounts to a finite computation which necessarily corresponds to a proof in ZFC.

so there are 3 options:

(1) Riemann hypothesis is true, and provable in ZFC

(2) Riemann hypothesis is true, but ZFC is not strong enough to prove it

(3) Riemann hypothesis is false, and then ZFC necessarily proves that it's false

scenarios 1 and 2 are both plausible imo, and in scenario 2 I think we as humans are likely incapable of proving Riemann, as I don't think it's likely that ZFC is just too weak for some kind of proof strategy of riemann that humans could muster.