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

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

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

Definition 4.1.

A set A is eventually uniformly wtt -array computable (e.u.wtt-a.c. for short) if there exist computable functions g , k : ω 2 → { 0 , 1 } and a computable order h : ω → ω such that, for all e, x, (6) A † ( x ) = lim s → ∞ g ( x , s ) , (7) k ( x , s ) ⩽ k ( x , s + 1 ) , (8) k ( x , s ) = 1 ⇒ | { t ⩾ s : g ( x , t + 1 ) ≠ g ( x , t ) } | ⩽ h ( x ) , (9) ∀ e ( Φ ˆ e A total ⇒ ∀ ∞ x ∃ s ( k ( ⟨ e , x ⟩ , s ) = 1 ) ) . For functions g, k and h as above, we say that A is eventually uniformly wtt -array computable via g, k and h, and we let EUwttAC denote the class of all c.e. e.u.wtt-a.c. sets.

Now the main result is as follows.

Theorem 4.2 (Characterization Theorem).

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

A is eventually uniformly wtt -array computable.

Theorem 4.3.

Let A be c.e. and eventually uniformly wtt -array computable. Then A is ibT-reducible to some maximal set.

Theorem 4.4.

Let A and D be c.e. sets such that A ⩽ wtt D and D is dense simple. Then A is eventually uniformly wtt -array computable.

In the remainder of this section we prove these two theorems.

Proof of Theorem 4.3.

Let { A s } s ∈ ω be a computable enumeration of A and fix computable functions g ˆ , k ˆ and h ˆ which witness that A is e.u.wtt-a.c. according to Definition 4.1. We construct a c.e. set M in stages s, where M s denotes the finite set of numbers which are enumerated into M by stage s, such that M is maximal and A ⩽ ibT M . Clearly, any such M witnesses that Theorem 4.3 holds.

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

In order to make M maximal, it suffices to ensure that the complement of M is infinite, (10) | M ‾ | = ω , and that M meets the requirements (11) R e : M ‾ ⊆ ∗ W e or M ‾ ⊆ ∗ W e ‾ . for e ∈ ω .

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

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

In order to approximate the true path, for any node α and any stage s, we let V α , s = M s ‾ ↾ s ∩ { y : σ ( | α | , y , s ) = α } = M s ‾ ↾ s ∩ { y : ∀ e < | α | ( y ∈ W e , s ⇔ α ( e ) = 0 ) } and V α = M ‾ ∩ { y : σ ( | α | , y ) = α } = M ‾ ∩ { y : ∀ e < | α | ( y ∈ W e ⇔ α ( e ) = 0 ) } , and we use the following length of agreement function (12) l ( α , s ) = | V α , s | . Based on l ( α , s ) , we define the set of α-stages by induction on | α | as follows. Every stage is a λ-stage. An α-stage s is called α-expansionary if s = 0 or l ( α 0 , s ) > l ( α 0 , t ) holds for all α-stages t < s . Then a stage s is an α 0 -stage if it is α-expansionary and an α 1 -stage if it is an α-stage but not α-expansionary. At stage s, the current approximation δ s of the true path is the unique node α of length s such that s is an α-stage, and we say that α is accessible at stage s + 1 if α is an initial segment of δ s , i.e., α ⊑ δ s . Then the true path TP through T is defined by TP = lim inf s → ∞ δ s , i.e., TP ↾ n is the leftmost node of length n which is accessible infinitely often (for every n).

