On the orbits of computably enumerable sets

DOI10.1090/S0894-0347-08-00604-8MaRDI QIDQ3058264zbMATH OpenOpenAlexFDO

Authors Peter A. Cholak, Rodney G. Downey, Leo Harrington

Publication date 19 November 2010

Published in Journal of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0705.0125

zbMATH Keywords

automorphismBoolean algebracomputably enumerable setisomorphismorbitScott ranksimple settree

Mathematics Subject Classification ID

Recursively (computably) enumerable sets and degrees (03D25)

Abstract: The goal of this paper is to announce there is a single orbit of the c.e. sets with inclusion, $E$, such that the question of membership in this orbit is $Sigm{a}_1^1$-complete. This result and proof have a number of nice corollaries: the Scott rank of $E$ is $wock+1$; not all orbits are elementarily definable; there is no arithmetic description of all orbits of $E$; for all finite $alphageq9$, there is a properly $Delt{a}_a^{0}lpha$ orbit (from the proof). A few small corrections made in this version

Recommendations

• The Complexity of Orbits of Computably Enumerable Sets
• There is no fat orbit
• Codable sets and orbits of computably enumerable sets
• Extension theorems, orbits, and automorphisms of the computably enumerable sets
• The computably enumerable sets: recent results and future directions

Cites work

• Automorphisms of the lattice of recursively enumerable sets. I: Maximal sets
• Automorphisms of the lattice of recursively enumerable sets: Orbits
• Codable sets and orbits of computably enumerable sets
• Computable structures and the hyperarithmetical hierarchy
• Extension theorems, orbits, and automorphisms of the computably enumerable sets
• scientific article; zbMATH DE number 4091484 (Why is no real title available?)
• scientific article; zbMATH DE number 194101 (Why is no real title available?)
• Isomorphisms of splits of computably enumerable sets
• ON THE DEFINABILITY OF THE DOUBLE JUMP IN THE COMPUTABLY ENUMERABLE SETS
• On the Lattice of Recursively Enumerable Sets
• On the orbits of hyperhypersimple sets
• Post's program and incomplete recursively enumerable sets.
• Realizing levels of the hyperarithmetic hierarchy as degree spectra of relations on computable structures
• Some orbits for \({\mathcal E}\)
• The Δ₃⁰-automorphism method and noninvariant classes of degrees
• Π₁¹ relations and paths through

Cited in

(16)

• The dense simple sets are orbit complete with respect to the simple sets
• Some orbits for \({\mathcal E}\)
• Orbits of computably enumerable sets: Low sets can avoid an upper cone
• There is no fat orbit
• \(\mathcal{D}\)-maximal sets
• 2011 North American Annual Meeting of the Association for Symbolic Logic, University of California at Berkeley, Berkeley, CA, USA, March 24--27, 2011
• On orbits, of prompt and low computably enumerable sets
• Codable sets and orbits of computably enumerable sets
• Definable Encodings in the Computably Enumerable Sets
• There is no classification of the decidably presentable structures
• Isomorphisms of splits of computably enumerable sets
• The Complexity of Orbits of Computably Enumerable Sets
• Extension theorems, orbits, and automorphisms of the computably enumerable sets
• The computably enumerable sets: recent results and future directions
• Some recent research directions in the computably enumerable sets
• The isomorphism problem for torsion-free abelian groups is analytic complete

This page was built for publication: On the orbits of computably enumerable sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3058264)