[FOM] Actual Logical Complexity

[Joe Shipman]

The Poincaré conjecture is straightforwardly Pi^0_2 but to get it down to Pi^0_1 requires advanced topological considerations, rather than general principles.

-- JS

Sent from my iPhone

> On Mar 24, 2016, at 9:44 PM, Harvey Friedman <hmflogic at gmail.com> wrote:
> 
> What is the actual logical complexity of theorems that have been cited
> for the Fields Medal? And for other awards? Of course, much larger
> sets of theorems can be considered from this point of view, but those
> cited for Fields Medals and other major awards seem more realistically
> manageable to analyze. How has this changed over time (if it has)?
> 
> I am taking about the usual classification
> 
> Pi01, Pi02, Pi03, Pi04, ...
> 
> Sigma01, Sigma02, Sigma03, Sigma04,...
> 
> Pi11, Pi12, Pi13, Pi14, ...
> 
> Sigma11, Sigma12, Sigma13, Sigma14
> 
> and higher.
> 
> Now there is a problem in making this reasonably precise. After a
> Theorem is proved, the Theorem becomes provably equivalent to 0 = 0,
> which is in both Pi01 and Sigma01.
> 
> So we have to be a bit careful just how we talk about this.
> 
> One way of talking about this in a reasonable way is to look at the
> Theorem and see what is the lowest form you are able to put it in,
> where the equivalence is by general considerations that do not involve
> the ideas from the proof of the Theorem.
> 
> Of course, this is a bit awkward, and maybe sounds judgmental. BUT I
> claim that it is a rough enough guide and that matters are robust
> enough, that one can informatively make these calculations.
> 
> If things turn out for some reason not to be as robust as expected in
> some situations, then that can be given special analysis.
> 
> CONJECTURE. The complexity levels for theorems cited for Fields Medal
> and related awards have been generally going down over time, and are
> as indicated below. Actually, I am NOT all that confident in my
> instincts here, and am quite interested in seeing what people find
> when they actually look. I just haven't had the time to take a real
> look.
> 
> 1. Pi01. I think this is most common. Most famously, FLT. Riemann
> Hypothesis, still open, is Pi01 by reasonably general considerations.
> However, using yet more general considerations, perhaps you would not
> get down to Pi01. But what would you get down to via various
> considerations? And how should we deal with this robustness issue
> here?
> 
> One way is to step back and expand the problem. So we are looking at
> complex functions defined by nice series, and stating some nice
> property of the complex function. Well, without dealing specifically
> with the Riemann Zeta Function, what can you say about such questions
> in terms of logical complexity? If you pick the right level of
> generality, presumably you can get precise math logic results about
> complexity here.
> 
> Then there is Poincare Conjecture, again Pi01 by fairly general
> considerations. Once again, step back and expand the problem, and see
> what complexity you get, also with an eye to exact math logic
> complexity results.
> 
> There are many situations like this to explore. Also Goldbach's conjecture.
> 
> 2. Pi02. Most famously, Twin Prime Conjecture. But it should be
> factored in that there are obvious stronger conjectures that are down
> to Pi01. The expectation is that any proof would prove such stronger
> statements.
> 
> 3. Pi03. I think a lot of stuff in Diophantine Approximation, and also
> stuff in Diophantine Equations where you only get "at most finitely
> many solutions".  Roth's theorem, Mordell stuff.
> 
> 4. Other arithmetic statements. I don't know if we are going to find
> Pi04. By the way, the whole field of finite group theory. Is this all
> Pi01 and sometimes Sigma01?
> 
> 5. Now what is cited in Fields Medals and other Awards that is not
> arithmetic? Well, what about countable infinite combinatorics? And
> infinite graph theory? Here it would seem that one runs across Pi11,
> and also Pi12. There will also probably be sometimes, that there are
> stronger statements that are arithmetic, and that needs to be factored
> in.
> 
> 6. What about cited results in ergodic theory? Of course, often, and
> probably usually, the use of measure is really by general
> considerations far closer to the computational than would be indicated
> by the usual set theoretic development of measure theory. So I expect
> that general considerations would push this cited stuff down into the
> Pi01.
> 
> 7. What about Fields Medals and other Awards in functional analysis
> and operator theory? Here there is of course the best chance of seeing
> stuff that is not only arithmetic, but maybe not even Pi11. Or maybe
> much worse. Of course, there is the continuum hypothesis, but that was
> not a theorem. Instead, Cohen won the award for a relative consistency
> proof, which was of a Pi01 statement. So Cohen was Pi01.
> 
> Harvey Friedman
> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> http://www.cs.nyu.edu/mailman/listinfo/fom