The complexity of orbits of computably enumerable sets

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

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)

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 92,227

External links

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

Through your library

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
2010-08-30

Downloads
73 (#226,819)

6 months
23 (#120,782)

Historical graph of downloads
How can I increase my downloads?

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

References found in this work

Systems of logic based on ordinals..Alan Turing - 1939 - London,: Printed by C.F. Hodgson & son.
Computable structures and the hyperarithmetical hierarchy.C. J. Ash - 2000 - New York: Elsevier. Edited by J. Knight.
[Omnibus Review].Rod Downey - 1997 - Journal of Symbolic Logic 62 (3):1048-1055.
Automorphisms of the lattice of recursively enumerable sets.Peter Cholak - 1995 - Providence, RI: American Mathematical Society.

View all 23 references / Add more references