[FOM] Re: Absoluteness of Clay prize problems

[Timothy Y. Chow]

"John T. Baldwin" <jbaldwin at uic.edu> wrote:

> I had lunch with a mathematician the other day who opined that the Clay 
> problems were probably all provable
> or refuatable in ZFC.    One way to argue this (without finding proofs) 
> is to give a syntactic analysis showing that the varous statements
> are absolute.  For instance,  I have heard that the Riemann Hypothesis 
> is pi^0_1.  Can anyone provide references on specific
> statements or even better a summary article on this subject.  

I don't completely understand your question; however, I think the 
following observation is relevant.  If one were to prove that (say)
RH is either provable or refutable in ZFC, then one would have almost
reduced RH to a finite computation.  Specifically, one would have
proved that a program that blindly searches for either a proof or
a disproof of RH from ZFC would terminate in a finite amount of time.
(This might not quite "settle" RH, since you need some sort of reflection
principle to get from "ZFC proves RH" to RH itself, but probably most
mathematicians implicitly believe in such a reflection principle.)

In other words, proving that RH is provable or refutable in ZFC would
be an enormous achievement, coming very close to settling RH itself.
And of course, nobody has done anything like this.

As for the fact that RH is Pi^0_1, this follows from Lagarias's result
that RH is equivalent to the statement that for all n,

  sigma(n) <= H_n + exp(H_n) log(H_n),

where sigma is the sum-of-divisors function and H_n is the nth harmonic 
number.  Also, P != NP is easily expressed as a Pi^0_2 sentence: for all
machines and polynomials, there's a SAT instance that is incorrectly
handled.

Tim