Sage Journals: Discover world-class research

Abstract

We introduce the notion of eventually uniformly weak truth table array computable (e.u.wtt-a.c.) sets. As our main result, we show that a computably enumerable (c.e.) set has this property iff it is weak truth table ( $wtt$ -) reducible to a maximal set. Moreover, in this equivalence we may replace maximal sets by quasi-maximal sets, hyperhypersimple sets or dense simple sets and we may replace $wtt$ -reducibility by identity-bounded Turing reducibility (or any intermediate reducibility).

Here, a set A is e.u.wtt-a.c. if there is an effective procedure which, for any given partial $wtt$ -functional $\hat{Φ}$ , yields a computable approximation $g (x, s)$ of the domain of ${\hat{Φ}}^{A}$ together with a computable indicator function $k (x, s)$ and a computable order $h (x)$ such that, once the indicator becomes positive, i.e., $k (x, s) = 1$ , the number of the mind changes of the approximation g on x after stage s is bounded by $h (x)$ where, for total ${\hat{Φ}}^{A}$ , the indicator eventually becomes positive on almost all arguments x of ${\hat{Φ}}^{A}$ .

In addition to our main result, we show several properties of the computably enumerable e.u.wtt-a.c. sets. For instance, the class of these sets is closed downwards under $wtt$ -reductions and closed under join. Moreover, we relate this class to – and separate it from – well known classes in the literature. On the one hand, the class of the $wtt$ -degrees of the c.e. e.u.wtt-a.c. sets is strictly contained in the class of the array computable c.e. $wtt$ -degrees. On the other hand, every bounded low set is e.u.wtt-a.c. but there are e.u.wtt-a.c. c.e. sets which are not bounded low. Here a set A is bounded low if $A^{†} ⩽_{wtt} \emptyset^{†}$ , i.e., if $A^{†}$ is ω-c.a., where $A^{†}$ is the $wtt$ -jump of A (Anderson, Csima and Lange (Archive for Mathematical Logic 56(5–6) (2017) 507–521)).

Finally, we prove that there is a strict hierarchy within the class of the bounded low c.e. sets A depending on the order h that bounds the number of mind changes of a computable approximation of $A^{†}$ , and we show that there exists a Turing complete set A such that $A^{†}$ is h-c.a. for any computable order h with $h (0) > 0$ .

Keywords

Computably enumerable sets maximal sets hh-simple sets dense simple sets Post’s Programme Turing degrees wtt-reducibility ibT-reducibility jump bounded jump lowness bounded lowness bounded jump traceability array (non)computability Downey–Greenberg Hierarchy

1. Introduction

The first goal of this paper is to seek to understand the computational power of a class of computably enumerable sets, the maximal sets, in terms of what kinds of sets they can compute, at least through the eyes of a strong reducibility. Our answer to this question yields another goal of this paper. We introduce a new hierarchy classifying computably enumerable sets according to their ability to compute functions and sets, measured in terms of their “mind change” moduli. This is in the spirit of the Strong Jump Tracing [24] and Downey–Greenberg Hierarchies [13]. However, our new hierarchy is not aligned to either of these hierarchies. The new hierarchy is generated via a calibration method involving strong reducibilities and restricted forms of the jump, which may well have further applications. Before we turn to our results, we wish to place them in a historical context.

1.1. Post’s programme and maximal sets

