# Towards characterizing the $>\omega^{2}$-fickle
recursively enumerable Turing degrees

Liling Ko<EMAIL_ADDRESS>[

###### Abstract

Given a finite lattice $L$ that can be embedded in the recursively enumerable
(r.e.) Turing degrees
$\langle\mathcal{R}_{\mathrm{T}},\leq_{\mathrm{T}}\rangle$, it is not known
how one can characterize the degrees $\mathbf{d}\in\mathcal{R}_{\mathrm{T}}$
below which $L$ can be bounded. Two important characterizations are of the
$L_{7}$ and $M_{3}$ lattices, where the lattices are bounded below
$\mathbf{d}$ if and only if $\mathbf{d}$ contains sets of “ _fickleness_ ”
$>\omega$ and $\geq\omega^{\omega}$ respectively. We work towards finding a
lattice that characterizes the levels above $\omega^{2}$, the first non-
trivial level after $\omega$. We considered lattices that are as “short” and
“narrow” as $L_{7}$ and $M_{3}$, but the lattices characterize also the
$>\omega$ or $\geq\omega^{\omega}$ levels, if the lattices are not already
embeddable below all non-zero r.e. degrees. We also considered upper
semilattices (USLs) by removing the bottom meet(s) of some previously
considered lattices, but the removals did not change the levels characterized.
This leads us to conjecture that a USL characterizes the same r.e. degrees as
the lattice it is based on. We discovered three lattices besides $M_{3}$ that
also characterize the $\geq\omega^{\omega}$-levels. Our search for a
$>\omega^{2}$-candidate therefore involves the lattice-theoretic problem of
finding lattices that do not contain any of the four
$\geq\omega^{\omega}$-lattices as sublattices.

###### keywords:

recursively enumerable , Turing degrees , fickleness , computable
approximation , hierarchy , lattice , embedding

###### MSC:

03D25 , 03D55

††journal: Annals of Pure and Applied Logic

url]sites.nd.edu/liling-ko/

## Acknowledgements

This work has been partially supported by Peter Cholak’s NSF grant
DMS-1854136, and also by funding from Rosalie O’Mahony for women in
Mathematics in the University of Notre Dame. The author is grateful to Steffen
Lempp for valuable discussion, and indebted to Peter Cholak for his support
over many years.

##  1 Introduction

A long standing open problem in the study of the recursively enumerable (r.e.)
Turing degrees $\langle\mathcal{R}_{\mathrm{T}},\leq_{\mathrm{T}}\rangle$
involves identifying the lattices $\mathcal{L}=\langle
L,\leq,\cap,\cup\rangle$ that can be embedded in $\mathcal{R}_{\mathrm{T}}$,
and characterizing the degrees below which such $L$ can be bounded. Here, a
lattice is a partial order $\leq$ such that every pair of elements
$\mathbf{a},\mathbf{b}\in L$ has a join $\mathbf{a}\cup\mathbf{b}\in L$, which
is the lowest upper bound of the pair, and a meet $\mathbf{a}\cap\mathbf{b}\in
L$, which is the greatest lower bound of the pair. It is known that
$\langle\mathcal{R}_{\mathrm{T}},\leq_{\mathrm{T}}\rangle$ forms an upper
semilattice (USL) with minimal element $\mathbf{0}$ and greatest element
$\mathbf{0}^{\prime}$. As an USL, the join between any pair must exist, but
the meet may not (Ambos-Spies, 1984). By the minimal pair priority argument
(Yates, 1966; Lachlan, 1966), one can construct incomparable pairs whose meet
exists, and therefore embed the diamond lattice (Figure 1) in
$\mathcal{R}_{\mathrm{T}}$. One can also generalize the construction to embed
below any nonzero r.e. degree, any lattice that does not contain $N_{5}$ or
$M_{3}$ (Figure 2) as sublattices (Thomason, 1971; Lachlan, 1972). Lattices
that avoid $N_{5}$ and $M_{3}$ are called _distributive_ lattices (Birkhoff,
1937), because they can be characterized as lattices $L$ whose meets
distribute over the joins:

$(\forall\mathbf{a},\mathbf{b},\mathbf{c}\in
L)\;\;[\mathbf{a}\cap(\mathbf{b}\cup\mathbf{c})=(\mathbf{a}\cap\mathbf{b})\cup(\mathbf{a}\cap\mathbf{c})].$

$\mathbf{a}\cap\mathbf{b}$$\mathbf{a}$$\mathbf{a}\cup\mathbf{b}$$\mathbf{b}$
Figure 1: The diamond lattice can be embedded in $\mathcal{R}_{\mathrm{T}}$
(Yates, 1966; Lachlan, 1966).

There is no known procedure for deciding if a given non-distributive lattice
can be embedded in $\mathcal{R}_{\mathrm{T}}$. To sketch the challenges faced,
consider Birkhoff’s representation Theorem 1.2:

######  Definition 1.1.

Let $L$ be a finite lattice.

  1. 1.

An element $\mathbf{b}\in L$ is _join-irreducible_ if
$\mathbf{b}=\mathbf{a_{0}}\cup\mathbf{a_{1}}$ implies
$\mathbf{b}=\mathbf{a_{0}}$ or $\mathbf{b}=\mathbf{a_{1}}$.

  2. 2.

An element $\mathbf{b}\in L$ is _join-prime_ if
$\mathbf{b}\leq\mathbf{a_{0}}\cup\mathbf{a_{1}}$ implies
$\mathbf{b}\leq\mathbf{a_{0}}$ or $\mathbf{b}\leq\mathbf{a_{1}}$.

######  Theorem 1.2 (Birkhoff’s Representation (Birkhoff, 1937)).

Non-distributive lattices must contain a join-irreducible element that is not
join-prime.

For $N_{5}$ and $M_{3}$, the witnesses to Birkhoff’s theorem are shown in
Figure 2 as $\mathbf{b}\leq\mathbf{a_{0}}\cup\mathbf{a_{1}}$, which cannot be
computed by $\mathbf{a_{0}}$ or $\mathbf{a_{1}}$. When we construct an r.e.
set $B$ whose degree $\mathbf{b}$ satisfies these requirements, the
diagonalization condition $\mathbf{b}\nleq\mathbf{a_{0}}$ forces us to
enumerate elements into $B$. However, the join requirement
$\mathbf{b}\leq\mathbf{a_{0}}\cup\mathbf{a_{1}}$ says that whenever we
enumerate into $B$, we must also enumerate into $A_{0}$ or $A_{1}$. Therefore,
at least two permissions are requested — one for $B$ and another for $A_{0}$
or $A_{1}$. Distributive lattices work to the effect of involving no joins, so
a single permission is enough, allowing any nonzero r.e. degree to bound the
lattice. In non-distributive lattices, joins prevent sets from being
constructed independently. These dependencies can become complicated or even
contradictory, preventing some lattices, such as $S_{8}$ (Lachlan and Soare,
1980) and $L_{20}$(Lempp and Lerman, 1997) (Figure 3), from being embedded at
all.

The important non-distributive lattices that are known to be embeddable
include $N_{5}$, $M_{3}$, and $L_{7}$. The ability for an r.e. degree
$\mathbf{d}$ to bound these lattices depends only on the “ _fickleness_ ” of
the sets in $\mathbf{d}$, with degrees that bound $N_{5}$ ($L_{7}$, $M_{3}$)
being exactly those that contain sets of fickleness $>1$ ($>\omega$,
$\geq\omega^{\omega}$) (Downey et al., 2007; Ambos-Spies and Losert, 2019;
Downey and Greenberg, 2020). Here, set fickleness can be thought of as the
number of times elements change their minds on their membership in the set.
For instance, r.e. sets have fickleness $\leq 1$ since elements are allowed to
enter but not exit, and in a similar vein, $n$-r.e. sets have fickleness $\leq
n$. Sets in an r.e. degree that are not r.e. may have fickleness $\geq\omega$,
and we define a degree’s fickleness to be the smallest ordinal $\alpha$ that
bounds the fickleness of all sets in the degree. We formalize these
definitions in Section 1.1 (Downey and Greenberg, 2020).

$\mathbf{a_{0}}$$\mathbf{b}$$\mathbf{a_{1}}$$N_{5}$$\mathbf{a_{0}}$$\mathbf{a_{1}}$$\mathbf{b}$$M_{3}$
Figure 2: Non-distributive lattices are those that contain $N_{5}$ or $M_{3}$
as sublattices (Birkhoff, 1937). $S_{8}$$L_{20}$ Figure 3: $S_{8}$ (Lachlan
and Soare, 1980) and $L_{20}$ (Lempp and Lerman, 1997) cannot be embedded in
$\mathcal{R}_{\mathrm{T}}$. $L_{7}$ Figure 4: An r.e. degree bounds $L_{7}$ if
and only if it contains an $>\omega$-fickle set (Downey et al., 2007; Ambos-
Spies and Losert, 2019).

The fickleness hierarchy of the r.e. degrees was introduced by Downey and
Greenberg in 2020, and was based on Ershov’s work on $n$-r.e. sets (Eršov,
1968a, b, 1970). The hierarchy collapses exactly to the powers of $\omega$,
making the first few levels at $1$, $\omega$, $\omega^{2}$, $\ldots$,
$\omega^{\omega}$, $\omega^{\omega+1}$, $\ldots$ (Downey and Greenberg, 2020),
where the 1-fickle r.e. degrees contains just the zero degree. From earlier
discussion, all known lattices characterize fickleness at the $>1$, $>\omega$,
or $\geq\omega^{\omega}$-levels, which begs the question of whether there are
lattices that characterize the degrees above the second non-trivial level
$\omega^{2}$. This is the motivation of our work and the question remains
open.

We search for $>\omega^{2}$-candidates by considering lattices that are as “
_short_ ” and “ _narrow_ ” as $L_{7}$ and $M_{3}$, like those in Figure 5. In
Section 2, we discuss the fickleness that is sufficient for bounding these
lattices, and in Section 3 we discuss the fickleness that is necessary.
Including $M_{3}$, we now have four lattices that characterize
$\geq\omega^{\omega}$-fickleness. In Section 4, we use these four to quickly
reject “larger” candidates, for $>\omega^{2}$-candidates cannot contain any of
those four overly fickle ones as sublattices. In Section 5, we consider some
USLs as candidates, obtained by removing the meet(s) of earlier lattices. We
show that these USLs characterize the same degrees as their lattices, which
leads us to conjecture in 5.2 that all USLs behave this way. We suggest future
work in Section 6.

###  1.1 Defining $\alpha$-fickleness

We formalize what it means for an r.e. set or degree to be $\alpha$-fickle. By
Shoenfield’s Limit Lemma, every $\Delta^{0}_{2}$ set $A$ has a _computable
approximation_ $a(x,s):\omega^{2}\to\omega$, such that for all $x,s\in\omega$:

$A(x)=\lim_{s}a(x,s).$

We “count” how often $a(x,-)$ changes its mind:

######  Definition 1.3 ((Eršov, 1968a, b, 1970)).

Let $\mathcal{R}=(R,<_{\mathcal{R}})$ be a computable well-ordering (both $R$
and $<_{\mathcal{R}}$ are computable), and let $A$ be a $\Delta^{0}_{2}$ set.
An $\mathcal{R}$-computable approximation ($\mathcal{R}$-c.a.) of $A$ is a
computable approximation $a(x,s):\omega^{2}\to\omega$ of $A$ together with a
computable _mind-change function_ $m(x,s):\omega^{2}\to R$, such that for all
$x$ and $s$:

  * 1.

$a(x,0)=0$,

  * 2.

$m(x,s+1)\leq_{\mathcal{R}}m(x,s)$,

  * 3.

if $a(x,s+1)\neq a(x,s)$, then $m(x,s+1)<_{\mathcal{R}}m(x,s)$.

We think of $\alpha$ as the order type of $R$. $a$ is a computable guessing
function for $A$, and $m$ associates an ordinal with each guess, so the
initial ordinal $m(x,0)$ should represent $\alpha$. Like in the usual
approximation for r.e. sets, the set is empty at first, so our first guess is
$a(x,0)=0$ to represent that $x\notin A$. If $a(x,s+1)\neq a(x,s)$, then the
ordinal must decrease. After the first mind-change, the ordinal is represented
by an element of $R$.

The ideas behind this definition were first formalized by Ershov (Eršov,
1968a, b, 1970), who referred to a set as $\alpha$-r.e. if $\alpha$ is the
order type of $\mathcal{R}$, and if $\mathcal{R}$ satisfied the additional
computable structure of being represented by a notation. Ershov’s notion of
being $\alpha$-r.e. was defined for $\alpha<\omega_{1}^{\mathrm{CK}}$. There
is an equivalent version given by Epstein et al., and there is another version
given by Ash and Knight.

For the notion of fickleness to be independent from the $\mathcal{R}$ used,
even stronger computable structure needs to be imposed on $\mathcal{R}$. To
these ends, Downey and Greenberg required $\mathcal{R}$ to be _canonical_ ,
which is stronger than having a notation:

######  Definition 1.4 (Downey and Greenberg (2020)).

Let $\mathcal{R}$ be a computable well-ordering with _order type_ $\alpha$.
Given $z\in R$, let $|z|$ denote the order type of $z$. Let
$\mathrm{nf}_{\mathcal{R}}:\omega\rightarrow(\omega^{2})^{<\omega}$ denote the
function that takes each ordinal below $\alpha$ to its Cantor-normal form;
i.e. $\forall z\in R$

$\mathrm{nf}_{\mathcal{R}}(z)=\langle\langle z_{0},n_{0}\rangle,\ldots,\langle
z_{i},n_{i}\rangle\rangle,$

where $z_{j}\in R$, $|z_{0}|>\ldots>|z_{i}|$, $n_{j}\in\omega-\\{0\\}$, and

$|z|=\omega^{|z_{0}|}\cdot n_{0}+\ldots+\omega^{|z_{i}|}\cdot n_{i}$

is the unique Cantor-normal form of $|z|$. If $\mathrm{nf}_{\mathcal{R}}$ is
computable, we say that $\mathcal{R}$ is _canonical_.

######  Definition 1.5 (Downey and Greenberg (2020)).

Let $A,\mathbf{d}\in\Delta^{0}_{2}$.

  1. 1.

$A$ is _$\leq\alpha$ -fickle_ if $A$ has a canonical $\mathcal{R}$-c.a. of
order type $\alpha$.

  2. 2.

