# Nonlowness independent from frequent mind changes

Li Ling Ko111I would like to thank my advisor Prof. Peter Cholak for his
patience and guidance, without which this piece of work will not be possible.
222Department of Mathematics, University of Notre Dame, Hayes-Healy, Notre
Dame, Indiana 46556, USA
<EMAIL_ADDRESS>
###### Abstract

It was recently shown that the computably enumerable (c.e.) degrees that embed
the critical triple [3] and the $M_{3}$ lattice structure [2] are exactly
those that change their minds sufficiently often. Therefore the embeddability
strength of a c.e. degree has much to do with the degree’s mind change
frequency. Nonlowness is another common measure of degree strength, with
nonlow degrees expected to compute more degrees than low ones. We ask if
nonlowness and frequent mind changes are independent measures of strength.
Downey and Greenberg (2015) claimed this to be true without proof, so we
present one here. We prove the claim by building low and nonlow c.e. sets with
an arbitrary number of mind changes. We base our proof on our direct
construction of a nonlow $\mathrm{low}_{2}$ array computable set. Such sets
were always known to exist, but also never constructed directly in any
publication.

Keywords: approximable, degrees, low computably enumerable sets and degrees,
$\alpha$-computably approximable, array non computable, low and low2

##  1 Introduction

For many years one of the major themes in the study of the c.e. degrees is
identifying the lattices that can be embedded below $0^{\prime}$, and
characterizing the degrees below which one can embed a given lattice. It has
been known for some time that all distributive lattices can be embedded below
any c.e. degree [9]. As for non-distributive lattices, which are the lattices
that contain either the $N_{5}$ or $M_{3}$ lattice (Figure 1) as sub-lattices,
it is also known for some time that being able to embed $N_{5}$ is exactly the
same as being non-contiguous [7]. However little was known about $M_{3}$ until
2015, when it was finally shown that a c.e. degree embeds $M_{3}$ if and only
if the degree “changes its mind frequently” [2]. More precisely, a c.e. set
$A$ needs to have a computable-approximation that “changes its mind more than
$\omega^{\omega}$-times” before $A$ can embed $M_{3}$. We formally define what
it means for a degree to “change its mind $\alpha$-times” in Section 3.1.

$a$$b$$a_{0}$$0$$a_{1}$$N_{5}$$a=a_{0}\vee a_{1}=b\vee
a_{1}$,$a_{0},b|_{T}a_{1}$, $b>_{T}a_{0}$,$a_{0}\wedge a_{1}=b\wedge
a_{1}=0$$a$$a_{0}$$b$$0$$a_{1}$$M_{3}$$a=a_{0}\vee a_{1}=b\vee a_{0}=b\vee
a_{1}$,$a_{0},a_{1},b$ incomparable,$a_{0}\wedge a_{1}=b\wedge a_{0}=b\wedge
a_{1}=0$$a$$a_{0}$$b$$a_{1}$Critical-triple$a=a_{0}\vee a_{1}=b\vee
a_{0}=b\vee a_{1}$,$a_{0},a_{1},b$ incomparable,$(\forall
c\leq_{T}a_{0},a_{1})\;[b\geq_{T}c]$ Figure 1: Lattices $N_{5}$, $M_{3}$, and
critical triple structure. The critical triple is similar to $M_{3}$ but does
not require meets $a_{0}\wedge a_{1}$, $b\wedge a_{0}$, or $b\wedge a_{1}$ to
exist.

In a similar vein, to embed the critical triple, which is a structure
resembling $M_{3}$ but with fewer restrictions (Figure 1), a c.e. degree only
needs to change its mind more than $\omega$-times to succeed [3]. Therefore a
degree’s ability to embed certain lattices is highly dependent on the degree’s
fickleness (Downey and Greenberg use the phrase “change mind frequently”, but
we sometimes use the word “fickle” instead to be less verbose). This
connection follows from our usual approach to constructing a c.e. degree that
embeds a specific lattice, which is to prioritize the requirements for
embeddability and satisfy them in turn. A more fickle degree is more likely to
permit requirements to be satisfied, increasing the chances of a successful
construction.

Motivated by how fickleness aids embeddability, Downey and Greenberg [2]
defined a hierarchy of c.e. degrees based on mind change frequency, in which
degrees that are more fickle lie higher up the hierarchy. It turns out that
c.e. degrees with “reasonable” fickleness are $\operatorname{low}_{2}$. Lying
at the bottom level of the hierarchy are the most unfickle degrees, which turn
out to be exactly the array computable ones [2].

Our work is based on this recent work of fickleness characterizing
embeddability strength. Given that nonlowness is another measure of degree
strength, we explore how lowness and nonlowness sits within the mind change
hierarchy. We expect nonlow degrees to compute more degrees than low ones, but
does that necessarily imply nonlows embed more types of lattices? This
statement is believed to be false, for Downey and Greenberg [2] claimed there
are lows and nonlows on every level of the mind change hierarchy. But we are
not aware of any formal proof of their claim, and provide one here.

Given an arbitrary “reasonable” ordinal $\alpha$, we construct low and nonlow
c.e. sets that “change their minds $\alpha$-times”. Our construction of the
nonlow extends from our construction of a nonlow $\operatorname{low}_{2}$ c.e.
set. It is not difficult to build nonlow $\operatorname{low}_{2}$’s, but we
are not aware of a direct proof in the literature. We build such a set
directly.

By distributing injury from nonlow requirements uniformly, our nonlow
$\operatorname{low}_{2}$ set turns out to be array computable. Therefore, our
construction also directly gives a nonlow array computable c.e. set, which are
also sets whose proof of existence have always been indirect 333First,
construct an array computable, 1-topped, and incomplete c.e. set, then use the
fact that every array computable and 1-topped degree is either incomplete or
nonlow $\operatorname{low}_{2}$ [6]. Alternatively, construct a nonlow c.e.
degree that contains only a single $W$-degree and whose elements are all
mitotic, then use the fact that every array noncomputable c.e. degree must
contain a c.e. set that is non-$W$-mitotic [1]..

After we build a nonlow array computable c.e. set $A$, given an arbitrary
“reasonable” ordinal $\alpha$, we injure $A$ “$\alpha$-more times” but no more
than that. Then $A$ will be a nonlow c.e. set that lies in the $\alpha$-level
of the mind change hierarchy, as desired. To build a low set at the
$\alpha$-level, we “simplify” the construction given by Downey and Greenberg
([2], Lemma III.2.1), where the authors constructed a c.e. set at the
$\alpha$-level. The authors used a tree in the construction, so the
constructed set was not necessarily low. By tracking injury more carefully, we
managed to avoid using a tree, ensuring the lowness of the constructed
$\alpha$-level set.

##  2 Nonlow, Array Computable

We directly build a nonlow $\operatorname{low}_{2}$ c.e. set $A$ in Section
2.2, and show in Section 2.3 that $A$ is array computable. Our construction
uses the “usual” tree framework to handle the infinite injury from the nonlow
requirements. Refer to [10] Chapter 14 for priority constructions using trees.
We introduce common terminologies in the following Section 2.1.

###  2.1 Tree constructions

We mainly follow terminology from [2] Chapter 1.1. Often in the construction
we say that we pick a _large_ number as a use or a follower. Large refers to
the first number greater than any number that has ever been seen or used up to
the point of construction. Requirements are ordered
$R_{0}<R_{1}<R_{2}<\ldots$, with smaller requirements having higher priority
than larger ones.

Trees provide an intuitive framework for infinite injury constructions. Such
constructions begin by fixing an ordering of the requirements
$R_{0}<R_{1}<\ldots$, where each requirement has exactly one true outcome from
an ordered and computable set
$\texttt{outcomes}=\\{o_{0}<o_{1}<o_{2}<\ldots\\}$, with smaller outcomes
having higher priority. The tree of construction is

$\Lambda=\texttt{outcomes}^{<\omega}.$

At each stage $s$ of the construction, we guess the outcomes of an initial
segment of the requirements to get a node $\delta_{s}\in\Lambda$ of outcomes.
Given $s\in\omega$ and $\delta\in\Lambda$, if $\delta\preceq\delta_{s}$, we
say _stage $s$ is an $\delta$-stage_, or _$\delta$ is accessible at stage
$s$_. Given $\delta,\delta^{\prime}\in\Lambda$, we say _$\delta$ lies to the
left of $\delta^{\prime}$_, written $\delta<_{L}\delta^{\prime}$, to mean

$\delta<_{L}\delta^{\prime}\iff(\exists\eta\in\Lambda,o_{0}<o_{1}\in\texttt{outcomes})\;\left[\eta^{\frown}o_{0}\preceq\delta\text{
and }\eta^{\frown}o_{1}\preceq\delta^{\prime}\right].$

A node $\delta\in\Lambda$ is said to _lie on the true path of outcomes_ iff
$\delta$ is accessed infinitely often but any node to the left of $\delta$ is
only accessed finitely often. Formally,

$\delta\text{ lies on true path of outcomes
}\iff(\exists^{\infty}s)\;\left[\delta\preceq\delta_{s}\text{ and
}(\forall\delta^{\prime}<_{L}\delta)\;\left[\left|\\{t:\delta^{\prime}\preceq\delta_{t}\\}\right|<\omega\right]\right].$

Note that from this definition, the set of nodes that lie on the the true path
must form a chain. We define the true path of outcomes $\delta_{\omega}$ as
the union of this chain

$\delta_{\omega}:=\bigcup\\{\delta\in\Lambda:\delta\text{ lies on the true
path of outcomes}\\},$

and write $\delta\prec\delta_{\omega}$ to mean that $\delta$ lies on this true
path. Often in tree constructions we want to show that
$|\delta_{\omega}|=\omega$, i.e. the true path meets all requirements.

###  2.2 Nonlow, Low2

We give a direct construction of the following known fact:

######  Theorem 2.1.

There exists a nonlow $\operatorname{low}_{2}$ c.e. set $A$.

$N$-module ($\operatorname{low}_{2}$): To ensure $A$ is
$\operatorname{low}_{2}$, $\emptyset^{\prime\prime}$ uniformly computes a
series of computable sets $S_{0},S_{1},\ldots\equiv_{T}\emptyset$ such that
$\forall e\in\omega$:

$N_{e}:(\forall x)(\exists^{\infty}s\in
S_{e})\;[\Phi^{A}_{e}(x)[s]\downarrow]\implies\Phi^{A}_{e}\text{ total}.$

To see how $N_{e}$ gives $\operatorname{low}_{2}$-ness, note that the left
clause of $N_{e}$ is a $\Pi_{2}$-formula and therefore can be decided by
$\emptyset^{\prime\prime}$. So $\emptyset^{\prime\prime}$ can determine if
$\Phi^{A}_{e}$ is total, meaning that
$\text{Tot}^{A}\leq_{T}\emptyset^{\prime\prime}$, making $A$
$\operatorname{low}_{2}$.

Let $N_{e}(x)$ denote the negative sub-requirement of $N_{e}$ that works to
protect computation $\Phi^{A}_{e}(x)$. To reduce the number of variables used,
if context is clear, we sometimes drop the subscript $e$ and write $N$ for
$N_{e}$, and $N(x)$ for $N_{e}(x)$. Also, if $N=N_{e}$, we write
$\Phi^{A}_{N}$ to mean $\Phi^{A}_{e}$.

To meet a single $N(x)$, wait for $\Phi^{A}_{N}\restriction x$ to converge for
the first time. Then $N(x)$ will want to protect $\Phi^{A}_{N}(x)$ by
“initializing” positive requirements $P$ that threaten $\Phi^{A}_{N}(x)$. But
if $N(x)$ is overly protective, $P$-requirements may never get satisfied. As a
compromise, each $N(x)$ is allocated a fixed _quota_ of requirements $P<N$
allowed to injure $N(x)$. The quota also limits the number of times a given
$P<N$ can inflict injury. We provide details on quota allocation later. $N(x)$
“initializes” $P$ only if $P$ threatens to injure $\Phi^{A}_{N}(x)$ yet does
not satisfy $N(x)$’s quota.

$P$-module (Nonlow): To make $A$ nonlow, fix a partial computable enumeration
of the computable functions
$\langle\langle\psi^{e}_{s}(x)\rangle_{s}\rangle_{e}$ and construct functional
$\Gamma$ such that $\Gamma^{A}$ is c.e. in $A$ and satisfies positive
requirements $\forall e\in\omega$:

$P_{e}:(\forall x)\;\left[\lim_{s}\psi^{e}_{s}(x)\text{
exists}\right]\implies(\exists
x)\;\left[\chi_{\Gamma^{A}}(x)\neq\lim_{s}\psi^{e}_{s}(x)\right].$

To see how $P_{e}$ give nonlowness, note that $\Gamma^{A}$ is $\Sigma_{1}$ in
$A$ and therefore computable by $K^{A}$. Also, the limits
$\lim_{s}\psi^{e}_{s}$, when they exist, enumerate all the $\Delta^{0}_{2}$
functions by Shoenfield’s limit lemma. Thus the $P_{e}$ requirements ensure no
$\Delta^{0}_{2}$ function computes $K^{A}$, making $A$ nonlow.

To meet a single $P_{e}$, begin by picking a _follower_ $y$ for $P_{e}$. Wait
for $\psi^{e}(y)[s]=0$. Then $P_{e}$ will want to pick a large _use_ $u$, and
_diagonalize $\Gamma^{A}$ out of $\psi^{e}$ at $y$_ by declaring
$\Gamma^{A\restriction u}(y)[s]\downarrow$. We say that $P_{e}$ wants to _act
via picking use_. But $P_{e}$ needs approval from all $N<P_{e}$ before acting
so as not to injure these $N$-requirements too often. If some $N(x)$’s quota
does not tolerate another action from $P_{e}$, then $P_{e}$ must wait for
$\Phi^{A}_{N}(x)$ to stabilize first before acting. Quota for all $N(x)$’s is
designed to be generous enough to allow $P_{e}$ to eventually act.

After acting, wait for $\psi^{e}(y)$ to change its mind to equal 1. Then
$P_{e}$ will want to enumerate $u$ into $A$. The enumeration will diagonalize
$\Gamma^{A}$ out of $\psi^{e}$ at $y$ because
$\Gamma^{(A\cup\\{u\\})\restriction u}(y)[s]$ is not yet declared to converge
and therefore diverges at stage $s$. We say that $P_{e}$ wants to _act via
enumerating use_. Like before, $P_{e}$ waits for approval from all $N<P_{e}$
to act. After acting, $P_{e}$ is considered to have no assigned use. So if
$\psi^{e}(y)$ returns to 0 later, $y$ will need to be assigned a new use like
before, and we repeat the earlier process of waiting for approval to act via
picking use.

Observe that if the follower $y$ picked was such that
$\lim_{s}\psi^{e}_{s}(y)$ does not exist, then $y$ will act infinitely often,
enumerating infinite elements into $A$. Let $P_{e}(k)$ denote the sub-
requirement of $P_{e}$ that works to enumerate $k$ elements into $A$ for
$P_{e}$ since the beginning of the construction. To reduce the number of
variables used, if context is clear, we drop the subscript $e$ and write $P$
for $P_{e}$, and $P(k)$ for $P_{e}(k)$. Also, if $P=P_{e}$, we write
$\psi^{P}$ to mean $\psi^{e}$.

