Can an existence theorem be proved to be undecidable?

Question

Please help me to think through this.

Take Riemann, for example. Finding a non-trivial zero with a real part not equal to $\frac{1}{2}$ (i.e., a counterexample) would disprove the conjecture, and also so it to be decidable.

How about demonstrating that Riemann is undecidable? Would that not imply that we can check zeros ad infinitum without resolving the hypothesis? But, checking zeros can only provide a counterexample, i.e., a disproof.

How (if at all) do these statements differ?

Any non-trivial zeros that we can find through brute force checking will have a real part of $\frac{1}{2}$.

All non-trival zeros have a real part of $\frac{1}{2}$.

Is my assumption that all non-trivial zeros is in the infinite set of zeros that can be checked by brute force correct, or even relevant? Or meaningful?

Please be kind. I'm not sure if my question even makes sense.

Answer 1

Statements of this form (the Goldbach conjecture is another such statement) that would be proven to be true if they were proven to be undecidable in ZFC, cannot be shown to be undecidable in ZFC within ZFC.

The reason is that such a proof of undecidability could not work in ZFC because this would proof the statement.

Statements like the continuum hypothesis or the axiom of choice are of another kind. In this case we could prove them to be undecidable in ZFC without running into some contradiction.

A counterexample of the continuum hypothesis for example must be so abstract that we can not construct it in ZFC.

The proof of undecidability would have to come from outside ZFC. In this way, it could be possible to show that the Riemann hypothesis is undecidable in ZFC and thus proving it to be true.

A statement is (by Goedel) provable if and only if it is true in every interpretation. If it is false in at least one interpretation and true in at least one interpretation, it can neither be proven nor disproven, hence is undecidable within the given theory.

Answer 2

They do not differ. "Any non-trivial zeros that we can find through brute force checking " is exactly the same as "All non-trivial zeros". That is, there is a "brute-force" procedure that will enumerate all the zeros.

If the RH is false, it is provably false. So if it happens to be undecidable, it must be true. But of course, for all we know, it could be provably true.

Answer 3

Certainly, if the Riemann hypothesis is false, it's decidable, since there is a counter-example, as you say. It's conceivable that it's true but undecidable, since we would never get done checking zeros. This doesn't mean that the Riemann hypothesis actually is undecidable, because brute force is not the only way to attack the problem.

Compare Fermat's last theorem. A brute force approach would be to check the quadruples $(x,y,x,n)$ in some sequence to see if $x^n+y^n=z^n$. We would never find a counterexample, because Fermat's last theorem has been decided -- it's true.

Answer 4

It is important to differentiate two aspects of mathematics, the deductive system (which is about what can be proved or not) and the model (about what is true or what is false). They are related, as everything that can be proved is true, but the converse does not hold: being true does not imply it can be proved.

Let's take RH for example. Assume it is true, does that mean we can prove it? Maybe yes, maybe not. There is no easy way to tell beforehand. Assume RH is false, does that mean we can disproove it? Yes, as it being false then there is a non trivial zero, and therefore we can prove that it is infact a zero.

So yes, RH could be undecidable, but only in the case that it is true. This generalizes to every existential question (with a sufficiently powerful deductive system).