$A$ is _$\alpha$ -fickle_ if $\alpha$ is the smallest ordinal such that $A$ is
$\leq\alpha$-fickle.

  3. 3.

$\mathbf{d}$ is _$\leq\alpha$ -fickle_ if every set in $\mathbf{d}$ is
$\leq\alpha$-fickle.

  4. 4.

$\mathbf{d}$ is _$\alpha$ -fickle_ if $\alpha$ is the smallest ordinal such
that $\mathbf{d}$ is $\leq\alpha$-fickle.

Note that being $\alpha$-fickle was first introduced by Downey and Greenberg
as being _properly totally $\alpha$-computably approximable_. We use the term
fickleness for succinctness. By canonicalness, if $\alpha$ is _reasonably
small_ :

$\alpha<\epsilon_{0},\mathrm{where}\epsilon_{0}=\sup\\{\omega,\omega^{\omega},\omega^{\omega^{\omega}},\ldots\\},$

then in Definition 1.5, the choice of $\mathcal{R}$ would not matter (Downey
and Greenberg, 2020), because we would be able to switch from one computable
approximation to another recursively. Restricting to smalls ordinals is enough
for now because the embeddability results discussed do not involve ordinals
exceeding $\omega^{\omega}<\epsilon_{0}$. Also, note that when a set $A$ is
$\alpha$-fickle for some $\alpha\geq\omega$, the “number of mind changes” of
the set is actually still finite, in the sense that $\lim_{s}A(x,s)$ exists
for all $x\in\omega$; nonetheless the smallest canonical computable
approximation for $A$ has an infinite order type.

The fickleness hierarchy collapses to the powers of $\omega$:

######  Theorem 1.6 (Downey and Greenberg (2020)).

Let $\alpha\leq\epsilon_{0}$. $\alpha$-fickle degrees exist if and only if
$\alpha$ is a power of $\omega$. Also, an r.e. degree is 1-fickle if and only
if the degree is the zero degree.

Recall that the r.e. degrees that bound $N_{5}$ ($L_{7}$, $M_{3}$) are exactly
those that contain sets of fickleness $>1$ ($>\omega$, $\geq\omega^{\omega}$
respectively). From Theorem 1.6, the first non-trivial level that has not been
characterized is at $\omega^{2}$, which makes our search for a
$>\omega^{2}$-lattice meaningful.

###  1.2 Some “Short” and “Narrow” Lattices

We consider $>\omega^{2}$-candidates that are as “short” and “narrow” as
$L_{7}$ and $M_{3}$. We introduce the notion of _3-directness_ to describe
such smallish lattices:

######  Definition 1.7.

A lattice $L$ is _$n$ -direct_ if $L$ contains $n$ incomparable elements
$\mathbf{a_{0}},\ldots,\mathbf{a_{n-1}}$, and every element in $L$ is of the
form $\bigcup_{i\in I}\mathbf{a_{i}}$ or $\bigcap_{i\in I}\mathbf{a_{i}}$,
where $I\subseteq\\{0,\ldots,n-1\\}$.

For instance, $L_{7}$ is 3-direct because we can name the middle element
$\mathbf{a_{1}}$ and the two at the side $\mathbf{a_{0}}$ and
$\mathbf{a_{2}}$. Then the top element will be
$\mathbf{a_{0}}\cup\mathbf{a_{1}}=\mathbf{a_{0}}\cup\mathbf{a_{2}}=\mathbf{a_{1}}\cup\mathbf{a_{2}}$,
the lower two elements will be $\mathbf{a_{0}}\cap\mathbf{a_{1}}$ and
$\mathbf{a_{1}}\cap\mathbf{a_{2}}$, and the bottom element will be
$\mathbf{a_{0}}\cap\mathbf{a_{2}}=\mathbf{a_{0}}\cap\mathbf{a_{1}}\cap\mathbf{a_{2}}$.
Figure 10 gives two lattices that are not 3-direct, for they each contain more
than three incomparable elements.

$\geq\omega^{\omega}$$>\omega$$>0$$\underbrace{\hskip
227.62204pt}_{\mathrm{distributive}}$ Figure 5: All $\leq 3$-direct lattices
(Definition 1.7) are exhausted here, grouped by the fickleness levels
characterized. We include also the diamond, which is the only $\leq 2$-direct
lattice, if we ignore trivial lattices such as the single point. Lattices
including and to the right of the diamond are distributive.

In Figure 5, we exhibit some $\leq 3$-direct lattices, which turns out to
exhaust all of them (Ko, 2021). Eight of them are distributive and can
therefore be embedded below any nonzero r.e. degree (Thomason, 1971).
Excluding $L_{7}$ and $M_{3}$, we are left with seven non-distributive
lattices to characterize in the next two sections.

##  2 Some Lattices where $>1$ or $\geq\omega^{\omega}$-Fickleness is
Sufficient

We can apply the techniques in (Downey and Greenberg, 2020) to show:

######  Lemma 2.1.

The four lattices at the top row of Figure 5, which includes $M_{3}$, can be
bounded below any r.e. degree that contains $\geq\omega^{\omega}$-fickle sets.

Known methods can also show:

######  Lemma 2.2.

The first three lattices in the bottom row of Figure 5 can be bounded below
any non-zero r.e. degree.

Lemma 2.2 is an application of the methods in (Lerman et al., 1984). The
authors introduced a lattice-theoretic property known as the _Trace-Probe
Property_ (TPP), which is sufficient for a lattice to be embeddable in
$\mathcal{R}_{\mathrm{T}}$. It is not hard to show that their TPP embedding
technique is compatible with nonzero permitting. The three lattices satisfy
TPP, and can therefore be bounded below any nonzero r.e. degree. The fourth
lattice in the bottom row, enlarged in Figure 6, does not satisfy TPP. But we
can still prove:

######  Lemma 2.3.

The lattice in Figure 6 can be bounded below any non-zero r.e. degree.

In the rest of this section, we shall prove the lemma by modifying the TPP
techniques, and applying nonzero permitting. The fickleness requested by a
lattice comes from its positive requirements $\rho$. If $\rho$ requests for
$n$ many permissions, then any set that can grant $\geq n$ permissions can
satisfy $\rho$. In TPP lattices, $n\in\omega$ is a constant, while in the
lattice of Lemma 2.3, $n$ is bounded by $|\rho|\in\omega$. Since nonzero r.e.
sets can grant $n$ many permissions for any fixed $n$, both types of lattices
can be bounded below any nonzero degree.

$D$$A$$AC$$C$$B$$AB$$BC$$\begin{array}[]{rrclll}\mathrm{Join:}&B&\leq&ACD,\\\
\mathrm{Diagonalize:}&A&\nleq&BCD,&&a\\\ &B&\nleq&AD,&&bc\to ba\to\ldots\\\
&B&\nleq&CD,&&ba\to bc\to\ldots\\\ &C&\nleq&ABD,&&c\\\
\mathrm{Meet:}&ABD&\cap&BCD&\leq BD,\\\ &BCD&\cap&AD&\leq D,\\\
&ABD&\cap&CD&\leq D.\end{array}$ Figure 6: Here is a lattice that can be
bounded below any non-zero r.e. degree. $\rho:B\nleq AD$ generates traces of
length two that retarget between $BC$ and $BA$-traces, where the number of
times we re-target is bounded by $|\rho|$. In particular, by the notation of
Lerman et al. (1984), this lattice is not a TPP lattice because the bound is
not independent from $\rho$.

To see how $|\rho|$ comes about, we need to observe the interactions between
$\rho$ and other requirements, such as with negative requirements $\eta$, and
with joins $J$. We borrow notations from Downey et al. (2007); Downey and
Greenberg (2020); Lempp (2012); Ambos-Spies and Losert (2019); Lempp et al.
(2006). In these constructions, $\rho$ generates sequences of elements that
need to be enumerated. The sequences are referred to as _traces_ , and each
element in a trace is often referred to as a _ball_. The process of
enumerating can be thought of as balls falling to the bottom of a pinball
machine, into buckets that represent each ball’s targeted set. Often, longer
traces are _partitioned_ into shorter ones, so that when the balls in a trace
are enumerated simultaneously, $\eta$ will not be injured in an unforeseeable
manner. A trace can be as short as a single ball in length. Each trace
enumeration must be permitted by the set bounding the lattice. A permission is
granted when the set changes its mind, or in other words, when the set loses
one fickleness. Henceforth, we shall use the terms “permissions” and
“fickleness” interchangeably. Therefore, the length of the traces generated by
$\rho$ bounds the fickleness sufficient for embedding $L$. As we shall see,
these lengths do not exceed $|\rho|$.

Let $X$ be an r.e. set of nonzero degree. We want to construct r.e. sets
$A,B,C,D\leq X$ satisfying the requirements in Figure 6. To derive these
requirements, we use $AB$ to abbreviate $A$ join $B$. We also let the r.e. set
that represents a point on the lattice be the join of its label, with the sets
of labels below it. For instance, the point labelled $A$ will be represented
by $AD$, the join of sets $A$ and $D$, while the point labelled $AC$ will be
represented by $ABCD$. This rule preserves the partial orders of the lattice,
allowing us to omit requirements such as $D\leq A$ for instance, since $D\leq
AD$. Because of this rule, to express “$B\leq AC$”, which says that the join
of the points $A$ and $C$ computes $B$, we use the requirement $B\leq ACD$.
Also, note that we omitted requirements that can be derived from those listed
in the figure. For instance, $BD\nleq AD$ holds if and only if $B\nleq AD$
holds, so we omit the longer version.

Fix a computable ordering of the requirements. We shall use a $\Pi_{2}$ tree
framework in our construction. First, consider the global requirements
$A,B,C,D\leq X$, where we construct functionals
$\Psi_{A},\Psi_{B},\Psi_{C},\Psi_{D}$ to satisfy:

$\displaystyle G_{A}:$ $\displaystyle\;A=\Psi_{A}(X),$ $\displaystyle G_{B}:$
$\displaystyle\;B=\Psi_{B}(X),$ $\displaystyle G_{C}:$
$\displaystyle\;C=\Psi_{C}(X),$ $\displaystyle G_{D}:$
$\displaystyle\;D=\Psi_{D}(X).$

We describe the strategy for $G_{A}$ only; the remaining $G$-strategies are
similar.

$G_{A}$-strategy: _Initialize_ $G_{A}$ by setting $\Psi=\Psi_{A}=\emptyset$.
Start with $a=0$.

  1. 1.

_Set up_ : At stage $a$, some positive requirement $\rho$ might pick $a$ as a
follower and assign a _code_ $i$ to $a$. Set use $\psi(a)=i$. At the next
stage start a new cycle with $a+1$.

  2. 2.

_Maintain_ : Finitely often, $\rho$ might want to lift the use $\psi(a)$ or
even enumerate $a$ into $A$. _Permission is granted by $X$_ to take those
actions at the stage when $X\restriction\psi(a)$ changes. With permission,
$\rho$ may also change the code of $a$ to $i^{\prime}$, and we update the use
to $\psi(a)=i^{\prime}$.

Note that it is possible for many elements to be assigned the same code. These
elements wait for the same permission from $X$ to be enumerated, and if they
come from the same follower of a positive requirement, they will be enumerated
together.

Next, consider the join requirement, which is also global, where we construct
functional $K=K_{B}$ such that

$\displaystyle J_{B}:B$ $\displaystyle=K_{B}(ACD).$

Since this lattice has no other join requirements, we drop the subscript $B$.

$J$-strategy: _Initialize_ $J$ by setting $K=\emptyset$. Start with $n=0$.

  1. 1.

_Set up_ : At some stage $\geq n$, pick a large value as use $\kappa(n)$
targeted for $A$, $C$, or $D$, and set $K(n)=0$ with that use. The choice of
the target will depend on the positive requirement $\rho$, if any, with which
$n$ is associated. Start a new cycle with $n+1$. Note that $n$ is targeted for
$B$, and as mentioned in the $G$-strategies, $n$ will be assigned by other
requirements a code $i$. Assign the same code to $\kappa(n)$.

  2. 2.

_Maintain_ : We may _lift the use at $n$_ by enumerating $\kappa(n)$ into $A$,
$C$, or $D$, then choosing a new large $\kappa(n)$. With the new use, we
declare $K(n)=0$ if $n$ has been enumerated into $B$, otherwise we declare
$K(n)=1$. The new use will be targeted for one of $A$, $C$, or $D$ again.
Depending on $\rho$, the choice of the target may change, and we refer to this
change as _re-targeting_. Whenever we lift the use, the requirement that
wanted the lifting may assign to the new use a new code. We will need to
ensure that $\rho$ does not lift $\kappa(n)$ infinitely often.

Consider the meet requirements $\eta$, where we construct $\Theta$ such that:

$\displaystyle\eta_{\Phi W}:$
$\displaystyle\Phi_{0}(ABD)=\Phi_{1}(BCD)=W\implies(\exists\Theta)[W=\Theta(BD)],$
$\displaystyle\eta_{BA\Phi W}:$
$\displaystyle\Phi_{0}(BCD)=\Phi_{1}(AD)=W\implies(\exists\Theta)[W=\Theta(D)],$
$\displaystyle\eta_{BC\Phi W}:$
$\displaystyle\Phi_{0}(ABD)=\Phi_{1}(CD)=W\implies(\exists\Theta)[W=\Theta(D)].$

We drop subscripts if context is clear. Consider $\eta_{BA}$, also referred to
as _$BA$ -gates_, because $B$ and $A$ appear on opposite sides of the gate,
which as we shall see, generally forbids $B$\- and $A$-balls from being
enumerated at the same time. Similarly, $\eta_{BC}$ is often referred to as a
$BC$-gate. Maintaining a computation $W(m)=\Theta(m)$ at subrequirement
$\eta_{AB},m$ involves protecting the computation at the $BCD$-side
$\Phi_{0}(BCD,m)$, or the $AD$-side $\Phi_{1}(AD,m)$. In the $BA$-gate, if the
hypothesis $\Phi_{0}=\Phi_{1}=W$ holds, we want to ensure that $W\leq D$, and
hence refer to $D$ as a _computing set(s)_ of the gate. Similarly, the
computing sets of the two other types of gates are $BD$ and $D$.

A gate’s strategy is based on the minimal pair strategy of (Yates, 1966),
where whenever both sides of a computation are simultaneously injured, say at
subrequirement $m$, an element $\leq\theta(m)$ must enter a computing set,
which we refer to as the use $\theta(m)$ being _lifted_ :

