FOM: priority arguments; Kleene-r.e. degrees; Pi01 classes

[Stephen G Simpson]

Response to Joseph Shoenfield, FOM 12 Aug 1999 20:33:14.

This posting of Shoenfield contains much food for thought.  I want to
respond briefly to a few of the scientific points.

[ I have responded off-line to Shoenfield to the points about
``tone'', my administration of the FOM list, etc.  As always, I am
open to off-line discussion of such non-scientific issues, but I would
like the FOM list itself to focus on scientific issues related to
f.o.m. ]

 > I suspect there are many more cases in which a simpler priority
 > argument than that originally used would suffice.

I would like to know more about such cases, where priority arguments
can be simplified or eliminated.  I regard this as an interesting
methodological issue in recursion theory.  (As I said in 13 Aug 1999
15:03:02, I inherited my interest in this kind of methodological issue
long ago from my thesis advisor, Gerald Sacks.)

 > I also think there are more general results, like the Thickness
 > Lemma, which could give a large number of results about RE degrees
 > without further use of priority.

Yes, this would be very desirable indeed.

In order to deal with difficult technical issues in mathematics, a
tried and true approach is to prove one or more ``technical lemmas''
which can be used over and over again in various contexts.  In the
case of priority methods, this has not happened often, and ad hoc
arguments have seemed to predominate.  In software engineering terms,
priority arguments have tended to be ``non-modular''.  Is there any
identifiable reason for this?

Shoenfield's thickness lemma was one of the most successful attempts
at a ``modular'' approach to priority arguments.

 > Finally, I think it would be very desirable to find methods of
 > proving that certain results in RE degree theory could not be
 > proved by certain types of priority arguments.  It seems to me that
 > this might be a question of interest to enthusiasts of Reverse
 > Mathematics.

Well, there is the work on ``reverse recursion theory'' where people
have shown that certain amounts of induction are needed to prove
certain theorems on r.e. degrees.  It appears that more induction is
correlated to more advanced types of priority methods such as infinite
injury.  The most active researchers in this area currently are
Chi-Tat Chong and Yue Yang.

 > There is a vague possibility which has occurred to me of producing
 > a more natural intermediate degree.  There has been some study of
 > degrees of type n objects, mostly by Simpson and his students.  One
 > pleasant feature is that many of the degrees needed are degrees of
 > fairly natural objects.  Perhaps by coding type n objects by type
 > one objects one could transfer these results into ordinary degree
 > theory.  Of course, one cannot fully code a type n object by a type
 > one object; but maybe one could code enough to get the result which
 > one wants.

If A and B are sets of reals, we say that A is Kleene reducible to B
if there exists a real x such that A is Kleene recursive in x, B, E^2
where E^2 is Kleene's type-2 number quantifier.  This has a nice
tie-in to descriptive set theory: A is Kleene-recursive if and only if
A is Borel, and A is Kleene-r.e. if and only if A is co-analytic.
Thus Kleene-r.e. degrees represent a natural way of classifying
analytic sets ``modulo Borel computations''.

Set theory comes in here, because if sharps exist then intermediate
Kleene-r.e. degrees do not exist.  But under assumptions such as V = L
or V = a forcing extension of L, natural examples of intermediate
Kleene-r.e. degrees can be obtained.  This work was published in the
1970's by me and others.  (But many of the researchers in this area
were not my students!)

This is interesting stuff, to me at least, but I have no clue of how
to push these ideas down to get natural examples of r.e. degrees.

 > The lack of many applications outside of RE degree thery and the
 > lack of natural examples of RE degrees are, of course, disappointing
 > to the priority theorists; but I don't think they imply (as Simpson
 > and Friedman seem to think) that they show that priority theory is
 > not worth studying.   

I don't think the structure of the r.e. degrees is not worth studying.
But the lack of applications and the lack of natural examples are
serious disadvantages, which cannot be swept under the rug.  My gut
feeling about this is that one should respond by looking for some
richer but closely related structure, which does not suffer from these
disadvantages.

How about the structure of the Pi01 subclasses of 2^omega under some
appropriate reducibility relation?  See my posting of 13 Aug 1999
13:42:46.

-- Steve