Extension theorems, orbits, and automorphisms of the computably enumerable sets

Abstract:

We prove an algebraic extension theorem for the computably enumerable sets, $\mathcal {E}$. Using this extension theorem and other work we then show if $A$ and $\widehat {A}$ are automorphic via $\Psi$, then they are automorphic via $\Lambda$ where $\Lambda \restriction \mathcal {L}^*(A) = \Psi$ and $\Lambda \restriction \mathcal {E}^*(A)$ is $\Delta ^0_3$. We give an algebraic description of when an arbitrary set $\widehat {A}$ is in the orbit of a computably enumerable set $A$. We construct the first example of a definable orbit which is not a $\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 $A$ is simple and $\widehat {A}$ is in the same orbit as $A$, then they are in the same $\Delta ^0_6$-orbit and, furthermore, we provide a classification of when two simple sets are in the same orbit.