Natural first-order definability of the totally $\omega^n$-c.a. degrees in the computably enumerable degrees for finite $n>1$

The hierarchy of totally $\alpha$-c.a. computably enumerable (c.e.) Turing degrees of Downey and Greenberg classifies c.e. degrees by the mind-change complexity, measured by ordinals below $\varepsilon_0$, of the functions they compute. Exactly two pieces of its finite part are known to be naturally first-order definable in the c.e. degrees: the bottom level, the totally $\omega$-c.a. degrees, via the theorem that a c.e. degree bounds a critical triple iff it is not totally $\omega$-c.a. (2007); and the union of all finite levels, the totally $<\omega^\omega$-c.a. degrees, via embeddings of the diamond lattice $M_3$ (2020). Question 5.6 of the source survey asks whether some intermediate level $\omega^n$ with $n>1$ — the first target being $\omega^2$ — is also (naturally) definable. No definability result is known for any $n>1$, and no proof of a general obstruction is known; the question remains open.

Background

A set of natural numbers is computably enumerable (c.e.) if it is the range of a computable function, and its Turing degree measures what can be computed from it; the c.e. degrees form an upper semilattice $(\mathcal{R},\leq_{\mathrm T},\vee)$ under Turing reducibility and join. By the limit lemma, the functions computable from a c.e. set are exactly the $\Delta^0_2$ functions, each admitting a computable approximation $f_s$ converging to $f$; the number of times the approximation changes its mind on an input is a basic complexity measure. A function $f$ is $\alpha$-computably approximable ($\alpha$-c.a.), for a computable ordinal $\alpha<\varepsilon_0$, if it has a computable approximation whose mind changes on each input are bounded along a computable notation for $\alpha$ (the Ershov hierarchy, made canonical via effective Cantor normal forms so that the notion does not depend on the notation chosen). A c.e. degree $\mathbf{d}$ is totally $\alpha$-c.a. if every function computable from every set of degree $\mathbf{d}$ is $\alpha$-c.a. Downey and Greenberg proved that as $\alpha$ ranges below $\varepsilon_0$ these classes form a strict hierarchy precisely at the powers of $\omega$, that all of them lie inside the low$_2$ degrees (degrees whose second jump equals that of the computable degree), and that the hierarchy unifies the combinatorics of many classical constructions: array computability, multiple permitting, presentations of left-c.e. reals, maximal sets, and more.

A longstanding theme in the study of $\mathcal{R}$ is natural definability: which collections of c.e. degrees are first-order definable in $(\mathcal{R},\leq_{\mathrm T},\vee)$ by a formula expressing a genuine degree-theoretic property, rather than by coding arithmetic. Such results are rare, and the available general definability metatheorems only produce definitions of classes invariant under the double jump — useless here, because all totally $\alpha$-c.a. degrees are low$_2$, so the entire hierarchy sits in a single double-jump class. The hierarchy instead delivers definability through finite-lattice embeddings. A critical triple is a configuration of three incomparable c.e. degrees $a_0,a_1,b$ with $a_0\vee b=a_1\vee b$ such that every degree below both $a_0$ and $a_1$ is below $b$; Downey, Greenberg and Weber proved that a c.e. degree fails to be totally $\omega$-c.a. exactly when it bounds a critical triple, which makes the totally $\omega$-c.a. degrees definable. One level up, the five-element diamond lattice $M_3$ (also called $M_5$ or the 1-3-1 lattice: five elements with three pairwise incomparable middle elements) characterizes the top of the finite part: a c.e. degree bounds a copy of $M_3$ in the c.e. degrees iff it is not totally $<\omega^\omega$-c.a., i.e. iff it computes functions of unbounded finite-level mind-change complexity; hence the union of all totally $\omega^n$-c.a. classes is definable too. A seven-element lattice $L_7$ due to Ambos-Spies and Losert gives yet another characterization of the not-totally-$\omega$-c.a. degrees. In these embedding proofs the lattice contains designated elements, called gates, whose interaction forces controlled streams of mind changes in any embedding; the known gate mechanisms calibrate either $\omega$-many changes (isolating the $\omega$ level) or unboundedly many finite levels (isolating the $<\omega^\omega$ level). Following Question 5.6, the source accompanies the question with an explicitly speculative remark about the shape an affirmative answer might take: a finite lattice or finite partial order $P$ whose embeddability below a c.e. degree would be equivalent to that degree not being totally $\omega^n$-c.a. for a fixed $n>1$ — in the authors' words, what 'would be needed' is 'a lattice or partial ordering whose embedding needed "$n$-gates"', for example at level $\omega^2$ 'a structure whose embedding needed two gates and could not be done with one'; the authors describe this paragraph as speculation.