Next we explore under which assumptions on M the true path TP actually has the desired properties, i.e., satisfies that, for any n, TP ↾ n is the leftmost node α of length n such that V α is infinite. We start with some observations. Note that (13) V α 0 , s = V α , s ∩ W | α | , s and V α 1 , s = V α , s ∩ W | α | , s ‾ . So V α , s is the disjoint union of V α 0 , s and V α 1 , s , (14) V α , s = V α 0 , s ∪ ˙ V α 1 , s , and (15) l ( α , s ) = l ( α 0 , s ) + l ( α 1 , s ) . Note that the analog of (14) holds for V α , too, and that the equation can be extended to (16) V α , s = ⋃ ˙ | β | = n V α β , s and V α = ⋃ ˙ | β | = n V α β for any n ⩾ 0 . Next note that, for any node α, { V α , s } s ∈ ω is a computable approximation of V α , i.e., for any number y, (17) V α ( y ) = lim s → ∞ V α , s ( y ) . Moreover, a number y ∈ V α , s is in V α unless y is enumerated into M after stage s or the | α | -state of y decreases after stage s. So, if we let V ˆ α = ⋃ { α ′ : | α ′ | = | α | & α ′ ⩽ L α } V α ′ , then (18) V ˆ α = M ‾ ∩ ( ⋃ s ∈ ω ⋃ { α ′ : | α ′ | = | α | & α ′ ⩽ L α } V α ′ , s ) . In fact, if we say that α ′ is stronger than α ( α ′ ≺ α ) if α ′ < L α or α ⊏ α ′ (i.e., viewed as a state, either α ′ is less than α or α ′ contains more information than α) then, by the definition of V ˆ α and (16), V ˆ α ′ ⊆ V ˆ α for any α ′ which is stronger than α whence (19) V ˆ α = ⋃ { α ′ : α ′ ⪯ α } V α ′ = M ‾ ∩ ( ⋃ s ∈ ω ⋃ { α ′ : α ′ ⪯ α } V α ′ , s ) .

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

Assume ( 10 ). For any node α ⊏ TP , the set S α of the α-stages is infinite and (20) lim s → ∞ , s ∈ S α l ( α , s ) = ω . Moreover, if α ′ is to the left of TP then S α ′ and V ˆ α ′ are finite.

Proof.

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

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

Claim 2 (Maximal Set Lemma).

Assume that M is c.e. and coinfinite. If, for any α ⊏ TP , M ‾ ⊆ ∗ V ˆ α then M is maximal.

Proof.

Since V ˆ α is the finite union of V α and the sets V α ′ such that α ′ < L α and | α ′ | = | α | , it follows by the second part of the Infinity Lemma that M ‾ ⊆ ∗ V α for all α ⊏ TP . So, for any n ⩾ 0 , almost all numbers in M ‾ have ( n + 1 ) -state TP ↾ n + 1 . As pointed out before, this implies that all requirements R n are met. Since, by assumption, M is c.e. and coinfinite this implies that M is maximal. □

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

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

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

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

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

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

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

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

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

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

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

Now, using the notation introduced above, the steps of stage s + 1 are as follows.

Step 1 (Defining the blocks B n α ). A B n α -node β requires attention at stage s + 1 if one of the following holds.

B n α [ s ] ↑

β ⊏ δ s or δ s < L β and | β | < s .

Neither β nor any equivalent node β ′ such that β ′ < L β is eligible at stage s.

For any node β ′ such that β ′ ⊏ β , the block associated with β ′ is defined at stage s.

For any node β ′ such that β < L β ′ , | β ′ | = | β | and β ′ is not equivalent to β, the block associated with β ′ is defined at stage s.

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

r ( β , s ) < min B ,

B ⊆ ⋃ { α ′ : | α ′ | = | α | and α ′ ⩽ L α } V α ′ , s ,

The block B has cardinality | B | = F ( β , s ) where F ( γ , s ) is defined (by induction on γ) by F ( γ , s ) = 2 + H ( γ ) + ∑ { γ ′ : γ ′ < L γ and γ ′ is eligible at stage s } F ( γ ′ , s ) where, for a B n ′ α ′ -node γ, H ( γ ) = h ( ⟨ α ′ , n ′ ⟩ ) (and where ∑ ∅ = 0 ). (Note that, at any given stage s, there are only finitely many eligible nodes, hence F ( γ , s ) is well-defined.)

Fix β minimal such that β requires attention.

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

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

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

