Maximality and collapse in the hierarchy of α -c.a. degrees

Abstract

In (A Hierarchy of Turing Degrees: A Transfinite Hierarchy of Lowness Notions in the Computably Enumerable Degrees, Unifying Classes, and Natural Definability (2020), Annals of Mathematics Studies, Princeton University Press), Downey and Greenberg define a transfinite hierarchy of ${low}_{2}$ c.e. degrees – the totally α-c.a. degrees, for appropriately small ordinals α. This new hierarchy is of particular interest because it has already given rise to several natural definability results, and provides a new definable antichain in the c.e. degrees. Several levels of this hierarchy contain maximal degrees. We discuss how maximality interacts with upper cones, and the related notion of hierarchy collapse in upper cones. For example, we show that there is a totally ω-c.a. degree above which there is no maximal totally ω-c.a. degree.

Keywords

maximal degrees upper cones

1. Introduction

One underlying theme in mathematical logic is calibrating mathematical objects in various hierarchies. In computability theory this method also seems to give alignment between syntactical and algorithmic complexity of the objects in question. For instance, the arithmetical hierarchy aligns itself with iterations of the Turing Jump.

In this spirit, building on earlier work of Downey, Greenberg and Weber [4], Downey and Greenberg [3,5] introduced a new transfinite hierarchy of (mainly computably enumerable) degrees based around considerations about the “mind-change” functions of computable approximations of $Δ_{2}^{0}$ functions. In [5], it is argued that the hierarchy is both natural and significant because the hierarchy

Unifies the combinatorics of a wide class of constructions, both in the Turing degrees and in areas of applications of computability theory, such as effective model theory and algorithmic randomness.

Gives a number of new examples of natural definability of degree classes in the c.e. degrees.

Gives such results within the ${low}_{2}$ c.e. degrees; classes to which general metatheorems do not pertain.

