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

Simple item page
dc.creatorCholak, Peter
dc.creatorHarrington, Leo
dc.date2004-08-20
dc.date2005-08-31
dc.date.accessioned2026-07-07T05:11:26Z
dc.date.available2026-07-07T05:11:26Z
dc.descriptionWe 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 $Ψ$ then they are automorphic via $Λ$ where $Λ\restriction Ł^*(A) = Ψ$ and $Λ\restriction \E^*(A)$ is $Δ^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 $Δ^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 $Δ^0_6$-orbit and furthermore we provide a classification of when two simple sets are in the same orbit.
dc.descriptionComments 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 other change were made. This section was added to allow a clean clear inferface with the sequel. Comments as of March 31, 05: This is now the final version of this paper. (Section 7 was rewritten. A few other lemmas were added.)
dc.identifierhttps://arxiv.org/abs/math/0408279
dc.identifierhttp://arxiv.org/abs/math/0408279
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/72240
dc.subjectLogic
dc.subject03D25
dc.titleExtensions Theorems, Orbits, and Automorphisms of the Computably Enumerable Sets
dc.typetext

Files

Collections

arXiv