Post's programme for the Ershov hierarchy
by B. Afshari, G. Barmpalias, B. S. Cooper and F. Stephan
Summary
This paper extends Post's programme to finite levels of the
Ershov hierarchy of $\Delta^0_2$ sets. Our initial characterisation, in the spirit of
Post, of the degrees of the immune and hyperimmune $n$-enumerable
sets leads to a number of results setting other immunity properties in the
context of the Turing and wtt-degrees derived from the Ershov hierarchy.
For instance, we show that any n-enumerable hyperhyperimmune set
must be co-enumerable, for each n larger than 1.
The situation with regard to
the wtt-degrees is particularly interesting, as demonstrated by a range
of results concerning the wtt-predecessors of hypersimple sets.
Finally, we give a number of results directed at characterising basic
classes of n-enumerable degrees in terms of natural information content.
For example, a 2-enumerable degree contains a 2-enumerable dense immune set
iff it contains a 2-enumerable r-cohesive set iff it bounds a
high enumerable set. This result is extended to a characterisation of
n-enumerable degrees which bound high enumerable degrees.
Furthermore, a characterization for n-enumerable degrees bounding only low-2
enumerable degrees is given.