Bulletin of Symbolic Logic 14 (1):69 - 87 (2008)

Abstract
The goal of this paper is to announce there is a single orbit of the c.e. sets with inclusion, ε, 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 ε is $\omega _1^{{\rm{CK}}}$ + 1; not all orbits are elementarily definable; there is no arithmetic description of all orbits of ε; for all finite α ≥ 9, there is a properly $\Delta _\alpha ^0 $ orbit (from the proof)
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.2178/bsl/1208358844
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 50,447
Through your library

References found in this work BETA

Systems of Logic Based on Ordinals.Alan Mathison Turing - 1939 - London: Printed by C.F. Hodgson & Son.
[Omnibus Review].Rod Downey - 1997 - Journal of Symbolic Logic 62 (3):1048-1055.

View all 17 references / Add more references

Citations of this work BETA

Model-Theoretic Complexity of Automatic Structures.Bakhadyr Khoussainov & Mia Minnes - 2009 - Annals of Pure and Applied Logic 161 (3):416-426.

Add more citations

Similar books and articles

On Orbits, of Prompt and Low Computably Enumerable Sets.Kevin Wald - 2002 - Journal of Symbolic Logic 67 (2):649-678.
Definable Incompleteness and Friedberg Splittings.Russell Miller - 2002 - Journal of Symbolic Logic 67 (2):679-696.
On the Orbits of Hyperhypersimple Sets.Wolfgang Maass - 1984 - Journal of Symbolic Logic 49 (1):51-62.
Orbits of Hyperhypersimple Sets and the Lattice of ∑03 Sets.E. Herrmann - 1983 - Journal of Symbolic Logic 48 (3):693 - 699.
Computability Results Used in Differential Geometry.Barbara F. Csima & Robert I. Soare - 2006 - Journal of Symbolic Logic 71 (4):1394 - 1410.
On a Problem of Cooper and Epstein.Shamil Ishmukhametov - 2003 - Journal of Symbolic Logic 68 (1):52-64.
Definable Structures in the Lattice of Recursively Enumerable Sets.E. Herrmann - 1984 - Journal of Symbolic Logic 49 (4):1190-1197.

Analytics

Added to PP index
2010-08-30

Total views
38 ( #248,670 of 2,326,404 )

Recent downloads (6 months)
16 ( #38,216 of 2,326,404 )

How can I increase my downloads?

Downloads

My notes