Step 2 (Defining the partial computable use functions ψ α ). For any α and any n such that either n = 0 or ψ α ( n − 1 ) [ s ] ↓ , ψ α ( n ) [ s ] ↑ and B n + 1 α [ s ] ↓ , let ψ α ( n ) = max B n + 1 α .

Step 3 (Defining the wtt -functionals Ψ α ). For any α and any n such that ψ α ( n ) [ s ] ↓ let (26) Ψ α A ( n ) [ s + 1 ] ↓ if Ψ α A ( n ) [ s ] ↑ and g ( ⟨ α , n ⟩ , s ) = 0 , and let (27) Ψ α A ( n ) [ s + 1 ] ↑ if Ψ α A ( n ) [ s ] ↓ , g ( ⟨ α , n ⟩ , s ) = 1 and A s + 1 ↾ ψ α ( n ) ≠ A s ↾ ψ α ( n ) . In any other case let Ψ α A ( n ) [ s + 1 ] ↓ if and only if Ψ α A ( n ) [ s ] ↓ .

Step 4 (Freezing blocks). A block B n α is freezable at stage s + 1 if the following hold.

⟨ | α | , n ⟩ < s .

B n α is not frozen at stage s.

For any x covered by B n α there is a block B n x α x such that α x ≺ α , B n x α x is admissible at stage s, and B n x α x covers x.

If there is a freezable block then choose q = ⟨ m , n ⟩ minimal such that there is a freezable block B n α with | α | = m and fix the rightmost α such that | α | = m and B n α is freezable. Declare that B n α becomes frozen at stage s + 1 .

Step 5 (Enumerating M). A number y ∉ M s is enumerated into M at stage s + 1 if (at least) one of the following hold.

(Freezing) There is a block B n α which becomes frozen in Step 4 of stage s + 1 and y is in the core B ˆ n α [ s + 1 ] of B n α at stage s + 1 .

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

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

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

We first summarize the properties of the blocks we will need. Claim 3.

The definition of the blocks satisfies the following conditions.

If B n α becomes defined at stage s + 1 (i.e., B n α [ s + 1 ] ↓ and B n α [ s ] ↑ ) then B n α ∩ M s = ∅ .

If B n α is defined then B n α ∩ M ‾ ⊆ ⋃ { α ′ : | α ′ | = | α | and α ′ ⩽ L α } V α ′ .

If B n α is defined then ⟨ | α | , n ⟩ ⩽ min B n α .

If B n + 1 α is defined then B n α is defined and max B n α < min B n + 1 α .

If B n α is defined then, for the core B ˆ n α = B n α ∖ ⋃ { ( α ′ , n ′ ) : α ′ ≺ α , n ′ ⩾ 0 and B n ′ α ′ ↓ } B n ′ α ′ of B n α , | B ˆ n α | > h ( ⟨ α , n ⟩ ) + 1 .

If B n α is defined and α ≺ α ′ and | α ′ | ⩽ | α | then B n α ′ is defined, too.

Assume that M ‾ is infinite. Then, for any α on or to the right of the true path, the blocks B n α are defined for all n.

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

Proof.

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

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

(B₀). This is immediate by clause (ii) in the definition of suitability since, for any node α and any stage s, V α , s ⊆ M s ‾ .

(B₁). This is immediate by clause (ii) in the definition of suitability since, for any node α and any stage s, M ‾ ∩ ⋃ { α ′ : | α ′ | = | α | and α ′ ⩽ L α } V α ′ , s ⊆ ⋃ { α ′ : | α ′ | = | α | and α ′ ⩽ L α } V α ′ .

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

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

