Extension theorems, orbits, and automorphisms of the computably enumerable sets
Peter A. Cholak, Leo A. Harrington · Transactions of the American Mathematical Society · 2007
We prove an algebraic extension theorem for the computably enumerable sets, E \mathcal {E} . Using this extension theorem and other work we then show if A A and A ^ \widehat {A} are automorphic via Ψ \Psi , then they are automorphic via Λ \Lambda where Λ ↾ L ∗ ( A ) = Ψ \Lambda \restriction \mathcal {L}^*(A) = \Psi and Λ ↾ E ∗ ( A ) \Lambda \restriction \mathcal {E}^*(A) is Δ 3 0 \Delta ^0_3 . We give an algebraic description of when an arbitrary set A ^ \widehat {A} is in the orbit of a computably enumerable set A A . We construct the first example of a definable orbit which is not a Δ 3 0 \Delta ^0_3 orbit. We conclude with some results which restrict the ways one can increase the complexity of orbits. For example, we show that if