On the Orbits of Computably Enumerable Sets

Details On the Orbits of Computably Enumerable Sets On the Orbits of Computably Enumerable Sets

2006-07-11

arxiv.org/abs/math/0607264v4

Mathematics

Logic

Scientific paper

The goal of this paper is to show there is a single orbit of the c.e. sets with inclusion, $\mathcal{E}$, such that the question of membership in this orbit is $\Sigma^1_1$-complete. This result and proof have a number of nice corollaries: The Scott rank of $\mathcal{E}$ is $\omega^{CK}_1+1; Not all orbits are elementarily definable; There is no arithmetic description of all orbits of $\mathcal{E}$; For all finite $\alpha \geq 9$, there is a properly $\Delta^0_\alpha$ orbit (from the proof). April 6, 2007, minor changes Nov 20, 2007, minor changes

Affiliated with

Also associated with

No associations

Rating

On the Orbits of 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 On the Orbits of Computably Enumerable Sets, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Orbits of Computably Enumerable Sets will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-138968