$\eta$-strategy: _Initialize_ $\eta$ by setting $\Theta=\emptyset$ and $m=0$
and _use_ $\theta(m^{\prime})$ to be undefined for all $m^{\prime}\in\omega$.

  1. 1.

_Set up_ : Wait for _equality_

$\Phi_{0}\restriction(m+1)=\Phi_{1}\restriction(m+1)=W\restriction(m+1)$

at $m$ for the first time, say at stage $s_{0}$. Start a new phase at set up
for the $(m+1)$-th subrequirement.

  2. 2.

_Maintain_ : When equality is first observed or has returned and $\theta(m)$
does not exist, assign a new large value for $\theta(m)$. Whenever
$\Phi_{0}(m)$ or $\Phi_{1}(m)$ is injured by a follower that existed at stage
$s_{0}$, and an element $\leq\theta(m)$ enters a computing set at the same
time, we lift the use by declaring $\theta(m)$ to be undefined. Then we wait
for the next $\eta$-stage before returning to the beginning of this
maintenance phase to pick a new large use.

To verify that $\eta$ is satisfied, we would like to show that the only
elements that can injure $\Phi_{0}(m)$ or $\Phi_{1}(m)$ are those that existed
at stage $s_{0}$. Also, $\Phi_{0}(m)$ and $\Phi_{1}(m)$ cannot be injured
together unless $\theta(m)$ is lifted. Note that if equality at $m$ never
returns, $\eta$ would be satisfied vacuously. If the hypothesis of the gate
holds, we will need to show that the use is not lifted infinitely often. We
shall provide such a verification in Lemma 5.6 for a more complex
construction.

Now, consider the diagonalization or positive requirements, say $B\not\leq
AD$. Given functional $\Xi$, we satisfy

$\rho_{\Xi}:B\neq\Xi(AD).$

$\rho:B\neq\Xi(AD)$ $bc_{0}$ $BA\mathrm{-gate}$ $BA\mathrm{-gate}$
$BC\mathrm{-gate}$ $b\cancel{c_{0}}$ $BA\mathrm{-gate}$ $b\cancel{a_{0}}$
$BC\mathrm{-gate}$ $b\cancel{c_{1}}$ $BA\mathrm{-gate}$ $b\cancel{a_{1}}$
$b\cancel{c_{2}}$ $\begin{array}[]{rclll}B&\leq&ACD\end{array}$ Figure 7:
Traces generated by $\rho$, after interacting with the join on the right, and
with gates depicted by a horizontal line. Gates of higher priority are drawn
lower down. Whenever the trace meets consecutive $BA$\- and $BC$-gates, it is
re-targeted between $BC$\- and $BA$-traces. Therefore, the total fickleness
requested does not exceed $|\rho|$. In this toy example, the length of a
stopped trace does not exceed 2. In more complex constructions, traces can be
arbitrarily long, like those in Figure 8.

The strategy is built on the usual Friedberg Muchnik approach, where we pick a
follower $b$, wait for $b$ to be _realized_ when $\Xi(b)=0$, set a restraint
of $\xi(b)$ on $AD$ to prevent un-realization, then wait for permission from
$X$ to enumerate $b$ into $B$. But the joins and gates complicate this
enumeration. Consider how $\rho=\rho_{\Xi}$ interacts with $J$ and with higher
priority $BA$-gates and $BC$-gates. Refer to Figure 7 for an illustration.
Assume $\rho$ has a follower $b$ that is realized at stage $s_{0}$. We want to
enumerate $b$ into $B$ at the same time prevent elements $\leq\xi(b)$ from
entering $AD$. But $J$ says that before we can enumerate $b$, we need to
enumerate $\kappa(b)$ into targets $A$, $C$, or $D$. If $b$ was realized after
$J$ chose $\kappa(b)$, then $\xi(b)>\kappa(b)$ and we cannot choose $A$ or $D$
as targets otherwise we will un-realize $b$. So we can only target $C$. So we
want to enumerate $c_{0}=\kappa(b)$ into $C$, then $b$ into $B$. We think of
these elements $c_{0}$ and $b$ as _balls_ falling past gates of a pinball
machine, to be collected by their target sets $C$ and $B$ respectively. The
enumeration of the $B$-ball demanded that a $C$-ball be enumerated first, and
we say that the $B$-ball generates an _$BC$ -trace_.

One might be tempted to enumerate the $BC$-trace simultaneously. But
$BC$-gates prevent us from doing so, unless the gate’s use $d$ targeted for
$D$ is lifted at the same time. But if $d$ was picked before $b$ got realized,
then $d<\xi(b)$ cannot be lifted without un-realizing $b$. Thus the $BC$-gate
forces us to enumerate the balls in the $BC$-trace separately and in reverse,
starting from the $C$-ball, say at stage $s_{1}\geq s_{0}$. We say that the
trace is _stopped_ by the $BC$-gate from simultaneous enumeration. After
enumerating $c_{0}$, we have to wait for the $C$-side computation of stopping
gate to recover at some stage $s_{2}>s_{1}$, before we can enumerate the
$B$-ball. When recovery has occurred, we say that the $BC$-gate has
_reopened_. While waiting for recovery, $J$ requires that we pick a new large
use to be re-targeted to $A$, $C$, or $D$. The new target cannot be on the
$C$-side of the $BC$-gate; otherwise, when the new use is enumerated later, we
will injure the $C$-side again. Therefore we cannot re-target to $C$ or $D$,
and are forced to choose $A$. Thus we re-target $bc_{0}$ to a $BA$-trace
$ba_{0}$. In other words, once $c_{0}$ is enumerated, we need to pick an
$A$-ball $a_{0}$ and wait for it to be enumerated into $A$, before we are
allowed to enumerate $b$ into $B$. After the $C$-enumeration, the trace is no
longer stopped by the $BC$-gate, and we say that it has _passed_ the gate.

After the $C$-side of the $BC$-gate recovers, one might again be tempted to
enumerate the $BA$-trace $ba_{0}$ simultaneously when permitted. But higher
priority $BA$-gates disallows $B$\- and $A$-balls from being enumerated
together. We say that the trace is _stopped_ at this $BA$-gate. Repeating the
argument in the above paragraph but with the role of $A$ and $C$ swapped, we
will want to enumerate $a_{0}$ first, then retarget the $BA$-trace to a
$BC$-trace $bc_{1}$. Again if there is a higher priority $BC$-gate, we will
need to retarget to a $BA$-trace $ba_{1}$, and so on.

Suppose $\rho$ has $k$ many higher priority gates

$\eta_{1}<\ldots<\eta_{k}<\rho,$

that alternate between $BA$\- and $BC$-gates. Refer to Figure 7 for an
illustration, where higher priority gates are drawn lower down. The trace of
$\rho$ first descends to the lowest priority gate $\eta_{k}$ and is stopped by
that gate. After retargeting, enumerating, and waiting for the gate to reopen,
the trace descends to the next lower priority gate $\eta_{k-1}$, where it
again waits to pass. This process is repeated $k$ many times until the trace
passes gate $\eta_{0}$, and the elements of the trace is enumerated
simultaneously. Each enumeration requests one permission from $X$. Given that
$k<|\rho|$, $|\rho|$ many fickleness will be sufficient to satisfy $\rho$.

The last type of gate $\eta$, which asserts that $ABD\cap BCD\leq BD$, will
not stop $BC$ or $BA$-traces, because $\eta$’s computing sets includes $B$,
and $B$-elements are picked only as followers $b$ and not as trace extensions,
meaning that the picking occurs at $\eta$-expansionary stages. At these
stages, if a subrequirement $\eta,m$ has already been set up, then the $b$
will be too large to inflict injury; and if the subrequirement has yet to be
set up, then $\theta(m)$ can always be lifted above $b$, allowing for
simultaneous injuries from $b$ on $\eta,m$. Details can be found in (Ko,
2021). Using the same framework, we can show that the other $\rho$
requirements generate traces no longer than $|\rho|$, which allows any nonzero
r.e. degree to satisfy all requirements, and hence bound the lattice.

##  3 Some Lattices where $\geq\omega^{\omega}$-Fickleness is Necessary

In 2020, when Downey and Greenberg showed that the $M_{3}$ needed
$\geq\omega^{\omega}$-fickleness, they proved:

######  Theorem 3.1 (Downey and Greenberg (2020)).

Let $L$ be a structure with 3 elements $A,B,C$ satisfying

$\displaystyle\begin{matrix}A\leq BC,\\\ B\leq AC,\\\ C\leq AB,\\\ (\forall
W\leq A,B)\;[W\leq C],\\\ (\forall W\leq A,C)\;[W\leq B],\\\ A\not\leq
C\;\;(\mathrm{or}B\not\leq C\mathrm{or}A\not\leq B).\end{matrix}$

If $\mathbf{d}$ is an r.e. degree that bounds $L$, $\mathbf{d}$ must contain a
$\geq\omega^{\omega}$-fickle set.

The conditions in the theorem are satisfied by only two lattices in Lemma 2.1,
including $M_{3}$. To show that all lattices in the lemma demand
$\geq\omega^{\omega}$-fickleness, we strengthen Theorem 3.1 by removing one
join condition:

######  Theorem 3.2.

Let $L$ be a structure with 3 elements $A,B,C$ satisfying

$\displaystyle\begin{matrix}A\leq BC,\\\ B\leq AC,\\\ (\forall W\leq
A,B)\;[W\leq C],\\\ (\forall W\leq A,C)\;[W\leq B],\\\ A\not\leq
C\;\;(\mathrm{or}B\not\leq C\mathrm{or}A\not\leq B).\end{matrix}$

If $\mathbf{d}$ is an r.e. degree that bounds $L$, $\mathbf{d}$ must contain a
$\geq\omega^{\omega}$-fickle set.

All lattices in the lemma satisfy the conditions in the strengthened Theorem
3.2, allowing us to apply the theorem with Lemma 2.1 to get:

######  Corollary 3.3.

The four lattices in the top row of Figure 5 characterize the r.e. degrees
that contain $\geq\omega^{\omega}$-fickle sets.

$\rho:A\neq\Xi(C)$$abababab$$AB\mathrm{-gate}$ $abababa\cancel{b}$
$AC\mathrm{-gate}$ $a\cancel{c}$ $AB\mathrm{-gate}$ $ababababababa\cancel{b}$
$\begin{array}[]{rclll}A&\leq&BC,\\\
B&\leq&AC\end{array}$$\rho:A\neq\Xi(C)$$abababab$$AB\mathrm{-gate}$
$abababa\cancel{b}$ $AC\mathrm{-gate}$ $acacacacacaca\cancel{c}$
$AB\mathrm{-gate}$ $\cdots$ $\begin{array}[]{rclll}A&\leq&BC,\\\ B&\leq&AC,\\\
C&\leq&AB\end{array}$ Figure 8: The top set of traces is obtained from the
conditions in Theorem 3.2, while the bottom set is from Theorem 3.1, which has
the additional join $J_{C}:C\leq AB$ shown at the right. The traces are
generated by $\rho$. Without $J_{C}$, the top traces do not grow at the
$AC$-gates, though they can still grow at the $AB$-gates. The lengths of the
traces are bounded by $\omega^{|\rho|/2}$ and $\omega^{|\rho|}$ respectively.

The rest of this section will be used to prove Theorem 3.2, where we tighten
the layering technique of Theorem 3.1. To get $\omega^{\omega}$, we generalize
the framework in Section 2, where we described the rules for the _extending_
and _partitioning_ of traces, so as to appease higher priority gates.

In that framework, diagonalization conditions, such as $\rho:A\neq\Xi(C)$ in
Theorem 3.2, generates traces, whose first element is known as the follower
and is targeted for $A$. $\rho$ interacts with joins such as $J_{A}:A\leq BC$
and $J_{B}:B\leq AC$, to _extend_ the length of its trace. As illustrated at
the top of Figure 8, the initial trace of $\rho$ is written in the top row as
“$abababab$”, to depict balls whose targets alternate between $A$ and $B$, and
where the first “$a$” is the follower of $\rho$ is targeted for $A$. To obtain
this $ABAB$-trace, we start with the follower. Since it is targeted for $A$,
we apply $J_{A}$ to determine that the target for the next ball must be $B$ or
$C$. In our example we picked $B$. Then since $J_{B}$ exists, the ball
extending the second one needs to be targeted for $A$ or $C$ according to
$J_{B}$. In our example we chose $A$. This process repeats until the follower
gets realized.

Generally, we pick targets that make the trace shorter, so as to demand less
fickleness. One might then wonder why we did not choose to target $C$ in the
initial trace, since no $J_{C}$ requirements exist, meaning that $C$ elements
do not need to be extended. The reason is $C$ elements cannot be picked until
the follower is realized, otherwise the enumeration of those elements later
will un-realize the follower. Therefore we are forced to pick a growing
$ABAB$-trace at first. The initial situation is similar for Theorem 3.1, where
the first trace is an $ABAB$-one, as illustrated at the bottom of Figure 8.

After realization, the $ABAB$-trace descends and gets stopped at the lowest
priority gate $\preceq\rho$ that does not allow the entire trace to pass. Each
gate represents a meet condition, for which there are two types in our
theorem:

$\displaystyle(\forall W\leq A,B)\;[W\leq C],$ $\displaystyle(\forall W\leq
A,C)\;[W\leq B].$

We shall call these $AB$\- and $AC$-gates respectively. Gates do not allow
elements from both of its sides to be enumerated at the same time. In our
theorem as shown at the top of the figure, lower priority gates are drawn
further up, so the lowest priority gate is an $AB$-gate, preventing elements
from $A$ and $B$ from passing simultaneously. Since the initial trace contains
elements for $A$ and $B$, the trace will be _stopped_ by this gate. A similar
argument can be made for the $ABAB$-trace at the bottom of the figure, which
is also stopped by the lowest priority $AB$-gate.