Overall Strategy: The conflict between the $N$ and $P$ requirements is now
clear: A given $P$ may enumerate infinite elements into $A$, injuring some $N$
infinitely often, yet each sub-requirement $N(x)$ of $N$ can tolerate only
finite injury from all positive requirements. To distribute injury from $P$
across $N(x)$, we use a quota system where we assign each $N(x)$ a fixed quota
$\texttt{quota}_{N}(x)$ of sub-requirements $P(k)$ allowed to injure $N(x)$.
So if $P(k)$ lies in $\texttt{quota}_{N}(x)$, then $N(x)$ allows $P$ to act
$k$ times. $\texttt{quota}_{N}(x)$ needs to be generous enough so that every
$P$ gets infinite opportunities to act, yet also restrictive enough so that
every $N(x)$ suffers only finite injury:

  * •

$(\forall N,P,k)(\exists\text{ cofinite }x)\;[P(k)\in\texttt{quota}_{N}(x)]$

  * •

$(\forall N,x)\;[|\texttt{quota}_{N}(x)|<\omega]$.

To these ends, we set

$\texttt{quota}_{N}(x)=\\{P(k):\;(\exists k^{\prime})\;[\langle
P,k^{\prime}\rangle<x\quad\&\quad 1\leq k\leq k^{\prime}]\\}.$

This quota is generous enough: Given $P(k)$, if $P$ wishes to act for the
$k$-th time, then for all $x>\langle P,k\rangle$, $N(x)$ will allow $P$ to
act. In other words, $N$ will allow $P$ to enumerate the $k$-th element the
moment computations $\Phi^{A}_{N}(0),\ldots,\Phi^{A}_{N}(\langle P,k\rangle)$
have finalized.

At the same time, the quota is restrictive enough because $N(x)$ will only
suffer injury in the scale of $|\texttt{quota}_{N}(x)|$, which is finite. Any
$P$ with $P(1)\not\in\texttt{quota}_{N}(x)$ will always be initialized by
$N(x)$ if $P$ threatens $\Phi^{A}_{N}(x)$, meaning there are only finitely
many $P$ that can ever injure $N(x)$.

Consider when $N$ should allow $P$ to act via enumeration. If
$P(1)\in\texttt{quota}_{N}(x)$, then $N(x)$ must never initialize $P$ if $P$
is to get enough chances to act. Therefore $N$ must always allow such $P$ to
enumerate uses, even if $P$ has injured $N(x)$ $k$-times already and
$P(k)\not\in\texttt{quota}_{N}(x)$.

Now consider when $N$ should allow $P$ to act via picking use. If $P$ wants to
pick a new use, $N(x)$ will use the quota system to bound injury inflicted by
$P$: If $P$ has acted $k$-times and $P(k+1)\in\texttt{quota}_{N}(x)$, then
$N(x)$ will allow $P$ to pick a new use. But if
$P(k+1)\not\in\texttt{quota}_{N}(x)$, $P$ must wait till computation $N(x)$ is
“correct” first before being allowed to act. That is, $P$ must wait for the
stage $s$ where for all $P^{\prime}<P$, the use assigned to $P^{\prime}$, if
any, exceeds $\operatorname{use}(\Phi^{A}_{N}(x)[s])$. By making $P$ wait, the
excess injury on $N(x)$ after $P$’s $k$-th action can be bounded, even if $P$
was wrong about the “correctness” of computation $\Phi^{A}_{N}(x)$. The proof
of boundedness uses a combinatorial argument, which we will show in Main Lemma
1.6.

Summarizing, the quota system distributes injury from $P$ across all $N(x)$
such that every $P$ only needs wait for finitely many $N(x)$ to finalize
before being allowed to act, every $N(x)$ can only be injured by finitely many
$P$, and each such $P$ can injure $N(x)$ only finitely often.

Tree Construction: $P$-requirements can inflict either finite or infinite
injury, so we say that $P$ has _outcome_ fin or $\infty$. Given $N<P$, $N$
would play a different strategy depending on $P$’s outcome. If $P$ has outcome
fin, then $N$ will wait for $P$ to finish acting before beginning to protect
the $N$-computations. But if $P$ has outcome $\infty$, then $N$, knowing $P$
will enumerate larger and larger elements into $A$, will wait till the
elements enumerated are too large to ever cause injury before protecting
$\Phi^{A}_{N}$.

Similarly, $N$-requirements can injure $P$-requirements finitely or infinitely
often, depending on whether $\Phi^{A}_{N}$ is non-total or total respectively.
And $P$ changes strategy depending on the injury outcome of a higher priority
$N<P$. If $N$ has outcome fin, then $P$ will wait for $N$ to stabilize before
acting. And if $N$ has outcome $\infty$, then $P$ will wait for all sub-
requirements $N(y)$ whose quota cannot tolerate another injury from $P$ to
stabilize first before $P$ acts.

The framework of changing strategies based on the outcomes of higher priority
requirements is often implemented using trees. Since our $P$ and $N$
requirements can have _outcomes_ from

$\texttt{outcomes}:=\\{\infty<\texttt{fin}\\},$

our tree of construction is

$\Lambda:=\\{\infty,\texttt{fin}\\}^{<\omega}.$

Prioritize the requirements $N_{0}<P_{0}<N_{1}<P_{1}<\ldots$. Then a node
$\delta\in\Lambda$ works for $N_{e}$ if $|\delta|=2e$, and works for $P_{e}$
if $|\delta|=2e+1$. Given $\delta\in\Lambda$, if $\delta$ works for $N_{e}$,
we write $\delta=\eta_{e}$. Often we drop the subscript $e$ and write $\eta$
in place of $\eta_{e}$ and $\Phi^{A}_{\eta}$ in place of $\Phi^{A}_{e}$. Also,
we write $\eta(x)$ to refer to the sub-requirement of $\eta$ that works to
protect $\Phi^{A}_{\eta}(x)$. Similarly, if $\delta$ works for $P_{e}$, we
write $\delta=\rho_{e}$. We often drop the subscript $e$ and write $\rho$ for
$\rho_{e}$ and $\psi^{\rho}$ for $\psi^{e}$. Also, we write $\rho(k)$ to mean
the sub-requirement that works to get $\rho$ to act $k$ times since the
beginning of the construction (as opposed to since the last time $\rho$ was
initialized).

Let the current stage be $s$. Given a node $\delta\in\Lambda$, depending
whether $\delta=\eta$ or $\delta=\rho$, we initialize and design
$\delta$-strategy as follows:

Initialize $\eta$: Do nothing.

Outcome of $\eta$: Roughly speaking, we guess that $\eta$ has outcome $\infty$
iff more $\Phi^{A}_{\eta}$ computations have converged since the previous
$\eta$-stage. However some of these computations may not be “correct” yet
because they will subsequently be injured by $\rho\prec\eta$ with infinite
outcome. Specifically, if $\rho^{\frown}\infty\preceq\eta$ and $\rho$’s use
$u$ does not exceed $\operatorname{use}(\Phi^{A}_{\eta}(x)[s]\downarrow)$,
then $u$ will eventually be enumerated into $A$ because $\rho$ is expected to
act infintely often. The enumeration injures computation $\Phi^{A}_{\eta}(x)$,
so this computation is “incorrect” at stage $s$. Therefore when we guess the
outcome of $\eta$, we count only the number of “correct” $\eta$-computations,
and let $\eta$ have outcome $\infty$ iff this number has increased.

Formally, given $x\in\omega$ and comparable nodes
$\delta,\delta^{\prime}\in\Lambda$, we say _computation
$\Phi^{A}_{\delta}(x)[s]$ is $\delta^{\prime}$-correct at stage $s$_ if for
all $\rho\preceq\delta^{\prime}$ such that $\rho=\delta^{\prime}$ or
$\rho^{\frown}\infty\preceq\delta^{\prime}$, if $\rho$ has an assigned use $u$
at stage $s$, then $u>\operatorname{use}(\Phi^{A}_{\delta}(x)[s])$. Also,
define the _length of $\eta$ at stage $s$_ as

$l_{s}(\eta):=\max\left\\{x\leq s:(\forall
y<x)\;\left[\Phi^{A}_{\eta}(y)[s]\downarrow\text{ and is
}\eta\text{-correct}\right]\right\\}.$

We say _$s$ is an $\eta$-expansionary stage_ iff

$l_{s}(\eta)>\max\\{l_{s^{\prime}}(\eta):\;s^{\prime}<s\text{ and
}s^{\prime}\text{ is an }\eta\text{-stage}\\},$

and let $\eta$ have outcome $\infty$ iff $s$ is $\eta$-expansionary.

$(\eta^{\frown}\texttt{fin})$-strategy: Do nothing.

$(\eta^{\frown}\infty)$-strategy: Following the discussion in “Overall
Strategy”, given $x\in\omega$, allocate $\eta(x)$ a fixed quota
$\texttt{quota}_{\eta}(x)$ to distribute injury from positive requirements
across negative ones in a generous yet restrictive manner:

$\displaystyle\texttt{quota}_{\eta}(x)=$
$\displaystyle\\{\rho(k):\;\Phi^{A}_{\eta}(x)\text{ allows }\rho\text{ to act
}k\text{-times}\\}$ $\displaystyle:=$ $\displaystyle\\{\rho(k):\;(\exists
k^{\prime})\;\left[\langle\rho,k^{\prime}\rangle<x\quad\&\quad 1\leq k\leq
k^{\prime}\right]\\}.$ (1)

Since $\texttt{quota}_{\eta}(x)$ does not depend on $\eta$, we drop the
subscript $\eta$ and just write $\texttt{quota}(x)$. If
$\rho(1)\in\texttt{quota}(x)$, we say _$\rho$ lies in the quota of $x$_, and
write $\rho\in\texttt{quota}(x)$. Define the _quota for $\rho$ from $x$_ as

$\texttt{quotaFor}_{x}(\rho):=\max\\{k:\;\rho(k)\in\texttt{quota}(x)\\}.$

We say _$\rho$ has exhausted its quota from $x$ at stage $s$_ if $\rho$ has
acted $k$-times at stage $s$ since the beginning of construction (as opposed
to since the last time $\rho$ was initialized), but
$\rho(k+1)\not\in\texttt{quota}(x)$. From earlier discussion, given
$x\in\omega$, _$\eta(x)$ allows $\rho\succeq\eta^{\frown}\infty$ to act via
picking use at stage $s$_ iff any of the following hold:

  * •

$\Phi^{A}_{\eta}(x)$ is $\rho$-correct at stage $s$

  * •

$\rho$ has not yet exhausted its quota from $x$ at stage $s$

_$\eta(x)$ allows $\rho$ to act via enumerating use at stage $s$_ iff any of
the following hold:

  * •

The use of $\rho$ at stage $s$ exceeds
$\operatorname{use}(\Phi^{A}_{\eta}(x)[s])$

  * •

$\rho\in\texttt{quota}(x)$.

_$\eta$ allows $\rho$ to act at stage $s$_ iff for all $x<l_{s}(\eta)$,
$\eta(x)$ allows $\rho$ to act at stage $s$.

Note that by $\eta(x)$’s strategy for allowing $\rho$ to act via enumeration,
the only $\rho$ that can injure $\eta(x)$ are those that lie in the quota of
$x$, and there are only finitely many such $\rho$. Also, given
$\rho,\eta\in\Lambda$, only finitely many $\eta(x)$ can initialize $\rho$
because $\rho\in\texttt{quota}(x)$ for all large enough $x$. Therefore the
quota system is both restrictive enough for $\eta(x)$ requirements and
generous enough for $\rho$ requirements.

Initialize $\rho$: Destroy the follower and use assigned to $\rho$, if any. So
the next time $\rho$ is visited, $\rho$ is considered to have neither follower
nor use.

Outcome of $\rho$: If $\rho$ does not have a follower $y$ at this stage $s$,
assign a large one. By our construction, if $\rho$ has an assigned use $u$
then $\Gamma^{A\restriction u}(y)[s]\downarrow$, and if $\rho$ does not have
an assigned use, then $\Gamma^{A}(y)[s]\uparrow$. $\rho$ has outcome $\infty$
if $\psi^{\rho}(y)$ has changed its mind again such that $\Gamma^{A}(y)$ is no
longer diagonalized out of $\psi^{\rho}(y)$. Formally, $\rho$’s outcome is
$\infty$ iff any of the following hold:

  1. 1.

$\psi^{\rho}_{s}(y)=0$ and $\rho$ has no assigned use

  2. 2.

$\psi^{\rho}_{s}(y)=1$ and $\rho$ has an assigned use

In the first case we say _$\rho$ wants to act via picking use_, and in the
second case we say _$\rho$ wants to act via enumerating use_.

$(\rho^{\frown}\texttt{fin})$-strategy: Let $y$ be the follower assigned to
$\rho$. If $\psi^{\rho}_{s}(y)=0$ and $\rho$ has an assigned use $u$ at this
stage, then _$\rho$ diagonalizes $\Gamma^{A}_{\rho}$ out of $\psi^{\rho}$_ by
declaring $\Gamma^{A\restriction u}(y)[s]\downarrow$.

$(\rho^{\frown}\infty)$-strategy: For $\rho$’s outcome to be $\infty$, $\rho$
must have wanted to act. If $\rho$ wants to act via picking use, then $\rho$
will want to pick a new large use $u$ for its follower $y$ and diagonalize
$\Gamma^{A}_{\rho}$ out of $\psi^{\rho}$ by declaring $\Gamma^{A\restriction
u}(y)[s]\downarrow$. If $\rho$ wants to act via enumerating use $u$, then
$\rho$ will want to enumerate $u$ into $A$, so the next time $\rho$ is
accessed, $\rho$ is considered to have no assigned use. _$\rho$ is allowed to
act_ only if every $\eta^{\frown}\infty\preceq\rho$ allows $\rho$ to act at
stage $s$. Refer to $(\eta^{\frown}\infty)$-strategy for what it means for
$\eta$ to allow $\rho$ to act. If $\rho$ is not allowed to act via
enumeration, then all $\delta\succeq\rho$ and $\delta\geq_{L}\rho$ will be
initialized.

Playing the $\eta$ and $\rho$ strategies in a tree framework, we construct the
nonlow $\operatorname{low}_{2}$ c.e. set $A$:

Stage $s$: Let $\delta_{s,0}$ be the empty node. From step $e=0$ to $s$:
Determine the outcome $o\in\\{\infty,\texttt{fin}\\}$ of $\delta_{s,e}$. Set
$\delta_{s,e+1}=\delta_{s,e}^{\frown}o$, and initialize all nodes to the right
of $\delta_{s,e+1}$. If $\delta_{s,e+1}=\rho^{\frown}\texttt{fin}$, play the
$(\rho^{\frown}\texttt{fin})$-strategy described above to diagonalize
$\Gamma^{A}_{\rho}$ out of $\psi^{\rho}$.

At the end of step $s$, we will get a node
$\delta_{s}:=\delta_{s,s}\in\Lambda$ of length $s$. Some of the positive
initial segments $\rho\preceq\delta_{s}$ may have outcome $\infty$, meaning
that they want to act. Let

