Finite-lattice characterizability of the $>\omega^2$-fickle (not totally $\omega^2$-c.a.) computably enumerable Turing degrees

The computably enumerable (c.e.) Turing degrees are calibrated by the Downey–Greenberg fickleness hierarchy, which measures how many mind changes the sets in a degree need in a computable approximation. Exactly three levels of this hierarchy are known to be characterizable by finite lattice embeddings: the pentagon $N_5$ characterizes the $>1$-fickle (nonzero) degrees, the seven-element lattice $L_7$ characterizes the $>\omega$-fickle degrees, and the five-element modular lattice $M_3$ characterizes the $\ge\omega^\omega$-fickle degrees. Liling Ko's 2021–2024 work systematically searched for a finite lattice (or finite upper semilattice) whose bounding degrees are exactly the $>\omega^2$-fickle degrees — the first uncharacterized level — and found that every small candidate collapses to an adjacent level or to all nonzero degrees. The open problem is to determine whether such a lattice exists at all: either construct a finite lattice or upper semilattice embeddable in the c.e. degrees whose bounding class is exactly the $>\omega^2$-fickle degrees, or prove that no such lattice exists, as predicted by the Cholak–Ko conjecture that every embeddable finite lattice characterizes one of the already-known classes.

Background

A set is computably enumerable (c.e., classically recursively enumerable) if there is an algorithm listing its elements; its Turing degree measures its unsolvability, and the c.e. degrees $\mathcal{R}_T$ form an upper semilattice (USL): the join $\mathbf{a}\cup\mathbf{b}$, the degree of a computable disjoint union of two c.e. representatives, always exists, but an infimum (meet) of two degrees need not. A finite lattice $L=\langle L,\le,\cap,\cup\rangle$ embeds below a c.e. degree $\mathbf{d}$ if there is an injection of $L$ into the c.e. degrees at most $\mathbf{d}$ preserving order, joins, and meets; one then says $\mathbf{d}$ bounds $L$. By Birkhoff's theorem, a finite lattice is distributive (meets distribute over joins) exactly when it contains neither the pentagon $N_5$ nor the five-element modular diamond $M_3$ as a sublattice, and every finite distributive lattice embeds below every nonzero c.e. degree (Thomason, Lachlan). Non-distributive lattices can fail to embed at all: the lattices $S_8$ (Lachlan–Soare 1980) and $L_{20}$ (Lempp–Lerman 1997) are not embeddable in $\mathcal{R}_T$, and no decision procedure for embeddability of a given finite lattice is known (survey: Lempp–Lerman–Solomon).

The obstruction to embedding a non-distributive lattice is permission: a diagonalization requirement $b\not\le a_0$ that must simultaneously respect a join requirement $b\le a_0\cup a_1$ forces the construction — an infinite priority argument, in which competing requirements are met in a computably enumerable priority order — to wait for enumerations into $a_0$ or $a_1$, so the number of permissions a degree can grant becomes the invariant. Downey and Greenberg (2020) quantified this by fickleness. By Shoenfield's limit lemma, every $\Delta^0_2$ set $A$ (every set computable from the halting problem) has a computable approximation $a(x,s)$ converging to $A(x)$; $A$ is $\alpha$-computably approximable ($\alpha$-c.a.) if the mind changes of $a$ are counted downward along a computable well-ordering of order type $\alpha$ whose Cantor-normal-form function is itself computable (a canonical ordering). $A$ is $\le\alpha$-fickle if it admits such an approximation of order type $\alpha$, and $\alpha$-fickle if $\alpha$ is least such; a Turing degree is $\le\alpha$-fickle if every set it contains is, so a '$>\omega^2$-fickle' degree is one that is not $\le\omega^2$-fickle — equivalently, in the standard terminology, a degree that is not totally $\omega^2$-c.a. Ko uses fickle for Downey–Greenberg's 'properly totally $\alpha$-computably approximable'. The hierarchy collapses to powers of $\omega$: $\alpha$-fickle degrees exist iff $\alpha$ is a power of $\omega$, so the successive levels are $1,\omega,\omega^2,\dots,\omega^\omega,\omega^{\omega+1},\dots$ (all below $\varepsilon_0$).

