On the Orbits of Computably Enumerable Sets

Peter Cholak; Rod Downey; Leo Harrington

paper

On the Orbits of Computably Enumerable Sets

arXiv:math/0607264

Abstract

The goal of this paper is to show there is a single orbit of the c.e. sets with inclusion, $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 $E$ is $ω_{1}^{C K} + 1; N o t a l l or bi t s a r ee l e m e n t a r i l y d e f inab l e; T h er e i s n o a r i t hm e t i c d escr i pt i o n o f a l l or bi t so f$ \mathcal{E} $; F or a l l f ini t e$ α\geq 9 $, t h er e i s a p r o p er l y$ Δ^0_α$ orbit (from the proof). April 6, 2007, minor changes Nov 20, 2007, minor changes