The nonlow computably enumerable degrees are not invariant in $\mathcal {E}$
Rachel Epstein · Transactions of the American Mathematical Society · 2012
We study the structure of the computably enumerable (c.e.) sets, which form a lattice $\mathcal {E}$ under set inclusion. The upward closed jump classes $\overline {\mathbf {L}}_n$ and $\mathbf {H}_n$ have all been shown to be definable by a lattice-theoretic formula, except for $\overline {\mathbf {L}}_{1}$, the nonlow degrees. 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 of $\mathcal E$. All definable classes of degrees are invariant. We show that $\overline {\mathbf {L}}_{1}$ is not invariant, thus proving a 1996 conjecture of Harrington and Soare that the nonlow degrees are not definable, and completing the problem of determining the definability of each jump class. We prove this by constructing a nonlow c.e. set $D$ such that for all c.e. $A\leq _\textrm {T} D$, there is a low set $B$ such that $A$ can be taken by an automorphism of $\mathcal {E}$ to $B$.