On the Orbits of Computably Enumerable Sets
Loading...
Date
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Description
The goal of this paper is to show there is a single orbit of the c.e. sets with inclusion, $\mathcal{E}$, such that the question of membership in this orbit is $Σ^1_1$-complete. This result and proof have a number of nice corollaries: The Scott rank of $\mathcal{E}$ is $ω^{CK}_1+1; Not all orbits are elementarily definable; There is no arithmetic description of all orbits of $\mathcal{E}$; For all finite $α\geq 9$, there is a properly $Δ^0_α$ orbit (from the proof).
April 6, 2007, minor changes
Nov 20, 2007, minor changes