# 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?

• He doesnt claim that the proof must exist, all he claims is that if it is undecidable, then it is true. And as pointed out by Brian this is not a formal proof (within the system). At least that is what I took from it...
– Sil
Jun 1, 2017 at 5:54
• There is a reason that the video didn't go into the fine details. They are technical, they are difficult, they require time to be processed. Even in the video there were some glaring problems with the explanation and examples (e.g. Wiles' proof of FLT was not in the same system that du Sautoy was talking about, Peano Axioms, but in a much stronger system and efforts are being made to bring the proof down to the level of this system). It's hard to give a good answer without knowing what you know or not know about mathematical logic, provability, and so on. Jun 1, 2017 at 5:56
• (Don't misinterpret my last comment, though, despite disliking a lot of the Numberphile videos, this one was good, and du Sautoy did a fine job dumbing down the incompleteness theorem to an understandable level, even if in the process he introduced mistakes (purposefully or not) which are cringe worthy for any logician with a sound mind.) Jun 1, 2017 at 5:59
• The 1st sentence in your question should be "if the RH is undecidable in PA, there is no proof in PA it is false" and the 4th sentence should be "This means the RH is true, but we have still no way (in PA) to prove it is". Jun 1, 2017 at 6:29
• @user1952009 Yes. This has been pointed out in one of the answers below. However I've left the question as is because If I make the change the question becomes more of a non-question. This was the misunderstanding that the question lies upon. Jun 1, 2017 at 6:32

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.

• No, but I can try and describe it. $\exists x\varphi(x)$ is a relatively simple sentence, and it is true; then pick some $n$ such that $\varphi(n)$ holds. Then replacing the free occurrences of $x$ by the numeral for $n$ gives us a simple sentence which is true. This means that this sentence is now provable, so we proved that there exists such $x$ by existential generalization. Jun 1, 2017 at 15:47
• @Yakk I don't know a name for the neat little trick itself, but the result is called "$\Sigma_1$-completeness" (this is a bit of an odd name - it does not mean that the theory in question proves or disproves each $\Sigma_1$ sentence, which it might suggest, but rather that it proves exactly the true $\Sigma_1$ sentences). In general the proof of the $\Sigma_1$-completeness of a theory $T$ is carried out in a stronger theory $T'$; however, sufficiently strong theories (PA is more than enough by far) can prove their own $\Sigma_1$-soundness. Jun 1, 2017 at 17:25
• The question of how weak we can go, in terms of theories proving their own $\Sigma_1$-completeness, is a difficult one with connections to major open problems in complexity theory. Meanwhile, the study of "alternative" theories, which prove their own $\Sigma_1$-incompleteness, also yields some interesting results; I recall that Visser wrote a paper on this, but I can't find it at the moment. Jun 1, 2017 at 17:29
• @Yakk The paper I was thinking of was "Oracle bites theory"; I can't find a copy online, but I do have a copy on my computer and if you're interested I could email to you. OBT studies a theory which proves that a given theory proves false $\Sigma_1$ sentences, that is, is consistent iff it is not $\Sigma_1$-complete. This is a rather perverse thing to study, but reveals a lot about weak systems of arithmetic, and the paper in general is quite fun. Jun 1, 2017 at 19:09
• @J.FabianMeier: Smullyan wrote a book about the incompleteness theorem. As did Peter Smith. But practically any book about the incompleteness theorem should do the trick. Jun 2, 2017 at 11:53

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}$.

• underrated !! +1
– mick
Aug 1, 2021 at 23:09

If the axioms are consistent, for a statement $P$, we can imagine the following situations:

1. $P$ is true, and a proof of this can be found
2. $P$ is true but no proof of this fact exists from the axioms we use
3. $P$ is false, and a proof of this can be found
4. $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.

• This answer is simply wrong! Even if $P$ is independent of the axioms, it does not imply that it is neither true nor false! In ZF for example, every arithmetical sentence is in fact either true or false, even though ZF knows that if itself is consistent then some of them are unprovable in ZF. Jun 1, 2017 at 18:41
• That part is wrong but I think it is a correct account otherwise. Those four situations are the only possible ones, even without assuming a consistent theory. Jun 1, 2017 at 18:57
• @user21820 I "struck out" that part. I did not mean to confuse being provable from the axioms, with being "true" in some model that satisfies the axioms. What I wanted to say, is for something like the Riemann hypothesis, it could be either 1., 2., or 3. If it is 1. or 3., there is hope some smart guys will discover the proof one day. If no proof or disproof exists, then the Riemann hypothesis is true (2.). Jun 2, 2017 at 9:18
• Thanks for editing! It's much better now. Note that your 4 possibilities are all there is for an arithmetical statement (since usually we work in a meta-system that already has a collection of natural numbers), but for a non-arithmetical sentence the 4 possibilities are only meaningful if specified with respect to a model. Take CH for example, for which we simply can't state that it is true or false without specifying a particular model. The key point to note is that the notion of truth involved in this kind of "if false then provable" claims is tied to a single model of PA. Jun 3, 2017 at 12:22

To me Marcus du Sautoy's claim seems to be inconsistent especially in light of Asaf's answer. If you can construct the same two logical statements about the RH and GC then it cannot be that one is decidable and the other is not in the same system.

Since the GC is about a basic arithmetic truth you may not need a stronger axiomatic system than the Peano Axioms (PA). So if anything it would make more sense to propose the RH (which is a claim in complex analysis and probably requires ZF) is undecidable and the GC is decidable in ZF. But as Asaf mentioned the decidability of RH can be formalised as a relatively simple statement.

• @NoahSchweber I don't think you understood what I said. I didn't refer to the logical statements of the RH and GC but to the logical statements regarding their deciadability. This is what the original poster asked. Oct 2, 2018 at 3:29
• So I am an idiot, but for a different reason: I was indeed talking about the statements re: their decidability, I just somehow managed to misremember what GC is. It's unfortunately too late for me to retract my -1 unless you edit but I still do take a small issue with part of this answer: namely, the line "Since the GC is about a basic arithmetic truth you may not need a stronger axiomatic system than the Peano Axioms (PA) ... [but] RH ... is a claim in complex analysis and probably requires ZF" is in my opinion very misleading, since it does suggest that simplicity of topic is relevant here. Oct 2, 2018 at 3:59
• The Twin Prime Conjecture is completely irrelevant to this discussion as it is not falsifible by example. The question was why the same logic proving RH is decidable cannot be applied to GC. So far I've seen a lot of comments here discussing various topics in logic but nobody bothered (or knows how) to answer the original poster's question. Oct 2, 2018 at 4:05
• TP is irrelevant to the question, but it's not irrelevant to what you've written: since most people would consider TP to also be about "a basic arithmetic truth," your line I've quoted is unfortunately somewhat misleading. And "falsifiable by example" is exactly the notion of logical simplicity being discussed, so I'm not sure why you think "nobody bothered (or knows how) to answer the original poster's question" - Asaf has quite clearly explained the point, that it can be so applied. (Meanwhile, re: forgetting what GC is, I've already admitted that and said I was stupid.) Oct 2, 2018 at 4:14
• And I think Asaf's (accepted) answer explains this quite well. Oct 2, 2018 at 4:26