Of course, this “mind change” hierarchy was built on the ideas of many early studies. These studies began with Ershov [8–10], and Epstein, Haass, and Kramer [7], which extended the idea of a d.c.e. set, which is one with a computable approximation where elements begin outside, can enter, and then might leave. Indeed, the Limit Lemma says that each set $A ⩽_{T} \emptyset^{'}$ has an approximation where each element might enter and leave a finite number of times. The idea of Ershov, and Epstein et al. was to give a fine-grained analysis to calibrate such approximations. Further work along these lines can be found in work of Selivanov [14], and many authors, such as Shore, Lachlan and others, have studied d.c.e. and ω-c.a. sets and degrees. Some of this work we mention below. The key insight in the Downey–Greenberg Hierarchy work is the use of canonical notations (as explained below) to provide a foundation for the classification work.

In [5], a number of apparently difficult and natural questions were left open about the structure of the hierarchy. Several of these questions involved notions of maximality in this hierarchy. In this paper we solve a number of these questions, and hence this paper complements the monograph [5] in an essential way. The overarching goal of the present paper is to understand the extent to which the hierarchy collapses, and to identify unusual or interesting features.

1.1. Background: Array computable, and totally ω-c.a. degrees

The Shoenfield Limit Lemma [15] states that a function $f : ω \to ω$ is computable from the halting problem $\emptyset^{'}$ if and only if it has a computable approximation: a uniformly computable sequence $⟨ f_{s} ⟩$ such that for all x, ${lim}_{s} f_{s} (x) = f (x)$ (in the sense that for all but finitely many s, $f_{s} (x) = f (x)$ ). The mind-change function of this approximation is $λ x . # {s ∣ f_{s} (x) \neq f_{s + 1} (x)}$ , the number of times the approximation ‘changes its mind’ on value x. The intuition is that if a function only has approximations that require many changes, then it is relatively complicated. Indeed, a function is weak-truth-table reducible to $\emptyset^{'}$ if and only if it has a computable approximation whose mind-change function is bounded by a computable function. Such functions are also called ω-computably approximable.

A c.e. Turing degree d is array computable [6] if and only if every function $f \in d$ has a computable approximation whose mind-change function is bounded by the identity function (any fixed order function, a computable, non-decreasing and unbounded function, would do). Array computability captures the dynamics of multiple permitting characterising several constructions in computability. Thus, for example, a c.e. Turing degree is array computable if and only if it is the degree of a perfect, thin $Π_{1}^{0}$ class, if and only if it contains a c.e. set of maximal Kolmogorov complexity [12], if and only if it does not have a strong minimal cover in the Turing degrees [11]. Several other equivalences are listed in [5].

Weakening array computability, a c.e. degree is totally ω-computably approximable if every function $f \in d$ is ω-computably approximable (c.a. for short), a notion suggested by Joseph Miller. The difference is that we no longer require a uniform bound on the mind-change functions. Like array computability, this notion captures the dynamic combinatorics of a number of constructions, involving, for example, presentations of left-c.e. reals. Further, one such construction gives a natural definition of the class of totally ω-c.a. degrees within the c.e. degrees: these are the degrees that do not bound a critical triple, a lattice-theoretic notion useful in embedding lattices in the c.e. degrees.

1.2. Totally α-c.a. degrees

Considerations of embeddings of the 1-3-1 lattice, closely related to critical triples, led Downey and Greenberg to define a further weakening of the notion of totally ω-c.a. degrees, and by generalisation, to a transfinite hierarchy of such lowness-like notions. The generalisation utilises the Ershov hierarchy. Much like complexity related to the mind-change function, Ershov calibrates the complexity of a computable approximation, and by extension, of the function being approximated, by considering well-founded witnesses to the approximation settling down. Namely, for a computable ordinal α, an α-computable approximation is a computable approximation $⟨ f_{s} ⟩$ of a $Δ_{2}^{0}$ function f, accompanied by a uniformly computable sequence $⟨ o_{s} ⟩$ of functions $o_{s} : ω \to α$ such that for all x and s, $o_{s + 1} (x) ⩽ o_{s} (x)$ and if $f_{s + 1} (x) \neq f_{s} (x)$ then $o_{s + 1} (x) < o_{s} (x)$ . Thus ${⟨ o_{s} (x) ⟩}_{s}$ is a ‘counting down’ in α, which guarantees that $⟨ f_{s} (x) ⟩$ will stabilise. The longer α is, the more space for mind-changes the approximation has. A function is α-c.a. (or $Δ_{α}^{- 1}$ ) if it has an α-computable approximation, and a c.e. degree is totally α-c.a. if every $f \in d$ is α-c.a.

An important caveat is that care has to be taken in the choice of the computable presentation of an ordinal α; such a presentation of course is required to make sense of computability of functions with range α. In general, many presentations are very much nonequivalent, in that they yield different classes of functions and degrees. Indeed, every ${low}_{2}$ c.e. degree is totally $ω^{2}$ -c.a. for some particular presentation of the ordinal $ω^{2}$ . The point is that the complexity of an approximation can be coded into the presentation of $ω^{2}$ ; such a presentation can be bad, for example, in that we cannot effectively tell, for each element, which copy of ω it lies in. When defining the notion of totally α-c.a. degrees, it is important to choose canonical presentations of the ordinals α; these yield robust notions that also behave well with respect to extending or shrinking the ordinals. A choice of canonical representations can be easily made below the ordinal $ϵ_{0}$ by requiring Cantor normal form to be effective. The details are given in [5]. Such canonical copies also allow us to characterise the lower levels of the hierarchy in terms of mind-change functions: a function is $ω^{n + 1}$ -c.a. if and only if it has a computable approximation whose mind-change function is bounded by some $ω^{n}$ -c.a. function.

1.3. Hierarchy collapse

One of the first questions to ask is whether the hierarchy is proper. At what levels is there collapse, in that no new degrees inhabit the level? This question was settled in [5]. For $α ⩽ ϵ_{0}$ , call a degree d properly totally α-c.a. if it is totally α-c.a. but not totally β-c.a. for any $β < α$ . Recall that an ordinal is closed under ordinal addition if and only if it is an ordinal power of ω.

Theorem 1.1 ([5]).

Let $α ⩽ ϵ_{0}$ . There is a properly totally α-c.a. degree if and only if α is a power of ω.

Thus, the first proper levels of the hierarchy are the totally ω-c.a., totally $ω^{2}$ -c.a., $ω^{3}, ω^{4}, \dots, ω^{ω}, ω^{ω + 1}, \dots$ .

Next, it is natural to check what happens to the hierarchy in upper and lower cones. In this paper we show that the hierarchy does not collapse in lower cones. Henceforth, all degrees are c.e.

Theorem 1.2.
Let $α < γ ⩽ ϵ_{0}$ be powers of ω. Every properly totally γ-c.a. degree bounds a properly totally α-c.a. degree.

We remark that the degree produced for Theorem 1.2 is proper in a strong way: it is not uniformly totally α-c.a. See Section 6.

We do not know whether no collapse occurs in upper cones. We prove the following two results:
Theorem 1.3.
Let $α < β ⩽ ϵ_{0}$ be powers of ω, and suppose that $β ⩾ α^{ω}$ . Then every totally α-c.a. degree is bounded by a properly totally β-c.a. degree.

In particular, above every totally ω-c.a. degree there are properly $ω^{ω}$ -c.a. degrees, properly $ω^{ω + 1}$ -c.a. degrees, and so on.
Theorem 1.4.
Let $α < ϵ_{0}$ be a power of ω. Above every totally α-c.a. degree there is a totally $(α^{3} \cdot ω)$ -c.a. degree which is not totally α-c.a.

That is, above every totally $ω^{δ}$ -c.a. degree there is one which is totally $ω^{δ \cdot 3 + 1}$ -c.a. but not $ω^{δ}$ -c.a. So for example, above every totally ω-c.a. degree there is a totally $ω^{4}$ -c.a. degree which is not totally ω-c.a.; we do not know if this degree can always be made totally $ω^{2}$ -c.a., or totally $ω^{3}$ -c.a., or not. So we ask:
Question 1.5.
Is every totally ω-c.a. degree bounded by a properly totally $ω^{2}$ -c.a. degree?

If the degree we start with is superlow, then the answer is positive; see Section 4.
1.4. Maximal degrees

In [5] it is shown that for every $α ⩽ ϵ_{0}$ which is a power of ω, there are maximal totally α-c.a. degrees: degrees a which are totally α-c.a., but such that no $b > a$ is totally α-c.a. We remark that since the totally ω-c.a. degrees are definable in the c.e. degrees, this gives us a naturally definable antichain in the c.e. degrees. The only other known example of such an antichain is the collection of maximal contiguous degrees [2].

In [5] the following is proved:

Theorem 1.6 ([5]).

Let $α ⩽ ϵ_{0}$ . Every totally $ω^{α}$ -c.a. degree lies strictly below a totally $ω^{α + 1}$ -c.a. degree.

As a corollary we see:

If $α < β ⩽ ϵ_{0}$ are powers of ω, then no totally α-c.a. degree can be maximal totally β-c.a.; and

Every maximal totally α-c.a. degree is properly totally α-c.a.

Thus maximality is closely related to hierarchy collapse. Indeed, to prove Theorem 1.3, we show:

Theorem 1.7.
Let $α, β ⩽ ϵ_{0}$ be powers of ω, and suppose that $β ⩾ α^{ω}$ . Then every totally α-c.a. degree is bounded by a maximal totally β-c.a. degree.

On the other hand we show
Theorem 1.8.
Let $α ⩽ ϵ_{0}$ be a power of ω. There is a totally α-c.a. degree which is not bounded by any maximal totally α-c.a. degree.

Toward proving Theorem 1.8 we examine ‘maximal covers’, see Theorem 5.1.

Similarly to Question 1.5, we ask:
Question 1.9.
Is every totally ω-c.a. degree bounded by a maximal totally $ω^{2}$ -c.a. degree?

A positive solution will necessarily be non-uniform. Again, we get a positive answer for superlow degrees.

Solving these problems required several new techniques. For instance, the proof of Theorem 1.7 is the first example of a construction of degrees in one of these bounded classes where there is infinitary positive activity along the true path of the strategy tree. We believe that our techniques will have wider applications.
1.4.1. Notation; enumerating functions

Throughout, we mostly follow the notation from [5]. In particular, we use lower-case Greek letters to denote the use of the corresponding upper-case functionals. We interpret the use differently, depending on the situation:

If a functional Φ is given to us, or the oracle X is given to us, then for any input x, the use $φ (x)$ is the smallest number not queried. So a computation $Φ (X, x) [s]$ is preserved if $X_{s} ↾ φ_{s} (x)$ is preserved. In this case we always assume that the domain of $Φ (X)$ is an initial segment of ω.

When a functional Λ that we build applies to a set D that we are enumerating, then the use is the only number queried. So if we define a computation $Λ_{s} (D_{s}, x)$ with use $λ_{s} (x)$ , then the computation is valid until we enumerate $λ_{s} (x)$ into D. When we set the use to be $- 1$ we mean that $Λ (D, x) ↓$ no matter what D is.

Sometimes, functionals that we build will take more than one oracle; some we build, some we don’t. We will usually apply the second convention, but this will be specified.

For diagonalising against α-c.a. functions, we use enumerations of approximations. We use the terminology from [5, Section 2.1.2]. An $(α + 1)$ -computable approximation $⟨ f_{s}, o_{s} ⟩$ is tidy if $f_{0}$ is the constant function 0, and for all n and s, if $o_{s} (n + 1) < α$ then $o_{s} (n) < α$ . Such an approximation is eventually α-computable if for all n there is some s such that $o_{s} (n) < α$ . If the approximation is not eventually α-computable then for all but finitely many n, for all s, $o_{s} (n) = α$ and so $f = {lim}_{s} f_{s}$ is eventually constant 0. Thus, the limit of any tidy $(α + 1)$ -computable approximation is α-c.a. We can think of these as partial α-computable approximations; $o_{s} (n) = α$ means that we have not yet given an ordinal bound for the α-computable approximation. Tidy approximations can be enumerated effectively:

Proposition 1.10 ([5]).

For every $α ⩽ ϵ_{0}$ , a power of ω, there is a sequence $⟨ f_{s}^{α, 0}, o_{s}^{α, 0} ⟩, ⟨ f_{s}^{α, 1}, o_{s}^{α, 1} ⟩, \dots$ of tidy $(α + 1)$ -computable approximations, uniformly computable (in both their index and in α), such that for every α-c.a. function f there is some i such that $f = f^{α, i} = {lim}_{s} f_{s}^{α, i}$ , and the approximation $⟨ f_{s}^{α, i}, o_{s}^{α, i} ⟩$ is eventually α-computable.

2. Non-collapsing in upper cones

In this section we prove Theorem 1.4. We prove a slightly more general theorem, which we believe will make the ordinal combinatorics clearer.

Theorem 2.1.
Let $α ⩽ β < ϵ_{0}$ be powers of ω. Above every totally α-c.a. degree there is a degree which is totally $(α β α ω)$ -c.a. but not totally β-c.a.

For Theorem 1.4 let $β = α$ .

To prove the theorem, fix a c.e. set A (with an effective enumeration $⟨ A_{s} ⟩$ ) whose degree is totally α-c.a. We enumerate a c.e. set D such that ${deg}_{T} (A \oplus D)$ is totally $(α β α ω)$ -c.a. and not totally β-c.a.
2.1. Requirements

Let ${⟨ Φ_{d} ⟩}_{d < ω}$ be an enumeration of all Turing functionals. To make $A \oplus D$ totally $(α β α ω)$ -c.a., we need to ensure, $\begin{matrix} for all d < ω, Q_{d} : If Φ_{d} (A, D) is total, then it is (α β α ω) -c.a. \end{matrix}$

To make $A \oplus D$ not totally β-c.a., we enumerate a functional Λ and ensure that $Λ (D)$ is not β-c.a. We will of course need to ensure that $Λ (D)$ is total.1

¹
Note that we could have added A as an oracle to Λ. However, we will see that this is not useful.

We diagonalise against the approximations

⟨ f_{s}^{β, i}, o_{s}^{β, i} ⟩

given by Proposition 1.10. We need to ensure,

\begin{matrix} for all i < ω, P^{i} : If ⟨ f_{s}^{β, i}, o_{s}^{β, i} ⟩ is eventually β -computable, then Λ (D) \neq f^{β, i} . \end{matrix}

2.2. Discussion

The proof uses some ideas from the proofs of Theorems 3.6 and 4.12 from [5].

We build a tree of strategies. A node σ working for a requirement $P^{i}$ appoints a follower p with the aim of ensuring that $Λ (D, p) \neq f^{β, i} (p)$ . Thus, whenever σ sees that $Λ (D, p) [s] = f_{s}^{β, i} (p)$ , we enumerate $λ_{s} (p)$ into $D_{s + 1}$ and redefine $Λ (D, p) [s + 1]$ to be large, and so not equal to $f_{s}^{β, i} (p)$ . Thus, if t is a future stage at which σ acts again, we have $o_{s}^{β, i} (p) > o_{t}^{β, i} (p)$ ; so σ acts only finitely often for the follower p, and in fact the ordinal $β + 1$ gives a bound on the “number of times” σ can act for p.

A node τ working for $Q_{d}$ measures the totality of $Φ_{d} (A, D)$ . Since A is not under our control, this cannot be done in a $Σ_{2} / Π_{2}$ fashion. If total, then for every input x, a computation $Φ_{d} (A, D, x)$ will eventually be ‘certified’, and henceforth the approximation for $Φ_{d} (A, D, x)$ will occur on τ-expansionary stages. When certifying the computation, the node τ needs to provide an ordinal below $α β α ω$ , and decrease this ordinal if a computation seen at an expansionary stage is later destroyed.

Such computations will be destroyed either by an A-change or a D-change. We soon discuss how to get an ordinal bound, below $β α ω$ , over the “number” of D-changes that can injure a certified computation $Φ_{d} (A, D, x)$ . Over A-changes however we have no control. To counter this, we use the fact that A is totally α-c.a. The node τ builds a “shadow functional” ${\hat{Φ}}_{τ}$ which keeps track of the A-part of the computations $Φ_{d} (A, D)$ . We will need to ensure that if $Φ_{d} (A, D)$ is total, then so is ${\hat{Φ}}_{τ} (A)$ . We will then be able to guess an α-computable approximation $⟨ f_{s}^{α, k}, o_{s}^{α, k} ⟩$ for ${\hat{Φ}}_{τ} (A)$ . Naively, we copy a computation $Φ_{d} (A, D, x)$ to ${\hat{Φ}}_{τ} (A, x)$ with the same use. If we see an A-change below that use, then we are free to redefine ${\hat{Φ}}_{τ} (A, x)$ to be large; the next time we see an agreement with $f_{s}^{α, k} (x)$ , the ordinal bound $o_{s}^{α, k} (x)$ will have decreased. In that way we could hope for an ordinal bound, below α, on the number of injuries to $Φ_{d} (A, D, x)$ because of A-changes.

However, sometimes D-changes destroy $Φ_{d} (A, D, x)$ but no corresponding A-change occurs. We cannot then redefine ${\hat{Φ}}_{τ} (A, x)$ . As we are dealing with Turing reductions, rather than weak truth-table reductions, the use on a new $Φ_{d} (A, D, x)$ -computation is larger, and so we cannot track subsequent A-changes on ${\hat{Φ}}_{τ} (A, x)$ . We need to track it on a new input. We thus appoint a tracker $c = tr (τ, x)$ , and keep track of the A-side of $Φ_{d} (A, D, x)$ at ${\hat{Φ}}_{τ} (A, c)$ . When D-enumerations occur, we cancel the tracker c and appoint a new one $c^{'}$ . The new tracker comes with a new ordinal bound below α, likely larger than c’s bound. Thus between any two D-changes we need to insert a copy of α, counting A-changes for a given tracker. That is, the overall bound covering both A- and D-changes is multiplicative: $α \cdot β α ω$ .

D-changes are caused by nodes σ for positive requirements $P^{i}$ operating below τ. For each such node σ, with a follower p, the ordinal $o_{s}^{i} (p)$ gives an ordinal bound $⩽ β$ on such action by σ; taking into account finitely many such nodes, it would seem that we can give a bound below $β ω$ .2

²
The ordinal arithmetic here follows ideas that were used in [5]. Let $σ_{1}, σ_{2}, \dots, σ_{k}$ list, in decreasing strength, the P-nodes below τ which have chosen their follower before the stage at which some x was certified by τ. For each $j ⩽ k$ and stage s, let $ϵ_{j, s} ⩽ β$ be the ordinal provided by $σ_{j}$ at stage s. If some $σ_{j}$ acts, then weaker $σ_{i}$ ’s are initialised and so can be removed from the list; and the ordinal $ϵ_{j}$ will decrease. Hence overall, the sum $\sum_{j ⩽ k} ϵ_{j, s}$ , which is smaller than $β ω$ , will decrease each time any of the nodes $σ_{j}$ will act. Alternatively, we can forget about the priority ordering between the nodes, and use commutative ordinal addition, based on Cantor normal form, which we review below in page 191).

Where does the extra α-term in the middle come from?

When a node τ as above certifies a computation $Φ_{d} (A, D, x)$ , it can observe the nodes σ below it that already have followers, and take into account their action in devising the ordinal bound. However, other σ-nodes that appoint followers later cannot be taken into account, and so we need to make sure that such nodes never injure a confirmed $Φ_{d} (A, D, x)$ computation. Consider however what happens when such a computation is destroyed by an A-change. A node σ with a follower p that is not allowed to injure $Φ_{d} (x)$ , must keep the use $λ (p)$ larger than the use $φ_{d} (x)$ . But even if we allowed A as an extra oracle for Λ, to keep $Λ (A, D)$ total, we need to appoint a new use $λ (p)$ immediately when we see this D-change – before we see the new $Φ_{d} (x)$ computation and its very large use. This is why adding A as an oracle to Λ is not useful. There doesn’t seem to be any other option but for us to discard p in this situation, and choose a new, large follower for σ. This is a new ingredient which does not appear in [5].

There will be counting difficulties, but first we need to argue that this process will end: that if σ lies on the true path, that eventually it will get a follower which is never cancelled. First, to this end, we see that even though we appoint a new large follower $p^{'}$ for σ, we cannot allow more computations $Φ_{d^{'}} (x^{'})$ cause further cancellations; the priority vis-a-vis computations belongs to σ rather than its followers individually. Still, we could imagine a loop: $Φ_{d} (x)$ sees an A-change and cancels a follower for σ; later we see a D-change that cancells the tracker for $Φ_{d} (x)$ ; a new tracker will see more A-changes;… However, the magic of the marketplace priority tree ensures this does not happen; the D-change cancelling the tracker for $Φ_{d} (x)$ must be caused by some other node $\bar{σ}$ which is stronger than σ, and it would initialise σ at that point.

Now for the counting difficulties. Suppose that $\bar{τ}$ is another node working for some $Q_{\bar{d}}$ , with $\bar{d}$ possibly different from d; and suppose that σ is allowed to injure $Φ_{\bar{d}} (\bar{x})$ . What is the ordinal count now on the “number of times” that σ will create a D-change injuring such a computation? When a new follower $p^{'}$ is assigned to σ, the ordinal count $o^{β, i} (p^{'})$ “resets” back to β. So we need a copy of β for each follower for σ; and we need an ordinal bound on the number of times we will need to appoint a new follower for σ. Each such cancellation is caused by an A-change in a computation such as $Φ_{d} (A, D, x)$ ; and these A-changes are tracked, so we have a bound below α on them. Since α is closed under addition, we would expect that adding these bounds for all pairs $(d, x)$ that can cancel followers for σ, we would get a bound still below α; and then overall we would get a bound below $β α$ on the number of times σ will ever act. A delicate timing issue means that when τ first confirms $Φ_{\bar{d}} (x)$ , it may see that σ has already appointed a follower, and so is allowed to injure this computation; but the ordinal bound on the number of times σ will act depends on a computation $Φ_{d} (x)$ , with τ below $\bar{τ}$ , which has not yet been tracked. Therefore the bound on the number of times σ will replace a follower is $α + 1$ rather than α; adding finitely many σ’s, we get an ordinal below $α ω$ .

We now turn to the formal details of the construction.

2.3. Strategy tree

A node τ working for requirement $Q_{d}$ has outcomes ∞ and $f$ , ordered $\infty < f$ , which measure ${lim sup}_{s} dom Φ_{d} (A, D) [s]$ (restricted to the τ-stages). The node τ is responsible for the enumeration of the shadow functional ${\hat{Φ}}_{τ} (A)$ . The node $τ \hat{} \infty$ has outcomes $\infty_{n}, f_{n}$ for all $n < ω$ , ordered in the manner $\infty_{0} < f_{0} < \infty_{1} < f_{1} < \dots$ which guess whether or not ${\hat{Φ}}_{τ} (A)$ is total. Each $τ \hat{} \infty \hat{} \infty_{n}$ node has outcomes $k < ω$ , ordered $0 < 1 < 2 < \dots$ , where each node $τ \hat{} \infty \hat{} \infty_{n} \hat{} k$ guesses that ${\hat{Φ}}_{τ} (A) = f^{α, k}$ (recall Proposition 1.10).

The nodes $τ \hat{} f$ , $τ \hat{} \infty \hat{} f_{y}$ for all y, and $τ \hat{} \infty \hat{} \infty_{n} \hat{} k$ for all $n, k$ all work for the next requirement in some ω-list of all requirements.

Since A is ${low}_{2}$ , the set of indices of functionals Ψ such that $Ψ (A)$ is total is $Σ_{3}^{0}$ . We can translate the question of membership in a $Π_{2}^{0}$ set into whether or not a given non-decreasing sequence is bounded. By the recursion theorem, the index of the functional ${\hat{Φ}}_{τ}$ enumerated by τ is known to us. We thus obtain a computable list $l_{s} (τ, n)$ of sequences, non-decreasing in s, such that ${\hat{Φ}}_{τ} (A)$ is total if and only if the sequence ${⟨ l_{s} (τ, n) ⟩}_{s < ω}$ is unbounded for some n. It is this list of sequences that we check against when $τ \hat{} \infty$ is accessible.

A node σ working for requirement $P^{i}$ has a unique outcome, which works for the next requirement on our list. As mentioned, such a node σ will appoint a follower p. When action by σ on p’s behalf injures a computation $Φ_{d} (A, D, x)$ monitored by some τ stronger than σ, we need to cancel its tracker. We keep track of those nodes and computations which are affected by σ. Let ${prec}_{\infty} (σ)$ be the set of nodes τ which work for some requirement $Q_{d}$ such that $τ \hat{} \infty \hat{} \infty_{n} ≺ σ$ for some $n < ω$ . For every $τ \in {prec}_{\infty} (σ)$ we will define a number $m_{s}^{τ} (σ)$ . We then let ${Pr}_{s} (σ)$ consist of the collection of pairs $(d, x)$ such that there is some $τ \in {prec}_{\infty} (σ)$ , working for requirement $Q_{d}$ , such that $x < m_{s}^{τ} (σ)$ . The computations $Φ_{d} (A, D, x)$ for $(d, x) \in {Pr}_{s} (σ)$ are the computations which σ cannot injure. We remark that between stages at which σ is initialised, the numbers $m_{s}^{τ} (σ)$ remain constant.

2.4. Construction

Let s be a stage. During the stage we define $γ_{s}$ , the collection of nodes accessible at s, by recursion; and describe how to act for each accessible node. The empty node is always accessible.

Suppose that τ, working for $Q_{d}$ , is accessible at stage s. Let $t < s$ be the last stage before s at which $τ \hat{} \infty$ was accessible, or $t = 0$ if there is no such stage. If $dom Φ_{d} (A, D) [s] ⩽ t$ , we let $τ \hat{} f$ be next accessible (added to $γ_{s}$ ); otherwise, we let $τ \hat{} \infty \in γ_{s}$ instead.

Suppose that $τ \hat{} \infty \in γ_{s}$ . Before we determine the next accessible node, we maintain our shadow functional ${\hat{Φ}}_{τ}$ . Let $x < t$ be such that $c = tr_{s} (τ, x)$ is defined (recall that this means that at stage s, c is the ${\hat{Φ}}_{τ}$ -tracker for $Φ_{d} (A, D, x)$ ). If ${\hat{Φ}}_{τ} (A, c) ↑ [s]$ then we define ${\hat{Φ}}_{τ, s + 1} (A_{s}, c)$ with large value but with use $φ_{d, s} (x)$ . If any $c < s$ is not currently a tracker for τ and ${\hat{Φ}}_{τ} (A, c) ↑ [s]$ , then we define ${\hat{Φ}}_{τ, s + 1} (A_{s}, c)$ with use 0. And for each $x < s$ for which $tr_{s} (τ, x)$ is undefined (either because x is new, or because the previous tracker was cancelled), we appoint a new, large tracker $tr_{s + 1} (τ, x)$ .

Recall that t is the previous stage at which $τ \hat{} \infty$ was accessible. Let y be least such that either $Φ_{d} (A, D, y) ↑ [t]$ or the computation $Φ_{d} (A, D, y) [t]$ was destroyed since stage t. That is, if $A_{t} ↾ u \neq A_{s} ↾ u$ or $D_{t} ↾ u \neq D_{s} ↾ u$ where $u = φ_{d, t} (y)$ .

For each $n < s$ , let $t_{n}$ be the last stage before s at which $τ \hat{} \infty \hat{} \infty_{n}$ was accessible, or $t_{n} = 0$ if there is no such stage. If there is some $n ⩽ y$ such that $l_{s} (τ, n) ⩾ t_{n}$ , then we guess that the sequence $l (τ, n)$ is unbounded (and so that ${\hat{Φ}}_{τ} (A)$ is total), and we let $τ \hat{} \infty \hat{} \infty_{n}$ be next accessible for the least such n. If there is no such $n ⩽ y$ , then we let $τ \hat{} \infty \hat{} f_{y}$ be next accessible.

Suppose now that $τ \hat{} \infty \hat{} \infty_{n}$ is accessible at s for some n. For each $k < s$ , let $r_{k}$ be the last stage before s at which $τ \hat{} \infty \hat{} \infty_{n} \hat{} k$ was accessible, or $r_{k} = 0$ if there was no such stage. We let $τ \hat{} \infty \hat{} \infty_{n} \hat{} k$ be next accessible for the least $k ⩽ s$ such that for all $x < r_{k}$ , $c = tr_{s} (τ, x)$ is defined, $o_{s}^{α, k} (c) < α$ , and ${\hat{Φ}}_{τ} (A, c) [s] ↓ = f_{s}^{α, k} (c)$ . We note that $r_{s} = 0$ , so such a k must exist, even if it merely satisfies these conditions trivially.

Let σ working for $P^{i}$ be accessible at s. One of several cases will apply to σ.

s is the first stage, after the last stage at which σ was initialised, at which σ is accessible. For all $τ \in {prec}_{\infty} (σ)$ we let $m_{s + 1}^{τ} (σ) = dom Φ_{d} (A, D) [s]$ , where τ works for $Q_{d}$ . We appoint a new, large follower p for σ, and define $Λ (D, p) [s + 1]$ with large value and use. We end the stage.

σ has a follower p, but for some $(d, x) \in {Pr}_{s} (σ)$ , $φ_{d, s} (x) > λ_{s} (p)$ . We will observe that for all $(d, x) \in {Pr}_{s} (σ)$ , $Φ_{d} (A, D, x) ↓ [s]$ . We cancel the follower p, and appoint a new, large follower q; we define $Λ (D, q) [s + 1]$ with large value and use. We end the stage.

σ has a follower p, case (ii) fails, and $Λ (D, p) [s] \neq f_{s}^{β, i} (p)$ . We let σ’s unique successor on the tree of strategies be next accessible.

σ has a follower p, case (ii) fails, and $Λ (D, p) [s] = f_{s}^{β, i} (p)$ . We enumerate $λ_{s} (p)$ into $D_{s + 1}$ and redefine $Λ (D, p) [s + 1]$ with large value and use. For every $τ \in {prec}_{\infty} (σ)$ , for every $x ⩾ m_{s}^{τ} (σ)$ , we cancel the tracker $tr_{s} (τ, x)$ . We then end the stage.

Note that we eventually run into a new long node σ, so each stage has only finitely many steps. At the conclusion of stage s, we maintain the functional Λ to ensure its totality: for any $q ⩽ s$ which is not currently a follower for any node σ and such that $Λ (D, q) ↑ [s]$ , we define $Λ (D, q) [s + 1]$ with use $- 1$ . Finally, we initialise all nodes that are (strictly) weaker than the last accessible node. When a node σ with a follower is initialised, its follower is cancelled. When a node τ is initialised, all its trackers are cancelled.

2.5. Verification

We introduce terminology: for a node μ on the tree, we denote s to be a μ-stage if $μ \in γ_{s}$ .

Lemma 2.2.
Let σ be a node working for requirement $P^{i}$ . Let s be a σ-stage such that ${Pr}_{s} (σ)$ is defined. Then for all $(d, x) \in {Pr}_{s} (σ)$ , $Φ_{d} (A, D, x) ↓ [s]$ . Further, if $τ \in {prec}_{\infty} (σ)$ works for $Q_{d}$ , and $τ \hat{} \infty \hat{} \infty_{n} \hat{} k ≼ σ$ , then $c = tr_{s} (τ, x)$ is defined, ${\hat{Φ}}_{τ} (A, c) ↓ [s] = f_{s}^{α, k} (c)$ , and $o_{s}^{α, k} (c) < α$ .
Proof.
Let $t < s$ be the first σ-stage after the last time (prior to s) at which σ was initialised. So at stage t we define the value $m_{t + 1}^{τ} (σ) = m_{s}^{τ} (σ)$ . Let $x < m_{s}^{τ} (σ)$ . We define $m_{t + 1}^{τ} (σ) = dom Φ_{d} (A, D) [t] < t$ . If $s > t$ then as s is a $τ \hat{} \infty$ -stage, $dom Φ_{d} (A, D) [s] > t > m_{s}^{τ} (σ) > x$ . Similarly, the rest follows from the fact that both t and s are $τ \hat{} \infty \hat{} \infty_{n} \hat{} k$ -stages. □
Lemma 2.3.
For any node σ, if p is a follower for σ at the beginning of stage s, then $Λ (D, p) ↓ [s]$ .
Proof.
Formally, by induction on s. When σ appoints p, or enumerates $λ_{s} (p)$ into $D_{s + 1}$ , a new computation $Λ (D, p) [s + 1]$ is defined. We just need to note that unless σ acts for p at stage s, then $λ_{s} (p) \notin D_{s + 1}$ ; the point is that if $p^{'}$ is a follower for $σ^{'}$ at the beginning of stage s then $λ_{s} (p) \neq λ_{s} (p^{'})$ , as all uses are chosen large. □
Lemma 2.4.
Let σ be a node working for some $P^{i}$ . Let s be a σ-stage, and suppose that at the beginning of stage s, σ has a follower p. Let τ be a node working for $Q_{d}$ such that $τ \hat{} \infty \hat{} f_{y} ≼ σ$ , and let $x < y$ . Then $Φ_{d} (A, D, x) ↓ [s]$ and $φ_{d, s} (x) < λ_{s} (p)$ .
Proof.
Let $t < s$ be the stage at which the stage s use $λ_{s} (p)$ was defined; so t was a σ-stage and $t < λ_{t + 1} (p) = λ_{s} (p)$ (as new uses are chosen large). Since $τ \hat{} \infty \hat{} f_{y} \in γ_{t}$ , $y ⩽ dom Φ_{d} (A, D) [t]$ , so $Φ_{d} (A, D, x) ↓ [t]$ . Let $u = φ_{d, t} (x) < t$ . So $u < λ_{s} (p)$ . It suffices to show that $A_{t} ↾ u = A_{s} ↾ u$ and $D_{t} ↾ u = D_{s} ↾ u$ . If not, then let $r > t$ be the least $τ \hat{} \infty$ -stage at which we see either $A_{t} ↾ u \neq A_{r} ↾ u$ or $D_{t} ↾ u \neq D_{r} ↾ u$ . Then at stage $r ⩽ s$ , either $τ \hat{} \infty \hat{} \infty_{n} \in γ_{s}$ or $τ \hat{} \infty \hat{} f_{n} \in γ_{s}$ for some $n ⩽ x < y$ . This outcome lies to the left of the outcome $f_{y}$ , and so $r < s$ and at stage r, σ is initialised, which is impossible. □

We need to be sure that if a computation is destroyed by a change in D, its tracker is cancelled immediately to allow us to correctly anticipate further A-changes.
Lemma 2.5.
Let τ be a node working for requirement $Q_{d}$ . Let s be a stage; let $x < ω$ be such that $c = tr_{s} (τ, x)$ is defined. Suppose that ${\hat{Φ}}_{τ} (A, c) ↓ [s]$ , and let $u = {\hat{φ}}_{τ, s} (c)$ . Then:
$Φ_{d} (A, D, x) ↓ [s]$ and $u = φ_{d, s} (x)$ .

If $D_{s} ↾ u \neq D_{s + 1} ↾ u$ then the tracker c is cancelled at stage s.

Proof.
Suppose that (i) and (ii) hold up to stage s, and that the lemma’s hypotheses hold at s. Let $t < s$ be the stage at which the computation ${\hat{Φ}}_{τ} (A, c) [s]$ was defined; then $A_{t} ↾ u = A_{s} ↾ u$ . Since trackers are chosen to be large, $c = tr_{t} (τ, x)$ . At the $τ \hat{} \infty$ -stage t we define $u = {\hat{φ}}_{τ, t + 1} (c) = φ_{d, t} (x)$ . Since the tracker c was not cancelled at any stage prior to s, by induction, $D_{t} ↾ u = D_{s} ↾ u$ . The constancy of both A and D imply that $φ_{d, s} (x) = φ_{d, t} (x) = u$ .

For (ii), suppose that $D_{s} ↾ u \neq D_{s + 1} ↾ u$ ; then at stage s we enumerate a number $λ_{s} (p) < u$ into D, where p is a follower for a node σ, which works for a requirement $P^{i}$ .

Since $λ_{s} (p) < u = φ_{d, t} (x)$ , we know that the use $λ_{s} (p)$ was chosen prior to stage t; so p was chosen as a follower for σ prior to stage t.

Now we ask: how does τ relate to σ?

If σ lies to the right of $τ \hat{} \infty$ , then σ is initialised at stage t; this is impossible. If τ is weaker than σ, then τ is initialised at stage s; in particular, c is cancelled at s. If not, then $τ \hat{} \infty ≺ σ$ .

Suppose that $τ \hat{} \infty \hat{} f_{y} ≼ σ$ . Let $\bar{s} < s$ be the last $τ \hat{} \infty$ -stage prior to stage s. Since t is a $τ \hat{} \infty$ -stage, $t ⩽ \bar{s}$ . Since the computation $Φ_{d} (A, D, x) [t]$ still holds at stage s, it is unchanged between stages $\bar{s}$ and s. Now $f_{y}$ is the outcome chosen at stage s; so either $Φ_{d} (A, D, y) ↑ [\bar{s}]$ or the computation $Φ_{d} (A, D, y) [\bar{s}]$ does not persist at t. We assume that the functional $Φ_{d}$ is use-monotone, so we conclude that $x < y$ . By Lemma 2.4, $λ_{s} (p) > φ_{d, s} (x)$ , which is not the case.

Hence $τ \in {prec}_{\infty} (σ)$ . By our instructions for σ, since p is not cancelled at stage s, $(d, x) \notin {Pr}_{s} (σ)$ , i.e., $x ⩾ m_{s}^{τ} (σ)$ . At stage s, σ is instructed to cancel c. □
Corollary 2.6.
Let τ be a node working for requirement $Q_{d}$ . Let $x < ω$ , and suppose that at some point a tracker $c = tr (τ, x)$ is defined and is never cancelled. Suppose that ${\hat{Φ}}_{τ} (A, c) ↓$ . Then $Φ_{d} (A, D, x) ↓$ .

Let the true path, $γ_{ω}$ , consist of the nodes μ such that:
$μ \in γ_{s}$ for infinitely many s; and

μ is initialised only finitely often.
If μ lies to the right of some node in $γ_{s}$ then μ is initialised at stage s. It follows that $γ_{ω}$ is a path: linearly ordered by extension of nodes, and closed under taking initial segments. Note that we have not yet shown that $γ_{ω}$ is infinite.
Lemma 2.7.
Let σ be a node which works for $P^{i}$ , and let p be a follower for σ. There are only finitely many stages s at which σ acts on p’s behalf by enumerating $λ_{s} (p)$ into $D_{s + 1}$ .
Proof.
Let $s_{0} < s_{1} < \dots$ be the stages s at which σ enumerates $λ_{s} (p)$ into $D_{s + 1}$ . If σ acts thus at a stage s, it must be because $Λ (D, p) [s] = f_{s}^{β, i} (p)$ . We then redefine $Λ (D, p) [s + 1]$ to be large, and so greater than $f_{s}^{β, i} (p)$ . So $f_{s_{0}}^{β, i} (p) \neq f_{s_{1}}^{β, i} (p) \neq \dots$ , and hence $o_{s_{0}}^{β, i} (p) > o_{s_{1}}^{β, i} (p) > \dots$ – implying that the sequence $s_{0}, s_{1}, \dots$ must be finite. □
Lemma 2.8.
Let σ be a node working for requirement $P^{i}$ . Let $s < t$ be σ-stages such that ${Pr}_{s} (σ)$ is defined and σ is not initialised at any stage $r \in [s, t)$ . Let $(d, x) \in {Pr}_{s} (σ)$ ; let $τ \in {prec}_{\infty} (σ)$ work for $Q_{d}$ . Then $tr_{s} (τ, x) = tr_{t} (τ, x)$ .

Note that $tr_{s} (τ, x)$ is defined by Lemma 2.2.
Proof.
Suppose not; let $r \in [s, t)$ be the stage at which $tr_{s} (τ, x) = tr_{r} (τ, x)$ is cancelled. Let $\bar{σ}$ be the node which causes this cancellation. So $τ \in {prec}_{\infty} (\bar{σ})$ and $x ⩾ m_{r}^{τ} (\bar{σ})$ . By assumption, $x < m_{s}^{τ} (σ) = m_{r}^{τ} (σ)$ . Hence $σ \neq \bar{σ}$ . Since σ is not initialised at stage r, $\bar{σ}$ is weaker than σ. Let $v < s$ be the stage at which $m_{s}^{τ} (σ)$ is defined. Then $\bar{σ}$ is initialised at stage v. Hence $m_{r}^{τ} (\bar{σ})$ is defined at a stage $\bar{v} > v$ . As both v and $\bar{v}$ are $τ \hat{} \infty$ -stages, $\begin{matrix} x ⩾ m_{\bar{v}}^{τ} (\bar{σ}) = dom Φ_{d} (A, D) [\bar{v}] > v > m_{v}^{τ} (σ) = m_{s}^{τ} (σ) > x, \end{matrix}$ a contradiction. □

The following lemma fits here but will only be used later.
Lemma 2.9.
Let σ be a node working for requirement $P^{i}$ . Let $s < t$ be σ-stages such that ${Pr}_{s} (σ)$ is defined and σ is not initialised at any stage $r \in [s, t)$ . Suppose that a follower for σ is cancelled at stage t. Then there is some $(d, x) \in {Pr}_{s} (σ)$ such that $o_{s}^{α, k} (c) > o_{t}^{α, k} (c)$ , where $τ \in {prec}_{\infty} (σ)$ works for $Q_{d}$ , $τ \hat{} \infty \hat{} \infty_{n} \hat{} k ≼ σ$ , and $c = tr_{t} (τ, x)$ .
Proof.
σ’s follower p is cancelled at stage t because $φ_{d, t} (x) > λ_{t} (p)$ for some $(d, x) \in {Pr}_{t} (σ) = {Pr}_{s} (σ)$ . Let $τ \in {prec}_{\infty} (σ)$ work for $Q_{d}$ , and let $n, k < ω$ such that $τ \hat{} \infty \hat{} \infty_{n} \hat{} k ≼ σ$ . Let $c = tr_{s} (τ, x) = tr_{t} (τ, x)$ (Lemma 2.8).

We need to argue that $f_{s}^{α, k} (c) \neq f_{t}^{α, k} (c)$ . By Lemma 2.2, ${\hat{Φ}}_{τ} (A, c) ↓ [s] = f_{s}^{α, k} (c)$ , and the same holds at t. So we need to show that ${\hat{Φ}}_{τ} (A, c) [s] \neq {\hat{Φ}}_{τ} (A, c) [t]$ . By increasing s we may assume that s is the σ-stage prior to t, so p is the follower for σ at stage $s + 1$ . Either we define $Λ (D, p) [s + 1]$ at stage s; then its use $λ_{s + 1} (p) = λ_{t} (p)$ is large, greater than $φ_{d, s} (x)$ . Or p is already the follower for σ at the beginning of stage s, in which case $λ_{s} (p)$ is already defined; but since p is not cancelled at stage s, we have $λ_{t} (p) = λ_{s} (p) ⩾ φ_{d, s} (x)$ . In either case we see that $φ_{d, s} (x) ⩽ λ_{t} (p) < φ_{d, t} (x)$ . By Lemma 2.5, ${\hat{φ}}_{τ, s} (c) = φ_{d, s} (x)$ and the same holds at t. So ${\hat{φ}}_{τ, s} (c) < {\hat{φ}}_{τ, t} (c)$ . Hence the computation ${\hat{Φ}}_{τ} (A, c) [s]$ was destroyed and redefined before stage t, with a value large relative to stage s. □
Lemma 2.10.
Let $σ \in γ_{ω}$ be a node working for some $P^{i}$ . Then σ is eventually assigned a follower which is never cancelled.
Proof.
Let s be the second σ-stage after the last stage at which σ is initialised. By stage s we have already defined $Pr (σ) = {Pr}_{s} (σ)$ which equals ${Pr}_{t} (σ)$ for all $t ⩾ s$ .

Let $(d, x) \in Pr (σ)$ ; let $τ \in {prec}_{\infty} (σ)$ work for $Q_{d}$ . By Lemma 2.8, the tracker $c = tr_{s} (τ, x)$ is never cancelled.

Let $n < ω$ such that $τ \hat{} \infty \hat{} \infty_{n} ≺ σ$ . Since the outcome $\infty_{n}$ is guessed infinitely often, the sequence ${⟨ l_{t} (τ, n) ⟩}_{t < ω}$ is unbounded. Hence ${\hat{Φ}}_{τ} (A)$ is total. In particular, ${\hat{Φ}}_{τ} (A, c) ↓$ .

By Corollary 2.6, $Φ_{d} (A, D, x) ↓$ . If a follower p is appointed for σ after the correct computation $Φ_{d} (A, D, x)$ has appeared, then the pair $(d, x)$ will not be responsible for cancelling p. The lemma follows from the fact that $Pr (σ)$ is finite. □

The following will imply that $A \oplus D$ is ${low}_{2}$ .
Lemma 2.11.
Suppose that τ works for $Q_{d}$ and that $τ \hat{} \infty \in γ_{ω}$ .
Every $x < ω$ is eventually appointed a tracker which is never cancelled.

If $Φ_{d} (A, D)$ is total then so is ${\hat{Φ}}_{τ} (A)$ , and for some $n < ω$ , $τ \hat{} \infty \hat{} \infty_{n} \in γ_{ω}$ .

If $Φ_{d} (A, D)$ is partial then so is ${\hat{Φ}}_{τ} (A)$ , and $τ \hat{} \infty \hat{} f_{y} \in γ_{ω}$ , where $y = dom Φ_{d} (A, D)$ .

Proof.
Let $x < ω$ . At all but finitely many $τ \hat{} \infty$ -stages s, if $tr_{s} (τ, x)$ in undefined, then we define a new tracker $tr_{s + 1} (τ, x)$ . Thus, it suffices to show that a tracker $tr_{s} (τ, x)$ is cancelled only finitely many times.

After the last stage at which τ is initialised, such a tracker can be cancelled only by nodes σ such that $τ \in {prec}_{\infty} (σ)$ and $m_{s}^{τ} (σ) ⩽ x$ . There are only finitely many such nodes: $dom Φ_{d} (A, D) [s]$ is strictly increasing on the $τ \hat{} \infty$ -stages, and so eventually the values $m_{t}^{τ} (σ)$ are chosen large. By Lemmas 2.7 and 2.10, each node σ with $m_{s}^{τ} (σ) ⩽ x$ cancels x’s tracker only finitely many times. This establishes (1).

For (2), suppose that $Φ_{d} (A, D)$ is total. Let $c < ω$ . If c is chosen as a tracker for some x and is later cancelled, let t be the stage at which c is cancelled; if c is never chosen as a tracker, let $t = c$ . Let s be the least stage $s > t$ at which $τ \hat{} \infty$ is accessible and ${\hat{Φ}}_{τ} (A, c) ↑ [s]$ . We then define ${\hat{Φ}}_{τ, s + 1} (A_{s}, c) = 0$ with use 0, and so $c \in dom {\hat{Φ}}_{τ} (A)$ .

Suppose then that c is chosen as a tracker for some x and is never cancelled. At every sufficiently late $τ \hat{} \infty$ -stage s, if $c \notin dom {\hat{Φ}}_{τ} (A) [s]$ then we define a new computation ${\hat{Φ}}_{τ, s + 1} (A_{s}, c)$ with use $φ_{d, s} (x)$ . The computation which is made when we first see the correct $Φ_{d} (A, D, x)$ -computation is also a correct ${\hat{Φ}}_{τ} (A, c)$ -computation. Overall we see that ${\hat{Φ}}_{τ} (A)$ is total.

Therefore, there is some $n < ω$ such that ${⟨ l_{s} (τ, n) ⟩}_{s < ω}$ is an unbounded sequence; let n be least such. Since $Φ_{d} (A, D)$ is total, any outcome $f_{y}$ is guessed only finitely many times. It follows that the outcome $\infty_{n}$ will be guessed infinitely often.

Now we suppose that $Φ_{d} (A, D)$ is partial. Let $y = dom Φ_{d} (A, D)$ ; let c be the tracker that is eventually assigned to y and is never cancelled. Corollary 2.6 implies that ${\hat{Φ}}_{τ} (A, c) ↑$ , so ${\hat{Φ}}_{τ} (A)$ is partial. Thus, each sequence ${⟨ l_{s} (τ, n) ⟩}_{s < ω}$ is bounded, so each outcome $\infty_{n}$ is guessed only finitely often. Also, each outcome $f_{x}$ for $x < y$ is guessed only finitely often. On the other hand, the outcome $f_{y}$ will be guessed infinitely often. □
Lemma 2.12.
The true path $γ_{ω}$ is infinite.
Proof.
The empty node lies on the true path. We show that every node on the true path has a child on the true path.

This is clear for a node τ working for some $Q_{d}$ , as it has only two outcomes. The case $τ \hat{} \infty \in γ_{ω}$ is dealt with in Lemma 2.11.

Suppose that $τ \hat{} \infty \hat{} \infty_{n} \in γ_{ω}$ . By Lemma 2.11, ${\hat{Φ}}_{τ} (A)$ is total. Since ${deg}_{T} (A)$ is totally α-c.a., there is some k such that ${\hat{Φ}}_{τ} (A) = f^{α, k}$ and $⟨ f_{s}^{α, k}, o_{s}^{α, k} ⟩$ is eventually α-computable (recall that this means that for all c there is some s such that $o_{s}^{α, k} (c) < α$ ). Since every input x eventually receives a tracker which is not cancelled, for the least such k, $τ \hat{} \infty \hat{} \infty_{n} \hat{} k \in γ_{ω}$ .

Let σ be a node which works for $P^{i}$ ; suppose that $σ \in γ_{ω}$ . By Lemmas 2.7 and 2.10, σ acts only finitely many times after the last stage at which it was initialised. Hence for all but finitely many stages s, if $σ \in γ_{s}$ then σ’s only child is also in $γ_{s}$ . □

The true path then contains, for every P and Q requirement, a node that works for it. But first we need to show:
Lemma 2.13.
$Λ (D)$ is total.
Proof.
Let $p < ω$ . If p is never appointed as a follower, or if p is appointed to a node working for $P^{i}$ and later cancelled, then $p \in dom Λ (D)$ ; at a sufficiently late stage t, if $Λ (D, p) ↑ [t]$ then we define $Λ (D, p) [t + 1]$ with use $- 1$ .

Suppose then that p is appointed as a follower for a node σ working for $P^{i}$ , and that p is never cancelled. By Lemma 2.3, $p \in dom Λ_{s} (D)$ at every stage s after the stage at which p was chosen as follower. Since σ acts only finitely often for p (Lemma 2.7), the use $λ (p)$ is raised only finitely often. At the last stage t at which it is raised, we define $Λ (D, p) [t + 1]$ with a use $λ_{t + 1} (p)$ which is never enumerated into D, and so this computation is D-correct. □
Lemma 2.14.
Every requirement $P^{i}$ is met.
Proof.
Fix $i < ω$ , and let σ be the node on the true path working for requirement $P^{i}$ . By Lemma 2.10, σ has a follower p which is never cancelled. Then $Λ (D, p) \neq f^{i} (p)$ : at some sufficiently late σ-stage s we have both $Λ (D, p) ↓ [s]$ via a D-correct computation, and $f_{s}^{i} (p) = f^{i} (p)$ ; if we had equality, then at stage s, the node σ would act. □

To show that the Q-requirements are met, for simplicity, we use the commutative addition operation on ordinals. For ordinals γ, δ, the commutative ordinal sum $γ \oplus δ$ is determined by their Cantor normal form: if $γ = ω^{α_{1}} n_{1} + ω^{α_{2}} n_{2} + \dots + ω^{α_{k}} n_{k}$ , with $α_{1} > α_{2} > \dots > α_{k}$ and each $n_{i} < ω$ , and $δ = ω^{α_{1}} m_{1} + ω^{α_{2}} m_{2} + \dots + ω^{α_{k}} m_{k}$ , then $γ \oplus δ = ω^{α_{1}} (n_{1} + m_{1}) + ω^{α_{2}} (n_{2} + m_{2}) + \dots + ω^{α_{k}} (n_{k} + m_{k})$ .

The following are well known:
⊕ is commutative and associative.

Any power of ω is closed under ⊕.

Let $β_{1}, β_{2}, \dots, β_{n}$ and $γ_{1}, γ_{2}, \dots, γ_{n}$ be two n-tuples of ordinals. Suppose that for all $i ⩽ n$ , $β_{i} ⩽ γ_{i}$ . Then $⨁_{i ⩽ n} β_{i} ⩽ ⨁_{i ⩽ n} γ_{i}$ , and $⨁_{i ⩽ n} β_{i} < ⨁_{i ⩽ n} γ_{i}$ if, and only if, there is some $i ⩽ n$ such that $β_{i} < γ_{i}$ .
Lemma 2.15.
Every requirement $Q_{d}$ is met.
Proof.
Let $d < ω$ , and suppose that $Φ_{d} (A, D)$ is total. Let τ be the node on the true path working for $Q_{d}$ . Then $τ \hat{} \infty \in γ_{ω}$ ; by Lemmas 2.11 and 2.12, for some n and $k < ω$ , $ρ = τ \hat{} \infty \hat{} \infty_{n} \hat{} k$ lies on the true path. Let $s_{0} < s_{1} < \dots$ be the ρ-stages following the last stage at which ρ is initialised. We proceed to define an $(α β α ω)$ -computable approximation $⟨ f_{s}, o_{s} ⟩$ for $Φ_{d} (A, D)$ .

From now on, fix $x < ω$ . Let $j^{} = j^{} (x)$ be the least $j > 0$ such that $x < s_{j - 1}$ . For all $j ⩾ j^{}$ , $Φ_{d} (A, D, x) ↓ [s_{j}]$ . So for all $j ⩾ j^{}$ we let $f_{j} (x) = Φ_{d} (A, D, x) [s_{j}]$ . Certainly ${lim}_{j \to \infty} f_{j} (x) = Φ_{d} (A, D, x)$ . Let $u_{j} = u_{j} (x) = φ_{d, s_{j}} (x)$ .

To define the ordinal bound we need to measure both A-changes and D-changes. For the A-changes, we note that for all $j ⩾ j^{}$ , since $ρ \in γ_{s_{j}}$ and $x < s_{j - 1}$ , $c_{j} = c_{j} (x) = tr_{s_{j}} (τ, x)$ is defined, $o_{s_{j}}^{α, k} (c_{j}) < α$ , and ${\hat{Φ}}_{τ} (A, c_{j}) ↓ [s_{j}] = f_{s_{j}}^{α, k} (c_{j})$ . By Lemma 2.5, $u_{j} = {\hat{φ}}_{τ, s_{j}} (c_{j})$ . For brevity, for $j ⩾ j^{}$ we let $\begin{matrix} θ_{j} = θ_{j} (x) = o_{s_{j}}^{α, k} (c_{j}) . \end{matrix}$ Claim 2.15.1.
For all $j ⩾ j^{}$ , $θ_{j} < α$ . Suppose that* $c_{j} = c_{j + 1}$ . Then $θ_{j} ⩾ θ_{j + 1}$ ; and if $A_{s_{j}} ↾ u_{j} \neq A_{s_{j + 1}} ↾ u_{j}$ then $θ_{j} > θ_{j + 1}$ .
Proof.
The first part is immediate: $o_{s_{j}}^{α, k} (c_{j}) ⩾ o_{s_{j + 1}}^{α, k} (c_{j})$ . The second part is argued like the end of the proof of Lemma 2.9: if $A_{s_{j}} ↾ u_{j} \neq A_{s_{j + 1}} ↾ u_{j}$ then the computation ${\hat{Φ}}_{τ} (A, c_{j}) [s_{j}]$ is destroyed before stage $s_{j + 1}$ and redefined with large use, so $\begin{matrix} f_{s_{j}}^{α, k} (c_{j}) = {\hat{Φ}}_{τ} (A, c_{j}) [s_{j}] \neq {\hat{Φ}}_{τ} (A, c_{j}) [s_{j + 1}] = f_{s_{j + 1}}^{α, k} (c_{j}) . \end{matrix}$ □

For the D-changes, let $a = a (x)$ be the set of nodes $σ ≽ ρ$ , working for some requirement $P^{i} = P^{i (σ)}$ , such that ${Pr}_{s_{j^{}}} (σ)$ is defined. For all $j ⩾ j^{}$ we let $a_{j} = a_{j} (x)$ be the set of nodes $σ \in a$ which were not initialised at any stage in the interval $[s_{j^{}}, s_{j})$ . So $a_{j + 1} \subseteq a_{j}$ .

For $σ \in a$ , let $Pr (σ) = {Pr}_{s_{j^{}}} (σ)$ . If $σ \in a_{j}$ then $Pr (σ) = {Pr}_{s_{j}} (σ)$ . Let $s_{init} (σ) < s_{j^{}}$ be the stage at which $Pr (σ)$ was defined. We let $\begin{matrix} T (σ) = {s_{init} (σ)} \cup {s_{j} : j ⩾ j^{}, σ \in a_{j}, s_{j} is a σ -stage and σ ends stage s_{j}} . \end{matrix}$ For each $t \in T (σ)$ let $p_{t} (σ)$ be σ’s follower at the end of stage t. Again for brevity, for $t \in T (σ)$ we let $\begin{matrix} ϵ_{t} (σ) = o_{t}^{β, i} (p_{t} (σ)), \end{matrix}$ where σ works for requirement $P^{i}$ . Claim 2.15.2.
For all $t \in T (σ)$ , $ϵ_{t} (σ) ⩽ β$ . If $t_{0} < t_{1}$ are stages in $T (σ)$ and $p_{t_{0}} (σ) = p_{t_{1}} (σ)$ then $ϵ_{t_{0}} (σ) > ϵ_{t_{1}} (σ)$ .
Proof.
Let $t_{0} < t_{1}$ be stages in $T (σ)$ and suppose that $p_{t_{0}} (σ) = p_{t_{1}} (σ)$ , call it p. Since p was appointed as follower before stage $t_{1}$ , and σ acts for p at stage $t_{1}$ , $Λ (D, p) [t_{1}] = f_{t_{1}}^{β, i} (p)$ , where again σ works for $P^{i}$ . The important fact is that at the end of stage $t_{0}$ , a new computation $Λ (D, p) [t_{0} + 1]$ is defined, with large value (either because p is chosen at stage $t_{0}$ or $λ_{t_{0}} (p)$ is enumerated into $D_{t_{0} + 1}$ and a new computation defined). Hence $Λ (D, p) [t_{1}] > t_{0}$ . By convention, $f_{t_{0}}^{β, i} (p) < t_{0}$ so $f_{t_{0}}^{β, i} (p) \neq f_{t_{1}}^{β, i} (p)$ . □

Fix some $σ \in a (x)$ , and some $(\bar{d}, \bar{x}) \in Pr (σ)$ . Let $\bar{τ} \in {prec}_{\infty} (σ)$ be the node working for $Q_{\bar{d}}$ . For any $t \in T (σ)$ with $t > s_{init} (σ)$ , $tr_{t} (\bar{τ}, \bar{x})$ is defined (Lemma 2.2), and does not depend on t (Lemma 2.8); we denote this tracker, if it exists, by $c (\bar{d}, \bar{x}, σ)$ . Let $\bar{k} < ω$ such that $\bar{τ} \hat{} \infty \hat{} \infty_{\bar{n}} \hat{} \bar{k} ≼ σ$ for some $\bar{n} < ω$ . For $t \in T (σ)$ we let $\begin{matrix} δ_{t} (\bar{d}, \bar{x}, σ) = \{\begin{matrix} α, & if t = s_{init} (σ); and \\ o_{t}^{α, \bar{k}} (c (\bar{d}, \bar{x}, σ)), & if t > s_{init} (σ) . \end{matrix} \end{matrix}$ Note that if $t > s_{init} (σ)$ then $δ_{t} (\bar{d}, \bar{x}, σ) < α$ (Lemma 2.2). We then let $\begin{matrix} δ_{t} (σ) = ⨁_{(\bar{d}, \bar{x}) \in Pr (σ)} δ_{t} (\bar{d}, \bar{x}, σ) . \end{matrix}$ Claim 2.15.3.
For all $t \in T (σ)$ , $δ_{t} (σ) < α ω$ . 3
³
Because α is closed under addition, we could have defined $δ_{s_{init} (σ)} (σ) = α$ rather than $α \cdot | Pr (σ) |$ , and obtain the seemingly better bound $δ_{t} (σ) ⩽ α$ . But after adding these ordinals for more than one node σ, this does not give us an overall better bound.

Let $t_{0} < t_{1}$ be stages in $T (σ)$ . Then $δ_{t_{0}} (σ) ⩾ δ_{t_{1}} (σ)$ . If $p_{t_{0}} (σ) \neq p_{t_{1}} (σ)$ then $δ_{t_{0}} (σ) > δ_{t_{1}} (σ)$ .
Proof.
Let $t_{0} < t_{1}$ be stages in $T (σ)$ , and suppose that $p_{t_{0}} (σ) \neq p_{t_{1}} (σ)$ . If $t_{0} = s_{init} (σ)$ then for all $(\bar{d}, \bar{x}) \in Pr (σ)$ , $δ_{t_{0}} (\bar{d}, \bar{x}, σ) = α > δ_{t_{1}} (\bar{d}, \bar{x}, σ)$ and so certainly $δ_{t_{0}} (σ) > δ_{t_{1}} (σ)$ . If $t_{0} > s_{init} (σ)$ then Lemma 2.9 applies. □

For $t \in T (σ)$ let $\begin{matrix} ζ_{t} (σ) = β \cdot δ_{t} (σ) + ϵ_{t} (σ) . \end{matrix}$ Claims 2.15.2 and 2.15.3 together imply: Claim 2.15.4.
For all $t \in T (σ)$ , $ζ_{t} (σ) < β α ω$ . If $t_{0} < t_{1}$ are stages in $T (σ)$ then $ζ_{t_{0}} (σ) > ζ_{t_{1}} (σ)$ .

The last fact we need is the following. Claim 2.15.5.
Let $j ⩾ j^{}$ . Suppose that* $Φ_{d} (A, D, x) [s_{j}] \neq Φ_{d} (A, D, x) [s_{j + 1}]$ , and that $s_{j} \notin ⋃_{σ \in a} T (σ)$ . Then $θ_{j} > θ_{j + 1}$ .
Proof.
Recall that $u_{j} = φ_{d, s_{j}} (x)$ . By Claim 2.15.1, it suffices to show that $c_{j} = c_{j + 1}$ and that $A_{s_{j}} ↾ u_{j} \neq A_{s_{j + 1}} ↾ u_{j}$ .

Suppose that $c_{j} \neq c_{j + 1}$ . Let σ be the node which cancels $c_{j}$ , at a stage $t \in [s_{j}, s_{j + 1})$ . Since τ is not initialised after stage $s_{j^{}}$ , it must be that $τ \in {prec}_{\infty} (σ)$ and $x ⩾ m_{t}^{τ} (σ)$ . Since $dom Φ_{d} (A, D) [r] > x$ at every $τ \hat{} \infty$ -stage $r ⩾ s_{j^{}}$ , it must be that $m_{t}^{τ} (σ)$ was defined prior to stage $s_{j^{}}$ ; so ${Pr}_{s_{j^{}}} (σ)$ is defined and σ is not initialised at any stage $r \in [s_{j^{}}, t]$ .

If σ lies to the right of ρ, then σ is initialised at stage $s_{j^{}}$ , which is not the case; and since ρ is not initialised at stage t, σ cannot be stronger than ρ. Hence $σ ≽ ρ$ . We conclude that $σ \in a$ and in fact that $σ \in a_{j}$ . Since σ cannot be accessible between stages $s_{j}$ and $s_{j + 1}$ , we must have $t = s_{j}$ ; it follows that $s_{j} \in T (σ)$ .

Now suppose that $A_{s_{j}} ↾ u_{j} = A_{s_{j + 1}} ↾ u_{j}$ . Then necessarily $D_{s_{j}} ↾ u_{j} \neq D_{s_{j + 1}} ↾ u_{j}$ . By Lemma 2.5, $c_{j}$ would be cancelled prior to stage $s_{j + 1}$ , which we just argued is not the case. □

We are now ready to define our ordinal bound. For each $j ⩾ j^{}$ and $σ \in a$ , since $min T (σ) = s_{init} (σ) < s_{j^{}}$ , we can let $\begin{matrix} t_{j} (σ) = max (T (σ) \cap s_{j}), \end{matrix}$ that is, $t_{j} (σ)$ is the last stage in $T (σ)$ prior to stage $s_{j}$ . For $j ⩾ j^{}$ we then let $\begin{matrix} o_{j} (x) = α \cdot (⨁_{σ \in a} ζ_{t_{j} (σ)} (σ)) + θ_{j} . \end{matrix}$ Since $β α ω$ is closed under addition, $⨁_{σ \in a_{j}} ζ_{t_{j} (σ)} (σ) < β α ω$ , and as $θ_{j} < α$ , $o_{j} (x) < α β α ω$ .

We need to show that for all $j ⩾ j^{}$ , $o_{j} (x) ⩾ o_{j + 1} (x)$ , and if $Φ_{d} (A, D, x) [s_{j}] \neq Φ_{d} (A, D, x) [s_{j + 1}]$ then $o_{j} (x) > o_{j + 1} (x)$ .

Let $j ⩾ j^{*}$ . If $s_{j} \in T (σ)$ for some $σ \in a_{j}$ then $t_{j} (σ) < t_{j + 1} (σ)$ , and so $ζ_{t_{j} (σ)} (σ) > ζ_{t_{j + 1} (σ)} (σ)$ ; as $θ_{j} < α$ , it follows that $o_{j} (x) > o_{j + 1} (x)$ .

Suppose that $s_{j} \notin ⋃_{σ \in a} T (σ)$ . For all $σ \in a$ , $ζ_{t_{j} (σ)} (σ) ⩾ ζ_{t_{j + 1} (σ)} (σ)$ ; and $θ_{j} ⩾ θ_{j + 1}$ , so together we get $o_{j} (x) ⩾ o_{j + 1} (x)$ . If $Φ_{d} (A, D, x) [s_{j}] \neq Φ_{d} (A, D, x) [s_{j + 1}]$ then Claim 2.15.5 says that $θ_{j} > θ_{j + 1}$ , which implies that $o_{j} (x) > o_{j + 1} (x)$ .

This concludes the proof of Lemma 2.15, and so of Theorem 2.1. □

2.6. Powers of α

We could modify the previous construction: instead of diagonalising against all β-c.a. functions we can diagonalise against all functions which are γ-c.a. for some $γ < β$ . Of course if β is a successor power of ω then we get nothing new. Suppose that β is a limit of powers of ω. We then get ${deg}_{T} (A \oplus D)$ to be not totally $(< β)$ -c.a., which is actually stronger than not totally γ-c.a. for all $γ < α$ (see [5, Section 3.4]). Further, every $f ⩽_{T} A \oplus D$ has an approximation where on each input we start with an ordinal bounded below $α γ α ω$ for some $γ < α$ . Suppose further that β is a limit of powers of α. Then $α γ α ω < β$ . In this case we have constructed a properly totally β-c.a. degree. So for example, above every totally ω-c.a. degree there is one which is properly totally $ω^{ω}$ -c.a., $ω^{ω \cdot 2}$ -c.a., and so on. This is a special case of Theorem 1.7, and as we discussed, gives a little bit more in the cases it applies (being not totally $(< β)$ -c.a.). It would be interesting to find a direct construction proving all cases of Theorem 1.7.

3. Existence of maximal degrees in upper cones

In this section we prove Theorem 1.7. Indeed we prove the slightly more general theorem:

Theorem 3.1.
Let $α ⩽ β < ϵ_{0}$ . Above every totally α-c.a. degree there is a degree d which is totally $(α β)$ -c.a., but such that no degree strictly above d is totally β-c.a.

Theorem 1.7 follows since if $β ⩾ α^{ω}$ then $α β = β$ .

Let $α, β$ be as in the theorem, and let A be a c.e. set of totally α-c.a. degree. We proceed to enumerate a c.e. set D with the intent that $d = {deg}_{T} (A \oplus D)$ satisfies the conclusion of the theorem. As well as building on the previous construction, the proof utilises some ideas of the proof of Theorem 4.1 from [5].
3.1. Requirements

Let ${⟨ Φ_{d} ⟩}_{d < ω}$ be an enumeration of all functionals. To ensure that ${deg}_{T} (A \oplus D)$ is totally $(α β)$ -c.a., we must meet the set of requirements given by: $\begin{matrix} for all d < ω, Q_{d} : If Φ_{d} (A, D) is total, then it is (α β) -c.a. \end{matrix}$

For the maximality property of ${deg}_{T} (A \oplus D)$ , we need to ensure that for all $e < ω$ , either $W_{e} ⩽_{T} A \oplus D$ or ${deg}_{T} (A \oplus D \oplus W_{e})$ is not totally β-c.a. To this end, we enumerate a Turing functional $Λ_{e}$ with the intent that either $W_{e} ⩽_{T} A \oplus D$ , or $Λ_{e} (D, W_{e})$ is not β-c.a. Again we do not have use for the oracle A. We meet the following set of requirements: $\begin{matrix} for all e, i < ω, P_{e}^{i} : If ⟨ f_{s}^{β, i}, o_{s}^{β, i} ⟩ is eventually β -computable, then Λ_{e} (D, W_{e}) \neq f^{β, i}, or W_{e} ⩽_{T} A \oplus D . \end{matrix}$

3.2. Discussion

As usual, we work with a tree of strategies. Nodes τ working for $Q_{d}$ behave in exactly the same way as in the previous construction. The difference is the analysis of the ordinal number of D-changes that may injure a certified computation; we need to get that below β. This analysis is made easier than in the previous proof, because the extra oracle $W_{e}$ allows us to lift uses $λ_{e} (p)$ beyond the use $φ_{d} (x)$ of a certified computation. On the other hand, in order to compute $W_{e}$ , we will need to appoint a possibly infinite sequence of followers for every σ, and σ may act positively infinitely often.

Let us discuss this in greater detail. Suppose that σ appoints a follower p with the aim of making $Λ_{e} (D, W_{e}, p) \neq f^{β, i} (p)$ . A new restriction is that we are not allowed any action while $o_{s}^{β, i} (p) = β$ ; we need to provide to τ above us an ordinal strictly smaller than β. This creates a timing difficulty: σ firsts appoints p; then τ certifies $Φ_{d} (A, D, x)$ ; only later do we see $o_{s}^{β, i} (p) < β$ . We need to protect $Φ_{d} (x)$ from p. To do this, we first wait for a $W_{e}$ -change that allows us to lift $λ_{e} (p)$ . Once this has happened, we can attack with p. If we never see such a change, then we made a step toward computing $W_{e}$ .

It seems though that we nonetheless run into the same problem as in the previous construction: after we lift the use we get an A-change below $φ_{d} (x)$ for a protected computation. Even if we allowed A as an extra oracle for $Λ_{e}$ , we would still need to immediately redefine the use $λ_{e} (p)$ , and the new $φ_{d} (x)$ use which is revealed only later is greater. Recall however that we are not trying to show that $W_{e}$ is computable, merely computable from $A \oplus D$ . Thus, when we get such an A-change, we again cancel the follower p. In this construction, this allows us to make progress on computing $W_{e}$ from $A \oplus D$ .

Now unlike the previous construction, we do not want the α-ordinal count tracked by some $\bar{τ}$ to force follower cancellations; we are trying to keep the ordinals tracking D-changes below β, not below $β α ω$ . Thus, which $Φ_{d} (x)$ computations are protected must be determined by follower rather being the same for all followers for σ. That is, the later a follower is appointed, the more computations $Φ_{d} (x)$ it needs to protect. There will be no last follower appointed; so we could have infinitely many cycles in which σ starts acting for p, enumerating numbers into D, and then p gets cancelled. We will need to argue that τ lying below σ will not by injured infinitely often by σ. Such a node τ will guess that σ acts infinitely often, and it works in σ’s “wake”: it waits for a cycle of attack to finish, and then certifies some computations; the next attack cycle will start with lifting the use to a much larger number.

3.3. Strategy tree

A node τ working for requirement $Q_{d}$ is structured exactly as in the previous construction, with descendants being $τ \hat{} f$ , $τ \hat{} \infty$ , $τ \hat{} \infty \hat{} f_{y}$ , $τ \hat{} \infty \hat{} \infty_{n}$ , and $τ \hat{} \infty \hat{} \infty_{n} \hat{} k$ . As in the previous construction, since A is ${low}_{2}$ , we have a computable list $l_{s} (τ, n)$ of sequences, non-decreasing in s, such that ${\hat{Φ}}_{τ} (A)$ is total if and only if the sequence ${⟨ l_{s} (τ, n) ⟩}_{s < ω}$ is unbounded for some n.

A node σ working for requirement $P_{e}^{i}$ has outcomes ∞ and $f$ , with $\infty < f$ , which guess whether σ will act infinitely or finitely often (respectively). Both children of σ work for the next (lower priority) requirement.

The node σ is responsible for the enumeration of an enumeration operator $Δ_{σ}$ , with the aim of having either $Λ_{e} (D, W_{e}) \neq f^{β, i}$ , or $Δ_{σ} (A, D) = W_{e}^{∁}$ (the complement of $W_{e}$ ).

During the construction, the node σ will likely appoint several followers. Each follower p is connected with a particular potential element k of $W_{e}$ ; we write $p = p (σ, k)$ . Unless σ is initialised, at most one follower is appointed for each k, and so the value $p (σ, k)$ does not depend on the stage. Nor does the index of a particular follower ever change.

A follower p for σ may become realised at some σ-stage. This will be a σ-stage at which we see $o_{s}^{β, i} (p) < β$ . At a later stage a realised follower may become permitted. An unrealised follower, or a permitted follower, can later be cancelled; a realised but unpermitted follower will only be cancelled if σ is initialised.

A follower $p = p (σ, k)$ will be permitted at a stage s if $k \in W_{e, s} \ W_{e, s - 1}$ . This may not be a σ-stage. To keep $Λ_{e} (D, W_{e})$ total, it is important that we redefine the lifted use $λ_{e, s + 1} (p)$ immediately. For that reason, the proof of Lemma 2.4 doesn’t apply in this construction; it relies on the use being lifted only during σ-stages. We therefore need to actively protect the computations that were covered by that lemma.

To this end, we let $prec (σ)$ be the set of nodes τ which work for some requirement $Q_{d}$ such that $τ \hat{} \infty ≺ σ$ . We let $τ \in {prec}_{\infty} (σ)$ if $τ \hat{} \infty \hat{} \infty_{n} ≺ σ$ for some n; for $y < ω$ , we let $τ \in {prec}_{y} (σ)$ if $τ \hat{} \infty \hat{} f_{y} ≼ σ$ . When a follower p is realised, we define numbers $m^{τ} (p)$ for all $τ \in {prec}_{\infty} (σ)$ (which are not changed later). We then let $Pr (p)$ be the set of pairs $(d, x)$ such that for some $τ \in prec (σ)$ working for $Q_{d}$ , either

$τ \in {prec}_{\infty} (σ)$ , and $x < m^{τ} (p)$ ; or

$τ \in {prec}_{y} (σ)$ , and $x < y$ .

Again, the idea is that for

(d, x) \in Pr (p)

, the computation

Φ_{d} (A, D, x)

should be protected from actions for p.

The functionals $Λ_{e}$ take as oracles both D and $W_{e}$ . We will give each oracle a separate use: each oracle is queried on a single number. We denote the D-use of a computation $Λ (D, W_{e}, p) [s]$ by $λ_{e, s} (p)$ . If $p = p (σ, k)$ for some σ working for $P_{e}^{i}$ , then the $W_{e}$ -use of the computation is k; that is, such a computation can be removed if k later enters $W_{e}$ . Otherwise, no $W_{e}$ -changes can affect the computation (including when p is not currently a follower for such σ).

3.4. Construction

Let s be a stage. First, at s, we observe the effects of enumerations into $W_{e}$ . Let σ be a node which works for requirement $P_{e}^{i}$ ; and suppose that $k \in W_{e, s} \ W_{e, s - 1}$ . Suppose that $p = p (σ, k)$ is currently defined.

If p is currently unrealised, we cancel it.

If p is realised, then we redefine $Λ_{e, s + 1} (D_{s + 1}, W_{e, s}, p)$ with large value and large D-use $λ_{e, s + 1} (p)$ (and no $W_{e}$ -use); we will ensure below that $Λ_{e} (D, W_{e}, p) ↑ [s]$ . Henceforth p is permitted.

If such action occurred, we end the stage.

If the stage was not terminated, we proceed to define the collection $γ_{s}$ of accessible nodes, and act according to the instructions below. The first accessible node is the empty node.

Let $τ \in γ_{s}$ work for requirement $Q_{d}$ . The instructions for τ, and the designation of the next accessible nodes, are precisely as in the previous construction.

Let $σ \in γ_{s}$ work for requirement $P_{e}^{i}$ . There are several possible circumstances for σ which require individual attention.

σ has a permitted follower. There may be more than one permitted follower. For each permitted follower $p = p (σ, k)$ :

If $k \notin Δ_{σ} (A, D) [s]$ , then we cancel the follower p.

If $k \in Δ_{σ} (A, D) [s]$ and $Λ_{e} (D, W_{e}, p) [s] = f_{s}^{β, i} (p)$ , then we enumerate $λ_{e, s} (p)$ into $D_{s + 1}$ , and redefine $Λ_{e, s + 1} (D_{s + 1}, W_{e, s}, p)$ to be large, with large D-use $λ_{e, s + 1} (p)$ (and no $W_{e}$ -use). For all $τ \in {prec}_{\infty} (σ)$ , for all $x ⩾ m^{τ} (p)$ , we cancel the tracker $tr_{s} (τ, x)$ if it is defined.

Now we decide which, if any, child of σ is next accessible:

If $λ_{e, s} (p)$ was enumerated into $D_{s + 1}$ for some follower p, then we initialise all nodes to the right of $σ \hat{} \infty$ , including $σ \hat{} f$ . We do not initialise nodes extending $σ \hat{} \infty$ . We end the stage s.

Otherwise, if all permitted followers were just cancelled, then we let $σ \hat{} \infty$ be next accessible.

Otherwise, we let $σ \hat{} f$ be next accessible.

σ has no permitted followers, but does have a yet unrealised follower $p = p (σ, k)$ . There will be at most one such follower.

If $o_{s}^{β, i} (p) = β$ then we let $σ \hat{} f$ be next accessible.

If $o_{s}^{β, i} (p) < β$ then we let, for all $τ \in {prec}_{\infty} (σ)$ , $m^{τ} (p) = dom Φ_{d} (A, D) [s]$ , where τ works for $Q_{d}$ . The follower p is henceforth realised. We let $σ \hat{} f$ be next accessible.

Suppose that σ has no followers, or that all followers for σ are already realised, but none are permitted.

We maintain $Δ_{σ}$ . For each k such that $p (σ, k)$ is defined, if $k \notin Δ_{σ} (A, D) [s]$ , then we let $k \in Δ_{σ, s + 1} (A_{s}, D_{s})$ with use $\begin{matrix} δ_{σ, s + 1} (k) = max {φ_{d, s} (x) : (d, x) \in Pr (p)} . \end{matrix}$ We will observe below that indeed for each $(d, x) \in Pr (p)$ , $Φ_{d} (A, D, x) ↓ [s]$ .

We then let k be the least element of $W_{e, s}^{∁}$ such that $p (σ, k)$ is yet undefined. We pick a new, large follower p and let $p = p (σ, k)$ . We define $Λ_{e, s + 1} (D_{s}, W_{e, s}, p)$ to be large with large D-use and $W_{e}$ -use k. We initialise all nodes to the right of σ (but not nodes extending $σ \hat{} f$ ). We end the stage.

Note that we eventually run into a long node σ with no followers, so each stage has only finitely many steps.

At the end of every stage, we maintain the functionals $Λ_{e}$ as in the previous construction: for any pair $(e, p) ⩽ s$ such that p is not currently a follower for any node σ working for $P_{e}^{i}$ for some $i < ω$ , if $p \notin dom Λ_{e} (D, W_{e}) [s]$ then we define a permanent computation $Λ_{e} (D, W_{e}, p)$ with use $- 1$ .

3.5. Verification

Before we begin our verification, we need to show that the construction can run smoothly, in that its instructions can be carried out.

Lemma 3.2.
Let σ be a node working for requirement $P_{e}^{i}$ .
If $p = p (σ, k)$ is a realised follower for σ at the start of stage s, and $k \in W_{e, s} \ W_{e, s - 1}$ , then $Λ_{e} (D, W_{e}, p) ↑ [s]$ .

If p is a follower for σ at a σ-stage s, and p is realised by the end of the stage, then for all $(d, x) \in Pr (p)$ , $Φ_{d} (A, D, x) ↓ [s]$ .

Between stages at which σ is initialised, for all k, σ appoints at most one follower $p (σ, k)$ .

Proof.
For (1), let $t < s$ be the stage at which p is appointed. At that stage we define a computation $Λ_{e} (D, W_{e}, p)$ with some D-use $λ_{e, t + 1} (p)$ and $W_{e}$ -use k. We never act for p before it is permitted, and so this computation is preserved until stage s, at which k’s entry into $W_{e}$ invalidates it.

For (2), Let $t ⩽ s$ be the σ-stage at which p is first realised (and $m^{τ} (p)$ and hence $Pr (p)$ defined). Let $(d, x) \in Pr (p)$ ; let $τ \in prec (σ)$ work for $Q_{d}$ . Suppose that $τ \in {prec}_{y} (σ)$ ; so $y > x$ . Since s is a $σ \hat{} \infty \hat{} f_{y}$ -stage, the instructions imply that $y ⩾ dom Φ_{d} (A, D) [s]$ . Suppose that $τ \in {prec}_{\infty} (σ)$ ; so $x < m^{τ} (p)$ . If $t = s$ then we define $m^{τ} (p) = dom Φ_{d} (A, D) [s]$ . If $s > t$ then as s is a $τ \hat{} \infty$ -stage, $dom Φ_{d} (A, D) [s] > t > m^{τ} (p)$ .

For (3), suppose that at stage t, a follower $p = p (σ, k)$ is appointed. Before σ is initialised, p will only be cancelled after k enters $W_{e}$ (either because this happens while p is still unrealised, or after p is permitted.) Later, no new follower $p (σ, k)$ will ever be appointed. □
Lemma 3.3.
For any node σ working for $P_{e}^{i}$ , if $p = p (σ, k)$ is a follower for σ at the beginning of stage s, and it is not the case that $k \in W_{e, s} \ W_{e, s - 1}$ , then $Λ_{e} (D, W_{e}, p) ↓ [s]$ .
Proof.
A computation is defined with $W_{e}$ -use k (where $p = p (σ, k)$ ) at the stage $t < s$ at which p is first appointed. Whenever σ itself destroys the computation by enumerating its D-use into D, a new computation is immediately set up. If k enters $W_{e}$ , we either immediately cancel p (if it is unrealised), or permit p, at which stage a new computation with no $W_{e}$ -use is defined. □

Our next task is to show that protection works: action for a follower p cannot injure a computation $Φ_{d} (A, D, x)$ for any $(d, x) \in Pr (p)$ .
Lemma 3.4.
Let p be a follower for a node σ working for requirement $P_{e}^{i}$ , and suppose that $λ_{e, s} (p) \in D_{s + 1} \ D_{s}$ . Then for all $(d, x) \in Pr (p)$ , $φ_{d, s} (x) < λ_{e, s} (p)$ .
Proof.
The stage s is a σ-stage. The follower $p = p (σ, k)$ received permission at some stage $t < s$ . At stage s, $k \in Δ_{σ} (A, D) [s]$ , as otherwise we would cancel p rather than act for it. Let $r < s$ be the stage at which this enumeration was defined. Then $r < t$ , as between t and s, no new $Δ_{σ} (A, D)$ -enumerations are defined.

As σ was not initialised between stages r and s, by stage r, p was already chosen as a follower and realised. At stage r we define $δ_{σ, s} (k) = δ_{σ, r + 1} (k) = max {φ_{d, r} (x) : (d, x) \in Pr (p)}$ . By our choice of r, we have $A_{r} ↾ δ_{σ, s} (k) = A_{s} ↾ δ_{σ, s} (k)$ , and the same holds for D. Hence for all $(d, x) \in Pr (p)$ , $φ_{d, r} (x) = φ_{d, s} (x)$ by the same computation. At stage t we lift $λ_{e, t + 1} (p)$ to be large, and so $λ_{e, s} (p) > t > φ_{d, r} (x)$ (recall $r < t$ ). □

As in the previous proof, we need to be sure that if a computation is destroyed by a change in D, its tracker is cancelled immediately, to allow us to correctly anticipate further A-changes. Note that the following lemma implies that though we may have infinite positive action by a node on the true path, this action will not injure weaker nodes on the true path: they simply wait for the action and confirm only relatively small numbers.
Lemma 3.5.
Let τ be a node working for requirement $Q_{d}$ . Let s be a stage; let $x < ω$ be such that $c = tr_{s} (τ, x)$ is defined. Suppose that ${\hat{Φ}}_{τ} (A, c) ↓ [s]$ , and let $u = {\hat{φ}}_{τ, s} (c)$ . Then:
$Φ_{d} (A, D, x) ↓ [s]$ and $u = φ_{d, s} (x)$ .

If $D_{s} ↾ u \neq D_{s + 1} ↾ u$ then the tracker c is cancelled at stage s.

Proof.
Suppose that (i) and (ii) hold up to stage s, and that the lemma’s hypotheses hold at s. The proof of part (i) is identical to the corresponding part of Lemma 2.5. Again let $t < s$ be the stage at which the computation ${\hat{Φ}}_{τ} (A, c) [s]$ was defined.

For (ii), suppose that $D_{s} ↾ u \neq D_{s + 1} ↾ u$ ; then at stage s we enumerate a number $λ_{e, s} (p) < u$ into D, where p is a follower for a node σ, which works for requirement $P_{e}^{i}$ .

Since $λ_{e, s} (p) < u = φ_{d, t} (x)$ , we know that the computation $Λ_{e} (D, W_{e}, p) [s]$ was defined prior to stage t; so p was permitted prior to stage t.

As before we ask: how does τ relate to σ?

If σ lies to the right of $τ \hat{} \infty$ , then σ is initialised at stage t; this is impossible. If τ lies to the right of $σ \hat{} \infty$ , then τ is initialised at stage s; in particular, c is cancelled at s.

There are two possibilities left: $σ \hat{} \infty ≼ τ$ , and $τ \hat{} \infty ≺ σ$ .

Suppose that $σ \hat{} \infty ≼ τ$ . Since t is a τ-stage, it is also a $σ \hat{} \infty$ -stage. But at the end of every $σ \hat{} \infty$ -stage, σ has no permitted followers, contradicting p being such a follower.

Hence $τ \hat{} \infty ≺ σ$ , i.e., $τ \in prec (σ)$ . By Lemma 3.4, $(d, x) \notin Pr (p)$ .

Suppose that $τ \in {prec}_{y} (σ)$ . Then $x ⩾ y$ . Since s is a $τ \hat{} \infty \hat{} f_{y}$ -stage, the computation $Φ_{d} (A, D, x) [t]$ is destroyed by stage s; this is not the case. Hence $τ \in {prec}_{\infty} (σ)$ ; and as $x ⩾ m^{τ} (p)$ , at stage s, σ is instructed to cancel c. □

We obtain the analogue of Corollary 2.6:
Corollary 3.6.
Let τ be a node working for requirement $Q_{d}$ . Let $x < ω$ , and suppose that at some point a tracker $c = tr (τ, x)$ is defined and is never cancelled. Suppose that ${\hat{Φ}}_{τ} (A, c) ↓$ . Then $Φ_{d} (A, D, x) ↓$ .

We also obtain the analogue of Lemma 2.7, with the same proof:
Lemma 3.7.
Let σ be a node which works for $P_{e}^{i}$ , and let p be a follower for σ. There are only finitely many stages s at which σ acts on p’s behalf by enumerating $λ_{e, s} (p)$ into $D_{s + 1}$ .

Let the true path, $γ_{ω}$ , consist of the nodes μ such that:
$μ \in γ_{s}$ for infinitely many s; and

μ is initialised only finitely often.
Note that unlike the previous construction, in this construction nodes sometimes get initialised even if they don’t lie to the right of $γ_{s}$ , namely when a node σ acts by enumeration into D. This needs to be taken into consideration when proving some node lies on the true path.
Lemma 3.8.
Suppose that τ works for $Q_{d}$ and that $τ \hat{} \infty \in γ_{ω}$ .
Every $x < ω$ is eventually appointed a tracker which is never cancelled.

If $Φ_{d} (A, D)$ is total then so is ${\hat{Φ}}_{τ} (A)$ , and for some $n < ω$ , $τ \hat{} \infty \hat{} \infty_{n} \in γ_{ω}$ .

If $Φ_{d} (A, D)$ is partial then so is ${\hat{Φ}}_{τ} (A)$ , and $τ \hat{} \infty \hat{} f_{y} \in γ_{ω}$ , where $y = dom Φ_{d} (A, D)$ .

Proof.
The proof is almost identical to the proof of Lemma 2.11. For (1), we need to observe that for all $x < ω$ , there are only finitely many followers p ever appointed such that $m^{τ} (p) ⩽ x$ ; again this happens because $dom Φ_{d} (A, D) [s]$ is strictly increasing on the $τ \hat{} \infty$ -stages; now Lemma 3.7 suffices, we have no need for something like Lemma 2.10.

For (2), we only need to add that if $τ \hat{} \infty \hat{} \infty_{n}$ is initialised at stage s, but this node does not lie to the right of $γ_{s}$ , then τ is initialised at stage s. The same holds for $τ \hat{} \infty \hat{} f_{y}$ for (3). □
Corollary 3.9.
Let $σ \in γ_{ω}$ work for $P_{e}^{i}$ ; let $p = p (σ, k)$ be a realised follower for σ, appointed after the last stage at which σ is initialised. For every $(d, x) \in Pr (p)$ , $Φ_{d} (A, D, x) ↓$ . Hence, the set ${δ_{σ, s} (k) : s < ω is such that k \in Δ_{σ} (A, D) [s]}$ is bounded.
Proof.
Let $(d, x) \in Pr (p)$ ; let $τ \in prec (σ)$ which works for $Q_{d}$ . If $τ \in {prec}_{\infty} (σ)$ then $Φ_{d} (A, D)$ is total. If $τ \in {prec}_{y} (σ)$ then $x < y = dom Φ_{d} (A, D)$ . The second part follows from the definition of $δ_{σ, s + 1} (k)$ . □
Lemma 3.10.
Let $σ \in γ_{ω}$ work for requirement $P_{e}^{i}$ . Then either $σ \hat{} \infty \in γ_{ω}$ or $σ \hat{} f \in γ_{ω}$ .
Proof.
If $σ \hat{} \infty$ is accessible infinitely often, then it lies on the true path. Suppose, then, that this doesn’t happen; let $s^{}$ be a stage after which σ is never initialised, and $σ \hat{} \infty$ never accessible.

There are a couple of possibilities. If there is a stage $t > s^{}$ such that at t, some follower for p is permitted, then after stage t, no new followers will ever be appointed. By Lemma 3.7, there will be only finitely many stages after stage t at which σ is the last accessible stage and $σ \hat{} f$ is initialised. In all other σ stages after stage t, $σ \hat{} f$ is accessible. Hence $σ \hat{} f \in γ_{ω}$ .

Otherwise, $σ \hat{} f$ is not initialised after stage $s^{}$ . We may or may not appoint infinitely many followers for σ. However even if we do, if $t > s^{}$ is a σ-stage at which we appoint a follower and end the stage, then at the next σ-stage, $σ \hat{} f$ is accessible. Hence in this case too, $σ \hat{} f \in γ_{ω}$ . □
Lemma 3.11.
The true path $γ_{ω}$ is infinite.
Proof.
First we need to show that the empty node lies on the true path. This amounts to showing that it is impossible that at all but finitely many stages, some realised follower gets permitted or an unrealised follower cancelled. But in that case, there are only finitely many followers ever appointed, and each such follower is realised or cancelled at most once.

We the observe that every node on the true path has a child on the true path. Nodes τ working for $Q_{d}$ and their derivative nodes are dealt with precisely as in the proof of Lemma 2.12, using Lemma 3.8. Nodes σ working for some $P_{e}^{i}$ are dealt with in Lemma 3.10. □
Lemma 3.12.
For all e, $Λ_{e} (D, W_{e})$ is total.
Proof.
Like the proof of Lemma 2.13, using Lemmas 3.3 and 3.7. □
Lemma 3.13.
Every requirement $P_{e}^{i}$ is met.
Proof.
There are three possibilities.

First, suppose that some follower p for σ is permitted and never cancelled. The argument of Lemma 2.14 shows that $Λ_{e} (D, W_{e}) (p) \neq f^{β, i} (p)$ , and so the requirement is met.

Second, suppose that some follower p for σ is appointed, never cancelled, and never realised. Then $o_{s}^{β, i} (p) = β$ for all s. In this case the requirement $P_{e}^{i}$ is met vacuously: the approximation $⟨ f_{s}^{β, i}, o_{s}^{β, i} ⟩$ is not eventually β-computable.

The last possibility is that every follower is eventually cancelled or realised; but every permitted follower is later cancelled. In this case we show that $Δ_{σ} (A, D) = W_{e}^{∁}$ .

For one direction, we use: Claim 3.13.1.
Suppose that s is a σ-stage and suppose that at stage s, σ has no permitted followers. Then $Δ_{σ} (A, D) [s] \subseteq W_{e, s}^{∁}$ .
Proof.
Let $k \in Δ_{σ} (A, D) [s]$ . Let r be the σ-stage at which the enumeration was defined. At stage r, $p = p (σ, k)$ is defined, realised but not permitted, and so $k \notin W_{e, r}$ . Suppose that k is enumerated into $W_{e, t}$ at some stage $t \in (r, s]$ . Then p becomes permitted at stage t, and so $t < s$ . By assumption, p is cancelled prior to stage s. It is cancelled (at stage $w \in (t, s)$ ) because $k \notin Δ_{σ} (A, D) [w]$ , contrary to our choice of r. □

Now we note that there are infinitely many σ-stages s at which σ has no permitted follower: suppose that t is a σ-stage at which σ has some permitted followers. While σ has some permitted followers, no new followers are appointed. Each permitted follower is eventually cancelled. Hence, even if more followers are permitted (while some permitted followers from stage t are still around), eventually there will be a $σ \hat{} \infty$ -stage. The next σ-stage after that is as required. Overall, we conclude that $Δ_{σ} (A, D) \subseteq W_{e}^{∁}$ .

In the other direction, we observe that there are infinitely many σ-stages s at which option (iii) is taken: $Δ_{σ}$ is maintained and a new follower is appointed. If r is such a stage (after the last stage at which σ is initialised), then at some the follower p appointed at stage r is either cancelled or realised at some stage $t > r$ . Either the next σ stage after stage t is as required; or some follower for σ is permitted before that next σ-stage. We then undergo an “attack cycle”; as above, the next σ-stage after the following $σ \hat{} \infty$ -stage is as required.

By induction on $k \in W_{e}^{∁}$ , we show that at some stage s we appoint a follower $p = p (σ, k)$ . Since $k \notin W_{e}$ , this follower is never cancelled. Hence it is never permitted; but by assumption, it is at some point realised. At infinitely many σ-stages s, if $k \notin Δ_{σ} (A, D) [s]$ , then we define a new enumeration at stage s. By Corollary 3.9, all of these enumerations’ uses are bounded, and so one must be $(A, D)$ -correct. Hence $k \in Δ_{σ} (A, D)$ . □

The following will conclude the proof of Theorem 3.1. Lemma 3.14.
For all $d < ω$ , the requirement $Q_{d}$ is met.
Proof.
The proof is similar to the proof of Lemma 2.15, but simpler, because we do not need to count the (ordinal) number of possible followers for a node σ.

Let $d < ω$ , and suppose that $Φ_{d} (A, D)$ is total. Let τ be the node on the true path working for $Q_{d}$ . Then $τ \hat{} \infty \in γ_{ω}$ ; by Lemmas 3.8 and 3.11, for some n and $k < ω$ , $ρ = τ \hat{} \infty \hat{} \infty_{n} \hat{} k$ lies on the true path. Let $s_{0} < s_{1} < \dots$ be the ρ-stages following the last stage at which ρ is initialised. We proceed to define an $(α β)$ -computable approximation $⟨ f_{s}, o_{s} ⟩$ for $Φ_{d} (A, D)$ .

From now on, fix $x < ω$ . Let $j^{} = j^{} (x)$ be the least $j > 0$ such that $x < s_{j - 1}$ . For all $j ⩾ j^{}$ , $Φ_{d} (A, D, x) ↓ [s_{j}]$ . So for all $j ⩾ j^{}$ we let $f_{j} (x) = Φ_{d} (A, D, x) [s_{j}]$ . Certainly ${lim}_{j \to \infty} f_{j} (x) = Φ_{d} (A, D, x)$ . Let $u_{j} = u_{j} (x) = φ_{d, s_{j}} (x)$ .

Again we measure A-changes and D-changes. The A-changes are measured exactly as in the previous construction: for $j ⩾ j^{}$ we define $\begin{matrix} θ_{j} = θ_{j} (x) = o_{s_{j}}^{α, k} (c_{j}), \end{matrix}$ where $c_{j} = c_{j} (x) = tr_{s_{j}} (τ, x)$ . We again use the following claim, whose proof is identical to the proof of Claim 2.15.1. Claim 3.14.1.
For all* $j ⩾ j^{}$ , $θ_{j} < α$ . Suppose that* $c_{j} = c_{j + 1}$ . Then $θ_{j} ⩾ θ_{j + 1}$ ; and if $A_{s_{j}} ↾ u_{j} \neq A_{s_{j + 1}} ↾ u_{j}$ then $θ_{j} > θ_{j + 1}$ .

To measure the D-changes, we let $a = a (x)$ be the collection of followers p for nodes $σ ≽ ρ$ which are already realised by stage $s_{j^{}}$ (and not cancelled before that stage). We do not need to define $a_{j}$ . For each follower $p \in a (x)$ let $T (p)$ be the set of stages t such that either:
p is realised at stage t; or

at stage t, p’s node σ enumerates $λ_{e, t} (p)$ into $D_{t + 1}$ (where σ works for $P_{e}^{i}$ ).
So for all $p \in a (x)$ , $min T (p) < s_{j^{}}$ . As above, for $t \in T (p)$ we let $\begin{matrix} ϵ_{t} (p) = o_{t}^{β, i} (p) . \end{matrix}$ Claim 3.14.2.
For all $p \in a (x)$ , for all $t \in T (p)$ , $ϵ_{t} (p) < β$ . If $t_{0} < t_{1}$ are stages in $T (p)$ then $ϵ_{t_{0}} (p) > ϵ_{t_{1}} (p)$ .
Proof.
The first part follows from the fact that p is realised at or before stage t. The second part is similar to the proof of Claim 2.15.2. Since $t_{1} \neq min T (p)$ , we have $Λ_{e} (D, W_{e}, p) [t_{1}] = f_{t_{1}}^{β, i} (p)$ , where p’s node σ works for $P_{e}^{i}$ . The follower p was permitted before stage $t_{1}$ . Again the point is that $Λ_{e} (D, W_{e}, p) [t_{1}] > t_{0}$ , as the $t_{1}$ -computation is defined no later than stage $t_{0}$ : either σ acts for p at stage $t_{0}$ and defines a new computation then; or $t_{0} = min T (p)$ and p is permitted at some stage between $t_{0}$ and $t_{1}$ , at which a new computation is defined. □

Finally, we need: Claim 3.14.3.
Let $j ⩾ j^{}$ . Suppose that* $Φ_{d} (A, D, x) [s_{j}] \neq Φ_{d} (A, D, x) [s_{j + 1}]$ , and that $s_{j} \notin ⋃_{p \in a} T (p)$ . Then $θ_{j} > θ_{j + 1}$ .
Proof.
Essentially identical to the proof of Claim 2.15.5. We need to show that if action for a follower p of a node σ destroys the $s_{j}$ -computation then $p \in a$ . The argument is the same: σ must be an extension of ρ, and p must be realised prior to stage $s_{j^{}}$ , otherwise $x < m^{τ} (p)$ . □

The rest is again the same (but simpler). For each $j ⩾ j^{}$ and $p \in a$ , we let $\begin{matrix} t_{j} (p) = max T (p) \cap s_{j} . \end{matrix}$ We then let $\begin{matrix} o_{j} (x) = α \cdot ⨁_{p \in a} ϵ_{t_{j} (p)} (p) + θ_{j} . \end{matrix}$ The claims above show this works. □

4. Above a superlow c.e. degree

Recall that a set A is superlow if $A^{'} \equiv_{wtt} \emptyset^{'}$ . If A is c.e. then superlowness is equivalent to a stronger property, namely the approximability of the jump function. To make sense of approximations, we identify a partial function φ with a total function from ω to $ω \cup {↑}$ , where the value ↑ denotes that the input is not in the domain of φ. Schaeffer [13] showed that a c.e. set is superlow if and only if every A-partial computable function φ is ω-c.a., considered as a total function. That is, there is an ω-computable approximation $⟨ f_{s} ⟩$ of functions from ω to $ω \cup {↑}$ such that $φ = {lim}_{s} f_{s}$ . It follows that every c.e., superlow degree is totally ω-c.a. In fact, because there is a universal A-partial computable function, every c.e. superlow set is array computable.

Theorem 4.1.
Let $β ⩽ ϵ_{0}$ be a power of ω. Every c.e. superlow degree is bounded by a (c.e.) maximal β-c.a. degree (and hence by a properly β-c.a. degree).

Let A be a superlow c.e. set. We enumerate a set D such that ${deg}_{T} (A \oplus D)$ is maximal β-c.a.
4.1. Requirements

The requirements are similar to the ones for the previous construction (Section 2). Let ${⟨ Φ_{d} ⟩}_{d < ω}$ be an enumeration of all Turing functionals. To make $A \oplus D$ totally β-c.a., we need to ensure, $\begin{matrix} for all d < ω, Q_{d} : If Φ_{d} (A, D) is total, then it is β -c.a. \end{matrix}$

For the maximality property, we enumerate a Turing functional $Λ_{e}$ with the intent that either $W_{e} ⩽_{T} A \oplus D$ , or $Λ_{e} (D, W_{e})$ is not β-c.a. We meet the following set of requirements: $\begin{matrix} for all e, i < ω, P_{e}^{i} : If ⟨ f_{s}^{β, i}, o_{s}^{β, i} ⟩ is eventually β -computable, then Λ_{e} (D, W_{e}) \neq f^{β, i}, or W_{e} ⩽_{T} A \oplus D . \end{matrix}$

4.2. Discussion

The construction is similar to the previous one (proving Theorem 3.1). The extra strength we have is the ability to approximation not only total A-computable functions but also partial ones. How does this help? Now a node τ, working for $Q_{d}$ , is not required to make ${\hat{Φ}}_{τ} (A)$ total, even if $Φ_{d} (A, D)$ is. What this means is that we are allowed to reserve future trackers for each input x for $Φ_{d} (A, D)$ .

Consider first the simpler case, $β = ω$ . In this case, a node τ, upon first certifying a computation $Φ_{d} (A, D, x)$ , knows a bound on the number k of times a D-enumeration can injure a computation it certifies. It can reserve a set of k-many trackers and immediately find a bound on the number of times any one of them will record an A-change. Adding these up we get an overall bound and so can give an ω-computable approximation for $Φ_{d} (A, D, x)$ . If the number of D-changes does not reach the bound k then ${\hat{Φ}}_{τ} (c)$ will remain undefined for some unused trackers.

In the slightly more complicated case $β > ω$ , we present the ordinal bound on D-changes at a given stage t as $δ_{t} + m_{t}$ , where $δ_{t}$ is a limit ordinal (smaller than β) and $m_{t} < ω$ . If t is the first stage at which we see the current value of $δ_{t}$ then we reserve a set of $m_{t}$ -many trackers, and get a bound on the number of A- and D-changes until the limit ordinal $δ_{t}$ is decreased. When we get a new version of $δ_{t}$ , we repeat the process with a new set of trackers.

4.3. Strategy tree

A less important yet convenient advantage in the superlow case is the existence of a universal A-partial computable function; this gives us a way to obtain approximations uniformly, so they don’t need to be guessed. A node τ on the tree working for $Q_{d}$ has two outcomes $\infty < f$ , with $τ \hat{} f$ working for the next, weaker requirement on our ω-list of requirements. The node $τ \hat{} \infty$ has outcomes $\infty < f_{0} < f_{1} < f_{2} < \dots$ .

The node τ enumerates a “shadow” functional ${\hat{Φ}}_{τ}$ as in the previous constructions. By the fixed-point theorem, we know an index for this functional, that is, a column of the jump function $J^{A}$ which copies ${\hat{Φ}}_{τ} (A)$ . Using a fixed ω-computable approximation for $J^{A}$ , we obtain, uniformly in τ, an ω-computable approximation $⟨ f_{s}^{τ}, o_{s}^{τ} ⟩$ of ${\hat{Φ}}_{τ} (A)$ . We use this not only to track the number of A-changes of a computation $Φ_{d} (A, D, x)$ (between two D-changes), but also to replace the ${low}_{2}$ guessing procedure that indirectly gave us a guess about $dom Φ_{d} (A, D)$ ; lowness allows us to directly ask if ${\hat{Φ}}_{τ} (A, c) ↓$ , and as above if c is the last tracker for $y = dom Φ_{d} (A, D)$ then ${\hat{Φ}}_{τ} (A, c) ↑$ .

Nodes σ working for $P_{e}^{i}$ again have two outcomes $\infty < f$ . We let $prec (σ)$ be the collection of nodes τ working for some $Q_{d}$ such that $τ \hat{} \infty ≼ σ$ . We let ${prec}_{\infty} (σ)$ be the collection of nodes τ such that $τ \hat{} \infty \hat{} \infty ≼ σ$ ; for $y < ω$ , we let ${prec}_{y} (σ)$ be the collection of nodes τ such that $τ \hat{} \infty \hat{} f_{y} ≼ σ$ . As above, when a follower p for σ is realised we define $m^{τ} (p)$ for all $τ \in {prec}_{\infty} (σ)$ ; this will define $Pr (p)$ in the same way as in the previous construction.

4.4. Construction

The construction is identical to the construction proving Theorem 3.1, except that the behaviour of the τ-nodes is a bit simpler. Every stage s starts with an attempt to permit realised followers of nodes σ, or cancel unrealised followers for such nodes, based on enumerations of numbers into $W_{e, s}$ . The instructions are the same as in the previous construction.

Suppose that a node τ, working for requirement $Q_{d}$ , is accessible at stage s. Let $t < s$ be the last stage before s at which $τ \hat{} \infty$ was accessible, or $t = 0$ if there is no such stage. If $dom Φ_{d} (A, D) [s] ⩽ t$ , we let $τ \hat{} f$ be next accessible. Otherwise we let $τ \hat{} \infty$ be next accessible.

Suppose that $τ \hat{} \infty$ is accessible. We maintain the shadow functional and assign new trackers. For all x such that $c = tr_{s} (τ, x)$ is already defined, if ${\hat{Φ}}_{τ} (A, c) ↑ [s]$ then we define a new computation ${\hat{Φ}}_{τ, s + 1} (A_{s}, c)$ with use $φ_{d, s} (x)$ (and large value). For each $x < s$ for which $tr_{s} (τ, x)$ is undefined we appoint a new tracker $tr_{s + 1} (τ, x)$ . Unlike the previous constructions, this new tracker is chosen as the next unused element of the column $ω^{[x]}$ which is reserved for trackers for x.

Next we determine which outcome is accessible. Let r be the previous $τ \hat{} \infty \hat{} \infty$ -stage, $r = 0$ if there is no such stage. If for all $x < r$ , $c = tr_{s} (τ, x)$ is already defined and ${\hat{Φ}}_{τ} (A, c) ↓ [s] = f_{s}^{τ} (c)$ then we let $τ \hat{} \infty \hat{} \infty$ be next accessible.

Otherwise, let y be the least number such that $Φ_{d} (A, D) ↑ [t]$ , or the computation $Φ_{d} (A, D, y) [t]$ was destroyed since stage t. We let $τ \hat{} \infty \hat{} f_{y}$ be next accessible.

The instructions for a node σ working for $P_{e}^{i}$ are identical to those given in the previous construction.

At the end of every stage we maintain the functionals $Λ_{e}$ as above.

4.5. Verification

Most of the verification follows that of the previous construction, except that in places it is simpler. We list the lemmas we need. Lemma 3.2 and its proof is copied verbatim, as are the statements and proofs of Lemmas 3.3 to 3.5 and 3.7 and Corollary 3.6.

Lemma 3.8 is different. Indeed, ${\hat{Φ}}_{τ} (A)$ will be partial. The following is what we need:

Lemma 4.2.
Suppose that τ works for D and that $τ \hat{} \infty \in γ_{ω}$ .
Every $x < ω$ is eventually appointed a tracker which is never cancelled.

If $Φ_{d} (A, D)$ is total then $τ \hat{} \infty \hat{} \infty \in γ_{ω}$ .

If $Φ_{d} (A, D)$ is partial then $τ \hat{} \infty \hat{} f_{y} \in γ_{ω}$ , where $y = dom Φ_{d} (A, D)$ .

Proof.
(1) is proved in the same way as the corresponding part of Lemma 3.8.

(2) is not complicated; for every $r < ω$ , eventually each $x < r$ will be appointed a permanent tracker c, and as $Φ_{d} (A, D, x) ↓$ , eventually a permanent computation ${\hat{Φ}}_{τ} (A, c)$ will be defined, and eventually we will see it is equal to $f^{τ} (c)$ .

The interesting part is (3). Suppose that $y = dom Φ_{d} (A, D)$ is finite. For every $x < y$ , the outcome $f_{x}$ is guessed only finitely many times. It remains to show that the outcome ∞ is chosen only finitely many times. Let c be the tracker which is appointed for y and is never cancelled. Again by the analogue of Corollary 3.6, ${\hat{Φ}}_{τ} (A, c) ↑$ . This by itself is not sufficient to prove that the outcome ∞ is chosen only finitely many times, as we may see infinitely many false convergences. However, since ${\hat{Φ}}_{τ} (A, c) ↑$ , for all but finitely many s, $f_{s}^{τ} (p) = ↑$ , and this guarantees what we need. □

Corollary 3.9 and Lemmas 3.10 to 3.13 now follow, with the same proofs. All that remains is: Lemma 4.3.
For all $e < ω$ , the requirement $Q_{d}$ is met.
Proof.
We start as in the proof of Lemma 3.14. Let τ on the true path work for $Q_{d}$ , and suppose that $Φ_{d} (A, D)$ is total. Let $ρ = τ \hat{} \infty \hat{} \infty$ ; ρ is on the true path. Let $s_{0} < s_{1} < s_{2} < \dots$ be the ρ-stages after the last stage at which ρ is initialised. Fix $x < ω$ ; let $j^{}$ be the least such that $x < s_{j - 1}$ . For all $j ⩾ j^{}$ we let $f_{j} (x) = Φ_{d} (A, D, x) [s_{j}]$ .

Our mechanisms for counting A- and D-changes are the same. We define $c_{j}$ as in the previous argument; we then let $\begin{matrix} θ_{j} = o_{s_{j}}^{τ} (c_{j}); \end{matrix}$ then $θ_{j} < ω$ . We then prove Claim 3.14.1 in the same way, noting that $f_{s_{j}}^{τ} (c_{j}) = {\hat{Φ}}_{τ} (A, c_{j}) [s_{j}]$ for all j. For the D-changes we define $a = a (x)$ and for $p \in a$ , the set $T (p)$ of stages, as above. Similarly we define $ϵ_{t} (p)$ for $t \in T (p)$ , and prove Claims 3.14.2 and 3.14.3. In fact, we require the following, which is part of the proof of Claim 3.14.3: Claim 4.3.1.
Let $j ⩾ j^{}$ . If* $c_{j} \neq c_{j + 1}$ then:
$s_{j} \in ⋃_{p \in a} T (p)$ ; and

$c_{j + 1}$ is the successor of $c_{j}$ in $ω^{[x]}$ .

This means: if $c_{j} \neq c_{j + 1}$ then we know that $c_{j}$ is cancelled at stage $s_{j}$ by some $p \in a$ ; further, $c_{j + 1}$ is the next tracker for x appointed at the next $τ \hat{} \infty$ -stage after stage $s_{j}$ – that tracker is not cancelled until possibly stage $s_{j + 1}$ . The point again is that nodes accessible between stages $s_{j}$ and $s_{j + 1}$ cannot cancel trackers for x: only nodes extending ρ may do so.

Now define $t_{j} (p)$ as above; we then write, for each $j ⩾ j^{*}$ , $\begin{matrix} ⨁_{p \in a} ϵ_{t_{j} (p)} (p) = δ_{j} + m_{j}, \end{matrix}$ where $δ_{j} < β$ is a limit ordinal (or 0), and $m_{j} < ω$ .

We let $C_{j}$ be the set of consecutive elements of $ω^{[x]}$ starting with $c_{j}$ and having size $m_{j} + 1$ . That is, $C_{j}$ consists of the current tracker $c_{j}$ , and the next $m_{j}$ -many numbers that may be assigned as future trackers. We let $\begin{matrix} n_{j} = \sum_{c \in C_{j}} o_{s_{j}}^{τ} (c) . \end{matrix}$ We then let $\begin{matrix} o_{j} (x) = δ_{j} + m_{j} + n_{j} . \end{matrix}$

To prove that this works, we first need to show that if $δ_{j} = δ_{j + 1}$ then $n_{j} ⩾ n_{j + 1}$ . This will follow once we show that $C_{j} \supseteq C_{j + 1}$ . Note that under the assumption $δ_{j} = δ_{j + 1}$ , we have $m_{j} ⩾ m_{j + 1}$ . If $c_{j} = c_{j + 1}$ then $C_{j} \supseteq C_{j + 1}$ is clear. If $c_{j} \neq c_{j + 1}$ then $s_{j} \in ⋃_{p \in a} T (p)$ , and so $δ_{j} + m_{j} > δ_{j + 1} + m_{j + 1}$ ; it follows that $m_{j} > m_{j + 1}$ , and then $c_{j + 1}$ being $c_{j}$ ’s successor in $ω^{[x]}$ yields $C_{j} \supseteq C_{j + 1}$ . Hence for all j, $o_{j} (x) ⩾ o_{j + 1} (x)$ .

Suppose that $Φ_{d} (A, D, x) [s_{j}] \neq Φ_{d} (A, D, x) [s_{j + 1}]$ . If $s_{j} \in ⋃_{p \in a} T (p)$ and $δ_{j} = δ_{j + 1}$ then $m_{j} > m_{j + 1}$ (and $n_{j} ⩾ n_{j + 1}$ ); so $o_{j} (x) > o_{j + 1} (x)$ . Otherwise, $θ_{j} > θ_{j + 1}$ , and as $c_{j} \in C_{j}$ , this implies $n_{j} > n_{j + 1}$ ; in this case too $o_{j} (x) > o_{j + 1} (x)$ . □

4.6. Higher levels of superlowness

We can generalise superlowness to higher ordinals:

Definition 4.4.
Let $α ⩽ ϵ_{0}$ . A set A is α-superlow if $A^{'}$ is α-c.a.

If A is c.e. then A is α-superlow if every A-partial computable function is α-c.a., equivalently, if a universal A-partial computable function (often denoted by $J^{A}$ ) is α-c.a. Every α-superlow (c.e.) degree is totally α-c.a. This is tight:
Proposition 4.5.
Let $α ⩽ ϵ_{0}$ be a power of ω. Then there is an α-superlow degree which is not totally γ-c.a. for any $γ < α$ .
Sketch of proof.
This is a finite injury construction with shifting priorities. We enumerate a c.e. set C and a functional Λ. The requirements to meet are:
For $γ < α$ and $i < ω$ , $P^{γ, i}$ : $Λ (C) \neq f^{γ, i}$ .
and
For all $x < ω$ , $N_{x}$ : $J^{C} (x)$ has an α-computable approximation.
A requirement $P^{i, γ}$ appoints a follower p, defines $Λ (C, p) [s]$ and when it observes that $Λ (C, p) [t] = f_{t}^{γ, i} (p)$ then it enumerates $λ_{t} (p)$ into $C_{t + 1}$ and defines a new computation (with a new large use).

Let $⟨ P_{e} ⟩$ be an ω-listing of all positive requirements. We start with the priority ordering $P_{0} < N_{0} < P_{1} < N_{1} < \dots$ .

A requirement $N_{x}$ observes the action of positive requirements stronger than it. When it sees a new $J^{C} (x)$ computation, it will cancel the followers of all weaker positive requirements. However, when a positive requirement $P_{e}$ acts, at some stage t, it not only cancels the followers for all weaker positive requirements, it also demotes them down the ordering: every requirement $P_{e^{'}}$ for $e^{'} > e$ is now declared weaker than $N_{t}$ .

By induction, we see that every positive requirement $P_{e}$ is eventually never kicked down the list, and acts only finitely often. Indeed, suppose that stage s is the last stage at which positive requirements $P_{\bar{e}}$ for $\bar{e} < e$ ever acts. Then at stage s the final priority for $P_{e}$ is determined to be between $N_{s}$ and $N_{s + 1}$ . After stage s, each requirement $N_{x}$ for $x ⩽ s$ will cancel $P_{e}$ ’s follower at most once. This is because no positive requirement stronger than $N_{x}$ will act after stage s. Thus, every $J^{C} (x)$ computation observed by $N_{x}$ after stage s is permanent.

What’s left is calculating an ordinal bound on the “number of times” that a computation $J^{C} (x)$ observed by $N_{x}$ is injured by the action of a positive requirement stronger than $N_{x}$ . Let $P_{e}$ be stronger than $N_{x}$ at some stage s. Then we know that $P_{e}$ will not appoint more than x many followers while it is still stronger than $N_{x}$ . This is the same argument: while $P_{e}$ is stronger than $N_{x}$ , no requirement $P_{\bar{e}}$ for $\bar{e} < e$ acts. During that period, for each $N_{y}$ stronger than $P_{e}$ , we have $y < x$ , and $N_{y}$ will cancel $P_{e}$ ’s follower at most once, as its own $J^{C} (y)$ computation cannot be injured. Hence we can put an ordinal bound of $γ \cdot x$ on the total number of injuries that $P_{e}$ can cause $N_{x}$ , where $P_{e} = P^{γ, i}$ for some i. Since α is closed under addition, $γ \cdot x < α$ . Adding for x many positive requirements ( $P_{e}$ for $e ⩽ x$ ) still lands us below α. □

However, trying to generalise the proof of Theorem 4.1 to α-superlow degrees instead of superlow degrees does not work. Here the fundamental difference is the one between the number of times and (an ordinal) “number of times”. If A is α-superlow then the number $n_{j}$ in the proof of the last lemma is replaced by some ordinal below α; but we need, at each stage, consider $c_{j}$ and only finitely many other trackers in the set $C_{j}$ . There is no ordinal way to add up the ordinals for infinitely many potential trackers. This means that in examining the ordinal number of potential D-changes, we cannot replace the presentation $δ_{j} + m_{j}$ by some $δ_{j} + γ_{j}$ , where $γ_{j} < α$ and $δ_{j}$ is an ordinal multiple of α: such $γ_{j}$ does not tell us in advance a finite bound on the number of tracker needed before we see a change in $δ_{j}$ . If we stick to the presentation $δ_{j} + m_{j}$ , with $m_{j} < ω$ , then defining $o_{j} (x) = δ_{j} + m_{j} + η_{j}$ where $η_{j} < α$ (or some other combination of $m_{j}$ and the ordinals for potential trackers in $C_{j}$ ); but $δ_{j}$ is not a multiple of α, and then $o_{j} (x)$ is not necessarily decreasing. Hence we ask:
Question 4.6.
Is every $ω^{2}$ -superlow degree bounded by a maximal totally $ω^{2}$ -c.a. degree? Maximal $ω^{n}$ -c.a. for some or all $n < ω$ ?
5. A maximal interval and a proper ideal

5.1. A maximal interval

In this section we prove:

Theorem 5.1.
Let $α ⩽ ϵ_{0}$ be a power of ω. There are totally α-c.a. degrees $a < b$ such that every totally α-c.a. degree above a is below b .

So not only is b maximal totally α-c.a., it is even maximal over a.

We enumerate c.e. sets A and B with the intention that $a = {deg}_{T} (A)$ and $b = {deg}_{T} (A \oplus B)$ are as promised in the theorem.
5.1.1. Requirements

Some of the requirements are familiar. Let ${⟨ Φ_{d} ⟩}_{d < ω}$ be an enumeration of all Turing functionals. To make $A \oplus B$ totally α-c.a., we need to ensure, $\begin{matrix} for all d < ω, Q_{d} : If Φ_{d} (A, B) is total, then it is α -c.a. \end{matrix}$

For the maximality property, for each e, we enumerate a Turing functional $Λ_{e}$ with the intent that either $W_{e} ⩽_{T} A \oplus B$ , or $Λ_{e} (A, W_{e})$ is not α-c.a. We meet the following set of requirements: $\begin{matrix} for all e, i < ω, P_{e}^{i} : If ⟨ f_{s}^{α, i}, o_{s}^{α, i} ⟩ is eventually α -computable, then Λ_{e} (A, W_{e}) \neq f^{α, i}, or W_{e} ⩽_{T} A \oplus B . \end{matrix}$

Finally, we add Friedberg–Muchnik requirements: $\begin{matrix} for all c < ω, R_{c} : Ψ_{c} (A) \neq B . \end{matrix}$ Here $⟨ Ψ_{e} ⟩$ is an effective list of all Turing functionals; we use different notation to avoid confusion between requirements.

5.1.2. Discussion

This is a mild elaboration on the construction of a maximal totally α-c.a. degree from [5]. Essentially, we show that that construction is compatible with the introduction of extra Friedberg–Muchnik requirements. Each such requirement acts at most once, and so it is not difficult to take into account how many injuries of this kind a certified computation $Φ_{d} (A, B, x)$ will sustain.

Compared to previous constructions, this construction is simplified by not having to work over a given A.

5.1.3. Strategy tree

The tree is simplified as a result. A node τ working for $Q_{d}$ has two outcomes $\infty < f$ . Both outcomes work for the next requirement.

A node σ working for $P_{e}^{i}$ will appoint followers $p (σ, k)$ as in the previous two constructions. We let ${prec}_{\infty} (σ)$ be the set of nodes τ working for some $Q_{d}$ such that $τ \hat{} \infty ≼ σ$ . Followers will be realised, permitted and cancelled as in previous constructions; again we define $m^{τ} (p)$ for each $τ \in {prec}_{\infty} (σ)$ , and let $Pr (p)$ be the set of pairs $(d, x)$ such that $x < m^{τ} (p)$ for $τ \in {prec}_{\infty} (σ)$ working for $Q_{d}$ . And as above, the node σ will build an enumeration operator $Δ_{σ}$ . The behaviour of σ is much simplified; in fact, we barely need the functional $Δ_{σ}$ , and keep it for consistency of presentation with the previous constructions. Indeed, if we see no reason to cancel a follower when it is permitted, then we will not need to cancel it later, and the attack with this follower will succeed.

Nodes σ working for requirements $P_{e}^{i}$ , and nodes ρ working for requirements $R_{c}$ , have only one outcome. Their action will be finitary.

5.1.4. Construction

Let s be a stage. Let σ be a node which works for requirement $P_{e}^{i}$ ; and suppose that $k \in W_{e, s} \ W_{e, s - 1}$ . Suppose that $p = p (σ, k)$ is currently defined.

If $k \notin Δ_{σ} (A, B) [s]$ then we cancel p.

Otherwise, we redefine $Λ_{e, s + 1} (A_{s + 1}, W_{e, s}, p)$ with large value and large A-use $λ_{e, s + 1} (p)$ (and no $W_{e}$ -use). Henceforth p is permitted. We cancel all other followers for σ, and initialise all nodes weaker than σ (including proper extensions of σ). We end the stage.

Note that if more than one node σ wishes to act as in (2), then we act for the strongest one only, as the others will be immediately initialised.

If the stage was not terminated, we proceed to define the collection $γ_{s}$ of accessible nodes, and act according to the instructions below. The first accessible node is the empty node.

Let $τ \in γ_{s}$ work for requirement $Q_{d}$ . Let t be the last $τ \hat{} \infty$ -stage prior to stage s, if there was one; $t = 0$ otherwise. We let $τ \hat{} \infty \in γ_{s}$ if $dom Φ_{d} (A, B) [s] > t$ ; otherwise $τ \hat{} f \in γ_{s}$ .

Let $σ \in γ_{s}$ work for requirement $P_{e}^{i}$ . One of the following will hold:

σ has permitted follower p. If $Λ_{e} (A, W_{e}, p) [s] = f_{s}^{β, i} (p)$ , then we enumerate $λ_{e, s} (p)$ into $A_{s + 1}$ , and redefine $Λ_{e, s + 1} (A_{s + 1}, W_{e, s}, p)$ to be large, with large A-use $λ_{e, s + 1} (p)$ (and no $W_{e}$ -use); we then end the stage. Otherwise, we let σ’s child be next accessible.

σ has a yet unrealised follower p. If $o_{s}^{α, i} (p) < α$ then we let, for all $τ \in {prec}_{\infty} (σ)$ , $m^{τ} (p) = dom Φ_{d} (A, B) [s]$ , where τ works for $Q_{d}$ . The follower p is henceforth realised. In either case, we let σ’s child be next accessible.

σ has no followers, or all followers for σ are already realised, but none are permitted.

We maintain $Δ_{σ}$ . For each k such that $p (σ, k)$ is defined, if $k \notin Δ_{σ} (A, B) [s]$ , then we let $k \in Δ_{σ, s + 1} (A_{s}, B_{s})$ with use $\begin{matrix} δ_{σ, s + 1} (k) = max {φ_{d, s} (x) : (d, x) \in Pr (p)} . \end{matrix}$ We then let k be the least element of $W_{e, s}^{∁}$ such that $p (σ, k)$ is yet undefined. We pick a new, large follower p and let $p = p (σ, k)$ . We define $Λ_{e, s + 1} (A_{s}, W_{e, s}, p)$ to be large with large A-use and $W_{e}$ -use k. We then let σ’s child be next accessible.

Suppose that $ρ \in γ_{s}$ works for requirement $R_{c}$ .

If ρ has no follower, then we appoint a new, large follower q. We end the stage.

If ρ has a follower q, $Ψ_{c} (A, q) ↓ [s] = 0$ , and $q \notin B_{s}$ , then we enumerate q into $B_{s + 1}$ , and end the stage.

Otherwise, we let ρ’s child be next accessible.

At the end of the stage we initialise all nodes weaker than the last accessible node (including all proper extensions of that node). We also maintain the functionals $Λ_{e}$ as usual to ensure their totality.

5.1.5. Verification

The usual lemma that ensures that the construction goes smoothly holds. Lemma 3.2 holds (in (1), of course, replace D by A; in (2), by B); the proofs are simpler. Similarly with Lemmas 3.3, 3.7 and 3.12.

The finitary nature of the construction and the simplicity of the $Σ_{2} / Π_{2}$ behaviour of nodes that work for $Q_{d}$ show that the true path is infinite, and that every Friedberg–Muchnik requirement $R_{c}$ is met. Toward showing that the $P_{e}^{i}$ requirements are met, we need to prove that $A \oplus B$ is ${low}_{2}$ .

Lemma 5.2.
Let τ be a node working for $Q_{d}$ . Let $\bar{t} < t$ be $τ \hat{} \infty$ -stages; let $x < \bar{t}$ .
Let $ρ ≽ τ \hat{} \infty$ be a node working for $R_{c}$ . Suppose that at t, ρ has a follower q; and suppose that q was appointed at some stage $r \in (\bar{t}, t)$ . Then $Φ_{d} (A, B, x) ↓ [t]$ and $q > φ_{d, t} (x)$ .

Let $σ ≽ τ \hat{} \infty$ be a node working for $P_{e}^{i}$ . Suppose that at t, σ has a permitted follower p; and suppose that p became realised at some stage $r \in (\bar{t}, t)$ . Then $Φ_{d} (A, B, x) ↓ [t]$ and $λ_{e, t} (p) > φ_{d, t} (x)$ .

Proof.
(1): The stage r is a $τ \hat{} \infty$ -stage greater than $\bar{t}$ , so $x < dom Φ_{d} (A, B) [r]$ ; q is chosen large, so $q > φ_{d, r} (x)$ . We claim that $A_{r} ↾ φ_{d, r} (x) = A_{t} ↾ φ_{d, r} (x)$ and that the same holds for B; it follows that $x < dom Φ_{d} (A, B) [t]$ and that $φ_{d, t} (x) = φ_{d, r} (x)$ . For suppose that at some stage $s \in [r, t)$ , a number $u < φ_{d, r} (x)$ enters either A or B. This is done by some node μ. Since ρ is not initialised at stage s, μ must be weaker than ρ. Certainly $μ \neq ρ$ since $q > φ_{d, r} (x)$ . Hence μ is initialised at stage r. But this means that any number associated with μ at stage s must be greater than r, which is impossible.

(2) is similar, with the complication being that the stage $w \in (r, t)$ at which p became permitted is not a $τ \hat{} \infty$ -stage. We do note however that r is a $τ \hat{} \infty$ -stage and so that $m^{τ} (p) > x$ . Since p is not cancelled at stage w, we know that $k \in Δ_{σ} (A, B) [w]$ , where $p = p (σ, k)$ . Let u be the stage at which this enumeration was defined; so u is a σ-, hence a $τ \hat{} \infty$ -stage, and $r ⩽ u < w < t$ . At stage u we define $δ_{σ, u} (k) ⩾ φ_{d, u} (x)$ , and there is no change in either A or B below $δ_{σ, u} (x)$ between stages u and w. At stage w we define $λ_{e, w + 1} (p)$ to be large, and initialise nodes weaker than σ. Now the argument for (1) works: by considering initialisations, no node μ can enumerate a number smaller than w into either A or B during the interval of stages $(w, t)$ , whence $φ_{d, t} (x) = φ_{d, w} (x) < λ_{e, t} (p)$ . □
Lemma 5.3.
Let τ be a node on the true path working for $Q_{d}$ . Then $τ \hat{} \infty$ is on the true path if and only if $Φ_{d} (A, B)$ is total.
Proof.
In the non-trivial direction, suppose that $τ \hat{} \infty \in γ_{ω}$ . Let $x < ω$ ; let $\bar{t}$ be a $τ \hat{} \infty$ -stage such that $\bar{t} > x$ . Lemma 5.2 says that only followers appointed or realised at or before stage $\bar{t}$ can ever injure a computation $Φ_{d} (A, B, x) [t]$ ; there are finitely many such followers, and by the analogue of Lemma 3.7, each follower acts finitely many times. □
Lemma 5.4.
For every $i, e < ω$ , the requirement $P_{e}^{i}$ is met.
Proof.
The argument is like that for Lemma 3.13, but simpler, as permitted followers cannot be cancelled. Let σ be the node on the true path which works for $P_{e}^{i}$ ; let $s^{}$ be a stage after which σ is never initialised.

First, suppose that some follower p for σ is permitted after stage $s^{}$ . Then the usual argument shows that $Λ_{e} (A, W_{e}, p) \neq f^{α, i} (p)$ , so the requirement is met.

Otherwise, suppose that some follower p for σ is never cancelled and never realised; then the requirement is met vacuously.

Finally, if no follower is permitted, but all followers are realised, then $Δ_{σ} (A, B) = W_{e}^{∁}$ , with a similar argument to that of Lemma 3.13. The key ingredient is the analogue of Corollary 3.9, which in our case follows from Lemma 5.3. Claim 3.13.1 is easier, since no attacks are cancelled: at every stage s we have $Δ_{σ} (A, B) [s] \subseteq W_{e, s}^{∁}$ , as otherwise, some follower is permitted. □
Lemma 5.5.
For all $d < ω$ , the requirement $Q_{d}$ is met.
Proof.
We use the same terminology. Let $s_{0} < s_{1} < \dots$ be the $τ \hat{} \infty$ -stages after the last stage at which τ is initialised, where $τ \in γ_{ω}$ works for $Q_{d}$ . Fix some $x < ω$ . Let $j^{}$ be the least such that $x < s_{j^{} - 1}$ . To track changes in $f_{j} (x) = Φ_{d} (A, B, x) [s_{j}]$ , we define:
$a (x)$ be the collection of followers p for nodes $σ ≽ τ \hat{} \infty$ working for $P_{e}^{i}$ , which have been realised prior to stage $s_{j^{}}$ ;

$b (x)$ be the collection of followers q for nodes $ρ ≽ τ \hat{} \infty$ working for $R_{c}$ , which were appointed prior to stage $s_{j^{}}$ .

Lemma 5.2, together with initialisations at $τ \hat{} \infty$ -stages, shows that for all $j ⩾ j^{}$ , if $Φ_{d} (A, B, x) [s_{j}] \neq Φ_{d} (A, B, x) [s_{j + 1}]$ , then action is taken during stage $s_{j}$ for some follower in either $a (x)$ or $b (x)$ . Each follower in $b (x)$ acts at most once; between any two actions for some $p \in a (x)$ , the associated ordinal $o^{α, i} (p)$ drops. Hence again, for $p \in a (x)$ we let $T (p)$ be the collection of stages t at which either p is first realised, or $λ_{e, t} (p)$ is enumerated into $A_{t + 1}$ ; and for $j ⩾ j^{}$ we let $t_{j} (p) = max T (p) \cap s_{j}$ . We then let $\begin{matrix} δ_{j} (p) = o_{t_{j} (p)}^{i} (p), \end{matrix}$ where p is a follower for a node that works for $P_{e}^{i}$ ; note that $δ_{j} (p) < α$ as p is realised at or after stage $t_{j} (p)$ . Finally we let $\begin{matrix} o_{j} (x) = ⨁_{p \in a (x)} δ_{j} (p) + | {q \in b (x) : q \notin B_{s_{j}}} | . \end{matrix}$ If p acts at stage $s_{j}$ , then $δ_{j + 1} (p) < δ_{j} (p)$ ; if some follower in $b (x)$ acts at stage s, then the second summand shrinks. □

5.2. A maximal ideal

In this subsection we prove Theorem 1.8: for every α there is some totally α-c.a. which is bounded by no maximal totally α-c.a. degree. Paradoxically, the proof is yet another elaboration on the construction of a maximal degree. We expand the construction of the previous subsection to construct a “maximal (proper) ideal”:

Theorem 5.6.
Let $α ⩽ ϵ_{0}$ be a power of ω. There are totally α-c.a. degrees $d_{0} < d_{1} < d_{2} < \dots$ such that every totally α-c.a. degree above $d_{0}$ lies below $d_{n}$ for some n.

To prove the theorem, we enumerate sets A and $B_{0}, B_{1}, B_{2}, \dots$ with the intention of letting $d_{n} = A \oplus B_{0} \oplus B_{1} \oplus \dots \oplus B_{n - 1}$ .
5.2.1. Requirements

Let ${⟨ Φ_{d} ⟩}_{d < ω}$ be an enumeration of all Turing functionals. To make each $d_{n}$ totally α-c.a., we need to meet, $\begin{matrix} for all d, n < ω, Q_{d}^{n} : If Φ_{d} (A, B_{0}, \dots, B_{n - 1}) is total, then it is α -c.a. \end{matrix}$

For the maximality property, for each e, we enumerate a Turing functional $Λ_{e}$ and meet the following set of requirements: $\begin{array}{l} for all e, i < ω, P_{e}^{i} : If ⟨ f_{s}^{α, i}, o_{s}^{α, i} ⟩ is eventually α -computable, then Λ_{e} (A, W_{e}) \neq f^{α, i}, or \\ W_{e} ⩽_{T} A \oplus B_{0} \oplus \dots \oplus B_{n - 1} for some n . \end{array}$

And the Friedberg–Muchnik requirements: $\begin{matrix} for all n, c < ω, R_{d}^{n} : Ψ_{c} (A, B_{0}, \dots, B_{n - 1}) \neq B_{n} . \end{matrix}$ Again $⟨ Ψ_{e} ⟩$ is an effective list of all Turing functionals.

5.2.2. Discussion

The construction is a very mild modification of the previous construction. The entire thing proceeds rather pleasantly, and without complication. We just need to explain where n comes from, to meet requirement $P_{e}^{i}$ : if σ on the true path works for $P_{e}^{i}$ , then there are only finitely many nodes $τ \in {prec}_{\infty} (σ)$ , and each such τ works for a requirement that mentions only finitely many $B_{n}$ ’s; we take all these which are mentioned. Other than that, the construction is identical to the previous one, so we omit the details.

6. Uniformly totally α-c.a. degrees

One of the ideas in [5] was to further refine the totally $ω^{α}$ -c.a. hierarchy by exploring an analogue of the fact that array computability was a uniform version of being totally ω-c.a. This generalization was done as follows.

Let $α ⩽ ϵ_{0}$ . We call $h : ω \to α$ an α-order function if h is nondecreasing, computable, and its range is unbounded in α. Again, for computability, we take any canonical computable copy of α. An h-computable approximation is an α-computable approximation $⟨ f_{s}, o_{s} ⟩$ such that for all x, $o_{0} (x) < h (x)$ . Just like for α-computable approximations, we can produce an effective list $⟨ f_{s}^{h, i}, o_{s}^{h, i} ⟩$ of tidy $(h + 1)$ -computable approximations whose limits $f^{h, i}$ consists of all h-c.a. functions. Of course every α-c.a. function is h-c.a. for some α-order function h, but when uniform bounds are required for all functions in a degree, we get a stronger notion. And just like the ω-case, the bound does not matter:

Proposition 6.1 ([5]).

The following are equivalent for a c.e. degree d :

For some α-order function h, all functions $f \in d$ are h-c.a.

For every α-order function h, all functions $f \in d$ are h-c.a.

A degree d satisfying these conditions is called uniformly totally α-c.a. A c.e. degree is uniformly totally ω-c.a. if and only if it is array computable. These new levels refine the hierarchy of totally α-c.a. degrees:

Proposition 6.2 ([5]).

Let $α ⩽ ϵ_{0}$ be a power of ω.

For every $β < α$ , every totally β-c.a. degree is uniformly totally α-c.a;

There is a degree which is uniformly totally α-c.a. and not totally β-c.a. for any $β < α$ ;

There is a degree which is totally α-c.a. but not uniformly so.

And again for ordinals which are not powers of ω, we get nothing new: if α is a power of ω and $γ \in (α, α \cdot ω)$ , then total uniform γ-c.a.-ness coincides with total γ-c.a.-ness coincides with total α-c.a.-ness.

The last theorem in this paper examines the cone below a c.e. degree which is not totally α-c.a.

Theorem 6.3.
Let $α ⩽ ϵ_{0}$ be a power of ω. Every degree which is not totally α-c.a. bounds a degree which is totally α-c.a. but not uniformly so.

This implies Theorem 1.2: indeed, even the refined hierarchy does not collapse at any level in any lower cone.

To prove the theorem, recall that a modulus function g has a “self-modulating” computable approximation $⟨ g_{s} ⟩$ :
for all n and s, $g_{s} (n) ⩽ s$ ;

if $g_{s} (n) \neq g_{s - 1} (n)$ then $g_{s} (n) = s$ , indeed $g_{s} (m) = s$ for all $m ⩾ n$ .
So $g_{s - 1} ⩽ g_{s}$ (pointwise), and if $g_{s} (n) \neq g_{s - 1} (n)$ then $g_{s} (m) \neq g_{s - 1} (m)$ for all $m ⩾ n$ . Such a function clearly has a c.e. degree, and every c.e. degree contains such a function. Indeed, given a c.e. degree d which is not totally α-c.a. we can find a modulus function $g \in d$ which is not α-c.a. Fixing this g, we will give a self-modulating computable approximation $⟨ f_{s} ⟩$ of a modulus function f such that $f ⩽_{T} g$ , and ${deg}_{T} (f)$ is as required.
6.1. Requirements

Let ${⟨ Φ_{d} ⟩}_{d < ω}$ be an enumeration of all functionals. To ensure that ${deg}_{T} (f)$ is totally α-c.a., we must meet the set of requirements given by: $\begin{matrix} for all d < ω, Q_{d} : If Φ_{d} (f) is total, then it is α -c.a. \end{matrix}$

To ensure that ${deg}_{T} (f)$ is not uniformly totally α-c.a., we fix an α-order function h and arrange that f itself is not h-c.a. We need to meet the requirements, $\begin{matrix} for all i < ω, P^{i} : f \neq f^{h, i}, \end{matrix}$ where $⟨ f^{h, i} ⟩$ is a list of h-c.a. functions equipped with tidy $(h + 1)$ -c.a. approximations as described above.

6.2. Discussion

We apply the technique of non-total α-c.a. permitting to the construction from [5] that separates between totally α-c.a. and uniformly totally α-c.a. degrees.

To meet $P^{i}$ , we would like to choose a follower p and change $f (p)$ each time we see that $f_{s} (p) = f_{s}^{h, i} (p)$ . This action will be taken at most $h (p) + 1$ many “times”. Any change in f necessitates a change in g below a previously specified location. Permission will not always be given, so a node σ working for $P_{i}$ will appoint several followers, and we will argue that eventually it will receive permission; if not, then it appoints infinitely many followers and we use that to build an α-computable approximation for g.

Nodes τ working for $Q_{d}$ can observe all ordinals of all followers appoints prior to the first stage at which a $Φ_{d} (f)$ -computation is certified. Since all approximations are “total”, we do not have to wait for realisations and lift the use: all ordinals supplied to τ are below α, as they are bounded by h.

When we change $f (p)$ for some follower p for a node σ, we need to cancel all larger followers for σ. The reason is that this change may have injured a computation $Φ_{d} (f, x) [s]$ that was not protected from p, but protected from $p^{'}$ ; when the computation comes back, its use will be bigger than $p^{'}$ .

This has implications to the nature of the reduction of f to g. Originally we would like the use of this reduction to be the identity: say that p is permitted at a stage s if $g_{s} ↾ p \neq g_{s + 1} ↾ p$ . The idea is that if p will not receive enough permissions, then we can bound the “number” of changes to $g ↾ p$ . But when $p^{'}$ is cancelled, in order for this process to give an approximation for all of g, in the future, we need to allow g changes below $p^{'}$ to permit changes in $f (p)$ . Hence the use of the reduction on p has risen beyond $p^{'}$ ; the reduction is therefore a Turing reduction, and we will need to argue that the uses do stabilise.

6.3. Strategy tree

A node τ working for $Q_{d}$ has two outcomes, $\infty < f$ ; a node σ working for $P^{i}$ has a unique outcome.

To define the reduction of f to g we will define moveable markers $ζ_{s} (n)$ . A change in g below $ζ_{s} (n)$ allows us to change $f (n)$ , and to redefine the marker $ζ_{s} (n)$ . We start with $ζ_{0} (n) = n$ for all n.

6.4. Construction

Let s be a stage. Let σ be a node which works for requirement $P^{i}$ . A follower p for σ is permitted at stage s if $g_{s} ↾ ζ_{s} (p) \neq g_{s + 1} ↾ ζ_{s} (p)$ . The follower requires attention if $f_{s} (p) = f_{s}^{h, i} (p)$ . If some node σ has a follower which requires attention and is permitted at this stage, then we choose the strongest such σ, and the smallest such p for this σ, and define $f_{s + 1} (m) = s + 1$ for all $m ⩾ p$ (and $f_{s + 1} ↾ p = f_{s} ↾ p$ ). We redefine $ζ_{s + 1} (m) = max {s + 1, m}$ for all $m ⩾ p$ , and $ζ_{s + 1} (m) = ζ_{s} (m)$ for all $m < p$ . We cancel all followers $p^{'} > p$ for σ, and initialise all nodes weaker than σ. We then end the stage.

Suppose that the stage did not end. We let $f_{s + 1} = f_{s}$ and $ζ_{s + 1} = ζ_{s}$ . We then define the path $γ_{s}$ of nodes accessible at stage s. The instructions for a node τ working for $Q_{d}$ are as in the previous section; choose the outcome ∞ if $dom Φ_{d} (f) [s]$ is greater than the previous $τ \hat{} \infty$ -stage; otherwise choose $f$ .

Suppose that a node σ working for requirement $P^{i}$ is accessible at stage s. If for some follower p for σ we have $f_{s} (p) \neq f_{s}^{h, i} (p)$ then we let σ’s child be next accessible. Otherwise (this includes the case that σ has no followers) we appoint a new, large follower p for σ, end the stage, and initialise all nodes weaker than σ.

6.5. Verification

Lemma 6.4.

The sequence $⟨ f_{s} ⟩$ converges to a limit f, which is computable from g.

Proof.

For every p we show that there are finitely many stages s at which $f_{s} (p) \neq f_{s + 1} (p)$ but $f_{s} ↾ p = f_{s + 1} ↾ p$ . Fix p. If there is such a stage, then p is a follower for some node σ working for a requirement $P^{i}$ . The usual argument shows that σ will act for p only finitely often: if it acts for p at stages $\bar{s} < s$ then as $f_{\bar{s}} (p) = f_{\bar{s}}^{h, i} (p)$ and $f_{s} (p) = f_{s}^{h, i} (p)$ and $f_{s} (p) ⩾ f_{\bar{s} + 1} (p) = s + 1 > f_{s} (p)$ implies that $o_{\bar{s}}^{h, i} (p) > o_{s}^{h, i} (p)$ .

The fact that $⟨ f_{s} ⟩$ stabilises implies that the sequence of use functions $⟨ ζ_{s} ⟩$ reaches a limit as well. The permitting instructions imply that if $g_{s} ↾ ζ_{s} (m) = g ↾ ζ_{s} (m)$ then $f_{s} ↾ m = f ↾ m$ , whence $f ⩽_{T} g$ . □

Meeting the requirement $Q_{d}$ is done in the usual way, using the following:

Lemma 6.5.

Let $τ \in γ_{ω}$ be a node working for $Q_{d}$ ; let $\bar{t} < t$ be $τ \hat{} \infty$ -stages, let $σ ≽ τ \hat{} \infty$ be a node working for $P^{i}$ , and let p be a follower for σ at stage t which is appointed after stage $\bar{t}$ . Then for all $x < \bar{t}$ , $Φ_{d} (f, x) ↓ [t]$ and $p > φ_{d, t} (x)$ .

Proof.

Similar to the previous section, except that we have to deal with more than one follower for each node. Let $u = φ_{d, r} (x)$ , where $r > \bar{t}$ is the stage at which p was appointed; so $p > u$ . Let $s \in (r, t)$ be a stage at which $f_{s} ↾ u \neq f_{s + 1} ↾ u$ ; suppose that this is done on behalf of a follower $\bar{p}$ for a node $\bar{σ}$ . If σ is stronger than $\bar{σ}$ then the latter is initialised at stage r, whence $\bar{p} > r > u$ . If $\bar{σ}$ is stronger than σ then σ is initialised at stage s, and p cancelled. If $\bar{σ} = σ$ then $\bar{p} < u < p$ , whence p would be cancelled at stage s. □

The familiar process now gives an α-computable approximation to $Φ_{d} (f)$ in case it is total and a node $τ \in γ_{ω}$ works for $Q_{d}$ . We omit the details. The proof of the theorem will be complete once we show:

Lemma 6.6.

Let $σ \in γ_{ω}$ work for requirement $P^{i}$ . Then σ ends the stage only finitely many times, and the requirement is met.

Proof.

We claim that there is a follower p for σ which is never cancelled and such that $f (p) \neq f^{h, i} (p)$ . If this is so, then the requirement is certainly met, and once both $f_{s} (p) = f (p)$ and $f_{s}^{h, i} (p) = f^{h, i} (p)$ permanently, no further followers will be appointed by σ, and eventually σ will cease all action.

Suppose then that for every follower p for σ, either p is eventually cancelled, or $f (p) = f^{h, i} (p)$ . Since σ is accessible infinitely often, by considering “non-deficiency followers” (the smallest follower for σ ever to receive attention after a given stage) we see that there are infinitely many followers for σ that are never cancelled.

Fix $k < ω$ . Let $s^{*} (k)$ be the least stage s after which σ is never initialised, and at which there is a follower $p > k$ for σ. We let $p^{*} (k)$ be this follower. For all $s ⩾ s^{*} (k)$ we let $P_{s} (k)$ be the set of followers $p ⩽ p^{*} (k)$ for σ at stage s. Observe that if $\bar{s} < s$ then $P_{\bar{s}} (k) \supseteq P_{s} (k)$ . Some followers in $P_{\bar{s}} (k)$ may get cancelled, but new followers are chosen large. On the other hand, $P_{s} (k)$ is nonempty for all $s ⩾ s^{*} (k)$ ; $min P_{s} (k)$ is the first follower appointed for σ since the last stage it was initialised. For each $s ⩾ k$ we let $p_{s} (k) = max P_{s} (k)$ .

We let $s_{0} (k) < s_{1} (k) < s_{2} (k) < \dots$ be an enumeration of the stages $s ⩾ s^{*} (k)$ at which $f_{s} (p_{s} (k)) = f_{s}^{h, i} (p_{s} (k))$ . By assumption, there are infinitely many such stages (note that $⟨ p_{s} (k) ⟩$ stabilises). For $j ⩾ 0$ we let $\begin{matrix} {\hat{g}}_{j} (k) = g_{s_{j} (k)} (k) \end{matrix}$ and $\begin{matrix} o_{j} (k) = ⨁_{p \in P_{s_{j} (k)} (k)} o_{s_{j} (k)}^{h, i} (p) + | P_{s_{j} (k)} | . \end{matrix}$

Certainly ${lim}_{j} {\hat{g}}_{j} (k) = g (k)$ . Note that $o_{j} (k) < α$ . Since $P_{s} (k)$ is decreasing in s, we see that for all $j ⩾ 0$ , $o_{j} (k) ⩾ o_{j + 1} (k)$ . Claim 6.6.1.

For all $s ⩾ s^{*} (k)$ , $ζ_{s} (p_{s} (k)) > k$ .

Proof.

By induction on s. At stage $s^{*}$ we have $ζ_{s} (p_{s^{*}} (k)) ⩾ p_{s^{*}} (k) > k$ . Since $ζ_{s} (p) ⩽ ζ_{s + 1} (p)$ , we are done if $p_{s} (k) = p_{s + 1} (k)$ . Otherwise, at stage s we act for $p = p_{s + 1} (k)$ and redefine $ζ_{s + 1} (p) = s + 1 > k$ . □

Now suppose that ${\hat{g}}_{j} (k) \neq {\hat{g}}_{j + 1} (k)$ . We need to show that $o_{j} (k) > o_{j + 1} (k)$ . For brevity let $\bar{s} = s_{j} (k)$ and $s = s_{j + 1} (k)$ . If $P_{\bar{s}} (k) \neq P_{s} (k)$ then $| P_{\bar{s}} (k) | > | P_{s} (k) |$ and we are done. Otherwise, let $p = p_{\bar{s}} (k) = p_{s} (k)$ . We show that $o_{\bar{s}}^{h, i} (p) > o_{s}^{h, i} (p)$ .

This is clear if $f_{\bar{s}}^{h, i} (p) \neq f_{s}^{h, i} (p)$ . Suppose that $f_{\bar{s}}^{h, i} (p) = f_{s}^{h, i} (p)$ . Since $f_{\bar{s}} (p) = f_{\bar{s}}^{h, i} (p)$ and $f_{s} (p) = f_{s}^{h, i} (p)$ we see that $f_{\bar{s}} (p) = f_{s} (p)$ . This implies that for all $r \in [\bar{s}, s)$ , $f_{r} (p) = f_{r + 1} (p)$ . On the other hand there is some stage $r \in [\bar{s}, s)$ such that $g_{r} (k) \neq g_{r + 1} (k)$ . By Claim 6.6.1, $ζ_{r} (p) > k$ . Since p is not cancelled at stage r, and we do not redefine $f_{r + 1} (p) = r + 1 > f_{r} (p)$ , it must be that $f_{r} (p) \neq f_{r}^{h, i} (p)$ . Hence $f_{r}^{h, i} (p) \neq f_{s}^{h, i} (p)$ , so $o_{\bar{s}}^{h, i} (p) > o_{r}^{h, i} (p) > o_{s}^{h, i} (p)$ as required.

Overall, we see that $⟨ {\hat{g}}_{j}, o_{j} ⟩$ is an α-computable approximation for g, which we assumed does not exist. □

Footnotes

Acknowledgements

This work is supported by Marsden Grants to Downey and to Greenberg, and a Rutherford Discovery Fellowship to Greenberg. The results are from Arthur’s MSc Thesis [].

References

Arthur, Maximality in the α-c.a. degrees, MSc Thesis, Victoria University of Wellington, 2016.

Cholak,

Downey and

Walk, Maximal contiguous degrees, J. Symbolic Logic 67(1) (2002), 409–437. doi:10.2178/jsl/1190150052.

Downey and

Greenberg, A hierarchy of computably enumerable degrees, Bull. Symb. Log. 24(1) (2018), 53–89. doi:10.1017/bsl.2017.41.

Downey,

Greenberg and

Weber, Totally ω-computably enumerable degrees and bounding critical triples, J. Math. Log. 7(2) (2007), 145–171. doi:10.1142/S0219061307000640.

R.G.

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, Vol. 206, Princeton University Press, 2020.

R.G.

Downey,

C.G.

JockuschJr. and

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

R.L.

Epstein,

Haas and

R.L.

Kramer, Hierarchies of sets and degrees below 0^′, in: Logic Year 1979–80 (Proc. Seminars and Conf. Math. Logic, Univ. Connecticut, Storrs, Conn., 1979/80), Lecture Notes in Math., Vol. 859, Springer, Berlin, 1981, pp. 32–48. doi:10.1007/BFb0090937.

Y.L.

Ershov, A certain hierarchy of sets. I, Algebra i Logika 7(1) (1968), 47–74.

Y.L.

Ershov, A certain hierarchy of sets. II, Algebra i Logika 7(4) (1968), 15–47.

10.

Y.L.

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

11.

Ishmukhametov, Weak recursive degrees and a problem of spector, in: Recursion Theory and Complexity,

Arslanov and

Lempp, eds, Vol. 2, de Gruyter, Berlin, 1999, pp. 81–87.

12.

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

13.

Schaeffer, Dynamic notions of genericity and array noncomputability, Annals of Pure and Applied Logic 95(1–3) (1998), 37–69. doi:10.1016/S0168-0072(98)00014-1.

14.

V.L.

Selivanov, Fine hierarchies of arithmetic sets, and definable index sets, Trudy Inst. Mat. (Novosibirsk) 12(Mat. Logika i Algoritm. Probl.) (1989), 165–185, 190.

15.

J.R.

Shoenfield, On degrees of unsolvability, Ann. of Math. (2) 69 (1959), 644–653. doi:10.2307/1970028.

Maximality and collapse in the hierarchy of α -c.a. degrees

Abstract

Keywords

1. Introduction

1.1. Background: Array computable, and totally ω-c.a. degrees

1.2. Totally α-c.a. degrees

1.3. Hierarchy collapse

Theorem 1.1 ([5]).

Theorem 1.6 ([5]).

Proposition 1.10 ([5]).

2. Non-collapsing in upper cones

1 Note that we could have added A as an oracle to Λ. However, we will see that this is not useful.

2.4. Construction

2.5. Verification

3. Existence of maximal degrees in upper cones

3.2. Discussion

3.3. Strategy tree

3.4. Construction

3.5. Verification

Theorem 4.1. Let β ⩽ ϵ 0 be a power of ω. Every c.e. superlow degree is bounded by a (c.e.) maximal β-c.a. degree (and hence by a properly β-c.a. degree). Let A be a superlow c.e. set. We enumerate a set D such that deg T ( A ⊕ D ) is maximal β-c.a. 4.1. Requirements

4.2. Discussion

4.3. Strategy tree

4.4. Construction

4.5. Verification

5.1. A maximal interval

5.1.2. Discussion

5.1.3. Strategy tree

5.1.4. Construction

5.1.5. Verification

5.2.2. Discussion

6. Uniformly totally α-c.a. degrees

Proposition 6.1 ([5]).

Proposition 6.2 ([5]).

6.2. Discussion

6.3. Strategy tree

6.4. Construction

6.5. Verification

Footnotes

Acknowledgements

References

¹
Note that we could have added A as an oracle to Λ. However, we will see that this is not useful.

Theorem 4.1.
Let $β ⩽ ϵ_{0}$ be a power of ω. Every c.e. superlow degree is bounded by a (c.e.) maximal β-c.a. degree (and hence by a properly β-c.a. degree).

Let A be a superlow c.e. set. We enumerate a set D such that ${deg}_{T} (A \oplus D)$ is maximal β-c.a.
4.1. Requirements