FOM: intermediate r.e. degrees

[Piergiorgio Odifreddi]

a few comments on the recent postings of shipman, fenner and simpson.

1) definability in the structure of r.e. degrees

simpson has quoted the paper of nies, shore and slaman, in which it is
proved the definability of the jump classes invariant under double
jump, in particular L_n and H_n for n greater than 1. however, by a
trick, in the same paper it is also proved that H_1 is definable.
cooper has instead announced that L_1 is NOT definable. so even the
remaning two cases are settled. 

in any case, definability in the structure of the r.e. degrees is
natural only to recursion theorists, so this meaning of "natural"
may have little interest for fom readers

2) simple constructions of intermediate r.e. sets

i'm not sure that the construction of friedberg and muchnik is the
simplest or more natural available, independently of its invariance
w.r.t. the underlying coding. one should not forget that when this
solution was obtained, it was not considered satisfactory even by
insiders, since it was perceived as a brute force approach.

post had tried to obtain a solution by defining a "natural" property
of r.e. sets which implied nonrecursiveness and incompleteness, but
had failed. his approach was revitalized in the 70s in the soviet
union, and in 1976 marchenkov obtained a solution to post's problem
in his spirit, by a variation of the notion of hyperhypersimplicity
introduced by post himself. 

the solution is explained in section III.5 of volume I of my book
(classical recursion theory), and it raises two question of naturalness:
one relative to the property of r.e. sets, the other relative to the
proof that one such set exists.

as for the property itself, it is very natural in an informal way
(which i think relevant for fom readers). it is obtained by extending
post's approach of thinning out the complement of an r.e. set, and
adding a missing ingredient to take care of the fact, unforseen by
post, that even the thinnest possible complement (i.e. even a maximal
set) does not necessarily imply incompleteness. actually, the whole
development leading to the solution almost reads like a spy story,
and i tried to write it up as such on pp. 252-304 of my book.

such a property is probably NOT natural in the sense of being definable
in the lattice of the r.e. sets. but this notion of naturalness was
never a concern of post himself: in his work he considered hypersimple
sets, which are provably not definable in this sense, and 
hyperhypersimple sets, which are indeed definable in this sense, but
in a very unexpected and surprising way that could not have been
foreseen by post (these developments are related in volume II of my
book, chapter IX).

however, soare and harrington have found some years ago a property
that is definable in the lattice of the r.e. sets, and which implies
nonrecursiveness and incompleteness. such a property is natural in
this technical sense, but it may look quite unnatural to outsiders,
i.e. in the informal sense, unlike marchenkov's property quoted 
above.

turning now to the question of naturalness of the construction of
a set satisfying marchenkov's property, it could be claimed that it
is MORE natural than the original friedberg and muchnik solution. 
obviously, the same problems of coding dependence arise here as
there. but the construction involves much less machinery and it 
relies on the socalled e-state method, which is much simpler to
understand that the general priority method. obviously, much of this
relies on taste. but it is a fact that i gave the marchenkov's
solution in detail very early on in my book (chapter III, volume I),
without waiting the introduction of the priority method (chapter X,
volume II). 

in particular, the construction is a modification of the original
construction of a simple set given by post, and of the construction
of a maximal set given by friedberg. but it is SIMPLER than the 
latter, since it does not try to make the set maximal (basically,
it constructs an equivalence relation w.r.t. which the set is
maximal, instead of trying to make it maximal w.r.t. the equality
relation). 

as fom readers might be aware, there are solutions to post's problem
that do NOT use the priority method, due to kucera. the interested
reader can judge by himself whether such a solution is simpler that
the other ones discussed above (section X.4, volume II of my book).
the priority method is here replaced by an appeal to the low basis
theorem, and the permitting method is also needed.