On isolating r.e. and isolated d-r.e. degrees

Summary

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₀(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₁ − A₂. (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.