(B₄). Assume that B n α is defined. Fix the node β and the stage s + 1 such that B n α has priority β and B n α becomes defined by activity of β at stage s + 1 . Then, given any state α ′ and any number n ′ such that (30) α ′ ≺ α , B n ′ α ′ is defined and B n ′ α ′ ∩ B n α ≠ ∅ , it suffices to show that, for the priority β ′ of B n ′ α ′ , (31) β ′ < L β , (32) β ′ is eligible at stage s , and (33) | B n ′ α ′ | = F ( β ′ , s ) hold. Namely, since different blocks have different priorities, it follows that | B ˆ n α | = | B n α ∖ ⋃ { ( α ′ , n ′ ) : α ′ ≺ α , n ′ ⩾ 0 and B n ′ α ′ ↓ } B n ′ α ′ | ⩾ | B n α | − ∑ { ( α ′ , n ′ ) : α ′ ≺ α , n ′ ⩾ 0 , B n ′ α ′ ↓ and B n ′ α ′ ∩ B n α ≠ ∅ } | B n ′ α ′ | ⩾ F ( β , s ) − ∑ { β ′ : β ′ < L β and β ′ is eligible at stage s } F ( β ′ , s ) ( by the definition of B n α and by (30) implying (31)–(33) ) ⩾ H ( β ) + 2 ( by the definition of F ( β , s ) ) = h ( ⟨ α , n ⟩ ) + 2 ( by the definition of H ( β ) ) So, assuming that (30) implies (31)–(33), (B₄) holds.

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

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

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

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

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

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

We claim that there is a stage s ∗ such that no node β ′ with β ′ < β which is not equivalent to β requires attention after stage s ∗ . This is shown as follows. Note that any node β ′ with β ′ < β which is not equivalent to β is element of one of the following sets. N 0 = { β ′ : | β ′ | ⩽ | β | & β ′ < L TP ↾ | β ′ | } N 1 = { β ′ : | β ′ | < | β | & TP ↾ | β ′ | ⩽ L β ′ } N 2 = { β ′ : | β ′ | = | β | & TP ↾ | β | ⩽ L β ′ < L β β ′ is not a B n α -node } N 3 = { β ′ : | β | < | β ′ | & β ′ < L β } So it suffices to show that for i ⩽ 4 there is a stage s i such that no node in N i requires attention after stage s i .

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

i = 1 . Note that by the minimality of q, any node β ′ ∈ N 1 is associated with a block which eventually becomes defined. Since N 1 is finite, this gives the existence of the desired stage s 1 .

i = 2 . Note that, for any β ′ ∈ N 2 , β ′ < L β , | β ′ | = | β | and β ′ and β are not equivalent. Since the block B n α associated with β is never defined, it follows, by clause (v) in the definition of requiring attention via (a), that no node in N 1 will ever require attention via (a). So s 2 = 0 will do.

i = 3 . If β ′ ∈ N 3 then, for the proper initial segment β ″ = β ′ ↾ | β | of β ′ of length | β | , either β ″ ∈ N 2 or β ″ is a B n α -node. In either case the block associated with β ″ is never defined. So, by clause (iv) in the definition of requiring attention via (a), β ′ does not require attention via (a), hence does not require attention. So s 3 = 0 will do.

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

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

So in order to show that β ˆ eventually requires attention via (b), it suffices to show that there is a stage s ⩾ t ∗ such that | ⋃ { α ′ : | α ′ | = | α | and α ′ ⩽ L α } V α ′ , s | > r ( β ˆ , t ∗ ) + F ( β ˆ , t ∗ ) . But, since TP ↾ m ⩽ L α , this follows from the fact, that, by the assumption that M ‾ is infinite and by the True Path Lemma, V TP ↾ m is infinite.

This completes the proof of (B₆).

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

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

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

Next we summarize relevant properties of the use functions ψ α and the wtt -functionals Ψ α . Claim 4.

The partial functions ψ α , α ∈ { 0 , 1 } ∗ , are uniformly computable. Moreover, for any α, the domain of ψ α (at stage s) is an initial segment of ω, and ψ α is strictly increasing on its domain. Finally, ψ α is total if and only if the blocks B n α are defined for all n ⩾ 0 .

Proof.