$\displaystyle\Theta$
$\displaystyle=\\{\rho\preceq\delta_{s}:\;\rho^{\frown}\infty\preceq\delta_{s},\text{
and }\rho\text{ wants to pick use at stage }s\text{ and is allowed}\\}$
$\displaystyle\cup\\{\rho\preceq\delta_{s}:\;\rho^{\frown}\infty\preceq\delta_{s},\text{
and }\rho\text{ wants to enumerate use at stage }s\\}.$

If $\Theta$ is empty, go to the next stage. Otherwise, select one
$\rho\in\Theta$. This $\rho$ will be called _the selected node at stage $s$_,
and is selected as:

$\rho=\underset{\rho^{\prime}\in\Theta}{\mathrm{argmin}}\;\\{\langle\rho^{\prime},k\rangle:\;\rho^{\prime}\text{
has been selected }k\text{-times before stage }s\\}.$

Play the $(\rho^{\frown}\infty)$-strategy described above. Go to next stage.

######  Lemma 2.2.

$|\delta_{\omega}|=\omega$.

###### Proof.

Follows immediately from the facts that $|\delta_{s}|$ is increasing in $s$
and that $\Lambda$ is finitely branching. ∎

######  Main Lemma 1.

Given $n\in\omega$, let $\delta=\delta_{\omega}\restriction n\in\Lambda$.

  1. 1.

If $\delta=\rho$ then $\rho$ eventually stops being initialized. Thus $\rho$
has a final follower $y_{\rho}$.

  2. 2.

If $\delta=\rho$ and $\rho^{\frown}\texttt{fin}\prec\delta_{\omega}$, then if
$\lim_{s}\psi^{\rho}_{s}(y_{\rho})$ exists the limit will not equal
$\chi_{\Gamma^{A}}(y_{\rho})$.

  3. 3.

If $\delta=\rho$ and $\rho^{\frown}\infty\prec\delta_{\omega}$, then $\rho$
will act infinitely often. Thus $\lim_{s}\psi^{\rho}_{s}(y_{\rho})$ does not
exist.

  4. 4.

If $\delta=\eta$, then $\eta$ eventually stops being initialized.

  5. 5.

If $\delta=\eta$ and $\eta^{\frown}\texttt{fin}\preceq\delta_{\omega}$, then
$\Phi^{A}_{\eta}$ is not total.

  6. 6.

If $\delta=\eta$ and $\eta^{\frown}\infty\preceq\delta_{\omega}$, then
$\Phi^{A}_{\eta}$ is total.

We prove Main Lemma 1 after this immediate corollary:

######  Corollary 2.3.

$A$ is $\operatorname{low}_{2}$ nonlow.

###### Proof.

Let $e\in\omega$. We show that all $P_{e}$ and $N_{e}$ are satisfied. Let
$\rho=\delta_{\omega}(2e+1)$, which works for $P_{e}$. If
$\rho^{\frown}\texttt{fin}\prec\delta_{\omega}$, then from Lemmas 2.2 and Main
Lemma 1.2, if $\lim_{s}\psi^{e}_{s}(y_{\rho})$ exists, $P_{e}$ will be
satisfied with witness $y_{\rho}$. If the limit does not exist, then $P_{e}$
will be vacuously true. On the other hand, if
$\rho^{\frown}\infty\prec\delta_{\omega}$, then from Lemmas 2.2 and Main Lemma
1.3, $\lim_{s}\psi^{e}_{s}(y_{\rho})$ cannot exist, so $P_{e}$ will be
vacuously true.

From Lemma 2.2 and Main Lemmas 1.5 and 1.6, $\forall e\in\omega$,

$\Phi^{A}_{e}\text{ is total}\iff\delta_{\omega}(2e)=\infty.$

Then since $\delta_{\omega}\leq_{T}\emptyset^{\prime\prime}$, we get
$\text{Tot}^{A}\leq_{T}\emptyset^{\prime\prime}$, so $A$ is
$\operatorname{low}_{2}$. ∎

We prove the 6 claims of Main Lemma 1 by simultaneous induction on $n$. In
each claim for $\delta\in\Lambda$, always assume that we are working in
$\delta$-stages after higher priority requirements or sub-requirements have
“stabilized”. These stages exist from induction hypothesis.

Formally, _requirement $\delta\in\Lambda$ has stabilized at stage $s$_ if no
$\delta^{\prime}\preceq\delta$ ever gets initialized at or after stage $s$.
Such stages exist from induction hypothesis on Main Lemma 1.1 and 1.4. _Sub-
requirement $\rho(k)$ has stabilized at stage $s$_ if for all
$\langle\rho^{\prime},k^{\prime}\rangle\leq\langle\rho,k\rangle$, if node
$\rho^{\prime}\in\Lambda$ is ever selected $k^{\prime}$-times or less since
the beginning of the construction, then these selections have already been
made by stage $s$. _Sub-requirement $\eta(x)$ has stabilized at stage $s$_ if
$\eta$ has stabilized at stage $s$, and computations
$\Phi^{A}_{\eta}\restriction(x+1)$ are never injured again at or after stage
$s$. Such stages exist from induction hypothesis on Main Lemma 1.6.

######  Claim (Main Lemma 1.1).

If $\rho\prec\delta_{\omega}$, then $\rho$ eventually stops being initialized.

###### Proof.

Wait for all $\delta\prec\rho$ to stabilize. We can assume
$\rho^{\frown}\infty\prec\delta_{\omega}$ otherwise $\rho$ will never be
initialized again. From the $(\eta^{\frown}\infty)$-strategy, if $\eta(x)$
initializes $\rho$, then $\eta(x)$ must have satisfied
$\eta^{\frown}\infty\preceq\rho$ and $\rho\not\in\texttt{quota}(x)$. There are
only finitely many such $\eta(x)$, so wait for all of them to stabilize, which
will eventually occur from induction hypothesis. Now these $\eta(x)$ will
initialize $\rho$ when $\rho$ wants to act via enumeration but the use of
$\rho$ does not exceed the use of $\eta(x)$. But after stabilizing, and after
possibly one more initialization from $\eta(x)$, $\rho$ will always pick a use
that exceeds $\operatorname{use}(\eta(x))$. Then $\eta(x)$ will forever allow
$\rho$ to enumerate use and therefore never initialize $\rho$ again.
∎

######  Claim (Main Lemma 1.2).

If $\rho^{\frown}\texttt{fin}\prec\delta_{\omega}$, then if
$\lim_{s}\psi^{\rho}_{s}(y_{\rho})$ exists the limit will not equal
$\chi_{\Gamma^{A}}(y_{\rho})$.

###### Proof.

From construction, $\rho$ will choose outcome $\infty$ the moment
$\psi^{\rho}(y_{\rho})$ agrees with $\chi_{\Gamma^{A}}(y_{\rho})$. ∎

######  Claim (Main Lemma 1.3).

If $\rho^{\frown}\infty\prec\delta_{\omega}$, then $\rho$ will act infinitely
often. Thus $\lim_{s}\psi^{\rho}_{s}(y_{\rho})$ does not exist.

###### Proof.

Assume for contradiction that $\rho$ only gets to act $(k-1)$-times during the
construction, which implies that $\rho$ was selected $\geq(k-1)$-times. Wait
for $\rho$ and $\rho(k)$ to stabilize. Then $\rho$ will always have the
highest priority to act.

First consider the case where $\rho$’s $k$-th action is to pick a use. From
the $(\eta^{\frown}\infty)$-strategy, if $\eta(x)$ disallows $\rho$ to pick
use, then $\eta^{\frown}\infty\preceq\rho$ and $\rho$ has exhausted its quota
from $x$. But since $\rho$ never acts more than $(k-1)$-times, there are only
finitely many $\eta(x)$ satisfying these two conditions. Wait for all such
$\eta(x)$ to stabilize. We show that $\eta(x)$ is eventually $\rho$-correct,
so that $\rho$ will be allowed by $\eta(x)$ to pick use: Let $\rho^{\prime}$
be such that
$\eta(x)^{\frown}\infty\preceq\rho^{\prime\frown}\infty\preceq\rho$. We need
to show that the uses of $\rho^{\prime}$ eventually exceed
$\operatorname{use}(\eta(x))$. But this is true because $\rho^{\prime}$ gets
to act infinitely often from induction hypothesis.

So it must be that $\rho$’s $k$-th action was to enumerate use. Now from
construction, if $\rho$ has highest priority to act and $\rho$ wants to act
via enumeration, then $\rho$ will be selected, even if some
$\eta^{\frown}\infty\preceq\rho$ does not allow $\rho$ to enumerate use. And
should such $\eta$ exist, then $\rho$ will be initialized. But $\rho$ has
already stabilized, a contradiction. ∎

######  Claim (Main Lemma 1.4).

If $\eta\prec\delta_{\omega}$, then $\eta$ eventually stops being initialized.

###### Proof.

Wait for all $\rho\prec\eta$ to stabilize. Then $\eta$ will never be
initialized again. ∎

######  Claim (Main Lemma 1.5).

If $\eta^{\frown}\texttt{fin}\prec\delta_{\omega}$, then $\Phi^{A}_{\eta}$ is
not total.

###### Proof.

Assume for contradiction $\Phi^{A}_{\eta}$ is total. We claim that given
arbitrary $x$, computation $\Phi^{A}_{\eta}(x)$ is eventually $\eta$-correct.
Equivalently, we are claiming that if $u$ is a use assigned to $\rho$ where
$\rho^{\frown}\infty\prec\eta$, and
$u<\operatorname{use}(\Phi^{A}_{\eta}(x))$, then $u$ must eventually be
enumerated into $A$. This claim is induction hypothesis with Main Lemma 1.3.
Then $\eta^{\frown}\infty\prec\delta_{\omega}$, a contradiction. ∎

######  Claim (Main Lemma 1.6).

If $\eta^{\frown}\infty\prec\delta_{\omega}$, then $\Phi^{A}_{\eta}$ is total.

This claim is the heart of the argument on why the construction works. Always
assume we are working in the $(\eta^{\frown}\infty)$-stages after $\eta$
stabilizes. The proof idea is that given $x\in\omega$, the moment
$\Phi^{A}_{\eta}\restriction(x+1)\downarrow$, the only $\rho\in\Lambda$ that
can injure $\eta(x)$ are those that lie in the quota of $x$. But there are
only finitely many such $\rho$, and we will show that each of them will
eventually stop injuring $\eta(x)$:

The first $\rho$ to stop injuring $\eta(x)$ are those that know the outcomes
of higher priority injurious nodes. That is, $\rho$ can injure $\eta(x)$, but
no $\rho^{\prime}\succeq\rho^{\frown}\infty$ can injure $\eta(x)$ again. We
call such nodes _edge nodes_ , for they can be seen as the outer most layer of
nodes that can injure $\eta$. Wait for edge nodes $\rho$ to exhaust their
quota from $x$. Then $\rho$ can act only when $\eta(x)$ is $\rho$-correct;
that is, when $\rho$ believes the action will not injure $\eta(x)$. But having
no extension that can injure $\eta(x)$, $\rho$ has complete knowledge of the
outcomes of all relevant injurious nodes. In particular, when $\rho$ believes
an action will never injure $\eta(x)$, that action will indeed never injure
$\eta(x)$.

Therefore after exhausting quota, edge nodes can never injure $\eta(x)$, and
can be removed from the set of nodes that are injurious to $\eta(x)$. Peeling
away this outer layer of nonthreatening nodes exposes an inner layer of nodes,
which will become the new edge nodes. This inner layer nodes will also
eventually exhaust quota and stop injuring $\eta(x)$. Peeling away the inner
layer nodes exposes an even inner layer of new edge nodes. Repeating this
process, since only finitely many nodes can injure $\eta(x)$, eventually all
layers of these nodes will be peeled away until no nodes are left to injure
$\eta(x)$, completing the proof.

Formally, let $x\in\omega$ and $\eta^{\frown}\infty\prec\delta_{\omega}$, and
we will show that $\Phi^{A}_{\eta}(x)\downarrow$. Work only in
$(\eta^{\frown}\infty)$-stages after $\eta$ stabilizes. The following fact
follows directly from the $(\eta^{\frown}\infty)$-strategy of the
construction:

######  Fact 2.4.

For all $s\in\omega$ and $\eta\in\Lambda$,

$\\{\rho:\rho\text{ will injure }\eta(x)\text{ at an
}(\eta^{\frown}\infty)\text{-stage}\\}\subseteq\\{\rho:\;\rho\in\texttt{quota}(x)\\},$

Note that the larger set is finite, computable, and independent from $\eta$.

######  Definition 2.5.

We call $\rho$ an edge node for $\eta(x)$ at stage $s$ if no
$\rho^{\prime}\succeq\rho^{\frown}\infty$ injures $\eta(x)$ at or after stage
$s$.

######  Claim 2.6.

If $\rho\in\texttt{quota}(x)$ is an edge node for $\rho$ at stage $s$, the
injury that $\rho$ can inflict on $\eta(x)$ after stage $s$ is bounded by
$\texttt{quotaFor}_{x}(\rho)+1$.

###### Proof.

Wait for $\rho$ to exhaust its quota from $x$ after stage $s$, inflicting no
more than $\texttt{quotaFor}_{x}(\rho)$ injury on $\eta(x)$. We show that
$\rho$ cannot injure $\eta(x)$ more than once: Then if $\rho$ has an assigned
use, wait for that use to be enumerated, possibly injuring $\eta(x)$ one last
time. If the use is never enumerated, then $\rho$ can never injure $\eta(x)$,
and we are done. After enumerating use, assume that $\rho$ eventually wants to
pick a new use, otherwise we are again done. Then since $\rho$ has exhausted
its quota from $x$, the $(\eta^{\frown}\infty)$-strategy will only allow
$\rho$ to pick a new use when $\eta(x)$ is $\rho$-correct.

Assume for contradiction that $\rho$ injures $\eta(x)$ at stage $s_{2}$, via a
use that was picked at stage $s_{0}<s_{2}$. That means between picking that
use and injuring $\eta(x)$, there must have been a first
$\rho^{\prime}\succeq\eta^{\frown}\infty$ that injured $\eta(x)$, say at stage
$s_{1}>s_{0}$, $s_{1}<s_{2}$. Now $\rho^{\prime}\not\preceq\rho$ since
$\eta(x)$ was $\rho$-correct when $\rho$ picked its new use. Yet
$\rho^{\prime}\not\succeq\rho$ because no $\rho^{\prime}\succeq\rho$ can
injure $\eta(x)$, by choice of $\rho$ being an edge node. Also,
$\rho^{\prime}\not<_{L}\rho^{\frown}\infty$ otherwise $\rho$ would be
initialized at stage $s_{1}$ and cannot injure $\eta(x)$ later with the use
that was picked at stage $s_{0}$. Finally, $\rho^{\prime}\not>_{L}\rho$
because $\rho$ would have initialized $\rho^{\prime}$ at stage $s_{0}$,
implying that the use of $\rho^{\prime}$ at stage $s_{1}$ must exceed the use
of $\rho$ at stage $s_{0}$. So $\rho^{\prime}$ cannot exist. ∎

######  Definition 2.7.

The edge layer of $\rho$ with respect to $x$ is defined as