When the gate _opens_ , only elements from the same side of the gate can pass.
Therefore, we _partition_ the stopped trace into a head and a tail, making the
tail as long as possible, but ensuring that when the elements in the tail are
simultaneously enumerated, no more than one side of the gate is injured. In
the figure, the last element of the trace is targeted for $B$, so that $b$ can
pass when the $AB$-gate opens. The passing injures the $B$-side of the gate,
thereby _closing_ the gate, which will only reopen when the injured side has
recovered. The $A$-element preceding $b$ cannot pass with $b$ because that
will injure also the $A$-side of the gate. Hence, the original trace
$abababab$ is _partitioned_ into the $abababa$ head and the $b$ tail, where
only the tail passes, leaving the head at the gate. The tail descends to the
next gates. These gates will eventually allow $b$ to pass, since a single
$B$-enumeration will not injure both sides of any gate. $b$ passes all the
gates, and gets enumerated, as depicted by the cancellation of $b$ in the
figure.

After the tail is enumerated, we return to its head $abababa$, which remains
at the lowest priority $AB$-gate. This trace terminates with an $A$-element,
so we shall refer to such traces as $ABABA$-traces. While waiting for the
stopping gate to reopen, the joins force us to extend the trace. We apply
again the trace _extension_ rules described earlier, adding to the rules the
criteria that the extension’s targets should avoid the elements at the side of
the stopping gate that is just injured. For instance, since the last element
of the $ABABA$-trace is targeted for $A$, by the extension rules we can extend
by a $B$\- or $C$-element, and by the new criteria we cannot choose $B$ since
the $AB$-gate has just been injured at the $B$-side. So we are forced to
extend by $C$. By the extension rules again, in the top example, since there
are no $J_{C}$ conditions, the trace stops growing. But in the bottom example,
the rules say we must continue extending by $A$ or $B$, and by the new
criteria we can only choose $A$, and repeating the extension rules we get an
$ACAC$-extension.

When the $AB$-gate reopens, the stopped trace stops extending. We apply the
_partitioning_ rules again to break the stopped trace into a head and tail,
making the tail as long as possible without containing elements targeted for
both sides of the gate. The tail passes the $AB$-gate until it gets stopped
again. In the top example, when the $AB$-gate reopens, the waiting trace is an
$ABABAC$-one, which we can partition into an $ABAB$-head and an $AC$-tail
according to the partitioning rules, since $A$ and $C$-elements do not appear
on both sides of the $AB$-gate. The tail passes the gate but is stopped by the
next $AC$-gate, which prevents $A$ and $C$-elements from passing
simultaneously. A similar argument can be made for the bottom example, where
trace is partitioned to a $ACAC$-tail.

We repeat the process with the trace that is just stopped — waiting for the
stopping gate to open; partitioning the waiting trace into a head and a tail;
allowing the tail to pass till it is stopped by a higher priority gate;
repeating the process with the tail as the new waiting trace if the tail is
not yet enumerated; returning to tend to the head when the tail is gone;
extending the head by the extension rules when that happens; letting the
extended head be the new waiting trace; and continuing until the follower is
enumerated.

Every enumeration requests for one permission; therefore the total length of
the traces bounds the fickleness required. Consider the length of the traces
for the conditions in Theorem 3.2. In our example at the top of Figure 8,
$\rho$ has three higher priority gates that alternate between $AB$ and $AC$.
Following the trace extension and partitioning rules, the length of the
initial trace that gets stopped at the lowest priority $AB$-gate is bounded by
$\omega$, since the trace is an $ABAB$-one that stops extending only when the
follower of $\rho$ gets realized, which could take arbitrarily long. At the
middle $AC$-gate, the stopped trace could be an $AC$-trace or a $BC$-trace.
Either way, the length does not exceed two. At the bottom $AB$-gate, the
stopped trace is an $ABAB$-one, which keeps extending until the previous
$AC$-gate reopens, and that again could take arbitrary long. Hence the trace’s
length is bounded by $\omega$.

Now each element of the trace at the bottom gate requests for one permission,
so the number of requests by a trace of length $<\omega$ at the bottom is
$<\omega$. But every $<\omega$-length trace at the bottom gate is extended
from one element at the middle $AC$-gate. Since the trace at the middle gate
is never more than two elements long, if we consider only the effect from the
bottom two gates, the fickleness requested is bounded by $\omega\cdot 2$.
Repeating this argument, every 2-element trace at the middle is generated from
one element at the top gate, and since there are $>\omega$-elements at the
top, the total length of all the traces of $\rho$ is bounded by $\omega\cdot
2\cdot\omega=\omega^{2}$, in our example where $\rho$ has only three higher
priority gates. More generally, given that $\rho$ will not have more than
$|\rho|$ many higher priority gates, the total length of the traces from
$\rho$ is bounded by

$\underbrace{\omega\cdot 2\cdot\omega\cdot 2\cdot\ldots\cdot\omega\cdot
2\cdot\omega}_{\leq|\rho|\text{ many
products}}<\omega^{\lceil|\rho|/2\rceil},$

obtained from the alternating $ABAB$ then $AC$-traces of length $<\omega$ and
$\leq 2$ respectively.

Similarly, with the addition of $J_{C}$ in Theorem 3.1, the traces of $\rho$
alternate between $ABAB$\- and $ACAC$-ones of length $<\omega$, as shown at
the bottom of Figure 8, bounding the total length of traces by

$\underbrace{\omega\cdot\omega\cdot\ldots\cdot\omega}_{\leq|\rho|\text{ many
products}}<\omega^{|\rho|}.$

Given that $|\rho|$ can get arbitrarily large, the bound of the fickleness for
our theorem is still $\omega^{\omega}$, even though our traces do not grow at
every other gate. The alternating $ABAB$\- and $AC$-trace of our theorem
guides the modification of the proof of Theorem 3.1. In the original proof,
roughly speaking, the authors set up $<\omega^{\omega}$-many layers to protect
$\rho:A\not\leq C$. The layers alternate between $ABAB$\- and $ACAC$-layers,
each of length $<\omega$, to reflect the $ABAB$\- and $ACAC$-traces generated
by $\rho$. We tighten their proof by replacing every pair of
$ABAB$-$ACAC$-layers by $ABAB$-$AC$-$ABAB$-layers, where the $ABAB$-layers are
of length $<\omega$, while the middle $AC$-layer is an $AC$-pair. These
$ABAB$-$AC$-$ABAB$ layers reflect the $ABAB$-$AC$-$ABAB$-traces.

We reuse notation from Downey and Greenberg (2020). We describe the
construction for the case with just two alternations of $AB$\- then
$AC$-gates, where we show that no r.e. set $X$ with degree fickleness
$\leq\omega^{2}$ can embed structures satisfying the conditions of Theorem
3.2. The generalization from $\omega^{2}$ to $\omega^{n}$ for arbitrary
$n\in\omega$ will not be different from described in (Downey and Greenberg,
2020), so we focus on $\omega^{2}$, which illustrates most of the changes
needed. Fix functionals $\Lambda$, $\Phi_{0}$, $\Phi_{1}$ such that
$\Lambda(X)=(A,B,C)$, $A=\Phi_{0}(B,C)$, and $B=\Phi_{1}(A,C)$. For
$x\in\omega$, define

$\displaystyle x^{(1)}=_{\mathrm{def}}$
$\displaystyle\;\max\\{\phi_{0}(x),\phi_{1}(x)\\},$ $\displaystyle
x^{(n+1)}=_{\mathrm{def}}$ $\displaystyle\;\left(x^{(n)}\right)^{(1)},$

with the idea that a change in $A$ or $B$ below $x$ necessitates a change in
$A$ or $B$ or $C$ below $x^{(1)}$. We think of $x^{(n)}$ as having $n$
_layers_ of protection above $x$, which our opponent $X$ can peel with all the
fickleness that it has remaining. Our bottom-most layer can be thought of as
an $A$-layer that is associated with an $A\leq C$-computation that we want to
stop $X$ from peeling at all costs. If we set up enough layers, we can prevent
$X$ from reaching that $A$-layer, which would have resulted in an $A$-change
that diagonalized $A$ against a $C$-computation. Since $X$ has
$\leq\omega^{2}$-fickleness, we set up $\omega^{2}$ many layers above the
bottom one. But this strategy will only work if $X$ peels layers one at a
time. If layers are lost quickly, then $X$ might reach the bottom layer with
$\leq\omega^{2}$-fickleness. When double peeling occurs, we arrange to win by
a meet requirement. For instance, if $A$ and $B$-layers are simultaneously
peeled, we will receive the $AB$-changes needed to diagonalize some set $Q\leq
A,B$ against another $C$-computable function, allowing us to win by $(\exists
Q\leq A,B)[Q\nleq C]$. Similarly, if the $AC$-layers are peeled, we can win by
$(\exists Q\leq A,C)[Q\nleq B]$.

Let $\Delta(X)$ be the $\leq\omega^{2}$-fickle function in our construction.
To know the number of layers to set up at a given stage, we want to know the
fickleness that remains in $\Delta(X)$. In other words, we want to know the
$\leq\omega^{2}$-fickle function that computably approximates $\Delta(X)$. By
the following lemma, there are only countably many approximations to guess
from, and we can effectively enumerate them:

######  Lemma 3.4 (Downey and Greenberg (2020)).

Let $\alpha\leq\epsilon_{0}$. There exists a canonical $\mathcal{R}$ of order
type $\alpha$, a computable function $g(e):\omega\to R$ known as the _bounding
function_ , and uniformly computable functions
$f^{e}(x,s):\omega^{3}\to\omega$ and $m^{e}(x,s):\omega^{3}\to R$ known as the
_computable approximation functions_ , such that $\langle
f^{e}(x,s),m^{e}(x,s)\rangle_{s}$ is a $g(e)$-computable approximation of
$f^{e}(x):=\lim_{s}f^{e}(x,s)$, and $\langle f^{e}\rangle_{e\in\omega}$
enumerates the $<\alpha$-fickle functions.

We will not know which computable approximation works for $\Delta(X)$, so we
simultaneously try all of them, letting the $e$-th _agent_ guess that
$\Delta(X)$ is the $e$-th approximation $f^{e},o^{e}$ as in the lemma, with
$\Delta(X)=f^{e}$. At stage $s$, we keep track of the first $s$ steps of the
first $s$ agents. As we shall see, the agents work independently because they
construct their own sets and functionals that do not interfere with each
other. If we guess that $\Delta(X)$ has $(\omega m_{1}+m_{0})$ many fickleness
remaining, we would like to have $m_{1}$, followed by $m_{0}$ many levels of
protection. Each level involves a pair of elements, so we shall set up
$(2m_{1}+1)$ inner $ABAB$-layers, followed by a middle $AC$-layer, followed by
$(2m_{0}+1)$ outer $ABAB$-layers, as illustrated at the top of Figure 9. The
bottom-most $A$-layer works for $C\leq A$, the $ABAB$-layers work to construct
a set $\leq A,B$ that cannot be computed by $C$, and the middle $AC$-layer
works to construct a set $\leq A,C$ that cannot be computed by $B$.

Without $J_{C}:C\leq AB$$ABAB\ldots ABAB$$AC$$ABAB\ldots
ABAB$$\underbrace{\hskip 73.97733pt}$$\begin{array}[]{c}\scriptstyle
2m_{1}+1\\\ \scriptstyle A,B\geq
Q_{ij}\neq\Psi_{k}(C)\end{array}$$\overbrace{\hskip
73.97733pt}$$\begin{array}[]{c}\scriptstyle 2m_{0}+1\\\ \scriptstyle A,B\geq
Q\neq\Psi_{i}(C)\end{array}$$\overbrace{\hskip 11.38092pt}^{A,C\geq
Q_{i}\neq\Psi_{j}(B)}$$x_{ij}$$u_{ij}<x_{i}<u_{i}<x$$u$$\overbrace{\hskip
2.84544pt}^{\Xi_{ijk}(C)=A}$With $J_{C}:C\leq AB$$ABAB\ldots ABAB$$ACAC\ldots
ACAC$$\underbrace{\hskip 73.97733pt}$$\begin{array}[]{c}\scriptstyle
2m_{1}+1\\\ \scriptstyle A,B\geq
Q\neq\Psi_{j}(C)\end{array}$$\overbrace{\hskip
73.97733pt}$$\begin{array}[]{c}\scriptstyle 2m_{0}+1\\\ \scriptstyle A,C\geq
Q\neq\Psi_{i}(B)\end{array}$$\overbrace{\hskip 2.84544pt}^{\Xi_{ij}(C)=A}$
Figure 9: The top set of layers is obtained from the conditions in Theorem
3.2, while the bottom set is from Theorem 3.1, which has the additional join
$J_{C}$. At the top, given that the opponent has $(\omega m_{1}+m_{0})$ many
fickleness remaining, we set up $(2m_{1}+1)$ inner $ABAB$-layers, followed by
a middle $AC$-layer, followed by $(2m_{0}+1)$ outer $ABAB$-layers. Without
$J_{C}$, the $AC$-layer cannot be longer. The $ABAB$-layers protect the
$AB$-gate computations while the $AC$-layer protects the $AC$-gate
computation. At the bottom, which has $J_{C}$, the $AC$-pair and second
$ABAB$-layer can be replaced by a long $ACAC$-layer.

The $e$-th agent sets up its layers by enumerating an r.e. set $Q=Q^{e}$ and
functionals $\Gamma=\Gamma^{e}$ and $\Theta=\Theta^{e}$ with the aim of having

$\Gamma(A)=\Theta(B)=Q\neq\Psi_{i}(C)$

for all $i\in\omega$. If we fail at some $i$, we enumerate a backup r.e. set
$Q_{i}=Q^{e}_{i}$ and functionals $\Gamma_{i}=\Gamma^{e}_{i}$ and
$\Theta_{i}=\Theta^{e}_{i}$, with the aim of having

$\Gamma_{i}(A)=\Theta_{i}(C)=Q_{i}\neq\Psi_{j}(B)$

for all $j\in\omega$. If we fail at some $j$, we enumerate a backup r.e. set
$Q_{ij}=Q^{e}_{ij}$ and functionals $\Gamma_{ij}=\Gamma^{e}_{ij}$ and
$\Theta_{ij}=\Theta^{e}_{ij}$, with the aim of having

$\Gamma_{ij}(A)=\Theta_{ij}(B)=Q_{ij}\neq\Psi_{k}(C)$

for all $k\in\omega$. If we fail at some $k$, we enumerate a functional
$\Xi_{ijk}=\Xi^{e}_{ijk}$ with the aim of having

$\Xi_{ijk}(C)=A.$

The agent appoints followers $x$, $x_{i}$, $x_{ij}$ targeted for
$Q,Q_{i},Q_{ij}$ respectively. Each $x_{ij}$ may change several $x_{i}$’s and
each $x_{i}$ may change several $x$’s. If $n$ is the code associated with
these three followers, then at a stage where $o^{e}(n)=\omega m_{1}+m_{0}$, we
shall arrange that