Uniform computability follows by the effectivity of (part 1 of) the construction. The second part of the claim is immediate by definition and by (B₃). The third part is immediate by definition. □

Claim 5.

The functionals Ψ α are uniformly computable and, for any X, α and n such that Ψ α X ( n ) is defined, ψ α ( n ) is defined and the use of Ψ α X ( n ) is bounded by ψ α ( n ) . Moreover, for any α and n such that ψ α ( n ) is defined, Ψ α A ( n ) is defined, too.

Proof.

The proof of the first part is straightforward. For a proof of the second part, for a contradiction assume ψ α ( n ) ↓ and Ψ α A ( n ) ↓ . Since Ψ is a wtt -functional, it follows that Ψ α A ( n ) [ s ] ↑ for almost all s. Moreover, by (22), g ( ⟨ α , n ⟩ , s ) = 0 for almost all s. So there is a least stage s 0 such that ψ α ( n ) [ s 0 ] ↓ and Ψ α A ( n ) ↑ and g ( ⟨ α , n ⟩ , s ) = 0 for all stages s ⩾ s 0 . By clause (26) in the definition of Ψ, this implies Ψ α A ( n ) [ s 0 + 1 ] ↓ . Contradiction. □

Note that the first part of Claim 5 justifies that in advance we have fixed a computable function f satisfying (21). Claim 6.

Assume that ψ α is total. Then the following hold.

Ψ α A is total.

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

Proof.

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

For the remaining claims we need some more notation. Let p be the unique path through T defined in (B₇). Then, for any node α such that α ⊏ p or p < L α , all blocks B n α are defined. So, by Claims 4 and 6, ψ α and Ψ α A are total and we may fix n α such that lim s → ∞ k ( ⟨ α , n ⟩ , s ) = 1 for all n ⩾ n α . It follows that, for n ⩾ n α , the block B n α will eventually become truly realized. So, if we let x α = max B n α α , then all numbers x ⩾ x α are eventually truly α-covered. Hence, for such x we may fix n x α and s x α such that n x α is the unique n such that x becomes covered by B n α and s x α is the least stage s such that x is truly covered by B n x α α at stage s. Claim 7.

Let α ⊏ p and let x ⩾ x α . There is a node α ′ ⪯ α , a number n ⩾ 0 and a stage t such that the block B n α ′ covers x and is admissible at all stages s ⩾ t (hence is never frozen).

Proof.

Note that, by (B₂), there are only finitely many blocks which may cover x. So there is a stage t 0 such that any block which covers x and becomes frozen is frozen by stage t 0 . So it suffices to show that, for almost all stages s, there is a block B n α ′ such that α ′ ⪯ α , B n α ′ covers x and B n α ′ is admissible at stage s. This is established by proving the following two facts. (a) There is a stage s such that x is covered by a block B n α ′ where α ′ ⪯ α and B n α ′ is admissible at stage s. (b) If x is covered by a block B n α ′ which is admissible at stage s then, at any stage s ′ > s , x is covered by a block B n ′ α ″ such that α ″ ⪯ α ′ and B n ′ α ″ is admissible at stage s ′ .

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

For a proof of (b), it suffices to consider the case of s ′ = s + 1 . (Then the general case follows by induction.) So assume that B n α ′ covers x and is admissible at stage s. If B n α ′ does not become frozen at stage s + 1 then we are done. Otherwise, it follows by construction that there is a block B n ′ α ″ such that α ″ ⪯ α ′ , B n ′ α ″ covers x and B n ′ α ″ is admissible at stage s + 1 . This completes the proof of (b) and the proof of the claim. □

Claim 8.

Assume that B n α becomes defined and is never frozen. Then, for the core B ˆ n α of B n α , B ˆ n α ∩ M ‾ ≠ ∅ . Similarly, if B n α is defined but not frozen at stage s then B ˆ n α [ s + 1 ] ∩ M s ‾ ≠ ∅ .

Proof.

We prove the first part of the claim. The second part is obtained by straightforward modifications of the proof.

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

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