Early applications of computability theory to demonstrate problems in classical mathematics were algorithmically undecidable all worked essentially in the same way. These proofs directly code the halting problem into the decision question at hand. It seemed that all semidecidable (i.e. computably enumerable, c.e.) problems, such as the Entscheidungsproblem or the word problem for groups, were simply the halting problem in disguise under the equivalence $\equiv_{T}$ . This observation led to Post’s Problem which asked if there were intermediate computably enumerable Turing degrees. That is, do there exist c.e. degrees a with $0 <_{T} a <_{T} 0^{'}$ ?

In the quest to solve this question, Post’s Programme [32] tried to find a “thinness” property of the complement of a c.e. set which would guarantee Turing incompleteness. In [32], Post gave the motivation for this programme. Whilst he could not solve his problem, he observed that it is possible to solve it using the thinness approach for reducibilities stronger than Turing reducibility, such as m- and $tt$ -reducibilities.1

¹
We remind the reader that $A ⩽_{m} B$ means that A is computable or there is a computable function f such that $x \in A$ iff $f (x) \in B$ . $A ⩽_{tt} B$ can be formulated as $A ⩽_{T} B$ via a Turing procedure Φ, $Φ^{B} = A$ , such that $Φ^{X}$ is total for all oracles X. Both of these reducibilities were clarified by Post [32].

For example, recall that a co-infinite c.e. set A is simple if its complement is immune: it has no infinite c.e. subsets. Also, A is called hypersimple if there is no computable sequence of pairwise disjoint canonical finite sets

{D_{f (x)} | x \in ω}

where for all x,

D_{f (x)} \cap \overline{A} \neq \emptyset

. Post showed that if A is simple then it has intermediate m-degree, and hypersimple sets have intermediate

tt

-degrees. One reducibility stronger than T-reducibility (but weaker than

tt

-reducibility) is weak truth table (

wtt

-) reducibility, where

A ⩽_{wtt} B

means that there is a Turing procedure Φ and a computable function φ, such that

Φ^{B} (x) = A (x)

and the use of

Φ^{B} (x)

is less than

φ (x)

for all x. If φ is the identity function, then we would say

A ⩽_{ibT} B

(identity bounded Turing reducibility). Friedberg and Rogers [20] showed that hypersimple sets have intermediate

wtt

-degrees.2

In fact Downey and Jockusch [17] showed that if A is hypersimple, then there is no set X with $A {⩽̸}_{wtt} X$ and $A \oplus X ⩾_{wtt} \emptyset^{'}$ .

It is worth noting that the concepts introduced by Post [32] have been highly influential. The original solution to Post’s Problem was by Friedberg [21] and Muchnik [28]. These papers famously introduced the priority method in computability theory. The concepts of immunity and hyperimmunity correlate with various domination properties whose ramifications are still being explored today, both in computability theory and in reverse mathematics. As well as being some of the mainstays of computational complexity (in time bounded form) Post’s fine-grained reducibilities have had applications especially in the theory of algorithmic randomness as they allow for transfer of measure.

Since Post was unable to show that any of his c.e. sets with thin complements were necessarily Turing incomplete, he suggested that perhaps there were c.e. sets with even thinner complements. He asked if there exists a c.e. maximal set. That is, a c.e. co-infinite set M such that for all c.e. sets W, if $M \subseteq W$ then either $M =^{*} W$ (finitely different) or $W =^{*} ω$ . Post did not know if there was a maximal c.e. set. In [19], Friedberg gave a novel and intricate construction of a maximal set, using a primitive form of the infinite injury method. Would such a set yield a realization of Post’s Programme?

Alas no. We now know that Post’s Programme, in its original form, has a negative solution since there is a Turing complete maximal set (Yates [39]). Moreover, since Soare [34] showed that all maximal sets were automorphic in the automorphism group of the lattice of c.e. sets, there are no “extra” properties we could add to maximality which would guarantee Turing incompleteness. Indeed, Cholak, Downey and Stob [8] showed that no property of the lattice of supersets of a c.e. set A alone can guarantee incompleteness.

Ultimately Post’s intuition that structural properties of a c.e. set in the lattice of c.e. sets can guarantee incompleteness does have a realization. Harrington and Soare [25] showed that there is an elementarily definable property Q of c.e. sets such that $Q (A)$ guarantees incompleteness and noncomputability, and there were c.e. sets A such that $Q (A)$ held.

1.2. Maximal sets

Turning the Post programme on its head, Martin [11] and Tennenbaum [36] showed that maximal sets are computationally powerful, rather than weak, as measured by Turing degree. In particular, they are all high. That is, if M is maximal then $M^{'} \equiv_{T} \emptyset^{″}$ . Thus, computationally, they are indistinguishable from the halting problem when we use only the Turing jump to understand them.

The high c.e. degrees are an important well-understood class. Martin realized that the high c.e. degrees capture the computational complexity of a number of classes of c.e. sets. He showed that the high c.e. degrees are precisely the degrees capturing the combinatorics and computational power (in terms of $⩽_{T}$ ) of dense simple, r-maximal, hyperhypersimple, and similar sets.3

³
It is not important here to define these sets, save to say that they are important classes of c.e. sets.

High sets have the ability to compute a function g wich dominates all computable functions.4

⁴

That is, if f is computable then $g (x) > f (x)$ for almost all x.

This highness characterization in terms of domination properties has also been used in many other contexts from computable model theory, degree theory (see Lerman [27]), algorithmic learning theory (Gold [23]), algorithmic randomness (see, e.g., Nies, Stephan and Terwijn [30]), etc. Similar jump characterizations such as

{low}_{2}

(i.e.

X^{″} \equiv_{T} \emptyset^{″}

) have proven very productive (Lerman [27], for example).

1.3. New initiatives

Beginning with the work of Downey, Jockusch and Stob [15,16], a finer classification of c.e. sets has been initiated. This classifies sets according to the number of mind changes needed to compute approximations. Shoenfield’s Limit Lemma says that $f ⩽_{T} \emptyset^{'}$ iff there is a computable approximation $g (\cdot, \cdot)$ such that $g (x, s + 1) \neq g (x, s)$ for only finitely many s and $f (x) = {lim}_{s} g (x, s)$ . Going back to work of Ershov [18], it is possible to understand how complex a $Δ_{2}^{0}$ set or function is by classifying the complexity of its computable approximations g according to their “mind change” functions: $\begin{matrix} m_{g} (x) = | {s | g (x, s + 1) \neq g (x, s)} | . \end{matrix}$ For example, $f ⩽_{wtt} \emptyset^{'}$ iff there is a computable approximation g of f and a computable h where $m_{g} (x) ⩽ h (x)$ . We say that f is h-c.a. (computably approximable) where we usually assume that the bound h is an order, i.e., nondecreasing and unbounded.

The [15] intuition is that we can classify c.e. degrees and sets according to the mind-change complexity of the functions computable from them. A degree would be computationally weak in this sense if it could only compute things with computable approximations which have few mind changes. Downey, Jockusch and Stob studied the c.e. degrees a such that there is a computable h such that every function $f ⩽_{T} a$ is h-c.a. These degrees are called the array computable degrees. They precisely capture the combinatorics of a wide class of degree classes in several parts of computability theory. (This is elaborated in Section 7.) This idea was later generalized by Downey and Greenberg [13] by using computable ordinals into an infinite hierarchy, where array computability was the bottom of this hierarchy. The second level is a non-uniform version of being array computable.

Definition 1.1.
a is called totally ω-c.a. iff for each $f ⩽_{T} a$ , there is a computable h such that f is h-c.a.

Again the notion of being totally ω-c.a. captures the combinatorics of a large number of constructions in computability theory, algorithmic randomness and effective model theory. We refer the reader to [13] for a detailed discussion.

Related here, and of great relevance to us, comes the notion of approximating partial a-computable functions. Frequently this is done in terms of tracing. We say that a set A (and its degree a) is jump traceable at order h (or h-jump traceable for short) if, for any partial A-computable function ψ, there are uniformly c.e. sets ${T_{n} | n \in ω}$ with $| T_{n} | < h (n)$ for all n and $ψ (n) ↓$ implying $ψ (n) \in T_{n}$ . This notion was explicitly introduced by Nies [29], although the idea had been used earlier. Certainly the idea of taming the complexity of a function using tracing had arisen in set theory, and this was the inspiration for its use in algorithmic randomness where it is used to characterize lowness for Schnorr randomness and helps understand K-triviality (see Terwijn and Zambella [37], Downey and Hirschfeldt [14]).

Jump tracing is widely used in the theory of algorithmic randomness, and is a lowness property, in that it implies computational weakness. For example, a natural refinement of the notion of a low set is called superlowness. A set A is superlow if $A^{'} \equiv_{wtt} \emptyset^{'}$ (equivalently, $A^{'} \equiv_{tt} \emptyset^{'}$ ). It is easy to see that a c.e. set A is superlow iff A is h-jump traceable for some computable order h.
1.4. The computational power of maximal sets

Our work was inspired by the following attractive result which characterizes the Turing degrees of the c.e. sets which are not wtt-reducible to hypersimple sets.

Theorem 1.2 (Barmpalias, Downey and Greenberg [5]).

A c.e. Turing degree a contains a c.e. set which is not wtt-computable from a hypersimple set iff a is not totally ω- c.a.

Our motivating question, asked by Ambos-Spies, is

“What is the analog of Theorem 1.2 if we replace hypersimple by maximal?”.

Our hope was that we would get a class of sets A which fell into one of the classes totally ω-c.a., array computable, superlow, or similar classes already investigated in the literature. Unfortunately, this is not the case. It turned out that the answer to Ambos-Spies’s question lay not in understanding the Turing jump, but a weaker notion called the $wtt$ -jump.

The way that this classification came about was quite natural. Initially, we found that if A was a c.e. superlow set, $A ⩽_{wtt} M$ for some maximal set M. We analysed the proof and realized that all of the uses of the computations in the construction had computably bounded uses, and a weaker notion being $wtt$ -superlow sufficed. We discuss this concept in the next subsection.

1.5. The $wtt$ -jump

The strong reducibilities, in particular $wtt$ -reducibility and $tt$ -reducibility, turned out to be a central unifying idea in algorithmic randomness (e.g., Downey–Hirschfeldt [14]). This fact, plus work in many other areas using reducibilities stronger than Turing, show that, rather than mere artifacts of definitions in classical computability theory, hierarchies related to strong reducibilities and bounded jump operators (such as those below) can give classification and unification of combinatorics in parts of computable mathematics. As a consequence, it seems we should better understand analogs of the core notions of classical computability for such hierarchies. This paper contributes to that program.

The earliest analog of a jump operator using only bounded reducibilities is the “mini-jump” hierarchy introduced by Ershov [18] as discussed in Odifreddi [31], Chapter XI.6. Ershov’s hierarchy concerned a jump operator for the m-degrees involving the partial m-degrees. Also a bounded analog of the jump for $tt$ -reductions was investigated by Gerla [22].

For us the bounded jump for $wtt$ -reductions will be of interest. As in Downey and Greenberg [13], from a standard listing of all pairs consisting of a partial Turing procedure and a partial computable function, we obtain a standard listing ${{\hat{Φ}}_{e}}_{e \in ω}$ of the partial $wtt$ -functionals together with a computable listing ${{\hat{φ}}_{e}}_{e \in ω}$ of the corresponding partial computable use bounds (see Section 3 below for details). Then the $wtt$ -jump or bounded jump of a set A is defined by $\begin{matrix} A^{†} = {⟨ e, x ⟩ : {\hat{Φ}}_{e}^{A} (x) ↓} . \end{matrix}$ Clearly the usual equivalences obtained by the s-m-n theorem apply. So the $wtt$ -jump of A is (up to m-degree) the same as the diagonal $wtt$ -jump ${e | {\hat{Φ}}_{e}^{A} (e) ↓}$ (in the literature sometimes the latter is denoted by $A^{†}$ ). Note that $\emptyset^{'} \equiv_{m} \emptyset^{†}$ , and that for a c.e. set A, $\emptyset^{'} ⩽_{wtt} A^{†} ⩽_{wtt} {(\emptyset^{'})}^{†}$ . Moreover if X is $Δ_{2}^{0}$ , $X^{†}$ is also $Δ_{2}^{0}$ .

The analog of the idea of lowness for the bounded jump can be defined as follows. A set A is bounded low or $wtt$ -superlow if $A^{†} ⩽_{wtt} \emptyset^{'}$ (or, equivalently, $A^{†} ⩽_{tt} \emptyset^{'}$ ). Variations of bounded lowness – all of them $wtt$ -equivalent to this notion – have been studied by Coles, Downey, and LaForte [9], Csima, Downey and Ng [10], Anderson and Csima [3], Ambos-Spies, Downey and Monath [2], and Wu and Wu [38]. It is easy to see that all superlow sets A are bounded low (i.e., $wtt$ -superlow), but below we prove that there are Turing complete bounded low c.e. sets. (This result was independently obtained by Wu and Wu [38].)

We discovered that, if A is $wtt$ -superlow, then $A ⩽_{wtt} M$ for some maximal set M. However, $wtt$ -superlowness is not a necessary condition to be $⩽_{wtt} M$ for some maximal M.

1.6. The main theorem

In the end, we discovered that a technical variation of the idea above actually gives a necessary and sufficient condition. This variation will be defined in Section 4, and is called eventually uniformly $wtt$ -array computable. Armed with this notion we prove the following.

Theorem 1.3.
For a c.e. A, $A ⩽_{ibT} M$ for some maximal set M iff $A ⩽_{wtt} M$ for some maximal set M iff A is eventually uniformly $wtt$ -array computable.

Moreover, in this theorem we may replace maximal sets by quasimaximal sets or hyperhypersimple sets or dense simple sets. The proof of Theorem 1.3 is quite technical and will be given in Section 4.
1.7. New hierachies

We have seen that our new notion of (eventual) $wtt$ -array computability classifies precisely the computational power of maximal sets. Having seen the usefulness of the ideas of array computability, superlowness, and those in the Downey–Greenberg Hierarchy, we believe that hierarchies based around analogs of these ideas, but concerning strong reducibilities could well prove similarly useful. Thus we will devote the remainder of the paper to this exploration. Proofs are given in some detail as the techniques here are new.

Since the new notions concern weak truth table reducibility, it is natural to explore these concepts via reducibilities stronger $⩽_{T}$ , whilst still keeping in mind how they relate to known hierarchies. In the later sections we show that the $wtt$ -degrees of the eventually uniformly $wtt$ -array computable c.e. sets form an ideal (Section 5). We relate the e.u.wtt-a.c. sets to other lowness notions thereby giving strict lower and upper bounds on the class of the c.e. sets with this property (and their $wtt$ -degrees). First we show that any $wtt$ -superlow set is eventually uniformly $wtt$ -array computable (Section 6) and that any eventually uniformly $wtt$ -array computable c.e. set is array computable (Section 7). Then, in the final Section 8, we give separations of these concepts by showing that there are maximal sets which are not $wtt$ -superlow, and there are array computable c.e. sets which are not $wtt$ -reducible to any maximal set. Note that, by $wtt$ -invariance of the e.u.wtt-a.c. property, these separations extend to the corresponding $wtt$ -degrees.

1.8. A new hierarchy of bounded lowness

In Section 6, we have a closer look at the $wtt$ -superlow (i.e., bounded low) c.e. sets. We remark that Anderson, Csima and Lange already demonstrated in [4] that the bounded jump and the Turing jump are quite different with respect to the low/high hierarchy by showing the existence of both a low set which is bounded high and a high set which is bounded low. For example we can sharpen at least on of these results by demonstrating the following.

Theorem 1.4.
There is a T-complete $wtt$ -superlow c.e. set.

In fact, we get more. The $wtt$ -analog of (h-)jump traceability, (h-) $wtt$ -jump traceability, turns out to be equivalent to $wtt$ -superlowness (just as $jump$ -traceability is equivalent to superlowness). This leads to a new hierarchy of the $wtt$ -superlow sets based on the growth rates of the orders h. This is a strong reducibility analog of the Downey–Greenberg Hierarchy, but calibrates the c.e. sets in ways which are very different from that known hierarchy.

We first show that this hierarchy is proper. This result allows us to can define very strong lowness notions, such as A being strongly $wtt$ -superlow if A is h- $wtt$ -jump traceable for all computable orders h. Theorem 1.4 can actually be improved to say that there is a Turing complete strongly $wtt$ -superlow set. Whilst we have only begun exploration of this new hierarchy, we will prove this and some other results in Section 6.
2. Notation

We follow the standard notation as given in [35]. In particular, ${Φ_{e}}_{e \in ω}$ denotes a standard enumeration of all Turing functionals, where $φ_{e}^{A} (x)$ denotes the use of a computation of $Φ_{e}^{A} (x)$ with oracle A and input x. Moreover, ${φ_{e}}_{e \in ω}$ denotes a standard enumeration of all unary partial computable functions and ${W_{e}}_{e \in ω}$ , where $W_{e} = dom (φ_{e})$ – the domain of $φ_{e}$ – denotes the induced standard enumeration of all c.e. sets. We let $Φ_{e, s}^{A} (x)$ , $φ_{e, s}^{A} (x)$ and $φ_{e, s} (x)$ denote the approximation of $Φ_{e}^{A} (x)$ , $φ_{e}^{A} (x)$ and $φ_{e} (x)$ within s steps, respectively, and we let $W_{e, s} = dom (φ_{e, s})$ . We adapt the now commonly used Lachlan notation for approximations of computations, i.e., if A is a set and ${A_{s}}_{s \in ω}$ is a sequence of sets approximating A in the limit then we let $Φ_{e}^{A} (x) [s] = Φ_{e, s}^{A_{s}} (x)$ . Finally, we follow the usual convention on converging computations, i.e., for any oracle A and any numbers e, x, y, s, if $Φ_{e, s}^{A} (x) ↓ = y$ then $max {e, x, y, φ_{e}^{A} (x)} < s$ , and, similarly, if $φ_{e, s} (x) ↓ = y$ then $max {e, x, y} < s$ ; in particular, we have $W_{e, s} \subseteq ω ↾ s$ .

3. Basic definitions and properties

Let us start by giving the definition of the bounded jump. The underlying notation is mostly adapted from [13].

Definition 3.1 ([13]).

For any set $X \subseteq ω$ and for any numbers $e_{0}, e_{1}, y \in ω$ , let $\begin{aligned} (1) & {\hat{Φ}}_{⟨ e_{0}, e_{1} ⟩}^{X} (y) = \{\begin{array}{ll} Φ_{e_{0}}^{X} (y) & if Φ_{e_{0}}^{X} (y) ↓, φ_{e_{1}} (y) ↓ and φ_{e_{0}}^{X} (y) ⩽ φ_{e_{1}} (y), \\ ↑ & otherwise, \end{array} \\ (2) & {\hat{φ}}_{⟨ e_{0}, e_{1} ⟩} = φ_{e_{1}} . \end{aligned}$ Given a set A, the (diagonal) bounded jump and the bounded jump function of A, denoted by $A^{†}$ ( $A_{d}^{†}$ ) and ${\hat{J}}^{A}$ , respectively, are defined as $\begin{aligned} (3) & A^{†} = {⟨ e, x ⟩ : {\hat{Φ}}_{e}^{A} (x) ↓}, \\ (4) & A_{d}^{†} = {e : {\hat{Φ}}_{e}^{A} (e) ↓}, and \\ (5) & {\hat{J}}^{A} (e) = {\hat{Φ}}_{e}^{A} (e) . \end{aligned}$

For notational convenience, we define the bounded jump $A^{†}$ of a set A such that $A^{†}$ codes all computations of partial $wtt$ -functionals instead of only the diagonal computations, the latter one being denoted by $A_{d}^{†}$ . However, it is easy to see that $A^{†}$ and $A_{d}^{†}$ are computably isomorphic (see clause 3. of Lemma 3.4 below). Before we start examining some of the properties of $A^{†}$ and ${\hat{J}}^{A}$ for a (c.e.) set A, let us make some general remarks on the definition of ${\hat{Φ}}_{e}$ and introduce some terminology to be used below which is also mostly taken from [13]. First of all, we say that a Turing functional Φ is a $wtt$ -functional if there exists a number $e \in ω$ such that $Φ = {\hat{Φ}}_{e}$ . Note that, for any set A and any total function g, $g ⩽_{wtt} A$ holds iff there exists $e \in ω$ such that $g = {\hat{Φ}}_{e}^{A}$ . So ${{\hat{Φ}}_{e}}_{e \in ω}$ incorporates all $wtt$ -reductions.

Using ${{\hat{Φ}}_{e}}_{e \in ω}$ , we may extend the definition of being $wtt$ -reducible to a set A to partial functions. We say that a partial function $φ : ω \to ω$ is $wtt$ -reducible to a set A, and denote it by $φ ⩽_{wtt} A$ , if there exists $e \in ω$ such that $φ = {\hat{Φ}}_{e}^{A}$ . Furthermore, for sets A and B, we say that A is bounded computably enumerable in B, bounded c.e. in B or bounded B-c.e. for short, if there exists a partial function φ such that φ is $wtt$ -reducible to B and $A = dom (φ)$ . In particular, $A^{†}$ is bounded c.e. in A for all sets A.

We fix computable approximations ${\hat{Φ}}_{⟨ e_{0}, e_{1} ⟩, s}^{X} (y)$ ( $s ⩾ 0$ ) of ${\hat{Φ}}_{⟨ e_{0}, e_{1} ⟩}^{X} (y)$ where ${\hat{Φ}}_{⟨ e_{0}, e_{1} ⟩, s}^{X} (y)$ is defined iff ${\hat{Φ}}_{⟨ e_{0}, e_{1} ⟩}^{X} (y)$ , $Φ_{e_{0}, s}^{X} (y)$ and $φ_{e_{1}, s} (y)$ are defined. Then, for any c.e. set A and any fixed computable enumeration ${A_{s}}_{s \in ω}$ of A, we have a canonical approximation to $A^{†}$ , denoted by ${A_{s}^{†}}_{s \in ω}$ , such that, for all numbers e, x, we have that $⟨ e, x ⟩ \in A_{s}^{†}$ iff ${\hat{Φ}}_{e}^{A} (x) [s] ↓$ . We tacitly assume that this approximation to $A^{†}$ is clear from the context whenever a c.e. set A and a computable enumeration of A is given to or constructed by us. Note that if ${\hat{Φ}}_{e}^{A} (x) [s] ↓$ holds for infinitely many stages s then ${\hat{Φ}}_{e}^{A} (x) ↓$ holds as the use of ${\hat{Φ}}_{e}$ is bounded (this does not hold for Turing functionals in general).

Moreover, we will often make use of the Recursion Theorem (with Parameters) with respect to ${{\hat{Φ}}_{e}}_{e \in ω}$ . For that, we need the following definition.

Definition 3.2.
A sequence of $wtt$ -functionals ${Ψ_{e}}_{e \in ω}$ is uniformly computable if ${Ψ_{e}}_{e \in ω}$ is uniformly computable in the sense of Turing functionals and there exists a uniformly computable sequence of partial computable functions ${ψ_{e}}_{e \in ω}$ such that, for any $e \in ω$ , the use of $Ψ_{e}$ is bounded by $ψ_{e}$ .

Then the following lemma says that ${{\hat{Φ}}_{e}}_{e \in ω}$ is a Gödel numbering of the $wtt$ -functionals whence we may argue as in the proof of the classical Recursion Theorem (with Parameters) that the Recursion Theorem also holds for uniformly computable sequences of $wtt$ -functionals.
Lemma 3.3 (Recursion Theorem (with Parameters)).

Let ${Ψ_{e}}_{e \in ω}$ be a sequence of $wtt$ -functionals and $g : ω \to ω$ and $H : ω^{2} \to ω$ be total computable functions. Then the following holds.

${Ψ_{e}}_{e \in ω}$ is uniformly computable iff there exists a computable one-one function $f : ω \to ω$ such that $Ψ_{e}^{A} = {\hat{Φ}}_{f (e)}^{A}$ holds for any number e and any set A.

There exists $e \in ω$ such that ${\hat{Φ}}_{g (e)} = {\hat{Φ}}_{e}$ .

There exists a computable function $h : ω \to ω$ such that ${\hat{Φ}}_{h (e)} = {\hat{Φ}}_{H (h (e), e)}$ holds for any $e \in ω$ .

Proof.
For the “only if”-part of clause 1., note that a sequence ${{\hat{Φ}}_{f (e)}}_{e \in ω}$ , where $f : ω \to ω$ is a computable function, is a uniformly computable sequence of $wtt$ -functionals since the use bound ${{\hat{φ}}_{f (e)}}_{e \in ω}$ is a uniformly computable sequence of partial computable functions. For the “if”-direction, by Definition 3.2, we may fix computable one-one functions $f_{i} : ω \to ω$ ( $i ⩽ 1$ ) such that, for any $e \in ω$ , we have $Ψ_{e} = Φ_{f_{0} (e)}$ and $ψ_{e} = φ_{f_{1} (e)}$ . Then, by (1) and by assumption on $Ψ_{e}$ , we have that $Ψ_{e} = {\hat{Φ}}_{f (e)}$ for the computable one-one function $f (e) = ⟨ f_{0} (e), f_{1} (e) ⟩$ .

For the proofs of clauses 2. and 3., it is easy to see that the proofs of the Recursion Theorem and the Recursion Theorem with Parameters can be carried out in the setting of uniformly computable $wtt$ -functionals. In the following, we give a sketch of the proofs by outlining the critical parts.

For clause 2., the proof is as follows. For any numbers $e, x \in ω$ and any set A, let $\begin{array}{r} Ψ_{e}^{A} (x) = \{\begin{array}{ll} {\hat{Φ}}_{φ_{e} (e)}^{A} (x) & if φ_{e} (e) ↓, \\ ↑ & otherwise . \end{array} \end{array}$ Then the sequence ${Ψ_{e}}_{e \in ω}$ is a uniformly computable sequence of Turing functionals whose use if uniformly bounded by $ψ_{e} (x) = {\hat{φ}}_{φ_{e} (e)} (x)$ . So since ${ψ_{e}}_{e \in ω}$ is a uniformly computable sequence of partial computable functions, by clause 1., we may fix a computable function $d : ω \to ω$ such that $Ψ_{e}^{A} = {\hat{Φ}}_{d (e)}^{A}$ holds for any $e \in ω$ and any set A, and we may fix $i \in ω$ such that $φ_{i} (x) = g (d (x))$ . Then, by virtually the same argument as in the proof of the classical Recursion Theorem, it follows that $e = d (i)$ is a fixed point for g.

For clause 3., we argue analogously. Let $\begin{array}{r} Ψ_{⟨ x, y ⟩}^{A} (z) = \{\begin{array}{ll} {\hat{Φ}}_{φ_{x} (⟨ x, y ⟩)}^{A} (z) & if φ_{x} (⟨ x, y ⟩) ↓, \\ ↑ & otherwise . \end{array} \end{array}$ Then since ${Ψ_{e}}_{e \in ω}$ is clearly a uniformly computable sequence of Turing functionals and ${ψ_{e}}_{e \in ω}$ , where $ψ_{⟨ x, y ⟩} (z) = {\hat{φ}}_{φ_{x} (⟨ x, y ⟩)} (z)$ is a uniformly computable sequence of partial computable functions bounding the use of $Ψ_{⟨ x, y ⟩}^{A}$ for any $x, y \in ω$ and any set A, we may easily argue as in the proof of the Recursion Theorem with Parameters that $h (x) = d (i, x)$ is as desired, where, by clause 1., $d : ω^{2} \to ω$ is chosen such that $Ψ_{⟨ x, y ⟩}^{A} = {\hat{Φ}}_{d (x, y)}^{A}$ holds and $i \in ω$ is chosen such that $φ_{i} (⟨ x, y ⟩) = H (d (x, y), y)$ holds for all $x, y \in ω$ . □

It is natural to ask what properties the bounded jump operator share with the classical Turing jump operator if we replace Turing reductions by $wtt$ -reductions. In the following lemma, we list some of the common properties which can be found in [13, p.30].
Lemma 3.4 ([13]).

Let A and B be any (not necessarily c.e.) sets. Then the following holds.

If $A ⩽_{wtt} B$ then there exists a strictly increasing computable function $f : ω \to ω$ such that, for any $e \in ω$ , ${\hat{Φ}}_{e}^{A} = {\hat{Φ}}_{f (e)}^{B}$ .

$A^{†}$ is 1-complete for the class of the bounded A-c.e. sets. In particular, $\emptyset^{'}$ is computably isomorphic to $\emptyset^{†}$ .

There exists a strictly increasing computable function $f : ω \to ω$ such that, for any e, x and any set A, ${\hat{Φ}}_{e}^{A} (x) = {\hat{J}}^{A} (f (⟨ e, x ⟩))$ . Hence, $A^{†}$ is computably isomorphic to $A_{d}^{†}$ .

$A <_{wtt} A^{†}$ .

$A ⩽_{wtt} B$ implies $A^{†} ⩽_{1} B^{†}$ .

However, not every property of the Turing jump carries over to the bounded jump as the following lemma of [13] shows.

Lemma 3.5 ([13], Lemma 3.6).

There is a c.e. set B and a set A such that $A^{†} ⩽_{1} B^{†}$ holds but $A ≰_{wtt} B$ .

The fact that the converse of clause 5. in Lemma 3.4 fails is due to the fact that the Complement Lemma does not carry over to bounded-c.e. sets as Downey and Greenberg also show in [13, Proposition 3.1(3)]. However, the proof of Lemma 3.5 (and similarly for [13, Proposition 3.1(3)]) builds on the fact that the set A constructed there may change its mind whether a given x is in A or not more than once. This leaves the question open whether the Complement Lemma and hence the converse of clause 5. in Lemma 3.4 hold if A is chosen to be computably enumerable. We can affirmatively answer both questions.

Lemma 3.6.
For any sets A and B such that A is c.e. or co-c.e., if A and $\overline{A}$ are bounded-c.e. in B then $A ⩽_{wtt} B$ . In particular, if A and B are c.e. then $A^{†} ⩽_{1} B^{†}$ implies that $A ⩽_{wtt} B$ holds.
Proof.
For a proof of the first part of the lemma, fix sets A and B such that A is c.e. or co-c.e. and A and $\overline{A}$ are bounded-c.e. in B. By $\overline{A} \equiv_{wtt} A$ w.l.o.g. we may assume that A is computably enumerable. So fix a computable enumeration ${A_{s}}_{s \in ω}$ of A and fix a number e such that $\overline{A} = dom ({\hat{Φ}}_{e}^{B})$ . Then we can compute A from B by a Turing reduction whose use is computably bounded as follows.

Let $f (x) = μ s (x \in A_{s} or {\hat{φ}}_{e, s} (x) ↓)$ . Then f is a total computable function as ${\hat{φ}}_{e} (x) ↓$ holds for any number $x \notin A$ . Given x, with oracle B compute the least stage $s ⩾ f (x)$ such that either $x \in A_{s}$ or ${\hat{Φ}}_{e, s}^{B} (x) ↓$ . Then, by our assumptions on A, stage s exists, and $x \in A$ iff $x \in A_{s}$ . Moreover, since, by the convention on converging computations, ${\hat{φ}}_{e} (x) < f (x)$ if ${\hat{φ}}_{e} (x) ↓$ , $B ↾ f (x)$ can compute the stage s.

For the second part of Lemma 3.6, it suffices to note that $A^{†} ⩽_{1} B^{†}$ implies that A and $\overline{A}$ are bounded-c.e. in B. So the second part follows from the first part. □

Next, we formulate and prove the main result of this paper.
4. C.E. sets which are bounded Turing reducible to maximal sets

For our main result, we make the following definition.

Definition 4.1.
A set A is eventually uniformly $wtt$ -array computable (e.u.wtt-a.c. for short) if there exist computable functions $g, k : ω^{2} \to {0, 1}$ and a computable order $h : ω \to ω$ such that, for all e, x, $\begin{array}{c} (6) & A^{†} (x) = lim_{s \to \infty} g (x, s), \\ (7) & k (x, s) ⩽ k (x, s + 1), \\ (8) & k (x, s) = 1 \Rightarrow | {t ⩾ s : g (x, t + 1) \neq g (x, t)} | ⩽ h (x), \\ (9) & \forall e ({\hat{Φ}}_{e}^{A} total \Rightarrow \forall^{\infty} x \exists s (k (⟨ e, x ⟩, s) = 1)) . \end{array}$ For functions g, k and h as above, we say that A is eventually uniformly $wtt$ -array computable via g, k and h, and we let EUwttAC denote the class of all c.e. e.u.wtt-a.c. sets.

Now the main result is as follows.
Theorem 4.2 (Characterization Theorem).

For a c.e. set A the following are equivalent.

A is eventually uniformly $wtt$ -array computable.

A is $wtt$ -reducible to some maximal (quasi-maximal, hh-simple, dense simple) set.

A is ibT-reducible to some maximal (quasi-maximal, hh-simple, dense simple) set.

Since $ibT$ -reducibility is stronger than $wtt$ -reducibility, for a proof of Theorem 4.2 it suffices to prove the implications $(i) \Rightarrow (iii)$ and $(ii) \Rightarrow (i)$ . In fact, since the strength of the simplicity notions considered here is ordered by $\begin{matrix} maximal \Rightarrow quasi-maximal \Rightarrow hh-simple \Rightarrow dense simple \end{matrix}$ (see, e.g., Soare [35], page 211), in the proof of the former implication it suffices to consider maximal sets, and in the proof of the latter implication it suffices to consider dense simple sets. So Theorem 4.2 follows from the following two theorems.

Theorem 4.3.
Let A be c.e. and eventually uniformly $wtt$ -array computable. Then A is ibT-reducible to some maximal set.
Theorem 4.4.
Let A and D be c.e. sets such that $A ⩽_{wtt} D$ and D is dense simple. Then A is eventually uniformly $wtt$ -array computable.

In the remainder of this section we prove these two theorems.
Proof of Theorem 4.3.
Let ${A_{s}}_{s \in ω}$ be a computable enumeration of A and fix computable functions $\hat{g}$ , $\hat{k}$ and $\hat{h}$ which witness that A is e.u.wtt-a.c. according to Definition 4.1. We construct a c.e. set M in stages s, where $M_{s}$ denotes the finite set of numbers which are enumerated into M by stage s, such that M is maximal and $A ⩽_{ibT} M$ . Clearly, any such M witnesses that Theorem 4.3 holds.

Before we give the formal construction, let us discuss some of the ideas behind it and introduce some of the concepts to be used in the construction. We start with the task of making M maximal.

In order to make M maximal, it suffices to ensure that the complement of M is infinite, $\begin{matrix} (10) & | \overline{M} | = ω, \end{matrix}$ and that M meets the requirements $\begin{aligned} (11) & R_{e} : \overline{M} \subseteq^{} W_{e} or \overline{M} \subseteq^{} \overline{W_{e}} . \end{aligned}$ for $e \in ω$ .

In order to achieve these goals, just as in the classical maximal set construction (as for instance in Soare [35]), we use n-states and “optimize” the states of almost all elements in $\overline{M}$ . Since we use a priority tree here, however, in our definition of the states the infinitary outcome (corresponding to the case that $W_{e} \cap \overline{M}$ is infinite) is denoted by 0 (as common on priority trees) and not by 1 as in the classical definition of states. So here the n-state of a number x at stage s is the unique binary string $σ (n, x, s)$ of length n such that, for $e < n$ , $\begin{matrix} σ (n, x, s) (e) = 0 iff x \in W_{e, s}, \end{matrix}$ and the (true) n-state of x is the unique binary string $σ (n, x)$ of length n such that, for $e < n$ , $\begin{matrix} σ (n, x) (e) = 0 iff x \in W_{e} . \end{matrix}$ Note that requirements $R_{0}, \dots, R_{n}$ are met if almost all elements of $\overline{M}$ have the same $(n + 1)$ -state. So, in order to meet the maximal set requirements, it suffices to guarantee that, for any $n ⩾ 0$ , almost all numbers in $\overline{M}$ have the same n-state. In the construction of M we achieve this by attempting to minimize the n-states of the numbers in $\overline{M}$ (which corresponds to the classical strategy of maximizing the (classically defined) n-states).

For this sake we use the full binary tree $T = {0, 1}^{< ω}$ as the priority tree. Elements of T are called nodes. As usual, we say for two nodes α and β that α has higher priority than β and denote it by $α < β$ iff $α ⊏ β$ (i.e., α is a proper initial segment of β) or α is to the left of β, denoted by $α <_{L} β$ , i.e., there exists $γ \in T$ such that $γ 0 ⊑ α$ and $γ 1 ⊑ β$ . Nodes are viewed as states in the following sense. A node $α \in T$ of length n codes the guess that there are infinitely many numbers in $\overline{M}$ with n-state α. Then, assuming that $\overline{M}$ is infinite, there is a leftmost path through T such that, for any node α on this path, there are infinitely many elements of $\overline{M}$ which have state α. So it suffices to guarantee that almost all elements of $\overline{M}$ have state α.

In order to approximate the true path, for any node α and any stage s, we let $\begin{aligned} V_{α, s} & = \overline{M_{s}} ↾ s \cap {y : σ (| α |, y, s) = α} \\ = \overline{M_{s}} ↾ s \cap {y : \forall e < | α | (y \in W_{e, s} \Leftrightarrow α (e) = 0)} \end{aligned}$ and $\begin{matrix} V_{α} = \overline{M} \cap {y : σ (| α |, y) = α} = \overline{M} \cap {y : \forall e < | α | (y \in W_{e} \Leftrightarrow α (e) = 0)}, \end{matrix}$ and we use the following length of agreement function $\begin{aligned} (12) & l (α, s) = | V_{α, s} | . \end{aligned}$ Based on $l (α, s)$ , we define the set of α-stages by induction on $| α |$ as follows. Every stage is a λ-stage. An α-stage s is called α-expansionary if $s = 0$ or $l (α 0, s) > l (α 0, t)$ holds for all α-stages $t < s$ . Then a stage s is an $α 0$ -stage if it is α-expansionary and an $α 1$ -stage if it is an α-stage but not α-expansionary. At stage s, the current approximation $δ_{s}$ of the true path is the unique node α of length s such that s is an α-stage, and we say that α is accessible at stage $s + 1$ if α is an initial segment of $δ_{s}$ , i.e., $α ⊑ δ_{s}$ . Then the true path $TP$ through T is defined by $TP = {lim inf}_{s \to \infty} δ_{s}$ , i.e., $TP ↾ n$ is the leftmost node of length n which is accessible infinitely often (for every n).

Next we explore under which assumptions on M the true path TP actually has the desired properties, i.e., satisfies that, for any n, $TP ↾ n$ is the leftmost node α of length n such that $V_{α}$ is infinite. We start with some observations. Note that $\begin{matrix} (13) & V_{α 0, s} = V_{α, s} \cap W_{| α |, s} and V_{α 1, s} = V_{α, s} \cap \overline{W_{| α |, s}} . \end{matrix}$ So $V_{α, s}$ is the disjoint union of $V_{α 0, s}$ and $V_{α 1, s}$ , $\begin{matrix} (14) & V_{α, s} = V_{α 0, s} \dot{\cup} V_{α 1, s}, \end{matrix}$ and $\begin{matrix} (15) & l (α, s) = l (α 0, s) + l (α 1, s) . \end{matrix}$ Note that the analog of (14) holds for $V_{α}$ , too, and that the equation can be extended to $\begin{matrix} (16) & V_{α, s} = \underset{| β | = n}{⋃^{˙}} V_{α β, s} and V_{α} = \underset{| β | = n}{⋃^{˙}} V_{α β} \end{matrix}$ for any $n ⩾ 0$ . Next note that, for any node α, ${V_{α, s}}_{s \in ω}$ is a computable approximation of $V_{α}$ , i.e., for any number y, $\begin{matrix} (17) & V_{α} (y) = lim_{s \to \infty} V_{α, s} (y) . \end{matrix}$ Moreover, a number $y \in V_{α, s}$ is in $V_{α}$ unless y is enumerated into M after stage s or the $| α |$ -state of y decreases after stage s. So, if we let $\begin{matrix} {\hat{V}}_{α} = ⋃_{{α^{'} : | α^{'} | = | α | & α^{'} ⩽_{L} α}} V_{α^{'}}, \end{matrix}$ then $\begin{matrix} (18) & {\hat{V}}_{α} = \overline{M} \cap (⋃_{s \in ω} ⋃_{{α^{'} : | α^{'} | = | α | & α^{'} ⩽_{L} α}} V_{α^{'}, s}) . \end{matrix}$ In fact, if we say that $α^{'}$ is stronger than α ( $α^{'} ≺ α$ ) if $α^{'} <_{L} α$ or $α ⊏ α^{'}$ (i.e., viewed as a state, either $α^{'}$ is less than α or $α^{'}$ contains more information than α) then, by the definition of ${\hat{V}}_{α}$ and (16), ${\hat{V}}_{α^{'}} \subseteq {\hat{V}}_{α}$ for any $α^{'}$ which is stronger than α whence $\begin{matrix} (19) & {\hat{V}}_{α} = ⋃_{{α^{'} : α^{'} ⪯ α}} V_{α^{'}} = \overline{M} \cap (⋃_{s \in ω} ⋃_{{α^{'} : α^{'} ⪯ α}} V_{α^{'}, s}) . \end{matrix}$

We can now state the two crucial facts on TP used in the proof. Claim 1 (Infinity Lemma).

Assume ( 10 ). For any node $α ⊏ TP$ , the set $S_{α}$ of the α-stages is infinite and $\begin{matrix} (20) & lim_{s \to \infty, s \in S_{α}} l (α, s) = ω . \end{matrix}$ Moreover, if $α^{'}$ is to the left of TP then $S_{α^{'}}$ and ${\hat{V}}_{α^{'}}$ are finite.

Proof.
For a proof of the first part, fix $α ⊏ TP$ . The infinity of $S_{α}$ is immediate by the definition of $TP$ . The proof of (20) is by induction on $| α |$ . We distinguish the following three cases. First assume that $α = λ$ . Then $S_{α} = ω$ and $V_{λ} = \overline{M}$ . So (20) holds by the infinity of $\overline{M}$ . Next assume that $α = \hat{α} 0$ for some node $\hat{α}$ . Then, by $α ⊏ TP$ there are infinitely many $\hat{α}$ -expansionary stages. So $S_{α}$ is infinite and (20) holds by definition. Finally assume that $α = \hat{α} 1$ for some node $\hat{α}$ . Then, by $\hat{α} 1 ⊏ TP$ , there are only finitely many $\hat{α} 0$ -stages, whence $l (\hat{α} 0, s)$ is bounded. By the former, $S_{α} =^{*} S_{\hat{α}}$ while, by the latter and by (15), there is a constant c such that $l (α, s) + c ⩾ l (\hat{α}, s)$ for all stages s. So infinity of (20) follows by the inductive hypothesis.

For a proof of the second part, fix $α^{'}$ to the left of $TP$ , let $α = TP ↾ | α^{'} |$ and let $\hat{α}$ be the longest common initial segment of $α^{'}$ and α. Then $\hat{α} 0 ⊑ α^{'}$ and $\hat{α} 1 ⊑ α$ whence $\hat{α}$ and $\hat{α} 1$ are on the true path. By the definition of $TP$ , it follows that $S_{\hat{α} 0}$ is finite. Since, by $\hat{α} 0 ⊑ α^{'}$ , $S_{α^{'}} \subseteq S_{\hat{α} 0}$ , $S_{α^{'}}$ is finite, too. Finally, in order to show that ${\hat{V}}_{α^{'}}$ is finite, for a contradiction assume that ${\hat{V}}_{α^{'}}$ is infinite. Since ${\hat{V}}_{α^{'}}$ is the finite union of the sets $V_{α^{″}}$ where $| α^{″} | = | α^{'} |$ and $α^{″} ⩽_{L} α^{'}$ , for notational convenience, w.l.o.g. we may assume that $V_{α^{'}}$ is infinite. It follows that $V_{\hat{α} 0}$ is infinite since, by $\hat{α} 0 ⊑ α^{'}$ , $V_{α^{'}} \subseteq V_{\hat{α} 0}$ . By (17) this implies that ${lim}_{s \to ω} l (\hat{α} 0) = ω$ . Since, by $\hat{α} ⊏ TP$ , $S_{\hat{α}}$ is infinite, it follows that there are infinitely many $\hat{α}$ -expansionary stages, hence $S_{\hat{α} 0}$ is infinite contradicting the above observation that $S_{\hat{α} 0}$ is finite. □
Claim 2 (Maximal Set Lemma).

Assume that M is c.e. and coinfinite. If, for any $α ⊏ TP$ , $\overline{M} \subseteq^{*} {\hat{V}}_{α}$ then M is maximal.

Proof.
Since ${\hat{V}}_{α}$ is the finite union of $V_{α}$ and the sets $V_{α^{'}}$ such that $α^{'} <_{L} α$ and $| α^{'} | = | α |$ , it follows by the second part of the Infinity Lemma that $\overline{M} \subseteq^{} V_{α}$ for all $α ⊏ TP$ . So, for any $n ⩾ 0$ , almost all numbers in $\overline{M}$ have $(n + 1)$ -state $TP ↾ n + 1$ . As pointed out before, this implies that all requirements $R_{n}$ are met. Since, by assumption, M is c.e. and coinfinite this implies that M is maximal. □

The Infinity Lemma shows that (assuming $\overline{M}$ is infinite), for any α on the true path and for any numbers r and k, there are infinitely many stages at which α is accessible and where we can pick k numbers greater than r of current state α which have not yet been enumerated into M. (Note that, for meeting a finitary requirement we typically need such a set of numbers, where later in the construction some of these numbers may be put into M and some of the numbers may be kept out of M.) On the other hand, the Maximal Set Lemma tells us that if we make sure that infinitely many of the numbers we pick in this way are kept out of M and that, for any $α ⊏ TP$ , up to finitely many exceptions, only those numbers picked for α or a stronger node $α^{'}$ are kept out of M then M is maximal. These observations lead to the following strategy ensuring maximality. We pick the numbers which become associated with a given node α for ensuring any of the additional finitary tasks in such a way that one of these numbers is never needed for this task (this will ensure that $\overline{M}$ infinite). Moreover, if the task assigned to the numbers associated with a state α can be taken over by the numbers associated with a stronger state (or, as in the following, associated with a finite collection of stronger states) then the original attempt becomes superfluous and we may cancel it and enumerate the corresponding numbers into M.

Having introduced the basic technical notions needed for the maximal set strategy, we now turn to the second goal of the construction, namely, to ensure that the given computably enumerable e.u.wtt-a.c. set A is ibT-reducible to the maximal set M that we construct. We first note that this part requires the construction of a uniformly computable sequence of auxiliary $wtt$ -functionals ${Ψ_{α}}_{α \in {0, 1}^{}}$ , where we denote the partial computable use bound of $Ψ_{α}$ by $ψ_{α}$ . By identifying ${0, 1}^{}$ with ω in the standard way, by Lemma 3.3 (Recursion Theorem), we may assume that in advance* we are given a computable function $f : {0, 1}^{} \to ω$ such that $\begin{matrix} (21) & Ψ_{α} = {\hat{Φ}}_{f (α)} \end{matrix}$ holds for all $α \in {0, 1}^{}$ . So, by letting $g (⟨ α, x ⟩, s) = \hat{g} (⟨ f (α), x ⟩, s)$ , $k (⟨ α, x ⟩, s) = \hat{k} (⟨ f (α), x ⟩, s)$ and $h (⟨ α, x ⟩) = \hat{h} (⟨ f (α), x ⟩)$ , we obtain $\begin{array}{c} (22) & lim_{s \to \infty} g (⟨ α, n ⟩, s) = \{\begin{array}{ll} 0 & if Ψ_{α}^{A} (n) ↑, \\ 1 & otherwise \end{array} \\ (23) & k (⟨ α, n ⟩, s) ⩽ k (⟨ α, n ⟩, s + 1) \\ (24) & k (⟨ α, n ⟩, s) = 1 \Rightarrow | {t ⩾ s : g (⟨ α, n ⟩, t + 1) \neq g (⟨ α, n ⟩, t)} | ⩽ h (⟨ α, n ⟩) \\ (25) & Ψ_{α}^{A} is total \Rightarrow \forall^{\infty} n \exists s (k (⟨ α, n ⟩, s) = 1) \end{array}$ and we may use these equations in the construction.

Now, coming back to the second goal of the construction, in order to ensure that A is ibT-reducible to M, we use a variant of straight permitting: if a number x enters A at a “late” stage s then, in order to indicate that x is in A we enumerate a number $y ⩽ x$ into M at stage s or at a later stage. Note that if we reserve a number y for such a permitting and x does not enter A then y will not enter M, too. So, in order to be compatible with the maximal set strategy, we have to ensure that the states of the permitters y are sufficiently small. In order to show that there are sufficiently many permitters of small state, we exploit that A is eventually uniformly $wtt$ -array computable. The basic idea of how to obtain permitters (for almost all numbers x) of a given m-state α (on or to the right of $TP$ ) is as follows. We attempt to define a strong array ${B_{n}^{α}}_{n \in ω}$ of finite sets $B_{n}^{α}$ , in the following called (α-)blocks. The α-blocks are defined one after the other in increasing order, and we ensure that the numbers in $B_{n + 1}^{α}$ are greater than the numbers in $B_{n}^{α}$ . Moreover, when an α-block becomes defined, say, at stage $s + 1$ then all of its elements are not in $M_{s}$ and have m-state α or stronger than α at stage s. (Note that (assuming that $\overline{M}$ is infinite), by the Infinity Lemma, for α on or to the right of the true path, we will find such numbers no matter how large we want to make the blocks. So, for such α, all the α-blocks will become defined.) Now the idea is that the numbers y in block $B_{n}^{α}$ serve as permitters for the numbers x in the interval $I_{n}^{α} = [max B_{n}^{α}, max B_{n + 1}^{α}]$ (note that these intervals cover all numbers $x ⩾ max B_{0}^{α}$ ). In order to guarantee that the size (i.e., cardinality) of $B_{n}^{α}$ is large enough to provide the required numbers of permitters, we appropriately define the corresponding auxiliary $wtt$ -functional $Ψ_{α}$ . We let $ψ_{α} (n) = max B_{n + 1}^{α}$ (if the latter block becomes defined) be the use of $Ψ_{α}^{X} (n)$ . Moreover, if $ψ_{α} (n)$ is defined then we ensure that $Ψ_{α}^{A} (n)$ is defined, too, where – exploiting that, by (22), $g (⟨ α, n ⟩, s)$ approximates the domain of $Ψ_{α}^{A}$ – we make sure that any enumeration of a number $x \in I_{n}^{α}$ in A is followed by a change of $g (⟨ α, n ⟩, s + 1) \neq g (⟨ α, n ⟩, s)$ at a later stage s. Now, since $Ψ_{α}^{A}$ is total, it follows by (25) that (for almost all n) there is a least stage $s_{n}$ such that $k (⟨ α, n ⟩, s_{n}) = 1$ , and, by (24), $λ s . g (⟨ α, n ⟩, s)$ will change after stage $s_{n}$ at most $h (⟨ α, n ⟩)$ times. So if we say that a number $x \in I_{n}^{α}$ enters A “late” if it does so after stage $s_{n}$ then $h (⟨ α, n ⟩)$ permitters suffice for dealing with all numbers in $I_{n}^{α}$ . So it suffices to let $B_{n}^{α}$ have size $h (⟨ α, n ⟩)$ .

The above explains how, for a single α on or to the right of the true path, we can ensure that $A ⩽_{ibT} M$ and at the same time only numbers of state α or a stronger state are left in $\overline{M}$ (namely, it suffices to enumerate all numbers which are not in any α-block into M). Moreover, by adding one more element to each α-block we can guarantee that no α-block becomes completely enumerated into M whence $\overline{M}$ will be infinite.

For the actual construction, however, we have to ensure that, for any α on the true path, almost all numbers left in $\overline{M}$ have state α or stronger state. We achieve this by (1) carrying out the above strategy for all α and by (2) suspending the permitting numbers in block $B_{n}^{α}$ (in the actual construction we say that the block $B_{n}^{α}$ becomes frozen) and enumerating them into M once we see that, for any number $x \in I_{n}^{α}$ , there is a node $α^{'} ≺ α$ and a number $n^{'}$ such that x is in the interval $I_{n^{'}}^{α^{'}}$ covered by the $α^{'}$ -block $B_{n^{'}}^{α^{'}}$ and x is considered to be “late” relative to this block, too (i.e., $k (⟨ α^{'}, n^{'} ⟩, s) = 1$ if this happens at stage $s + 1$ ). As we will show, this will provide the required improvements of states.

There is one technical problem left, however. We cannot achieve that, for $α \neq α^{'}$ , the α-blocks and $α^{'}$ -blocks are disjoint. So when determining the sizes of the blocks we have to consider possible overlaps. By allowing the $α^{'}$ -strategy to use a number in the intersection of the blocks $B_{n}^{α}$ and $B_{n^{'}}^{α^{'}}$ only if $α^{'}$ is stronger than α, we have to ensure that any block $B_{n}^{α}$ contains a core ${\hat{B}}_{n}^{α}$ of size $h (⟨ α, n ⟩) + 1$ which does not intersect any $α^{'}$ -block for all stronger $α^{'}$ . The sole purpose of the priority tree is to resolve this problem. The interval $B_{n}^{α}$ will be defined by one of the nodes β which extends α and has length $⟨ | α |, n ⟩$ . As long as $B_{n}^{α}$ is not yet defined there will be (at most) one such β “eligible” to define $B_{n}^{α}$ . The stage when this node becomes eligible gives a lower bound on $min B_{n}^{α}$ and, by initializing a node, its eligibility can be (temporarily) deleted. This will suffice to avoid overlaps between α-blocks and $α^{'}$ -blocks for comparable α and $α^{'}$ and will give an eligible node β a bound on the sizes of the potential overlaps in terms of the higher priority nodes currently admissible.

Having explained the ideas of the construction and some of its technical features, we now turn to the construction. Any stage $s + 1$ consists of 5 steps (Stage 0 is vacuous).

In Step 1 the blocks are defined. We let the nodes β with $α ⊑ β$ and $| β | = ⟨ | α |, n ⟩$ define the block $B_{n}^{α}$ . We call such a node β a $B_{n}^{α}$ -node and call $B_{n}^{α}$ the block associated with β. Moreover, we call two nodes equivalent if they are associated with the same block. If $B_{n}^{α}$ is defined by (activity of) the node β then we say that $B_{n}^{α}$ has priority β. As long as $B_{n}^{α}$ is not yet defined, there will be at most one $B_{n}^{α}$ -node β which is eligible. This node attempts to define $B_{n}^{α}$ . Once $B_{n}^{α}$ is defined, no $B_{n}^{α}$ -node will be eligible. A node β can become eligible only at a stage $s + 1$ such that $β ⊏ δ_{s}$ or $δ_{s} <_{L} β$ . Once β is eligible, β stays eligible unless β becomes initialized. The only effect of initialization of a node is to make it non-eligible. If initialized, a node may become eligible at a later stage again. We write $B_{n}^{α} [s] ↓$ if $B_{n}^{α}$ is defined by the end of Step 1 of stage s, and we write $B_{n}^{α} [s] ↑$ otherwise. Moreover, $B_{n}^{α} ↓$ ( $B_{n}^{α} ↑$ ) denotes that $B_{n}^{α}$ is eventually defined (never defined). For any α and n such that $B_{n}^{α}$ is defined, we let $\begin{matrix} {\hat{B}}_{n}^{α} = {y \in B_{n}^{α} : ∄ α^{'} ≺ α ∄ n^{'} (B_{n^{'}}^{α^{'}} ↓ & y \in B_{n^{'}}^{α^{'}})} \end{matrix}$ be the core of $B_{n}^{α}$ . Similarly, for s such that $B_{n}^{α} [s] ↓$ , we let $\begin{matrix} {\hat{B}}_{n}^{α} [s] = {y \in B_{n}^{α} : ∄ α^{'} ≺ α ∄ n^{'} (B_{n^{'}}^{α^{'}} [s] ↓ & y \in B_{n^{'}}^{α^{'}})} \end{matrix}$ be the core of $B_{n}^{α}$ at stage s.

In Steps 2 and 3, the partial use functions $ψ_{α}$ and the $wtt$ -functionals $Ψ_{α}$ are defined. We write $ψ_{α} (n) [s] ↓$ if $ψ_{α} (n)$ has been defined by the end of Step 2 of stage s and write $ψ_{α} (n) [s] ↑$ otherwise, and we write $Ψ_{α}^{A} (n) [s] ↓$ if $Ψ_{α}^{A_{s}} (n)$ has been defined by the end of Step 3 of stage s and $Ψ_{α}^{A} (n) [s] ↑$ otherwise. We say that the α-block $B_{n}^{α}$ is realized at stage s if $ψ_{α} (n) [s] ↓$ and we say that $B_{n}^{α}$ is truly realized at stage s if $B_{n}^{α}$ is realized at stage s and $k (⟨ α, n ⟩, s) = 1$ ; and $B_{n}^{α}$ is realized (truly realized) if it is realized (truly realized) at some stage. Finally, we say that x is (truly) covered by $B_{n}^{α}$ (at stage s) – or (truly) $⟨ α, n ⟩$ -covered (at stage s) for short – if $⟨ α, n ⟩$ is (truly) realized (at stage s) and $x \in [max B_{n}^{α}, ψ_{α} (n)]$ ; and we say that x is α-covered (at stage s) if x is $⟨ α, n ⟩$ -covered (at stage s) for some n.

In Step 4 blocks become frozen. We say that a block $B_{n}^{α}$ is admissible at stage s, if it is truly realized at stage s and has not been frozen by the end of Step 4 of stage s.

In Step 5 numbers are enumerated into M, i.e., $M_{s + 1}$ becomes defined.

Now, using the notation introduced above, the steps of stage $s + 1$ are as follows.
Step 1 (Defining the blocks $B_{n}^{α}$ ). A $B_{n}^{α}$ -node β requires attention at stage $s + 1$ if one of the following holds.
$B_{n}^{α} [s] ↑$

$β ⊏ δ_{s}$ or $δ_{s} <_{L} β$ and $| β | < s$ .

Neither β nor any equivalent node $β^{'}$ such that $β^{'} <_{L} β$ is eligible at stage s.

For any node $β^{'}$ such that $β^{'} ⊏ β$ , the block associated with $β^{'}$ is defined at stage s.

For any node $β^{'}$ such that $β <_{L} β^{'}$ , $| β^{'} | = | β |$ and $β^{'}$ is not equivalent to β, the block associated with $β^{'}$ is defined at stage s.

β is eligible at stage s, and there is a block B which is suitable for the definition of $B_{n}^{α}$ by β at stage $s + 1$ . Here a block B is suitable for the definition of $B_{n}^{α}$ by the $B_{n}^{α}$ -node β at stage $s + 1$ if B has the following properties.

$r (β, s) < min B$ ,

$B \subseteq ⋃_{{α^{'} : | α^{'} | = | α | and α^{'} ⩽_{L} α}} V_{α^{'}, s}$ ,

The block B has cardinality $| B | = F (β, s)$ where $F (γ, s)$ is defined (by induction on γ) by $\begin{matrix} F (γ, s) = 2 + H (γ) + \sum_{{γ^{'} : γ^{'} <_{L} γ and γ^{'} is eligible at stage s}} F (γ^{'}, s) \end{matrix}$ where, for a $B_{n^{'}}^{α^{'}}$ -node γ, $H (γ) = h (⟨ α^{'}, n^{'} ⟩)$ (and where $\sum_{\emptyset} = 0$ ). (Note that, at any given stage s, there are only finitely many eligible nodes, hence $F (γ, s)$ is well-defined.)
Fix β minimal such that β requires attention.

If (a) holds then declare that β becomes eligible, set $r (β^{'}, s + 1) = s$ for all $β^{'} ⩾ β$ , and initialize all nodes $β^{'}$ with $β < β^{'}$ (i.e., no such $β^{'}$ is eligible at stage $s + 1$ ).

If (b) holds then let $B_{n}^{α} = B$ for the least (w.r.t. the canonical index) block B which is suitable for the definition $B_{n}^{α}$ by β at stage $s + 1$ , let β be the priority of $B_{n}^{α}$ , set $r (β^{'}, s + 1) = s$ for all $β^{'} > β$ , and initialize all nodes $β^{'}$ such that $β ⩽ β^{'}$ .

If no node requires attention then Step 1 of stage $s + 1$ is vacuous.

Step 2 (Defining the partial computable use functions $ψ_{α}$ ). For any α and any n such that either $n = 0$ or $ψ_{α} (n - 1) [s] ↓$ , $ψ^{α} (n) [s] ↑$ and $B_{n + 1}^{α} [s] ↓$ , let $ψ_{α} (n) = max B_{n + 1}^{α}$ .

Step 3 (Defining the $wtt$ -functionals $Ψ_{α}$ ). For any α and any n such that $ψ_{α} (n) [s] ↓$ let $\begin{matrix} (26) & Ψ_{α}^{A} (n) [s + 1] ↓ if Ψ_{α}^{A} (n) [s] ↑ and g (⟨ α, n ⟩, s) = 0, \end{matrix}$ and let $\begin{matrix} (27) & Ψ_{α}^{A} (n) [s + 1] ↑ if Ψ_{α}^{A} (n) [s] ↓, g (⟨ α, n ⟩, s) = 1 and A_{s + 1} ↾ ψ_{α} (n) \neq A_{s} ↾ ψ_{α} (n) . \end{matrix}$ In any other case let $Ψ_{α}^{A} (n) [s + 1] ↓$ if and only if $Ψ_{α}^{A} (n) [s] ↓$ .

Step 4 (Freezing blocks). A block $B_{n}^{α}$ is freezable at stage $s + 1$ if the following hold.
$⟨ | α |, n ⟩ < s$ .

$B_{n}^{α}$ is not frozen at stage s.

For any x covered by $B_{n}^{α}$ there is a block $B_{n_{x}}^{α_{x}}$ such that $α_{x} ≺ α$ , $B_{n_{x}}^{α_{x}}$ is admissible at stage s, and $B_{n_{x}}^{α_{x}}$ covers x.
If there is a freezable block then choose $q = ⟨ m, n ⟩$ minimal such that there is a freezable block $B_{n}^{α}$ with $| α | = m$ and fix the rightmost α such that $| α | = m$ and $B_{n}^{α}$ is freezable. Declare that $B_{n}^{α}$ becomes frozen at stage $s + 1$ .

Step 5 (Enumerating M). A number $y \notin M_{s}$ is enumerated into M at stage $s + 1$ if (at least) one of the following hold.

(Freezing) There is a block $B_{n}^{α}$ which becomes frozen in Step 4 of stage $s + 1$ and y is in the core ${\hat{B}}_{n}^{α} [s + 1]$ of $B_{n}^{α}$ at stage $s + 1$ .

(Enumerating nonblock numbers) y is not in any block defined at stage $s + 1$ and y is less than the maximum of a block defined at stage $s + 1$ .

(Coding A into M) There is a node α and a number n such that the block $B_{n}^{α}$ is admissible at stage s and $\begin{matrix} (28) & Ψ_{α}^{A} (n) [s] ↓ and Ψ_{α}^{A} (n) [s + 1] ↑ \end{matrix}$ or $\begin{matrix} (29) & g (⟨ α, n ⟩, s) = 1 and g (⟨ α, n ⟩, s + 1) = 0, \end{matrix}$ holds, and y is the least element of the core ${\hat{B}}_{n}^{α} [s + 1]$ of $B_{n}^{α}$ at stage $s + 1$ which is not in $M_{s}$ . In this case, call y an $⟨ α, n ⟩$ -coding number.

This completes the construction. In the remainder of the proof we show that M has the required properties.

We first summarize the properties of the blocks we will need. Claim 3.
The definition of the blocks satisfies the following conditions.
If $B_{n}^{α}$ becomes defined at stage $s + 1$ (i.e., $B_{n}^{α} [s + 1] ↓$ and $B_{n}^{α} [s] ↑$ ) then $B_{n}^{α} \cap M_{s} = \emptyset$ .

If $B_{n}^{α}$ is defined then $\begin{matrix} B_{n}^{α} \cap \overline{M} \subseteq ⋃_{{α^{'} : | α^{'} | = | α | and α^{'} ⩽_{L} α}} V_{α^{'}} . \end{matrix}$

If $B_{n}^{α}$ is defined then $⟨ | α |, n ⟩ ⩽ min B_{n}^{α}$ .

If $B_{n + 1}^{α}$ is defined then $B_{n}^{α}$ is defined and $max B_{n}^{α} < min B_{n + 1}^{α}$ .

If $B_{n}^{α}$ is defined then, for the core $\begin{matrix} {\hat{B}}_{n}^{α} = B_{n}^{α} ∖ ⋃_{{(α^{'}, n^{'}) : α^{'} ≺ α, n^{'} ⩾ 0 and B_{n^{'}}^{α^{'}} ↓}} B_{n^{'}}^{α^{'}} \end{matrix}$ of $B_{n}^{α}$ , $| {\hat{B}}_{n}^{α} | > h (⟨ α, n ⟩) + 1$ .

If $B_{n}^{α}$ is defined and $α ≺ α^{'}$ and $| α^{'} | ⩽ | α |$ then $B_{n}^{α^{'}}$ is defined, too.

Assume that $\overline{M}$ is infinite. Then, for any α on or to the right of the true path, the blocks $B_{n}^{α}$ are defined for all n.

There is an infinite path p through $T = {0, 1}^{}$ such that, for any α, all blocks* $B_{n}^{α}$ ( $n ⩾ 0$ ) are defined if and only if α is on or to the right of p.

Proof.
With the exception of property (B₇) the proof only depends on the definition of the blocks and not on the other parts of the construction. In case of (B₇) we use that at any stage $s + 1$ any number y which is enumerated into M at stage $s + 1$ is bounded by the maximum of some block existing at this stage.

We tacitly use that the restraint function is nondecreasing in both arguments, i.e., $r (β, s) ⩽ r (β^{'}, s^{'})$ for $β ⩽ β^{'}$ and $s ⩽ s^{'}$ , and that for any pair $⟨ α, n ⟩$ and any stage s there is at most one eligible $B_{n}^{α}$ -node at stage s and there is no such node if $B_{n}^{α} [s] ↓$ .

(B₀). This is immediate by clause (ii) in the definition of suitability since, for any node α and any stage s, $V_{α, s} \subseteq \overline{M_{s}}$ .

(B₁). This is immediate by clause (ii) in the definition of suitability since, for any node α and any stage s, $\begin{matrix} \overline{M} \cap ⋃_{{α^{'} : | α^{'} | = | α | and α^{'} ⩽_{L} α}} V_{α^{'}, s} \subseteq ⋃_{{α^{'} : | α^{'} | = | α | and α^{'} ⩽_{L} α}} V_{α^{'}} . \end{matrix}$

(B₂). If β is the priority of the block $B_{n}^{α}$ and $B_{n}^{α}$ becomes defined at stage $s + 1$ then $r (β, s) < min B_{n}^{α}$ by clause (i) in the definition of suitability. Moreover, there is a stage $s^{'} + 1 ⩽ s$ such that β receives attention via (a) and becomes eligible at stage $s^{'} + 1$ . By clause (ii) in (a), this implies that $| β | < s^{'} = r (β, s^{'} + 1) ⩽ r (β, s)$ . Finally, since β is a $B_{n}^{α}$ -node, $| β | = ⟨ | α |, n ⟩$ .

(B₃). Assume that $B_{n + 1}^{α}$ becomes defined by β at stage $s + 1$ . Then, for the greatest stage $t < s + 1$ such that β is not eligible at stage t, $t + 1 ⩽ s$ and β receives attention via clause (a) at stage $t + 1$ . So, since there is $B_{n}^{α}$ -node $β^{'}$ such that $β^{'} ⊏ β$ , $B_{n}^{α} [t + 1] ↓$ whence $max B_{n}^{α} ⩽ t$ . Moreover, $r (β, t + 1) = t$ hence, by $t + 1 ⩽ s$ , $r (β, s) ⩾ t$ . By the latter and by clause (i) in the definition of suitability of a block B, it follows that $t < min B_{n + 1}^{α}$ , which completes the proof of (B₃).

(B₄). Assume that $B_{n}^{α}$ is defined. Fix the node β and the stage $s + 1$ such that $B_{n}^{α}$ has priority β and $B_{n}^{α}$ becomes defined by activity of β at stage $s + 1$ . Then, given any state $α^{'}$ and any number $n^{'}$ such that $\begin{matrix} (30) & α^{'} ≺ α, B_{n^{'}}^{α^{'}} is defined and B_{n^{'}}^{α^{'}} \cap B_{n}^{α} \neq \emptyset, \end{matrix}$ it suffices to show that, for the priority $β^{'}$ of $B_{n^{'}}^{α^{'}}$ , $\begin{array}{c} (31) & β^{'} <_{L} β, \\ (32) & β^{'} is eligible at stage s, \end{array}$ and $\begin{matrix} (33) & | B_{n^{'}}^{α^{'}} | = F (β^{'}, s) \end{matrix}$ hold. Namely, since different blocks have different priorities, it follows that $\begin{aligned} | {\hat{B}}_{n}^{α} | & = | B_{n}^{α} ∖ ⋃_{{(α^{'}, n^{'}) : α^{'} ≺ α, n^{'} ⩾ 0 and B_{n^{'}}^{α^{'}} ↓}} B_{n^{'}}^{α^{'}} | \\ ⩾ | B_{n}^{α} | - \sum_{{(α^{'}, n^{'}) : α^{'} ≺ α, n^{'} ⩾ 0, B_{n^{'}}^{α^{'}} ↓ and B_{n^{'}}^{α^{'}} \cap B_{n}^{α} \neq \emptyset}} | B_{n^{'}}^{α^{'}} | \\ ⩾ F (β, s) - \sum_{{β^{'} : β^{'} <_{L} β and β^{'} is eligible at stage s}} F (β^{'}, s) \\ (by the definition of B_{n}^{α} and by (30) implying (31)–(33)) \\ ⩾ H (β) + 2 \\ (by the definition of F (β, s)) \\ = h (⟨ α, n ⟩) + 2 \\ (by the definition of H (β)) \end{aligned}$ So, assuming that (30) implies (31)–(33), (B₄) holds.

Hence, for the remainder of the proof of (B₄), fix $α^{'}$ and $n^{'}$ such that (30) holds, and let $β^{'}$ be the priority of $B_{n^{'}}^{α^{'}}$ . We have to show that (31)–(33) hold. Fix $t < s$ maximal such that β is not eligible at stage t and fix $t^{'} + 1 < s^{'} + 1$ such that $B_{n^{'}}^{α^{'}}$ becomes defined via $β^{'}$ at stage $s^{'} + 1$ and $t^{'}$ is maximal such that $t^{'} < s^{'}$ and $β^{'}$ is not eligible at stage $t^{'}$ . Note that β becomes eligible at stage $t + 1$ , β is not initialized (hence eligible) at any stage u such that $t + 1 ⩽ u < s + 1$ , and $B_{n}^{α}$ is defined by β at stage $s + 1$ . Hence $\begin{matrix} (34) & t = r (β, t + 1) = r (β, s) < min B_{n}^{α} ⩽ max B_{n}^{α} ⩽ s . \end{matrix}$ Similarly, $β^{'}$ becomes eligible at stage $t^{'} + 1$ , $β^{'}$ is not initialized (hence eligible) at any stage $u^{'}$ such that $t^{'} + 1 ⩽ u^{'} < s^{'} + 1$ , and $B_{n^{'}}^{α^{'}}$ is defined by $β^{'}$ at stage $s^{'} + 1$ . Hence $\begin{matrix} (35) & t^{'} = r (β^{'}, t^{'} + 1) = r (β^{'}, s^{'}) < min B_{n^{'}}^{α^{'}} ⩽ max B_{n^{'}}^{α^{'}} ⩽ s^{'} . \end{matrix}$ Moreover, any node γ with $β < γ$ is initialized at stages $t + 1$ and $s + 1$ , and any node $γ^{'}$ with $β^{'} < γ^{'}$ is initialized at stages $t^{'} + 1$ and $s^{'} + 1$ . Finally note that, by $(α, n) \neq (α^{'}, n^{'})$ , $β \neq β^{'}$ and the stages t, s, $t^{'}$ , $s^{'}$ are pairwise distinct.

Now, the proof of (31)–(33) is in two steps: before we prove (31), we show that (31) implies (32) and (33). So assume (31). Now, if $s^{'} + 1 < s + 1$ then (by (31)) β is initialized at stage $s^{'} + 1$ hence $s^{'} + 1 < t + 1$ . So, by (34) and (35), $max B_{n^{'}}^{α^{'}} < min B_{n}^{α}$ contradicting (30). Similarly, if $s + 1 < t^{'} + 1$ , then by (34) and (35), $max B_{n}^{α} < min B_{n^{'}}^{α^{'}}$ , again contradicting (30). So $t^{'} + 1 < s + 1 < s^{'} + 1$ must hold. Now (35) is immediate by the choice of $t^{'}$ . Moreover, again by the choice of $t^{'}$ , no node $γ ⩽ β^{'}$ is initialized at any stage $u^{'} \in [t^{'} + 1, s^{'} + 1)$ , whence no node $γ^{'} < β^{'}$ becomes active at any such stage. So a node $γ^{'} < β^{'}$ is eligible at stage s if and only if it is eligible at stage $s^{'}$ . By the definition of F, this implies that $F (β^{'}, s) = F (β^{'}, s^{'})$ . Equation (33) follows since $| B_{n^{'}}^{α^{'}} | = F (β^{'}, s^{'})$ .

It remains to establish (31). By assumption $α^{'} ≺ α$ , hence $α^{'} <_{L} α$ or $α ⊏ α^{'}$ . In the former case, (31) is immediate since $α^{'} ⊑ β^{'}$ and $α ⊑ β$ . So, for the remainder of the argument assume that $α ⊏ α^{'}$ and, for a contradiction, assume that (31) fails, i.e. that $β^{'} ⊏ β$ or $β ⊏ β^{'}$ or $β <_{L} β^{'}$ . If $β^{'} ⊏ β$ then, by construction, $B_{n^{'}}^{α^{'}}$ has to be defined before β can become eligible, i.e., $s^{'} + 1 < t + 1$ whence $max B_{n^{'}}^{α^{'}} < min B_{n}^{α}$ contrary to (30). Similarly, if $β ⊏ β^{'}$ then $s + 1 < t^{'} + 1$ hence $max B_{n}^{α} < min B_{n^{'}}^{α^{'}}$ contrary to (30).

This leaves the case that $β <_{L} β^{'}$ . If $s^{'} + 1 < t + 1$ or $s + 1 < s^{'} + 1$ then, as above, we may conclude from (34) and (35) that (30) fails (note that in the latter case, $s + 1 < t^{'} + 1$ by $β < β^{'}$ ). So w.l.o.g. $t + 1 < s^{'} + 1 < s + 1$ . But since $α ⊏ α^{'}$ and since $β < β^{'}$ , $V_{α^{'}, s^{'}} \subseteq V_{α, s^{'}}$ , $F (β, s^{'}) ⩽ F (β^{'}, s^{'})$ and $r (β, s^{'}) ⩽ r (β^{'}, s^{'})$ . So since the block $B_{n^{'}}^{α^{'}}$ is suitable for $β^{'}$ at stage $s^{'} + 1$ , $B_{n^{'}}^{α^{'}}$ or a subblock B of it will be suitable for β at stage $s^{'} + 1$ , too. So, since β is eligible at stage $s^{'} + 1$ , β will require attention at stage $s^{'} + 1$ . Since $β < β^{'}$ , this contradicts the fact that $β^{'}$ receives attention. This completes the proof of (31) and the proof of (B₄).

(B₅). Fix α, $α^{'}$ and n such that $B_{n}^{α} ↓$ and either $α^{'} ⊏ α$ or $α <_{L} α^{'}$ and $| α | = | α^{'} |$ . It suffices to show $B_{n}^{α^{'}} ↓$ . (Then the claim follows by induction on $| α |$ .) Let β be the priority of $B_{n}^{α}$ and fix the least stage $s + 1$ at which β becomes eligible hence requires attention via clause (a). Then the subclauses (iv) and (v) of (a) guarantee that, for any node $β^{'}$ such that either $β^{'} ⊏ β$ or $β <_{L} β^{'}$ , $| β | = | β^{'} |$ and β and $β^{'}$ are not equivalent, the block associated with $β^{'}$ is defined at stage s. But if $α^{'} ⊏ α$ then $B_{n}^{α^{'}}$ is associated with the proper initial segment $β^{'} = β ↾ ⟨ | α^{'} |, n ⟩$ of β and if $α <_{L} α^{'}$ and $| α | = | α^{'} |$ then $B_{n}^{α^{'}}$ is associated with the node $β^{'} = α^{'} 1^{| β | - | α |}$ and $β <_{L} β^{'}$ , $| β | = | β^{'} |$ and β and $β^{'}$ are not equivalent. So in either case $B_{n}^{α^{'}} ↓$ .

(B₆). The proof is indirect. Assume that $\overline{M}$ is infinite and that there is a node α and a number n such that $TP ↾ | α | ⩽_{L} α$ and $B_{n}^{α}$ is not defined. Fix $q = ⟨ m, n ⟩$ minimal such that there is a node α of length m such that $TP ↾ m ⩽_{L} α$ and $B_{n}^{α}$ is not defined and fix the rightmost corresponding α. Moreover, let β be the rightmost $B_{n}^{α}$ -node. (Note that $β = α 1^{q - m}$ . In particular, $α ⊑ β$ , $| β | = q$ and, by $TP ↾ | α | ⩽_{L} α$ and by the definition of β, $TP ↾ q ⩽_{L} β$ .)

We claim that there is a stage $s^{}$ such that no node $β^{'}$ with $β^{'} < β$ which is not equivalent to β requires attention after stage $s^{}$ . This is shown as follows. Note that any node $β^{'}$ with $β^{'} < β$ which is not equivalent to β is element of one of the following sets. $\begin{array}{c} N_{0} = {β^{'} : | β^{'} | ⩽ | β | & β^{'} <_{L} TP ↾ | β^{'} |} \\ N_{1} = {β^{'} : | β^{'} | < | β | & TP ↾ | β^{'} | ⩽_{L} β^{'}} \\ N_{2} = {β^{'} : | β^{'} | = | β | & TP ↾ | β | ⩽_{L} β^{'} <_{L} β β^{'} is not a B_{n}^{α} -node} \\ N_{3} = {β^{'} : | β | < | β^{'} | & β^{'} <_{L} β} \end{array}$ So it suffices to show that for $i ⩽ 4$ there is a stage $s_{i}$ such that no node in $N_{i}$ requires attention after stage $s_{i}$ .

$i = 0$ . Fix $t_{0}$ minimal such that $TP ↾ q < δ_{s}$ for all stages $s ⩾ t_{0}$ . Then no $β^{'} \in N_{0}$ can become eligible after stage $t_{0}$ . So whenever a node $β^{'} \in N_{0}$ requires attention at a stage $s + 1 > t_{0}$ , either the block associated with $β^{'}$ becomes defined (namely, if $β^{'}$ acts at stage $s + 1$ ) or $β^{'}$ becomes initialized (namely, if a higher priority node $β^{″} < β^{'}$ acts at stage $s + 1$ ). In either case $β^{'}$ will not require attention after stage $s + 1$ . Since $N_{0}$ is finite, this gives the existence of the desired stage $s_{0}$ .

$i = 1$ . Note that by the minimality of q, any node $β^{'} \in N_{1}$ is associated with a block which eventually becomes defined. Since $N_{1}$ is finite, this gives the existence of the desired stage $s_{1}$ .

$i = 2$ . Note that, for any $β^{'} \in N_{2}$ , $β^{'} <_{L} β$ , $| β^{'} | = | β |$ and $β^{'}$ and β are not equivalent. Since the block $B_{n}^{α}$ associated with β is never defined, it follows, by clause (v) in the definition of requiring attention via (a), that no node in $N_{1}$ will ever require attention via (a). So $s_{2} = 0$ will do.

$i = 3$ . If $β^{'} \in N_{3}$ then, for the proper initial segment $β^{″} = β^{'} ↾ | β |$ of $β^{'}$ of length $| β |$ , either $β^{″} \in N_{2}$ or $β^{″}$ is a $B_{n}^{α}$ -node. In either case the block associated with $β^{″}$ is never defined. So, by clause (iv) in the definition of requiring attention via (a), $β^{'}$ does not require attention via (a), hence does not require attention. So $s_{3} = 0$ will do.

Having established the existence of $s^{}$ , we next claim that there is a stage $t^{} > s^{}$ and a $B_{n}^{α}$ node $\hat{β}$ such that $\hat{β}$ is eligible at all stages $s ⩾ t^{}$ . Since, by the choice of $s^{}$ , a $B_{n}^{α}$ -node $β^{'}$ can be initialized at a stage $s + 1 > s^{}$ only if a $B_{n}^{α}$ -node $β^{″}$ to the left of it becomes active at stage $s + 1$ , and since by $B_{n}^{α} ↑$ this implies that $β^{″}$ acts via clause (a) hence becomes eligible at stage $s + 1$ , it suffices to show that some $B_{n}^{α}$ -node $β^{'}$ will be eligible at some stage $s + 1 > s^{}$ . For a contradiction assume that such $β^{'}$ and $s + 1$ do not exist. By the minimality of q and maximality of α, we may fix a stage $s^{ } ⩾ s^{}$ such that for any $q^{'} = ⟨ m^{'}, n^{'} ⟩ < n$ the block $B_{n^{'}}^{β ↾ m^{'}}$ is defined at stage $s^{ }$ and, for any $α^{'}$ with $| α^{'} | = | α |$ and $α <_{L} α^{'}$ , the block $B_{n}^{α^{'}}$ is defined at stage $s^{* }$ , too. Then, for the rightmost $B_{n}^{α}$ -node β and any $s ⩾ s^{ }$ , the subclauses (i) (by $B_{n}^{α} ↑$ ), (iii) (by assumption) and (iv) and (v) (by the choice of $s^{ }$ ) in the definition of requiring attention (a) hold at stage s. So if we let s be the least stage $⩾ s^{ }$ such that $TP ↾ q ⊏ δ_{s}$ then β requires attention via (a), at stage $s + 1$ hence becomes eligible (since by assumption and by the choice of $s^{}$ no higher priority node requires attention). Contradiction.

So, for the remainder of the argument we may fix the $B_{n}^{α}$ -node $\hat{β}$ which is permanently eligible after stage $t^{}$ . In order to get the final contradiction, we show that, eventually, there is a stage $s + 1 > t^{}$ such that $\hat{β}$ requires attention via (b) at stage $s + 1$ . Since no higher priority node requires attention after stage $t^{}$ , it follows that the block $B_{n}^{α}$ becomes defined at stage $s + 1$ contrary to choice of α and n. Now, by the choice of $t^{}$ , for any node $β^{'} ⩽ \hat{β}$ , eligibility of $β^{'}$ does not change after stage $t^{}$ . So $r (\hat{β}, s) = r (\hat{β}, t^{})$ and $F (\hat{β}, s) = F (\hat{β}, t^{})$ .

So in order to show that $\hat{β}$ eventually requires attention via (b), it suffices to show that there is a stage $s ⩾ t^{}$ such that $\begin{matrix} | ⋃_{{α^{'} : | α^{'} | = | α | and α^{'} ⩽_{L} α}} V_{α^{'}, s} | > r (\hat{β}, t^{}) + F (\hat{β}, t^{}) . \end{matrix}$ But, since $TP ↾ m ⩽_{L} α$ , this follows from the fact, that, by the assumption that $\overline{M}$ is infinite and by the True Path Lemma, $V_{TP ↾ m}$ is infinite.

This completes the proof of (B₆).

(B₇). First note that infinitely many blocks become defined. (Namely, otherwise, it follows that M is finite since any number y which is enumerated into M at stage $s + 1$ is less than or equal to the maximum of a block $B_{n}^{α}$ defined at stage s. So, by (B₆), infinitely many blocks will be defined contrary to assumption.) Now, call a node β a block node if for all $β^{'} ⊑ β$ the block associated with $β^{'}$ is defined, and let B be the set of all block nodes. Note that any initial segment of a block node is a block node again, and any priority of a block which becomes defined is a block node. Moreover, for $⟨ α, n ⟩ \neq ⟨ α^{'}, n^{'} ⟩$ , the blocks $B_{n}^{α}$ and $B_{n^{'}}^{α^{'}}$ (if defined) have different priorities. Since infinitely many blocks become defined, we may conclude that the set B of block nodes is an infinite subtree of the priority tree $T = {0, 1}^{}$ .

Now, by König’s Lemma, let p be the leftmost infinite path through B. To show that p has the required properties, first fix α on p and $n ⩾ 0$ . Then $β = p ↾ ⟨ | α |, n ⟩$ is a block node and $B_{n}^{α}$ is associated with β. So $B_{n}^{α}$ is defined. By (B₄) we may conclude that, for α to the right of the path p, the blocks $B_{n}^{α}$ ( $n ⩾ 0$ ) are defined, too. Finally, fix α to the left of p and, for a contradiction, assume that $B_{n}^{α}$ is defined for all $n ⩾ 0$ . Then, the set of priorities $β_{n}$ of the blocks $B_{n}^{α}$ , $n ⩾ 0$ , is an infinite subset of nodes in B all extending the node α. By $α <_{L} p$ and by König’s Lemma this contradicts the fact that p is the leftmost infinite path through B.

This completes the proof of (B₇) and the proof of Claim 3. □

Next we summarize relevant properties of the use functions $ψ_{α}$ and the $wtt$ -functionals $Ψ_{α}$ . Claim 4.
The partial functions* $ψ_{α}$ , $α \in {0, 1}^{}$ , are uniformly computable. Moreover, for any α, the domain of* $ψ_{α}$ (at stage s) is an initial segment of ω, and $ψ_{α}$ is strictly increasing on its domain. Finally, $ψ_{α}$ is total if and only if the blocks $B_{n}^{α}$ are defined for all $n ⩾ 0$ .
Proof.
Uniform computability follows by the effectivity of (part 1 of) the construction. The second part of the claim is immediate by definition and by (B₃). The third part is immediate by definition. □
Claim 5.
The functionals $Ψ_{α}$ are uniformly computable and, for any X, α and n such that $Ψ_{α}^{X} (n)$ is defined, $ψ_{α} (n)$ is defined and the use of $Ψ_{α}^{X} (n)$ is bounded by $ψ_{α} (n)$ . Moreover, for any α and n such that $ψ_{α} (n)$ is defined, $Ψ_{α}^{A} (n)$ is defined, too.
Proof.
The proof of the first part is straightforward. For a proof of the second part, for a contradiction assume $ψ_{α} (n) ↓$ and $Ψ_{α}^{A} (n) ↓$ . Since Ψ is a $wtt$ -functional, it follows that $Ψ_{α}^{A} (n) [s] ↑$ for almost all s. Moreover, by (22), $g (⟨ α, n ⟩, s) = 0$ for almost all s. So there is a least stage $s_{0}$ such that $ψ_{α} (n) [s_{0}] ↓$ and $Ψ_{α}^{A} (n) ↑$ and $g (⟨ α, n ⟩, s) = 0$ for all stages $s ⩾ s_{0}$ . By clause (26) in the definition of Ψ, this implies $Ψ_{α}^{A} (n) [s_{0} + 1] ↓$ . Contradiction. □

Note that the first part of Claim 5 justifies that in advance we have fixed a computable function f satisfying (21). Claim 6.
Assume that $ψ_{α}$ is total. Then the following hold.
$Ψ_{α}^{A}$ is total.

There is a number $n_{α}$ such that, for any $n ⩾ n_{α}$ , there is a stage s such that $k (⟨ α, n ⟩, s) = 1$ .

Proof.
Part (i) is immediate by the second part of Claim 5. Part (ii) follows from part (i) by (23) and (25). □

For the remaining claims we need some more notation. Let p be the unique path through T defined in (B₇). Then, for any node α such that $α ⊏ p$ or $p <_{L} α$ , all blocks $B_{n}^{α}$ are defined. So, by Claims 4 and 6, $ψ_{α}$ and $Ψ_{α}^{A}$ are total and we may fix $n_{α}$ such that ${lim}_{s \to \infty} k (⟨ α, n ⟩, s) = 1$ for all $n ⩾ n_{α}$ . It follows that, for $n ⩾ n_{α}$ , the block $B_{n}^{α}$ will eventually become truly realized. So, if we let $x_{α} = max B_{n_{α}}^{α}$ , then all numbers $x ⩾ x_{α}$ are eventually truly α-covered. Hence, for such x we may fix $n_{x}^{α}$ and $s_{x}^{α}$ such that $n_{x}^{α}$ is the unique n such that x becomes covered by $B_{n}^{α}$ and $s_{x}^{α}$ is the least stage s such that x is truly covered by $B_{n_{x}^{α}}^{α}$ at stage s. Claim 7.
Let $α ⊏ p$ and let $x ⩾ x_{α}$ . There is a node $α^{'} ⪯ α$ , a number $n ⩾ 0$ and a stage t such that the block $B_{n}^{α^{'}}$ covers x and is admissible at all stages $s ⩾ t$ (hence is never frozen).
Proof.
Note that, by (B₂), there are only finitely many blocks which may cover x. So there is a stage $t_{0}$ such that any block which covers x and becomes frozen is frozen by stage $t_{0}$ . So it suffices to show that, for almost all stages s, there is a block $B_{n}^{α^{'}}$ such that $α^{'} ⪯ α$ , $B_{n}^{α^{'}}$ covers x and $B_{n}^{α^{'}}$ is admissible at stage s. This is established by proving the following two facts. (a) There is a stage s such that x is covered by a block $B_{n}^{α^{'}}$ where $α^{'} ⪯ α$ and $B_{n}^{α^{'}}$ is admissible at stage s. (b) If x is covered by a block $B_{n}^{α^{'}}$ which is admissible at stage s then, at any stage $s^{'} > s$ , x is covered by a block $B_{n^{'}}^{α^{″}}$ such that $α^{″} ⪯ α^{'}$ and $B_{n^{'}}^{α^{″}}$ is admissible at stage $s^{'}$ .

For a proof of (a) recall that x will be truly α-covered eventually. So there is a stage s and a number n such that the block $B_{n}^{α}$ truly covers x at stage s. If $B_{n}^{α}$ is not frozen at stage s then $B_{n}^{α}$ is admissible at stage s and we are done. Otherwise, there is a stage $\hat{s} ⩽ s$ such that $B_{n}^{α}$ becomes frozen at stage $\hat{s}$ . But, by construction, this implies that there is a block $B_{n^{'}}^{α^{'}}$ such that $α^{'} ⪯ α$ , $B_{n^{'}}^{α^{'}}$ covers x and $B_{n^{'}}^{α^{'}}$ is admissible at stage $\hat{s}$ . So (a) holds in this case, too.

For a proof of (b), it suffices to consider the case of $s^{'} = s + 1$ . (Then the general case follows by induction.) So assume that $B_{n}^{α^{'}}$ covers x and is admissible at stage s. If $B_{n}^{α^{'}}$ does not become frozen at stage $s + 1$ then we are done. Otherwise, it follows by construction that there is a block $B_{n^{'}}^{α^{″}}$ such that $α^{″} ⪯ α^{'}$ , $B_{n^{'}}^{α^{″}}$ covers x and $B_{n^{'}}^{α^{″}}$ is admissible at stage $s + 1$ . This completes the proof of (b) and the proof of the claim. □
Claim 8.
Assume that $B_{n}^{α}$ becomes defined and is never frozen. Then, for the core ${\hat{B}}_{n}^{α}$ of $B_{n}^{α}$ , ${\hat{B}}_{n}^{α} \cap \overline{M} \neq \emptyset$ . Similarly, if $B_{n}^{α}$ is defined but not frozen at stage s then ${\hat{B}}_{n}^{α} [s + 1] \cap \overline{M_{s}} \neq \emptyset$ .
Proof.
We prove the first part of the claim. The second part is obtained by straightforward modifications of the proof.

We first show that a number $y \in {\hat{B}}_{n}^{α}$ can be enumerated into M only if it is an $⟨ α, n ⟩$ -coding number. For a contradiction assume that $y \in {\hat{B}}_{n}^{α}$ is enumerated into M at stage $s + 1$ and y is not an $⟨ α, n ⟩$ -coding number. Then y cannot be enumerated into M as a nonblock number according to clause (ii). (Namely, if so, $B_{n}^{α} [s + 1] ↑$ . Hence $B_{n}^{α}$ becomes defined at a stage $t + 1 > s + 1$ . But, by (B₀) this implies that $B_{n}^{α} \cap M_{s + 1} = \emptyset$ hence $y \notin B_{n}^{α}$ . The claim follows since ${\hat{B}}_{n}^{α} \subseteq B_{n}^{α}$ .) Since $B_{n}^{α}$ is never frozen, this leaves the case that $y \in {\hat{B}}_{n^{'}}^{α^{'}} [s + 1]$ for some $⟨ α^{'}, n^{'} ⟩ \neq ⟨ α, n ⟩$ and y is enumerated into M since $B^{α^{'}}$ becomes frozen at stage $s + 1$ or y is an $⟨ α^{'}, n^{'} ⟩$ -coding number. Since, by (B₀), y can’t be in a block which is not yet defined at stage $s + 1$ , it follows by $y \in {\hat{B}}_{n^{'}}^{α^{'}} [s + 1]$ and by definition of the core ${\hat{B}}_{n^{'}}^{α^{'}}$ that $y \in {\hat{B}}_{n^{'}}^{α^{'}}$ . So it suffices to show that ${\hat{B}}_{n^{'}}^{α^{'}} \cap {\hat{B}}_{n}^{α} = \emptyset$ . Since the core of a block is contained in the block this is done as follows. If $α^{'} = α$ the claim is immediate. So, by symmetry, w.l.o.g. $α^{'} ≺ α$ . But then, by the definition of ${\hat{B}}_{n}^{α}$ , $B_{n^{'}}^{α^{'}} \cap {\hat{B}}_{n}^{α} = \emptyset$ .

Now, by the above and by construction, a number $y \in {\hat{B}}_{n}^{α}$ is enumerated into M at stage $s + 1$ only if $B_{n}^{α}$ is admissible at stage s (hence $k (⟨ α, n ⟩, s) = 1$ ) and (28) or (29) holds. Moreover, at any such stage $s + 1$ at most one number $y \in {\hat{B}}_{n}^{α}$ is enumerated into M. So, by (B₀) and (B₄), it suffices to show that $\begin{matrix} (36) & | {s ⩾ s_{0} : (28) or (29) holds} | < h (⟨ α, n ⟩) + 2 \end{matrix}$ where $s_{0}$ is minimal such that $k (⟨ α, n ⟩, s_{0}) = 1$ .

Since between any two stages $s < s^{'}$ for which (29) holds there must be a stage t such that $g (⟨ α, n ⟩, t) = 0$ and $g (⟨ α, n ⟩, t + 1) = 1$ , $\begin{matrix} (37) & \begin{aligned} 2 \cdot | {s ⩾ s_{0} : (29) holds} | & ⩽ | {s ⩾ s_{0} : g (⟨ α, n ⟩, s + 1) \neq g (⟨ α, n ⟩, s)} | + 1 \\ ⩽ h (⟨ α, n ⟩) + 1 \end{aligned} \end{matrix}$ where the second inequality holds by (24). Moreover, since $Ψ_{α}^{A} (n) ↓$ by Claim 5, any stage s at which (28) holds has to be followed by a stage $t > s$ such that $Ψ_{α}^{A} (n) [t] ↑$ and $Ψ_{α}^{A} (n) [t + 1] ↓$ , where $t < s^{'}$ for the least stage $s^{'} > s$ such that (28) holds (if there is such a stage $s^{'}$ ). Since, by construction, $g (⟨ α, n ⟩, t) = 0$ and $g (⟨ α, n ⟩, s^{'}) = 1$ for any such stage t, it follows that $\begin{matrix} | {s ⩾ s_{0} : (28) holds} | ⩽ | {s ⩾ s_{0} : (29) holds} | \end{matrix}$ holds. So, by (37), (36) holds. □
Claim 9.
$A ⩽_{ibT} M$ .
Proof.
It suffices to give an effective procedure which computes $A (x)$ from $M ↾ x + 1$ for all sufficiently large x.

Let $x ⩾ x_{λ}$ and let s be the least stage such that there is a node α and a number n such that
$B_{n}^{α}$ covers x at stage s,

$B_{n}^{α}$ is admissible at stage s,

$Ψ_{α}^{A} (n) [s] ↓$ and $g (⟨ α, n ⟩, s) = 1$ , and

$M ↾ x + 1 = M_{s} ↾ x + 1$ .

Note that such a stage s exists. (Namely, by Claim 7, there is a block $B_{n}^{α}$ which covers x and which is admissible at all sufficiently large stages. So (I) and (II) hold for all sufficiently large s. Moreover, since $Ψ_{α}^{A} (n) ↓$ (by the second part of Claim 5), it follows that (III) holds for all sufficiently large s, too (by (22)). Finally, (IV) obviously holds for all sufficiently large s.) Moreover, for any stage s, we can effectively check whether, among the finitely many blocks defined at stage s, there is a block $B_{n}^{α}$ satisfying (I)–(III). So we can find the above stage s by using $M ↾ x + 1$ as an oracle.

We claim that $A (x) = A_{s} (x)$ . For a proof, first note that $B_{n}^{α}$ does not become frozen after stage s hence is admissible at all later stages. (To wit, if $B_{n}^{α}$ becomes frozen at stage $s^{'} + 1 > s$ then ${\hat{B}}_{n}^{α} [s^{'}]$ is completely enumerated into M at stage $s^{'} + 1$ whence, by the second part of Claim 8, there is a number $y \in {\hat{B}}_{n}^{α} [s^{'} + 1]$ such that $y \in M_{s^{'} + 1} ∖ M_{s^{'}}$ . Since ${\hat{B}}_{n}^{α} [s^{'} + 1]$ is contained in $B_{n}^{α}$ and $max B_{n}^{α} ⩽ x$ it follows that $y ⩽ x$ hence $M ↾ x + 1 \neq M_{s} ↾ x + 1$ contrary to (IV).) Now, for a contradiction, assume that $A (x) \neq A_{s} (x)$ . Fix $s^{'} ⩾ s$ minimal such that a number $x^{'} ⩽ x$ is enumerated into A at stage $s^{'} + 1$ . Then, assuming that $Ψ_{α}^{A} (n) [s^{'}] ↓$ and $g (⟨ α, n ⟩, s^{'}) = 1$ , $Ψ_{α}^{A} (n) [s^{'} + 1] ↑$ by construction. So, in any case, there is a least stage $s^{″}$ such that $s ⩽ s^{″} ⩽ s^{'}$ and such that (28) or (29) holds for $s^{'}$ (in place of s). It follows, by construction and by Claim 8, that there is a number $y \in {\hat{B}}_{n}^{α} [s^{'} + 1]$ which is newly enumerated into M at stage $s^{'} + 1$ . But, as observed before, this contradicts (IV). □
Claim 10.
$\overline{M}$ is infinite.
Proof.
By (B₂) and by Claim 7 there are infinitely many blocks which are never frozen. So the claim follows by Claim 8. □
Claim 11.
For any node $α ⊏ p$ there are only finitely many blocks $B_{n}^{α^{'}}$ such that $α ≺ α^{'}$ , $n ⩾ 0$ and $B_{n}^{α^{'}}$ is never frozen.
Proof.
Fix $α ⊏ p$ . By (B₂) it suffices to show that any block $B_{n}^{α^{'}}$ such that $α ≺ α^{'}$ and $x_{α} ⩽ max B_{n}^{α^{'}}$ becomes frozen eventually. So fix such a block $B_{n}^{α^{'}}$ and, for a contradiction, assume that $B_{n}^{α^{'}}$ is never frozen. Note that, by $α ⊏ p$ and $α ≺ α^{'}$ , $α^{'}$ is on p or to the right of p whence $B_{n}^{α^{'}}$ becomes defined, say, at stage $s + 1$ . By Claim 7 we may fix a stage $t ⩾ s + 1$ such that, for any of the finitely many numbers x covered by $B_{n}^{α^{'}}$ there is a block $B_{n_{x}}^{α_{x}}$ such that $α_{x} ⪯ α$ (hence $α_{x} ≺ α^{'}$ ), $B_{n_{x}}^{α_{x}}$ covers x and $B_{n_{x}}^{α_{x}}$ is admissible at all stages $t^{'} ⩾ t$ . So $B_{n}^{α^{'}}$ is freezable at all stages $t^{'} ⩾ t$ . Since there are only finitely many blocks $B_{\hat{n}}^{\hat{α}}$ such that $⟨ | \hat{α} |, \hat{n} ⟩ < ⟨ | α^{'} |, n ⟩$ or $⟨ | \hat{α} |, \hat{n} ⟩ = ⟨ | α^{'} |, n ⟩$ and $α^{'} <_{L} \hat{α}$ , it follows that $B_{n}^{α^{'}}$ becomes frozen eventually. Contradiction. □
Claim 12.
The true path $TP$ coincides with the path p.
Proof.
Claim 10 and (B₆) immediately imply that $p ⩽_{L} TP$ . For a proof of the converse, i.e., $TP ⩽_{L} p$ , it suffices to show that, for any given node $α^{'} <_{L} TP$ , only finitely many $α^{'}$ -blocks become defined. Now, by Claim 10 and by the second part of the Infinity Lemma (Claim 1), there are only finitely many stages s such that $δ_{s} <_{L} α^{'}$ or $α^{'} ⊏ δ_{s}$ . So only finitely many $α^{'}$ -nodes can become eligible, hence only finitely many $α^{'}$ -blocks can be defined. □
Claim 13.
For any α on $TP$ , $\overline{M} \subseteq^{} {\hat{V}}_{α}$ .
Proof.
Fix $α ⊏ TP$ . Since (by (B₁) and (19)) $\overline{M} \cap B_{n}^{α^{'}} \subseteq {\hat{V}}_{α}$ for any block $B_{n}^{α^{'}}$ such $α^{'} ⪯ α$ , it suffices to show $\begin{matrix} (38) & \overline{M} \subseteq^{} ⋃_{{(α^{'}, n) : α^{'} ⪯ α, n ⩾ 0 and B_{n}^{α^{'}} ↓}} B_{n}^{α^{'}} . \end{matrix}$ For a proof of (38), first recall that (by Claim 12) the true path $TP$ coincides with the path p. So, by Claim 11, we may let B be the finite union of the blocks $B_{n}^{α^{'}}$ such that $α ≺ α^{'}$ , $n ⩾ 0$ and $B_{n}^{α^{'}}$ is never frozen. Now, call a number y a block number if y is element of some block, and call a block number y an $α^{'}$ -number if $α^{'}$ is ≺-minimal such that y is in an $α^{'}$ -block. (Note that any number is element of at most finitely many blocks. So $α^{'}$ is well-defined.) Then it suffices to show that any number $y \in \overline{M}$ which is not an $α^{'}$ -number for some $α^{'} ⪯ α$ is an element of B. So fix such y. We first observe that y is a block number. Namely, since there are infinitely many blocks, it follows by (B₂) that there is a stage s such that y is less than the maximum of a block defined at stage s. So if y is not a block number then y is enumerated into M at stage $s + 1$ for the least such s contrary to choice of y. So we may fix $α^{'}$ and the corresponding unique n such that y is an $α^{'}$ -number and $y \in B_{n}^{α^{'}}$ . It suffices to show that $B_{n}^{α^{'}}$ is contained in B. For a contradiction, assume that this is not the case. Since, by the choice of y, $α ⪯ α^{'}$ , this implies that there is a stage $s + 1$ at which $B_{n}^{α^{'}}$ becomes frozen. So ${\hat{B}}_{n}^{α} [s + 1] \subseteq M_{s + 1}$ by construction. But since y is an $α^{'}$ -number, y is in the core ${\hat{B}}_{n}^{α^{'}}$ of $B_{n}^{α^{'}}$ . Since, obviously, ${\hat{B}}_{n}^{α^{'}} \subseteq {\hat{B}}_{n}^{α^{'}} [s + 1]$ , it follows that $y \in M$ contrary to assumption.

This completes the proof of Claim 13. □
Claim 14.
M is maximal.
Proof.
By the effectivity of the construction and by Claims 10 and 13, the hypotheses of the Maximal Set Lemma (Claim 2) are satisfied. □

By Claims 9 and 14, M has the required properties. This completes the proof the Theorem 4.3. □

In order to complete the proof of the Characterization Theorem it remains to prove Theorem 4.4. For this sake, we use the following characterization of the dense simple sets given in Robinson [33]: a c.e. set D is dense simple if and only if D is coinfinite and, for every strong array ${F_{n}}_{n \in ω}$ of pairwise disjoint sets, there is a number m such that $\begin{matrix} (39) & \forall n ⩾ m (| F_{n} \cap \overline{D} | < n) . \end{matrix}$ Proof of Theorem 4.4.
Fix c.e. sets A and D such that $A ⩽_{wtt} D$ and D is dense simple. It suffices to define computable functions g, h and k witnessing that A is eventually uniformly $wtt$ -array computable.

Fix a $wtt$ -functional Γ such that $A = Γ^{D}$ and fix a computable function γ such that the use of $Γ^{D}$ is bounded by γ where w.l.o.g. γ is strictly increasing. Moreover, fix computable enumerations ${A_{s}}_{s \in ω}$ , ${D_{s}}_{s \in ω}$ and ${Γ_{s}}_{s \in ω}$ of A, D and Γ, respectively, such that the length of agreement function $\begin{matrix} l (s) = max {y : A_{s} ↾ y = Γ_{s}^{D_{s}} ↾ y} \end{matrix}$ is strictly increasing in s. (Such enumerations can be obtained by speeding up any given computable enumerations of A, D and Γ.) Note that this ensures $\begin{matrix} (40) & (x < l (s) & A_{s + 1} (x) \neq A_{s} (x)) \Rightarrow D_{s + 1} ↾ γ (x) \neq D_{s} ↾ γ (x) \end{matrix}$ for all numbers x and stages s.

Now the computable functions $g, k : ω^{2} \to {0, 1}$ and $h : ω \to ω$ are defined as follows. Define g by letting $\begin{matrix} g (⟨ e, y ⟩, s) = \{\begin{array}{ll} 1 & if {\hat{Φ}}_{e, s}^{A_{s}} (y) ↓, \\ 0 & otherwise, \end{array} \end{matrix}$ and let h be the order defined by $\begin{matrix} h (x) = {(x + 1)}^{2} . \end{matrix}$ Finally, for the definition of k, define the auxiliary uniformly partial computable functions ${\tilde{φ}}_{e}$ by ${\tilde{φ}}_{e} (y) = {lim}_{s \to \infty} {\tilde{φ}}_{e, s} (y)$ where $\begin{matrix} {\tilde{φ}}_{e, s} (y) = \{\begin{array}{ll} y + max {{\hat{φ}}_{e, s} (y^{'}) : y^{'} ⩽ y} & if \forall y^{'} ⩽ y ({\hat{φ}}_{e, s} (y^{'}) ↓), \\ ↑ & otherwise . \end{array} \end{matrix}$ Note that ${\tilde{φ}}_{e}$ is defined on an initial segment of ω, ${\tilde{φ}}_{e}$ is strictly increasing on its domain, ${\tilde{φ}}_{e}$ majorizes ${\hat{φ}}_{e}$ on its domain, and ${\tilde{φ}}_{e}$ is total if ${\hat{φ}}_{e}$ is total. So, for total ${\hat{Φ}}_{e}^{A}$ , ${\tilde{φ}}_{e}$ is total, strictly increasing and bounds the use of ${\hat{Φ}}_{e}^{A}$ . Now, the 0-1-valued function k is defined by letting $k (⟨ e, y ⟩, s) = 1$ iff $\begin{matrix} (41) & {\tilde{φ}}_{e, s} (y) ↓ & l (s) > {\tilde{φ}}_{e} (y) & | \overline{D_{s}} ↾ γ ({\tilde{φ}}_{e, s} (y)) | < \frac{{(⟨ e, y ⟩ + 1)}^{2}}{2} . \end{matrix}$

Obviously, the functions g, h and k are computable, and h is an order. Moreover, g is the canonical approximation of $A^{†}$ whence (6) holds. So it only remains to show that the functions g, h and k satisfy conditions (7)–(9) in Definition 4.1, too.

For a proof of (7) it suffices to note that k is 0-1-valued and that the three clauses in equation (41) that characterize the stages s such that $k (⟨ e, y ⟩, s) = 1$ persist if we replace s by a stage $t ⩾ s$ . (For the second clause, recall that the length function $l (s)$ is nondecreasing in s.)

For a proof of (8) fix $x = ⟨ e, y ⟩$ and s such that $k (x, s) = 1$ . By the definition of g and h, it suffices to show that $\begin{matrix} (42) & | {t ⩾ s : {\hat{Φ}}_{e, t}^{A_{t}} (y) ↓ & {\hat{Φ}}_{e, t + 1}^{A_{t + 1}} (y) ↑} | < \frac{{(⟨ e, y ⟩ + 1)}^{2}}{2} . \end{matrix}$ (Namely, (42) guarantees that $g (x, t)$ switches from 1 to 0 less than ${(x + 1)}^{2} \cdot 2^{- 1}$ times after stage s. So, since g is 0–1-valued, g may change on x after stage s at most $2 ({(x + 1)}^{2} \cdot 2^{- 1})$ ( $= h (x)$ ) times.)

So fix t as in (42). Then $A_{t + 1} ↾ {\hat{φ}}_{e} (y) \neq A_{t} ↾ {\hat{φ}}_{e} (y)$ . Note that, by $k (x, s) = 1$ , (41) holds. So, by ${\hat{φ}}_{e} (y) ⩽ {\tilde{φ}}_{e} (y)$ (if defined), by (40) and by the first two clauses in (41), there is a number $⩽ γ ({\tilde{φ}}_{e, s} (y))$ that is enumerated into D at stage $t + 1$ . But, by the third clause in (41), the latter can happen for at most $\frac{{(⟨ e, y ⟩ + 1)}^{2}}{2} - 1$ stages $t ⩾ s$ . So (8) holds.

Finally, for a proof of (9), fix e such that ${\hat{Φ}}_{e}^{A}$ is total. Then ${\tilde{φ}}_{e}$ is total, computable and strictly increasing (and so is γ). So we can define a computable partition of ω into nonempty intervals ${F_{n}}_{n \in ω}$ by letting $F_{0} = [0, γ ({\tilde{φ}}_{e} (0)))$ and $F_{n + 1} = [γ ({\tilde{φ}}_{e} (n)), γ ({\tilde{φ}}_{e} (n + 1)))$ . Now, since D is dense simple, it follows, by Robinson’s characterization of the dense simple sets given above, that there is a number m such that (39) holds. So there is a constant c such that $\begin{matrix} | \overline{D} ↾ γ ({\tilde{φ}}_{e} (n)) | = | \overline{D} ↾ 1 + max F_{n} | = \sum_{n^{'} ⩽ n} | \overline{D} \cap F_{n^{'}} | ⩽ (\sum_{n^{'} ⩽ n} n^{'}) + c = \frac{n (n + 1)}{2} + c \end{matrix}$ for all $n ⩾ 0$ . Since, by $y ⩽ ⟨ e, y ⟩$ , $y (y + 1) \cdot 2^{- 1} + c < {(⟨ e, y ⟩ + 1)}^{2} \cdot 2^{- 1}$ for all sufficiently large y, it follows that, for almost all y, there is a stage $s_{y}$ such that (41) holds for all stages $s ⩾ s_{y}$ . So, by the definition of $k (⟨ e, y ⟩, s)$ , ${lim}_{s \to \infty} k (⟨ e, y ⟩, s) = 1$ for all sufficiently large numbers y, whence (9) holds.

This completes the proof of Theorem 4.4. □

5. Closure properties of EUwttAC

In this section, we prove that EUwttAC is closed downwards under $⩽_{wtt}$ and closed under join. The former holds by the following slightly more general result where we do not require that the sets are computably enumerable.

Lemma 5.1.
Let A and B be any (not necessarily c.e.) sets such that $A ⩽_{wtt} B$ and such that B is e.u.wtt-a.c. Then A is e.u.wtt-a.c., too.
Proof.
Fix computable functions g, k and h such that B is e.u.wtt-a.c. via g, k and h, and, by clause 1. of Lemma 3.4, fix a computable function f such that ${\hat{Φ}}_{e}^{A} = {\hat{Φ}}_{f (e)}^{B}$ for $e ⩾ 0$ . Then A is e.u.wtt-a.c. via $\tilde{g}$ , $\tilde{k}$ and $\tilde{h}$ where $\tilde{g} (⟨ e, x ⟩, s) = g (⟨ f (e), x ⟩, s)$ , $\tilde{k} (⟨ e, x ⟩, s) = k (⟨ f (e), x ⟩, s)$ and $\tilde{h} (⟨ e, x ⟩) = h (⟨ f (e), x ⟩)$ (for $e, x, s \in ω$ ). □

For the closure under the join operation (and for some later applications), we need the following technical lemma.
Lemma 5.2.
Let $A_{0}$ and $A_{1}$ be c.e. sets. There exist strictly increasing computable functions $f_{0}, f_{1} : ω \to ω$ such that, for all $e, x \in ω$ , $\begin{aligned} (43) & {\hat{Φ}}_{e}^{A_{0} \oplus A_{1}} (x) ↓ \Leftrightarrow ({\hat{Φ}}_{f_{0} (e)}^{A_{0}} (x) ↓ & {\hat{Φ}}_{f_{1} (e)}^{A_{1}} (x) ↓) \end{aligned}$ and $\begin{aligned} (44) & {\hat{Φ}}_{e}^{A_{0} \oplus A_{1}} (x) ↓ \Rightarrow \exists i ⩽ 1 ({\hat{Φ}}_{f_{i} (e)}^{A_{i}} (x) = {\hat{Φ}}_{e}^{A_{0} \oplus A_{1}} (x)) . \end{aligned}$
Proof.
Given computable enumerations ${A_{i, s}}_{s \in ω}$ of $A_{i}$ ( $i ⩽ 1$ ), for each $i ⩽ 1$ and $e ⩾ 0$ define the functional $Ψ_{i, e}$ by letting, for any set Z and any number x, $\begin{array}{r} Ψ_{i, e}^{Z} (x) ↓ \Leftrightarrow \exists s ({\hat{Φ}}_{e}^{A_{0} \oplus A_{1}} (x) [s] ↓ & A_{i, s} ↾ {\hat{φ}}_{e} (x) + 1 = Z ↾ {\hat{φ}}_{e} (x) + 1) \end{array}$ and by setting $\begin{array}{r} Ψ_{i, e}^{Z} (x) = {\hat{Φ}}_{e}^{A_{0} \oplus A_{1}} (x) [s] \end{array}$ for the least such s if $Ψ_{i, e}^{Z} (x)$ is defined. Note that the use of $Ψ_{i, e}^{Z} (x)$ is bounded by ${\hat{φ}}_{e} (x)$ , and, for $i ⩽ 1$ , ${Ψ_{i, e}}_{e \in ω}$ is a uniformly computable sequence of $wtt$ -functionals. So, by clause 1. of Lemma 3.3, there is a strictly increasing computable function $f_{i}$ such that $Ψ_{i, e} = {\hat{Φ}}_{f_{i} (e)}$ . We claim that $f_{0}$ and $f_{1}$ are as desired.

Note that ${\hat{Φ}}_{e}^{A_{0} \oplus A_{1}} (x) ↓$ trivially implies that ${\hat{Φ}}_{f_{0} (e)}^{A_{0}} (x)$ and ${\hat{Φ}}_{f_{1} (e)}^{A_{1}} (x)$ are defined. So, assuming that ${\hat{Φ}}_{f_{0} (e)}^{A_{0}} (x)$ and ${\hat{Φ}}_{f_{1} (e)}^{A_{1}} (x)$ are defined, it suffices to show that ${\hat{Φ}}_{f_{i} (e)}^{A_{i}} (x) = {\hat{Φ}}_{e}^{A_{0} \oplus A_{1}} (x)$ for some $i ⩽ 1$ . By assumption, for $i ⩽ 1$ fix the least stage $s_{i}$ such that ${\hat{Φ}}_{e}^{A_{0} \oplus A_{1}} (x) [s_{i}] ↓$ and $A_{i, s_{i}} ↾ {\hat{φ}}_{e} (x) + 1 = A_{i} ↾ {\hat{φ}}_{e} (x) + 1$ holds. Then, for $s = max {s_{0}, s_{1}}$ , it follows by the use-principle that ${\hat{Φ}}_{e}^{A_{0} \oplus A_{1}} (x) = {\hat{Φ}}_{e}^{A_{0} \oplus A_{1}} (x) [s]$ . So, for the least $i ⩽ 1$ such that $s = s_{i}$ , we may deduce that ${\hat{Φ}}_{f_{i} (e)}^{A_{i}} (x) = {\hat{Φ}}_{e}^{A_{0} \oplus A_{1}} (x)$ . □

By applying Lemma 5.2, now we can prove that EUwttAC is closed under join.
Lemma 5.3.
Let $A_{0}$ and $A_{1}$ be c.e. e.u.wtt-a.c. sets. Then $A_{0} \oplus A_{1}$ is e.u.wtt-a.c., too.
Proof.
Fix computable functions $g_{i}$ , $k_{i}$ and $h_{i}$ such that $A_{i}$ is e.u.wtt-a.c. via $g_{i}$ , $k_{i}$ and $h_{i}$ ( $i ⩽ 1$ ). By Lemma 5.2, fix computable functions $f_{i} : ω \to ω$ ( $i ⩽ 1$ ) such that (43) holds. Define the functions g, k and h by letting $\begin{array}{c} g (⟨ e, x ⟩, s) = g_{0} (⟨ f_{0} (e), x ⟩, s) \cdot g_{1} (⟨ f_{1} (e), x ⟩, s), \\ k (⟨ e, x ⟩, s) = k_{0} (⟨ f_{0} (e), x ⟩, s) \cdot k_{1} (⟨ f_{1} (e), x ⟩, s), and \\ h (⟨ e, x ⟩) = h_{0} (⟨ f_{0} (e), x ⟩) + h_{1} (⟨ f_{1} (e), x ⟩) \end{array}$ (for all $e, x, s \in ω$ ). We claim that $A_{0} \oplus A_{1}$ is e.u.wtt-a.c. via g, k and h. Obviously, the functions g, k and h are computable. So it suffices to show (6) – (9) for $A = A_{0} \oplus A_{1}$ . Now, by the choice of $g_{i}$ and $k_{i}$ , (6) is immediate by (43) and (7) is immediate. For a proof of (8), note that, for any $e, x, s \in ω$ , $g (⟨ e, x ⟩, s + 1) \neq g (⟨ e, x ⟩, s)$ implies that $g_{0} (⟨ f_{0} (e), x ⟩, s + 1) \neq g_{0} (⟨ f_{0} (e), x ⟩, s)$ or $g_{1} (⟨ f_{1} (e), x ⟩, s + 1) \neq g_{1} (⟨ f_{1} (e), x ⟩, s)$ and $k (⟨ e, x ⟩, s) = 1$ implies $k_{0} (⟨ f_{0} (e), x ⟩, s) = k_{1} (⟨ f_{1} (e), x ⟩, s) = 1$ . So, by the choice of $g_{i}$ , $k_{i}$ and $h_{i}$ , $k (⟨ e, x ⟩, s) = 1$ implies $\begin{aligned} | {t ⩾ s : g (⟨ e, x ⟩, t + 1) \neq g (⟨ e, x ⟩, t)} | \\ ⩽ | {t ⩾ s : g_{0} (⟨ f_{0} (e), x ⟩, t + 1) \neq g_{0} (⟨ f_{0} (e), x ⟩, t)} | \\ + | {t ⩾ s : g_{1} (⟨ f_{1} (e), x ⟩, t + 1) \neq g_{1} (⟨ f_{1} (e), x ⟩, t)} | \\ ⩽ h_{0} (⟨ f_{0} (e), x ⟩) + h_{1} (⟨ f_{1} (e), x ⟩) \\ = h (⟨ e, x ⟩) . \end{aligned}$ Finally, for a proof of (9), fix e such that ${\hat{Φ}}_{e}^{A_{0} \oplus A_{1}}$ is total. Then, by (43), ${\hat{Φ}}_{f_{0} (e)}^{A_{0}}$ and ${\hat{Φ}}_{f_{1} (e)}^{A_{1}}$ are total, too. So, by the choice of $k_{0}$ and $k_{1}$ , there is a number $x_{0}$ such that ${lim}_{s \to \infty} k_{0} (⟨ f_{0} (e), x ⟩, s) = 1$ and ${lim}_{s \to \infty} k_{1} (⟨ f_{1} (e), x ⟩, s) = 1$ for all $x ⩾ x_{0}$ . By the definition of k, this implies that ${lim}_{s \to \infty} k (⟨ e, x ⟩, s) = 1$ $x ⩾ x_{0}$ . □

The above closure properties of EUwttAC show that the $wtt$ -degrees of the c.e. e.u.wtt-a.c. sets are an ideal in the upper semilattice of the c.e. $wtt$ -degrees. Moreover, by the Characterization Theorem, this ideal intersects all high c.e. Turing degrees.
Theorem 5.4.
The class ${EUwttAC}_{wtt}$ of the $wtt$ -degrees of c.e. e.u.wtt-a.c. sets is an ideal in the upper semilattice of the c.e. $wtt$ -degrees. Moreover, for any high c.e. Turing degree a , there is a c.e. set $A \in a$ such that ${deg}_{wtt} (A) \in {EUwttAC}_{wtt}$ .
Proof.
The first part of the theorem is immediate by Lemmas 5.1 and 5.3. For the second part of the theorem, note that, by Theorem 4.2, any maximal set is e.u.wtt-a.c. So the claim follows by Martin’s Theorem [11] which asserts that any high c.e. Turing degree contains a maximal set. □

In the remainder of the paper we relate the eventually uniformly $wtt$ -array computable sets to the $wtt$ -superlow sets and to the array computable sets. As we will show this provides strict lower bounds and upper bounds, respectively. We start with the $wtt$ -superlow sets which are of great interest in themselves.
6. $Wtt$ -Superlow sets

In this section, we will study notions of lowness for the bounded jump, i.e., we will look at the $wtt$ -superlow (i.e., bounded low) sets introduced in the introduction already. After showing that $wtt$ -superlow sets are eventually uniformly $wtt$ -array computable (Section 6.1), we have a closer look at this class of sets. So we observe that the $wtt$ -degrees of the c.e. $wtt$ -superlow sets form an ideal, and we give an analog of the equivalence of superlowness and jump traceability by introducing a corresponding notion of $wtt$ -jump traceability (Section 6.2). We use this equivalence in order to give a strict hierarchy of the $wtt$ -superlow sets depending on the order of the mind changes needed in computable approximations of the bounded jump (Section 6.3). Finally, we look at the lowest level of this hierarchy, the class of the strongly $wtt$ -superlow sets, and we show that there are Turing complete sets in this class (Section 6.4).

6.1. $Wtt$ -Superlow sets are eventually uniformly $wtt$ -array computable

We recall the following definition from the introduction.

Definition 6.1.
A (not necessarily c.e.) set A is $wtt$ -superlow if $A^{†} ⩽_{wtt} \emptyset^{'}$ .

In order to show that any (not necessarily c.e.) $wtt$ -superlow set is eventually uniformly $wtt$ -array computable, we characterize the $wtt$ -superlow sets in terms of approximability of their bounded jumps. We first recall the relevant notions needed. A total function $f : ω \to ω$ is called h-computably approximable via g or h-c.a. via g for short, if $g : ω^{2} \to ω$ is a computable function and $h : ω \to ω$ is a computable order such that $f (x) = {lim}_{s \to \infty} g (x, s)$ and $| {s : g (x, s + 1) \neq g (x, s)} | ⩽ h (x)$ (for any x), i.e., g is a computable approximation of f where the number of mind changes of g is computably bounded by h; f is called h-computably approximable (h-c.a.) if f is h-computably approximable (h-c-a.) via some computable function $g : ω^{2} \to ω$ ; and f is ω-computably approximable or ω-c.a. for short if f is h-c.a. for some computable order h. (Note that if the range of f is bounded, say, $f (x) ⩽ k$ for all x, then we may assume that the approximating function g is also bounded by k. So if A is an ω-c.a. set and g approximates A in the limit then in the following we tacitly assume that g is 0-1 valued.)
Lemma 6.2.
Let A be any (not necessarily c.e.) set. The following are equivalent.
A is $wtt$ -superlow, i.e., $A^{†} ⩽_{wtt} \emptyset^{'}$ .

$A^{†} ⩽_{tt} \emptyset^{'}$ .

$A^{†}$ is ω-c.a.

There exists a computable order h such that any set B which is bounded-c.e. in A is h-c.a.

Proof.
The equivalence of the first three clauses 1., 2. and 3. is immediate by the general fact that, for any set B, $B ⩽_{wtt} \emptyset^{'}$ iff $B ⩽_{tt} \emptyset^{'}$ iff B is ω-c.a., see, e.g., [31, III.8.14] and [14, Corollary 2.6.2]. Moreover, the implication “4. ⇒ 3.” is immediate, too, since $A^{†}$ is bounded-c.e. in A. This leaves the implication “3. ⇒ 4.”.

So suppose that $A^{†}$ is ω-c.a. Fix a computable function $g : ω^{2} \to {0, 1}$ and a computable order $\hat{h}$ such that $A^{†} (x) = {lim}_{s \to \infty} g (x, s)$ and $| {s : g (x, s + 1) \neq g (x, s)} | ⩽ \hat{h} (x)$ hold for all x. We claim that any bounded A-c.e. set is h-c.a. for the order $h (x) = \hat{h} (⟨ x, x ⟩)$ . So let B be a bounded A-c.e. set. Fix $e \in ω$ such that $B = dom ({\hat{Φ}}_{e}^{A})$ . Then $x \in B$ iff $⟨ e, x ⟩ \in A^{†}$ . Define the computable function $\tilde{g} : ω^{2} \to {0, 1}$ by letting $\begin{array}{r} \tilde{g} (x, s) = \{\begin{array}{ll} B (x) & if x < e, \\ g (⟨ e, x ⟩, s) & otherwise . \end{array} \end{array}$ By definition, $B (x) = {lim}_{s \to \infty} \tilde{g} (x, s)$ holds for all x. So it suffices to show that the number of mind changes of $\tilde{g} (x, \cdot)$ is bounded by $h (x)$ for any x. The latter clearly holds if $x < e$ . On the other hand, for $x ⩾ e$ we may argue that $\begin{aligned} | {s : \tilde{g} (x, s + 1) \neq \tilde{g} (x, s)} | = | {s : g (⟨ e, x ⟩, s + 1) \neq g (⟨ e, x ⟩, s)} | ⩽ \hat{h} (⟨ e, x ⟩) ⩽ h (x), \end{aligned}$ where the latter inequality holds since $\hat{h}$ is a computable order. □
Corollary 6.3.
Any (not necessarily c.e.) $wtt$ -superlow set is eventually uniformly $wtt$ -array computable.
Proof.
Assume that A is $wtt$ -superlow. Then, by Lemma 6.2, $A^{†}$ is ω-c.a. So we may fix a computable order h and a computable function g such that $A^{†}$ is h-c.a. via g. It follows that A is eventually uniformly $wtt$ -array computable via g, k and h where we may let k be the constant function $k (x, s) = 1$ . □

From Lemma 6.2 we can further deduce that the class of the $wtt$ -superlow sets is closed downwards under $wtt$ -reducibility and that the class of the c.e. $wtt$ -superlow sets is closed under join. So the class of the $wtt$ -superlow c.e. $wtt$ -degrees is an ideal in EUwttAC. Corollary 6.4.

Let A and B be any (not necessarily c.e.) sets such that $A ⩽_{wtt} B$ and B is $wtt$ -superlow. Then A is $wtt$ -superlow, too.

Let $A_{0}$ and $A_{1}$ be $wtt$ -superlow c.e. sets. Then $A_{0} \oplus A_{1}$ is $wtt$ -superlow, too.

Proof.
(a). By $wtt$ -superlowness of B, $B^{†} ⩽_{wtt} \emptyset^{'}$ while, by $A ⩽_{wtt} B$ and by part 5. of Lemma 3.4, $A^{†} ⩽_{wtt} B^{†}$ . Hence $A^{†} ⩽_{wtt} \emptyset^{'}$ . By Lemma 6.2 this implies that A is $wtt$ -superlow.

(b). By Lemma 5.2 fix computable functions $f_{i}$ ( $i ⩽ 1$ ) satisfying (43). Then, for all $e, x \in ω$ , we have $\begin{array}{r} ⟨ e, x ⟩ \in {(A_{0} \oplus A_{1})}^{†} \Leftrightarrow \forall i ⩽ 1 (2 ⟨ f_{i} (e), x ⟩ + i \in A_{0}^{†} \oplus A_{1}^{†}) . \end{array}$ Hence, ${(A_{0} \oplus A_{1})}^{†} ⩽_{tt} A_{0}^{†} \oplus A_{1}^{†} ⩽_{tt} \emptyset^{'}$ . □

6.2. $Wtt$ -Superlowness and $wtt$ -jump traceability

For computably enumerable sets the equivalent characterizations of $wtt$ -superlowness given in Lemma 6.2 can be expanded. In particular, a computably enumerable set A is $wtt$ -superlow iff A is $wtt$ -jump traceable where the latter is defined as follows.

Definition 6.5.
A set A is h- $wtt$ -jump traceable via ${V_{e}}_{e \in ω}$ if h is a computable order and ${V_{e}}_{e \in ω}$ is a uniformly c.e. sequence of finite sets such that, for all $e ⩾ 0$ , $| V_{e} | ⩽ h (e)$ and ${\hat{J}}^{A} (e) ↓$ implies ${\hat{J}}^{A} (e) \in V_{e}$ ; A is h- $wtt$ -jump traceable if there exists a uniformly c.e. sequence ${V_{e}}_{e \in ω}$ such that A is h- $wtt$ -jump traceable via ${V_{e}}_{e \in ω}$ ; and A is $wtt$ -jump traceable if there exists a computable order h such that A is h- $wtt$ -jump traceable. If A h- $wtt$ -jump traceable via ${V_{e}}_{e \in ω}$ then we say that ${V_{e}}_{e \in ω}$ is an h-trace for ${\hat{J}}^{A}$ .
Theorem 6.6.
For a c.e. set A, A is $wtt$ -superlow if and only if A is $wtt$ -jump traceable.

By Lemma 6.2, Theorem 6.6 is immediate by the following two lemmas. In these lemmas, in addition we analyze how the relevant orders are affected if we go from one notion to the other. (This analysis will be used below in the proof of Lemma 6.12). Lemma 6.7.
Let A be a c.e. set, let h be a computable order, and suppose that $A^{†}$ is h-c.a. Then A is $\hat{h}$ - $wtt$ -jump traceable for the computable order $\hat{h} (x) = ⌈ \frac{h (⟨ x, x ⟩)}{2} ⌉$
Proof.
We adapt some of the techniques from [29, Theorem 4.1] where it is shown that the c.e. superlow sets coincide with the c.e. jump traceable sets.

Fix a computable function $g : ω^{2} \to {0, 1}$ such that $A^{†}$ is h-c.a. via g and fix a computable enumeration ${A_{s}}_{s \in ω}$ of A. We show that there exists a number $d \in ω$ and a uniformly c.e. sequence ${V_{e}}_{e \in ω}$ such that A is $h^{'}$ - $wtt$ -jump traceable via ${V_{e}}_{e \in ω}$ for the computable order $h^{'} (x) = ⌈ \frac{h (⟨ d, x ⟩)}{2} ⌉ + 1$ . Then, obviously, A is $\hat{h}$ - $wtt$ -jump traceable via ${{\hat{V}}_{e}}_{e \in ω}$ via the uniformly c.e. sequence $\begin{array}{r} {\hat{V}}_{e} = \{\begin{array}{ll} \emptyset & if e < d and {\hat{J}}^{A} (e) ↑ \\ {{\hat{J}}^{A} (e)} & if e < d and {\hat{J}}^{A} (e) ↓ \\ V_{e} & otherwise. \end{array} \end{array}$

Now, along with ${V_{e}}_{e \in ω}$ , we define an auxiliary $wtt$ -functional Ψ in stages s where, by the Recursion Theorem, we may assume that in advance we know an index $d \in ω$ such that $Ψ = {\hat{Φ}}_{d}$ holds (the intuition behind $Ψ^{A} (x)$ is that its computation is a delayed version of the computation of ${\hat{J}}^{A} (x)$ ). In more detail, we define a uniformly computable sequence of $wtt$ -functionals ${{\tilde{Ψ}}_{e}}_{e \in ω}$ (intuitively, for any $e \in ω$ , we have a version for the definition of Ψ, where e is a guess for an index of Ψ). Then, in the construction, we make ${\tilde{Ψ}}_{e}^{A} (x)$ defined (undefined) at a certain stage $s + 1$ only if $g (⟨ e, x ⟩, s)$ correctly approximates the status of definedness of ${\tilde{Ψ}}_{e}^{A} (x) [s]$ . Then, by the Recursion Theorem, there exists a number d such that ${\tilde{Ψ}}_{d} = {\hat{Φ}}_{d}$ . So $Ψ = {\tilde{Ψ}}_{d}$ is as desired. Now the definition of $V_{e}$ and $Ψ^{A} (e)$ for given $e \in ω$ is as follows.
Stage 0. Let $V_{e, 0} = \emptyset$ and $Ψ^{A} (e) [0] ↑$ .

Stage $s + 1$ . Let $V_{e, s}$ and $Ψ^{A} (e) [s]$ be given. If ${\hat{φ}}_{e} (e) [s] ↑$ or if $A_{s + 1} ↾ {\hat{φ}}_{e} (e) + 1 \neq A_{s} ↾ {\hat{φ}}_{e} (e) + 1$ holds then let $Ψ^{A} (e) [s + 1] ↑$ and $V_{e, s + 1} = V_{e, s}$ . Otherwise, distinguish between the following cases.
If $Ψ^{A} (e) [s] ↑$ , ${\hat{J}}^{A} (e) [s] ↓$ and $g (⟨ d, e ⟩, s) = 0$ then let $Ψ^{A} (e) [s + 1] ↓ = {\hat{J}}^{A} (e) [s]$ with use ${\hat{φ}}_{e} (e)$ and let $V_{e, s + 1} = V_{e, s}$ .

If $Ψ^{A} (e) [s] ↓$ and $g (⟨ d, e ⟩, s) = 1$ then let $Ψ^{A} (e) [s + 1] = Ψ^{A} (e) [s]$ and $V_{e, s + 1} = V_{e, s} \cup {Ψ^{A} (e) [s]}$ .
If neither of the previous cases applies then let $Ψ^{A} (e) [s + 1] = Ψ^{A} (e) [s]$ and $V_{e, s + 1} = V_{e, s}$ .

By the effectivity of the construction, ${V_{e}}_{e \in ω}$ is uniformly c.e. and Ψ is a $wtt$ -functional. We claim that ${V_{e}}_{e \in ω}$ and the number d obtained from the Recursion Theorem are as desired. We first prove that ${V_{e}}_{e \in ω}$ is a trace for ${\hat{J}}^{A}$ . So let $e \in ω$ be given such that ${\hat{J}}^{A} (e) ↓$ . Then we may fix the least stage s such that ${\hat{J}}^{A} (e) [s] ↓$ and $A ↾ {\hat{φ}}_{e} (e) + 1 = A_{s} ↾ {\hat{φ}}_{e} (e) + 1$ . Since ${lim}_{s \to \infty} g (⟨ d, e ⟩, s) = dom (Ψ^{A}) (e)$ , it follows that there exists a stage $s_{0}$ such that (i) applies at stage $s_{0} + 1$ . So $Ψ^{A} (e) [s_{0} + 1] ↓ = {\hat{J}}^{A} (e)$ holds by construction; hence, for the least stage $s_{1} > s_{0}$ such that (ii) applies at stage $s_{1} + 1$ , it follows that ${\hat{J}}^{A} (e) \in V_{e, s_{1} + 1}$ ; hence, ${\hat{J}}^{A} (e) \in V_{e}$ .

It remains to show that ${V_{e}}_{e \in ω}$ is an $h^{'}$ -trace. For that, we observe that, by construction, a number x may be enumerated into $V_{e}$ at stage $s + 1$ only if $x = Ψ^{A} (e) [s] ↓$ . So if $s_{0} < s_{1}$ are stages such that $Ψ^{A} (e) [s_{0}] ↓ \neq Ψ^{A} (e) [s_{1}] ↓$ and such that $Ψ^{A} (e) [s_{i}]$ enter $V_{e}$ at stage $s_{i} + 1$ ( $i ⩽ 1$ ) then, by construction, there must be a stage s such that $s \in (s_{0}, s_{1})$ and such that $Ψ^{A} (e) [s + 1] ↑$ . Thus, by (i), there exists a stage $t \in (s, s_{1})$ such that $Ψ^{A} (e) [t + 1] ↓$ . So, by (ii), we can argue that each new element that enters $V_{e}$ corresponds to a change of $g (⟨ d, e ⟩, \cdot)$ from 1 to 0 and back to 1. Since there are at most $⌈ \frac{h (⟨ d, e ⟩)}{2} ⌉$ many such stages, this completes the proof. □
Lemma 6.8.
Let A be a c.e. set. There exists a strictly increasing computable function $f : ω \to ω$ such that, for any computable order h such that A is h- $wtt$ -jump traceable, $A^{†}$ is $\tilde{h}$ -c.a. via the computable order $\tilde{h} (x) = 2 h (f (x)) + 1$ .
Proof.
Given a computable enumeration ${A_{s}}_{s \in ω}$ of A, consider the $wtt$ -functional Ψ such that, for any oracle X and any input $e, x \in ω$ , we have $\begin{aligned} (45) & Ψ^{X} (⟨ e, x ⟩) = μ s ({\hat{Φ}}_{e}^{A} (x) [s] ↓ & X ↾ {\hat{φ}}_{e} (x) + 1 = A_{s} ↾ {\hat{φ}}_{e} (x) + 1) \end{aligned}$ and, by 3. of Lemma 3.4, let $f : ω \to ω$ be a computable function such that $Ψ^{X} (n) = {\hat{J}}^{X} (f (n))$ holds for all oracles X and all numbers n.

Now fix a computable order h and suppose that A is h- $wtt$ -jump traceable. By the latter, fix a uniformly c.e. sequence ${V_{e}}_{e \in ω}$ which is an h-trace for ${\hat{J}}^{A}$ . Then, for all $n, e, x, s \in ω$ , let $\begin{aligned} (46) & t (n, s) = max (V_{f (n), s}), and \\ (47) & g (⟨ e, x ⟩, s) = \{\begin{array}{ll} 1 & if {\hat{Φ}}_{e}^{A} (x) [t (⟨ e, x ⟩, s)] ↓ and \\ A_{s} ↾ {\hat{φ}}_{e} (x) + 1 = A_{t (⟨ e, x ⟩, s)} ↾ {\hat{φ}}_{e} (x) + 1, \\ 0 & otherwise. \end{array} \end{aligned}$ We claim that $A^{†}$ is $\tilde{h}$ -c.a. via g for the computable order $\tilde{h}$ as given by the lemma. First of all, we show that ${lim}_{s \to \infty} g (⟨ e, x ⟩, s) = A^{†} (⟨ e, x ⟩)$ holds for all $e, x \in ω$ . First, suppose that ${\hat{Φ}}_{e}^{A} (x) ↑$ . Then ${\hat{Φ}}_{e}^{A} (x) [s] ↑$ holds for almost all stages s; hence, ${lim}_{s \to \infty} g (⟨ e, x ⟩, s) = 0$ , as desired. Otherwise, $Ψ^{A} (⟨ e, x ⟩) ↓$ ; hence, ${\hat{J}}^{A} (f (⟨ e, x ⟩)) ⩽ t (⟨ e, x ⟩, s)$ holds for almost all s by the definition of f and by (47) which in turn implies that ${lim}_{s \to \infty} g (⟨ e, x ⟩, s) = 1$ , as desired.

In order to show that the number of mind changes of $g (⟨ e, x ⟩, \cdot)$ is bounded by $2 h (f (⟨ e, x ⟩)) + 1$ , by the fact that $g (⟨ e, x ⟩, 0) = 0$ , it suffices to show that the number of stages $s_{0} < s_{1}$ such that $g (⟨ e, x ⟩, s_{0}) = 1$ , $g (⟨ e, x ⟩, s_{0} + 1) = 0$ and such that $s_{1}$ is the least stage greater than $s_{0}$ such that $g (⟨ e, x ⟩, s_{1}) = 1$ is bounded by $h (f (⟨ e, x ⟩))$ . For the latter, let $e, x \in ω$ be given and suppose that $s_{0} < s_{1}$ are as above. We claim that $t (⟨ e, x ⟩, s_{0}) < t (⟨ e, x ⟩, s_{1})$ holds. Otherwise, since $t (⟨ e, x ⟩, s)$ is nondecreasing in s and by (47), it follows that $\begin{matrix} {\hat{Φ}}_{e}^{A} (x) [t (⟨ e, x ⟩, s_{0})] ↓ \end{matrix}$ and $\begin{matrix} A_{s_{1}} ↾ {\hat{φ}}_{e} (x) + 1 = A_{t (⟨ e, x ⟩, s_{0})} ↾ {\hat{φ}}_{e} (x) + 1 . \end{matrix}$ Hence, $g (⟨ e, x ⟩, s) = 1$ holds for all $s \in [s_{0}, s_{1})$ , contrary to choice of stage $s_{0}$ . So for any such two stages $s_{0} < s_{1}$ there exists a number which is enumerated into $V_{f ⟨ e, x ⟩}$ . As ${V_{e}}_{e \in ω}$ is an h-trace, this completes the proof. □

6.3. A hierarchy of $wtt$ -superlow sets

We conclude the section by looking at strong variants of $wtt$ -superlowness and by introducing a hierarchy of $wtt$ -superlow sets. By Lemma 6.2 a set A is $wtt$ -superlow if there is a computable order h such that $A^{†}$ is h-c.a. So we may ask whether the function h depends on A or not. In this subsection we show that in general this is the case. In fact, we show that, for any computable order $h_{1}$ , there is a (faster growing) computable order $h_{2}$ such that there is a c.e. set A such that the bounded jump $A^{†}$ of A is $h_{2}$ -c.a. but not $h_{1}$ -c.a., and there is a (slower growing) computable order $h_{0}$ such that there is a c.e. set B such that the bounded jump $B^{†}$ of B is $h_{1}$ -c.a. but not $h_{0}$ -c.a. On the other hand, in the next subsection we will show that there are noncomputable – in fact, Turing complete – c.e. sets A such that $A^{†}$ is h-c.a. for all computable orders.

The key to the hierarchy results in this subsection is the following technical lemma.

Lemma 6.9.
Let h, $\hat{h}$ , H and $\hat{H}$ be computable orders such that, for $n ⩾ 0$ , $\begin{matrix} (48) & \hat{h} (n) = h (⟨ n, n ⟩) and H (n) = 2 \hat{H} (n) + 1 \end{matrix}$ and such that there are a computable order $neg (n)$ and a strong array ${F_{n}}_{n \in ω}$ of mutually disjoint finite sets satisfying $\begin{matrix} (49) & \forall n (| F_{n} | = neg (n) + 1) \end{matrix}$ and $\begin{matrix} (50) & \forall m (\sum_{{n : neg (n) ⩽ m}} (\hat{h} (max F_{n}) + 1) ⩽ \hat{H} (m)) . \end{matrix}$ Then there is a c.e. set A such that $A^{†}$ is H-c.a. but not h-c.a.
Proof.
By a finite injury argument, we give a computable enumeration ${A_{s}}_{s \in ω}$ of a c.e. set A with the required properties.

We make $A^{†}$ H-c.a. via the canonical computable approximation $g : ω^{2} \to {0, 1}$ of $A^{†}$ induced by ${A_{s}}_{s \in ω}$ where (for $e, x ⩾ 0$ ) $\begin{matrix} (51) & g (⟨ e, x ⟩, s) = 1 \Leftrightarrow {\hat{Φ}}_{e}^{A} (x) [s] ↓ . \end{matrix}$ For this sake it suffices to ensure that $\begin{matrix} m_{g} (⟨ e, x ⟩) ⩽ H (⟨ e, x ⟩) \end{matrix}$ for all $e, x ⩾ 0$ where $\begin{matrix} m_{g} (⟨ e, x ⟩) = | {s : g (⟨ e, x ⟩, s + 1) \neq g (⟨ e, x ⟩, s)} | \end{matrix}$ is the number of mind changes of g on $⟨ e, x ⟩$ . In order to achieve this, it suffices to meet the (negative) requirements $\begin{matrix} N_{⟨ e, x ⟩} : {\hat{φ}}_{e} (x) ↓ \Rightarrow | (A ∖ A_{s_{⟨ e, x ⟩}}) ↾ {\hat{φ}}_{e} (x) | ⩽ \hat{H} (⟨ e, x ⟩) \end{matrix}$ for $e, x ⩾ 0$ where $s_{⟨ e, x ⟩}$ is the least stage s such that ${\hat{φ}}_{e, s} (x) ↓$ . Namely, for any stage s such that $g (⟨ e, x ⟩, s) = 1$ and $g (⟨ e, x ⟩, s + 1) = 0$ , the definition of g implies that $s ⩾ s_{⟨ e, x ⟩}$ and $A_{s + 1} ↾ {\hat{φ}}_{e} (x) \neq A_{s} ↾ {\hat{φ}}_{e} (x)$ . Since $g (⟨ e, x ⟩, s) = 1$ for any other stage s such that $g (⟨ e, x ⟩, s + 1) \neq g (⟨ e, x ⟩, s)$ , it follows that $\begin{aligned} m_{g} (⟨ e, x ⟩) & ⩽ 2 \cdot | {s : g (⟨ e, x ⟩, s) = 1 & g (⟨ e, x ⟩, s + 1) = 0} | + 1 \\ ⩽ 2 \cdot | {s ⩾ s_{⟨ e, x ⟩} : A_{s + 1} ↾ {\hat{φ}}_{e} (x) \neq A_{s} ↾ {\hat{φ}}_{e} (x) |} | + 1 \\ ⩽ 2 \cdot | (A ∖ A_{s_{⟨ e, x ⟩}}) ↾ {\hat{φ}}_{e} (x) | + 1 \\ ⩽ 2 \cdot \hat{H} (⟨ e, x ⟩) + 1 \\ = H (⟨ e, x ⟩) \end{aligned}$ where the last inequality holds by $N_{⟨ e, x ⟩}$ .

In order to guarantee that $A^{†}$ is not h-c.a., we define an auxiliary $wtt$ -functional Ψ together with a corresponding partial computable use bound ψ such that $\begin{matrix} (52) & dom (Ψ) is not \hat{h} -c.a. \end{matrix}$ The proof that this guarantees that $A^{†}$ is not h-c.a. is indirect. For a contradiction assume that $A^{†}$ is h-c.a. Fix $\hat{g}$ such that $A^{†}$ is h-c.a. via $\hat{g}$ and fix e such that $Ψ = {\hat{Φ}}_{e}$ . Then, for $x ⩾ 0$ , $λ s . \hat{g} (⟨ e, x ⟩, s)$ converges to $dom (Ψ) (x)$ with $⩽ h (⟨ e, x ⟩)$ mind changes. Since $h (⟨ e, x ⟩) ⩽ \hat{h} (x)$ for all numbers $x ⩾ e$ , this implies that $dom (Ψ)$ is $\hat{h}$ -c.a. contrary to (52).

Since, for any order h, any h-c.a. set B is h-c.a. via a primitive recursive function, condition (52) can be broken up into the (positive) requirements $\begin{matrix} P_{n} : dom (Ψ) is not \hat{h} -c.a. via g_{n} . \end{matrix}$ ( $n ⩾ 0$ ) where ${g_{n}}_{n \in ω}$ is a computable numbering of the primitive recursive functions of type $ω^{2} \to {0, 1}$ .

The basic strategy for meeting requirement $P_{n}$ is as follows. We pick a number y, called ( $P_{n}$ -)follower, such that $P_{n}$ may define Ψ and ψ on y. Then we ensure that the follower y witnesses that $P_{n}$ is met by guaranteeing $\begin{matrix} (53) & dom (Ψ^{A}) (y) = lim_{s \to \infty} g_{n} (y, s) \Rightarrow | {s : g_{n} (y, s + 1) \neq g_{n} (y, s)} | > \hat{h} (y) . \end{matrix}$ For this sake we pick $\hat{h} (y) + 1$ numbers $z_{0} < z_{1} < \dots < z_{\hat{h} (y)}$ , called ( $P_{n}$ -)attackers, which are not used as attackers by other strategies, let $ψ (y) = z_{\hat{h} (y)} + 1$ (note that this allows us to make a convergent computation $Ψ^{A} (y) [s] ↓$ divergent at stage $s + 1$ by enumerating one of the attackers into A at this stage), and define Ψ on y as follows (where initially $Ψ^{A} (y) [0] ↑$ ). For any stage s such that $Ψ^{A} (y) [s] ↑$ and $g_{n} (y, s) = 0$ we let $Ψ^{A} (y) [s + 1] ↓$ (note that this does not require to change the oracle $A_{s}$ ) and for any stage s such that $Ψ^{A} (y) [s] ↓$ , $g_{n} (y, s) = 1$ and there is at least one attacker $z_{i}$ left which is not yet in A, we put the least such $z_{i}$ into A at stage $s + 1$ and let $Ψ^{A} (y) [s + 1] ↑$ . Obviously, if the hypothesis of (53) holds, this guarantees that there are at least $\hat{h} (y) + 1$ stages s such that $g_{n} (y, s) = 1$ and $g_{n} (y, s + 1) = 0$ . So, in particular, (53) holds. Moreover, the functional Ψ defined in this way is a $wtt$ -functional with partial computable bound ψ on the use.

Now, in order to make the $P_{n}$ -strategies compatible with the goal of meeting the negative requirements $N_{⟨ e, x ⟩}$ , we have to adjust the basic strategy. In particular, it may happen that the $P_{n}$ -follower may be cancelled by a negative requirement, and the basic strategy for meeting $P_{n}$ has to be started all over again with a new follower (and new attackers).

We say that $P_{n}$ injures $N_{⟨ e, x ⟩}$ via follower y and corresponding attacker z at stage $s + 1$ if ${\hat{φ}}_{e, s} (x) ↓$ (i.e., $s_{⟨ e, x ⟩} ⩽ s$ ), $z < {\hat{φ}}_{e} (x)$ and $P_{n}$ enumerates z into A at stage $s + 1$ . So, since attackers are the only numbers which may enter A, in order to ensure that $N_{⟨ e, x ⟩}$ is met it suffices to guarantee that there are at most $\hat{H} (⟨ e, x ⟩)$ stages at which the requirement $N_{⟨ e, x ⟩}$ is injured. In order to achieve this, first we ensure that if a $P_{n}$ -follower y is appointed at stage $s + 1$ then the corresponding attackers $z_{i}$ are chosen to be $⩾ s + 1$ (in the actual construction we achieve this by letting $z_{i} = ⟨ y, s + 1, i ⟩$ which, in addition, ensures that the sets of attackers associated with different followers are disjoint) whence, for any requirement $N_{⟨ e, x ⟩}$ such that ${\hat{φ}}_{e, s} (x) ↓$ , $P_{n}$ will not injure $N_{⟨ e, x ⟩}$ after stage s since ${\hat{φ}}_{e} (x) ⩽ s_{⟨ e, x ⟩} ⩽ s ⩽ z_{i}$ for any attacker $z_{i}$ associated with y (or with any $P_{n}$ -follower appointed later). Next we assign priorities to the requirements, and we ensure that a negative requirement $N_{⟨ e, x ⟩}$ cannot be injured by any lower priority positive requirement $P_{n}$ as follows. If ${\hat{φ}}_{e} (x)$ becomes defined at stage s (i.e., if $s = s_{⟨ e, x ⟩}$ ) then $N_{⟨ e, x ⟩}$ initializes the lower priority positive requirements $P_{n}$ at stage s by cancelling the current follower y of $P_{n}$ (if any) and the corresponding attackers. So the strategy for meeting $P_{n}$ has to be restarted with a new follower and new attackers after stage s, thereby guaranteeing that the new attackers are too large to injure $N_{⟨ e, x ⟩}$ .

Note that $P_{n}$ can be injured by any higher priority negative requirement at most once. So in order to guarantee that there will be a follower y of $P_{n}$ left which is never cancelled (whence the basic strategy using follower y will succeed to meet $P_{n}$ ) it suffices to assign a reservoir of followers to $P_{n}$ which is greater than the number of the negative requirements that have higher priority than $P_{n}$ .

Here we achieve this by letting $N_{m}$ have higher priority than $P_{n}$ iff $m < neg (n)$ (and by letting $P_{n}$ have higher priority than $N_{m}$ otherwise) and by letting the finite set $F_{n}$ be the reservoir of $P_{n}$ -followers. Then there are $neg (n)$ negative requirements of higher priority than $P_{n}$ and, by (49) there are $neg (n) + 1$ potential $P_{n}$ -followers. So the positive requirements $P_{n}$ are met.

It remains to show that the negative requirements $N_{⟨ e, x ⟩}$ are met, too. By initialization, $N_{⟨ e, x ⟩}$ can be injured only by the higher priority positive requirements, i.e., by the requirements $P_{n}$ where $neg (n) ⩽ ⟨ e, x ⟩$ . Moreover, for any such requirement $P_{n}$ , $N_{⟨ e, x ⟩}$ can be injured via one $P_{n}$ -follower only. Namely, if $N_{⟨ e, x ⟩}$ becomes injured by $P_{n}$ via y at stage $s + 1$ then $s_{⟨ e, x ⟩} ⩽ s$ . So the attackers of any $P_{n}$ -followers which may be appointed later are greater than $s_{⟨ e, x ⟩}$ and hence cannot injure $N_{⟨ e, x ⟩}$ . So $N_{⟨ e, x ⟩}$ can be injured by a single higher priority positive requirement $P_{n}$ at most $\hat{h} (max F_{n}) + 1$ times, since any $P_{n}$ -follower y is picked from the reservoir $F_{n}$ and since y is associated with $\hat{h} (y) + 1$ attackers.

So, if we let $P_{n} > N_{m}$ denote that $P_{n}$ has higher priority than $N_{m}$ , then, for any $⟨ e, x ⟩$ such that ${\hat{φ}}_{e} (x) ↓$ , $\begin{aligned} | (A ∖ A_{s_{⟨ e, x ⟩}}) ↾ {\hat{φ}}_{e} (x) | & ⩽ \sum_{{n : P_{n} > N_{⟨ e, x ⟩}}} (\hat{h} (max F_{n}) + 1) \\ = \sum_{{n : neg (n) ⩽ ⟨ e, x ⟩}} (\hat{h} (max F_{n}) + 1) \\ ⩽ \hat{H} (⟨ e, x ⟩) \end{aligned}$ where the last inequality holds by assumption (50). So the negative requirements $N_{⟨ e, x ⟩}$ are met, too.

Having outlined the construction, we conclude the proof by giving the formal construction. We start with some additional notation. Let $y_{n} [s]$ be the follower of $P_{n}$ at stage s (if any); if $y_{n} [s] ↓$ let $z_{n, i} [s]$ ( $i ⩽ \hat{h} (y_{n} [s])$ ) be the attackers associated with $y_{n} [s]$ ; let $y_{0}^{n} < y_{1}^{n} < \dots < y_{neg (n)}^{n}$ be the elements of $F_{n}$ in order of magnitude; call a negative requirement critical at stage s if ${\hat{φ}}_{e, s} (x) ↓$ (i.e., $s_{⟨ e, x ⟩} ⩽ s$ ); and let $\begin{matrix} l (n, s) = | {⟨ e, x ⟩ < neg (n) : {\hat{φ}}_{e, s} (x) ↓} | = | {⟨ e, x ⟩ < neg (n) : s_{⟨ e, x ⟩} ↓ ⩽ s} | \end{matrix}$ be the number of the negative requirements of higher priority than $P_{n}$ which are critical at stage s. (Note that $λ s . l (n, s)$ is nondecreasing in s, $l (n, 0) = 0$ and $l (n, s) ⩽ neg (n)$ whence $y_{l (n, s)}^{n}$ is a well-defined element of $F_{n}$ .) In the construction all parameters persist unless explicitly stated otherwise.

Stage 0 is vacuous, i.e., $A_{0} = \emptyset$ , Ψ and ψ are nowhere defined, and no followers and attackers are defined.
Stage $s + 1$ . Requirement $P_{n}$ requires attention if
either $n = s$ , or $n < s$ and $l (n, s) < l (n, s + 1)$ or

$n < s$ and $l (n, s + 1) = l (n, s)$ and

$Ψ^{A} (y_{n} [s]) [s] ↑ & g_{n} (y_{n} [s], s) = 0$ or

$Ψ^{A} (y_{n} [s]) [s] ↓ & g_{n} (y_{n} [s], s) = 1$ and there is an attacker $z_{n, i} [s]$ which is not in $A_{s}$ .
For any requirement $P_{n}$ which requires attention act as follows according to the case via which the requirement requires attention.

If $n < s$ and $l (n, s) < l (n, s + 1)$ declare that $P_{n}$ is initialized at stage $s + 1$ and cancel the follower and attackers of $P_{n}$ existing at stage s. In any case appoint $y_{n} [s + 1] = y_{l (n, s + 1)}^{n}$ as (new) $P_{n}$ -follower, assign $z_{n, i} [s + 1] = ⟨ y_{n} [s + 1], s + 1, i ⟩$ as the corresponding attackers $(i ⩽ \hat{h} (y_{n} [s + 1]))$ , and let $ψ (y_{n} [s + 1]) = z_{n, \hat{h} (y_{n} [s + 1])} [s + 1] + 1$ .

Distinguish the following subcases. If (b1) holds then let $Ψ^{A} (y_{n} [s]) [s + 1] ↓$ . If (b2) holds then let $Ψ^{A} (y_{n} [s]) [s + 1] ↑$ and, for the least i such that $z_{n, i} [s] \notin A_{s}$ , enumerate $z_{n, i} [s]$ into A.

This completes the construction. The correctness of the construction follows from the preceding discussion. A formal verification is left to the reader. □
Theorem 6.10.
Let $h_{1}$ be any computable order. There are computable orders $h_{0}$ and $h_{2}$ such that the following hold.
There is a c.e. set A such that $A^{†}$ is $h_{2}$ -c.a. but not $h_{1}$ -c.a.

There is a c.e. set A such that $A^{†}$ is $h_{1}$ -c.a. but not $h_{0}$ -c.a.

Proof.
(a). Let h, $\hat{h}$ , H, $\hat{H}$ be the computable orders defined by $h = h_{1}$ , $\hat{h} (n) = ⟨ n, n ⟩$ , $\begin{matrix} (54) & \hat{H} (n) = n \cdot (\hat{h} (⟨ n, n ⟩) + 1), \end{matrix}$ and $H (n) = 2 \hat{H} (n) + 1$ ( $n ⩾ 0$ ), let neg be the computable order $neg (n) = n + 1$ , and let ${F_{n}}_{n \in ω}$ be the strong array of mutually disjoint finite sets given by $\begin{matrix} F_{n} = | {⟨ n, k ⟩ : k ⩽ n} | . \end{matrix}$ We claim that (a) holds for $h_{2} = H$ . By Lemma 6.9 it suffices to show that (49) and (50) hold. The former is immediate. The latter holds by $\begin{aligned} \sum_{{n : neg (n) ⩽ m}} (\hat{h} (max F_{n}) + 1) & = \sum_{{n : n + 1 ⩽ m}} (\hat{h} (⟨ n, n ⟩) + 1) \\ ⩽ m \cdot (\hat{h} (⟨ m, m ⟩) + 1) \\ = \hat{H} (m) \end{aligned}$ where the first equality holds by the definition of $neg (n)$ and $F_{n}$ while the last equality holds by the definition of $\hat{H}$ .

(b). Note that, for any computable orders $\tilde{h}$ and $\tilde{\tilde{h}}$ such that $\tilde{h}$ dominates $\tilde{\tilde{h}}$ , any $\tilde{\tilde{h}}$ -c.a. set is $\tilde{h}$ -c.a. Moreover, for any computable order $\tilde{h}$ there is a computable order $\hat{H}$ such that $\tilde{h}$ dominates the computable order $H (n) = 2 \hat{H} (n) + 1$ . So w.l.o.g. we may assume that there is a computable order $\hat{H}$ such that $h_{1}$ is the corresponding computable order H, i.e., $h_{1} (n) = H (n) = 2 \hat{H} (n) + 1$ for $n ⩾ 0$ . It suffices to define computable orders h, $\hat{h}$ , neg and a strong array ${F_{n}}_{n \in ω}$ of disjoint finite sets such that h, $\hat{h}$ , H, $\hat{H}$ , neg and ${F_{n}}_{n \in ω}$ satisfy the hypotheses of Lemma 6.9. Then (b) holds for $h_{0} = h$ .

Let neg be a strictly increasing computable function such that $\hat{H} (neg (n)) ⩾ s (n + 1)$ where $s (n) = 0 + 1 + \dots + n$ , and let ${F_{n}}_{n \in ω}$ be the computable partition of ω into intervals such that $max F_{n} + 1 = min F_{n + 1}$ and $\begin{matrix} | F_{n} | = neg (n) + 1 . \end{matrix}$ Finally, let h be any computable order such that $\begin{matrix} h (⟨ n, n ⟩) = m iff n \in F_{m} \end{matrix}$ and let $\hat{h} (n) = h (⟨ n, n ⟩)$ .

It remains to show that (49) and (50) hold. The former is immediate by the definition of $F_{n}$ . For a proof of (50) fix m. W.l.o.g. we may assume that there is a number n such that $neg (n) ⩽ m$ (otherwise, (50) trivially holds since $\sum_{\emptyset} (\dots) = 0$ ). So, since neg is an order, there is a greatest such n, say, $n_{0}$ . It follows that $\begin{aligned} \sum_{{n : neg (n) ⩽ m}} (\hat{h} (max F_{n}) + 1) & = \sum_{{n : neg (n) ⩽ m}} (n + 1) \\ (by the definition of h and \hat{h}) \\ ⩽ \sum_{{n : n ⩽ n_{0}}} (n + 1) \\ (by the maximality of n_{0}) \\ = s (n_{0} + 1) \\ ⩽ \hat{H} (neg (n_{0})) \\ (by the definition of neg) \\ ⩽ \hat{H} (m) \\ (by neg (n_{0}) ⩽ m) \end{aligned}$ which completes the proof of (50) and the proof of the theorem. □

6.4. Strongly $wtt$ -superlow sets

We now show that there is a noncomputable c.e. set – in fact, a Turing complete set – A such that $A^{†}$ is h-c.a. for any order h.

Definition 6.11.
A set A is strongly $wtt$ -superlow if $A^{†}$ is h-computably approximable for any computable order h; and A is strongly $wtt$ -jump traceable if A is h-wtt-jump traceable for any order h such that $h (0) > 0$ .

We first observe that the equivalence of $wtt$ -superlowness and $wtt$ -jump traceability for c.e. sets extends to strong $wtt$ -superlowness and strong $wtt$ -jump traceability.
Lemma 6.12.
Let A be a c.e. set. A is strongly $wtt$ -superlow if and only if A is strongly $wtt$ -jump traceable.
Proof.
First assume that A is strongly $wtt$ -superlow. Then, given a computable order h such that $h (0) > 0$ , we have to show that A is h- $wtt$ -jump traceable. Let $h^{'}$ be a computable order such that $⌈ \frac{h^{'} (⟨ x, x ⟩)}{2} ⌉ ⩽ h (x)$ for all $x ⩾ 0$ . Then, by assumption, $A^{†}$ , is $h^{'}$ -c.a. But, by Lemma 6.7, this implies that A is h- $wtt$ -jump traceable.

Now assume that A is strongly $wtt$ -jump traceable. Then, given a computable order h, we have to show that $A^{†}$ is h-c.a. Since any set which is h-c.a. is $h^{'}$ -c.a. for any finite variant $h^{'}$ of h, w.l.o.g. we may assume that $h (0) ⩾ 3$ . Fix a strictly increasing computable function f as in Lemma 6.8 and let $h^{'}$ be a computable order such that $h^{'} (0) = 1$ and $2 h^{'} (f (x)) + 1 ⩽ h (x)$ for $x ⩾ 0$ (note that, by $h (0) ⩾ 3$ such $h^{'}$ exists). Then, by assumption, A is $h^{'}$ - $wtt$ -jump traceable. But, by Lemma 6.8, this implies that $A^{†}$ is h-c.a. □
Theorem 6.13.
There exists a Turing complete set A which is strongly $wtt$ -superlow.
Proof.
We give a computable enumeration ${A_{s}}_{s \in ω}$ of a c.e. set A with the required properties. In order to make A Turing complete we use marker permitting. Fix a Turing complete set K, let $k : ω \to ω$ be a computable one-to-one function enumerating K, and let $K_{s} = {k (t) : t < s}$ . We inductively define the computable marker function $γ : ω^{2} \to ω$ by letting $\begin{aligned} (55) & \begin{aligned} γ (x, 0) = ⟨ x, 0 ⟩ \\ γ (x, s + 1) = \{\begin{array}{ll} γ (x, s) & if x < x_{s}, \\ ⟨ x, s + 1 ⟩ & otherwise, \end{array} \end{aligned} \end{aligned}$ where the number $x_{s}$ is determined at stage $s + 1$ of the construction. Moreover, we let $\begin{matrix} (56) & A_{s} = {γ (x_{t}, t) : t < s} \end{matrix}$ (for $s ⩾ 0$ ). Note that $γ (x, s)$ is strictly increasing in x and nondecreasing in s. Moreover, if γ is moved on x at stage $s + 1$ then $γ (x, s) < γ (x, s + 1)$ , $γ (x, s + 1) ⩾ s + 1$ , and $γ (x, s + 1) \neq γ (y, t)$ for all numbers y and all stages $t ⩽ s$ . It follows that $γ (x, s) \notin A_{s}$ for all numbers x and stages s. So the marker $γ (x_{s}, s)$ is enumerated into A at stage $s + 1$ , and the markers $γ (x_{s}, s)$ ( $s ⩾ 0$ ) are the only numbers enumerated into A. Now in order to ensure that K is Turing reducible to A it suffices to choose the numbers $x_{s}$ such that $\begin{matrix} (57) & \forall s (x_{s} ⩽ k (s)) \end{matrix}$ and $\begin{matrix} (58) & \forall x ({s : x_{s} ⩽ x} is finite) . \end{matrix}$ Namely, the latter ensures that, on any x, the marker γ reaches a final position $γ^{} (x)$ , i.e., ${lim}_{s \to \infty} γ (x, s) = γ^{} (x) \in ω$ exists. Moreover, $γ (x)$ reaches its final position at the least stage s such that $x < x_{t}$ for all $t ⩾ s$ , i.e., at the least stage s such that $A ↾ γ (x, s) + 1 = A_{s} ↾ γ (x, s) + 1$ . So $γ^{} ⩽_{T} A$ . By (57) this implies $K ⩽_{T} A$ since, for any x, $x \in K$ iff $x \in K_{s}$ for the least stage s such that $γ (x, s) = γ^{} (x)$ .

Note that, for any stage s, $\begin{matrix} (59) & | (A ∖ A_{s}) ↾ s + 1 | ⩽ x_{s} + 1 . \end{matrix}$ (Namely, $γ (x_{t}, t)$ is the unique number which enters A at stage $t + 1$ and $γ (x, t^{'}) ⩾ t + 1$ for $x ⩾ x_{t}$ and $t^{'} ⩾ t + 1$ . So, for $t^{'} > t ⩾ s$ such that $γ (x_{t}, t) ⩽ s$ and $γ (x_{t^{'}}, t^{'}) ⩽ s$ , we have $x_{t^{'}} < x_{t} ⩽ x_{s}$ .) So, for any number $n > 0$ and any stage s, we can ensure that A changes below $s + 1$ after stage s at most n times by letting $x_{s}$ be less than n. This will be crucial for achieving our second goal, namely the goal to make A strongly $wtt$ -superlow.

By Lemma 6.12, it suffices to make A strongly $wtt$ -jump traceable, i.e., to meet the requirements $\begin{aligned} R_{e} : & If φ_{e} is an order such that φ_{e} (0) > 0 then A is φ_{e} - wtt -jump traceable. \end{aligned}$ for $e ⩾ 0$ . The strategy for meeting these requirements is based on the following observation. Claim 1.
Assume that $φ_{e}$ is an order, $φ_{e} (0) > 0$ , and $\begin{matrix} (60) & \forall^{\infty} n ({\hat{φ}}_{n} (n) ↓ \Rightarrow γ^{} (φ_{e} (n) - 1) ⩾ {\hat{φ}}_{n} (n)) \end{matrix}$ holds. Then* $R_{e}$ is met.
Proof.
Fix $n_{0}$ such that the inner clause of (60) holds for $n ⩾ n_{0}$ . We have to show that there is a $φ_{e}$ -trace ${V_{n}}_{n \in ω}$ for ${\hat{J}}^{A}$ . Let $V_{n} = \emptyset$ if $n < n_{0}$ and ${\hat{J}}_{n}^{A} (n) ↑$ , let $V_{n} = {{\hat{J}}_{n}^{A} (n)}$ if $n < n_{0}$ and ${\hat{J}}_{n}^{A} (n) ↓$ , and let $\begin{matrix} V_{n} = {{\hat{J}}_{n}^{A} (n) [s] : s ⩾ 0 & γ (φ_{e} (n) - 1, s) ⩾ {\hat{φ}}_{n, s} (n) ↓ & {\hat{J}}_{n}^{A} (n) [s] ↓} \end{matrix}$ if $n ⩾ n_{0}$ . Obviously, ${V_{n}}_{n \in ω}$ is a c.e. sequence of finite sets. Moreover, by the choice of $n_{0}$ , ${\hat{J}}_{n}^{A} (n) \in V_{n}$ if ${\hat{J}}_{n}^{A} (n)$ is defined. So it suffices to show that $| V_{n} | ⩽ φ_{e} (n)$ . Since $φ_{e} (n) ⩾ 1$ for all n by assumption, this is immediate for $n < n_{0}$ . So fix $n ⩾ n_{0}$ and, for a contradiction, assume that $| V_{n} | > φ_{e} (n)$ . Then there are stages $s_{0} ⩽ s_{1} < \dots < s_{φ_{e} (n)}$ such that ${\hat{φ}}_{n, s_{0}} (n) ↓ ⩽ s_{0}$ , $γ (φ_{e} (n) - 1, s_{0}) ⩾ {\hat{φ}}_{n} (n)$ and, for $m < φ_{e} (n)$ , ${\hat{J}}_{n}^{A} (n) [s_{m + 1}] ↓ \neq {\hat{J}}_{n}^{A} (n) [s_{m}] ↓$ . By the latter, $\begin{matrix} (61) & | (A ∖ A_{s_{0}}) ↾ {\hat{φ}}_{n} (n) | ⩾ φ_{e} (n) . \end{matrix}$ On the other hand, if y is the first number $< {\hat{φ}}_{n} (n)$ which enters A after stage $s_{0}$ , say, at stage $t + 1 > s_{0}$ , then $\begin{matrix} y = γ (x_{t}, t) < {\hat{φ}}_{n} (n) ⩽ γ (φ_{e} (n) - 1, s_{0}) ⩽ γ (φ_{e} (n) - 1, t) . \end{matrix}$ So $x_{t} < φ_{e} (n) - 1$ . It follows that $\begin{aligned} | (A ∖ A_{s_{0}}) ↾ {\hat{φ}}_{n} (n) | & = | (A ∖ A_{t}) ↾ {\hat{φ}}_{n} (n) | (by the choice of t) \\ ⩽ | (A ∖ A_{t}) ↾ t + 1 | (by {\hat{φ}}_{n} (n) ⩽ s_{0} ⩽ t + 1) \\ ⩽ x_{t} + 1 (by (59)) \\ < φ_{e} (n) \end{aligned}$ contrary to (61). This completes the proof of Claim 1. □

Now, by the above discussion, it suffices to choose the numbers $x_{s}$ so that conditions (57) and (58) as well as, for $e ⩾ 0$ such that $φ_{e}$ is an order and $φ_{e} (0) > 0$ , condition (60) are satisfied. Unless the strategies for satisfying (60) assign a number $< k (s)$ to $x_{s}$ we let $x_{s} = k (s)$ . Obviously this guarantees (57) and, since k is one-to-one, this is consistent with (58).

The strategy for meeting (60) (if necessary) is as follows. Given e and n such that $φ_{e} (n) ↓ > 0$ and ${\hat{φ}}_{n} (n) ↓$ , $φ_{e, s} (n) ↓$ and ${\hat{φ}}_{n, s} (n) ↓$ for almost all stages s and, in order to guarantee that the inner clause of (60) is satisfied, it suffices that $x_{s} ⩽ φ_{e} (n) - 1$ for at least one of these stages s, since this ensures that $\begin{matrix} γ^{} (φ_{e} (n) - 1) ⩾ γ (φ_{e} (n) - 1, s + 1) ⩾ γ (x_{s}, s + 1) = ⟨ x_{s}, s + 1 ⟩ ⩾ s + 1 > {\hat{φ}}_{n} (n) . \end{matrix}$ (Also note that if e or n is not as above then we do not have to satisfy (60) or the inner clause is trivially satisfied.) So the following (preliminary) definition of the numbers $x_{s}$ will guarantee that (57) and (60) are satisfied.
Given s, fix e, n, t such that $s = ⟨ e, n, t ⟩$ . If ${\hat{φ}}_{n, s} (n) ↓$ (hence ${\hat{φ}}_{n} (n) ⩽ s$ ), $φ_{e, s} (n) ↓ ⩾ 1$ , $γ (φ_{e} (n) - 1, s) < {\hat{φ}}_{n} (n)$ , and $φ_{e} (n) - 1 < k (s)$ then let $x_{s} = φ_{e} (n) - 1$ . Otherwise, let $x_{s} = k (s)$ .

Unfortunately, however, this definition does not satisfy (58). Still, for fixed e, such that $φ_{e}$ is an order and $φ_{e} (0) > 0$ , the strategy for satisfying (60) will let $x_{s} ⩽ x$ for fixed x only finitely often, since this happens only for n such that $φ_{e} (n) ⩽ x + 1$ and, for each such n, this may happen at most once. So the claim follows since, by $φ_{e}$ being an order, there are only finitely many n such that $φ_{e} (n) ⩽ x + 1$ . Moreover, since it suffices to meet the inner clause of (58) for almost all n and since, for an order $φ_{e}$ , $φ_{e} (n) > e + 1$ for almost all n, we may restrict the action for $φ_{e}$ to such numbers n. So, for given x, there are only finitely many e which may let $x_{s} ⩽ x$ . Hence, the above modification will suffice to make the action of all orders $φ_{e}$ together compatible with (58). So we have only to ensure that the action for functions $φ_{e}$ which are not an order (and for which we do not have to satisfy (60)) does not affect (58) more seriously than the action for an order. For this sake, for any e, we let $x_{s} = φ_{e} (n) - 1$ only if $φ_{e} (n) > e + 1$ and if we can be sure that we will do so for only finitely many $n^{'}$ with $φ_{e} (n^{'}) = φ_{e} (n)$ . Note that the latter can be guaranteed, by letting $x_{s} = φ_{e} (n) - 1$ only if there is a number $n^{'} > n$ such that $φ_{e, s} (m)$ is defined and this $φ_{e}$ is nondecreasing on $ω ↾ n^{'} + 1$ and $φ_{e} (n) < φ_{e} (n^{'})$ . Also note that this may delay the necessary action for an order $φ_{e}$ only for finitely many stages. So the following definition of $x_{s}$ ( $s ⩾ 0$ ) will have the required properties.
Given s, fix e, n, t such that $s = ⟨ e, n, t ⟩$ . If
${\hat{φ}}_{n, s} (n) ↓$ (hence ${\hat{φ}}_{n} (n) ⩽ s$ ),

there is a number $n^{'} > n$ such that $φ_{e, s} (m) ↓$ for $m ⩽ n^{'}$ , $φ_{e}$ is nondecreasing on $ω ↾ n^{'} + 1$ , $φ_{e} (0) > 0$ , and $φ_{e} (n^{'}) > φ_{e} (n) > e + 1$ ,

$γ (φ_{e} (n) - 1, s) < {\hat{φ}}_{n} (n)$ , and

$φ_{e} (n) - 1 < k (s)$
then let $x_{s} = φ_{e} (n) - 1$ . Otherwise, let $x_{s} = k (s)$ .

We complete the proof by arguing more formally that condition (57), condition (58), and, for orders $φ_{e}$ where $φ_{e} (0) > 0$ , condition (60) are satisfied. Condition (57) is immediate by the definition of $x_{s}$ .

For a proof of (58) fix x. Let u be minimal such that $k (s) > x$ for $s ⩾ u$ . Call s an $(e, n)$ -stage* if $s = ⟨ e, n, t ⟩ ⩾ u$ for some number t and $x_{s} ⩽ x$ , call s an e-stage if s is an $(e, n)$ -stage for some number n, and call s critical if s is an e-stage for some number e. It suffices to show that there are only finitely many critical stages. We do this by showing that (a) any critical stage s is an e-stage for some $e ⩽ x$ and (b) for fixed e there are only finitely many e-stages. For a proof of (a) let s be critical. Fix the unique e, n, t such that $s = ⟨ e, n, t ⟩$ . Then s is an $(e, n)$ -stage. Hence (i)–(iv) in the definition of $x_{s}$ hold and $x_{s} = φ_{e} (n) - 1 ⩽ x$ . By the latter and by (ii), $e ⩽ φ_{e} (n) - 1 = x_{s} ⩽ x$ . So (a) holds. For a proof of (b) fix e, and, for a contradiction, assume that there are infinitely many e-stages. Obviously, for any n, there is at most one $(e, n)$ -stage. So, for any number m, there is an $(e, n)$ -stage such that $n > m$ . On the other hand, if there is an $(e, n)$ -stage s, then $φ_{e}$ is defined and nondecreasing on $ω ↾ n + 1$ and $φ_{e} (n)$ is not the maximum of $range (φ_{e})$ . So $φ_{e}$ is an order. It follows that there is a number $n_{0}$ such that $φ_{e} (n) > x + 1$ for $n ⩾ n_{0}$ . So there is no $(e, n)$ -stage with $n ⩾ n_{0}$ which gives the desired contradiction.

Finally, fix e such that $φ_{e}$ is an order and $φ_{e} (0) > 0$ . We have to show that (60) holds, i.e., that there is a number $n_{0}$ such that $γ^{} (φ_{e} (n) - 1) ⩾ {\hat{φ}}_{n} (n)$ for any $n ⩾ n_{0}$ such that ${\hat{φ}}_{n} (n) ↓$ . Let $n_{0}$ be the least number n such that $φ_{e} (n) > e + 1$ . Then, for any $n ⩾ n_{0}$ such that ${\hat{φ}}_{n} (n) ↓$ , fix t minimal such that, for $s = ⟨ e, n, t ⟩$ , clauses (i) and (ii) in the definition of $x_{s}$ hold. (Note that such a stage must exist since $φ_{e}$ is an order.) It suffices to show that $γ (φ_{e} (n) - 1, s + 1) ⩾ {\hat{φ}}_{n} (n)$ . If (iii) fails then this is immediate. Otherwise, $x_{s} ⩽ φ_{e} (n) - 1$ . So $γ (φ_{e} (n) - 1, s + 1) ⩾ {\hat{φ}}_{n} (n)$ in this case too.

This completes the proof of Theorem 6.13. □

We conclude this section by showing that the class of the strongly $wtt$ -superlow sets is downward closed under $wtt$ -reducibility and that the class of the c.e. strongly $wtt$ -superlow sets is closed under join. Compare this with the corresponding results for the eventually uniformly $wtt$ -array computable sets (Lemmas 5.1 and 5.3) and the $wtt$ -superlow sets (Corollary 6.4). Theorem 6.14.

Let A and B be any (not necessarily c.e.) sets such that* $A ⩽_{wtt} B$ and B is strongly $wtt$ -superlow. Then A is strongly $wtt$ -superlow, too.

Let $A_{0}$ and $A_{1}$ be strongly $wtt$ -superlow c.e. sets. Then $A_{0} \oplus A_{1}$ is strongly $wtt$ -superlow, too.

Proof.
(a). Given a computable order h, it suffices to show that $A^{†}$ is h-c.a. By clause 1. of Lemma 3.4, fix a strictly increasing computable function f such that, for $e ⩾ 0$ , ${\hat{Φ}}_{e}^{A} = {\hat{Φ}}_{f (e)}^{B}$ , hence $\begin{matrix} A^{†} (⟨ e, x ⟩) = B^{†} (⟨ f (e), x ⟩) \end{matrix}$ for $e, x ⩾ 0$ . Now, since f is strictly increasing and so is $⟨ \cdot, \cdot ⟩$ (in either argument), $⟨ f (e), x ⟩ ⩽ f (⟨ e, x ⟩)$ . So, for any order $h^{'}$ and any $h^{'}$ -bounded computable approximation $g^{'}$ of $B^{†}$ , g defined by $g (⟨ e, x ⟩) = g^{'} (⟨ f (e), x ⟩)$ is a computable approximation of $A^{†}$ and g is $h^{'} (f (n))$ -bounded. Since, for any computable order h there is a computable order $h^{'}$ such that $h^{'} (f (n)) ⩽ h (n)$ for $n ⩾ 0$ , and since, by assumption, $B^{†}$ is $h^{'}$ -c.a. for any computable order $h^{'}$ , this shows that $A^{†}$ is h-c.a.

(b) Given a computable order h, it suffices to show that ${(A_{0} \oplus A_{1})}^{†}$ is h-c.a. Fix strictly increasing computable functions $f_{0}, f_{1} : ω \to ω$ as given by Lemma 5.2, let $f (n) = f_{0} (n) + f_{1} (n)$ and let $h^{'}$ be a computable order such that $h^{'} (f (n)) ⩽ h (n)$ for $n ⩾ 0$ . Then, since $A_{0}$ and $A_{1}$ are strongly $wtt$ -superlow, we may fix $h^{'}$ -bounded computable approximations $g_{i}$ of $A_{i}^{†}$ ( $i ⩽ 1$ ). Now define g by $\begin{matrix} g (⟨ e, x ⟩, s) = min {g_{0} (⟨ f_{0} (e), x ⟩, s), g_{1} (⟨ f_{1} (e), x ⟩, s)} . \end{matrix}$ By (43), g is a computable approximation of ${(A_{0} \oplus A_{1})}^{†}$ . Moreover, by the definition of g and by the choice of $g_{0}$ and $g_{1}$ , g is $\hat{h}$ -bounded by for the computable order $\hat{h}$ defined by $\begin{matrix} \hat{h} (⟨ e, x ⟩) = h^{'} (⟨ f_{0} (e), x ⟩) + h^{'} (⟨ f_{1} (e), x ⟩) ⩽ 2 h^{'} (f (⟨ e, x ⟩)) . \end{matrix}$ But, since f majorizes $f_{0}$ and $f_{1}$ and f and $⟨ \cdot, \cdot ⟩$ are strictly increasing, it follows by the choice of $h^{'}$ that $\hat{h} (n) ⩽ h^{'} (f (n)) ⩽ n$ for $n ⩾ 0$ . So ${(A_{0} \oplus A_{1})}^{†}$ is h-c.a. □

7. EUwttAC and array computable sets

In the preceding section we have shown that the class of the c.e. $wtt$ -superlow sets is a subclass of EUwttAC. Here we show that the class of c.e. sets having array computable (a.c.) $wtt$ -degree is a superclass of EUwttAC, i.e., there is no e.u.wtt-a.c. c.e. set which is $wtt$ -equivalent to an array noncomputable (a.n.c.) set.

Before we do so, we give some background on the array (non)computable sets and degrees. We mentioned in the introduction, already, that the array computable degrees, introduced by Downey, Jockusch and Stob [15], have proven a highly successful unifying tool in the study of the computational power of c.e. (and general) sets and Turing degrees. We recall from [15] that a degree a is array noncomputable (a.n.c.) iff for all functions $f ⩽_{wtt} \emptyset^{'}$ there is a function g computable from a such that $\begin{matrix} \exists^{\infty} x (g (x) > f (x)) . \end{matrix}$ So array noncomputability is a kind of non-lowness property, closely resembling – but more general than – non- ${low}_{2}$ -ness since the latter property is obtained if in the above definition we consider all functions f which are Turing reducible to $\emptyset^{'}$ and not only the ones which are $wtt$ -reducible to $\emptyset^{'}$ . It turned out that many constructions which were originally proven using non- ${low}_{2}$ -ness, could be adapted to work with the weaker assumption that a is array noncomputable. For example, Downey, Jockusch and Stob [16] showed that every array noncomputable degree bounds a 1-generic degree. The unifying power of such degrees can be seen in the following summary theorem.

Theorem 7.1.
The c.e. a.n.c. degrees are those that:
(Kummer [ 26 ]) contain c.e. sets of infinitely often maximal Kolmogorov complexity. 5
⁵
Again, these classes are mentioned only to demonstrate the amazing unifying power of this class, and hence we won’t formally define them, as it would interrupt the narrative flow.

(Barmpalias, Downey and McInerney [ 6 ]) have integer valued randoms.

(Downey and Greenberg [ 12 ]) have reals of effective packing dimension 1.

Moreover, (Cholak et al. [ 7 ]) the array noncomputable c.e. degrees form an invariant class for the lattice of $Π_{1}^{0}$ classes via the thin perfect classes.

Having illustrated the importance of the array noncomputable sets and degrees, we now come back to our goal. For this purpose, we have to consider array noncomputable sets and their $wtt$ -degrees (not their Turing degrees as in the examples above). We use a characterization of the a.n.c. $wtt$ -degrees in terms of multiple permitting which is closer to the original definition of the computably enumerable a.n.c. sets in [15] than the non-domination characterization given above. Multiply permitting sets have been introduced by Ambos-Spies in [1], and there it is shown that the array noncomputable c.e. $wtt$ -degrees, i.e., the $wtt$ -degrees which contain a computably enumerable a.n.c. set, can be characterized as those c.e. $wtt$ -degrees whose c.e. members are multiply permitting. For the definition of a multiply permitting set, recall that a very strong array (v.s.a. for short) is a sequence $F = {F_{n}}_{n \in ω}$ of finite sets such that there exists a computable function $f : ω \to ω$ such that for all n, $F_{n} = D_{f (n)}$ , i.e., $f (n)$ is the canonical index of $F_{n}$ , $0 < | F_{n} | < | F_{n + 1} |$ and $F_{n} \cap F_{m} = \emptyset$ hold for all $m \neq n$ . Then multiply permitting c.e. sets are defined as follows.
Definition 7.2 ([1]).

Let $F = {F_{n}}_{n \in ω}$ be a v.s.a., let f be a computable function, let A be a c.e. set, and let ${A_{s}}_{s \in ω}$ be a computable enumeration of A. Then A is $F$ -permitting via f and ${A_{s}}_{s \in ω}$ if, for any partial computable function ψ, $\begin{matrix} (62) & \exists^{\infty} n \forall x \in F_{n} (ψ (x) ↓ \Rightarrow A ↾ f (x) + 1 \neq A_{ψ (x)} ↾ f (x) + 1) \end{matrix}$ holds. A is $F$ -permitting via f if there is a computable enumeration ${A_{s}}_{s \in ω}$ of A such that A is $F$ -permitting via f and ${A_{s}}_{s \in ω}$ ; A is $F$ -permitting if A is $F$ -permitting via some computable f; and A is multiply permitting if A is $F$ -permitting for some v.s.a. $F$ . Finally, a c.e. $wtt$ -degree a is multiply permitting if there is a multiply permitting set $A \in a$ .

By [1, Lemma 1], the property of being multiply permitting for a c.e. set does not depend on the choice of the very strong array.

Lemma 7.3 ([1]).

Let A be multiply permitting and let $F = {F_{n}}_{n \in ω}$ be a v.s.a. Then A is $F$ -permitting.

Moreover, as shown in [1], too, the multiple-permitting property is $wtt$ -invariant and the multiply permitting $wtt$ -degrees coincide with the c.e. array noncomputable $wtt$ -degrees.

Lemma 7.4 ([1]).

For a c.e. $wtt$ -degree a , the following are equivalent.

a is a.n.c.

a is multiply permitting.

Every c.e. set $A \in a$ is multiply permitting.

Using Lemma 7.3, we can show that the following holds.

Theorem 7.5.
Let A be multiply permitting. Then A is not e.u.wtt-a.c.
Proof.
Suppose that A is multiply permitting. It suffices to show that, for any given computable functions $g, k : ω^{2} \to {0, 1}$ and any given computable order h such that (6), (7) and (9) hold, (8) fails. For that, let $F = {F_{n}}_{n \in ω}$ be the unique very strong array such that each $F_{n}$ is an interval such that $| F_{n} | = \hat{h} (n)$ , where $\hat{h} (n) = ⌊ \frac{h (⟨ n, n ⟩) + 1}{2} ⌋$ (note that $\hat{h}$ is a computable order) and such that $min (F_{n + 1}) = max (F_{n}) + 1$ holds for all n. By Lemma 7.3, we may fix a computable function f and a computable enumeration ${A_{s}}_{s \in ω}$ of A such that A is $F$ -permitting via f and ${A_{s}}_{s \in ω}$ , where, w.l.o.g., we may assume that f is strictly increasing.

Then we define a $wtt$ -functional Γ in stages s where, by Lemma 3.3, we may assume that in advance we know a number d such that $Γ = {\hat{Φ}}_{d}$ holds. In particular, by (6), ${lim}_{s \to \infty} g (⟨ d, n ⟩, s) = 1$ holds iff $n \in dom (Γ^{A})$ . In more detail, we define a uniformly computable sequence of $wtt$ -functionals ${{\tilde{Γ}}_{e}}_{e \in ω}$ and we declare ${\tilde{Γ}}_{e}^{A} (n)$ to be defined (undefined) at a stage $s + 1$ only if $g (⟨ e, n ⟩, s)$ correctly approximates whether or not ${\tilde{Γ}}_{e}^{A} (n) [s]$ is defined (so below, the reader may replace Γ by ${\tilde{Γ}}_{e}$ and any occurrence of d in any of the functions g and k by e). Then, by clauses 1. and 2. of Lemma 3.3 there exists $d \in ω$ such that ${\tilde{Γ}}_{d} = {\hat{Φ}}_{d}$ . So d and $Γ = {\tilde{Γ}}_{d}$ are as desired.

Then the definition of Γ is as follows, where we stick to the convention that $Γ^{A} (n) [s + 1] = Γ^{A} (n) [s]$ holds for any n and any stage s unless otherwise stated. Fix n in the following. Definition of $Γ^{A} (n)$ .

Stage 0. Let $Γ^{A} (n) [0] ↑$ .

Stage $s + 1$ . Let $Γ^{A} (n) [s]$ be given. Then we distinguish between the following two cases.

If $Γ^{A} (n) [s] ↑$ and $g (⟨ d, n ⟩, s) = 0$ hold then declare $Γ^{A} (n) [s + 1] ↓$ .

If $Γ^{A} (n) [s] ↓$ , $g (⟨ d, n ⟩, s) = 1$ , $k (⟨ d, n ⟩, s) = 1$ and we have that $A_{s + 1} ↾ f (max (F_{n})) + 1 \neq A_{s^{-}} ↾ f (max (F_{n})) + 1$ , where $s^{-}$ is the largest stage $⩽ s$ such that $Γ^{A} (n) [t] ↓$ holds for all $t \in [s^{-}, s]$ , then declare $Γ^{A} (n) [s + 1] ↑$ .

By definition, Γ is a Turing functional and since, by clause (2), the use of Γ on input n is bounded by $f (max (F_{n}))$ , it follows that Γ is indeed a $wtt$ -functional. Moreover, by clause (1), we may argue that $Γ^{A}$ is total as we keep $Γ^{A} (n) [s] ↑$ for any stage s unless (1) holds. However, as $g (⟨ d, n ⟩, s)$ correctly approximates the question as to whether or not $x \in dom (Γ^{A})$ holds, it follows that, for any stage s such that $Γ^{A} (n) [s] ↑$ , there exists a least stage $t ⩾ s$ such that $Γ^{A} (n) [t] ↑$ and $g (⟨ d, n ⟩, t) = 0$ . So for the least s such that $A_{s} ↾ f (max (F_{n})) + 1 = A ↾ f (max (F_{n})) + 1$ and $Γ^{A} (n) [s] ↓$ , it follows that $Γ^{A} (n) [t] ↓$ for all $t > s$ . Hence, by (9), we may fix $n_{0} \in ω$ such that ${lim}_{s \to \infty} k (⟨ d, n ⟩, s) = 1$ holds for all $n ⩾ n_{0}$ . Likewise, we can argue that for any stage s such that $Γ^{A} (n) [s] ↓$ there exists a least stage $t ⩾ s$ such that $Γ^{A} (n) [t] ↓$ and $g (⟨ d, n ⟩, t) = 1$ . In particular, the clauses (1) and (2) always apply alternatingly to $Γ^{A} (n)$ .

Now consider the partial computable function $ψ : ω \to ω$ which is defined as follows. Given n, let $x_{0}^{n} < \dots < x_{\hat{h} (n) - 1}^{n}$ be the elements of $F_{n}$ . Then $ψ (x_{i}^{n})$ is defined inductively such that, for all $i < \hat{h} (n) - 1$ , we have $\begin{aligned} ψ (x_{0}^{n}) = μ s (P (n, s)), \\ ψ (x_{i + 1}^{n}) = μ s (s > ψ (x_{i}^{n}) & P (n, s) & \exists t \in (ψ (x_{i}^{n}), s) (Γ^{A} (n) [t] ↑)), \end{aligned}$ where $P (n, s)$ holds iff $Γ^{A} (n) [s] ↓$ , $g (⟨ d, n ⟩, s) = 1$ and $k (⟨ d, n ⟩, s) = 1$ holds. Note that, for all n, we have that either $dom (ψ) \cap F_{n} = \emptyset$ or $F_{n} \subset dom (ψ)$ . Namely, by definition, $ψ (x_{i}^{n}) ↓$ can only hold if $ψ (x_{j}^{n}) ↓$ holds for all $j < i$ and, if $ψ (x_{i}^{n}) ↓$ holds for some $i < \hat{h} (n)$ then, by (62) and since ${lim}_{s \to \infty} g (⟨ d, n ⟩, s) = 1$ holds, there exists a stage $t > ψ (x_{i}^{n})$ such that (2) applies at stage t in the definition of $Γ^{A} (n)$ ; hence, by (7), by the definition of $P (n, s)$ and by the totality of $Γ^{A}$ , we may infer that $ψ (x_{i + 1}^{n}) ↓$ holds. So since ${lim}_{s \to \infty} k (⟨ d, n ⟩, s) = 1$ holds for all $n ⩾ n_{0}$ , it follows that there exist infinitely many n such that $ψ (x_{0}^{n}) ↓$ ; hence, $F_{n} \subset dom (ψ)$ holds. However, for any such n, by the definition of Γ, it follows that, for any $i ⩽ \hat{h} (n)$ , there exist two stages $ψ (x_{i}^{n}) ⩽ s_{0} < s_{1}$ such that $g (⟨ d, n ⟩, s_{i} + 1) \neq g (⟨ d, n ⟩, s_{i})$ holds for all $i ⩽ 1$ ; and, if $i < \hat{h} (n)$ then $s_{1} < ψ (x_{i + 1}^{n})$ holds. So for any $n ⩾ d$ such that $ψ (x_{0}^{n}) ↓$ holds the number of mind changes of $g (⟨ d, n ⟩, \cdot)$ after stage $ψ (x_{0}^{n})$ is at least $\begin{array}{r} 2 \hat{h} (n) > h (⟨ n, n ⟩) > h (⟨ d, n ⟩), \end{array}$ so (8) fails for any such n. However, as there are infinitely many $n ⩾ d$ such that $ψ (x_{0}^{n}) ↓$ , we conclude that (8) fails, contrary to the choice of A. This completes the proof. □
Corollary 7.6.
Let A be c.e. and e.u.wtt-a.c. Then any c.e. set B which is $wtt$ -equivalent to A is array computable.
Proof.
By Lemma 7.4 and Theorem 7.5. □

8. Separations

In the preceding sections we have given lower and upper bounds for the class of the c.e. e.u.wtt-a.c. sets in terms of $wtt$ -superlowness and array computability, respectively: any $wtt$ -superlow set is e.u.wtt-a.c. (Corollary 6.3) and any c.e. e.u.wtt-a.c. set is array computable (Corollary 7.6). We conclude our investigations of the e.u.wtt-a.c. sets by showing that these inclusions are proper. In fact, in the case of the second inclusion, we get a slightly stronger result by showing that there is an array computable c.e. Turing degree which contains a c.e. set which is not e.u.wtt-a.c.

We start with the separation of $wtt$ -superlowness and eventually uniform $wtt$ -array computability on the c.e. sets.

8.1. A c.e. e.u.wtt-a.c. set which is not $wtt$ -superlow

In order to separate the c.e. $wtt$ -superlow sets from the c.e. e.u.wtt-a.c. sets, by the Characterization Theorem 4.2, it suffices to show the following.

Theorem 8.1.
There is a maximal set M which is not $wtt$ -superlow.

In the proof of the theorem we use the following sufficient condition for a c.e. set M to be not $wtt$ -superlow. Lemma 8.2.
Assume that M is c.e. and there is a partial computable function ψ and a Turing functional Ψ such that the following hold. $\begin{array}{c} (63) & If Ψ^{M} (x) ↓ then ψ (x) ↓ and Ψ^{M} (x) = Ψ^{M ↾ ψ (x)} (x) (for x ⩾ 0). \\ (64) & The domain of Ψ^{M} is not ω -c.a. \end{array}$ Then M is not $wtt$ -superlow.
Proof of Lemma 8.2 (sketch).
By (63) there is an index e such that the domain of $Ψ^{M}$ coincides with the domain of ${\hat{Φ}}_{e}^{M}$ . So, for any x, $x \in dom (Ψ^{M})$ iff $⟨ e, x ⟩ \in M^{†}$ . By (64) this implies that $M^{†}$ is not ω-c.a. So M is not $wtt$ -superlow by Lemma 6.2. □
Proof of Theorem 8.1.
We construct a c.e. set M, an auxiliary partial computable function ψ, and an auxiliary Turing functional Ψ such that M is maximal and (63) and (64) hold. Then, by Lemma 8.2, the set M has the required properties. The construction is in stages, and we let $M_{s}$ , $ψ_{s}$ and $Ψ_{s}$ denote the finite parts of M, ψ and Ψ, respectively, enumerated by the end of stage s. Moreover, as in other places too, we abbreviate $Ψ_{s}^{M_{s}} (x)$ by $Ψ^{M} (x) [s]$ .

The proof is similar to the proof of Theorem 4.3 though less involved. In particular, in order to make M maximal, we use the maximal set technique based on a priority tree introduced there. We use the notation introduced there as well as the basic observations made there, hence assume the reader to be familiar with the first part of the proof of Theorem 4.3 discussing the maximal set strategy (up to the Maximal Set Lemma).

The strategy to make M not $wtt$ -superlow, i.e., the strategy to ensure that the functional Ψ and its use function ψ satisfy conditions (63) and (64) locally resembles the strategy used in the proof of Theorem 4.3 in order to ensure that $A ⩽_{ibT} M$ . So Ψ and ψ here and the functionals and functions $Ψ_{α}$ and $ψ_{α}$ defined there show some fundamental similarities. Condition (64) is split into the requirements $\begin{aligned} {\hat{R}}_{e} : & If dom (Ψ^{M}) = λ x . {lim}_{s} g_{e_{0}} (x, s) and φ_{e_{1}} is total then there is a \\ number x such that | {s : g_{e_{0}} (x, s + 1) \neq g_{e_{0}} (x, s + 1)} | > φ_{e_{1}} (x) \end{aligned}$ for $e ⩾ 0$ where ${g_{e}}_{e \in ω}$ is a computable numbering of the primitive recursive functions of type $ω^{2} \to {0, 1}$ and where (here and in the following) we assume that $e = ⟨ e_{0}, e_{1} ⟩$ .

The basic strategy for meeting requirement ${\hat{R}}_{e}$ is as follows. We fix a number x, called the target, which we make to witness that requirement ${\hat{R}}_{e}$ is met. So we leave the definition of $ψ (x)$ and $Ψ^{X} (x)$ to the ${\hat{R}}_{e}$ -strategy. We wait for a stage $s_{0}$ such that $φ_{e_{1}, s_{0}} (x)$ is defined. (Note that if there is no such stage then x witnesses that $φ_{e_{1}}$ is not total whence ${\hat{R}}_{e}$ is trivially met.) Once we see stage $s_{0}$ , we pick $φ_{e_{1}} (x) + 1$ many numbers $y_{φ_{e_{1}} (x)} < y_{φ_{e_{1}} (x) - 1} < \dots < y_{0}$ not yet in M, called followers, and let the ${\hat{R}}_{e}$ -strategy decide which of these numbers are enumerated into M. Moreover, we let the use $ψ (x)$ of Ψ on x be a strict upper bound on the followers, say, $ψ (x) = y_{0} + 1$ , declare the strategy to be saturated and let the attack reach its final phase where we guarantee that either $g_{e_{0}}$ does not approximate $Ψ^{M}$ on x or the number of mind changes of the approximation exceeds the allowed bound $φ_{e_{1}} (x)$ . Note that when we start this phase, say, at stage $s_{1}$ , then $Ψ^{M_{s_{1}}} (x)$ is still undefined and none of the followers is in $M_{s_{1}}$ . Now at stage $s + 1 > s_{1}$ act as follows. If $Ψ^{M_{s}} (x) ↑$ and $g_{e_{0}} (x, s + 1) = 0$ then make $Ψ^{M_{s + 1}} (x)$ be defined thereby making the approximation incorrect at stage $s + 1$ . Note that this does not require to change the oracle. If $Ψ^{M_{s}} (x) ↓$ and $g_{e_{0}} (x, s + 1) = 1$ and $\begin{matrix} (65) & | {t ⩽ s : g_{e_{0}} (x, t + 1) \neq g_{e_{0}} (x, t)} | ⩽ φ_{e_{1}} (x) \end{matrix}$ then enumerate the greatest follower into M at stage $s + 1$ that has not been enumerated into M previously. This allows to make $Ψ^{M_{s + 1}} (x)$ to be undefined (thereby making the approximation incorrect at stage $s + 1$ ).

Note that this procedure ensures that the approximation $g_{e_{0}}$ of $Ψ^{M}$ is incorrect on x unless $g_{e_{0}}$ changes its mind on x after stage $s_{1}$ more than $φ_{e_{1}} (x)$ times, whence ${\hat{R}}_{e}$ is met. Namely, if the approximation is correct, then, by using $φ_{e_{1}} (x)$ of the followers we may force the approximation to change $1 + 2 \cdot φ_{e_{1}} (x)$ times by making the computation of Ψ on x alternatingly defined and undefined when the current approximation is correct where the first switch is from undefined to defined and where only a switch from defined to undefined requires to change the current oracle below its use by enumerating a follower into M. So, in fact, the least follower will never be enumerated into M, a fact which will be utilized in the maximal set part of the construction (in particular, it will allow us to argue that $\overline{M}$ is infinite).

In order to make this strategy compatible with the maximal set strategy, for any node α of length e there will be a strategy ${\hat{R}}_{α}$ for meeting requirement ${\hat{R}}_{e}$ . This strategy, which is based on the guess that α is on the true path, may act only if α is accessible and it picks only followers which have current e-state $⩽ α$ . Moreover, it picks followers one-by-one. We will argue that, for the node α of length e on the true path, these modifications will not undermine the basic strategy. In particular for such α where $φ_{e_{0}}$ is defined on the target x, the strategy eventually will become saturated.

Having explained the underlying ideas we can now give the formal construction of M and the auxiliary functional Ψ and function ψ. If a strategy ${\hat{R}}_{α}$ is initialized at stage $s + 1$ then its target (if any) and followers (if any) are cancelled and the strategy is declared to be not saturated. Stage 0 is vacuous, i.e., $M_{0} = \emptyset$ , $Ψ_{0}^{X} (x) ↑$ and $ψ_{0} (x) ↑$ for all numbers x, and all strategies ${\hat{R}}_{α}$ are initialized.
Stage $s + 1$ . A strategy ${\hat{R}}_{α}$ requires attention at stage $s + 1$ if $α ⊑ δ_{s}$ and one of the following holds where $e = | α |$ .
No target is assigned to ${\hat{R}}_{α}$ at the end of stage s.

Target x is assigned to ${\hat{R}}_{α}$ at the end of stage s, $φ_{e_{1}, s} (x) ↓$ , and ${\hat{R}}_{α}$ is not saturated at the end of stage s. Moreover, for the greatest number y such that $y = x$ or y is a follower of ${\hat{R}}_{α}$ at the end of stage s, there is a number $y^{'}$ such that $y < y^{'} ⩽ s$ , $y^{'}$ is greater than any follower of any higher priority strategy ${\hat{R}}_{α^{'}}$ at the end of stage s, and $y^{'} \in ⋃_{{α^{'} : | α^{'} | = | α | and α^{'} ⩽_{L} α}} V_{α^{'}, s}$ (i.e., $y^{'} \notin M_{s}$ and $σ (| α |, y^{'}, s) ⩽ α$ ).

${\hat{R}}_{α}$ is saturated at the end of stage s, x is the target of ${\hat{R}}_{α}$ at the end of stage s and one of the following holds.

$Ψ_{s}^{M_{s}} (x) ↑$ and $g_{e_{0}} (x, s + 1) = 0$ .

$Ψ_{s}^{M_{s}} (x) ↓$ , $g_{e_{0}} (x, s + 1) = 1$ , (65) holds, and there is a follower y of ${\hat{R}}_{α}$ at the end of stage s such that $y \notin M_{s}$ .
Fix the least α (if any) such that ${\hat{R}}_{α}$ requires attention. Declare that ${\hat{R}}_{α}$ receives attention and is active at stage $s + 1$ , and perform the following action according to the case via which ${\hat{R}}_{α}$ requires attention.
Assign $s + 1$ as target to ${\hat{R}}_{α}$ .

Appoint the least $y^{'}$ as in (b) as follower of ${\hat{R}}_{α}$ . Moreover, if there are $φ_{e_{1}} (x) + 1$ followers of ${\hat{R}}_{α}$ then let $ψ_{s} (x) = y^{'} + 1$ and declare ${\hat{R}}_{α}$ to be saturated.

If (A) holds then let $Ψ_{s + 1}^{M_{s}} (x) = 0$ . If (B) holds then enumerate the greatest follower y of ${\hat{R}}_{α}$ such that $y \notin M_{s}$ into M and let $Ψ_{s + 1}^{M_{s + 1}} (x) ↑$ .
In case of (b) or (c), initialize all lower priority strategies ${\hat{R}}_{β}$ ( $α < β$ ) and enumerate all numbers $z ⩽ s$ such that $z \notin M_{s}$ and z is not a follower of any strategy ${\hat{R}}_{β^{'}}$ with $β^{'} ⩽ α$ at stage $s + 1$ into M.

If no strategy ${\hat{R}}_{α}$ requires attention then do nothing.

This completes the construction. In the remainder of the proof we show that the set M has the required properties. This proof uses that the Infinity Lemma and the Maximal Set Lemma hold which were established in the proof of Theorem 4.3 already.

Now, first note that the construction is effective and ${M_{s}}_{s \in ω}$ is a computable enumeration of M. So M is c.e. Similarly, ψ is a partial computable function and Ψ is a Turing functional with computable enumerations ${ψ_{s}}_{s \in ω}$ and ${Ψ_{s}}_{s \in ω}$ , respectively. Moreover, (63) holds. (Namely, assume that $Ψ_{s + 1}^{M_{s + 1}} (x) \neq Ψ_{s}^{M_{s}} (x) ↓$ for some number x and stage s. Then there is a saturated strategy ${\hat{R}}_{α}$ such that ${\hat{R}}_{α}$ has target x and an ${\hat{R}}_{α}$ -follower y is enumerated into M at stage $s + 1$ . Since, by construction, $y < ψ (x) ↓$ , it follows that $M_{s + 1} ↾ ψ (x) \neq M_{s} ↾ ψ (x)$ . Obviously this implies (63).)

So it only remains to show that $\overline{M}$ is infinite and, for any $α ⊏ TP$ , $\overline{M} \subseteq^{} {\hat{V}}_{α}$ (by the Maximal Set Lemma this implies that M is maximal) and that the requirements ${\hat{R}}_{e}$ are met. For this sake we prove a series of claims. Claim 1.
For any number y and any stage s there is at most one node α such that y is an* ${\hat{R}}_{α}$ -follower at the end of stage s. Moreover, if y is an ${\hat{R}}_{α}$ -follower at the end of stage s then $| α | < y ⩽ s$ , $σ (| α |, y) ⩽ σ (| α |, y, s) ⩽ | α |$ , and y is greater than any follower of any higher priority strategy ${\hat{R}}_{β}$ ( $β <_{L} α$ ) at the end of stage s. Finally if y is ${\hat{R}}_{α}$ -follower at stages $s < s^{'}$ then ${\hat{R}}_{α}$ is not initialized at any stage $s^{″}$ such that $s^{'} ⩽ s^{″} ⩽ s^{'}$ (hence y is ${\hat{R}}_{α}$ -follower at any such stage $s^{″}$ ).
Proof.
By a straightforward induction on s. For the proof of the final part note that if ${\hat{R}}_{α}$ is initialized at a stage $s^{″}$ then any follower y appointed after stage $s^{″}$ will correspond to a target appointed after this stage whence $y > s^{″}$ . □
Claim 2.
Assume that y is the least follower of ${\hat{R}}_{α}$ at stage s. Then $y \notin M_{s}$ .
Proof.
For a contradiction assume that $y \in M_{s}$ and let $t_{y} + 1 ⩽ s$ be the stage at which y is enumerated into M. Let $s_{y} + 1 ⩽ s$ be the stage at which y is appointed and let x be the target of ${\hat{R}}_{α}$ at stage $s_{y}$ . Then ${\hat{R}}_{α}$ is neither initialized at stage $s_{y}$ nor at any stage $s^{'} + 1$ with $s_{y} + 1 ⩽ s^{'} + 1 ⩽ s$ . Hence, for any such stage $s^{'}$ , y follows ${\hat{R}}_{α}$ at stage $s^{'} + 1$ and x is the target of ${\hat{R}}_{α}$ at stage $s^{'}$ . It follows that y can be enumerated into M at such a stage $s^{'} + 1$ only by action of ${\hat{R}}_{α}$ whence ${\hat{R}}_{α}$ has to be saturated at stage $t_{y}$ . So we may pick the unique stage $s_{y}^{'}$ such that $s_{y} + 1 ⩽ s_{y}^{'} + 1 < t_{y} + 1$ and ${\hat{R}}_{α}$ becomes saturated at stage $s_{y}^{'} + 1$ . Then $φ_{e_{1}, s^{'}} (x) ↓$ and there are $φ_{e_{1}} (x) + 1$ followers of ${\hat{R}}_{α}$ at stage $s_{y}^{'} + 1$ , say, $y_{0} > y_{1} > \dots > y_{φ_{e_{1}} (x)}$ , where $y = y_{φ_{e_{1}} (x)}$ and none of theses followers is in $M_{s_{y}^{'} + 1}$ . Now, after stage $s_{y}^{'} + 1$ followers are enumerated into M in decreasing order, and this happens only if ${\hat{R}}_{α}$ becomes active via clause (c) in the definition of requiring attention. As observed before this implies that $g_{e_{0}} (x, s)$ has to change at least once before the first follower is enumerated into M and between the enumeration of two followers, $g_{e_{0}} (x, s)$ has to change at least twice. So, for $0 ⩽ k ⩽ φ_{e_{1}} (x)$ , if $y_{k}$ is enumerated into M at stage $s^{'} + 1 ⩽ t_{y} + 1$ then $\begin{matrix} | {t ⩽ s^{'} : g_{e_{0}} (x, t + 1) \neq g_{e_{0}} (x, t)} | ⩾ 1 + 2 k \end{matrix}$ holds. It follows by the choice of $t_{y}$ that $\begin{matrix} | {t ⩽ t_{y} : g_{e_{0}} (x, t + 1) \neq g_{e_{0}} (x, t)} | ⩾ 1 + 2 φ_{e_{1}} (y) > φ_{e_{1}} (y) . \end{matrix}$ But this implies that (65) fails for $s = t_{y}$ . So ${\hat{R}}_{α}$ does not require attention via clause (c) at stage $t_{y} + 1$ whence $y = y_{φ_{e_{1}} (x)}$ is not enumerated into M at stage $M_{t_{y}}$ contrary to the choice of $t_{y}$ . □
Claim 3.
Any strategy ${\hat{R}}_{α}$ on the true path ( $α ⊏ TP$ ) is initialized at most finitely often, requires attention at most finitely often and has a permanent target.
Proof.
Note that the strategies ${\hat{R}}_{β}$ are finitary, i.e., if a strategy ${\hat{R}}_{β}$ is not initialized after some stage s then it will act after stage s only finitely often. So, since strategies require attention only if they are accessible and since there are only finitely many stages at which strategies to the left of $α ⊏ TP$ are accessible, by a straightforward induction on $| α |$ , there is a stage $s_{0}$ such that no strategy ${\hat{R}}_{β}$ with $β ⩽ α$ will be initialized or will require attention after stage $s_{0}$ . Moreover, ${\hat{R}}_{α}$ has a target at stage $s_{0}$ (since otherwise, for the first α-stage $s ⩾ s_{0}$ , ${\hat{R}}_{α}$ will require attention via clause (a) at stage $s + 1$ ) and the target is permanent since ${\hat{R}}_{α}$ is not initialized later. □
Claim 4.
Assume that $\overline{M}$ is infinite and that $α ⊏ TP$ . Then the following hold where $| α | = e = ⟨ e_{0}, e_{1} ⟩$ .
If $φ_{e_{1}}$ is total then ${\hat{R}}_{α}$ is permanently saturated, i.e., ${\hat{R}}_{α}$ becomes saturated at some stage and is not initialized later.

Requirement ${\hat{R}}_{e}$ is met.

$\overline{M} \subseteq^{} {\hat{V}}_{α}$ .

Proof.
(i). Assume that $φ_{e_{1}}$ is total. By Claim 3 fix a stage $s_{0}$ such that ${\hat{R}}_{α}$ is not initialized and does not require attention after stage $s_{0}$ and such that the permanent target x of ${\hat{R}}_{α}$ is defined at stage $s_{0}$ (whence $φ_{e_{1}, s_{0}} (x)$ is defined, too). Then any follower of any strategy ${\hat{R}}_{β}$ with $β ⩽ α$ which is defined at any stage $s ⩾ s_{0}$ is defined at stage $s_{0}$ hence is less than or equal to $s_{0}$ . It follows that ${\hat{R}}_{α}$ is permanently saturated at stage $s_{0}$ . Otherwise, by the Infinity Lemma, there is an α-stage $s > s_{0}$ such that $V_{α, s} ⊈ ω ↾ s_{0} + 1$ hence ${\hat{R}}_{α}$ will require attention via clause (b) at stage $s + 1$ contrary to choice of $s_{0}$ .

(ii). For a contradiction assume that requirement ${\hat{R}}_{e}$ is not met. Then the hypotheses of the requirement are satisfied, i.e., $dom (Ψ^{M}) = λ x . {lim}_{s} g_{e_{0}} (x, s)$ and $φ_{e_{1}}$ is total, but the conclusion fails, whence for all numbers x and all stages s, (65) holds. It follows that, for any sufficiently large stage s, the strategy ${\hat{R}}_{α}$ requires attention via clause (b) at stage $s + 1$ provided that s is an α-stage and ${\hat{R}}_{α}$ has a target x and a follower y at stage s where $y \notin M_{s}$ . Since, by $α ⊏ TP$ , there are infinitely many α-stages it follows by part (i) of the claim and by Claim 2 that there are infinitely many such stages s. So ${\hat{R}}_{α}$ requires attention infinitely often contrary to Claim 3.

(iii). Obviously, there are infinitely many numbers $e^{'} = ⟨ e_{0}^{'}, e_{1}^{'} ⟩$ such that $φ_{e_{1}^{'}}$ is total. So, by part (i) of the claim, there are infinitely many $α^{'} ⊏ TP$ such that ${\hat{R}}_{α^{'}}$ has a permanent follower. So, by Claim 3, there are infinitely many stages s at which a strategy ${\hat{R}}_{α^{'}}$ with $α^{'} ⪯ α$ acts via clause (b) whence any number y such that $y ⩽ s$ and y is not a follower of a strategy ${\hat{R}}_{α^{″}}$ such that $α^{″} ⪯ α$ or $α^{″} ⊏ α$ at the end of stage $s + 1$ will be enumerated into M at stage $s + 1$ (unless y is in $M_{s}$ already). Since, by Claim 3, the strategies ${\hat{R}}_{α^{'}}$ with $α^{'} ⊏ α$ have only finitely many followers during the course of the construction, it follows that almost all numbers y in $\overline{M}$ become a follower of a strategy ${\hat{R}}_{α^{'}}$ with $α^{'} ⪯ α$ at some stage s. But, by construction, this implies that y has e-state $⩽ α$ at stage s whence $y \in {\hat{V}}_{α}$ . □
Claim 5.
There are infinitely many stages s at which some strategy becomes active via clause (b).*
Proof.
For a contradiction fix a stage $s_{0}$ such that no strategy becomes active via clause (b) after stage $s_{0}$ . Then no follower is appointed after stage $s_{0}$ whence any follower is $⩽ s_{0}$ and there is a stage $s_{1} ⩾ s_{0}$ such that no strategy acts via clause (b) or (c) after stage $s_{1}$ . So, by construction, no number $⩾ s_{1}$ is enumerated into M, hence $\overline{M}$ is infinite. But, by Claim 4 (i), this implies that, for infinitely many $α ⊏ TP$ the strategy ${\hat{R}}_{α}$ acts via (b). Contradiction. □
Claim 6.
$\overline{M}$ is infinite.
Proof.
By Claim 2 it suffices to show that there are infinitely many strategies ${\hat{R}}_{α}$ which have a permanent follower. For a contradiction assume not. Fix the node α of lowest priority such that ${\hat{R}}_{α}$ has a permanent follower. Then ${\hat{R}}_{α}$ is initialized only finitely often, hence requires attention only finitely often. So we may fix a stage $s_{0}$ such that no strategy ${\hat{R}}_{β}$ with $β ⩽ α$ becomes active via (b) or (c) after stage $s_{0}$ . On the other hand, by Claim 5, there is a strategy ${\hat{R}}_{β}$ which becomes active via clause (b) after stage $s_{0}$ . So we may fix β of highest priority such that ${\hat{R}}_{β}$ acts via (b) or (c) after stage $s_{2}$ , say, at stage $s + 1$ . Then $α < β$ , ${\hat{R}}_{β}$ has a follower at stage $s + 1$ and, by the minimality of β, ${\hat{R}}_{β}$ is not initialized after stage s. So the followers of ${\hat{R}}_{β}$ at stage $s + 1$ are permanent. Contradiction. □
Claim 7.
M is maximal and not $wtt$ -superlow.
Proof.
As observed before, M is c.e. and (63) holds. So, in order to show that M is maximal, by the Maximal Set Lemma it suffices to show that $\overline{M}$ is infinite and, for any e, $\overline{M} \subseteq^{} {\hat{V}}_{TP ↾ e}$ , and, in order to show that M is not $wtt$ -superlow, it suffices to show that, for $e ⩾ 0$ , requirement ${\hat{R}}_{e}$ is met. But, by Claim 6 and by Claim 4 (iii) and (ii), these properties hold. □

This completes the proof of Theorem 8.1. □
Corollary 8.3.
There is an e.u.wtt-a.c. c.e. set which is not* $wtt$ -superlow.
Proof.
By Theorems 4.2 and 8.1. □

8.2. Separating eventually uniform $wtt$ -array computability from array computability

In this subsection we show that there is an array computable Turing degree which contains a c.e. set which is not e.u.wtt-a.c. By the Characterization Theorem 4.2 it suffices to prove the following theorem.

Theorem 8.4.
There is a c.e. set A such that the Turing degree of A is array computable and such that A is not $wtt$ -reducible to any maximal set.

Before proving the theorem, let us first describe the basic strategy for building a c.e. set which is not $wtt$ -reducible to any maximal set.

A c.e. set A such that A is not $wtt$ -reducible to any maximal set can be defined in stages s as follows (where $A_{s}$ denotes the finite part of A enumerated by the end of stage s and where $A_{0} = \emptyset$ ). It suffices to meet the requirements $\begin{matrix} P_{e} : If A = {\hat{Φ}}_{e_{1}}^{W_{e_{0}}} then W_{e_{0}} is not maximal. \end{matrix}$ for all numbers $e = ⟨ e_{0}, e_{1} ⟩$ .

The strategy for meeting $P_{e}$ is based on the following observation. If $F = {F_{n}}_{n \in ω}$ is a complete disjoint strong array of intervals (i.e., the effectively given finite sets $F_{n}$ are intervals partitioning ω where $min F_{n + 1} = (max F_{n}) + 1$ ) such that $\begin{matrix} (66) & \exists^{\infty} n (| \overline{W_{e_{0}}} \cap F_{n} | ⩾ 2) \end{matrix}$ holds then $W_{e_{0}}$ is not maximal. Namely, assuming (66), the c.e. set Q defined by $\begin{matrix} Q \cap F_{n} = \{\begin{array}{ll} (W_{e_{0}} \cap F_{n}) \cup {μ x \in F_{n} \cap \overline{W_{e_{0}}}} & if F_{n} ⊈ W_{e_{0}}, \\ F_{n} & otherwise \end{array} \end{matrix}$ is a c.e. super set of $W_{e_{0}}$ satisfying $W_{e_{0}} \subset^{\infty} Q \subset^{\infty} ω$ hence witnesses that $W_{e_{0}}$ is not maximal. On the other hand, if, for a complete disjoint strong array of intervals ${F_{n}}_{n \in ω}$ , (66) fails then $\begin{matrix} (67) & \forall^{\infty} n (| \overline{W_{e_{0}}} ↾ (max F_{n}) + 1 | < 2 n) . \end{matrix}$ This leads to the following idea. During the course of the construction we attempt to define a complete disjoint strong array of intervals ${F_{n}}_{n \in ω}$ such that, for any n, there are $2 n + 1$ numbers $x_{n, 0} < x_{n, 1} < \dots < x_{n, 2 n}$ in $F_{n}$ such that ${\hat{φ}}_{e_{1}} (x_{n, 2 n}) ⩽ max F_{n}$ (and where these numbers $x_{n, k}$ are reserved for the strategy to meet $P_{e}$ ). Now, assuming $A = {\hat{Φ}}_{e_{1}}^{W_{e_{0}}}$ we can define such a strong array (since the assumption implies that ${\hat{φ}}_{e_{1}}$ is total). Moreover, if (66) fails, hence (67) holds then, for any n which satisfies the inner clause of (67), we can guarantee $A \neq {\hat{Φ}}_{e_{1}}^{W_{e_{0}}}$ by enumerating (some of) the numbers $x_{n, 0} < x_{n, 1} < \dots < x_{n, 2 n}$ into A. Namely, assuming that $A = {\hat{Φ}}_{e_{1}}^{W_{e_{0}}}$ , for almost all stages s we have that $| \overline{W_{e_{0}, s}} ↾ (max F_{n}) + 1 | < 2 n$ and $A_{s} ↾ (max F_{n}) + 1 = {\hat{Φ}}_{e_{1}, s}^{W_{e_{0}, s}} ↾ (max F_{n}) + 1$ . But, since ${\hat{φ}}_{e_{0}} (x_{n, k}) ⩽ max F_{n}$ , at any such stage s we may force an additional number $y ⩽ max F_{n}$ to enter $W_{e_{0}}$ after stage s by enumerating x into A. Since there are less than $2 n$ numbers $y ⩽ max F_{n}$ which are not yet in $W_{e_{0}}$ at stage s whereas there are $2 n + 1$ numbers $x_{n, k}$ , $A \neq {\hat{Φ}}_{e_{1}}^{W_{e_{0}}}$ must hold.

Now we are ready to prove Theorem 8.4. Proof of Theorem 8.4.
By a tree argument, we construct a c.e. set A with the required properties. The finite part of A enumerated by the end of stage s is denoted by $A_{s}$ . $A_{0} = \emptyset$ .

In order to ensure that A is not $wtt$ -reducible to any maximal set and that $deg (A)$ is a.c., it suffices to meet the requirements $\begin{matrix} P_{e} : If A = {\hat{Φ}}_{e_{1}}^{W_{e_{0}}} then W_{e_{0}} is not maximal. \end{matrix}$ (where $e = ⟨ e_{0}, e_{1} ⟩$ ) and $\begin{matrix} N_{e} : If Φ_{e}^{A} is total then Φ_{e}^{A} is h -c.a. for h (n) = n + 1 . \end{matrix}$ respectively (for $e ⩾ 0$ ).

We call a requirement infinitary if its hypothesis is true. We need guesses which $N$ -requirements are infinitary. So we use the full binary tree $T = {0, 1}^{}$ as the priority tree. Then, for a node α of length $> e$ , $α (e) = 0$ codes the guess that requirement $N_{e}$ is infinitary.

Define the computable length function l by $\begin{matrix} l (e, s) = max {y : \forall x < y (Φ_{e, s}^{A_{s}} (x) ↓)} . \end{matrix}$ Then the guess $δ_{s}$ at which of the first s $N$ -requirements are infinitary made at stage $s + 1$ is defined as follows. Inductively define α-stages* for each node α as follows. Each stage $s ⩾ 0$ is a λ-stage. If s is an α-stage, then we call s α-expansionary if $l (| α |, s) > l (| α |, t)$ for all α-stages $t < s$ , and we let s be an $α 0$ -stage if s is α-expansionary and we let s be an $α 1$ -stage if s is an α-stage but not an $α 0$ -stage. Then $δ_{s} \in T$ is the unique string α of length s such that s is an α-stage. Moreover, we say that α is accessible at stage $s + 1$ if $α ⊏ δ_{s}$ , i.e., if s is an α-stage and $| α | ⩽ s$ .

The true path $f : ω \to {0, 1}$ of the construction is defined by $\begin{matrix} f (n) = \{\begin{array}{ll} 0 & if there are infinitely many (f ↾ n) -expansionary stages \\ 1 & otherwise. \end{array} \end{matrix}$ Note that f is the leftmost path through T visited infinitely often, i.e., for any n, $\begin{matrix} (68) & \forall^{\infty} s (f ↾ n ⩽ δ_{s}) and \exists^{\infty} s (δ_{s} ↾ n ⊏ f) . \end{matrix}$ Moreover, since $\begin{matrix} (69) & Φ_{e}^{A} total \Rightarrow lim_{s \to \infty} l (e, s) = ω \end{matrix}$ it follows that, for infinitary $N_{e}$ , $f (e) = 0$ .

For each node α of length e there is a strategy $P_{α}$ for $P_{e}$ which is based on the guess α.

At stage s any strategy $P_{α}$ is in one of the following states: n-expanding or n-diagonalizing for some n. If $P_{α}$ is n-expanding (n-diagonalizing) for some n then we say $P_{α}$ is expanding (diagonalizing). The rank of $P_{α}$ at stage s, denoted by $r_{s}^{α}$ , is the coded pair $⟨ | α |, m ⟩$ where m is the number of unfrozen intervals associated with $P_{α}$ at the end of stage s. If $P_{α}$ is n-expanding at stage s then the intervals $F_{n^{'}}^{α}$ with $n^{'} < n$ are defined and $P_{α}$ works on defining $F_{n}^{α}$ by first appointing the followers $x_{n, 0}^{α} < x_{n, 1}^{α} < \dots < x_{n, 2 n}^{α}$ one after the other and then by waiting for ${\hat{φ}}_{e_{1}, s} (x_{n, 2 n}^{α})$ to be defined in order to complete the definition of $F_{n}^{α}$ .

If a strategy $P_{α}$ is initialized then all intervals and followers associated with it are cancelled and the state of $P_{α}$ is reset to “0-expanding”. At any stage s such that $δ_{s} ⩽ α$ , $P_{α}$ is initialized (in particular all $P$ -strategies are initialized at stage 0). In addition $P_{α}$ may be initialized at stage $s + 1$ by the action of the acting strategy $P_{β}$ . The latter can happen only if $β ⊏ α$ (note that if $β <_{L} α$ then $P_{α}$ is initialized automatically since $β ⊏ δ_{s}$ ). If $P_{β}$ acts in order to diagonalize (i.e., according to clause (i) or (ii) below) then all $P_{α}$ with $β ⊏ α$ are initialized. Otherwise, i.e., if $P_{β}$ acts in order to expand, then only those $P_{α}$ with $β ⊏ α$ are initialized where $| α |$ is greater than the rank of $P_{β}$ .

If a strategy is initialized then it has to start all over again. In addition to initialization there will be freezing and partial cancellation. This affects only some of the intervals and the work on the current interval to be defined, respectively. If an interval is frozen then it cannot be used for diagonalization later (hence its followers cannot be enumerated into A later). Similarly all of the followers of an interval under construction may be cancelled. In this case the construction of this interval has to be started all over again with new followers greater than the current stage. There are two events which may lead to freezing of an α-interval $F_{n}^{α}$ or of the followers $x_{n, k}^{α}$ of $P_{α}$ : first if a lower priority strategy $P_{β}$ with $α ⊏ β$ acts by diagonalization and enumerates a number into A which is less than one of the followers of $F_{n}^{α}$ or one of the followers $x_{n, k}^{α}$ , respectively; second if the current approximation $δ_{s}$ of the true path moves to the left of the guess at the true path based on which the interval $F_{n}^{α}$ was (or is being) built. For the latter case we associate each interval with such a guess. If $P_{α}$ is diagonalizing then it is protected against freezing.

If a strategy $P_{α}$ is initialized then all intervals and followers associated with it are cancelled and the state of $P_{α}$ is reset to “0-expanding”. At any stage s such that $δ_{s} ⩽ α$ , $P_{α}$ is initialized (in particular all $P$ -strategies are initialized at stage 0). In addition $P_{α}$ may be initialized at stage $s + 1$ by the action of the acting strategy. Finally, any interval $F_{n}^{α}$ is associated with a guess γ. If $α ⊏ δ_{s}$ and $δ_{s} < γ$ then $F_{n}^{α}$ becomes frozen at the end of stage s unless $P_{α}$ is n-diagonalizing (or $F_{n}^{α}$ is frozen already). Freezing may also be caused by the acting strategies (see below).

At the end of any stage s, initialize all strategies $P_{α}$ such that $δ_{s} ⩽ P_{α}$ . Moreover if $P_{α}$ is n-expanding and there is an unfrozen interval $F_{n^{'}}^{α}$ of $P_{α}$ with guess $γ_{n^{'}}^{α}$ such that $δ_{s} ↾ r_{s}^{α} + 1 < γ_{n^{'}}^{α}$ then, for the least such $n^{'}$ , freeze all intervals $F_{n^{″}}^{α}$ with $n^{'} ⩽ n^{″} < n$ and cancel any follower $x_{n, k}^{α}$ which is defined. Similarly, if $P_{α}$ is n-expanding, $x_{n, 0}^{α}, \dots, x_{n, k}^{α}$ ( $k ⩾ 0$ ) are the current followers of $P_{α}$ of order n and $δ_{s} ↾ r_{s}^{α} + 1 < δ_{t_{k^{'}}} ↾ r_{t_{k^{'}}}^{α} + 1$ for all $k^{'} ⩽ k$ where $t_{k^{'}} + 1$ is the stage at which $x_{n, k^{'}}^{α}$ became appointed then cancel $x_{n, 0}^{α}, \dots, x_{n, k}^{α}$ .

Then stage $s + 1$ is as follows.
Requiring attention and the corresponding potential action. $P_{α}$ ( $| α | = e$ ) requires attention at stage $s + 1$ if $α ⊏ δ_{s}$ and one of the following holds.

$P_{α}$ is not diagonalizing and there is an unfrozen interval $F_{n}^{α}$ such that $\begin{matrix} (70) & | \overline{W_{e_{0}, s}} ↾ (max F_{n}^{α}) + 1 | < 2 n . \end{matrix}$

Corresponding action. For the least such n, declare that $P_{α}$ is n-diagonalizing.

Initialize all strategies $P_{β}$ such that $α ⊏ β$ . Moreover, for any strategy $P_{β}$ such that $β ⊏ α$ , $P_{β}$ is expanding, say, $n_{β}$ -expanding, and there is an $n^{'} ⩽ n_{β}$ such that there is a follower $x_{n^{'}, k^{'}}^{β} > x_{n, 0}^{α}$ , fix the least such $n^{'}$ , freeze all intervals $F_{n^{″}}^{α}$ with $n^{'} ⩽ n^{″} < n_{β}$ (if not frozen already) and cancel all β-followers $x_{n_{β}, k}^{β}$ of order $n_{β}$ which are defined.

There is an n such that $P_{α}$ is n-diagonalizing, $\begin{matrix} (71) & A_{s} ↾ x_{n, 2 n}^{α} + 1 = {\hat{Φ}}_{e_{1}, s}^{W_{e_{0}, s}} ↾ x_{n, 2 n}^{α} + 1, \end{matrix}$ and there is a follower $x_{n, k}^{α}$ in $F_{n}^{α} ∖ A_{s}$ .

Corresponding action. Put the greatest follower $x_{n, k}^{α} \in F_{n}^{α} ∖ A_{s}$ into A.

Initialize all strategies $P_{β}$ such that $α ⊏ β$ . Moreover, for any strategy $P_{β}$ such that $β ⊏ α$ , $P_{β}$ is expanding, say, $n_{β}$ -expanding, and there is an $n^{'} ⩽ n_{β}$ such that there is a follower $x_{n^{'}, k^{'}}^{β} > x_{n, 0}^{α}$ , fix the least such $n^{'}$ , freeze all intervals $F_{n^{″}}^{α}$ with $n^{'} ⩽ n^{″} < n_{β}$ (if not frozen already) and cancel all β-followers $x_{n_{β}, k}^{β}$ of order $n_{β}$ which are defined.

(i) does not hold, there is an n such that $P_{α}$ is n-expanding and the follower $x_{n, 2 n}^{α}$ is not yet defined.

Corresponding action. For the least k such that $x_{n, k}^{α}$ is not yet defined let $x_{n, k}^{α} = s + 1$ . Declare that $x_{n, k}^{α}$ becomes associated with $P_{α}$ as (n-)follower (of order k).

Initialize all strategies $P_{β}$ such that $α ⊏ β$ and $| β | > r_{s}^{α}$ .

(i) does not hold, there is an n such that $P_{α}$ is n-expanding, the follower $x_{n, 2 n}^{α}$ is defined and ${\hat{φ}}_{e_{1}, s} (x_{2 n}^{α})$ is defined as well.

Corresponding action. Let $F_{n}^{α} = [x_{n}, s]$ where $x_{0} = 0$ and $x_{n} = 1 + max F_{n - 1}^{α}$ for $n > 0$ . Assign the guess $γ_{n}^{α}$ to $F_{n}^{α}$ where $\begin{matrix} γ_{n}^{α} = min {δ_{t_{k}} ↾ r_{t_{k}}^{α} + 1 : k ⩽ 2 n} \end{matrix}$ where $t_{k} + 1$ is the stage at which $x_{n, k}^{α}$ became appointed. Declare that $P_{α}$ is $(n + 1)$ -expanding.

Initialize all strategies $P_{β}$ such that $α ⊏ β$ and $| β | > r_{s}^{α}$ .

Selecting the strategy which will act. If there is a strategy which requires attention then, for any $α ⊏ δ_{s}$ such that $P_{α}$ requires attention let $p_{s}^{α} = 2 | α |$ if α requires attention via one of the clauses (i) or (ii) and let $p_{s}^{α} = 2 r_{s}^{α} + 1$ if α requires attention via clause (iii) or (iv). Then, from the strategies which require attention, the strategy $P_{α}$ with minimal value $p_{s}^{α}$ receives attention and becomes active and the action corresponding to the clause according to which $P_{α}$ requires attention is performed.

VERIFICATION. Claim 1.
Assume that $P_{α}$ is n-diagonalizing at stage $s + 1$ and not initialized after stage s. Then $P_{α}$ is n-diagonalizing at all stage $s^{'} ⩾ s + 1$ and $P_{α}$ acts only finitely often.
Proof.
By assumption and by construction, strategy $P_{α}$ is n-diagonalizing at all stage $s^{'} ⩾ s + 1$ and $F_{n}^{α} [s^{'}] = F_{n}^{α} [s + 1]$ hence $x_{n, k}^{α} [s^{'}] = x_{n, k}^{α} [s + 1]$ for all $k ⩽ 2 n$ . So, after stage $s^{'}$ , $P_{α}$ can act only according to clause (ii) and, whenever it acts, one of the $2 n + 1$ followers $x_{n, 0}^{α} [s^{'}], \dots, x_{n, 2 n}^{α} [s^{'}]$ is enumerated into A. So this can happen at most $2 n + 1$ times. □
Claim 2.
Assume that $P_{f ↾ e}$ becomes active infinitely often. Then $\begin{matrix} (72) & lim_{s \to \infty} r_{s}^{f ↾ e} = ω . \end{matrix}$
Proof.
For a contradiction assume that the claim fails. Fix r minimal such that, for some number e, $\begin{matrix} (73) & P_{f ↾ e} becomes active infinitely often and \exists^{\infty} s (r_{s}^{f ↾ e} ⩽ r) . \end{matrix}$ Fix the unique numbers e and m such that $r = ⟨ e, m ⟩$ (note that $e ⩽ r$ ). Then, by the minimality of r, e is the unique number satisfying (73) whence $\begin{matrix} (74) & \forall e^{'} \neq e (P_{f ↾ e^{'}} becomes active infinitely often \Rightarrow \forall^{\infty} s (r_{s}^{f ↾ e^{'}} > r)) . \end{matrix}$ Moreover, $\begin{matrix} (75) & \forall^{\infty} s (r ⩽ r_{s}^{f ↾ e}) and \exists^{\infty} s (r = r_{s}^{f ↾ e}) . \end{matrix}$ Since, by the definition of the true path, $f ↾ r < δ_{s}$ for almost all s and since, by the definition of the rank, $r_{s}^{f ↾ e^{'}} > r$ for all $e^{'} > r$ and all s, by the above we may fix a stage $s_{0} > r$ such that, for any $s ⩾ s_{0}$ , the following hold. $\begin{array}{c} (76) & f ↾ r < δ_{s} \\ (77) & r ⩽ r_{s}^{f ↾ e} \\ (78) & \forall e^{'} \neq e (P_{f ↾ e^{'}} does not become active at stage s + 1 or r_{s}^{f ↾ e^{'}} > r) \end{array}$

By (76), (77) and (78), any strategy $P_{f ↾ e^{'}}$ with $e^{'} ⩽ r$ can be initialized after stage $s_{0}$ only if some strategy $P_{f ↾ e^{″}}$ with $e^{″} < e^{'}$ becomes active via clause (i) or (ii). So, by Claim 1, it follows by a straightforward induction on $e^{'}$ that there is a stage $s_{1} > s_{0}$ such that no $P_{f ↾ e^{'}}$ with $e^{'} ⩽ r$ is initialized or acts according to (i) or (ii) after stage $s_{1}$ . Hence, in particular, any interval assigned to $P_{f ↾ e}$ after stage $s_{1}$ is permanent. (In the following let $F_{n}^{α}$ ( $n ⩾ 0$ ) denote the permanent intervals of $P_{f ↾ e}$ if they exist.) Moreover, since $P_{f ↾ e}$ acts infinitely often we may deduce that $P_{f ↾ e}$ is expanding at all stages $s > s_{1}$ . So we fix $n_{s}$ such that $P_{f ↾ e}$ is $n_{s}$ -expanding at stage s ( $s > s_{1}$ ). Then $n_{s}$ is nondecreasing in s. Moreover, if ${n_{s} : s > s_{1}}$ is bounded then, for $n = max {n_{s} : s > s_{1}}$ , the followers of $P_{f ↾ e}$ are cancelled infinitely often. So (in any case) we may fix a stage $s_{2} > s_{1}$ such that, for $s ⩾ s_{2}$ , the least $P_{f ↾ e}$ -follower $x_{n_{s}, 0}^{f ↾ e} [s]$ of order $n_{s}$ at the end of stage s has been appointed after stage $s_{1}$ or is undefined.

Next observe that, by the second part of (75) and by the definition of the rank, there are at most m permanent $P_{f ↾ e}$ -intervals which are never frozen, say, $F_{p_{0}}^{f ↾ e}, \dots, F_{p_{m^{'} - 1}}^{f ↾ e}$ where $p_{0} < \dots < p_{m^{'} - 1}$ and $m^{'} ⩽ m + 1$ . Moreover, we may pick a stage $s_{3} > s_{2}$ such that $F_{p_{m^{'} - 1}}^{f ↾ e}$ is defined at stage $s_{3}$ . Then, for any $s > s_{3}$ and for the number $n_{s}$ such that $P_{f ↾ e}$ is $n_{s}$ -expanding at stage s, $n_{s} > p_{m^{'} - 1}$ . So, in order to get the desired contradiction, it suffices to show that there is a stage $s > s_{3}$ such that $F_{n_{s}}^{f ↾ e}$ becomes defined and is never frozen.

For this sake we first observe that there is a stage s such that $\begin{matrix} (79) & s > s_{3} and s is an (f ↾ r) -stage and r = r_{s}^{f ↾ e} . \end{matrix}$

The existence of such a stage is shown as follows. Since there are infinitely many $(f ↾ r)$ -stages and infinitely many stages s such that $r = r_{s}^{f ↾ e}$ , we may pick two consecutive $(f ↾ r)$ -stages $s^{'}$ and $s^{″}$ such that $s_{3} < s^{'} < s^{″}$ and such that there is a stage $t \in [s^{'}, s^{″}]$ such that $r = r_{t}^{f ↾ e}$ . Fix the least such t. We claim that $r = r_{s^{'}}^{f ↾ e}$ or $r = r_{s^{″}}^{f ↾ e}$ (or both). For a contradiction assume not. Then $s^{'} < t < s^{″}$ and $\begin{matrix} (80) & r_{t}^{f ↾ e} < r_{s^{'}}^{f ↾ e} and r_{t}^{f ↾ e} < r_{s^{″}}^{f ↾ e} . \end{matrix}$ Now, by the second part of (80), there must be an interval $F_{n}^{f ↾ e}$ with $n ⩾ n_{t}$ which is defined and not frozen at stage $s^{″}$ . On the other hand, by the first part of (80), some $(f ↾ n)$ -interval becomes frozen at stage t whence, by the freezing process, all $(f ↾ e)$ -followers of order $n_{t}$ are cancelled at stage t. So all of the followers $x_{n, k}^{f ↾ e}$ in $F_{n}^{f ↾ e}$ are appointed at stages $t^{'}$ with $t < t^{'} < s^{″}$ . Since, for any such stage $t^{'}$ , $f ↾ r <_{L} δ_{t^{'}} ↾ r$ it follows that $f ↾ r <_{L} γ_{n}^{f ↾ e}$ for the guess $γ_{n}^{f ↾ e}$ associated with $F_{n}^{f ↾ e}$ . Since, by the choice of $s^{″}$ , $f ↾ r ⊑ δ_{s^{″}} ↾ r_{s^{″}}^{f ↾ e}$ , it follows that $F_{n}^{f ↾ e}$ becomes frozen at stage $s^{″}$ contrary to choice of this interval. This completes the proof of (79).

Now fix a stage s as in (79). It suffices to show that $F_{n_{s}}^{f ↾ e}$ becomes defined and is never frozen. Fix $k ⩾ 0$ maximal such that $x_{n_{s}, k - 1}^{f ↾ e}$ is defined at stage s. Note that, by $s > s_{0}$ , $P_{f ↾ e}$ becomes active at any stage $s^{'} + 1 ⩾ s + 1$ such that $s^{'}$ is an $(f ↾ e)$ -stage and $r = r_{s^{'}}^{f ↾ e}$ . Now, first assume that $k < 2 n_{s} + 1$ . Then, at stage $s + 1$ , $x_{n_{s}, k}^{f ↾ e} = s$ becomes appointed and all strategies $P_{α}$ with $f ↾ r < α$ are initialized. Since, by the choice of $s_{1}$ , no strategy $P_{α}$ with $α ⩽ f ↾ r$ enumerates any number into A after stage $s_{1}$ , it follows that no number $⩽ s$ will enter A after stage s. So, in particular, if $k + 1 < 2 n_{s} + 1$ and $s^{'}$ is the least $(f ↾ e)$ -stage $> s$ then $r = r_{s^{'}}^{f ↾ e}$ (note that the rank of $P_{f ↾ e}$ can grow only if a new $(f ↾ e)$ -interval becomes assigned and that the latter can happen only at $(f ↾ e)$ -accessible stages) and the next follower $x_{n_{s}, k + 1}^{f ↾ e} = s^{'}$ becomes appointed at stage $s^{'} + 1$ . Moreover, again, all strategies $P_{α}$ with $f ↾ r < α$ are initialized whence no number $⩽ x_{n_{s}, k + 1}^{f ↾ e}$ may enter A after stage $s^{'}$ . It follows by induction that there is an $f ↾ r$ -stage $s^{″} > s$ such that $x_{n_{s}, 2 n_{s}}^{f ↾ e} = s^{″}$ becomes appointed at stage $s^{″} + 1$ and no number $< x_{n_{s}, 2 n_{s}}^{f ↾ e}$ enters A after stage $s^{″}$ . Since $P_{f ↾ e}$ acts infinitely often, it follows that at the next stage where the strategy acts, $F_{n_{s}}^{f ↾ e}$ becomes defined. Moreover, since no number $< x_{n_{s}, 2 n_{s}}^{f ↾ e}$ will enter A later, $F_{n_{s}}^{f ↾ e}$ will not be frozen by the action of any strategy. Finally, since $x_{n_{s}, k + 1}^{f ↾ e}$ became appointed at an $(f ↾ r)$ -accessible stage $s + 1$ where $r = r_{s}^{f ↾ e}$ , it follows that $F_{n_{s}}^{f ↾ e}$ is associated with the guess $γ_{n_{s}}^{f ↾ e} = f ↾ r$ whence $F_{n_{s}}^{f ↾ e}$ will no be frozen at all. This completes the proof that $F_{n_{s}}^{f ↾ e}$ becomes defined and is never frozen in the case of $k < 2 n_{s} + 1$ .

If $k = 2 n_{s} + 1$ then the argument is similar. Consider the stage $t + 1 < s + 1$ at which $x_{n_{s}, 2 n_{s}}^{f ↾ e}$ becomes defined. Since $x_{n_{s}, 2 n_{s}}^{f ↾ e}$ does not become cancelled by the end of stage s, as in the proof of (79) we may argue that t is an $(f ↾ r)$ -stage and $r = r_{t}^{f ↾ e}$ . So all strategies $P_{α}$ with $f ↾ r < α$ are initialized at stage $t + 1$ . So, as in the first case, we may argue that no number $⩽ x_{n_{s}, 2 n_{s}}^{f ↾ e}$ will be put into A after stage t, that $F_{n_{s}}^{f ↾ e}$ eventually becomes defined, and that $F_{n_{s}}^{f ↾ e}$ will never be frozen. □
Claim 3.
$P_{f ↾ e}$ is initialized at most finitely often.
Proof.
The proof is by induction on e. Fix e. Since $f ↾ e < δ_{s}$ for all sufficiently large s, by the inductive hypothesis we may fix a stage $s_{0} > e$ such that no strategy $P_{f ↾ e^{'}}$ with $e^{'} < e$ is initialized after stage $s_{0}$ and such $f ↾ e < δ_{s}$ for all $s ⩾ s_{0}$ . Moreover, w.l.o.g. we may assume that no strategy $P_{f ↾ e^{'}}$ with $e^{'} < e$ acts after stage $s_{0}$ unless it acts infinitely often. So, by Claim 1, $P_{f ↾ e}$ , will be initialized at a stage $s + 1 > s_{0}$ only if a strategy $P_{f ↾ e^{'}}$ with $e^{'} < e$ acts via clause (iii) or (iv) at this stage and $r_{s}^{f ↾ e^{'}} < e$ . Since $P_{f ↾ e^{'}}$ must be a strategy which can act infinitely often, it follows by Claim 2 that this can happen only finitely often. □
Claim 4.
Assume that $P_{f ↾ e}$ acts infinitely often. Then $P_{e}$ is met.
Proof.
By Claim 3 let $s_{0}$ be the greatest stage at which $P_{f ↾ e}$ is initialized. Then, at the end of stage $s_{0}$ , no interval is associated with $P_{f ↾ e}$ and $P_{f ↾ e}$ waits for 0-expansion. Moreover, any interval which becomes associated with $P_{f ↾ e}$ after stage $s_{0}$ is permanent. So let $F_{n}^{f ↾ e}$ be the nth interval permanently associated with $P_{f ↾ e}$ (if defined). Since, by assumption and by Claim 2, $\begin{matrix} (81) & lim_{s \to \infty} r_{s}^{f ↾ e} = ω \end{matrix}$ and since intervals become associated in order of their indices, it follows that $F_{n}^{f ↾ e}$ is defined for all n and, by construction, ${F_{n}^{f ↾ e}}_{n \in ω}$ is a complete disjoint strong array of intervals.

So, as pointed out in the description of the basic strategy for building a c.e. set which is not $wtt$ -reducible to any maximal set given after the statement of Theorem 8.4, in order to show that $P_{e}$ is met it suffices to show that (67) fails for $F_{n} = F_{n}^{f ↾ e}$ , i.e., that $\begin{matrix} (82) & \exists^{\infty} n (| \overline{W_{e_{0}}} ↾ (max F_{n}^{f ↾ e}) + 1 | ⩾ 2 n) \end{matrix}$ holds. We do this by showing that there are infinitely many permanent intervals which are never frozen and that any such interval satisfies the inner clause of (82): $\begin{array}{c} (83) & \exists^{\infty} n (F_{n}^{f ↾ e} is never frozen) \\ (84) & If F_{n}^{f ↾ e} is never frozen then | \overline{W_{e_{0}}} ↾ (max F_{n}^{f ↾ e}) + 1 | ⩾ 2 n . \end{array}$

For a proof of (83), for a contradiction, assume that there are only finitely many permanent $(f ↾ e)$ -intervals which are never frozen, say, $F_{n_{0}}^{f ↾ e}$ , $\dots$ , $F_{n_{m - 1}}^{f ↾ e}$ where $n_{0} < \dots < n_{m - 1}$ and let $r = ⟨ e, m ⟩$ . We will show that ${lim inf}_{s \to \infty} r_{s}^{f ↾ e} ⩽ r$ contrary to (81). For given s it suffices to find a stage $s^{″} > s$ such that $r_{s^{″}}^{f ↾ e} = r$ . Fix $s^{'} > s$ minimal such that the intervals $F_{n_{0}}^{f ↾ e}$ , $\dots$ , $F_{n_{m - 1}}^{f ↾ e}$ are defined at stage $s^{'}$ and let $s^{″}$ be the least stage $> s^{'}$ such that the interval with least index n which eventually becomes frozen after stage $s^{'}$ becomes frozen at stage $s^{″}$ . Then, by construction, for any $n^{'} > n$ such that $F_{n^{'}}^{f ↾ e}$ is defined at stage $s^{″}$ , $F_{n^{'}}^{f ↾ e}$ becomes frozen at stage $s^{″}$ , too (unless $F_{n^{'}}^{f ↾ e}$ had been frozen before already). Hence the only intervals which exist at stage $s^{″}$ and are not frozen are the intervals $F_{n_{0}}^{f ↾ e}$ , $\dots$ , $F_{n_{m - 1}}^{f ↾ e}$ . So $r_{s^{″}}^{f ↾ e} = ⟨ e, m ⟩ = r$ , which completes the proof of (83).

It remains to show (84). For a contradiction assume that $F_{n}^{f ↾ e}$ is never frozen and $| \overline{W_{e_{0}}} ↾ (max F_{n}^{f ↾ e}) + 1 | < 2 n$ . By Claims 1, 2 and 3 we may fix a stage t such that, for $e^{'} ⩽ e$ , $P_{e^{'}}$ is not initialized after stage t, $P_{e^{'}}$ does not act via clause (i) or (ii) after stage t, and – if $P_{e^{'}}$ acts infinitely often – then, for any $s ⩾ t$ , $P_{e^{'}}$ is expanding at stage s and $r_{s}^{f ↾ e^{'}} > e$ . Since, by assumption, $P_{e}$ acts infinitely often, it follows that $P_{e}$ is expanding at all stages $⩾ t$ and does not require attention via clause (i) after stage t (since, otherwise, it would become active via clause (i) contrary to choice of t). On the other hand, by the choice of n, for all sufficiently large stages s, $F_{n}^{f ↾ e}$ is defined and unfrozen at stage s and (70) holds. So $P_{e}$ requires attention via clause (i) at almost all stages $s > t$ . A contradiction. This completes the proof of (84) and the proof of Claim 4. □
Claim 5.
$P_{e}$ is met.
Proof.
W.l.o.g. we may assume that $A = {\hat{Φ}}_{e_{1}}^{W_{e_{0}}}$ (whence, in particular, ${\hat{φ}}_{e_{1}}$ is total). By Claim 4 it suffices to show that $P_{f ↾ e}$ acts infinitely often. For a contradiction assume that this is not the case. Then we may fix a stage $s_{0} > e$ such that $P_{f ↾ e}$ does not act after stage $s_{0}$ and such that the intervals associated with $P_{f ↾ e}$ at the end of stage $s_{0}$ – say, $F_{0}^{f ↾ e}, \dots, F_{n - 1}^{f ↾ e}$ ( $n ⩾ 0$ ) – are permanent, and such that the intervals associated with $P_{f ↾ e}$ which are not frozen at stage $s_{0}$ – say, $F_{n_{0}}^{f ↾ e}, \dots, F_{n_{m - 1}}^{f ↾ e}$ (where $n_{0} < \dots n_{m - 1} ⩽ n - 1$ and $m ⩽ n$ ) – do not become frozen later, and such that the followers of order n associated with $P_{f ↾ e}$ at the end of stage $s_{0}$ – say, $x_{n, 0}^{f ↾ e}, \dots, x_{n, k - 1}^{f ↾ e}$ ( $0 ⩽ k ⩽ 2 n + 1$ ) – are not cancelled later. Note that this implies that $r = r_{s}^{f ↾ e}$ for all $s ⩾ s_{0}$ where $r = r_{s_{0}}^{f ↾ e}$ .

Now, by Claims 1, 2 and 3, fix an $(f ↾ e)$ -stage $s_{1} > s_{0}$ such that no strategy $P_{f ↾ e^{'}}$ with $e^{'} ⩽ e$ is initialized after stage $s_{1} - 1$ , no strategy $P_{f ↾ e^{'}}$ with $e^{'} < e$ acts via clause (i) or (ii) after stage $s_{1}$ , and, for any $e^{'} < e$ such that $P_{f ↾ e^{'}}$ acts after stage $s_{1}$ , $r_{s}^{f ↾ e^{'}} > r$ for all $s ⩾ s_{1}$ . Moreover, by $A = {\hat{Φ}}_{e_{1}}^{W_{e_{0}}}$ and by the totality of ${\hat{φ}}_{e_{1}}$ , w.l.o.g. we may assume that $\begin{matrix} A ↾ 1 + max F_{n - 1}^{f ↾ e} = A_{s_{1}} ↾ 1 + max F_{n - 1}^{f ↾ e} = {\hat{Φ}}_{e_{1}, s_{1}}^{W_{e_{0}, s_{1}}} ↾ 1 + max F_{n - 1}^{f ↾ e} \end{matrix}$ (provided that $n > 0$ ) and ${\hat{φ}}_{e_{1}, s_{1}} (x_{n, k - 1}^{f ↾ e}) ↓$ (provided that $k = 2 n + 1$ ).

Note that $s_{1}$ is chosen so that $P_{f ↾ e}$ will become active at any stage $s + 1 > s_{1}$ at which it requires attention. So, by $s_{0} < s_{1}$ , $P_{f ↾ e}$ will not require attention after stage $s_{1}$ .

Now, in order to get the desired contradiction, we distinguish the following two cases depending of the state of $P_{f ↾ e}$ at stage $s_{1}$ .

Case 1: $P_{f ↾ e}$ is diagonalizing at stage $s_{1}$ . Fix $t < s_{1}$ maximal such that $P_{f ↾ e}$ is not diagonalizing at stage t. Then $P_{f ↾ e}$ acts via clause (i) at stage $t + 1$ and it becomes $n^{'}$ -diagonalizing for some $n^{'}$ at this stage. Moreover, by the maximality of t, $P_{f ↾ e}$ is not initialized after stage t, hence is $n^{'}$ -diagonalizing at all stages $s > t$ , the interval $F_{n^{'}}^{f ↾ e} [t]$ is permanent and so are the $2 n^{'} + 1$ -followers $x_{n^{'}, 0}^{f ↾ e} [t], \dots, x_{n^{'}, 2 n^{'}}^{f ↾ e} [t]$ . Moreover, by construction, none of these followers is in $A_{t + 1}$ and $\begin{matrix} (85) & | \overline{W_{e_{0}, t}} ↾ (max F_{n^{'}}^{f ↾ e} [t]) + 1 | < 2 n^{'} . \end{matrix}$ It follows by $A = {\hat{Φ}}_{e_{1}}^{W_{e_{0}}}$ that at any sufficiently large $(f ↾ e)$ -stage s such that there is a follower $x_{n^{'}, k}^{f ↾ e} [t]$ left which has not yet been enumerated into A, $P_{f ↾ e}$ will require attention according to clause (ii). Since, by the choice of $s_{1}$ , $P_{f ↾ e}$ does not require attention after stage $s_{1}$ , there must be stages $t < t_{2 n^{'}} < t_{2 n^{'} - 1} < \dots < t_{0}$ such that $P_{f ↾ e}$ acts according to clause (ii) at stage $t_{k^{'}} + 1$ and the follower $x_{n^{'}, k^{'}}^{f ↾ e} [t]$ is enumerated into A at stage $t_{k^{'}} + 1$ . So, $A_{t_{k^{'}} + 1} (x_{n^{'}, k^{'}}^{f ↾ e} [t]) \neq A_{t_{k^{'}}} (x_{n^{'}, k^{'}}^{f ↾ e} [t])$ . By condition (71) in (ii) this implies $\begin{matrix} {\hat{Φ}}_{e_{1}, t_{k^{'}}}^{W_{e_{0}, t_{k^{'}}}} (x_{n^{'}, k^{'}}^{f ↾ e} [t]) \neq {\hat{Φ}}_{e_{1}, t_{k^{'} - 1}}^{W_{e_{0}, t_{k^{'} - 1}}} (x_{n^{'}, k^{'}}^{f ↾ e} [t]) \end{matrix}$ where both sides are defined (and where $t_{- 1}$ is the least stage $s > t_{0}$ such that ${\hat{Φ}}_{e_{1}, s}^{W_{e_{0}, s}} ↾ x_{n^{'}, 2 n^{'}}^{α} [t] + 1 = {\hat{Φ}}_{e_{1}}^{W_{e_{0}}} ↾ x_{n^{'}, 2 n^{'}}^{α} [t] + 1$ ). Since ${\hat{φ}}_{e_{1}} (x_{n^{'}, k^{'}}^{f ↾ e} [t]) ⩽ max F_{n^{'}}^{f ↾ e} [t]$ for all $k^{'} ⩽ 2 n^{'}$ , this implies that $2 n^{'} + 1$ numbers $⩽ max F_{n^{'}}^{f ↾ e} [t]$ have to enter $W_{e_{0}}$ after stage t. But this contradicts (85).

Case 2: $P_{f ↾ e}$ is expanding at stage $s_{1}$ . Since $P_{f ↾ e}$ neither acts nor is initialized after stage $s_{0}$ and since $s_{0} < s_{1}$ , it follows that $P_{f ↾ e}$ is n-expanding at all stages $s ⩾ s_{1}$ . Moreover, for any such stage s, $x_{n, 0}^{f ↾ e}, \dots, x_{n, k - 1}^{f ↾ e}$ are the followers of order n associated with $P_{f ↾ e}$ at stage s. In order to get the desired contradiction, it suffices to show that $P_{f ↾ e}$ requires attention after stage $s_{1}$ . This is done by distinguishing the following two cases. If $k < 2 n + 1$ then $P_{f ↾ e}$ requires attention via clause (iii) at the first stage $s + 1 > s_{1}$ at which $P_{f ↾ e}$ is accessible. If $k = 2 n + 1$ then $P_{f ↾ e}$ requires attention via clause (iv) at the first stage $s + 1 > s_{1}$ at which $P_{f ↾ e}$ is accessible and at which ${\hat{φ}}_{e_{1}, s} (x_{n, k - 1}^{f ↾ e})$ is defined. Note that, by $A = {\hat{Φ}}_{e_{1}}^{W_{e_{0}}}$ , such a stage must exist. This completes the proof of Case 2 and the proof of Claim 5. □
Claim 6.
$N_{e}$ is met.
Proof.
W.l.o.g. assume that $Φ_{e}^{A}$ is total. It suffices to define a computable function g such that, for any $n ⩾ 0$ , $\begin{matrix} (86) & lim_{k \to \infty} g (n, k) = Φ_{e}^{A} (n) & | {k : g (n, k + 1) \neq g (n, k)} | ⩽ n + 1 . \end{matrix}$ By assumption, $f (e) = 0$ . So $α ⊏ f$ for $α = (f ↾ e) 0$ . Pick the least α-stage $s_{0}$ such that $\begin{matrix} (87) & \forall s ⩾ s_{0} (α < δ_{s}) \end{matrix}$ and $\begin{matrix} (88) & \forall β ⊑ α (P_{β} does not act via clause (i) or (ii) after stage s_{0}), \end{matrix}$ and let $s_{0} < s_{1} < s_{2} < \dots$ be the α-stages $⩾ s_{0}$ . Then, for $n < m$ , $l (e, s_{m}) > n$ hence $Φ_{e, s_{m}}^{A_{s_{m}}} (n) ↓$ (hence $φ_{e}^{A_{s_{m}}} (n) ↓$ ). Hence if we let $\begin{matrix} g (n, k) = Φ_{e, s_{n + 1 + k}}^{A_{s_{n + 1 + k}}} (n) \end{matrix}$ then g is total and computable and ${lim}_{k \to \infty} g (n, k) = Φ_{e}^{A} (n)$ . So, for a proof of (86), it suffices to show that $\begin{matrix} (89) & | {k : A_{s_{n + 1 + k + 1}} ↾ φ_{e}^{A_{s_{n + 1 + k}}} (n) \neq A_{s_{n + 1 + k}} ↾ φ_{e}^{A_{s_{n + 1 + k}}} (n)} | ⩽ n + 1 . \end{matrix}$ For a proof of (89) we first show by induction on n that, for any n, there exist at most n followers at the end of stage $s_{n}$ which may enter A later whence $\begin{matrix} (90) & | (A ↾ s_{n} + 1) ∖ (A_{s_{n}} ↾ s_{n} + 1) | ⩽ n \end{matrix}$ (since followers appointed after stage $s_{n}$ are greater than $s_{n}$ ). For $n = 0$ the claim is obvious if $s_{0} = 0$ . So w.l.o.g. assume that $s_{0} > 0$ . Since, by the choice of $s_{0}$ no strategy $P_{β}$ with $β ⩽ α$ enumerates a follower into A after stage $s_{0}$ , it suffices to show that no strategy $P_{γ}$ with $α < γ$ has a follower at the end of stage $s_{0}$ . If $α <_{L} γ$ then this is obvious since $P_{γ}$ becomes initialized at the α-stage $s_{0}$ . So assume that $α ⊏ γ$ . Fix the greatest α-stage $s < s_{0}$ . By the minimality of $s_{0}$ , (87) or (88) fails for s in place of $s_{0}$ . So $P_{γ}$ is initialized at stage s or stage $s + 1$ , respectively, and $P_{γ}$ does not act at stage $s + 1$ . So $P_{γ}$ does not have a follower at the end of stage $s + 1$ . Since s is the greatest α-stage $< s_{0}$ and $P_{γ}$ may act only at stages where α is accessible, $P_{γ}$ does not have any follower at the end of stage $s_{0}$ , either. This completes the proof of the case $n = 0$ . For the inductive step assume that $n > 0$ and that there are at most $n - 1$ followers at the end of stage $s_{n - 1}$ which may enter A later. Since at stage $s_{n - 1} + 1$ at most one new follower is appointed and since any follower appointed at a stage $s + 1$ such that $s_{n - 1} + 1 < s + 1 ⩽ s_{n}$ has to be appointed to a strategy $P_{γ}$ with $α <_{L} γ$ hence will be initialized at the end of stage $s_{0}$ , the claim for n follows immediately.

Now, by (90), for a proof of (89) it suffices to show that, for any $k ⩾ 0$ , such that $\begin{matrix} (91) & A_{s_{n + 1 + k + 1}} ↾ φ_{e}^{A_{s_{n + 1 + k}}} (n) \neq A_{s_{n + 1 + k}} ↾ φ_{e}^{A_{s_{n + 1 + k}}} (n) \end{matrix}$ we have $\begin{matrix} (92) & A_{s_{n + 1 + k + 1}} ↾ s_{n + 1} + 1 \neq A_{s_{n + 1 + k}} ↾ s_{n + 1} + 1 . \end{matrix}$ For a contradiction assume that the latter is not true. Fix k minimal such that (91) holds but (92) fails, and fix x minimal such that $x \in A_{s_{n + 1 + k + 1}} ∖ A_{s_{n + 1 + k}}$ . Then $\begin{matrix} s_{n + 1} < x < φ_{e}^{A_{s_{n + 1 + k}}} (n) ⩽ s_{n + 1 + k} . \end{matrix}$ Next fix β such that x is a $P_{β}$ -follower, say, $x = x_{m, p}^{β}$ . Note that, by the choice of $s_{0}$ , $α < β$ . In fact, since at stage $s_{n + 1 + k}$ all strategies $P_{γ}$ with $α <_{L} γ$ are initialized, $α ⊏ β$ . So $P_{β}$ may act only at stages where α is accessible, hence x is enumerated into A at stage $s_{n + 1 + k} + 1$ and (since $s_{n + 1} < x < s_{n + 1 + k}$ ) there is some $k^{'} < k$ such that $x = x_{m, p}^{β} = s_{n + 1 + k^{'}} + 1$ becomes appointed as $P_{β}$ -follower at stage $s_{n + 1 + k^{'}} + 1$ . Since, by the latter, $φ_{e}^{A_{s_{n + 1 + k^{'}}}} (n) ⩽ x$ whereas, by the choice of x, $x < φ_{e}^{A_{s_{n + 1 + k}}} (n)$ it follows that there must be a number $k^{″}$ such that $k^{'} ⩽ k^{″} < k$ and (91) holds for $k^{″}$ in place of k whence, by the minimality of k, (92) holds for $k^{″}$ in place of k, too. So fix $x^{'} ⩽ s_{n + 1}$ and s such that $s_{n + 1 + k^{″}} ⩽ s < s_{n + 1 + k^{″}}$ and $x^{'}$ is enumerated into A at stage $s + 1$ , and let $P_{β^{'}}$ be the strategy which enumerates $x^{'}$ into A at stage $s + 1$ . Now, in order to get the desired contradiction, consider the relation between β and $β^{'}$ . Since the $P_{β}$ -follower x exists at stage s and is enumerated into A after stage $s + 1$ , $P_{β}$ is not initialized at stage $s + 1$ and x neither becomes frozen nor becomes cancelled at stage $s + 1$ . By the former, $β ⩽ β^{'}$ . First assume $β < β^{'}$ . Then $P_{β}$ has to be m-diagonalizing at stage s since $x^{'} < x$ and $x = x_{m, p}^{β}$ is neither frozen nor cancelled at stage $s + 1$ . So we may fix the greatest stage $t + 1 < s$ at which $P_{β}$ acts according to clause (i) (thereby becoming m-diagonalizing at stage $t + 1$ ) then $B_{β^{'}}$ becomes initialized at stage $t + 1$ . Since, by the maximality of $t + 1$ , x is a $P_{β}$ -follower at stage $t + 1$ hence $x < t + 1$ . Since $x^{'} < x$ it follows that $x^{'}$ becomes cancelled at stage $t + 1$ , a contradiction. This leaves the case that $β^{'} = β$ . Then x and $x^{'}$ are $P_{β}$ -followers at stage $s_{n + 1 + k}$ hence both associated with the same interval $F_{m}^{β}$ . But, by construction, such followers are enumerated in decreasing order. So, by $x^{'} < x$ , x had to be enumerated first contrary to choice of x and $x^{'}$ . So this case is impossible, too. Hence (91) implies (92), which completes the proof of (89) and the proof of Claim 6. □

By Claims 5 and 6 all requirements are met. This completes the proof of the theorem. □
Corollary 8.5.
There is an array computable c.e. Turing degree a which contains a computably enumerable set which is not eventually uniformly $wtt$ -array computable.
Proof.
By the Characterization Theorem 4.2 and Theorem 8.4. □

9. Questions and comments

Having introduced some new classification tools including a hierarchy of bounded lowness notions, we have an infinite number of questions we might ask. We mention a couple.

One separation we have not yet succeeded in finding is a Turing degree containing an e.u.wtt-a.c. c.e. set which does not contain a $wtt$ -superlow set. There likely should be a domination/non-domination property corresponding to this question. What is it?

Some of the notions considered in this paper – like $wtt$ -superlowness and $wtt$ -jump traceability – are the $wtt$ -analogs of notions previously defined for Turing reducibility. The reader should note that the analogous game can be played from the $wtt$ -structures back to the Turing degrees. In particular, we may consider the Turing analog of the notion which turned out to be central for our investigations, namely, eventually uniform $wtt$ -array computability.

Definition 9.1.

A set A is eventually uniformly array computable if there exist computable functions $g, k : ω^{2} \to {0, 1}$ and a computable order h such that, for all e, x, $\begin{array}{c} (93) & A^{'} (x) = lim_{s \to \infty} g (x, s), \\ (94) & k (x, s) ⩽ k (x, s + 1), \\ (95) & k (x, s) = 1 \Rightarrow | {t ⩾ s : g (x, t + 1) \neq g (x, t)} | ⩽ h (x), \\ (96) & \forall e (Φ_{e}^{A} total \Rightarrow \forall^{\infty} x \exists s (k (⟨ e, x ⟩, s) = 1)) \end{array}$ (where $A^{'}$ is the general halting set for A, i.e., $A^{'} = {⟨ e, x ⟩ : Φ_{e}^{A} (x) ↓}$ ).

This notion and similar ones seem to yield classes of degrees of complexity different than any seen before. They appear worth investigating.

Footnotes

Acknowledgements

Downey is partially supported by Marsden Fund of New Zealand. The results of this paper were obtained whilst Downey was an Alexander von Humboldt Fellow at the University of Heidelberg.

References

Ambos-Spies, Multiple permitting and array noncomputability, in: Sailing Routes in the World of Computation, Lecture Notes in Computer Science, Springer International Publishing, 2018, pp. 30–39. doi:10.1007/978-3-319-94418-0_3.

Ambos-Spies,

Downey and

Monath, Some notes on the

w t t

-jump, Proceedings of the Asian Logic Meeting, (in press).

B.A.

Anderson and

B.F.

Csima, A bounded jump for the bounded Turing degrees, Notre Dame Journal of Formal Logic 55(2) (2014), 245–264. doi:10.1215/00294527-2420660.

B.A.

Anderson,

B.F.

Csima and

K.M.

Lange, Bounded low and high sets, Archive for Mathematical Logic 56(5–6) (2017), 507–521. doi:10.1007/s00153-017-0537-8.

Barmpalias,

Downey and

Greenberg, Working with strong reducibilities above totally ω-c.e. and array computable degrees, Transactions of the American Mathematical Society 362(2) (2010), 777–813. doi:10.1090/S0002-9947-09-04910-1.

Barmpalias,

Downey and

McInerney, Integer valued betting strategies and Turing degrees, Journal of Computing and System Sciences 81 (2015), 1387–1412. doi:10.1016/j.jcss.2015.05.001.

Cholak,

Coles,

Downey and

Herrmann, Automorphisms of the lattice of

π_{0}^{1}

classes: Perfect thin classes and anr degrees, Transactions of the American Mathematical Society 353 (2001), 4988–4924.

Cholak,

Downey and

Stob, Automorphisms of the lattice of recursively enumerable sets: Promptly simple sets, Trans. Amer. Math. Soc. 332 (1992), 555–570. doi:10.1090/S0002-9947-1992-1097164-6.

Coles,

Downey and

LaForte, Notes on wtt-jump and ordinal notations, 1998, Unpublished Manuscript.

10.

Csima,

Downey and

K.M.

Ng, Limits on jump inversion for strong reducibilities, J. Symbolic Logic 76(4) (2011), 1287–1296. doi:10.2178/jsl/1318338849.

11.

A.M.

Donald, Classes of recursively enumerable sets and degrees of unsolvability, Mathematical Logic Quarterly 12(1) (1966), 295–310. doi:10.1002/malq.19660120125.

12.

Downey and

Greenberg, Turing degrees of reals of positive effective packing dimension, Information Processing Letters 108 (2008), 298–303. doi:10.1016/j.ipl.2008.05.028.

13.

Downey and

Greenberg, A Hierarchy of Turing Degrees: A Transfinite Hierarchy of Lowness Notions in the Computably Enumerable Degrees, Unifying Classes, and Natural Definability, Annals of Mathematics, Studies, Princeton University Press, 2020.

14.

Downey and

D.R.

Hirschfeldt, Algorithmic Randomness and Complexity, Springer, New York, 2010.

15.

Downey,

Jockusch and

Stob, Array nonrecursive sets and multiple permitting arguments, in: Recursion Theory Week, Oberwolfach, 1989, Lecture Notes in Mathematics, Vol. 1432, Springer, Berlin, 1990, pp. 141–174. doi:10.1007/BFb0086116.

16.

Downey,

Jockusch and

Stob, Array nonrecursive degrees and genericity, in: Computability, Enumerability, Unsolvability, London Math. Soc. Lecture Note Ser., Vol. 224, Cambridge Univ. Press, Cambridge, 1996, pp. 93–104.

17.

Downey and

Jockusch, Jr., T-degrees, jump classes and strong reducibilities, Transactions of the American Math. Soc. 301 (1987), 103–136. doi:10.1090/S0002-9947-1987-0879565-X.

18.

Y.L.

Ershov, A certain hierarchy of sets. III, Algebra i Logika 9(1) (1970), 34–51.

19.

Friedberg, Three theorems on recursive enumeration, J. Symbolic Logic 23 (1958), 309–316. doi:10.2307/2964290.

20.

Friedberg and

Rogers, Jr., Reducibility and completeness for sets of integers, Z. Math. Logik Grung. Math. 5 (1959), 117–125. doi:10.1002/malq.19590050703.

21.

R.M.

Friedberg, Two recursively enumerable sets of incomparable degrees of unsolvability (solution of Post’s problem, 1944), Proceedings of the National Academy of Sciences 43(2) (1957), 236–238. doi:10.1073/pnas.43.2.236.

22.

Gerla, A generalization of the Ershov hierarchy, Unione Matematica Italiana. Bollettino. B. Serie V 16(2) (1979), 765–778.

23.

Gold, Language identification in the limit, Information and Control 10 (1967), 447–474. doi:10.1016/S0019-9958(67)91165-5.

24.

Greenberg and

Turetsky, Strong jump-traceability, Bulletin Symbolic Logic 24 (2018), 147–164. doi:10.1017/bsl.2017.38.

25.

Harrington and

Soare, Post’s program and incomplete recursively enumerable sets, Proc. Natl. Acad. Sci, USA 88 (1991), 10242–10246. doi:10.1073/pnas.88.22.10242.

26.

Kummer, Kolmogorov complexity and instance complexity of recursively enumerable sets, SIAM Journal on Computing 25(6) (1996), 1123–1143. doi:10.1137/S0097539794268789.

27.

Lerman, Degrees of Unsolvability, Springer-Verlag, 1985.

28.

A.A.

Mučnik, On the unsolvability of the problem of reducibility in the theory of algorithms, Doklady Akademii Nauk SSSR 108 (1956), 194–197.

29.

Nies, Reals which compute little, in: Logic Colloquium ’02, Lecture Notes in Logic, Vol. 27, Assoc. Symbol. Logic, La Jolla, CA, 2006, pp. 261–275.

30.

Nies,

Stephan and

Terwijn, Randomness, relativization and Turing degrees, Journal of Symbolic Logic 70 (2005), 515–535. doi:10.2178/jsl/1120224726.

31.

Odifreddi, Classical Recursion Theory, Vol. II, North-Holland, 1999.

32.

E.L.

Post, Recursively enumerable sets of positive integers and their decision problems, Bulletin of the American Mathematical Society 50(5) (1944), 284–316. doi:10.1090/S0002-9904-1944-08111-1.

33.

R.W.

Robinson, Simplicity of recursively enumerable sets, The Journal of Symbolic Logic 32(2) (1967), 162–172. doi:10.2307/2271653.

34.

R.I.

Soare, Automorphisms of the lattice of recursively enumerable sets, part I: Maximal sets, Annals of Math. 80 (1974), 80–120. doi:10.2307/1970842.

35.

R.I.

Soare, Recursively Enumerable Sets and Degrees, Springer-Verlag, Berlin, 1987.

36.

Tennenbaum, Degrees of unsolvability and the rate of growth of functions, Notices Amer. Math. Soc 8 (1961), 608.

37.

Terwijn and

Zambella, Algorithmic randomness and lowness, The Journal of Symbolic Logic 66 (2001), 1199–1205. doi:10.2307/2695101.

38.

Wu and

Wu, Bounded jump and the high/low hierarchy, in: Theory and Applications of Models of Computation, Lecture Notes in Comput. Sci., Vol. 11436, Springer, 2019, pp. 647–658.

39.

C.E.M.

Yates, Three theorems on the degree of recursively enumerable sets, Duke Math. J. 32 (1965), 461–468.

Lowness properties for strong reducibilities and the computational power of maximal sets

Abstract

Keywords

1. Introduction

1.1. Post’s programme and maximal sets

3 It is not important here to define these sets, save to say that they are important classes of c.e. sets.

Theorem 1.2 (Barmpalias, Downey and Greenberg [5]).

1.5. The wtt -jump

1.6. The main theorem

1.8. A new hierarchy of bounded lowness

3. Basic definitions and properties

Definition 3.1 ([13]).

Lemma 3.5 ([13], Lemma 3.6).

6.1. Wtt -Superlow sets are eventually uniformly wtt -array computable

Lemma 7.3 ([1]).

Lemma 7.4 ([1]).

8.1. A c.e. e.u.wtt-a.c. set which is not wtt -superlow

Footnotes

Acknowledgements

References

³
It is not important here to define these sets, save to say that they are important classes of c.e. sets.

1.5. The $wtt$ -jump

6.1. $Wtt$ -Superlow sets are eventually uniformly $wtt$ -array computable

8.1. A c.e. e.u.wtt-a.c. set which is not $wtt$ -superlow