$\displaystyle u_{ij}=$
$\displaystyle\;\max\left\\{x_{ij}^{(2m_{1}+1)},\gamma_{ij}(x_{ij})\right\\},$
$\displaystyle u_{i}=$
$\displaystyle\;\max\left\\{x_{i}^{(2)},\gamma_{i}(x_{i})\right\\},$
$\displaystyle u=$
$\displaystyle\;\max\left\\{x^{(2m_{0}+1)},\gamma(x)\right\\},$ $\displaystyle
x_{ij}<u_{ij}<x_{i}<u_{i}<x<u<\lambda(u_{x})<\delta(n),$ (1)

as illustrated at the top of Figure 9, where $x_{ij}$ denotes the position of
the bottom-most layer, $u_{ij}$ denotes the end of the $(2m_{1}+1)$ inner
$ABAB$-layers, $u_{i}$ denotes the end of the middle $AC$-layers, while $u$
denotes the end of the $(2m_{0}+1)$ outer $ABAB$-layers. The $e$-th agent
enumerates its version of $Q,Q_{i},Q_{ij}$, so there is no conflict with other
agents. We often drop the subscript $e$ for conciseness.

When the opponent attacks, it loses one fickleness and peels one or more
layers. If the middle layers are attacked, resulting in $AB$, $BA$, or
$AC$-changes, then we can win by the gate associated with those changes.
Consider what happens when the opponent peels one layer at a time, or in order
words, peels only the outermost layer whenever it attacks. What happens after
the outer set of $ABAB$-layers, then the middle pair of $AC$-layers, which are
those above $x_{i}$, have been peeled? The opponent’s remaining fickleness
would have descended to the next limit ordinal $\omega m_{1}$. Then when the
opponent next attacks, it will peel the $B$-layer below $x_{i}$, and its
ammunition would fall below the limit ordinal, say to
$\omega(m_{1}-1)+m_{0}^{\prime}$. The $B$-change causes $\Psi_{j}(B,x_{i})$ to
diverge, or, in other words, causes $x_{i}$ to be un-realized, which allows us
to set up a new pair of middle $AC$-layers and $(2m_{0}^{\prime}+1)$ outer
$ABAB$-layers above the pair. This makes us ready for
$(\omega(m_{1}-1)+m_{0}^{\prime})$ many attacks. In other words, no more than
two layers below $x_{i}$ will be lost before we can set up layers again, which
makes the $(2m_{0}+1)$ many layers above $x_{ij}$ sufficient against our
opponent.

In fuller detail, we pick large followers $x_{ij}<x_{i}<x$ satisfying Equation
(1) and wait for the followers to be realized. While waiting, we re-pick
$x_{i}$ and $x$, if necessary, to preserve the equation. In the meantime, we
also update

$\delta(n)=\lambda(u).$

After the followers are realized, set

$\displaystyle\xi(x_{ij})$ $\displaystyle=\max\\{u_{ij},\psi_{k}(x_{ij})\\},$
(2) $\displaystyle\theta_{ij}(x_{ij})$
$\displaystyle=\max\\{u_{i},\psi_{j}(x_{i})\\},$
$\displaystyle\theta_{i}(x_{i})$ $\displaystyle=\max\\{u,\psi_{i}(x)\\},$
$\displaystyle\theta(x)$ $\displaystyle=u.$

Note that $\xi$ ($\theta_{ij}$, $\theta_{i}$) can be maintained because it
only needs to exist if $\Psi_{k}$ (respectively $\Psi_{j}$, $\Psi_{i}$) is
total. Consider the possible ways that the opponent may peel
$x_{ij}^{\prime}s$ $(2m_{1}+1)$ many layers that lie between $x_{ij}$ and
$x_{i}$ and that are $\leq u_{ij}$. If $C$ changes below $u_{ij}$, then
$\xi(x_{ij})\uparrow$ and $\delta(n)\uparrow$, which allows us to cancel all
three followers and pick new large ones. If $C$ changes below
$\psi_{k}(x_{ij})$ but not below $u_{ij}$, then $x_{ij}$ is un-realized and
$\delta(n)\uparrow$, so we return to the earlier phase of waiting for
realization to update Equations (2). If an inner $A$-layer is peeled
($\gamma_{ij}(x_{ij})\uparrow$), which results in the next $B$-layer being
peeled ($\theta_{ij}(x_{ij})\uparrow$), then the simultaneous $AB$-change
allows us to _attack with $x_{ij}$_ by enumerating $x_{ij}$ into $Q_{ij}$ and
winning by
$\Gamma_{ij}(A,x_{ij})=\Theta_{ij}(B,x_{ij})=Q_{ij}(x)\neq\Psi_{k}(C,x_{ij})$.
If an $A$-change resulted instead in a $C$-change, then two of $x_{i}$’s
layers will be peeled, since $\gamma_{i}(x_{i}),\theta_{i}(x_{i})\geq
x_{i}>u_{x_{ij}}$. This allows us to attack with $x_{i}$. If $x_{ij}$’s outer-
most $B$-layer is peeled, then the $\theta_{ij}(x_{ij})$ and $\delta(n)$
changes allow us to cancel $x_{i}$ and $x$ and set up new large ones. Finally,
if $x_{ij}$’s outer-most $A$-layer is peeled, then $x_{ij}$ indeed loses a
layer.

Next, consider $x_{i}^{\prime}s$ two layers, which lie between $x_{i}$ and $x$
and that are $\leq u_{i}$. Similar to the smaller follower, $B$-changes below
$u_{i}$ allow us to cancel $x_{i}$ and $x$, while $B$-changes below
$\psi_{j}(x_{i})$ allow us to wait for realization of $x_{i}$ again. Also, if
the inner $A$-layer is peeled ($\gamma_{i}(x_{i})\uparrow$), which results in
the next $C$-layer to be peeled ($\theta_{i}(x_{i})\uparrow$), then we can
_attack with $x_{i}$_. If an $A$-change resulted instead in a $B$-change, then
two of $x$’s layers will be peeled, since $\gamma(x),\theta(x)\geq
x>u_{x_{i}}$. This allows us to attack with $x$. If $x_{i}$’s outer-most
$C$-layer is peeled, we can cancel $x$ and set up a new large one. Finally, if
$x_{i}$’s outer-most $A$-layer is peeled, then $x_{i}$ indeed loses a layer.

Finally, consider $x^{\prime}s$ $(2m_{0}+1)$ many layers that lie between $x$
and $\leq u$. Similar to the smallest follower, $B$-changes below $u$ allow us
to cancel $x$, while $C$-changes below $\psi_{i}(x)$ allow us to wait for
realization of $x$ again. Also, if the inner $A$-layer is peeled
($\gamma(x)\uparrow$), which results in the next $B$-layer to be peeled
($\theta(x)\uparrow$), we can _attack with $x$_. If an $A$-change resulted
instead in a $C$-change, then this change below $u$ allows us to cancel $x$,
as just mentioned. If $x$’s outer-most $A$ or $B$-layer is peeled, then $x$
indeed loses a layer.

Note that our two-gate construction is similar to the three-gate one of
(Downey and Greenberg, 2020). But we need to be careful when inner $C$-layers
are peeled, since we will not be able to obtain a $CA$\- or $CB$-change
without $J_{C}:C\leq BA$, and these changes could have helped us to win at a
gate. The paragraphs above hint at why $J_{C}$ was not needed: When we obtain
a solo $C$-change in the middle, we can cancel followers and set up new
layers, to the effect of not losing layers.

Consider the trickier situation where layers between $x$ and $u$ are still
unpeeled, but the $C$-layer below $u_{i}$ which belongs to $x_{i}$ is peeled
($\theta(x_{i})\uparrow$). One might worry that the $A$-layer below the peeled
layer will now become vulnerable. We argue that this is not the case: The
$C$-change allows us to cancel $x$ and set up $(2m_{0}+1)$ many new layers
above a new $x$. We are also allowed to lift $\theta_{i}(x_{i})$ above the new
$u$ and $\psi_{i}(x)$. Assume there are attacks on the $A$-layer
($\gamma(x_{i})\uparrow$) below the lost $C$-layer due to a $B$-change. If
this $A$-change occurred before the new $x$ is realized, then we can attack
with $x_{i}$, since $\gamma(x_{i})$ will not have converged yet. If the
$A$-change occurred after realization, we will be able to attack with the new
$x$ because the $AB$-change would be below the new $u_{i}$, which is in turn
$\leq x\leq\gamma(x),\theta(x)$. Another concern is if the $B$-change occurred
without the $A$-layer below being peeled away. The $B$-change would exceed
$\theta_{ij}(x_{ij})$, making us unable to cancel $x_{i}$, as we would have
before the $C$-layer was gone. The $B$-change must lead to an $A$\- or
$C$-change on the layer above. In the former case, we can attack with $x$, and
in the latter case, we can cancel $x$ and set up new layers, as in the
situation when the original $C$-layer was peeled.

A symmetrical argument can be made to show how the outer-most $A$-layer of
$x_{ij}$ cannot be peeled as long as there are layers belonging to $x_{i}$
sitting above. We are also prepared against attacks on the middle layers. For
instance, if the opponent attacked the layers of $x_{ij}$ ($x$), we can obtain
changes in $C$, $AC$, $BC$, $AB$, or in $BA$. In the first three cases, we may
cancel $x_{ij}$ (resp. $x$), and in the last two cases we may attack with
$x_{ij}$ (resp. $x$). If we attacked the middle layers of $x_{i}$, changes in
$AC$ allow us to attack with $x_{i}$, changes in $C$ or $BC$ allow us to
cancel $x$, while changes in $AB$ or $BA$ allow us to win by $x$.

The precise verification of this 2-gate construction is similar to the 3-gate
construction of (Downey and Greenberg, 2020). To generalize to the $n$-gate
case, the generalization in (Downey and Greenberg, 2020) still applies: If we
guess that $\Delta(X)$ is $\omega^{r}$-fickle, so that

$o^{e}(n)=\omega^{r-1}m_{r-1}+\ldots+\omega m_{1}+m_{0},$

we set up $2r-1$ many followers that alternate between having $AB$\- and
$AC$-layers, and a follower associated with $AC$ has only two $AC$-layers
above it, while the $k$-th largest follower associated with $AB$ has
$2m_{k}+1$ $AB$-layers above it.

##  4 Rejecting some “Larger” Lattices Quickly

Since the $\leq 3$-direct lattices are not $>\omega^{2}$-lattices, we
considered larger structures as candidates. Given that $L_{7}$ characterizes
the $>\omega$-levels, it was speculated that we could reach the
$>\omega^{2}$-levels by making two $L_{7}$’s interact with each other. The two
candidates in Figure 10 were suggested as a result. However, we can use
earlier results to reject these candidates immediately: Theorem 3.2 says that
any structure that satisfies the conditions of the theorem demands at least
$\omega^{\omega}$-fickleness and therefore cannot be a candidate
$>\omega^{2}$-lattice. In particular, since the four lattices in the top row
of Figure 5 satisfy those conditions, we get:

######  Corollary 4.1.

A structure cannot characterize $>\omega^{2}$-fickleness if it contains, as
sublattice, any of the four lattices in the top row of Figure 5.

Figure 10: These lattices cannot characterize $>\omega^{2}$-fickleness by
Corollary 4.1. The overly fickle sublattice is shown in solid black lines. The
lattices were suggested by Steffen Lempp and Manuel Lerman respectively.

##  5 Some “Short” and “Narrow” Upper Semilattices (USLs)

We also considered USLs $\mathcal{U}=(U,\leq,\cup,\cap)$ as
$>\omega^{2}$-candidates. In a USL, the meet function $\cap$ may not be total.
We obtained USLs by breaking some meets of the finite lattices considered
earlier. For example, if we removed the meet of $M_{3}$, we would get the
right most USL at the bottom row of Figure 11, where the removed meet is
depicted by an open circle. The figure also shows other USLs based on lattices
in Figure 5. We can show that:

Figure 11: Here are some USLs obtained by removing some meets of lattices in
Figure 5. Removed meets are shown as open circles. For instance, the USLs at
the top are based on $L_{7}$ (Figure 4). Each USL turns out to characterize
the same degrees as its lattice. Specifically, those at the top characterize
$>\omega$-fickleness, while those below characterize
$\geq\omega^{\omega}$-fickleness.

######  Theorem 5.1.

The USLs in Figure 11 characterize the same r.e. degrees as the lattice they
are based on.

In particular, the USLs considered do not characterize
$>\omega^{2}$-fickleness. From the theorem, we conjecture:

######  Conjecture 5.2.

Let $U$ be a USL obtained by removing some meets of a finite lattice $L$. An
r.e. degree bounds $U$ if and only if it bounds $L$.

Note that our USLs are different from the _partial lattices_ in (Lempp et al.,
2006), where the authors removed not just the meet but also requirements
associated with meets, producing structures that are embeddable below all
nonzero r.e. degrees. Our USLs retain some form of meet, making them more
difficult to embed.

The USL in Theorem 5.1 that takes most work is the one enlarged in Figure 12,
which is based on $M_{3}$ (Figure 2). In the rest of this section, we prove
the theorem for this USL. Details for the easier USLs can be found in (Ko,
2021).

$A$$C$$B$$\begin{array}[]{rrcll}\mathrm{Join:}&A&\leq&BC,\\\ &B&\leq&AC,\\\
&C&\leq&AB,\\\ \mathrm{Diagonalize:}&A&\nleq&B,\\\ &B&\nleq&A,\\\
&A&\nleq&C,\\\ &C&\nleq&A,\\\ &B&\nleq&C,\\\ &C&\nleq&B,\\\
\mathrm{Meet:}&(\forall W\leq A&,&B)&[W\leq C],\\\ &(\forall W\leq
A&,&C)&[W\leq B],\\\ &(\forall W\leq B&,&C)&[W\leq A],\\\ \mathrm{Non-
Meet:}&A&\cap&B&\text{does not exist},\\\ &A&\cap&C&\text{does not exist},\\\
&B&\cap&C&\text{does not exist}.\end{array}$ Figure 12: This USL is obtained
from removing the meet of $M_{3}$. The removed meet is shown as an open
circle, and the requirements for bounding this USL are shown on the right.
Like $M_{3}$, this USL characterizes the r.e. degrees that contain
$\geq\omega^{\omega}$-fickle sets.