Between the two definable extremes sit the individual higher levels — totally $\omega^2$-c.a., totally $\omega^3$-c.a., and so on — each strictly between its neighbours. No first-order definition, natural or otherwise, is known for any of them, and no technique is known for separating adjacent finite levels extensionally in the algebra of the c.e. degrees. Question 5.6 of the source survey (restated as Question 3.11 of the authors' 2021 sequel survey) asks whether any of these intermediate levels is naturally definable at all. The source also notes that if the requirement of naturalness is dropped, more delicate coding methods — of the style of Nies, Shore and Slaman, possibly involving strong reducibilities — might define these levels.

Problem Statement

Does there exist a finite $n>1$ such that the class of totally $\omega^n$-c.a. degrees is (naturally) first-order definable in the structure $(\mathcal{R},\leq_{\mathrm T},\vee)$ of computably enumerable (c.e.) Turing degrees — the upper semilattice of c.e. degrees ordered by Turing reducibility $\leq_{\mathrm T}$ with join $\vee$? Here a c.e. degree $\mathbf{d}$ is totally $\omega^n$-c.a. if every function computable from every set of degree $\mathbf{d}$ admits a computable approximation whose number of mind changes on each input is bounded along an effective Cantor normal form for $\omega^n$; 'naturally definable' means definable by a first-order formula with one free degree variable in the language $(\leq_{\mathrm T},\vee)$ of the degree structure, expressing a genuine degree-theoretic or lattice-theoretic property rather than by coding models of arithmetic — the informality of the adjective 'natural' is faithful to the source's parenthetical '(naturally)'. Because the question is existential in $n$, a positive answer for any single finite $n>1$ resolves it affirmatively; a negative answer must rule out a natural definition for every finite $n>1$, and hence presupposes a formalization of the informal adjective 'natural'. In particular, showing that the finite-lattice route fails — for instance, proving the conjecture of Cholak and Ko, recorded in the authors' 2021 sequel survey, that every finite lattice embeddable into the c.e. degrees characterizes only the 'not totally $\omega$-c.a.' or the 'not totally $<\omega^\omega$-c.a.' degrees — would establish only that finite-lattice embeddings cannot be used to answer the question, leaving the question itself open; no lattice-embedding impossibility result confined to a single level (including $n=2$) resolves it. The first example considered in the source and in subsequent work is the first nontrivial intermediate level, $n=2$: the totally $\omega^2$-c.a. degrees.

References

1. Rod Downey and Noam Greenberg, 'A hierarchy of computably enumerable degrees', Bulletin of Symbolic Logic 24(1):53–89, 2018. DOI 10.1017/bsl.2017.41, https://doi.org/10.1017/bsl.2017.41 (source paper)
2. Rod Downey and Noam Greenberg, 'A Hierarchy of Turing Degrees: A Transfinite Hierarchy of Lowness Notions in the Computably Enumerable Degrees, Unifying Classes, and Natural Definability', Annals of Mathematics Studies, Princeton University Press, 2020. DOI 10.23943/princeton/9780691199665.001.0001, https://doi.org/10.23943/princeton/9780691199665.001.0001
3. Rod Downey, Noam Greenberg, and Ellen Hammatt, 'Hierarchy of Computably Enumerable Degrees II', New Zealand Journal of Mathematics 52:175–231, 2021. DOI 10.53733/133, https://doi.org/10.53733/133
4. Rod Downey, Noam Greenberg, and Rebecca Weber, 'Totally ω-computably enumerable degrees and bounding critical triples', Journal of Mathematical Logic 7(2):145–171, 2007. DOI 10.1142/s0219061307000640, https://doi.org/10.1142/s0219061307000640
5. Liling Ko, 'Towards characterizing the >ω²-fickle recursively enumerable Turing degrees', Annals of Pure and Applied Logic 175(4):103403, 2024. DOI 10.1016/j.apal.2023.103403, https://doi.org/10.1016/j.apal.2023.103403 (arXiv:2109.09215, https://arxiv.org/abs/2109.09215)
6. Liling Ko, 'Towards Finding a Lattice that Characterizes the ω-Fickle Recursively Enumerable Turing Degrees', Bulletin of Symbolic Logic 27(4):528, 2021 (ASL abstract). DOI 10.1017/bsl.2021.56, https://doi.org/10.1017/bsl.2021.56
7. Liling Ko, 'Nonlowness is independent from fickleness', Computability 10(4):271–288, 2021. DOI 10.3233/com-190269, https://doi.org/10.3233/com-190269
8. Katherine Arthur, Rod Downey, and Noam Greenberg, 'Maximality and collapse in the hierarchy of α-c.a. degrees', Computability 10(3):181–214, 2021. DOI 10.3233/com-200297, https://doi.org/10.3233/com-200297
9. Klaus Ambos-Spies, Rod G. Downey, Martin Monath, and Keng Meng Ng, 'Notes on Sacks' splitting theorem', The Journal of Symbolic Logic, published online 26 October 2023, pp. 1–30. DOI 10.1017/jsl.2023.77, https://doi.org/10.1017/jsl.2023.77
10. Klaus Ambos-Spies and Nadine Losert, 'Universally array noncomputable sets', unpublished manuscript; no DOI or URL available.
11. Sapir Ben-Shahar, Rodney G. Downey, and Mariya Soskova, 'On quasi-reducibility for c.e. sets Part I. The structure of the $Q$-degrees and the $sQ$-degrees', Journal of Logic and Computation 36(1):article exaf076, 2026. DOI 10.1093/logcom/exaf076, https://doi.org/10.1093/logcom/exaf076
12. Klaus Ambos-Spies, Rod Downey, and Martin Monath, 'Lowness properties for strong reducibilities and the computational power of maximal sets', Computability 13(1):1–56, 2024 (published online 2 October 2023). DOI 10.3233/com-220432, https://doi.org/10.3233/com-220432
13. Michael McInerney and Keng Meng Ng, 'Multiple genericity: a new transfinite hierarchy of genericity notions', Israel Journal of Mathematics 250(1):1–51, 2022. DOI 10.1007/s11856-022-2331-5, https://doi.org/10.1007/s11856-022-2331-5
14. Nikolay Bazhenov, Manat Mustafa, Sergei Ospichev, and Luca San Mauro, 'How to approximate fuzzy sets: mind-changes and the Ershov Hierarchy', Synthese 201(2):article 55, 2023. DOI 10.1007/s11229-023-04056-y, https://doi.org/10.1007/s11229-023-04056-y