Three lattice characterizations are known. A c.e. degree bounds $N_5$ iff it is $>1$-fickle (iff nonzero). It bounds the seven-element lattice $L_7$ iff it is $>\omega$-fickle, i.e., not totally $\omega$-c.a.; the equivalent form via critical triples — triples of incomparable elements $a_0,a_1,b$ with $a_0\cup b=a_1\cup b$ and every element below both $a_0$ and $a_1$ below $b$ — is Downey–Greenberg–Weber 2007, and the $L_7$ form (Ko's Figure 4) is credited by Ko and by the Downey–Greenberg–Hammatt survey to an unpublished manuscript of Ambos-Spies and Losert. And it bounds $M_3$ (called $M_5$ in the Downey–Greenberg monograph and survey) iff it is $\ge\omega^\omega$-fickle, i.e., not totally $<\omega^\omega$-c.a. (Downey–Greenberg 2020). These are among the few known natural definability results in the c.e. degrees, and they leave the first intermediate level, $>\omega^2$, uncharacterized. Ko (2021 preprint, journal version 2024) searched exhaustively among lattices that are as short and narrow as $L_7$ and $M_3$ (the $\le3$-direct lattices, generated by three incomparable elements under joins and meets): every one either embeds below all nonzero degrees or characterizes the $>\omega$ or $\ge\omega^\omega$ level. She found three lattices besides $M_3$ that characterize the $\ge\omega^\omega$ level, giving an immediate obstruction (her Corollary 4.1): a structure cannot characterize $>\omega^2$-fickleness if it contains any of these four lattices as a sublattice. Removing meets to form upper semilattices did not help: the specific USLs she analyzed characterize the same degrees as the lattices they come from, motivating her Conjecture 5.2 (meet-removal never changes the characterized class). Larger candidate lattices suggested by Lempp and Lerman (her Figure 10) were rejected via the sublattice obstruction, and Cholak proposed the lattice of her Figure 13 as a remaining candidate, with her Conjecture 6.2 predicting it too demands $\ge\omega^\omega$-fickleness. Her Question 6.1 asks for a systematic lattice-theoretic enumeration of non-distributive lattices free of the four obstruction sublattices. The layering and trace-extension techniques used to prove the $\omega$ and $\omega^\omega$ characterizations do not yet extend to these larger candidates. In the Downey–Greenberg–Hammatt 2021 survey the same issue appears as Question 3.11 — whether the class of totally $\omega^n$-c.a. degrees is naturally definable in the c.e. degrees for any $n>1$ — together with the report that Cholak and Ko conjecture the negative answer: every finite lattice embeddable in the c.e. degrees is bounded by all nonzero degrees, or exactly by the $>\omega$-fickle degrees, or exactly by the $\ge\omega^\omega$-fickle degrees (stated in the survey as the dichotomy between its $L_7$ and $M_5$ classes), so that lattices cannot see any level strictly between $\omega$ and $\omega^\omega$.

Problem Statement

Determine whether there exists a finite lattice $L$ — or, more permissively, a finite upper semilattice (USL) in Ko's sense, a structure $\langle U,\le,\cup,\cap\rangle$ in which the meet $\cap$ need not be total, such as those obtained by deleting some meets from a finite lattice while retaining the embedding requirements attached to the remaining meets and the requirements that the deleted meets do not exist — embeddable into the computably enumerable Turing degrees $\mathcal{R}_T$, such that for every c.e. degree $\mathbf{d}$:

$\mathbf{d}\ \text{bounds an embedding of}\ L \iff\ \mathbf{d}\ \text{is}\ >\omega^2\text{-fickle},$

where $\mathbf{d}$ is $>\omega^2$-fickle iff it is not $\le\omega^2$-fickle, i.e., iff $\mathbf{d}$ contains a set that is not $\omega^2$-computably approximable (equivalently, $\mathbf{d}$ is not totally $\omega^2$-c.a.). A complete answer is either:

(a) an explicit finite lattice or USL $L$ together with proofs of both directions — every $>\omega^2$-fickle c.e. degree bounds an embedding of $L$, and every c.e. degree bounding an embedding of $L$ is $>\omega^2$-fickle; or

(b) a proof that no such finite lattice or USL exists.

Question 6.1 of Ko (2024) asks for a systematic enumeration of non-distributive finite lattices avoiding the four $\ge\omega^\omega$ sublattices of her Corollary 4.1, to which that obstruction is then applied in order to generate $>\omega^2$-candidates; her Conjecture 5.2 asserts that removing meets from a finite lattice never changes the class of c.e. degrees that bound it; and her Conjecture 6.2 asserts that the leading candidate (the lattice of her Figure 13, proposed by Peter Cholak) already characterizes $\ge\omega^\omega$-fickleness and hence fails to reach the $\omega^2$ level.

References

1. Ko, Liling (2021). Towards characterizing the $>\omega^2$-fickle recursively enumerable Turing degrees. arXiv:2109.09215 (v2, 27 November 2021). https://arxiv.org/abs/2109.09215 (source of Question 6.1, Conjectures 5.2 and 6.2, and Corollary 4.1)
2. Ko, Liling (2024). Towards characterizing the $>\omega^2$-fickle recursively enumerable Turing degrees. Annals of Pure and Applied Logic 175(4), article 103403. DOI: 10.1016/j.apal.2023.103403. https://doi.org/10.1016/j.apal.2023.103403 (journal version of the preceding preprint; zbMATH Zbl 7806911)
3. Downey, Rod; Greenberg, Noam (2020). A Hierarchy of Turing Degrees: A Transfinite Hierarchy of Lowness Notions in the Computably Enumerable Degrees, Unifying Classes, and Natural Definability. Princeton University Press. DOI: 10.23943/princeton/9780691199665.001.0001. https://doi.org/10.23943/princeton/9780691199665.001.0001 (origin of the fickleness hierarchy, the collapse theorem, and the $M_3$ characterization)
4. Downey, Rod; Greenberg, Noam; Weber, Rebecca (2007). Totally $\omega$-computably enumerable degrees and bounding critical triples. Journal of Mathematical Logic 7(2), 145–171. DOI: 10.1142/S0219061307000640. https://doi.org/10.1142/S0219061307000640 (level-$\omega$ characterization via critical triples)
5. Downey, Rod; Greenberg, Noam; Hammatt, Ellen (2021). A Hierarchy of Computably Enumerable Degrees, II: Some Recent Developments and New Directions. New Zealand Journal of Mathematics 52, 175–231. DOI: 10.53733/133. https://doi.org/10.53733/133 (Question 3.11 and the Cholak–Ko conjecture)
6. Lempp, Steffen; Lerman, Manuel; Solomon, Reed (2006). Embedding finite lattices into the computably enumerable degrees — a status survey. In: Logic Colloquium '02, Lecture Notes in Logic 27, pp. 206–229; Cambridge University Press online edition 2017. DOI: 10.1017/9781316755723.010. https://doi.org/10.1017/9781316755723.010
7. Lachlan, A. H.; Soare, Robert I. (1980). Not every finite lattice is embeddable in the recursively enumerable degrees. Advances in Mathematics 37(1), 74–82. DOI: 10.1016/0001-8708(80)90027-4. https://doi.org/10.1016/0001-8708(80)90027-4 (the $S_8$ non-embeddability result)
8. Lempp, Steffen; Lerman, Manuel (1997). A finite lattice without critical triple that cannot be embedded into the enumerable Turing degrees. Annals of Pure and Applied Logic 87(2), 167–185. DOI: 10.1016/S0168-0072(96)00031-0. https://doi.org/10.1016/S0168-0072(96)00031-0 (the $L_{20}$ non-embeddability result)
9. Ko, Liling (2021). Nonlowness is independent from fickleness. Computability 10(4), 271–288. DOI: 10.3233/COM-190269. https://doi.org/10.3233/com-190269 (the author's adjacent follow-up; does not touch the lattice problem)
10. Arthur, Katherine; Downey, Rod; Greenberg, Noam (2021). Maximality and collapse in the hierarchy of $\alpha$-c.a. degrees. Computability 10(3), 181–214. DOI: 10.3233/COM-200297. https://doi.org/10.3233/com-200297 (adjacent work on the internal structure of the same hierarchy)