Since between any two stages s < s ′ for which (29) holds there must be a stage t such that g ( ⟨ α , n ⟩ , t ) = 0 and g ( ⟨ α , n ⟩ , t + 1 ) = 1 , (37) 2 · | { s ⩾ s 0 : (29) holds } | ⩽ | { s ⩾ s 0 : g ( ⟨ α , n ⟩ , s + 1 ) ≠ g ( ⟨ α , n ⟩ , s ) } | + 1 ⩽ h ( ⟨ α , n ⟩ ) + 1 where the second inequality holds by (24). Moreover, since Ψ α A ( n ) ↓ by Claim 5, any stage s at which (28) holds has to be followed by a stage t > s such that Ψ α A ( n ) [ t ] ↑ and Ψ α A ( n ) [ t + 1 ] ↓ , where t < s ′ for the least stage s ′ > s such that (28) holds (if there is such a stage s ′ ). Since, by construction, g ( ⟨ α , n ⟩ , t ) = 0 and g ( ⟨ α , n ⟩ , s ′ ) = 1 for any such stage t, it follows that | { s ⩾ s 0 : (28) holds } | ⩽ | { s ⩾ s 0 : (29) holds } | holds. So, by (37), (36) holds. □

Claim 9.

A ⩽ ibT M .

Proof.

It suffices to give an effective procedure which computes A ( x ) from M ↾ x + 1 for all sufficiently large x.

Let x ⩾ x λ and let s be the least stage such that there is a node α and a number n such that

B n α covers x at stage s,

B n α is admissible at stage s,

Ψ α A ( n ) [ s ] ↓ and g ( ⟨ α , n ⟩ , s ) = 1 , and

M ↾ x + 1 = M s ↾ x + 1 .

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

We claim that A ( x ) = A s ( x ) . For a proof, first note that B n α does not become frozen after stage s hence is admissible at all later stages. (To wit, if B n α becomes frozen at stage s ′ + 1 > s then B ˆ n α [ s ′ ] is completely enumerated into M at stage s ′ + 1 whence, by the second part of Claim 8, there is a number y ∈ B ˆ n α [ s ′ + 1 ] such that y ∈ M s ′ + 1 ∖ M s ′ . Since B ˆ n α [ s ′ + 1 ] is contained in B n α and max B n α ⩽ x it follows that y ⩽ x hence M ↾ x + 1 ≠ M s ↾ x + 1 contrary to (IV).) Now, for a contradiction, assume that A ( x ) ≠ A s ( x ) . Fix s ′ ⩾ s minimal such that a number x ′ ⩽ x is enumerated into A at stage s ′ + 1 . Then, assuming that Ψ α A ( n ) [ s ′ ] ↓ and g ( ⟨ α , n ⟩ , s ′ ) = 1 , Ψ α A ( n ) [ s ′ + 1 ] ↑ by construction. So, in any case, there is a least stage s ″ such that s ⩽ s ″ ⩽ s ′ and such that (28) or (29) holds for s ′ (in place of s). It follows, by construction and by Claim 8, that there is a number y ∈ B ˆ n α [ s ′ + 1 ] which is newly enumerated into M at stage s ′ + 1 . But, as observed before, this contradicts (IV). □

Claim 10.

M ‾ is infinite.

Proof.

By (B₂) and by Claim 7 there are infinitely many blocks which are never frozen. So the claim follows by Claim 8. □

Claim 11.

For any node α ⊏ p there are only finitely many blocks B n α ′ such that α ≺ α ′ , n ⩾ 0 and B n α ′ is never frozen.

Proof.

