and Automorphisms of the Computably Enumerable Sets
Rachel Epstein · 2010
The computably enumerable (c.e.) sets have been central to computability theory since its inception. We study the structure of the c.e. sets, which forms a latticeE under set inclusion. Jump classes, such as the low degrees, allow us to classify the c.e. sets according to their information content. The upward closed jump classes Ln and Hn have all been shown to be denable by a lattice-theoretic formula, except for L1, the nonlow degrees, which is the only jump class whose denability was unknown. We say a class of c.e. degrees is invariant if it is the set of degrees of a class of c.e. sets that is invariant under automorphisms ofE. All denable classes of degrees are invariant. We show that L1 is in fact noninvariant, thus proving a 1996 conjecture of Harrington and Soare in [3] that the nonlow degrees are not denable, and completing the problem of determining the denability of each jump class.