The Δ₃⁰-automorphism method and noninvariant classes of degrees
Leo A. Harrington, Robert Irving Soare · Journal of the American Mathematical Society · 1996
A set A A of nonnegative integers is computably enumerable (c.e.) , also called recursively enumerable (r.e.) , if there is a computable method to list its elements. Let E \mathcal {E} denote the structure of the computably enumerable sets under inclusion, E = ( { W e } e ∈ ω , ⊆ ) \mathcal {E} = ( \{ W_e \}_{e\in \omega }, \subseteq ) . Most previously known automorphisms Φ \Phi of the structure E \mathcal {E} of sets were effective (computable) in the sense that Φ \Phi has an effective presentation. We introduce here a new method for generating noneffective automorphisms whose presentation is Δ 3 0 \Delta ^0_3 , and we apply the method to answer a number of long open questions about the orbits of c.e. sets under automorphisms of E \mathcal {E} . For example, we show that the orbit of every noncomputable ( i.e. , nonrecursive) c.e. set contains a set of high degree, and hence that for all n > 0 n>0 the well-known degree classes L n \mathbf {L}_n (the low n _n c.e. degrees) and