Fix α ⊏ p . By (B₂) it suffices to show that any block B n α ′ such that α ≺ α ′ and x α ⩽ max B n α ′ becomes frozen eventually. So fix such a block B n α ′ and, for a contradiction, assume that B n α ′ is never frozen. Note that, by α ⊏ p and α ≺ α ′ , α ′ is on p or to the right of p whence B n α ′ becomes defined, say, at stage s + 1 . By Claim 7 we may fix a stage t ⩾ s + 1 such that, for any of the finitely many numbers x covered by B n α ′ there is a block B n x α x such that α x ⪯ α (hence α x ≺ α ′ ), B n x α x covers x and B n x α x is admissible at all stages t ′ ⩾ t . So B n α ′ is freezable at all stages t ′ ⩾ t . Since there are only finitely many blocks B n ˆ α ˆ such that ⟨ | α ˆ | , n ˆ ⟩ < ⟨ | α ′ | , n ⟩ or ⟨ | α ˆ | , n ˆ ⟩ = ⟨ | α ′ | , n ⟩ and α ′ < L α ˆ , it follows that B n α ′ becomes frozen eventually. Contradiction. □

Claim 12.

The true path TP coincides with the path p.

Proof.

Claim 10 and (B₆) immediately imply that p ⩽ L TP . For a proof of the converse, i.e., TP ⩽ L p , it suffices to show that, for any given node α ′ < L TP , only finitely many α ′ -blocks become defined. Now, by Claim 10 and by the second part of the Infinity Lemma (Claim 1), there are only finitely many stages s such that δ s < L α ′ or α ′ ⊏ δ s . So only finitely many α ′ -nodes can become eligible, hence only finitely many α ′ -blocks can be defined. □

Claim 13.

For any α on TP , M ‾ ⊆ ∗ V ˆ α .

Proof.

Fix α ⊏ TP . Since (by (B₁) and (19)) M ‾ ∩ B n α ′ ⊆ V ˆ α for any block B n α ′ such α ′ ⪯ α , it suffices to show (38) M ‾ ⊆ ∗ ⋃ { ( α ′ , n ) : α ′ ⪯ α , n ⩾ 0 and B n α ′ ↓ } B n α ′ . For a proof of (38), first recall that (by Claim 12) the true path TP coincides with the path p. So, by Claim 11, we may let B be the finite union of the blocks B n α ′ such that α ≺ α ′ , n ⩾ 0 and B n α ′ is never frozen. Now, call a number y a block number if y is element of some block, and call a block number y an α ′ -number if α ′ is ≺-minimal such that y is in an α ′ -block. (Note that any number is element of at most finitely many blocks. So α ′ is well-defined.) Then it suffices to show that any number y ∈ M ‾ which is not an α ′ -number for some α ′ ⪯ α is an element of B. So fix such y. We first observe that y is a block number. Namely, since there are infinitely many blocks, it follows by (B₂) that there is a stage s such that y is less than the maximum of a block defined at stage s. So if y is not a block number then y is enumerated into M at stage s + 1 for the least such s contrary to choice of y. So we may fix α ′ and the corresponding unique n such that y is an α ′ -number and y ∈ B n α ′ . It suffices to show that B n α ′ is contained in B. For a contradiction, assume that this is not the case. Since, by the choice of y, α ⪯ α ′ , this implies that there is a stage s + 1 at which B n α ′ becomes frozen. So B ˆ n α [ s + 1 ] ⊆ M s + 1 by construction. But since y is an α ′ -number, y is in the core B ˆ n α ′ of B n α ′ . Since, obviously, B ˆ n α ′ ⊆ B ˆ n α ′ [ s + 1 ] , it follows that y ∈ M contrary to assumption.

This completes the proof of Claim 13. □

Claim 14.

M is maximal.

Proof.

By the effectivity of the construction and by Claims 10 and 13, the hypotheses of the Maximal Set Lemma (Claim 2) are satisfied. □

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

In order to complete the proof of the Characterization Theorem it remains to prove Theorem 4.4. For this sake, we use the following characterization of the dense simple sets given in Robinson [33]: a c.e. set D is dense simple if and only if D is coinfinite and, for every strong array { F n } n ∈ ω of pairwise disjoint sets, there is a number m such that (39) ∀ n ⩾ m ( | F n ∩ D ‾ | < n ) . Proof of Theorem 4.4.