$\max_{\begin{subarray}{c}\rho^{\prime}\succeq\rho^{\frown}\infty\\\
\rho^{\prime}\in\texttt{quota}(x)\end{subarray}}(|\\{\rho^{\prime\prime}:\rho^{\frown}\infty\preceq\rho^{\prime\prime}\preceq\rho^{\prime}\\}|).$

So the the outer most layer of nodes that lie in $\texttt{quota}(x)$ have edge
layer 0, and inner layer nodes have higher edge layer number. In particular,
if $\rho^{\prime}\succ\rho$, then $\rho^{\prime}$ has smaller edge layer than
$\rho$.

###### Proof.

(Of Main Lemma 1.6): From Fact 2.4, only nodes that lie in $\texttt{quota}(x)$
can injure $\eta(x)$. Let $\rho\in\texttt{quota}(x)$, and $r$ be the edge
layer of $\rho$ with respect to $x$. We prove by induction on $r$ that $\rho$
eventually stops injuring $\eta(x)$. The base case is Claim 2.6. From
induction hypothesis, all nodes $\rho^{\prime}\in\texttt{quota}(x)$ with edge
layer $<r$ will eventually stop injuring $\eta(x)$. When that happens $\rho$
becomes an edge node for $\eta(x)$, and will also stop injuring $\eta(x)$ from
Claim 2.6. Since $|\texttt{quota}(x)|$ is finite, eventually all nodes stop
injuring $\eta(x)$. ∎

###  2.3 Nonlow, Array Computable

We show in this section that the nonlow $\operatorname{low}_{2}$ c.e. set
constructed in Theorem 2.1 is array computable. Array computability was
introduced by Downey, Jockusch, and Stob [4], after observing how sufficient
fickleness was enough to satisfy many commonly encountered embeddability
requirements. Array computable degrees are the least fickle c.e. degrees, and
can be characterized as follows:

######  Definition 2.8.

A c.e. degree $\bm{d}$ is array computable [5] iff there exists a computable
$m:\omega\to\omega$ such that every $A\in\bm{d}$ has an $m$-bounded computable
approximation. That is, $A$ has a uniformly computable approximation
$a_{s}(x)\equiv_{T}\emptyset$ such that $\forall x\in\omega$,

  * •

$A(x)=\lim_{s}a_{s}(x)$, and

  * •

$|\\{s\in\omega:\;a_{s}(x)\neq a_{s+1}(x)\\}|\leq m(x)$.

Array computability turns out to characterize the c.e. degrees with a strong
minimal cover [8], showing again the connection between fickleness and lattice
structure. The set just constructed has the least possible fickleness:

######  Theorem 2.9.

The nonlow $\operatorname{low}_{2}$ c.e. $A$ constructed in Theorem 2.1 is
array computable.

We use notations from the proof of Theorem 2.1. Let
$\eta^{\frown}\infty\prec\delta_{\omega}$. Work only in the
$(\eta^{\frown}\infty)$-stages after $\eta$ has stabilized. Define

$\displaystyle S_{\eta}$ $\displaystyle:=\\{s\in\omega:\;s\text{ is
}(\eta^{\frown}\infty)\text{-stage after }\eta\text{ has stabilized}\\},$ (2)
$\displaystyle t_{\eta}(x)$ $\displaystyle:=(\mu\;s\in
S_{\eta})\;\left[\Phi^{A}_{\eta}\restriction(x+1)[s]\downarrow\right],$ (3)
$\displaystyle a_{\eta,s}(x)$
$\displaystyle:=\Phi^{A}_{\eta}(x)[s^{\prime}],\quad\text{ where
}s^{\prime}=\mu(s^{\prime}\in S_{\eta})\;[s^{\prime}\geq\max(s,t_{\eta}(x))].$
(4)

Note that $a_{\eta,s}(x)$ is the canonical computable approximation of
$\Phi^{A}_{\eta}(x)$ that we get from our construction. Also note that for a
fixed $\eta$, $S_{\eta}$ and $t_{\eta}(x)$ are computable, but not uniformly
computable. We need to define a computable $m:\omega\to\omega$ such that for
every $\eta^{\frown}\infty\prec\delta_{\omega}$ and $x\in\omega$,

$|\\{s\in S_{\eta},s\geq t_{\eta}(x):\;a_{\eta,s}(x)\neq
a_{\eta,s+1}(x)\\}|\leq m(x).$

Equivalently, we want to computably bound the injury on $\eta(x)$ at the
$S_{\eta}$-stages after stage $t_{\eta}(x)$, and also show that this bound is
independent from $\eta$. Our proof outline follows the proof of Main Lemma
1.6, where we bounded injury on $\eta(x)$. Independence from $\eta$ follows
directly from the fact that $\eta$’s quota for $x$ $\texttt{quota}_{\eta}(x)$
(Eq. (2.2)) does not depend on $\eta$. Therefore our proof of computable
boundedness for a given $\eta$ will also hold for arbitrary $\eta$.

Now we show that the injury bound in Main Lemma 1.6 is computable as a
function of $x$. Fact 2.4 gave a computable and finite bound on the set of
nodes that can injure $\eta(x)$. We computably bound the injury from each
$\rho$ in the set to computably bound the total injury on $\eta(x)$. We show
that after exhausting quota, any injury inflicted by $\rho$ must be
“triggered” by injury from some $\rho^{\prime}\neq\rho$ of smaller edge layer
than $\rho$:

Wait for $\rho$ to exhaust quota from $x$. Then $\rho$ will only act when
$\eta(x)$ is $\rho$-correct. But because $\rho$ may not yet be an edge node,
$\rho$ may not see the outcomes of injurious nodes extending
$\rho^{\frown}\infty$, and may misjudge the correctness of $\eta(x)$. For
example, $\rho$ may pick a use at a $\rho$-correct stage $s$, thinking that
computation $\eta(x)$ has finalized. Unknowing to $\rho$, some $\rho^{\prime}$
with use $u^{\prime}<\operatorname{use}(\Phi^{A}_{\rho}(x)[s])$ will injure
$\eta(x)$ later. The restored use of $\eta(x)$ exceeds $u$, so $\rho$ is
triggered to unexpectedly injure $\eta(x)$ when $\rho$ enumerates $u$ into
$A$. But $\rho^{\prime}$ cannot have been an initial segment of $\rho$,
because otherwise $\rho$ would have seen the outcome of $\rho^{\prime}$,
contradicting $s$ being a $\rho$-correct stage. In fact, $\rho^{\prime}$ also
cannot lie to the left or right of $\rho$ because the tree strategy makes
these nodes irrelevant to the argument. So $\rho^{\prime}$ must extend
$\rho^{\frown}\infty$ as nodes, implying that $\rho^{\prime}$ has smaller edge
layer than $\rho$.

Summarizing, after exhausting quota, whenever $\rho$ injures $\eta(x)$, $\rho$
must be “triggered” by another node of smaller edge layer. Therefore the
number of times $\rho$ injures $\eta(x)$ cannot exceed the total injury from
smaller edge layers. Then by strong induction on edge layer number, we can
computably bound the injury from any node in $\texttt{quota}(x)$. Summing
these bounds gives a computable bound of total injury on $\eta(x)$. Formally:

######  Definition 2.10.

Assume $\rho\in\texttt{quota}(x)$ injures $\eta(x)$ at stage $s$ by
enumerating its use $u$ into $A$, and use $u$ was picked by $\rho$ at some
$\rho$-stage $s^{\prime}\leq s$ after $\rho$ has exhausted quota from $x$.
Then $\operatorname{use}(\eta(x)[s^{\prime}])<u$, so between stages
$s^{\prime}$ and $s$, there must have been a first $\delta\neq\rho$ that
injured $\eta(x)$, causing the use of $\eta(x)$ to eventually exceed $u$. We
say that $\delta$ is the node that triggered $\rho$ to injure $\eta(x)$ at
stage $s$.

######  Claim 2.11.

If $\delta$ is the node that triggered $\rho$ to injure $\eta(x)$ at stage
$s$, then $\delta\succeq\rho^{\frown}\infty$. In particular, if
$\delta=\rho^{\prime}$, then $\rho^{\prime}$ has smaller edge layer than
$\rho$.

###### Proof.

Let $s_{0}<s$ be the $\rho$-stage after $\rho$ exhausted quota and where
$\rho$ picked the use which injured $\eta(x)$ at stage $s$. At stage $s_{0}$,
$\eta(x)$ was $\rho$-correct, implying
$u>\operatorname{use}(\Phi^{A}_{\eta}(x)[s_{0}])$. Let $s_{1}>s_{0}$ be the
$\delta$-stage where $\delta$ enumerated its use $u^{\prime}$ into $A$,
injuring $\eta(x)$ and triggering the future injury from $\rho$. Note that
$u^{\prime}<\operatorname{use}(\Phi^{A}_{\eta}(x)[s_{0}])$ and $u^{\prime}<u$.

