FOM: Comment on Pi^0_2 conjectures.

[Soren Riis]

---------------------------------
Comment on Pi^0_2 conjectures.
---------------------------------
In response to Joe Shipmans fascinating project of classifying 
"important problems" and "famous theorems" according to syntactic 
structure, Martin Davis wrote:

> Just wanted to remark that whereas the twin prime conjecture is 
> evidently Pi^0_2, there are Pi^0_1 statements believed (on 
> probabilistic grounds) to be true that imply it.

It seems to me that most Pi^0_2 conjectures which are believed to be 
valid must in fact be implied from Pi^0_1 sentences which also 
are believed to be valid. 

To see this suppose B=\forall x \exists y A(x,y) (*) (where A is 
a formula with all quantifiers bounded) is a conjecture.
From this conjecture we can form a slightly stronger conjecture, 
namely that \forall x \exists y<F(x) A(x,y) for some explicit 
given, strictly increasing, and very fast growing function F. The 
bound F(x) on y does NOT however make it Pi^0_1, because I will 
assume Joe Shipmans classification is over the language 
L=L(0,1,+,\cdot) of arithmetic. It seems however there is a small 
trick here: 

Write (*) as 

C = \forall x,z \exists y \leq z ("F^{-1}z \leq x" or A(x,y))

and define the graph of F^{-1} by a bounded formula (in the language L). 
The sentence C is Pi^0_1, is almost as plausible as B and implies the 
conjecture B. 

In some cases (the Poincare conjecture?) one might have an    
a priori bound on the existential quantifier (by some sufficiently 
fast growing function). In that case the given Pi^0_2-problem 
is (by the same trick) equivalent to a Pi^0_1-problem. 

But even if we do not have any priori bound any Pi^0_2 conjecture  
must be expected to be implied by a valid Pi^0_1 sentence. 
Thus it seems that open Pi^0_2-problems can (at least in practice) 
be reduced to Pi^0_1-problems.

Søren Riis