The complexity of orbits of computably enumerable sets

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)

Download options

PhilArchive



    Upload a copy of this work     Papers currently archived: 72,743

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Analytics

Added to PP
2010-08-30

Downloads
48 (#240,121)

6 months
1 (#386,989)

Historical graph of downloads
How can I increase my downloads?

References found in this work

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

Model-Theoretic Complexity of Automatic Structures.Bakhadyr Khoussainov & Mia Minnes - 2010 - 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.