Decidability of the Riemann Hypothesis vs. the Goldbach Conjecture
In the most recent numberphile video, Marcus du Sautoy claims that a proof for the Riemann hypothesis must exist (starts at the 12 minute mark). His reasoning goes as follows:
If the hypothesis is undecidable, there is no proof it is false.
If we find a non-trivial zero, that is a proof that it is false.
Thus if it is undecidable there are no non-trivial zeros.
This constitutes a proof the hypothesis is true, thus it is decidable.
This makes perfect sense, however only seconds earlier he states that the Goldbach conjecture might be undecidable. It seems to me that the exact same reasoning we applied to the Riemann hypothesis could be applied to the Goldbach conjecture. Just switch out the words "non-trivial zero" for "even number that cannot be represented by the sum of two primes" and to me this reasoning looks fine.
In fact as far as I can tell any statement that can be verified or falsified by example can be plugged into this to generate a proof it is decidable.
Since Marcus du Sautoy is considerably more qualified than I to speak about this I trust that there is something more complex going on behind the scenes here. Does this apply to the Goldbach conjecture? If not why not? What am I not understanding here?
Solution 1:
The issue here is how complicated is each statement, when formulated as a claim about the natural numbers (the Riemann hypothesis can be made into such statement).
For the purpose of this discussion we work in the natural numbers, with $+,\cdot$ and the successor function, and Peano Axioms will be our base theory; so by "true" and "false" we mean in the natural numbers and "provable" means from Peano Arithmetic.
We will say that a statement is "simple" if in order to verify it, you absolutely know that you do not have to check all the natural numbers. (The technical term here is "bounded" or "$\Delta_0$".)
For example, "There is a prime number small than $x$" is a simple statement, since verifying whether or not some $n$ is prime requires only checking its divisibility by numbers less than $n$. So we only need to check numbers below $x$ in order to verify this.
On the other hand, "There is a Fermat prime larger than $x$" is not a simple statement, since possibly this is false but only checking all the numbers above $x$ will tell us the truth of this statement.
The trick is that a simple statement is true if and only if it is provable. This requires some work, but it is not incredibly difficult to show. Alas, most interesting questions cannot be formulated as simple statements. Luckily for us, this "provable if and only if true" can be pushed a bit more.
We say that a statement is "relatively simple" if it has the form "There exists some value for $x$ such that plugging it in will turn the statement simple". (The technical term is $\Sigma_1$ statement.)
Looking back, the statement about the existence of a Fermat prime above $x$ is such statement. Because if $n>x$ is a Fermat prime, then the statement "$n$ is larger than $x$ and a Fermat prime" is now simple.
Using a neat little trick we can show that a relatively simple statement is also true if and only if it is provable.
And now comes the nice part. The Riemann hypothesis can be formulated as the negation of a relatively simple statement. So if the Riemann hypothesis was false, its negation was provable, so Riemann hypothesis would be refutable. This means that if you cannot disprove the Riemann hypothesis, it has to be true. The same can also be said on the Goldbach conjecture.
So both of these might turn to be independent, in the sense that they cannot be proved from Peano Arithmetic, but if you show that they are at least consistent, then you immediately obtain that they are true. And this would give us a proof of these statements from a stronger theory (e.g. set theory).
You could also ask the same about the twin prime conjecture. But this conjecture is no longer a relatively simple statement nor the negation of one. So the above does not hold for, and it is feasible that the conjecture is consistent, but false in the natural numbers.
Solution 2:
The last bullet point, saying that this constitutes a proof it is decidable, does not follow.
$X$ is decidable means either $X$ is provable or $\neg X$ is provable. It's possible that both are provable, in which case the theory is inconsistent and every statement and its negation are provable and every statement is decidable.
The situation generalizes to any statement on the same level of the arithmetical hierarchy as the Riemann hypothesis or the Goldbach conjecture, including the Gödel sentence. All assert the existence or non-existence of a natural number satisfying a computable predicate. If the existential form is unprovable then the universal form is true. And the contrapositive is: if the universal form is false, then the existential form is provable (implying both forms are decidable). So if RH is false then RH is decidable, and if GC is false then GC is decidable, and if arithmetic is inconsistent then the consistency of arithmetic is decidable. That may be what was intended by the final point.
An example of a problem with a different situation is $\text{P=NP}$.
Solution 3:
If the axioms are consistent, for a statement $P$, we can imagine the following situations:
- $P$ is true, and a proof of this can be found
- $P$ is true but no proof of this fact exists from the axioms we use
- $P$ is false, and a proof of this can be found
- $P$ is false but no proof of this fact exists from the axioms we use
Note that there may be other possibilities sometimes, for example $P$ might be independent of the axioms, meaning that it is neither true nor false.
For both the Riemann hypothesis and the Goldbach conjecture, we can quickly rule out item 4. above. Because if either is false, there exists a point which violates the statement, and with that counterexample we have an easy proof of the falsity of it.
When 4. can be ruled our in these special cases, we only need to figure out whether 1., 2., or 3. applies.