Csdrhrt

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?

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).

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

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.