On isolating r.e. and isolated d-r.e. degrees
M. M. Arslanov, Steffen Lempp, Richard A. Shore · Cambridge University Press eBooks · 1996
Introduction The notion of a recursively enumerable (r.e.) set , i.e. a set of integers whose members can be effectively listed, is a fundamental one. Another way of approaching this definition is via an approximating function { A s } s ∈ w to the set A in the following sense: We begin by guessing x ∉ A >/ i > at stage 0 (i.e. A 0 ( x ) ≥ 0); when x later enters A at a stage s + 1, we change our approximation from A s (x) = 0 to A s +1(x) = 1. Note that this approximation (for fixed) x may change at most once as s increases, namely when x enters A . An obvious variation on this definition is to allow more than one change: A set A is 2- r.e. (or d-r.e. ) if for each x, As(x) change at most twice as s increases. This is equivalent to requiring the set A to be the difference of two r.e. sets A 1 − A 2 . (Similarly, one can define n-r.e. sets by allowing at most n changes for each x .) The notion of d-r.e. and n -r.e. sets goes back to Putnam [1965] and Gold [1965] and was investigated (and generalized) by Ershov [1968a, b, 1970]. Cooper showed that even in the Turing degrees, the notions of r.e. and dr. e. differ: Theorem 1.1. (Cooper [1971[) There is a properly d-r.e. degree, i.e. a Turing degree containing a d-r.e. but no r.e. set. In the eighties, various structural differences between the r.e. and the dr. e. degrees were exhibited by Arslanov [1985], Downey [1989], and others.