FOM: priority arguments and reverse recursion theory

[Chong Chi Tat]

 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.