Cototal enumeration degrees and their applications to effective mathematics
Ethan McCarthy · Proceedings of the American Mathematical Society · 2017
A set $A\subseteq \omega$ is cototal under enumeration reducibility if $A\le _e \overline {A}$, that is, if the complement of $A$ is total. We show that the $e$-degrees of cototal sets characterize the $e$-degrees of maximal anti-chain complements, the $e$-degrees of enumeration-pointed trees on $2^{<\omega }$, and the $e$-degrees of languages of minimal subshifts on $2^\omega$. As a consequence, we obtain a characterization of the Turing degree spectra of nontrivial minimal subshifts: they are the enumeration cones of cototal sets. From the perspective of the Turing degrees, this provides a complete understanding of the computational power of minimal subshifts. We also obtain an application to computable structure theory, showing that the enumeration cones of cototal sets characterize those structure spectra which are Turing-upward closures of $F_\sigma$ sets of reals.