FOM: Comment on Pi^0_2 conjectures.
Soren Riis
sriis at fields.fields.utoronto.ca
Sun Apr 19 10:20:29 EDT 1998
---------------------------------
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
More information about the FOM
mailing list