For the easier direction of the proof, we need to show that any r.e. degree
that bounds the USL must contain a set of fickleness $\geq\omega^{\omega}$.
Consider the requirements involved, shown at the right of Figure 12. The join
($J$) and diagonalization ($\rho$) requirements are exactly the same as the
original lattice. As for the meets/gates $\eta$, there are three types:

$\displaystyle\eta_{W,C}:(\forall W\leq A,B)[W\leq C],$
$\displaystyle\eta_{W,B}:(\forall W\leq A,C)[W\leq B],$
$\displaystyle\eta_{W,A}:(\forall W\leq B,C)[W\leq A].$

We often drop the $W$ subscript. The computations associated with gate
$\eta_{A}$ need to be computable by $A$, so we say that $\eta_{A}$’s
_computing set_ is $A$. Similarly, the computing set of $\eta_{B}$
($\eta_{C}$) is $B$ (resp. $C$). These gates are not strictly meets because
$A\cap B$, $A\cap C$, and $B\cap C$ do not exist, but we still call them
meets/gates because their strategies are the same as the $\eta$-strategies of
Section 2. Now $J$, $\rho$, and $\eta$ satisfy the conditions in Theorem 3.2,
so $\geq\omega^{\omega}$-fickleness is necessary to bound the USL, which
completes the easier direction of the proof.

For the converse, fix an r.e. set $X$ whose degree contains a set $\Delta(X)$
of fickleness $\geq\omega^{\omega}$. We want to construct r.e. sets $A,B,C$
that satisfy the joins

$\displaystyle J_{A}:$ $\displaystyle A\leq BC,$ $\displaystyle J_{B}:$
$\displaystyle B\leq AC,$ $\displaystyle J_{C}:$ $\displaystyle C\leq AB,$

the three types of gates $\eta_{A}$, $\eta_{B}$, and $\eta_{C}$, and the six
types of $\rho$ requirements. The strategies for $J$ and $\eta$ were described
in Section 2. The interactions between $J$, $\rho$, and $\eta$ are like in
$M_{3}$, which was shown in (Downey and Greenberg, 2020) to produce traces of
length $<\omega^{\omega}$, making $\geq\omega^{\omega}$-fickleness sufficient
for satisfying $\rho$.

Finally, consider the “ _non-meet_ ” requirements. There are three types, and
they exert the non-existence of $A\cap B$, $A\cap C$ and $B\cap C$
respectively. We discuss only the first type, since the strategies of the
others are the same after swapping the roles of $A$, $B$, and $C$. Given an
r.e. set $V<A,B$ via $\Gamma=(\Gamma_{A},\Gamma_{B})$, we construct r.e.
$E=E_{V\Gamma}$ via functional and
$\Lambda=(\Lambda_{A},\Lambda_{B},\Lambda_{C})=(\Lambda_{V\Gamma,A},\Lambda_{V\Gamma,B},\Lambda_{V\Gamma,C})$,
such that for all $\Pi$:

$\displaystyle\tau_{V\Gamma}:\;$ $\displaystyle
V=\Gamma_{A}(A)=\Gamma_{B}(B)\implies\exists
E,\Lambda_{A},\Lambda_{B},\Lambda_{C}\text{ such that}$ $\displaystyle
E=\Lambda_{A}(A)=\Lambda_{B}(B)=\Lambda_{C}(C),\text{ and }$
$\displaystyle\tau_{V\Gamma\Pi}:\;$ $\displaystyle\Pi(V)\neq E.$

When context is clear, we drop subscripts $V\Gamma$. We use $\tau$ and
$\tau_{\Pi}$ to refer to the two requirements, and call them parent and child
nodes respectively. The hypothesis of the parent says that $V\leq A,B$. If
this holds, then $E$ witnesses that $V\neq A\cap B$, since $E$ is a set below
$A$ and $B$ that cannot be computed by $V$ regardless of the functional $\Pi$
used for the $V$-computation. Note that we have assumed $V$ to be r.e.; this
is enough because the meet of r.e. degrees, if it exists, must also be r.e.,
according to this lemma:

######  Lemma 5.3 (Lachlan (1966)).

If $A$ and $B$ are r.e. sets, and $U\leq_{\mathrm{T}}A,B$ (not necessarily
r.e.), then there exists an r.e. set $V\leq_{\mathrm{T}}A,B$ such that $U\leq
V$.

Note that $\tau$ and its countably many children $\tau_{\Pi}$ also exert the
non-existence of $A\cap B\cap C$, since any set below $A$ and $B$ is also
below $A,B,C$, and the r.e. set $E$ constructed lies not just below $A$ and
$B$, but also below $C$.

Fix a computable ordering of the requirements so that child nodes are always
of lower priority than their parent. We can ignore a child if the hypothesis
$V=\Gamma_{A}(A)=\Gamma_{B}(B)$ of its parent does not hold. We use the usual
notion of $\tau$-expansionary stages to guess the outcome of a parent’s
hypothesis. Specifically, define the _length_ of $\tau$ at stage $s$ as

$\displaystyle\mathrm{length}(\tau)[s]$ $\displaystyle:=\max_{v\leq
s}\;\left\\{V\restriction v=\Gamma_{A}\restriction v=\Gamma_{B}\restriction
v[s]\right\\},$

and we guess that $\tau$ has outcome $\infty$ at stage $s$ if $s$ is an
_$\tau$ -expansionary_ stage, which is when

$\displaystyle\mathrm{length}(\tau)[s]$
$\displaystyle>\max_{s^{\prime}<s}\\{\mathrm{length}(\tau)[s^{\prime}]:s^{\prime}\mathrm{isa}\tau\mathrm{-stage}\\}.$

Otherwise, we guess that the outcome of $\tau$ is fin. By $\tau$-expansionary
stages, we must increase our definitions of $E$, $\Lambda_{A}$, $\Lambda_{B}$,
and $\Lambda_{C}$, so that if $\tau$’s true outcome is $\infty$, then
$E=\Lambda_{A}(A)=\Lambda_{B}(B)=\Lambda_{C}(C)$:

$\tau=\tau_{V\Gamma}$-strategy: _Initialize_ $\tau$ by setting
$\Lambda_{A}=\Lambda_{B}=\Lambda_{C}=\emptyset$, $x=0$.

  1. 1.

_Maintain_ : Wait for a $\tau$-expansionary stage. For each $e<x$, if
$\lambda_{A}(e)$ or $\lambda_{B}(e)$ or $\lambda_{C}(e)$ is not defined, pick
a large value for these uses, which are targeted for $A$, $B$, and $C$
respectively. Return to the beginning of this maintenance phase for $e+1$.

We refer to $\lambda_{A}(e)$, $\lambda_{B}(e)$, and $\lambda_{C}(e)$ as the
$A$, $B$, and $C$-uses of $e$ respectively. Each of these uses may be lifted
only finitely often. Now consider the $\tau_{\Pi}$-strategy, which is based on
the usual Friedberg Muchnik one, and as we shall see, is a finite injury
requirement that inflicts both positive and negative injury. If
$\tau_{\Pi}\succeq\tau^{\frown}\texttt{fin}$, we can ignore $\tau_{\Pi}$.
Henceforth, assume $\tau_{\Pi}\succeq\tau^{\frown}\infty$. Pick a large
follower $e$ targeted for $E$, and (re)assign $e$ large $A$, $B$, and $C$-uses
by $\tau$-expansionary stages. Note that these stages are not necessarily
$\tau_{\Pi}$-stages, since $\tau^{\frown}\infty\preceq\tau_{\Pi}$. Therefore,
we need to be mindful of the interactions between $\tau_{\Pi}$ and $\eta$
later, if $\tau\prec\eta\prec\tau_{\Pi}$, for $\tau_{\Pi}$’s uses may not be
picked at $\eta$-expansionary stages, making the uses small enough to injure
some of $\eta$’s earlier subrequirements. Next, we wait for $e$ to be
_realized_ ($\Pi(e)=0$). We would like to diagonalize at $e$ by enumerating
$e$ with its uses simultaneously. But to avoid un-realizing $e$, we need:

$\displaystyle\lambda_{A}(e)>\gamma_{A}(\restriction\pi(e)+1),$
$\displaystyle\mathrm{or}\;\;\;\lambda_{B}(e)>\gamma_{B}(\restriction\pi(e)+1).$

In other words, we want to first lift the $A$\- or $B$-use above its
respective $\gamma$-use. Without loss of generality, we lift the $A$-use. To
prevent the $B$-side of the computation from being lost, which could cause $e$
to be un-realized, we impose a restraint of $\gamma_{B}(\pi(e)+1)$ on $B$
prior to lifting. After lifting, by the next $\tau$-expansionary stage, the
computation on the $\Gamma_{A}$-side would have returned, and we would pick a
new large value for the $A$-use $\lambda_{A}(e)$, to exceed the
$\gamma_{A}$-use. We can now change our restraint to the $A$-side by
cancelling our restraint on $B$ and preventing elements below the raised
$\gamma_{A}(\pi(e)+1)$ from entering $A$. Finally, we wait for $X$ to grant
permission to enumerate $e$ with its new uses simultaneously. The
$B$-enumeration may injure the $\gamma_{B}$-side of the computation, but $e$
will not become un-realized, because we are holding the $\gamma_{A}$-side of
the computation, and if the $\gamma_{B}$-side does not return to equal the
$\gamma_{A}$-side, then $\tau$ wins finitely and vacuously and we can ignore
$\tau_{\Pi}$. Notice that each $e$ sets restraints and enumerates uses no more
than twice. Therefore, $\tau_{\Pi}$ is a finite injury requirement, allowing
it to interact nicely with other finitary requirements such as $\rho$.

What about interactions with infinitary requirements such as gates? First
consider the easier case where a gate $\eta$ lies between $\tau$ and
$\tau_{\Pi}$; for instance, if:

$\tau^{\frown}\infty\preceq\eta_{A}^{\frown}\infty\preceq\tau_{\Pi}.$

Recall that the strategy of a subrequirement $\eta_{A},m$ involves enumerating
an element $\leq\theta(m)$ into $A$, if “small” elements are enumerated into
$B$ and $C$ simultaneously, which injured the $B$ and $C$-sides of the
subrequirement. Now simultaneous enumeration occurs only at the end of the
$\tau_{\Pi}$-strategy, when $e$ enumerates its uses. We need to ensure that if
the $B$ and $C$-uses are small, then $\theta(m)$ can be picked to exceed the
$A$-use. There are two cases. In the easier case, $\eta_{A},m$ is set up
before $e$. Then at least one of $e$’s $B$ and $C$-uses will be too large to
injure the computations of $\eta_{A},m$. In the harder case, the
subrequirement is set up later. But because we only tend to the subrequirement
at $\eta_{A}$-expansionary stages, which are also $\tau$-expansionary stages
where $e$’s uses exist, $\eta_{A},m$ will always know the latest values of
those uses, and in particular, update $\theta(m)$ to exceed the latest
$A$-use. Then the enumeration of the final $A$-use will lift $\theta(m)$, as
desired. Likewise, if $\eta$ works for $\eta_{B}$ ($\eta_{C}$), then because
$\tau\prec\eta$, $\eta$ can keep track of the latest $B$-use ($C$-use) of $e$,
and delay believing computations until that use and $e$ have been enumerated.

The situation is trickier when $\tau_{\Pi}$ interacts with infinitary gates
$\eta^{\frown}\infty\preceq\tau$ of higher priority than $\tau$; for instance,
if:

$\eta_{A}^{\frown}\infty\preceq\tau^{\frown}\infty\preceq\tau_{\Pi}.$

Recall in our sketch of the $\tau_{\Pi}$-strategy that $e$ lifted its $A$-use
once. A non-trivial situation occurs when a subrequirement $\eta_{A},m_{A}$ is
set up after $e$’s $A$-use is enumerated, but before stage $s_{0}$, the next
$\tau$-expansionary stage when the new use is picked. $e$’s $B$ and $C$-uses
may be small enough to injure both sides of the subrequirement, so we want
$\theta(m_{A})$ to exceed $e$’s $A$-use, should $e$’s current $B$ and $C$-uses
be the final ones to be enumerated together later. But $\theta(m_{A})$ may not
be large enough, because it must be picked by the next $\eta_{A}$-expansionary
stage, which generally comes before stage $s_{0}$. Therefore one of $e$’s
$B$\- or $C$-uses must be lifted after stage $s_{0}$, to avoid injuring
$\eta_{A},m_{A}$ at both sides.

Without loss of generality, suppose we lift the $B$-use at some stage
$s_{1}>s_{0}$. What happens if there is an $\eta_{B}$-gate of higher priority
than $\eta_{A}$:

$\eta_{B}^{\frown}\infty\preceq\eta_{A}^{\frown}\infty\preceq\tau^{\frown}\infty\preceq\tau_{\Pi}.$

A subrequirement $\eta_{B},m_{B}$ might be set up after $e$’s $B$-use is
enumerated, but before stage $s_{1}$, when the new $B$-use is picked. Like
above, $e$’s $A$ and $C$-uses might be small enough to injure both sides of
$\eta_{B},m_{B}$, so we either want to lift $\theta(m_{B})$ beyond $e$’s
$B$-use, or lift one of $e$’s $A$\- or $C$-uses. The former is not possible
because $\eta_{B}\prec\tau$, so we are forced to lift $e$’s use again.

Suppose we fix the convention of not lifting $e$’s $A$-use again, choosing
instead to lift the $B$ or $C$-uses when needed. In particular, we lift the
$C$-use at some stage $s_{2}>s_{1}$. What happens if there is an
$\eta_{C}$-gate of higher priority than $\eta_{B}$:

$\eta_{C}^{\frown}\infty\preceq\eta_{B}^{\frown}\infty\preceq\eta_{A}^{\frown}\infty\preceq\tau^{\frown}\infty\preceq\tau_{\Pi}.$

Repeating earlier argument, a subrequirement of $\eta_{C}$ that is set up
after $e$’s $C$-use is enumerated, but before stage $s_{2}$, will call for
$e$’s $B$ or $C$-use to be lifted after stage $s_{2}$. Even if we chose to
lift $e$’s $A$-use instead of its $C$-use at stage $s_{2}$, we cannot avoid
needing to lift one of $e$’s uses again after stage $s_{2}$, if there is a
gate which works for $B\cap C\leq A$ of higher priority than $\eta_{B}$.