Fix c.e. sets A and D such that A ⩽ wtt D and D is dense simple. It suffices to define computable functions g, h and k witnessing that A is eventually uniformly wtt -array computable.

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

Now the computable functions g , k : ω 2 → { 0 , 1 } and h : ω → ω are defined as follows. Define g by letting g ( ⟨ e , y ⟩ , s ) = 1 if Φ ˆ e , s A s ( y ) ↓ , 0 otherwise, and let h be the order defined by h ( x ) = ( x + 1 ) 2 . Finally, for the definition of k, define the auxiliary uniformly partial computable functions φ ˜ e by φ ˜ e ( y ) = lim s → ∞ φ ˜ e , s ( y ) where φ ˜ e , s ( y ) = y + max { φ ˆ e , s ( y ′ ) : y ′ ⩽ y } if ∀ y ′ ⩽ y ( φ ˆ e , s ( y ′ ) ↓ ) , ↑ otherwise . Note that φ ˜ e is defined on an initial segment of ω, φ ˜ e is strictly increasing on its domain, φ ˜ e majorizes φ ˆ e on its domain, and φ ˜ e is total if φ ˆ e is total. So, for total Φ ˆ e A , φ ˜ e is total, strictly increasing and bounds the use of Φ ˆ e A . Now, the 0-1-valued function k is defined by letting k ( ⟨ e , y ⟩ , s ) = 1 iff (41) φ ˜ e , s ( y ) ↓ & l ( s ) > φ ˜ e ( y ) & | D s ‾ ↾ γ ( φ ˜ e , s ( y ) ) | < ( ⟨ e , y ⟩ + 1 ) 2 2 .

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

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

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

So fix t as in (42). Then A t + 1 ↾ φ ˆ e ( y ) ≠ A t ↾ φ ˆ e ( y ) . Note that, by k ( x , s ) = 1 , (41) holds. So, by φ ˆ e ( y ) ⩽ φ ˜ e ( y ) (if defined), by (40) and by the first two clauses in (41), there is a number ⩽ γ ( φ ˜ e , s ( y ) ) that is enumerated into D at stage t + 1 . But, by the third clause in (41), the latter can happen for at most ( ⟨ e , y ⟩ + 1 ) 2 2 − 1 stages t ⩾ s . So (8) holds.

Finally, for a proof of (9), fix e such that Φ ˆ e A is total. Then φ ˜ e is total, computable and strictly increasing (and so is γ). So we can define a computable partition of ω into nonempty intervals { F n } n ∈ ω by letting F 0 = [ 0 , γ ( φ ˜ e ( 0 ) ) ) and F n + 1 = [ γ ( φ ˜ e ( n ) ) , γ ( φ ˜ e ( n + 1 ) ) ) . Now, since D is dense simple, it follows, by Robinson’s characterization of the dense simple sets given above, that there is a number m such that (39) holds. So there is a constant c such that | D ‾ ↾ γ ( φ ˜ e ( n ) ) | = | D ‾ ↾ 1 + max F n | = ∑ n ′ ⩽ n | D ‾ ∩ F n ′ | ⩽ ( ∑ n ′ ⩽ n n ′ ) + c = n ( n + 1 ) 2 + c for all n ⩾ 0 . Since, by y ⩽ ⟨ e , y ⟩ , y ( y + 1 ) · 2 − 1 + c < ( ⟨ e , y ⟩ + 1 ) 2 · 2 − 1 for all sufficiently large y, it follows that, for almost all y, there is a stage s y such that (41) holds for all stages s ⩾ s y . So, by the definition of k ( ⟨ e , y ⟩ , s ) , lim s → ∞ k ( ⟨ e , y ⟩ , s ) = 1 for all sufficiently large numbers y, whence (9) holds.

This completes the proof of Theorem 4.4. □

5. Closure properties of EUwttAC