Extensions Theorems, Orbits, and Automorphisms of the Computably Enumerable Sets

Details Extensions Theorems, Orbits, and Automorphisms of the Computably Enumerable Sets Extensions Theorems, Orbits, and Automorphisms of the Computably Enumerable Sets

2004-08-20

arxiv.org/abs/math/0408279v4

Mathematics

Logic

Comments as of Aug 31, 05: This is now the final final version of the paper. Another section, 5.3, was added to the paper. No

Scientific paper

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 $\hat{A}$ are automorphic via $\Psi$ then they are automorphic via $\Lambda$ where $\Lambda \restriction \L^*(A) = \Psi$ and $\Lambda \restriction \E^*(A)$ is $\Delta^0_3$. We give an algebraic description of when an arbitrary set $\Ahat$ is in the orbit of a \ce 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 $\hat{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.

Affiliated with

Also associated with

No associations

Rating

Extensions Theorems, Orbits, and Automorphisms of the Computably Enumerable Sets does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Extensions Theorems, Orbits, and Automorphisms of the Computably Enumerable Sets, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Extensions Theorems, Orbits, and Automorphisms of the Computably Enumerable Sets will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-713708