FOM: Priority

[Joseph Shoenfield]

     As one who has been involved in priority theory since its
inception, I have been pleased to see a discussion of applications
of this theory in fom.    I must say I have not been pleased by
the tone of some of the discussion, especially the debate between
Simpson and Soare.   This has mostly consisted of angry arguments
over who made what errors, how serious the errors were, who has
apologized for which errors, who originated the error, and so on.
To be blunt, I find the whole thing boring and irrelevant to matters
of interest.   I hope both participants will henceforth restrict
themselves to statements which at least might throw some light on
fom.
     By the way, my criticism of Simpson applies only to his
communications, not to his actions as the moderator of fom.    If
I understand the situation correctly, he initially allowed almost
any communications, but later found it necessary to reject some
communications for such reasons as irrelevance to fom or excessive
personal attacks.   I have the impression he has tried to avoid
rejecting communications outright, and has instead written to
the writer suggesting possible modifications or omissions.   I
have no criticism of his actions as a moderator except, perhaps,
his failure in some cases to apply his excellent standards to his
own communications.
     I found many of the applications mentioned quite interesting,
and only regretted that more wasn't said about them so I could
better appreciate how priority is involved.   There were a few
cases in which it was clearly a strech to say priority was involved.
For example, one correspodent gave an example of an application of
priority with no injury.   This may fit the common use of the word
priority, but I don't think it can be called priority theory.   The
idea of the original priority arguments was to show that each con-
dition is injured only finitely often, and the conditions were such
that a finite number of injuries did no harm.   When it became clear
that not all problems could be solved this way, people considered 
cases in which there were infinitely many injuries but that, because
of the nature of the set of injuries and the conditions, no harm was
done.    In finite injury, the proof of no harm was simple and the
same in all cases.   In infinite injury, is was often complicated
and varied from case to case, although several general principles
could be seen.   There is still plenty of room for investigations
of these general principles and when they apply.
     A difficult question is: What kind of priority argument is
needed to prove various reults?   For example, the existence of a
high RE degree below 0' was for long viewed as a basic example of
a result which required infinite injury; but the Jockusch and Shore
showed it could be done by finite injury, more exactly, by two
successive used of a finite injury argument.   I suspect there
are many more cases in which a simpler priority argument than
that originally used would suffice.   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.    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.
     The most important and difficult applications of priority
theory have, of course, been in the field of RE degrees.   The
first application was to show that this field is non-trivial.
For some time after that, it was disappointing that the results
obtained about RE degrees had little interest on their own.   For
example, the result obtained by Lachlan in his difficult Monster
Theorem did not seem at the time of too much interest, although
subsequent developments of the result were crucial in proving
non-decidability of the theory of RE degrees.   In any case, more
recent results are in some cases of great interest.   For example,
Cooper has proved two outstanding results: that the jump is defi-
nable in the theory of degrees and that the structure of the RE
degrees has a non-trivial automorphism.   Both of these problems
are quite old, and are of obvious interest to anyone interested
in the structure of the set of degrees.
  As to applications of degrees outside the study of degrees,
there have not been as many as one would like.   I wrote an
article about forty years ago, trying to describe what sort of
applications are possible and giving two example (not themselves
of very great interest).   I will let the interested reader (if
any) consult the article in the 1960 International Congress of
the IUHPS.
     Let me say a word about a question which came up in
some of the communications on priority theory: is there a natural
RE degree other than 0 and 0'?   Of course, it all depends on what
on means by natural.   However, it seems to me that the fact that
it took so much effort to prove such a degree exists shows that
in some sense, there is no such natural degree.   Of course,
one might find a very natural degree in which the complication was
in proving that it is intermediate; but this seems unlikely at this
stage.   In any case, I think Friedman is correct in saying that
Cooper's arguments are beside the point.   For example, consider
the result of Hanf (cited by Cooper): for every RE degree there is
a finitely axiomatizable theory of that degree.   This is one of my
favorite papers; I recommend it to all of you.   But it does not
really tell us anything about degrees; it tells us about the nature
of finitely axiomatizable theories.   This nature is still somewhat
of a mystery, despite interesting results by Kleene and model
theorists such as Zilber.   But I do not see how Hanf's finitely
axiomatizable theory (which, roughly speaking, describes a non-
standard Turing machine) can be considered as natural.
   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.
     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.   Natural examples and applications are only two
of the many reasons for examining a theory.