More generally, assume there are $n$ many gates of higher priority than
$\tau$:

$\eta_{1}^{\frown}\infty\preceq\eta_{1}^{\frown}\infty\preceq\ldots\preceq\eta_{n}^{\frown}\infty\preceq\tau.$

Following the sketch above, to prevent $e$ from being un-realized, we lift its
$A$-use once and set a restraint on $A$. Then by the convention of not lifting
the $A$-use again, we alternate between lifting the $B$ and $C$-uses to
appease the gates $\preceq\tau$. After $k$ many lifts, we would have appeased
the $k$ lowest priority gates

$\eta_{n-k+1}\prec\ldots\prec\eta_{n},$

and we say that $e$ has _passed_ those gates. $e$ passes one more higher
priority gate with every $B$ or $C$ lift, which means that no more
$n\leq|\tau|$ many $B$ and $C$ lifts will allow $e$ to pass all gates.

How do we ensure that a passed gate never gets into trouble with $e$ again?
Revisit the earlier situation:

$\eta_{C}^{\frown}\infty\preceq\eta_{B}^{\frown}\infty\preceq\eta_{A}^{\frown}\infty\preceq\tau^{\frown}\infty\preceq\tau_{\Pi}.$

Assume $e$ passed $\eta_{A}$ then $\eta_{B}$, and has just enumerated its
$B$-use, say at stage $s_{0}$, in an effort to pass $\eta_{C}$ also. When
should $e$ pick its new use, in order to work with all subrequirements
$\eta_{B},m$ of $\eta_{B}$, regardless of how late that subrequirement is set
up? By earlier argument, we cannot pick the new use before the next
$\eta_{C}$-expansionary stage, if we want $e$ to pass $\eta_{C}$ later. Yet,
we cannot wait beyond the next $\tau$-expansionary stage, according to the
$\tau$-strategy. If $\eta_{B},m$ is set up after stage $s_{0}$, it would
notice $e$’s relatively small $A$ and $C$-uses, which will injure both sides
of the subrequirement’s computations if the uses are enumerated simultaneously
later. To foresee this enumeration, $\eta_{B},m$ will need to set $\theta(m)$
above the new $B$-use. Therefore, the new use must be picked by the next
$\eta_{B}$-expansionary stage, not just by the next $\tau$-expansionary stage.

Generally, if $e$ has already passed a gate $\eta$, and has just enumerated
one of its uses in an effort to pass a higher priority gate
$\eta^{\prime}\preceq\eta$, then the new use must be picked by the next
$\eta$-expansionary stage, but not before the next
$\eta^{\prime}$-expansionary stage. To these ends, we shall do the picking at
the next $\eta^{\prime}$-expansionary stage.

Now consider the effect of $J$ on $\tau_{\Pi}$. Whenever $\tau_{\Pi}$ is
waiting for an event to occur, its uses, if defined, need to extend traces
because of $J$. We need to ensure that we can always choose targets for the
extensions so as not to un-realize $e$, or to undo the effect from lifting
uses. Consider the extension of the first $A$-use. Between knowing the
$B$-restraint and changing the restraint to an $A$-restraint, the $A$-use and
its traces will be enumerated. Until we know which $B$-values to avoid, the
$A$-use’s traces cannot be targeted for $B$. By $J_{A}$ and $J_{C}$, the
$A$-use can only grow an $ACAC$-trace in the meantime. After this trace is
enumerated, the $B$-restraint is dropped. Then a permanent $A$-restraint is
imposed, and a new $A$-use which exceeds the restraint is picked. Since the
$B$\- and $C$-uses may be enumerated later, before knowing the $A$-values to
avoid, the traces extending the $B$\- or $C$-uses cannot be targeted for $A$,
which forces us to extend them to $BCBC$\- and $CBCB$-traces respectively.

Summarizing, before we alternate between lifting $B$\- and $C$-uses, the
traces associated with these uses involve small $B$\- and $C$-elements. Wlog,
suppose we wish to lift the $B$-use next to appease a gate with $B$ on one
side. If we jump directly into lifting, small $B$-elements will still be
present in the $C$-use’s $CBCB$-trace, which when enumerated later, will undo
the effect of the lifting. Therefore, prior to lifting, we change the traces
of the $C$-use to a $CACA$-one to avoid small $B$-elements. We enumerate the
$C$-use’s trace except the use itself, then re-target with $A$ and $C$-balls.
We shall refer to this process as the _re-targeting of $B$’s extension_.
Similarly, to appease gates that want the $C$-use to be lifted, we cannot
allow the $B$-use’s trace to contain small $C$-elements, and therefore _re-
target $B$’s extension_ to a $BABA$-one prior to lifting.

What about the traces of $e$’s $A$-use? They also cannot be contain small $B$
or $C$-values. After re-targeting the $B$\- and $C$-extensions, we want to
lift the $B$-use next, so beforehand we need to change $A$’s trace to one that
avoids $B$. But, we also know that after $B$ is lifted, we want to lift $C$
and will need the $A$-use to avoid extending to $C$-traces that are smaller
than the $C$-elements of the $C$-use. For these reasons, we re-target $A$’s
extension to the trace associated with the $C$-use itself. In other words, if
currently the $A$-use’s trace is $ax_{0}x_{1}\ldots$, and the $C$-use’s trace
is $ca_{0}c_{0}\ldots$, then we change $A$’s trace to $aca_{0}c_{0}\ldots$ by
enumerating $x_{0}x_{1}\ldots$, and then re-targeting $a$ to $c$ just after
$x_{0}$ is enumerated. This way, after the $B$-use is lifted, there will be no
small $B$-elements in the traces of the $A$\- or $C$-uses to undo the effect
of the lifting. When the new $B$-use is picked, we extend it to a $BABA$-trace
to avoid $C$. Similarly, after the $C$-use is lifted, we re-target $A$’s
extension to the trace of the $B$-use, and after the new $C$-use is picked we
extend it to a $CACA$-trace.

Now we bound the fickleness for satisfying $\tau_{\Pi}$. After $e$ is
realized, we lift the $A$-use and re-target the $B$-, $C$-, then
$A$-extensions. Each lifting or re-targeting requests
$\leq\omega^{|\tau_{\Pi}|}$ many fickleness, if we follow the trace-extension
and partitioning rules of Section 3. After re-targeting extensions, we
alternate between lifting the $B$\- and $C$-uses, lifting $\leq|\tau|$ many
times. Finally, we enumerate $e$ with its uses, requesting one more
fickleness. Thus a sufficient amount of fickleness for $\tau_{\Pi}$ is:

$\displaystyle\omega^{|\tau_{\Pi}|}\cdot(4+|\tau|)+1<\omega^{|\tau_{\Pi}|+1}<\omega^{\omega}.$
(3)

Now a single follower may not be granted enough permissions by $\Delta(X)$. So
we keep picking new followers to eventually succeed on one of them,
threatening to approximate $\Delta(X)$ by a $<\omega^{\omega}$-fickle function
$f$ with mind-change function $o$ if no follower succeeds. Letting $e_{i}$
denote the $i$-th follower of $\tau_{\Pi}$, $o(i)[s]$ shall bound the total
length of the traces belonging to any of $e_{0},\ldots,e_{i}$ that has yet to
be enumerated by stage $s$. Function $o(i)[-]$ will then be non-increasing,
decreasing strictly when some follower $e\leq e_{i}$ enumerates elements. By
the earlier argument, each follower has traces of length
$\leq\omega^{|\tau_{\Pi}|+1}$; therefore,
$o(i)[0]\leq\omega^{|\tau_{\Pi}|+1}\cdot i$, making $f$ a
$\leq\omega^{|\tau_{\Pi}|+2}$-fickle function. Function $f(i)[s]$ shall
represent the guess of $\Delta(X,i)$ at stage $s$ and is, therefore, a
$\leq\omega^{|\tau_{\Pi}|+2}$-fickle function via $o$.

Ideally, $e_{i}$ should receive permission only from $\Delta(X,i)$, but a
complication arises when permission is received — we need to cancel lower
priority followers $e_{i^{\prime}}>e_{i}$ to avoid undesirable interactions
with gates $\eta,m$: $e_{i}$ might receive permission to act and injure one
side of the gate; then $e_{i^{\prime}}$ might receive permission and injure
the other side, resulting in $\theta(m)$ being lifted and un-realizing
$e_{i}$. But $e_{i^{\prime}}$ might have been the follower to receive
sufficient permissions. To prevent these permissions from being lost after
$e_{i^{\prime}}$’s cancellation, we adopt (Downey et al., 2007)’s strategy of
letting $e_{i}$ inherit the fickleness meant for $e_{i^{\prime}}$. Then since
$\Delta(i^{\prime})$ was fickle enough for $e_{0},\ldots,e_{i^{\prime}}$,
$\Delta(i^{\prime})$ will be fickle enough for $e_{i}$.

The above example illustrates another complication from multiple followers:
Without knowing which follower to wait for, gates cannot foresee if both of
its sides will be simultaneously injured. Therein lies the purpose a gate’s
computing sets — whenever a trace $t$ is waiting to be enumerated, we put $t$
into a _permitting_ bin, and _assign_ $t$ _permitting ball(s)_ , which are
element(s) targeted for the computing set(s) of gates, so that gates can use
their computing set(s) to foresee the enumeration, and delay believing
computations until those traces are gone. Suppose a trace $t$ is placed in the
permitting bin, and $t$ contains elements targeted for $A$ and $B$ only. Since
there are three types of gates, and together their computing sets include not
just $A$ and $B$ but also $C$, we need to assign $t$ a $C$-permitting ball,
which will given the same permitting code as $t$ to be enumerated with the
trace. When some $\eta_{C},m$ notices $t$ in the bin, $\eta_{C}$ will set
$\theta(m)$ to exceed the $C$-ball, so as to $C$-computably know if $t$ will
be enumerated later. Likewise, $\eta_{A}$ can use the $A$-elements in $t$ to
$A$-computably know if $t$ will be enumerated, and similarly for $\eta_{B}$.

We can now provide the $\tau_{\Pi}$-strategy for the non-existence of $A\cap
B$. For the other types of non-meets, swap the roles of $A$, $B$, and $C$ in
the description below.

$\tau_{\Pi}$-strategy: If $\tau_{\Pi}\succeq\tau^{\frown}\texttt{fin}$, do
nothing. Otherwise, _initialize_ $\tau_{\Pi}$ by cancelling all followers and
restraints, if any, that have been set up by $\tau_{\Pi}$.

  1. 1.

_Set up_ : Let $e$ be the largest follower that has been set up by $\tau$ and
that has not been assigned to any other child-requirement. $e$’s $A$, $B$, and
$C$-uses $\lambda_{A}(e)$, $\lambda_{B}(e)$, and $\lambda_{C}(e)$ would have
just been assigned. Extend the traces of these uses, following the discussed
rule that the traces of the $A$-use avoid $B$ and the traces of the $B$ and
$C$-uses avoid $A$. Set the codes of all traces to $\delta\restriction(k+1)$,
where $k$ is the number of followers of $\tau_{\Pi}$ so far.

  2. 2.

_Realization_ : Wait for $e$ to be realized at a $\tau_{\Pi}$-stage. Set a
restraint on the $B$-side to stop $e$ from being un-realized.

  3. 3.

_Lift $A$-use_: Enumerate the $A$-use’s trace. If enough permissions are
received that the $A$-use becomes enumerated, then at the next
$\tau$-expansionary stage, the injured computation
$V\restriction(\pi(e)+1)=\Gamma_{A}\restriction(\pi(e)+1)$ will have returned,
and $\tau$ will pick a new large $A$-use
$\lambda_{A}(e)>\gamma_{A}\restriction(\pi(e)+1)$. Set a restraint on the
$A$-side to stop $e$ from being un-realized and cancel the earlier
$B$-restraint. The $B$\- and $C$-uses of $e$ can now grow traces targeted for
$A$ if they wish.

  4. 4.

_Re-target $B$-extension_: Let $bc_{0}\ldots$ be the current trace of the
$B$-use. Enumerate this trace up to and including $c_{0}$. If enough
permissions are granted that $c_{0}$ becomes enumerated, extend the trace of
$b$ by a $BABA$-one.

  5. 5.

_Re-target $C$-extension_: Let $cb_{0}\ldots$ be the current trace of the
$C$-use. Enumerate this trace up to and including $b_{0}$. If enough
permissions are granted that $b_{0}$ becomes enumerated, extend the trace of
$c$ by a $CACA$-one.

  6. 6.

_Re-target $A$-extension_: Let $ax\ldots$ be the current trace of the $A$-use.
Enumerate this trace up to and including $x$. If enough permissions are
granted that $x$ becomes enumerated, let the trace of $a$ extend by the
$B$-use’s $BABA$-trace so that the $A$-trace is
$\lambda_{A}(e)\lambda_{B}(e)\ldots$. As discussed before, we consider $e$ not
to have passed any infinitary gate of higher priority than $\tau$.

  7. 7.

_Pass one more gate $\prec\tau$_: Let $\eta^{\frown}\infty\preceq\tau$ be the
lowest priority gate that $e$ has not yet passed. If $\eta$ does not exist,
then $e$ has passed all gates and we can go directly to the next
diagonalization phase. Otherwise, let $Z\in\\{B,C\\}$ be any set that appears
on one side of $\eta$. We want to lift the $Z$-use. Enumerate the $Z$-trace of
$e$. If enough permissions are granted that the $Z$-use is enumerated, pick
the new large $Z$-use at the next $\eta$-expansionary stage. If the trace
extending $e$’s $A$-use is the previous $Z$-use, then after that previous use
was enumerated, re-target $A$’s extension to the other use of $e$. Consider
$e$ to have passed gate $\eta$, and return to the beginning of this gate-
passing phase to pass the next lowest priority infinitary gate.

  8. 8.

_Diagonalize_ : Put $e$ and the traces of its uses into the permitting bin,
assigning permitting ball(s) if necessary. Wait for a single $X$-permission to
enumerate all elements simultaneously. Cancel all other followers and declare
$\tau_{\Pi}$ satisfied by $e$.

Apart from the rules above, we keep the usual conventions in priority
constructions of cancelling lower priority followers whenever a follower $e$
receives attention, and of waiting for the next $\tau_{\Pi}$-stage before
allowing $e$ to receive attention again and letting $\tau_{\Pi}$ pick a new
follower. Also, if $e$ received permission to enumerate, we let $e$ inherit
the permissions of all cancelled $e^{\prime}>e$. Putting all strategies
together, the overall construction is:

