Extensions Theorems, Orbits, And Automorphisms Of The Computably Enumerable Sets

We prove an algebraic extension theorem for the computably enumerable sets, E . Using this extension theorem and other work we then show: If A and via # where # # L # (A) # and # # E # (A) is # 3 . We give an algebraic description of when a random set A is in the orbit of a computably enumerable set A. We construct the first example of a definable orbit which is not a # 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 A is in the same orbit as A then they are in the same # -orbit and furthermore provide a classification of when two simple sets are in the same orbit