FOM: Natural degrees

[Joseph Shoenfield]

     I think that recent discussions about the existence of a natural
intermediate RE degree have been marred by a lack of explanation of
what is meant by natural.   The trouble is that "natural" has so
many different meanings in common usage.   I'm sure you have all
seen in recent times such statements as "Oral sex is not natural" or
"Natural foods are healthiest".   I presume none of the fom corres-
pondents want to be lumped with the people who argue for such doubtful
propositions; they should therefore explain more clearly their cri-
teria for naturalness.
     There is one common feature of the above uses of natural: the
assumption that whatever natural means, what is natural is good.   I
see some signs of this assumption in some of the communications to
fom, which seem to argue that if there is no natural intermediate
RE degree, then there is something wrong or deficient in the study
of RE degrees.   To justify such a claim, it is not merely necessary
to explain the meaning of natural; it is necessary to explain why
lack of this type of naturalness is a deficiency in a theory.
     There is a notion of naturalness for degrees which has been fre-
quently used by specialists in the field: an RE degree is natural if it
is definable in the theory of RE degrees.   (For this purpose, we take
the language of this theory to have < as its only non-logical symbol.
One could add further notation, such as symbols for sups and infs; this
might or moght not change the set of natural degrees.)
     Some correspondents have dismissed this notion as "technical" or
"not of interest in fom".   I don't know what they mean by "technical",
except that it, unlike "natural", is a bad word.   Certainly the study
of what concepts can be defined in various important languages has
been of continual interest in many branches of mathematical logic:
recursion theory, model theory, set theory.
     There is another sense of naturalness for degrees which comes up
in several communications.  An important theme in recursion theory
since the beginning has been to show that certain RE sets which arise
in a great variety of situations are non-recursive.   In every case,
the degree of the set is 0'.   It would be of great interest to either
produce such a set which has intermediate degree, or to give a good
explanation why the degree always is 0'.   I think it likely that it
is because, while we have many ways of constructing RE sets, we have
essentially only one method of proving them non-recursive, the diagonal
argument.   (This seems also to explain the difficulty in proving P
is not NP.)