9
$\begingroup$

I've read and heard in lectures that

A way to prove that the Riemann hypothesis is true is to show that its negation is not provable.

The argument (informally) usually goes like

If a statement is false, then there must exist a counterexample showing its falsity.

Hence, to prove any statement is false, one must have a constructive proof.

Question: Why doesn't Godel's incompleteness theorem apply to false statements? That is, how do we know that all false statements are provably so?

$\endgroup$
  • 2
    $\begingroup$ This question seems to be based on an incorrect assumption. We have nonconstructive proofs of falsity all the time. For example "There exists a bijection between the reals and the natural" has a rather famously nonconstructive proof. $\endgroup$ – Q the Platypus Mar 19 at 6:59
  • 1
    $\begingroup$ @QthePlatypus Do you have a reference for this "proof" ? $\endgroup$ – DanielV Mar 19 at 7:12
  • 1
    $\begingroup$ Sorry I should have said “Has a famous proof of it’s falsity”. $\endgroup$ – Q the Platypus Mar 19 at 7:25
  • 1
    $\begingroup$ @QthePlatypus Cantor's proof is constructive. It explicitly builds the real number that's not in the bijection using pieces from the previous rows in the hypothetical bijection. $\endgroup$ – ErotemeObelus Mar 19 at 7:35
  • 2
    $\begingroup$ See also math.stackexchange.com/questions/2305177/… $\endgroup$ – Asaf Karagila Mar 19 at 8:31
24
$\begingroup$

That is, how do we know that all false statements are provably so?

This is simply wrong. There are both true and false statements that cannot be proven. What is true is that any sufficiently nice foundational system (i.e. one that has a proof verifier program and can reason about finite program runs) is $Σ_1$-complete, meaning that it proves every true $Σ_1$-sentence. Here, a $Σ_1$-sentence is an arithmetical sentence (i.e. quantifies only over $\mathbb{N}$) that is equivalent to $∃k∈\mathbb{N}\ ( Q(k) )$ for some arithmetical property $Q$ that uses only bounded quantifiers. For example, "There is an even number that is not the sum of two primes." can be expressed as a $Σ_1$-sentence. The "$Σ_1$" stands for "$1$ unbounded existential". Similarly a $Π_1$-sentence is an arithmetical sentence equivalent to one with only $1$ unbounded universal quantifier in Skolem normal form.

In general, if you have a $Π_1$-sentence $C ≡ ∀k∈\mathbb{N}\ ( Q(k) )$, then $¬C$ is a $Σ_1$-sentence. Thus if $C$ is false, $¬C$ is true and hence provable in any sufficiently nice foundational system by $Σ_1$-completeness. This does not apply to all false sentences!

It turns out that non-trivially RH (Riemann Hypothesis) is equivalent to a $Π_1$-sentence, and hence by the above we know that if it is false then even PA (Peano Arithmetic) can disprove it. Also, I should add that no expert believes that it would be any easier to prove unprovability of RH over PA than to directly disprove RH, even if it is false in the first place.

Godel's incompleteness theorem has completely nothing to do with $Σ_1$-completeness. In fact, the generalized incompleteness theorem shows that any sufficiently nice foundational system (regardless of what underlying logic it uses) necessarily is either $Π_1$-incomplete or proves $0=1$. That is, if it is arithmetically consistent (i.e. does not prove $0=1$) then it also does not prove some true $Π_1$-sentence. Moreover, we can find such a sentence uniformly and explicitly (as described in the linked post).

$\endgroup$
  • 3
    $\begingroup$ Thank you for explaining that this implication is non-trivial. I've had so many people act like it's obvious that if RH is false you must be able to produce a counterexample, and look at me like I'm crazy when I ask "What if the only counterexamples are non-definable numbers?" $\endgroup$ – MartianInvader Mar 19 at 20:31
  • $\begingroup$ @MartianInvader: Exactly, and also thank the experts over at MO for making this non-triviality clear. Your objection is in fact a reasonable one and those people who look at you like you're crazy actually don't know the real truths. Next time, bring to them an open $Π_2$-conjecture as a counter-example to their implicit claim. For example, the Twin-prime conjecture says "For every natural $k$ there is some natural $p$ such that both $p$ and $p+2$ are primes. And the Collatz conjecture is also $Π_2$. For both, even if false (with natural number counter-example), we may be unable to disprove it. $\endgroup$ – user21820 Mar 20 at 4:59
  • $\begingroup$ Moreover, there is some evidence that the Collatz conjecture is complicated. Firstly, an obvious generalization with parameters has behaviour undecidable from the given parameters. Secondly, and intriguingly, TMs that generate the Collatz sequence seem to be potential contenders for universality. $\endgroup$ – user21820 Mar 20 at 5:14
  • $\begingroup$ @MartianInvader For more on Collatz and related problems see the links I gave in this comp.theory post on 7 Feb 1996 $\endgroup$ – Bill Dubuque Apr 14 at 19:09
9
$\begingroup$

This argument doesn't show that all false statements are provably so. (That's impossible for trivial reasons: if $P$ is a true statement that's not provable, then $\lnot P$ is a false statement that's not provable.) The argument shows that the Riemann hypothesis, if false, is provably so, because there would be a specific number $s$ (in the critical strip but not on the critical line) at which $\zeta(s)=0$, and so there would exist a proof (show that that specific number is a zero of $\zeta$).

$\endgroup$
  • 7
    $\begingroup$ Note that your final claim is not obvious--even if some number is a zero of $\zeta$, why must it be possible to prove that? It turns out that if such a zero exists then it can always be detected by some finite calculation, but this takes some work to prove. $\endgroup$ – Eric Wofsey Mar 19 at 7:11
  • $\begingroup$ @EricWofsey I agree with you. Still I hope my answer illustrates the logic point being sought. $\endgroup$ – Greg Martin Mar 19 at 7:16
  • $\begingroup$ "a true statement that's not provable" does that even make sense? If it's not provable, what does "true" even mean? $\endgroup$ – Arthur Mar 19 at 12:22
  • $\begingroup$ @Arthur: I can't speak for this answer, but truth is in fact well-defined for arithmetical sentences, and (as per my answer) there is always some true arithmetical sentence that you cannot prove in your chosen foundational system. $\endgroup$ – user21820 Mar 19 at 13:00
  • 1
    $\begingroup$ @RussellMcMahon: I don't understand your "Pi never 'repeats'" hypothesis. If you mean that the decimal representation of $\pi$ never enters an infinitely-repeating loop, then the statement is certainly true, and quite provable by mere mortals: https://en.wikipedia.org/wiki/Proof_that_π_is_irrational. $\endgroup$ – ruakh Mar 20 at 4:19
5
$\begingroup$

Because if you were lucky enough to guess the counterexample, you could just check it. Note that this only works for problems where it's easy to check whether a given value is in fact a counterexample. To take a non-mathematical example, you have no hope of proving you've found a counterexample to "all people are mortal" because you'd have to verify some individual is immortal, meaning you'd have to verify nothing at all can kill them, which isn't possible.

$\endgroup$

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.