Now $\delta\not<_{L}\rho^{\frown}\infty$, otherwise $\delta$ will initialize
$\rho$ at stage $s_{1}$, then $\rho$ cannot have injured $\eta(x)$ at stage
$s_{2}$ with use $u$. Also, $\rho\not<_{L}\delta$, otherwise $\rho$ would have
initialized $\delta$ at stage $s_{0}$, contradicting $u^{\prime}<u$. Finally,
$\delta\not\preceq\rho$, otherwise $\eta(x)$ would not be $\rho$-correct at
stage $s_{0}$ since $u^{\prime}<\operatorname{use}(\Phi^{A}_{\eta}(x[s_{0}])$.
So $\delta$ must extend $\rho^{\frown}\infty$ as nodes.
∎

######  Definition 2.12.

Define the injury power of $\rho$ on $\eta(x)$ as

$\texttt{InjPow}_{\eta}(x,\rho):=\text{Number of times }\rho\text{ injures
}\eta(x)\text{ at the }S_{\eta}\text{-stages after }t_{\eta}(x).$

######  Claim 2.13.

If $\rho\in\texttt{quota}(x)$ has edge layer $r$, then

$\displaystyle\texttt{InjPow}_{\eta}(x,\rho)\leq\texttt{quotaFor}_{x}(\rho)+\sum_{\begin{subarray}{c}\rho^{\prime}\in\texttt{quota}(x)\\\
\rho^{\prime}\text{ has edge layer
}<r\end{subarray}}\;\texttt{InjPow}_{\eta}(x,\rho^{\prime}).$ (5)

###### Proof.

The $\texttt{quotaFor}_{x}(\rho)$ term comes from $\rho$ exhausting quota from
$x$, and the summation term comes from Claim 2.11. ∎

###### Proof.

(Of Theorem 2.9): From Fact 2.4, working only in the
$(\eta^{\frown}\infty)$-stages after stage $t_{\eta}(x)$, the number of times
$\eta(x)$ gets injured equals
$\sum_{\rho\in\texttt{quota}(x)}\texttt{InjPow}_{\eta}(x,\rho)$, where we can
bound each $\texttt{InjPow}_{\eta}(x,\rho)$ computably using the recursive
relation Eq. (5). Together with the fact that $\texttt{quota}(x)$ is a
computable set, the total injury on $\eta(x)$ will be computable and
independent from $\eta$, which completes the proof.

To give a concrete bound of the injury on $\eta(x)$, we assume that the
pairing function used for the definition of $\texttt{quota}(x)$ is such that
$\max\\{\max(|\rho|,k):\;\langle\rho,k\rangle\in\texttt{quota}(x)\\}<x$. Then
we can show that

$\text{Number of times }\eta(x)\text{ gets injured}\leq x^{2}4^{x^{2}}.$ (6)

To prove the above, we first apply induction on edge layer $r$ of
$\rho\in\texttt{quota}(x)$ with Eq. (5) to show that
$\texttt{InjPow}_{\eta}(x,\rho)\leq x(r+1)4^{(r+1)^{2}}$: The claim holds
trivially if $r=0$, so assume $r\geq 1$. By assumption on the pairing
function, for all $\rho^{\prime}$, $\texttt{quotaFor}_{x}(\rho^{\prime})<x$,
so Eq. (5) becomes

$\displaystyle\texttt{InjPow}_{\eta}(x,\rho)\leq$ $\displaystyle
x+\sum_{\begin{subarray}{c}\rho^{\prime}\in\texttt{quota}(x)\\\
\rho^{\prime}\text{ has edge layer
}<r\end{subarray}}\;\texttt{InjPow}_{\eta}(x,\rho^{\prime})$
$\displaystyle\leq$ $\displaystyle
x+|\\{\rho^{\prime}\succ\rho:\;\rho^{\prime}\text{ edge layer
}<r\\}|\cdot\max_{\rho^{\prime\prime}\text{ edge layer
}r-1}\texttt{InjPow}_{\eta}(x,\rho^{\prime\prime})$ $\displaystyle\leq$
$\displaystyle x+2^{r}\cdot\max_{\rho^{\prime\prime}\text{ edge layer
}r-1}\texttt{InjPow}_{\eta}(x,\rho^{\prime\prime})$ $\displaystyle\leq$
$\displaystyle x+2^{r}\cdot\left(xr4^{r^{2}}\right)$
$\displaystyle(\text{induction hypothesis})$ $\displaystyle\leq$
$\displaystyle x2^{2r^{2}+r}+2^{r}\cdot\left(xr4^{r^{2}}\right)$
$\displaystyle(\because\;r\geq 1)$ $\displaystyle=$ $\displaystyle
x(r+1)2^{2(r+1)^{2}-3r-2}$ $\displaystyle\leq$ $\displaystyle
x(r+1)2^{2(r+1)^{2}}$ $\displaystyle=$ $\displaystyle x(r+1)4^{(r+1)^{2}},$

which completes the claim. Then by our assumption on the pairing function,

$\displaystyle\text{Number of times }\eta(x)\text{ gets injured}=$
$\displaystyle\sum_{\rho\in\texttt{quota}(x)}\texttt{InjPow}_{\eta}(x,\rho)$
$\displaystyle\leq$ $\displaystyle\texttt{InjPow}_{\eta}(x,\rho),$
$\displaystyle\text{where }\rho\text{ has edge layer }x$ $\displaystyle\leq$
$\displaystyle x(x+1)4^{(x+1)^{2}}$ $\displaystyle\leq$
$\displaystyle(x+1)^{2}4^{(x+1)^{2}}.$

∎

##  3 Low, Totally $\alpha$-c.a.

Given “reasonable” ordinal $\alpha$, we build a low c.e. set $A$ that “changes
its mind $\alpha$-times”. Before constructing $A$, we formalize in the
following Section 3.1 what it means for $A$ to make $\alpha$-mind-changes, and
what it means for $\alpha$ to be reasonable.

###  3.1 Totally $\alpha$-c.a.

By Shoenfield’s Limit Lemma, every $\Delta^{0}_{2}$ set $A$ has a _computable-
approximation_ $\langle a_{s}(x)\rangle_{s}$, which is a uniformly computable
sequence such that for all $x\in\omega$,

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

To measure how fickle $A$ is, we want to keep track of how often $a_{-}(x)$
changes its mind. This idea was formalized as follows:

######  Definition 3.1 ([2] II.D1.1).

Let $\mathcal{R}=(R,<_{\mathcal{R}})$ be a computable well-ordering (both $R$
and $<_{\mathcal{R}}$ are computable), and $A$ be a $\Delta^{0}_{2}$ function.
Then an $\mathcal{R}$-computable-approximation of $A$ is a computable-
approximation $\langle a_{s}\rangle$ of $A$, together with a uniformly
computable sequence $\langle m_{s}\rangle_{s}$ of functions
$m_{-}(x):\omega\to R$ such that for all $x$ and $s$:

  * •

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

  * •

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

The sequence $\langle m_{s}\rangle$ is called the _mind change function of
$A$_.

It is tempting to define $A$ as changing its mind $\alpha$-times if $A$ has an
$\mathcal{R}$-computable-approximation of _order type_
$\operatorname{otp}(\mathcal{R})=\alpha$. But we want a notion of mind changes
that gives a non-trivial hierarchy, and such that higher levels of the
hierarchy have stronger lattice-embedding abilities. If $\mathcal{R}$ was only
required to be computable, then the hierarchy would collapse to the
$\omega$-level (Ershov): Given $A\in\Delta^{0}_{2}$ and letting
$\langle\langle a_{s}(x)\rangle_{s}\rangle_{x}$ be a computable approximation
of $A$, the computable well ordering $\mathcal{R}$ with $R=\\{\langle
x,s\rangle:\;a_{s}(x)\neq a_{s+1}(x)\\}$ and ordering $\langle
x,s\rangle<_{\mathcal{R}}\langle
x^{\prime},s^{\prime}\rangle\iff[x<x^{\prime}\text{ or
}(x=x^{\prime}\;\&\;s>s^{\prime})]$ has order type $\omega$, witnessing $A$
being at the $\omega$ level.

Even if we require $\mathcal{R}$ to satisfy the additional properties of
having its set of limit points $L(\mathcal{R})$ and its successor function
$S_{\mathcal{R}}:R\to R$ to also be computable, the hierarchy would still
collapse, though to the $\omega^{2}$-level (Ershov): Let $\mathcal{R}$ be the
computable well ordering with $\operatorname{otp}(\mathcal{R})=\omega$ defined
above. Then $\omega\cdot\mathcal{R}$ will be be a computable well ordering of
order type $\omega^{2}$. Also, $L(\omega\cdot\mathcal{R})$ will be a
computable set, because $\langle n,z\rangle\in L(\omega\cdot\mathcal{R})$ iff
$n\neq 0$ and $z$ is the $\mathcal{R}$-smallest element. Finally,
$S_{\omega\cdot\mathcal{R}}(\langle n,z\rangle)$ is a computable function,
because $S_{\omega\cdot\mathcal{R}}(\langle n,z\rangle)=\langle n+1,z\rangle$.
Thus $\omega\cdot\mathcal{R}$ witnesses $A$ being at the $\omega^{2}$ level.
Therefore a meaningful definition of mind changes calls for $\mathcal{R}$ to
satisfy further properties.

In lattice embeddability constructions, we often need the notion mind changes
to be independent from the $\mathcal{R}$ used. Say we want to diagonalize out
of the sets that change their minds less than $\alpha$-times. To effectively
enumerate these less fickle sets, we fix some $\mathcal{R}$ with
$\operatorname{otp}(\mathcal{R})=\alpha$ and enumerate all sets with an
$\mathcal{R}$-computable-approximation. However, there might be some $A$ that
also changes its mind less than $\alpha$-times, but via a different computable
well-ordering $\mathcal{R}^{\prime}$. Then our enumeration will not include
$A$ if there is no procedure to get to $\mathcal{R}$ from
$\mathcal{R}^{\prime}$ effectively. Therefore $\mathcal{R}$ must be such that
if $A$ changes its mind $\alpha$-times via $\mathcal{R}$ and also
$\alpha^{\prime}$-times via $\mathcal{R}^{\prime}$ and
$\alpha>\alpha^{\prime}$, then $A$ changes its mind $\alpha^{\prime}$-times
via $\mathcal{R}\restriction\alpha^{\prime}$.

Another crucial property for $\mathcal{R}$ to have is sufficient
informativeness. Given $r\in R$, we want to have a rough idea of how large the
ordinal with notation $r$ is. For example, say we want to use a sufficiently
fickle $A$ to build another set satisfying certain requirements. At each stage
of the construction, we check the number of mind changes that $A$ has left,
and decide a strategy based on that number $r\in R$. If $A$ has more than
$\omega^{\omega}$-mind changes left for example, we might play a different
strategy than if $A$ has only $\omega$ mind changes left. Therefore
$\mathcal{R}$ needs to contain enough information to compare ordinal notations
meaningfully.

To these ends, it is enough for $\mathcal{R}$ to be _canonical_ :

######  Definition 3.2 ([2] II.D2.2).

Let $\mathcal{R}$ be a computable well-ordering with
$\operatorname{otp}(\mathcal{R})=\alpha$. Then
$\text{nf}_{\mathcal{R}}:\omega\rightarrow(\omega^{2})^{<\omega}$ denotes the
function that takes each ordinal below $\alpha$ to its Cantor-normal form,
i.e. $\forall z\in R$

$\operatorname{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}$

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

We are now ready to formalize mind change frequency of a set $A$ and of a c.e.
degree:

######  Definition 3.3 ([2] II.D2.9).

$A\in\Delta^{0}_{2}$ is $\alpha$-c.a. if $A$ has an $\mathcal{R}$-computable-
approximation for some canonical $\mathcal{R}$ with
$\operatorname{otp}(\mathcal{R})=\alpha$. Informally, if $A$ is $\alpha$-c.a.,
we say that set $A$ changes its mind $\alpha$-times.

######  Definition 3.4 ([2] III.D1, III.L1.1).

Degree $\bm{d}\in\Delta^{0}_{2}$ is totally $\alpha$-c.a. if every
$A\leq_{T}\bm{d}$ is $\alpha$-c.a.. Informally, we say that degree $\bm{d}$
changes its mind $\alpha$-times.

Note that when $A\in\Delta^{0}_{2}$ changes its mind $\alpha$-times, even when
$\alpha$ is infinite, $A(x)$ actually only changes its mind finitely often
from the definition of computable approximation (Definition 3.1), together the
fact that there is no infinite descending sequence of ordinals. Therefore when
we construct a set $A$ with $\geq\omega$ mind changes, the mind change
requirement will inflict only finite injury.

By requiring that $\mathcal{R}$ be canonical, the mind change hierarchy
obtained is $\operatorname{low}_{2}$ ([2] III.T1.2), and gives meaningful
lattice embeddability results - the degrees above the $\omega$-level are
exactly those below which one can embed the critical-triple [3], and the
degrees above the $\omega^{\omega}$-level are exactly those below which one
can embed $M_{3}$ [2]. Also, if we focus on the levels below

$\epsilon_{0}:=\sup\\{\omega,\omega^{\omega},\omega^{\omega^{\omega}},\ldots\\},$

then a set’s fickleness will not depend on the $\mathcal{R}$ picked ([2]
II.P2.3, P2.8). Looking at these lower level degrees is enough for now because
all the embeddability results we have discussed lie below $\epsilon_{0}$.
Finally, as desired, the mind change hierarchy is non-trivial:

######  Fact 3.5 ([2] III.L2.1).

Let $\alpha\leq\epsilon_{0}$, and let $A$ be a totally $\alpha$-c.a.. If
$\alpha$ is a power of $\omega$, then there exists a c.e. set $A$ that is
totally $\alpha$-c.a. but not totally $\beta$-c.a. for any $\beta<\alpha$.

The converse of the above fact is also true:

######  Fact 3.6 ([2] III.L2.2).

Let $\alpha\leq\epsilon_{0}$, and let $A$ be a totally $\alpha$-c.a.. If
$\alpha$ is not a power of $\omega$, then $A$ is totally $\beta$-c.a. for some
$\beta<\alpha$.

The key ingredient that makes Fact 3.5 hold is:

######  Fact 3.7.

Let $\alpha<\epsilon_{0}$. Then $\alpha$ is closed under ordinal addition if
and only if $\alpha$ is a power of $\omega$.

To see how $\alpha$ being closed under addition is crucial for constructing
sets $A$ at the $\alpha$ level, consider the requirements that $A$ will need
to satisfy. To avoid being totally $\beta$-c.a. for any $\beta<\alpha$, $A$
needs to compute some total $\Delta^{A}$ that diagonalizes out of all the
$\beta$-c.a. functions. This positive requirement calls for an uniform
enumeration of all $\beta$-c.a. functions, which we can get from the following
fact:

######  Fact 3.8 ([2] II.L2.6).

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

Now when diagonalizing $\Delta^{A}$ out of a $\beta$-c.a. function $f^{e}$,
$\beta$ elements 444The number of elements is finite, but the elements can
only be indexed canonically by a possibly infinite ordinal $\beta$. may be
enumerated into $A$. At the same time, for $A$ to be totally $\alpha$-c.a., if
$\Phi^{A}$ is total, then for all $x\in\omega$, $\Phi^{A}(x)$ cannot change
its mind more than $\alpha$-times. So $\Phi^{A}(x)$ must tolerate
$\beta$-injury from each of its higher priority positive requirements. There
are only finitely many such requirements, so the total injury on $\Phi^{A}(x)$
is a finite sum of ordinals $\beta<\alpha$. This sum can be bounded below
$\alpha$ if and only if $\alpha$ is closed under ordinal addition. Therefore
Fact 3.7 is crucial for a successful construction of a properly totally
$\alpha$-c.a. set $A$.

This construction outline was used by Downey and Greenberg to build a properly
$\alpha$-level set $A$ when $\alpha$ is a power of $\omega$ ([2] III.L2.2).
The authors used a tree in their construction. Because lowness generally
doesn’t mix on trees, it is not clear if the constructed set is low. In the
following Section 3.2, we use the same outline to construct a properly totally
$\alpha$-c.a. set $A$, but we count injury more carefully to avoid using a
tree, thus ensuring the lowness of our set.

###  3.2 Low, Totally $\alpha$-c.a.

######  Theorem 3.9.

Let $\alpha\leq\epsilon_{0}$ be a power of $\omega$. Then there exists a c.e.
set $A$ that is totally $\alpha$-c.a. but not totally $\beta$-c.a. for any
$\beta<\alpha$. Furthermore, $A$ can be made to be low.

We use the standard finite injury construction and count injury carefully to
bound the number of mind changes of each $\Phi^{A}_{e}(e)[-]$ below $\alpha$.
Fix a uniformly computable series of functions $\langle\langle
f^{e}_{s}\rangle_{s}\rangle_{e}$ from Fact 3.8 that enumerates the
$\beta$-c.a. functions for all $\beta<\alpha$. Note that for every
$e,x\in\omega$, the limit $f^{e}(x):=\lim_{s}f^{e}_{s}(x)$ exists. Also, fix a
computable bounding-function $g(e):\omega\to\alpha$ from Fact 3.8 which tells
us that $f^{e}:=\lim_{s}f^{e}_{s}$ is $g(e)$-computably-approximable.

$Q$-module ($(\forall\beta<\alpha)\;[\neg\beta\text{-c.a.}]$): Build an
$A$-computable total function $\Delta^{A}$ that diagonalizes out of all the
$\beta$-c.a. functions by satisfying positive requirements $\forall
e\in\omega$:

$Q_{e}:(\exists x)\;[\Delta^{A}(x)\neq\lim_{s}f^{e}_{s}(x)].$

To meet a single $Q_{e}$, start by picking a follower $x$ for $Q_{e}$ and a
large use $u$ for $x$. _Diagonalize $\Delta^{A}$ out of $f^{e}$_ by declaring
$\Delta^{A\restriction u}(x)[s]=1-f^{e}_{s}(x)$. Wait for $f^{e}(x)$ to change
its mind. Then $Q_{e}$ will want to _act_ by enumerating $u$ into $A$, picking
a new use, and diagonalizing $\Delta^{A}$ out of $f^{e}$ with the new use.
$Q_{e}$ needs permission from negative requirements $N$ before acting. We
elaborate later on this permission. $Q_{e}$ will act if allowed, and will be
initialized otherwise. After acting, $Q_{e}$ will wait for $f^{e}(x)$ to
change its mind again. Then $Q_{e}$ will want to act again, and we repeat the
process of seeking permission from $N$-requirements. Whenever $Q_{e}$ wants to
act, regardless of whether $Q_{e}$ was allowed, all lower priority $Q>Q_{e}$
will be initialized.

$N$-module (Totally $\alpha$-c.a., Low): To make $A$ totally $\alpha$-c.a. and
low, we construct a partial computable mind change function
$\phi(e):\omega\to\alpha$ to satisfy negative requirements $\forall
e\in\omega$:

$N_{e}:(\exists^{\infty}s)\;[\Phi^{A}_{e}(e)[s]\downarrow]\implies\left[\phi(e)\downarrow\text{
and }\Phi^{A}_{e}(e)[-]\text{ changes mind }\leq\phi(e)\text{-times}\right].$

To see how $N_{e}$ makes $A$ totally $\alpha$-c.a., let $h(e,x)$ be a total
computable function such that for all strings $\sigma$ and $e,x\in\omega$,
$\Phi^{\sigma}_{e}(x)=\Phi^{\sigma}_{h(e,x)}(h(e,x))$. Then if
$\Phi^{A}_{e}(-)$ is total, $\phi(h(e,-)):\omega\to\alpha$ will be a total
computable bounding function that witnesses $\Phi^{A}$ being $\alpha$-c.a..
Therefore the $N_{e}$ requirements above are enough to make $A$ totally
$\alpha$-c.a..

To meet a single $N_{e}$, wait for $\Phi^{A}_{e}(e)$ to converge for the first
time. We say that $N_{e}$ is _active_. An active $N_{e}$ remains active
forever, even if $\Phi^{A}_{e}(e)$ diverges later. Upon becoming active,
$N_{e}$ decides once and for all which $Q$-requirements are allowed to injure
$\Phi^{A}_{e}(e)$, and for each such $Q$, how much injury to tolerate. If
$N_{e}$ tolerates $k$ initializations from $Q$, then the injury from $Q$ will
be bounded by $g(Q)\cdot(k+1)$. Summing injury from all $Q$ gives a bound
$\phi(e)$ of total injury on $N_{e}$.

For bookkeeping, at each stage $s$ after becoming active, $N_{e}$ maintains a
list $\texttt{Qlist}(e,s)$ of $Q$-requirements allowed to injure $N_{e}$.
Requirements may be removed from the list, but new requirements are never
allowed to enter. $N_{e}$ allows $Q$ to act if $Q$ lies in $N_{e}$’s list.

Overall Strategy: When $Q$ acts, $Q$ will enumerate its use into $A$,
potentially injuring some active $N$. On the other hand, when $N$ first
becomes active, say at stage $s$, $N$ must decide which $Q$ to put into its
list, and then decide how many initializations to tolerate from each such $Q$.
How can $N$ make these decisions? The overarching strategy is for $N$ to
tolerate only injury from the highest priority positive requirement that still
wants to act. Let that positive requirement be $Q$. This $Q$ is “almost
stabilized” since all $Q^{\prime}<Q$ are presumably satisfied even though $Q$
is not. We argue that the number of times that $Q$ will be initialized is
bounded by $k$, the number of active negative requirements at stage $s$:

If $N^{\prime}$ is active at stage $s$, then $N^{\prime}$ cannot initialize
$Q$ more than once, because after the first initialization, all $Q^{\prime}>Q$
will be initialized and never allowed to injure $N$ again. On the other hand,
if $N^{\prime\prime}$ is inactive at stage $s$, then $N^{\prime\prime}$ can
never initialize $Q$, because when $N^{\prime\prime}$ becomes active later,
$N^{\prime\prime}$ can declare to tolerate at least $k$-initializations from
$Q$, which is generous enough by earlier argument.

Summarizing, because all $Q^{\prime}>Q$ are initialized whenever $Q$ acts, $Q$
cannot be initialized more than $k$ times. The overall strategy is for $N$ to
tolerate only injury from $Q$. So when $N$ first becomes active, $N$ will put
in its list all the $Q$ that have a follower, and allow $k$-initializations
from each such $Q$. If some $Q$ in the list is found to be initialized more
than $k$-times, or has a higher priority $Q^{\prime}<Q$ that wants to act,
then $Q$ could not have been the amost stabilized requirement, and will never
be allowed to injure $N$ again. Then by construction, $N$’s injury is bounded,
and from above argument, $Q$’s injury is also bounded, so the construction
succeeds.

Formally, let the current stage be $s$. Requirement $Q$ is the _almost
stabilized positive requirement of stage $s$_ if $Q$ is the highest priority
positive requirement that still wants to act at or after stage $s$. The $N$
and $Q$ strategies are as follows:

Initialize $N_{e}$: Declare $N_{e}$ inactive.

$N_{e}$-strategy: If $N_{e}$ is not yet active and
$\Phi^{A}_{e}(e)[s]\uparrow$, then $N_{e}$ remains inactive and we do nothing.
But if $N_{e}$ is active or $\Phi^{A}_{e}(e)[s]\downarrow$, declare $N_{e}$
active forever. Then if this is the first stage that $N_{e}$ is active, let

$k=|\\{N:N\text{ is active at stage }s\\}|,$

and set $\phi(e)$ and $\texttt{Qlist}(e,s)$:

$\displaystyle\texttt{Qlist}(e,s)$ $\displaystyle=\\{Q:Q\text{ has a follower
at stage }s\\},$ (7) $\displaystyle\phi(e)$
$\displaystyle=\sum_{Q\in\texttt{Qlist}(e,s)}\;g(Q)\cdot(k+1).$ (8)

Note that $\phi(e)<\alpha$ from Fact 3.7. In the above equations, if
$Q\in\texttt{Qlist}(e,s)$, we say that _$Q$ lies in the quota of $N_{e}$ at
stage $s$_, and we also say that _the quota for $Q$ from $N_{e}$ is $k$_. If
at a later stage $s^{\prime}>s$, $Q\in\texttt{Qlist}(e,s)$ is initialized more
than $k$-times between stages $s$ and $s^{\prime}$, we say that _$Q$ has
exhausted its quota from $N_{e}$ at stage $s^{\prime}$_.

Now consider the case when $N_{e}$ was active before stage $s$, and let
$s_{0}<s$ be the first stage that $N_{e}$ became active. Then $N_{e}$ will
maintain its list by removing all $Q$ that cannot have been the almost
stabilized positive requirement of stage $s_{0}$. These are the $Q$
requirements that were found to have a higher priority $Q^{\prime}<Q$ wanting
to act after stage $s_{0}$, or that have exhausted their quota from $N_{e}$:

$\displaystyle\texttt{Qlist}(e,s)$ $\displaystyle=\texttt{Qlist}(e,s-1)$
$\displaystyle-\\{Q:\;(\exists Q^{\prime}<Q)\;[Q^{\prime}\text{ wanted to act
at some stage between }s_{0}\text{ and }s]\\}$ $\displaystyle-\\{Q:Q\text{
exhausted its quota from }N_{e}\text{ at stage }s\\}.$

Finally if $N_{e}$ is active, $Q$-requirements may ask $N_{e}$ for permission
to act. _$N_{e}$ allows $Q$ to act at stage $s$_ if $Q\in\texttt{Qlist}(e,s)$,
or if $\Phi^{A}_{e}(e)[s]\uparrow$, or if the use of $Q$ exceeds
$\operatorname{use}(\Phi^{A}_{e}(e)[s])$.

Initialize $Q_{e}$: Destroy the follower and use assigned to $Q_{e}$, if any.
So the next time $Q_{e}$ is accessed, $Q_{e}$ is considered to have neither
follower nor use.

$Q_{e}$-strategy: If $Q_{e}$ does not have a follower, assign a new one that
is the smallest number not yet in the domain of $\Delta^{A}$, and assign the
follower a new large use. Let $x$ denote the current follower of $Q_{e}$ and
let $u$ denote the current use of $x$. $Q_{e}$ will want to _diagonalize
$\Delta^{A}$ out of $f^{e}$_ by declaring $\Delta^{A\restriction
u}(x)[s]=1-f^{e}_{s}(x)$. Perform the diagonalization if
$\Delta^{A\restriction u}(x)[s]$ was not already declared to be something else
earlier, which might occur when $f^{e}(x)$ changed its mind since the most
recent declaration of $\Delta^{A}(x)$.

Should contradiction occur, _$Q_{e}$ will want to act_ by enumerating $u$ into
$A$, picking a new use $u^{\prime}>u$, then diagonalizing $\Delta^{A}$ out of
$f^{e}$ with the new use. _$Q_{e}$ is allowed to act_ if every active $N$,
even those $N>Q_{e}$, allows $Q_{e}$ to act. Refer to the $N$-strategy for
when $N$ allows $Q_{e}$ to act. $Q_{e}$ will act if allowed and will be
initialized otherwise. If initialized, assign $Q_{e}$ a new follower and use
before diagonalizing $\Delta^{A}$ out of $f^{e}$. As long as $Q_{e}$ wanted to
act, regardless of whether $Q_{e}$ was allowed, initialize all $Q>Q_{e}$.

Play the $N$ and $Q$ strategies in the “usual” finite injury construction:

At stage $s$, play the $N_{0}$ to $N_{s}$ strategies described above to
maintain the lists of the active and newly active negative requirements. Then
from step $e=0$ to $s$: Play the $Q_{e}$-strategy described above. If $Q_{e}$
had a follower and did not want to act, go to the next step. But if $Q_{e}$
did not have a follower or wanted to act, skip remaining steps and go directly
to next stage.

We now verify that the construction works.

######  Lemma 3.10.

For all $e\in\omega$, $N_{e}$ is satisfied. Therefore $A$ is totally
$\alpha$-c.a. and low.

###### Proof.

Follows from construction. ∎

######  Lemma 3.11.

For all $e\in\omega$, $Q_{e}$ eventually stops being initialized and stops
wanting to act. Therefore $A$ is not totally $\beta$-c.a. for all
$\beta<\alpha$.

###### Proof.

It is enough to show that every $Q_{e}$ eventually stops being initialized,
because if $Q_{e}$ wants to act and is denied permission, then our
construction will initialize $Q_{e}$. We prove by induction on $e\in\omega$.

Wait for $Q_{e}$ to be almost stabilized. This eventually occurs from
induction hypothesis. If $Q_{e}$ is never initialized again, we are done. So
assume $Q_{e}$ is initialized again. Then from construction, $Q_{e}$ will be
assigned a new follower at the next stage, say at stage $s_{0}$. Let
$\mathcal{N}$ be the set of $N$-requirements that are active at stage $s_{0}$.

Let $N\in\mathcal{N}$. We first show that $N$ cannot initialize $Q_{e}$ more
than once: If $N$ never injures $Q_{e}$ again, we are done. So wait for $N$ to
injure $Q_{e}$ again. Then the new use picked by $Q_{e}$ will exceed the use
of $N$, meaning that if $N$ is injured again, that next injury cannot have
been inflicted by $Q_{e}$. Yet the next injury also cannot be inflicted by any
$Q>Q_{e}$, because all $Q>Q_{e}$ were removed from $\texttt{Qlist}(N,s_{0}+1)$
when $Q_{e}$ got initialized just before stage $s_{0}$. Finally, the next
injury also cannot be inflicted by any $Q^{\prime}<Q_{e}$ because no
$Q^{\prime}<Q_{e}$ ever acts again. Therefore computation $N$ is finalized,
and the use of $Q_{e}$ will always exceed the final use of $N$, implying that
$N$ will never initialize $Q_{e}$ again.

Next, we show that if $N^{\prime}\not\in\mathcal{N}$, then $N^{\prime}$ can
never initialize $Q_{e}$: Assume for contradiction that there exists a first
$N^{\prime}\not\in\mathcal{N}$ that initializes $Q_{e}$ after stage $s_{0}$.
Note that after stage $s_{0}$, $Q_{e}$ will always have a follower since
$Q$-requirements only lose their followers when a higher priority positive
requirement gets initialized. Therefore when $N^{\prime}$ first becomes
active, say at stage $s_{1}>s_{0}$, $N^{\prime}$ will put $Q_{e}$ into its
list $\texttt{Qlist}(N^{\prime},s_{1})$, and allow $Q_{e}$ to be initalized
more than $|\mathcal{N}|$-times. Let $s_{2}\geq s_{1}$ be the first stage that
$N^{\prime}$ initializes $Q_{e}$. For $N^{\prime}$ to be able to initialize
$Q_{e}$, $N^{\prime}$ must have removed $Q_{e}$ from its list at some stage
between $s_{1}$ and $s_{2}$. Since no $Q<Q_{e}$ acts again, $Q_{e}$ can only
have been removed because $Q_{e}$ was initialized more than
$|\mathcal{N}|$-times since stage $s_{1}$. Yet from earlier argument, $Q_{e}$
can only be initialized at most $|\mathcal{N}|$-times by all the elements in
$\mathcal{N}$, meaning that the $|\mathcal{N}+1|$-th initialization must have
been inflicted by some $N^{\prime\prime}\not\in\mathcal{N}$,
$N^{\prime\prime}\neq N^{\prime}$, contradicting the choice of $N^{\prime}$.

Therefore upon becoming almost stabilized, $Q_{e}$ cannot be initialized more
than $|\mathcal{N}|$-times. ∎

##  4 Nonlow, Totally $\alpha$-c.a.

In this section, given $\alpha$ which is a power of $\omega$, we construct a
c.e. set that is nonlow and totally $\alpha$-c.a.. We use the construction
framework of the nonlow, array computable set $A$ in Theorem 2.9. By
integrating the $Q$-module of Theorem 3.9, we increase the mind changes of $A$
to the desired $\alpha$.

Array computable sets are totally $\omega$-c.a., which by Facts 3.5 and 3.6,
imply that they sit at the bottom of the mind change hierarchy. Furthermore,
by the following definition and fact, not only do array computable sets change
their minds less than $\omega$ times, they do so uniformly:

######  Definition 4.1 ([2] III.D3.3).

Let $A$ have c.e. degree, and let $\alpha<\epsilon_{0}$. Then $A$ is
_uniformly totally $\alpha$-c.a._ if there exists a computable mind change
function $m(x):\omega\to\alpha$ such that for every $B\leq_{T}A$, $B$ has an
$\alpha$-c.a. approximation $\langle f_{s}(x),o_{s}(x)\rangle$ where
$o_{0}(x)\leq m(x)$ for all $x\in\omega$.

######  Fact 4.2 ([2] III.L3.4).

Let $A$ have c.e. degree. Then $A$ is _array-computable_ iff $A$ is uniformly
totally $\omega$-c.a..

Since the set $A$ constructed in Theorem 2.9 is nonlow and uniformly totally
$\omega$-c.a., roughly speaking, by adding $\alpha$ more mind changes to $A$,
$A$’s fickleness will increase to $\alpha$.

###  4.1 Nonlow, Totally $\alpha$-c.a.

######  Theorem 4.3.

Let $\alpha\leq\epsilon_{0}$ be a power of $\omega$. Then there exists a c.e.
set $A$ that is totally $\alpha$-c.a. but not totally $\beta$-c.a. for any
$\beta<\alpha$. Furthermore, $A$ can be made to be nonlow.

We use the tree framework of Theorem 2.1. To make $A$ nonlow, we use the
$P$-module from Theorem 2.1, and to make $A$ not $\beta$-c.a. for any
$\beta<\alpha$, we use the $Q$-module from Theorem 3.9, but played on a tree.
Finally, to make $A$ totally $\alpha$-c.a., we combine the $N$-modules from
Theorems 2.1 and 3.9:

$P$-module (Nonlow): Exactly the same as the $P$-module of Theorem 2.1.

$Q$-module ($(\forall\beta<\alpha)\;[\neg\beta\text{-c.a.}]$): Same as
$Q$-module of Theorem 3.9, but played on a tree. We elaborate on the subtle
differences from the finite injury construction later.

Note that even though $P$ and $Q$ both want to enumerate elements into $A$ to
diagonalize out of the limit of functions, their module designs are very
different for two reasons. First, the function $\Delta^{A}$ constructed by $Q$
needs to be total, but the function $\Gamma^{A}$ constructed by $P$ can be
partial. Therefore when picking a new use, $P$ can wait for negative
requirements $N$ to stabilize sufficiently first, but $Q$ cannot because $Q$
may never know when and if stability will occur. The moment $Q$ has a follower
$x$, $Q$ must immediately declare that $\Delta^{A\restriction u}(x)$ converges
with some use $u$, otherwise $\Delta^{A}(x)$ may diverge at the end of the
construction. Because of $Q$’s impatience, $Q$ will injure $N$ requirements
more often than $P$ does since $Q$ may pick uses that are too small to avoid
inflicting future injuries.

But $Q$ redeems itself by informing $N$ requirements of the injury
$g(Q)<\alpha$ to expect. $P$ on the other hand, cannot bound its injury
computably. $Q$’s lack of pacing but increased informativeness explains the
stark differences between the $P$ and $Q$ strategies introduced earlier.

$N$-module (Totally $\alpha$-c.a.): For all $e\in\omega$, construct mind
change function $\phi_{e}(-):\omega\to\alpha$ satisfying:

$N_{e}:\Phi^{A}_{e}\;\text{total}\implies\left[\phi_{e}(-)\text{ total
computable and }(\forall x)\;\left[\Phi^{A}_{e}(x)[-]\text{ changes mind
}\leq\phi_{e}(x)\text{-times}\right]\right].$

For every $x$, $N(x)$ works to protect computation $\Phi^{A}_{e}\restriction
x$. Yet $N(x)$ must also offer $P$ and $Q$ requirements sufficient
opportunities to act. Following the argument of the $N$ module in Theorem 2.1,
$N(x)$ allows $P$ requirements to act via the quota system. Also, following
the argument of the $N$ module in Theorem 3.9 and Eq. (7), $N(x)$ allows $Q$
requirements to act via the Qlist system, but modified to fit a tree
construction. We elaborate on the modifications later.

Note that unlike the $N$ requirements of Theorem 3.9, the series of mind
change functions $\phi_{e}$ will not be uniformly computable because we are
not trying to satisfy lowness. However for a fixed $e$, if $\Phi^{A}_{e}$ is
total, then $\phi_{e}(-)$ must be total-computable.

Tree construction: Order the requirements
$N_{0},P_{0},Q_{0},N_{1},P_{1},Q_{1},\ldots$ so that a node $\delta$ in the
tree $\Lambda$ works for $N_{e}$ if $|\delta|=3e$, works for $P_{e}$ if
$|\delta|=3e+1$, and works for $Q_{e}$ if $|\delta|=3e+2$. Given
$\delta\in\Lambda$, if $\delta$ works for $N_{e}$ we write $\delta=\eta_{e}$,
and if $\delta$ works for $P_{e}$ we write $\delta=\rho_{e}$, and if $\delta$
works for $Q_{e}$ we write $\delta=\xi_{e}$. $\eta$ and $\rho$ nodes have two
possible outcomes $\\{\infty<\texttt{fin}\\}$, while $\xi$ nodes, being of
finite injury, have only one possible outcome.

Let the current stage be $s$. Given a node $\delta\in\Lambda$, depending on
the type of requirement $\delta$ is working for, we initialize and design the
$\delta$-strategy as follows:

Initialize $\rho$: Destroy the follower and use assigned to $\rho$, if any. So
the next time $\rho$ is visited, $\rho$ is considered to have neither follower
nor use.

Outcome of $\rho$: Exactly the same as the $\rho$-outcome of Theorem 2.1.

$(\rho^{\frown}\texttt{fin})$-strategy: Exactly the same as the
$(\rho^{\frown}\texttt{fin})$-strategy of Theorem 2.1.

$(\rho^{\frown}\infty)$-strategy: Exactly the same as the
$(\rho^{\frown}\infty)$-strategy of Theorem 2.1.

Initialize $\xi$: Destroy the follower and use assigned to $\xi$, if any. So
the next time $\xi$ is visited, $\xi$ is considered to have neither follower
nor use.

Outcome of $\xi$: $\xi$ only has one outcome since it inflicts only finite
injury.

$\xi$-strategy: Same as the $Q$-strategy in Theorem 3.9, except that if $\xi$
wants to act, $\xi$ only needs permission from all initial segments $\eta$
such that $\eta^{\frown}\infty\preceq\xi$. Permission is no longer needed from
lower priority $\eta\succeq\xi$ because unlike the construction in Theorem
3.9, we are not trying to make the mind change function $\phi_{e}(-)$ to be
uniformly computable.

If $\xi$ wants to act, initialize all $\xi^{\prime}\succ\xi$ and
$\delta>_{L}\xi$. If $\xi$ wants to act but was not allowed, initialize $\xi$,
then assign $\xi$ new follower and large use, before diagonalizing
$\Delta^{A}$ out of $f^{\xi}$. Given $k\in\omega$, we let $\xi(k)$ denote the
sub-requirement of $\xi$ that works to let $\xi$ act $k$ times since the
beginning of the construction.

Initialize $\eta$: To keep track of the injury from $\rho$ nodes, for all
$x\in\omega$, $\eta(x)$ is fixed a quota $\texttt{quota}(x)$, which is
identical to Eq. (2.2) of Theorem 2.1. Also, to keep track of injury from
$\xi$ nodes, for each $x,s^{\prime}\in\omega$, $\eta$ maintains a list
$\texttt{Qlist}(\eta,x,s^{\prime})$ of $\xi$ nodes allowed to injure $\eta(x)$
at stage $s^{\prime}$. Initialize $\texttt{Qlist}(\eta,x,s)$ to undefined for
all $x\in\omega$.

Outcome of $\eta$: Exactly the same as the $\eta$-outcome of Theorem 2.1 –
$\eta$ has outcome $\infty$ iff $s$ is $\eta$-expansionary. Note that the
definition of $\eta$-correctness considers only the $\rho$ nodes that are
initial segments of $\eta$. In particular, the correctness of $\eta(x)$ will
not be affected by the use of some $\xi\prec\eta$ being smaller than
$\operatorname{use}(\eta(x)[s])$, because $\xi$ nodes are finitary nodes, and
in tree constructions, when accessing $\delta\succeq\xi$, we always assume
that $\xi$ never acts again.

$(\eta^{\frown}\texttt{fin})$-strategy: Do nothing.

$(\eta^{\frown}\infty)$-strategy: Some $\rho\succeq\eta^{\frown}\infty$ might
ask $\eta$ for permission to act via picking use or via enumeration. $\eta$’s
strategy for granting permission is exactly the same as the
$(\eta^{\frown}\infty)$-strategy of Theorem 2.1. Note again that the $\xi$
nodes are irrelevant when determining $\rho$-correctness of $\eta(x)$
computations.

Also, some $\xi\succeq\eta^{\frown}\infty$ may ask for permission to act.
$\eta$’s strategy for granting permission is similar to the $N$-strategy of
Theorem 3.9, but modified for a tree construction. The main idea is still for
$\eta$ to tolerate only actions from the “almost stabilized” $\xi$ node.
Formally, the _the almost stabilized node of stage $s$_ is the unique node
$\xi$ such that $\xi\prec\delta_{\omega}$, $\xi$ is the highest priority node
that still wants to act at or after stage $s$, and such that no
$\delta\prec\xi$ is initialized again after stage $s$. Like before, we can
computably bound the number of initializations from the almost stabilized
$\xi$. However this bound is more difficult to calculate because of the tree
construction, so we only sketch the idea here, and flesh out the details later
in Main Lemma 2.4:

Let $\eta^{\prime\frown}\infty\preceq\xi$, $x<l_{s}(\eta^{\prime})$, and
consider the number of times that $\eta^{\prime}(x)$ will initialize the
almost stabilized $\xi$. Wait for $\xi$ to be initialized again. Then all
$\xi^{\prime}\succ\xi$ and $\xi^{\prime}>_{L}\xi$ will be initialized and
never allowed to injure $\eta^{\prime}(x)$ again. Then by near stability of
$\xi$, the only positive nodes that can injure $\eta^{\prime}(x)$ are $\xi$
itself and those $\rho\in\texttt{quota}(x)$. So after $\xi$ exhausts its quota
from $\eta^{\prime}(x)$, $\eta^{\prime}(x)$ will behave like in the proof of
Theorem 2.9, where there are no $Q$ nodes to complicate the injury count of
$\eta^{\prime}(x)$. Thus the number of times that $\eta^{\prime}(x)$ gets
injured will be bounded by $(x+1)^{2}4^{(x+1)^{2}}$, as computed in Eq. (6),
implying that $\xi$ cannot be initialized by $\eta^{\prime}(x)$ more than
$(x+1)^{2}4^{(x+1)^{2}}$ times. Summing the initializations from
$\eta^{\prime}(x)$ for all $\eta^{\prime\frown}\infty\preceq\xi$ and all
$x<l_{s}(\eta^{\prime})$ gives a computable bound

$k^{\prime}(\xi,s):=\sum_{\begin{subarray}{c}\eta^{\prime\frown}\infty\preceq\xi,\\\
x<l_{s}(\eta^{\prime})\end{subarray}}(x+1)^{2}4^{(x+1)^{2}}$ (9)

of total initializations of $\xi$ after stage $s$.

Like in the finite injury construction, $\eta(x)$ maintains a list
$\texttt{Qlist}(\eta,x,s)$ of $\xi$ nodes that are potentially the almost
stabilized node of stage $s$, routinely removing nodes that are later found to
not have been the almost stabilized node. And for each $\xi$ in the list,
$\eta(x)$ will assume that $\xi$ is the almost stabilized node, and tolerate
injury from $\xi$ up to the $k^{\prime}$ bound computed earlier.

Formally, for every $x<l_{s}(\eta)$, we set or update
$\texttt{Qlist}(\eta,x,s)$ as follows: If the current stage $s$ is the first
$(\eta^{\frown}\infty)$-stage, or if there was a most recent
$(\eta^{\frown}\infty)$-stage $s_{0}<s$ but $\eta$ was initialized between
stage $s_{0}$ and $s$, or if $\texttt{Qlist}(\eta,x,s_{0})$ has not yet been
defined, set

$\displaystyle\texttt{Qlist}(\eta,x,s)$
$\displaystyle=\\{\xi\succeq\eta^{\frown}\infty:\xi\text{ has a follower at
stage }s\\}.$ (10)

Then following earlier argument, $\eta(x)$ will allow $k(\eta(x),s)$
initializations from each $\xi\in\texttt{Qlist}(\eta,x,s)$, where

$\displaystyle
k(\eta(x),s):=\max\left\\{k^{\prime}(\xi,s):\;\xi\in\texttt{Qlist}(\eta,x,s)\right\\}.$
(11)

For each $\xi\in\texttt{Qlist}(\eta,x,s)$, we say that _$\xi$ lies in the
quota of $\eta(x)$ at stage $s$_, and that _the quota for $\xi$ from $\eta(x)$
is $k(\eta(x),s)$_. If at a later stage $s^{\prime}>s$,
$\xi\in\texttt{Qlist}(\eta,x,s)$ is initialized more than $k(\eta(x),s)$-times
between stages $s$ and $s^{\prime}$, then we say that _$\xi$ has exhausted its
quota from $\eta(x)$ at stage $s^{\prime}$_.

Now if $\eta$ was not initialized between the most recent
$(\eta^{\frown}\infty)$-stage $s_{0}<s$ and the current stage $s$, and
$\texttt{Qlist}(\eta,x,s_{0})$ is already defined, then update $\eta(x)$’s
list by removing all the $\xi$ nodes that cannot have been the almost
stabilized node of stage $s_{0}$. These are the $\xi$ nodes that have either
exhausted their quota from $\eta(x)$, or have been initialized by some
positive node $\prec\xi$ or by some $\delta<_{L}\xi$:

$\displaystyle\texttt{Qlist}(\eta,x,s)$
$\displaystyle=\texttt{Qlist}(\eta,x,s_{0})$ (12)
$\displaystyle-\\{\xi:\;\xi\text{ exhausted its quota from }\eta(x)\text{ at
stage }s\\}$
$\displaystyle-\\{\xi:\;(\exists\xi^{\prime}\prec\xi)\;[\xi^{\prime}\text{
wanted to act at some stage between }s_{0}\text{ and }s]\\}$
$\displaystyle-\\{\xi:\;(\exists\rho\prec\xi)\;[\rho\text{ was initialized
between stages }s_{0}\text{ and }s]\\}$
$\displaystyle-\\{\xi:\;(\exists\delta<_{L}\xi)\;[\text{there is a
}\delta\text{-stage between }s_{0}\text{ and }s]\\}$

Finally, given $x<l_{s}(\eta)$ and $\xi\succeq\eta^{\frown}\infty$, we say
that _$\eta(x)$ allows $\xi$ to act at stage $s$_ if
$\xi\in\texttt{Qlist}(\eta,x,s)$, or if $\Phi^{A}_{\eta}(x)[s]\uparrow$, or if
$\xi$’s use exceeds the $\text{use}\left(\Phi^{A}_{\eta}(x)[s]\right)$. Then,
_$\eta$ allows $\xi$ to act at stage $s$_ if for all $x<l_{s}(\eta)$,
$\eta(x)$ allows $\xi$ to act at stage $s$.

Play the $\rho$, $\xi$, and $\eta$ strategies on a tree to construct the
nonlow, totally $\alpha$-c.a. set $A$:

Stage $s$: Let $\delta_{s,0}$ be the empty node. From step $e=0$ to $s$:
Determine the outcome $o$ of $\delta_{s,e}$. Set
$\delta_{s,e+1}=\delta_{s,e}^{\frown}o$, and initialize all nodes to the right
of $\delta_{s,e+1}$. If $\delta_{s,e}^{\frown}o=\rho^{\frown}\texttt{fin}$,
play the $(\rho^{\frown}\texttt{fin})$-strategy to diagonalize $\Gamma^{A}$
out of $\psi^{\rho}$. If $\delta_{s,e}^{\frown}o=\eta^{\frown}\infty$, play
the $(\eta^{\frown}\infty)$-strategy described above to set or to maintain
$\texttt{Qlist}(\eta,x,s)$.

At the end of step $s$, we will get a node
$\delta_{s}:=\delta_{s,s}\in\Lambda$ of length $s$. Some of the initial
segments belonging to positive nodes may want to act. Let

$\displaystyle\Theta$
$\displaystyle=\\{\rho\preceq\delta_{s}:\;\rho^{\frown}\infty\preceq\delta_{s},\text{
and }\rho\text{ wants to pick use at stage }s\text{ and is allowed}\\}$
$\displaystyle\cup\\{\rho\preceq\delta_{s}:\;\rho^{\frown}\infty\preceq\delta_{s},\text{
and }\rho\text{ wants to enumerate use at stage }s\\}$
$\displaystyle\cup\\{\xi\preceq\delta_{s}:\;\xi\text{ wants to act at stage
}s\\}.$

If $\Theta$ is empty, go to the next stage. Otherwise, select one
$\delta\in\Theta$. This $\delta$ will be called _the selected node at stage
$s$_, and is selected as:

$\delta=\underset{\delta^{\prime}\in\Theta}{\mathrm{argmin}}\;\\{\langle\delta^{\prime},k\rangle:\;\delta^{\prime}\text{
has been selected }k\text{-times before stage }s\\}.$

If $\delta=\xi$, play the $\xi$-strategy described above. If $\delta=\rho$,
play the $(\rho^{\frown}\infty)$-strategy described above. Go to next stage.

######  Lemma 4.4.

$\delta_{\infty}\in[\Lambda]$.

###### Proof.

Same as proof of Lemma 2.2. ∎

######  Main Lemma 2.

Given $n\in\omega$, let $\delta=\delta_{\omega}\restriction n\in\Lambda$.

  1. 1.

If $\delta=\rho$ then $\rho$ eventually stops being initialized. Thus $\rho$
has a final follower $y_{\rho}$.

  2. 2.

If $\delta=\rho$ and $\rho^{\frown}\texttt{fin}\prec\delta_{\omega}$, then if
$\lim_{s}\psi^{\rho}_{s}(y_{\rho})$ exists the limit will not equal
$\chi_{\Gamma^{A}}(y_{\rho})$.

  3. 3.

If $\delta=\rho$ and $\rho^{\frown}\infty\prec\delta_{\omega}$, then $\rho$
will act infinitely often. Thus $\lim_{s}\psi^{\rho}_{s}(y_{\rho})$ does not
exist.

  4. 4.

If $\delta=\xi$ then $\xi$ eventually stops being initialized. Thus $\xi$ has
a final follower $z_{\xi}$.

  5. 5.

If $\delta=\xi$ then $\xi$ eventually stops wanting to act. Thus
$\lim_{s}f^{\xi}(z_{\xi})\neq\Delta^{A}(z_{\xi})$.

  6. 6.

If $\delta=\eta$ then $\eta$ eventually stops being initialized.

  7. 7.

If $\delta=\eta$ and $\eta^{\frown}\texttt{fin}\prec\delta_{\omega}$, then
$\Phi^{A}_{\eta}$ is not total.

  8. 8.

If $\delta=\eta$ and $\eta^{\frown}\infty\prec\delta_{\omega}$, then
$\Phi^{A}_{\eta}$ is total, and there is computable function
$\phi_{\eta}(-):\omega\to\alpha$ such that for all $x$,
$\Phi^{A}_{\eta}(x)[s]$ changes its mind less than $\phi_{\eta}(x)$ times
during the $\eta$-stages.

We prove Main Lemma 2 after this immediate corollary:

######  Corollary 4.5.

$A$ is nonlow and properly totally $\alpha$-c.a..

###### Proof.

Let $e\in\omega$ be arbitrary. By the same argument as Corollary 2.3, $P_{e}$
is satisfied. From Main Lemma 2.4 and 2.5, $Q_{e}$ is satisfied. Finally, from
Lemmas 4.4, Main Lemma 2.7 and 2.8, $N_{e}$ is satisfied. ∎

We prove the 8 claims of Main Lemma 2 by simultaneous induction on $n$. Like
in the verification of Main Lemma 1, in each claim for $\delta\in\Lambda$,
always assume that we are working in $\delta$-stages after higher priority
requirements or sub-requirements have stabilized. These stages exist from
induction hypothesis. Refer to the proof of Main Lemma 1 for what it means for
$\rho$, $\eta$, or $\eta(x)$ requirements to have stabilized at stage $s$. As
for $\xi$ nodes, _$\xi$ has stabilized at stage $s$_ if $\xi$ never wants to
act again at or after stage $s$. If $\delta=\rho$ or $\delta=\xi$, then given
$k\in\omega$, sub-requirement _$\delta(k)$ has stabilized at stage $s$_ if for
all $\langle\delta^{\prime},k^{\prime}\rangle<\langle\delta,k\rangle$, if
$\delta^{\prime}$ is ever selected $k^{\prime}$ times or less since the
beginning of the construction, then these selections have already been made by
stage $s$.

######  Claim (Main Lemma 2.1).

If $\rho\prec\delta_{\omega}$, then $\rho$ eventually stops being initialized.

###### Proof.

Same as the proof for Main Lemma 1.1. $\xi$ nodes do not affect the argument.
∎

######  Claim (Main Lemma 2.2).

If $\rho^{\frown}\texttt{fin}\prec\delta_{\omega}$, then if
$\lim_{s}\psi^{\rho}_{s}(y_{\rho})$ exists the limit will not equal
$\chi_{\Gamma^{A}}(y_{\rho})$.

###### Proof.

Same as the proof for Main Lemma 1.2. $\xi$ nodes do not affect the argument.
∎

######  Claim (Main Lemma 2.3).

If $\rho^{\frown}\infty\prec\delta_{\omega}$, then $\rho$ will act infinitely
often.

###### Proof.

Same as the proof for Main Lemma 1.3. $\xi$ nodes do not affect the argument.
∎

######  Claim (Main Lemma 2.4).

If $\xi\prec\delta_{\omega}$, then $\xi$ eventually stops being initialized.

###### Proof.

Wait for $\xi$ to be the almost stabilized node, i.e. wait for all
$\delta\prec\xi$ to stabilize. If $\xi$ is never initialized, we are done. So
wait for $\xi$ to be initialized, say at stage $s_{0}$. We show that $\xi$
cannot be initialized more than $k^{\prime}(\xi,s_{0})$-times after stage
$s_{0}$, and where $k^{\prime}(\xi,s_{0})$ is defined in Eq. (9). Assume for
contradiction that $\xi$ was initialized more than $k^{\prime}(\xi,s_{0})$
times. Now any initialization of $\xi$ at or after stage $s_{0}$ must be due
to $\xi$ being denied action by some $\eta(x)$ with
$\eta^{\frown}\infty\preceq\xi$, because nodes $\delta<_{L}\xi$ are never
visited and nodes $\delta\prec\xi$ are never initialized by near stability of
$\xi$.

First consider the case where the $[k^{\prime}(\xi,s_{0})+1]$-th intialization
of $\xi$ was due to $\eta(x)$ with $\eta^{\frown}\infty\preceq\xi$ and
$x>l_{s_{0}}(\eta)$. Since $\xi$ is always initialized from being denied
action, the $\xi$-strategy will ensure that $\xi$ always has a follower.
Therefore at the $(\eta^{\frown}\infty)$-stage $s_{1}$ when
$x<l_{s_{1}}(\eta)$ for the first time after stage $s_{0}$,
$(\eta^{\frown}\infty)$-strategy will put $\xi$ into $\eta(x)$’s Qlist.
Furthermore, from Eqs. (9) and (11), $\eta(x)$ will tolerate
$k(\eta(x),s_{1})\geq k^{\prime}(\xi,s_{1})>k^{\prime}(\xi,s_{0})$
initializations from $\xi$, as long as $\xi$ is not removed from $\eta(x)$’s
Qlist before $\xi$ exhausts $\eta(x)$’s quota. But premature removal is not
possible from Eq. (12), because $\xi$ is almost stabilized.

So it must be that $[k^{\prime}(\xi,s_{0})+1]$-th intialization of $\xi$ was
due to $\eta(x)$ with $\eta^{\frown}\infty\preceq\xi$ and $x\leq
l_{s_{0}}(\eta)$. But $\eta(x)$ cannot initialize $\xi$ so often: At the end
of stage $s_{0}$, the $\xi$-strategy will initialize all
$\xi^{\prime}\succ\xi$ and $\xi^{\prime}>_{L}\xi$. Then immediately at the
next $(\eta^{\frown}\infty)$-stage, the $(\eta^{\frown}\infty)$-strategy will
remove these $\xi^{\prime}$ from $\eta(x)$’s Qlist to stop them from ever
injuring $\eta(x)$ again. So apart from $\xi$ itself, the only
$\xi^{\prime\prime}$ nodes that can injure $\eta(x)$ are those
$\xi^{\prime\prime}\succeq\eta^{\frown}\infty$ with
$\xi^{\prime\prime}\prec\xi$. But these $\xi^{\prime\prime}$ never want to act
again by near stability of $\xi$, implying they can never injure $\eta(x)$.
Thus the only positive nodes that can injure $\eta(x)$ are $\xi$ itself and
those $\rho\in\texttt{quota}(x)$. Now before $\xi$ exhausts quota from
$\eta(x)$, $\eta(x)$ cannot injure $\xi$. So wait for quota to be exhausted.
Then $\xi$ will also stop injuring $\eta(x)$, so $\eta(x)$ will behave like in
the proof of Theorem 2.9, with no $\xi^{\prime}$ requirements to complicate
counting of injury. Then by Eq. (6), $\eta(x)$ cannot be injured more than
$(x+1)^{2}4^{(x+1)^{2}}$ times, implying that $\eta(x)$ cannot initialize
$\xi$ more than $(x+1)^{2}4^{(x+1)^{2}}$ times, which is fewer times than
$k^{\prime}(\xi,s_{0})$ from Eq. (9). ∎

######  Claim (Main Lemma 2.5).

If $\xi\prec\delta_{\omega}$, then $\xi$ eventually stops wanting to act.

###### Proof.

Follows from the fact that $\xi$ always will want to act the moment
$\Delta^{A}$ is not diagonalized out of $f^{\xi}$ via the final follower
$z_{\xi}$, and the fact that $\lim_{s}f^{\xi}_{s}(z_{\xi})$ exists, and from
induction hypothesis with Main Lemma 2.4. ∎

######  Claim (Main Lemma 2.6).

If $\eta\prec\delta_{\omega}$, then $\eta$ eventually stops being initialized.

###### Proof.

Wait for all $\rho,\xi\prec\eta$ to stabilize. Then $\eta$ will never be
initialized again. ∎

######  Claim (Main Lemma 2.7).

If $\eta^{\frown}\texttt{fin}\prec\delta_{\omega}$, then $\Phi^{A}_{\eta}$ is
not total.

###### Proof.

Same as the proof for Main Lemma 1.5. ∎

######  Claim (Main Lemma 2.8).

If $\eta^{\frown}\infty\prec\delta_{\omega}$, then $\Phi^{A}_{\eta}$ is total,
and there is computable function $\phi_{\eta}(-):\omega\to\alpha$ such that
for all $x$, $\Phi^{A}_{\eta}(x)[s]$ changes its mind less than
$\phi_{\eta}(x)$ times during the $\eta$-stages.

Like in Main Lemma 1.6 of Theorem 2.1, this claim is the heart of the argument
on why the construction works. Define $S_{\eta}$, $t_{\eta}(x)$, and
$a_{\eta,s}(x)$ like in Eqs. (2), (3), and (4). Note that as before, for fixed
$\eta$, these sets and functions are computable, but not uniformly so. For a
given $x\in\omega$, always assume we are working in the $S_{\eta}$-stages
after $t_{\eta}(x)$.

We prove the claim by induction on $x$. We want to show that for all
$x\in\omega$, $\eta(x)$ gets injured by positive nodes less than $\alpha$
times, and we can compute this injury bound $\phi_{\eta}(x)$ as a computable
function of $x$. The proof outline follows the proof of Theorem 2.9, but with
additional injuries from $\xi$ nodes.

From construction, at stage $t_{\eta}(x)$, $\eta(x)$ will set
$\texttt{Qlist}(\eta,x,t_{\eta}(x))$ according to Eq. (10), deciding once and
for all which $\xi$ nodes are allowed to injure $\eta(x)$. Then by Eq. (11),
$\eta(x)$ also decides to tolerate $k(\eta(x),t_{\eta}(x))$ initializations
from each such $\xi$ node. Between intializations, $\xi$ cannot inflict more
than $g(\xi)$ injury, therefore the total injury on $\eta(x)$ from all the
$\xi$ nodes cannot exceed

$\displaystyle\beta(\eta(x)):=\sum_{\xi\in\texttt{Qlist}(\eta,x,t_{\eta}(x))}g(\xi)\cdot(k(\eta(x),t_{\eta}(x))+1),$
(13)

which is less than $\alpha$ from Fact 3.7.

Now consider the injury from $\rho$ nodes. If $\rho$ can injure $\eta(x)$,
then from Fact 2.4, $\rho$ must lie in the quota $\texttt{quota}(x)$ of
$\eta(x)$. And there are only finitely many such $\rho$ from Eq. (2.2). Recall
that in Theorem 2.9, the main proof idea was that after $\rho$ exhausts quota,
$\rho$ can only injure $\eta(x)$ if triggered by some $\rho^{\prime}$ of
smaller edge layer. This claim still holds except that $\rho$ might also have
been triggered by $\xi$ nodes:

######  Claim 4.6.

If $\delta$ is the node that triggered $\rho$ to injure $\eta(x)$ at stage
$s$, then either $\delta=\xi\in\texttt{Qlist}(\eta,x,t_{\eta}(x))$, or
$\delta=\rho^{\prime}$ where $\rho^{\prime}\succeq\rho^{\frown}\infty$. In
particular, if $\delta=\rho^{\prime}$, then $\rho^{\prime}$ has smaller edge
layer than $\rho$.

###### Proof.

If $\delta\neq\xi$, then the same argument for Claim 2.11 works here too. ∎

######  Claim 4.7.

If $\rho\in\texttt{quota}(x)$ has edge layer $r$, then

$\displaystyle\texttt{InjPow}_{\eta}(x,\rho)\leq\texttt{quotaFor}_{x}(\rho)+\beta(\eta(x))+\sum_{\begin{subarray}{c}\rho^{\prime}\in\texttt{quota}(x)\\\
\rho^{\prime}\text{ has edge layer
}<r\end{subarray}}\;\texttt{InjPow}_{\eta}(x,\rho^{\prime}).$ (14)

###### Proof.

The $\texttt{quotaFor}_{x}(\rho)$ term comes from $\rho$ exhausting quota from
$x$, and the $\beta(\eta(x))$ and summation terms come from Claim 4.6. ∎

###### Proof.

(Of Main Lemma 2.8): From Fact 2.4, working only in the
$(\eta^{\frown}\infty)$-stages after stage $t_{\eta}(x)$,

$\text{Number of times }\eta(x)\text{ gets injured
}\leq\beta(\eta(x))+\sum_{\rho\in\texttt{quota}(x)}\texttt{InjPow}_{\eta}(x,\rho).$

$\beta(\eta(x))$ term is computable as a function of $x$. Also, each term
within the summation is computably bounded below $\alpha$ by the recursive
relation Eq. (14) and Fact 3.7. Together with the fact that
$\texttt{quota}(x)$ is a computable set and Fact 3.7 again, the total injury
on $\eta(x)$ will be computable and less than $\alpha$.

To give a concrete bound on injury, like in the proof of Theorem 2.9, we
assume that the pairing function used for the definition of
$\texttt{quota}(x)$ is such that

$\max\\{\max(|\rho|,k):\;\langle\rho,k\rangle\in\texttt{quota}(x)\\}<x.$

We repeat the inductive proof of Theorem 2.9, but with the role of
$\texttt{quota}(x)$ replaced by $\beta(\eta(x))+\texttt{quota}(x)$. Then given
$\rho\in\texttt{quota}(x)$ with edge layer $r$,
$\texttt{InjPow}_{\eta}(x,\rho)$ will be bounded by
$[\beta(\eta(x))+x]\cdot(r+1)4^{(r+1)^{2}}$, so

$\displaystyle\text{Number of times }\eta(x)\text{ gets
injured}\leq[\beta(\eta(x))+x]\cdot(x+1)4^{(x+1)^{2}}.$

∎

## References

  * [1] Rod Downey.  Array nonrecursive degrees and lattice embeddings of the diamond.  Illinois journal of mathematics, 37(3):349–374, 1993.
  * [2] Rod Downey and Noam Greenberg.  A transfinite hierarchy of lowness notions in the computably enumerable degrees, unifying classes, and natural definability, 2015.
  * [3] Rod Downey, Noam Greenberg, and Rebecca Weber.  Totally $\omega$-computably enumerable degrees and bounding critical triples.  Journal of Mathematical Logic, 7(02):145–171, 2007.
  * [4] Rod Downey, Carl Jockusch, and Michael Stob.  Array nonrecursive sets and multiple permitting arguments.  In Recursion theory week, pages 141–173. Springer, 1990.
  * [5] Rod Downey, Carl Jockusch, and Michael Stob.  Array nonrecursive degrees and genericity.  Computability, Enumerability, Unsolvability (Cooper, Slaman, Wainer, eds.), London Mathematical Society Lecture Notes Series, 224:93–105, 1996.
  * [6] Rodney G Downey and Carl G Jockusch.  T-degrees, jump classes, and strong reducibilities.  Transactions of the American Mathematical Society, 301(1):103–136, 1987.
  * [7] Rodney G Downey and Steffen Lempp.  Contiguity and distributivity in the enumerable turing degrees.  The Journal of Symbolic Logic, 62(4):1215–1240, 1997.
  * [8] Shamil Ishmukhametov.  Weak recursive degrees and a problem of spector.  Recursion theory and complexity (Kazan, 1997), 2:81–87, 1999.
  * [9] Alistair H Lachlan.  Embedding nondistributive lattices in the recursively enumerable degrees.  In Conference in Mathematical Logic-London’70, pages 149–177. Springer, 1972.
  * [10] Robert I Soare.  Recursively enumerable sets and degrees.  Bulletin of the American Mathematical Society, 84(6):1149–1181, 1978.