Recursive Properties of Intervals of Recursive Linear Orders
Geoffrey R. Hird · Birkhäuser Boston eBooks · 1993
We investigate the possible recursive properties of intervals, and other suborderings, of recursive linear orders. Let A be a recursive linear order with a co-r.e. interval P. We characterize those (A, P) for which there exists a recursive linear order ℬ and an isomorphism f: ℬ ≅ A such that f -1 (P) is (a) not r.e.; (b) immune; (c) hyperimmune. We give general sufficient conditions for A and the subset P under which there exist such ℬ and f with f -1(P) exhibiting the above properties. We show, that no interval P can be hyperhyperimmune (or even strongly hyperimmune).