FOM: priority arguments and reverse recursion theory
Chong Chi Tat
scicct at leonis.nus.edu.sg
Sun Jul 23 02:24:31 EDT 2000
I would like to respond to Harvey Friedman's recent posting on the
use of priority arguments under weak induction assumptions such as
I\Sigma_1 (\Sigma_1 induction).
As pointed out by Simpson and Slaman, (finite injury) priority
arguments have been used to prove the Friedberg-Muchbik Theorem (by
Simpson, unpublished) and the Sacks Splitting Theorem (by
Mytillinaios) using only I\Sigma_1. In the latter case, Mourad showed
that Sacks splitting and I\Sigma_1 are actually equivalent, over the
base theory B\Sigma_1 (\Sigma_1 bounding: the range of any \Sigma_1
function on a finite set is finite).
From the point of view of reverse recursion theory, this is
interesting since it relates a method (finite injury priority
argument) to an axiom (\Sigma_1 induction).
There are two directions that one can go from here:
1. One can come up with an argument as to why I\Sigma_1 is probably
the weakest theory needed to carry out a finite injury argument. For
example, the Friedberg-Muchnik (F-M) construction involves a certain
\Sigma_1 relation that is defined on a cut, And this relation can be
extended to the entire universe if and only if I\Sigma_1
holds. Slaman and Groszek have provided an analysis of this
phenomenon in an inpublished paper on \Pi_1 constructions.
2. One may separate the method from the theorem, e.g. establishing the
F-M Theorem under a thegry strictly weaker than I\Sigma_1, without the
use of priority argument (of course). In this connection, Mourad and
Chong showed that F-M is a theorem of B\Sigma_1. The natural question
to ask is then whether I\Sigma_0 + Exp + F-M is equivalent to
B\Sigma_1, or where does F-M fit in the hierarchy of theires.
Infinite injury priority arguments may also be studied this
way. Groszek and Slaman have also studied this. The Density Theorem
is known to be a theorem of B\Sigma_2 (Groszek, Mytillinaios and
Slaman), but fails in B\Sigma_1 (Mourad: There exists a minimal
r.e. degree). It is not known if it is a theorem of I\Sigma_1 (though
it holds for certain special I\Sigma_1 models). Since I\Sigma_1 does
not provide an environment where infinite injury arguments may be
carried out in general, it becoems a good candidate to see if one can
separate the theorem from the (infinite injury priority) method.
More information about the FOM
mailing list