Construction. _Stage 0._ Initialize all requirements.

_Stage $s+1$_: Let $\lambda_{s}\in\Lambda$ be the node of length $s$
representing the outcomes of the first $s$ requirements, where we set up a
node $\lambda\preceq\lambda_{s}$ along the way if $\lambda$ has not been been
set up. Let $\lambda\preceq\lambda_{s}$ or $\lambda<_{L}\lambda_{s}$ be the
highest priority positive node that wants to act. Let $\lambda$ act and
initialize all nodes of lower priority than $\lambda$.

To prove that all requirements are satisfied, let $g\in[\Lambda]$ be the true
path on the tree of construction $\Lambda$. We prove by induction on $n$, the
length of the node along the true path, that the requirement represented by
node $\lambda=g(n)$ is satisfied. In the following lemmas, we can assume from
induction that we are working in stages after nodes to the left of $\lambda$
are never visited again, and after all $\rho\preceq\lambda$ have stopped
inflicting injury. Then $\lambda$ will never be cancelled and will always have
highest priority to act.

######  Lemma 5.4.

If $\lambda=\tau$, then $\tau$ is satisfied and inflicts no injury.

###### Proof.

$\tau$ never sets restraints or enumerates elements, and so cannot inflict
injury. If the outcome of $\tau$ is fin, then $\tau$ is vacuously satisfied.
So, assume there are infinitely many $\tau$-expansionary stages. Each follower
$e$ of $\tau$ is assigned to at most one child node $\tau_{\Pi}$, which by the
$\tau_{\Pi}$-strategy acts only finitely often until cancellation. Uses
$\lambda_{A}(e)$, $\lambda_{B}(e)$, and $\lambda_{C}(e)$ always exist at
$\tau$-expansionary stages, and when $e$ is enumerated, those uses are also
enumerated. Therefore, the uses are lifted finitely often, and
$E(e)=\Lambda_{A}(e)=\Lambda_{B}(e)=\Lambda_{C}(e)$. ∎

######  Lemma 5.5.

If $\lambda=\tau_{\Pi}$, then $\tau_{\Pi}$ is satisfied and inflicts finite
injury.

###### Proof.

Wait for $\tau_{\Pi}$ to stop being initialized. Followers that are realized
never become un-realized because of the restraints. If some follower was never
realized, the lemma holds trivially. So assume all followers eventually become
realized. Each follower $e$ requests $\leq\omega^{|\tau_{\Pi}|+1}$ many
permissions. Some $e$ must eventually receive enough permissions to satisfy
$\tau_{\Pi}$, otherwise we can approximate $\Delta(X)$ by a
$\leq\omega^{|\tau_{\Pi}|+2}$-fickle function, contradicting the
$\geq\omega^{\omega}$-fickleness of $\Delta(X)$. Even though
$\omega^{|\tau_{\Pi}|+1}\geq\omega$, in reality $e$ only enumerates finitely
many elements, except these elements may not be indexed canonically by a
natural number. Therefore, the injury by $\tau_{\Pi}$ is finite. ∎

The $G$ and $J$ requirements are global and satisfied by construction, like in
(Downey and Greenberg, 2020). The verification for $\rho$ also remains
unchanged, because the requirement is of finite injury, which allows it to mix
with $\tau$ and $\tau_{\Pi}$, for they inflict finite injury. The verification
that takes the most work is for $\eta$:

######  Lemma 5.6.

Let $\lambda=\eta$ and consider the subrequirement of $\eta$ at $m$. Let
$s_{0}$ be the first $\eta$-stage where $\mathrm{length}(\eta)>m$. Let
$s_{1}\geq s_{0}$ be the first $\eta$-stage where no follower that existed at
stage $s_{0}$ has balls targeted for the computing set of $\eta$ that will
later be enumerated. Note that the computing sets of $\eta$ can determine
stage $s_{1}$. From stage $s_{1}$ onward, we say that $\eta,m$ _believes its
computation_.

  1. 1.

The subrequirement can only be injured by followers that existed at stage
$s_{0}$. Therefore $\theta(m)$ is lifted finitely often, since followers act
finitely often.

  2. 2.

After stage $s_{1}$, $\Phi_{0}(m)$ and $\Phi_{1}(m)$ cannot be simultaneously
injured.

If $\eta^{\frown}\texttt{fin}\prec g$, then $\eta$ is vacuously satisfied. If
$\eta^{\frown}\infty\prec g$, then $\eta$ will also be satisfied from the
above two claims.

###### Proof.

Claim 1 follows from the tree framework: Let $y$ be the first element whose
enumeration contradicts the claim, and let $\sigma$ be node to which $y$
belongs. If $\sigma<_{L}\eta$ or $\sigma\preceq\eta$, then $y$ will never be
enumerated otherwise $\eta$ will be cancelled; if
$\sigma>_{L}\eta^{\frown}\infty$ then $y$ will be cancelled at expansionary
stages, and will be too large to inflict injury at non-expansionary stages. So
it must be that $\sigma\succeq\eta^{\frown}\infty$. Before $y$ acted, the
subrequirement’s use must have been lifted due to a recent action by some
other $y^{\prime}$. $y^{\prime}$ must have existed at stage $s_{0}$ by the
choice of $y$ being the first. Now $y$ must be picked after the action by
$y^{\prime}$, otherwise if $y$ is of higher priority than $y^{\prime}$ then
$y^{\prime}$ would be cancelled before it could act, and if $y$ is of lower
priority then $y$ would be cancelled by $y^{\prime}$. Since
$\sigma\succeq\eta^{\frown}\infty$, $y$ must be picked at an
$\eta$-expansionary stage, which is a stage after $\eta,m$ has recovered from
the injury inflicted by $y^{\prime}$. Then $y$ be too large to inflict injury.

Claim 2: We work in stages after $s_{1}$. By Claim 1, we can ignore all
followers that are set up after stage $s_{0}$ or that were cancelled by stage
$s_{1}$. Assume, for a contradiction, that there is a first stage where
$\eta,m$ was injured on both sides simultaneously. There are three cases for
how the injury could be inflicted, and we show that none of them are possible.

Case 1 — The injury was due to different followers: The permitting balls
prevent this situation. Assume follower $y_{0}$ injured one side of $\eta,m$,
but before the side recovered, some other $y_{1}$ belonging to
$\sigma\succeq\eta^{\frown}\infty$ injures the other side. $y_{0}$ must have
lower priority than $y_{1}$; otherwise, $y_{1}$ would be cancelled when
$y_{0}$ attacked, and Claim 1 prevents followers that are set up later from
inflicting injury. By our choice of $s_{1}$, $y_{1}$ did not have a permitting
ball at stage $s_{1}$. $y_{1}$ can only be assigned permitting balls after
$y_{0}$’s enumeration; otherwise, $y_{0}$ would be cancelled, and cannot
injure $\eta,m$ by Claim 1. But after the assignment, $y_{1}$ would have
waited for a $\sigma$-stage, which is an $\eta$-expansionary stage, before
enumerating. The injury from $y_{0}$ would have recovered before $y_{1}$ could
attack.

Case 2 — The injury was from a follower of $\rho$: This is not possible for
the same reason that $\rho$ requirements work well with $\eta$ requirements in
the embedding of $M_{3}$, which has been discussed in detail in (Downey and
Greenberg, 2020).

Case 3 — The injury was from a follower $e$ of $\tau_{\Pi}$: Until we reach
the diagonalization phase of the $\tau_{\Pi}$-strategy, enumerations by $e$
work like in Case 2, which does not give problems. So the injury must be
inflicted at the final phase, when $e$’s uses are simultaneous enumerated.
Assume wlog that $\tau_{\Pi}$ works for the non-existence of $A\cap B$. If
$\eta\succeq\tau^{\frown}\infty$, then $\eta,m$ will always know the updated
uses of $e$, since $e$ was set up before $\eta,m$ and always picks uses by
$\tau$-expansionary stages. Therefore, $\eta,m$ knows $e$ will be enumerated
and would not have believed computations until afterwards. So, assume
$\eta^{\frown}\infty\preceq\tau$, and wait for $e$ to pass $\eta$, which would
involve lifting the $B$\- or $C$-use of $e$. Wlog, assume it was the $B$-use
that was lifted, which means that $B$ appeared on exactly one side of $\eta$.
If $\eta,m$ was set up before the passing, then after passing, new
$B$-elements associated with $e$ will be too large to injure the $B$-side of
$\eta,m$, by the $\tau_{\Pi}$-strategy of not letting $e$’s $A$\- or
$C$-traces contain small $B$-elements. Therefore the simultaneous injury
cannot injure both sides of $\eta,m$. So it must be that $\eta,m$ was set up
after the passing. Then $\eta,m$ can keep track of the $A$\- and $C$-uses of
$e$, because $e$’s $A$-use is never lifted again and its $C$-use, if lifted
after passing $\eta$, will always be picked by the next $\eta$-expansionary
stage. In particular, $\eta,m$ can keep lifting $\theta(m)$ above the relevant
use of $e$, which will help the subrequirement delay believing computations
until after $e$ is enumerated. ∎

##  6 Future Work

We can proceed lattice theoretically or degree theoretically. We can consider
using lattice theory to find more $>\omega^{2}$-candidates:

######  Question 6.1.

Can we systematically list the non-distributive lattices and apply Corollary
4.1 to get $>\omega^{2}$-candidates?

Given a candidate, like the one in Figure 13, we can extend the known degree
theoretic techniques to characterize the lattice. The layering and trace-
extension methods need to be generalized before they can be applied here.

######  Conjecture 6.2.

The lattice in Figure 13 characterizes $\geq\omega^{\omega}$-fickleness.

Figure 13: A $>\omega^{2}$-candidate, proposed by Peter Cholak.

## References

  * Ambos-Spies (1984) Ambos-Spies, K., 1984.  On pairs of recursively enumerable degrees.  Transactions of the American Mathematical Society 283, 507–531.
  * Ambos-Spies and Losert (2019) Ambos-Spies, K., Losert, N., 2019\.  Universally array noncomputable sets.
  * Ash and Knight (2000) Ash, C.J., Knight, J., 2000\.  Computable structures and the hyperarithmetical hierarchy. volume 144 of Studies in Logic and the Foundations of Mathematics.  North-Holland Publishing Co., Amsterdam.
  * Birkhoff (1937) Birkhoff, G., 1937.  Rings of sets.  Duke Math. J. 3, 443–454.  URL: https://doi-org.proxy.library.nd.edu/10.1215/S0012-7094-37-00334-X, doi:10.1215/S0012-7094-37-00334-X.
  * Downey and Greenberg (2020) Downey, R., Greenberg, N., 2020\.  A Hierarchy of Turing Degrees: A Transfinite Hierarchy of Lowness Notions in the Computably Enumerable Degrees, Unifying Classes, and Natural Definability (AMS-206).  Princeton University Press.
  * Downey et al. (2007) Downey, R., Greenberg, N., Weber, R., 2007.  Totally $\omega$-computably enumerable degrees and bounding critical triples.  Journal of Mathematical Logic 7, 145–171.
  * Epstein et al. (1981) Epstein, R.L., Haas, R., Kramer, R.L., 1981.  Hierarchies of sets and degrees below ${\bf 0}^{\prime}$, in: Logic Year 1979–80 (Proc. Seminars and Conf. Math. Logic, Univ. Connecticut, Storrs, Conn., 1979/80), Springer, Berlin. pp. 32–48.
  * Eršov (1968a) Eršov, J.L., 1968a.  A certain hierarchy of sets. I.  Algebra i Logika 7, 47–74.
  * Eršov (1968b) Eršov, J.L., 1968b.  A certain hierarchy of sets. II.  Algebra i Logika 7, 15–47.
  * Eršov (1970) Eršov, J.L., 1970.  A certain hierarchy of sets. III.  Algebra i Logika 9, 34–51.
  * Ko (2021) Ko, L., 2021.  Phd thesis: Towards finding a lattice that characterizes the $>\omega^{2}$-fickle recursively enumerable turing degrees (https://curate.nd.edu/show/7m01bk15c0w).  URL: https://curate.nd.edu/show/7m01bk15c0w.
  * Lachlan (1966) Lachlan, A.H., 1966.  Lower bounds for pairs of recursively enumerable degrees.  Proc. London Math. Soc. (3) 16, 537–569.  URL: https://doi-org.proxy.library.nd.edu/10.1112/plms/s3-16.1.537, doi:10.1112/plms/s3-16.1.537.
  * Lachlan (1972) Lachlan, A.H., 1972.  Embedding nondistributive lattices in the recursively enumerable degrees, in: Conference in Mathematical Logic-London 70, Springer. pp. 149–177.
  * Lachlan and Soare (1980) Lachlan, A.H., Soare, R.I., 1980\.  Not every finite lattice is embeddable in the recursively enumerable degrees.  Advances in Mathematics 37, 74–82.
  * Lempp (2012) Lempp, S., 2012.  Priority arguments in computability theory, model theory, and complexity theory.  Lecture notes .
  * Lempp and Lerman (1997) Lempp, S., Lerman, M., 1997\.  A finite lattice without critical triple that cannot be embedded into the enumerable turing degrees.  Annals of Pure and Applied Logic 87, 167–185.
  * Lempp et al. (2006) Lempp, S., Lerman, M., Solomon, R., 2006.  Embedding finite lattices into the computably enumerable degrees—a status survey, in: Logic Colloquium ’02. Assoc. Symbol. Logic, La Jolla, CA. volume 27 of Lect. Notes Log., pp. 206–229.
  * Lerman et al. (1984) Lerman, M., Shore, R.A., Soare, R.I., 1984.  The elementary theory of the recursively enumerable degrees is not $\aleph_{0}$-categorical.  Adv. in Math. 53, 301–320.  URL: https://doi-org.proxy.library.nd.edu/10.1016/0001-8708(84)90028-8, doi:10.1016/0001-8708(84)90028-8.
  * Thomason (1971) Thomason, S.K., 1971.  Sublattices of the recursively enumerable degrees.  Mathematical Logic Quarterly 17, 273–280.
  * Yates (1966) Yates, C.M., 1966.  A minimal pair of recursively enumerable degrees.  The Journal of Symbolic Logic 31, 159–168.