79
$\begingroup$

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?

$\endgroup$
  • 6
    $\begingroup$ 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... $\endgroup$ – Sil Jun 1 '17 at 5:54
  • 1
    $\begingroup$ 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. $\endgroup$ – Asaf Karagila Jun 1 '17 at 5:56
  • 1
    $\begingroup$ (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.) $\endgroup$ – Asaf Karagila Jun 1 '17 at 5:59
  • 2
    $\begingroup$ @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. $\endgroup$ – Sriotchilism O'Zaic Jun 1 '17 at 6:32
  • 1
    $\begingroup$ May I suggest changing your Question title to something more like "Does proving undecidability prove a theorem? (Godel / Riemann Numberphile video)"? Your current title isn't helpful to people searching for this. $\endgroup$ – Jerry Guern Jun 1 '17 at 19:03
46
+100
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Can you name the "neat little trick"? $\endgroup$ – Yakk Jun 1 '17 at 15:38
  • 1
    $\begingroup$ 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. $\endgroup$ – Asaf Karagila Jun 1 '17 at 15:47
  • 5
    $\begingroup$ @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. $\endgroup$ – Noah Schweber Jun 1 '17 at 17:25
  • 3
    $\begingroup$ 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. $\endgroup$ – Noah Schweber Jun 1 '17 at 17:29
  • 2
    $\begingroup$ @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. $\endgroup$ – Noah Schweber Jun 1 '17 at 19:09
16
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – user21820 Jun 1 '17 at 18:41
  • 1
    $\begingroup$ 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. $\endgroup$ – Dan Brumleve Jun 1 '17 at 18:57
  • $\begingroup$ @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.). $\endgroup$ – Jeppe Stig Nielsen Jun 2 '17 at 9:18
  • $\begingroup$ 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. $\endgroup$ – user21820 Jun 3 '17 at 12:22
-1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @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. $\endgroup$ – marting Oct 2 '18 at 3:29
  • $\begingroup$ 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. $\endgroup$ – Noah Schweber Oct 2 '18 at 3:59
  • 1
    $\begingroup$ 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. $\endgroup$ – marting Oct 2 '18 at 4:05
  • $\begingroup$ 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.) $\endgroup$ – Noah Schweber Oct 2 '18 at 4:14
  • $\begingroup$ And I think Asaf's (accepted) answer explains this quite well. $\endgroup$ – Noah Schweber Oct 2 '18 at 4:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.