Post's Programme for the Ershov Hierarchy
No Thumbnail Available
Date
2006-10-31
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
This paper extends Post's programme to finite levels of the Ershov hierarchy of limit-computable sets. Our initial characterisation, in the spirit of Post's paper from 1944, 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 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, 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 characterisation for n-enumerable degrees is given which only bound enumerable sets A with A''=K'.