The Complexity of Orbits of Computably Enumerable Sets
The 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 | ||||||||||
| Options |
|
|||||||||
Download options| PhilPapers Archive |
Upload a copy of this paper Check publisher's policy on self-archival Papers currently archived: 5,709 |
| External links |
  Try with proxy. |
| Through your library | Configure |
Similar books and articlesLeo Harrington & Robert I. Soare (1998). Codable Sets and Orbits of Computably Enumerable Sets. Journal of Symbolic Logic 63 (1):1-28.
Peter A. Cholak & Leo A. Harrington (2003). Isomorphisms of Splits of Computably Enumerable Sets. Journal of Symbolic Logic 68 (3):1044-1064.
Kevin Wald (2002). On Orbits of Prompt and Low Computably Enumerable Sets. Journal of Symbolic Logic 67 (2):649-678.
Russell Miller (2002). Definable Incompleteness and Friedberg Splittings. Journal of Symbolic Logic 67 (2):679-696.
Wolfgang Maass (1984). On the Orbits of Hyperhypersimple Sets. Journal of Symbolic Logic 49 (1):51-62.
E. Herrmann (1983). Orbits of Hyperhypersimple Sets and the Lattice of ∑03 Sets. Journal of Symbolic Logic 48 (3):693 - 699.
Peter A. Cholak & Leo A. Harrington (2000). Definable Encodings in the Computably Enumerable Sets. Bulletin of Symbolic Logic 6 (2):185-196.
Leo Harrington & Robert I. Soare (1996). Definability, Automorphisms, and Dynamic Properties of Computably Enumerable Sets. Bulletin of Symbolic Logic 2 (2):199-213.
Michael A. Jahn (1999). Implicit Measurements of Dynamic Complexity Properties and Splittings of Speedable Sets. Journal of Symbolic Logic 64 (3):1037-1064.
Peter A. Cholak & Leo A. Harrington (2002). On the Definability of the Double Jump in the Computably Enumerable Sets. Journal of Mathematical Logic 2 (02):261-296.
Peter Cholak (1990). Boolean Algebras and Orbits of the Lattice of R.E. Sets Modulo the Finite Sets. Journal of Symbolic Logic 55 (2):744-760.
Barbara F. Csima & Robert I. Soare (2006). Computability Results Used in Differential Geometry. Journal of Symbolic Logic 71 (4):1394 - 1410.
Kenneth R. Berger & Edmond A. Murphy (1989). Angular Homeostasis: III. The Formalism of Discrete Orbits in Ontogeny. Theoretical Medicine and Bioethics 10 (4).
Shamil Ishmukhametov (2003). On a Problem of Cooper and Epstein. Journal of Symbolic Logic 68 (1):52-64.
E. Herrmann (1984). Definable Structures in the Lattice of Recursively Enumerable Sets. Journal of Symbolic Logic 49 (4):1190-1197.
Analytics
Monthly downloads
Sorry, there are not enough data points to plot this chart.
|
Added to index2010-08-30Total downloads0Recent downloads (6 months)0How can I increase my downloads? |
My notes
Discussion
