THE UNIVERSITY OF CHICAGO

AUTOMORPHISMS AND NONINVARIANT PROPERTIES OF THE COMPUTABLY ENUMERABLE SETS

A DISSERTATION SUBMITTED TO

THE FACULTY OF THE DIVISION OF THE PHYSICAL SCIENCES

IN CANDIDACY FOR THE DEGREE OF DOCTOR OF PHILOSOPHY

DEPARTMENT OF MATHEMATICS

BY KEVIN MITCHELL WALD

CHICAGO, ILLINOIS AUGUST 1999 To Bernard, Francine, and David Wald.

ABSTRACT

This thesis concerns automorphisms and noninvariant properties of the computably enumerable sets. We prove two results relating semilow sets and prompt degrees via automorphisms, one of which is complementary to a recent result of Downey and Harrington. We also show that the properties of quasicreativity, n-creativity, subcreativity, and effective simplicity are not invariant under automorphism, and that in fact every promptly simple set is automorphic to an effectively simple set. The techniques used in these proofs include a modification of the Harrington-Soare version of the method of Harrington-Soare and Cholak for constructing Δ_{3}^{0} automorphisms; this modification takes advantage of a recent result of Soare on the extension of “restricted” automorphisms to full automorphisms.

ACKNOWLEDGEMENTS

I would like to thank my thesis advisor, Prof. Robert Soare, to whom I am most indebted for the support, advice, and education he supplied, and for the interest and patience he displayed, during my research towards and preparation of this dissertation.

I would also like to thank Prof. Peter Cholak for his numerous helpful comments and observations; Prof. Carl Jokusch for his suggestions regarding effective simplicity; and all those others who through their help and encouragement made this dissertation possible.

TABLE OF CONTENTS

ABSTRACT iii

ACKNOWLEDGEMENTS iv

1 SEMILOW SETS AND PROMPT DEGREES 1

1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1.2 Lowness and Promptness . . . . . . . . . . . . . . . . . . . . . 2 1.1.3 Downey-Harrington and Theorem 1.1.11 . . . . . . . . . . . . 4

1.2 Proof Machinery . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2.1 The Harrington-Soare Machinery . . . . . . . . . . . . . . . . 5 1.2.2 The New Extension Theorem . . . . . . . . . . . . . . . . . . 10 1.2.3 Additional Machinery . . . . . . . . . . . . . . . . . . . . . . . 14 1.2.4 Construction . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

1.3 Verification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 1.3.1 Tree Properties (Restricted Version) . . . . . . . . . . . . . . 18 1.3.2 Correctness of M\overline{A}, M̂\overline{B}, N \overline{A}, and N̂ \overline{B} on f . . . . . . . . . . 20 1.3.3 Verifying that G^{A} = Ĝ^{B} . . . . . . . . . . . . . . . . . . . . . . 26 1.3.4 Tree Properties (Unrestricted Version) . . . . . . . . . . . . . 28 1.3.5 Verifying that B ≤_{T} C . . . . . . . . . . . . . . . . . . . . . . 28

1.4 Proof of Theorem 1.1.11 . . . . . . . . . . . . . . . . . . . . . . . . . 28

2 NONINVARIANCE 35 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 2.2 Distinctness of n-creativity Notions . . . . . . . . . . . . . . . . . . . 38

2.2.1 Another Definition of n-creative . . . . . . . . . . . . . . . . . 38 2.2.2 Proof of Theorem 2.1.2 . . . . . . . . . . . . . . . . . . . . . . 39 2.2.3 Proof of Theorem 2.1.3 . . . . . . . . . . . . . . . . . . . . . . 46

2.3 Noninvariance of Quasicreativity and n-creativity . . . . . . . . . . . 48 2.4 Noninvariance of Subcreativity . . . . . . . . . . . . . . . . . . . . . . 52

2.4.1 Proof via Theorem 2.4.1 . . . . . . . . . . . . . . . . . . . . . 52 2.4.2 Intuition and Machinery . . . . . . . . . . . . . . . . . . . . . 52 2.4.3 Construction . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 2.4.4 Verification . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

2.5 Effective Simplicity . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 2.5.1 Intuition and Machinery . . . . . . . . . . . . . . . . . . . . . 57 2.5.2 Construction . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 2.5.3 Verifying Correctness of M\overline{A}, M̂\overline{B}, N \overline{A}, and N̂ \overline{B} on f …. 63 2.5.4 Verifying that G^{A} = Ĝ^{B}. . . . . . . . . . . . . . . . . . . . . . 67 2.5.5 Verifying that B is Effectively Simple. . . . . . . . . . . . . . . 68

REFERENCES 69

CHAPTER 1 SEMILOW SETS AND PROMPT DEGREES

1.1 Introduction

1.1.1 Background

A set A ⊆ ω is computably enumerable (c.e.) if its elements can be listed by an effective algorithm. The collection of computably enumerable sets can then be given two different kinds of structure, one based on their computational properties, and one based on their algebraic properties:

1. The c.e. Turing degrees form an upper semilattice C under ≤_{T} (Turing reducibility), and

2. The c.e. sets form a lattice E under inclusion.

In 1944, Post [8] first looked at the connection between these structures; in the search for a noncomputable incomplete degree, he defined several new properties of c.e. sets (such as creativity, simplicity, and hyperhypersimplicity) that have turned out to be definable purely in terms of set inclusion. Ever since that time, there has been an ongoing program of examining the relationship between the structures of C and E.

One fruitful area of research has been the study of automorphisms of E. This began in the 1970s, starting with Soare [12], and being further developed by the work of Maass, Stob, Downey, Harrington, and others. This early work involved the construction of effective automorphisms of various sorts. Then in the mid 1990s, Harrington and Soare, and independently Cholak, introduced a powerful new method for constructing automophisms. This method, described in [6], combines the use of computable trees (as introduced by Lachlan) with previous automorphism methods to produce Δ_{3}^{0} (0′′-computable) automorphisms. This has allowed numerous results, which had not yielded to effective automorphism methods, to become attainable.

For any two c.e. sets A and B, if there an automorphism Φ of E such that Φ(A) = B, we say that A is automorphic to B (denoted A ≃ B). Many past questions about automorphisms have concerned whether two c.e. sets of particular kinds may or may not be automorphic. For instance, Soare [12] showed that any two maximal c.e. sets A and B are automorphic, and more recently Downey and Stob [4] have shown that the same is true for hemimaximal sets. Numerous other results connect sets of different kinds; to take just one example, the above-mentioned method of Harrington-Soare and of Cholak was applied by them ([6], [2]) to show that every noncomputable c.e. set is automorphic to some high c.e. set.

1.1.2 Lowness and Promptness

In constructing an automorphism involving a given c.e. set A, we frequently wish to exert two forms of control regarding the enumeration of elements into A:

(1) We want to be able to guarantee that at least some “unwanted” elements will remain outside of A, and

(2) We want to be able to guarantee that at least some “wanted” elements eventually enter A.

Among the properties of c.e. sets that can particularly help us achieve (1) are the lowness properties:

Definition 1.1.1 A is low if A′ ∈ 0′.

Definition 1.1.2 \overline{A} is semilow if \{e : W_{e} ∩ \overline{A} ≠ ∅\} ≤_{T} 0′.

Among the properties that can help us with (2) are the promptness properties:

Definition 1.1.3 A is promptly simple (p.s.) if there are a computable function p and a computable enumeration {A_{s}}_{s∈ω} of A such that for all e,

W_{e} infinite ⟹ (∃s)(∃x)[x ∈ W_{e, at s} ∩ A_{p(s)}].

Definition 1.1.4 A is prompt if A ≡_{T} B for some p.s. set B.

A classic result employing these properties is that of Maass [7]:

Theorem 1.1.5 (Maass, 1982) If A and B are low (or even have semilow compliment) and are p.s. then A ≃ B.

The first result of this paper deals with a similar case, but one with less information about our two sets:

Theorem 1.1.6 For any c.e. set A which is low (or even has semilow complement) and for any promptly simple (p.s.) set C, there exists a c.e. set B ≤_{T} C with A automorphic to B (denoted by A ≃ B).

The proof of this relies on a modification of the Δ_{3}^{0}-automorphism method described in [6]. A brief account of the machinery of this method will be given in §1.2.1. In §1.2.2, we will describe the major modification to the method that must be made; specifically, the construction will be restricted to the complements of the given set A and the constructed set B, and then the “New Extension Theorem” of Soare (Theorem 1.2.6) will be employed to show that this restricted construction implies the existence of a full automorphism between A and B. Then §1.2.3 will describe the other additions that are required, and §1.2.4 will describe the overall construction. The verification of this construction will be given in §1.3.

Theorem 1.1.6 gives rise to several corollaries. First of all, every c.e. degree contains a set with semilow compliment [14, p. 73]. Hence,

Corollary 1.1.7 (∀a > 0)(∀ promptly simple C)(∃A ∈ a)(∃B ≤_{T} C)[A ≃ B].

Also, as Downey and Cholak have observed, if we take two low p.s. degrees d and c, then the lower cone of either one consists of sets that can fulfill the role of A above, and can therefore be automorphically mapped into the lower cone of the other. Hence,

Corollary 1.1.8 There exist distinct noncomputable c.e. degrees d and c such that

(∀A ≤_{T} d)(∃B ≤_{T} c)[A ≃ B] & (∀B ≤_{T} c)(∃A ≤_{T} d)[A ≃ B].

1.1.3 Downey-Harrington and Theorem 1.1.11

A degree is said to be prompt if it contains a p.s. set, and tardy if it does not. Downey and Harrington have shown the following result on prompt low degrees and tardy degrees:

Theorem 1.1.9 (Downey-Harrington) There are a prompt low degree c and tardy degree a such that

(∀B ∈ c)(∀A ≤_{T} a)[A ≄ B].

Theorem 1.1.6 is complementary to this result, in that it shows that Theorem 1.1.9 cannot be extended to the cone below c. That is, Theorem 1.1.6 has the following corollary:

Corollary 1.1.10 For any prompt degree c (low or otherwise), and any degree a (tardy or otherwise), there exist some A ≤_{T} a (in fact, some A ∈ a) and some B ≤_{T} c such that A ≃ B.

Proof. Take A to be a set in a with semilow complement, and C to be a p.s. set in c, and apply Theorem 1.1.6.

Theorem 1.1.9, in turn, places a restriction on how Theorem 1.1.6 may be extended. In the latter theorem, we show that for \overline{A} semilow and C p.s., A is automorphic to some B ≤_{T} C. This raises the question of whether such a B can always be found so that B is not only computable from C, but actually Turing equivalent to C. Theorem 1.1.9 shows that this cannot always be done.

However, suppose we have an A that not only has semilow compliment, but is also promptly simple. Then we do get the following result:

Theorem 1.1.11 If A is low (or has semilow complement) and p.s. and C is p.s., then (∃B ≡_{T} C)[A ≃ B].

We prove this in §1.4, with the aid of Maass’s Theorem 1.1.5.

1.2 Proof Machinery

1.2.1 The Harrington-Soare Machinery

Since our work closely follows the methods of Harrington and Soare [6], it is necessary to review some of their machinery.

First of all, we consider the construction of our automorphism to be a game between two players, RED and BLUE. RED constructs two complete collections of the c.e. sets, {U_{n}}_{n∈ω} and {V_{n}}_{n∈ω}, and BLUE in response constructs {Û_{n}}_{n∈ω} and {V̂_{n}}_{n∈ω}, so that our final automorphism will map each U_{n} to Û_{n} and each V̂_{n} to V_{n}.

These constructions will be performed by enumerating elements into the appropriate sets. From one copy of the natural numbers (ω) RED enumerates elements into U_{n} and BLUE into V̂_{n}; from a second copy (ω̂) RED enumerates elements into V_{n} and BLUE into Û_{n}. To keep track of what sets a given x or x̂ is in, we define the full e-state of x, as follows:

Definition 1.2.1 Given two sequences of r.e. sets {X_{n}}_{n∈ω} and {Y_{n}}_{n∈ω}, define ν(e, x), the full e-state of x with respect to (w.r.t.) {X_{n}}_{n∈ω} and {Y_{n}}_{n∈ω} to be the triple ⟨e, σ(e, x), τ(e, x)⟩, where

σ(e, x) = {i : i ≤ e & x ∈ X_{i}}, and
τ(e, x) = {i : i ≤ e & x ∈ Y_{i}}.

To guarantee that a construction of this type produces an automorphism, it suffices to show that the states on one side that are “well resided” (contain infinitely many elements) correspond exactly to the “well resided” states on the other side. That is, that

(∀ν)(∃^{∞}x ∈ ω)[ν(e, x) = ν w.r.t. {U_{n}}_{n∈ω} and {V̂_{n}}_{n∈ω}]
⟺ (∃^{∞}x̂ ∈ ω̂)[ν(e, x̂) = ν w.r.t. {Û_{n}}_{n∈ω} and {V_{n}}_{n∈ω}].

Second, this construction is performed on a tree T. Each node α has attached to it certain guesses regarding what states will be “well visited” (will have infinitely many elements enter them) and what states will nonetheless be “emptied” (will be well visited but not well resided). The nodes on the true path f will in the end be those that have guessed correctly. As the construction progresses, there are successive approximations f_{s} to f.

In addition, elements travel along the tree either downwards or leftwards (the latter generally when f_{s} shifts leftwards). We may thus describe for each node α, at each stage s, the following sets:

S_{α,s} = {x : α(x, s) = α}

(the elements x “at” node α),

R_{α,s} = {x : α(x, s) ⊇ α}

(the elements x at or below node α), and

Y_{α,s} = ⋃ {R_{α,t} : t ≤ s}

(the elements x that have ever been at node α).

We also have the duals Ŝ_{α,s}, R̂_{α,s}, and Ŷ_{α,s} of these, for elements x̂.

For technical reasons, we will be dividing the elements that enter S_{α,s} into two sets, S_{α,s}^{0} and S_{α,s}^{1} (the former is used as a source of elements for coding and such purposes, while the latter provides the elements to be passed on down to successor nodes).

The elements of R_{α,s} (R̂_{α,s}) may then be enumerated into sets U_{α} and V̂_{α} (Û_{α} and V_{α}), which represent approximations to U_{n} and V̂_{n} (Û_{n} and V_{n}), for |α| = 5n + 1 and 5n + 2 respectively. (That is, we will have U_{α} =^{∗} U_{n} and V_{α} =^{∗} V_{n} by construction, and Û_{n} = Û_{α} and V̂_{n} = V̂_{α} by definition, for any α ⊂ f.)

For α in general, we let e_{α} (ê_{α}) be the greatest n such that 5n + 1 (5n + 2) ≤ |α|. (Thus, e_{α} > e_{α^{−}} exactly when there exist sets U_{α} and Û_{α}, and ê_{α} > ê_{α^{−}} exactly when there exist sets V̂_{α} and V_{α}.) Then to keep track of our α-sets we define α-states as follows:

Definition 1.2.2 (i) The α-state of x at stage s, ν(α, x, s), is the triple ⟨α, σ(α, x, s), τ(α, x, s)⟩ where

σ(α, x, s) = {e_{β} : β ⊆ α & e_{β} > e_{β^{−}} & x ∈ U_{β,s}},

τ(α, x, s) = {ê_{β} : β ⊆ α & ê_{β} > ê_{β^{−}} & x ∈ V̂_{β,s}}.

(ii) The final α-state of x is ν(α, x) = ⟨α, σ(α, x), τ(α, x)⟩ where σ(α, x) = lim_{s} σ(α, x, s) and τ(α, x) = lim_{s} τ(α, x, s).

For technical reasons, we will also sometimes need a modified version of ν(α, x, s) or ν(α, x̂, s) that depends solely on α^{−}. Where β = α^{−}, if e_{α} > e_{β} then we define ν^{+}(α, x, s) to be the result of replacing U_{α,s} in the definition of ν(α, x, s) with the similar set Z_{e_{α},s} defined by

Z_{e_{α},s+1} =_{dfn} {x : x ∈ U_{e_{α},s+1} & x ∈ Y_{β,s}^{1}}.

If ê_{α} > ê_{β} we similarly define ν^{+}(α, x̂, s) to be the result of replacing Û_{α,s} in the definition of ν(α, x̂, s) with Ẑ_{ê_{α},s} defined by

Ẑ_{ê_{α},s+1} =_{dfn} {x̂ : x̂ ∈ V_{ê_{α},s+1} & x̂ ∈ Ŷ_{β,s}^{1}}.

It is in terms of α-states that our guessing machinery for each node is phrased. For every node α, we have the following lists (sets of α-states):

1. M_{α}, α’s guess about what α-states are well visited;

2. B_{α}, α’s guess about what α-states are emptied by BLUE;

3. R_{α}, α’s guess about what α-states are emptied by RED;

4. N_{α} = B_{α} ∪ R_{α}, α’s guess about what α-states are emptied overall; and all of their duals. Our construction will guarantee that the guesses M_{α}, M̂_{α}, N_{α}, and N̂_{α} are correct for all α on the true path. For any α our guess M̂_{α} always equals {ν̂ : ν ∈ M_{α}} and N̂_{α} always equals {ν̂ : ν ∈ N_{α}} (we will sometimes loosely state these correspondences as M̂_{α} = M_{α} and N̂_{α} = N_{α}); we thus will guarantee that the sets of genuinely well resided states of both sides will likewise correspond. We will designate these sets of genuinely well resided states by K_{α} and K̂_{α}. (In this we depart slightly from the notation of [6], in which K_{α} and K̂_{α} referred to the complements of these sets.)

In addition, we have the following machinery to aid in our construction:

E_{α} = {ν : (∃^{∞}x)(∃s)[x ∈ S_{α,s} − ⋃ {S_{α,t} : t < s} & ν(α, x, s) = ν]}

(the set of all α-states that are well visited by elements first coming into S_{α}), for j = 1, 2,

E_{α}^{j} = {ν : (∃^{∞}x)(∃s)[x ∈ S_{α,s}^{j} − ⋃ {S_{α,t} : t < s} & ν(α, x, s) = ν]}

(the set of all α-states that are well visited by elements first coming into S_{α} in S_{α}^{j}), and

F_{α} = {ν : (∃^{∞}x)(∃s)[x ∈ R_{α,s} & ν(α, x, s) = ν]}

(the set of all α-states that are genuinely well visited by elements of R_{α}). For α ⊂ f, we will have E_{α} = E_{α}^{0} = E_{α}^{1} = F_{α} = M_{α}.

Also, for technical reasons, we have:

1. A list F_{β}^{+} similar to F_{α} that is attached to the node β = α^{−} and depends only on β. If e_{α} > e_{β} then we define

F_{β}^{+} = {ν : (∃^{∞}x)(∃s)[x ∈ Y_{β,s}^{1} & ν^{+}(α, x, s) = ν]},

and F̂_{β}^{+} = {ν̂ : ν ∈ F_{β}^{+}}; if ê_{α} > ê_{β} then we define F̂_{β}^{+} by the dual of the above expression and define F_{β}^{+} = {ν : ν̂ ∈ F̂_{β}^{+}}.

2. A number k_{α} that is attached to the node α; k_{α} is a guess at an upper bound

for the set of all x’s and x̂’s that are permanently in a non-well-resided α-state. These are used in the course of defining f and f_{s}. Specifically, f and f_{s} are defined using a recursive collection of c.e. sets {C_{α}}, with α ⊂ f iff |C_{α}| = ∞ and α ⊂ f_{s+1} iff α^{−} ⊂ f_{s+1} and |C_{α,s+1}| > |C_{α,s}|. These {C_{α}} are defined so that if |C_{α}| = ∞ then we automatically have that

1. M_{α} = F_{α^{−}}^{+},

2. M̂_{α} = F̂_{α^{−}}^{+},

3. R_{α} and R̂_{α} are correct guesses, and

4. k_{α} is a correct guess. Thus, to verify that our construction indeed yields an automorphism, we need only separately verify that f is infinite and that for all α ⊂ f,

1. F_{α^{−}}^{+} = F_{α},

2. F̂_{α^{−}}^{+} = F̂_{α}, and

3. B_{α} and B̂_{α} are correct guesses.

The final notions we must define are those of consistency; if a node α is inconsistent, then it is terminal (and we must ensure that it is not on the true path). Definition 1.2.3 A node α ∈ T is M-inconsistent if e_{α} > e_{β}, where β = α^{−}, and there are α-states ν_{0} <_{B} ν_{1} such that ν_{0} ∈ M_{α} and ν_{1} ↾ β ∈ M_{β} but ν_{1} ∉ M_{α}. Otherwise α is M-consistent. Definition 1.2.4 A node α ∈ T is R-consistent if

(∀ν_{0} ∈ R_{α})(∃ν_{1})[ν_{0} <_{R} ν_{1} & ν_{1} ∈ M_{α}].

That is, α is M-consistent if every state a BLUE move away from a putative well visited state is well visited, and R-consistent if every state which RED is supposed to empty has a state where RED can put the elements it is supposed to be removing. We also have the corresponding dual notions of M̂-consistency and R̂-consistency. In our modified version of the Harrington-Soare construction, a node α is said to be consistent if it is M-consistent, M̂-consistent, R-consistent, and R̂-consistent. (In this, our definition of consistency differs from the definition in [6], which also includes a notion of C-consistency or D-consistency, which makes it possible to do certain kinds of coding.)

1.2.2 The New Extension Theorem

We now add to the techniques of [6] the notion of restriction to \overline{A} and \overline{B}, which will enable us to use the New Extension Theorem. In [6], elements are enumerated into c.e. sets U_{α}, Û_{α}, V_{α}, and V̂_{α} (for α ∈ T) by two players, RED and BLUE. In this construction, where ρ = f ↾ 1, U_{ρ} and Û_{ρ} will, in the end, equal A (up to finite difference) and B respectively; U_{ρ} =^{∗} A because almost every element of A is eventually enumerated into U_{ρ}, and B is defined to equal Û_{ρ}.

For technical reasons, we will find it advantageous to modify this construction slightly, so that

1. We know during the course of the construction exactly what ρ is,

2. At every stage s, f_{s}↾1 = ρ, and

3. We can therefore define enumerations {A_{s}} and {B_{s}} of A and B by setting A_{s} = U_{ρ,s} and B_{s} = Û_{ρ,s}.

We do this by modifying the definition of C_{α} for all α such that α = 1. Let ρ_{1} be the node such that |ρ_{1}| = 1, and

1. M_{ρ_{1}} = {⟨ρ_{1}, ∅, ∅⟩, ⟨ρ_{1}, {0}, ∅⟩},

2. M̂_{ρ_{1}} = {⟨ρ_{1}, ∅, ∅⟩, ⟨ρ_{1}, {0}, ∅⟩}, and

3. k_{ρ_{1}} = 0.

That is, node ρ_{1} guesses that

1. Both U_{ρ_{1}} and its complement, considered as ρ_{1}-states, will be well visited,

2. Both Û_{ρ_{1}} and its complement, considered as ρ_{1}-states, will be well visited, and

3. No element will remain in a non-well-visited ρ_{1}-state.

(Note that we need not specify R_{ρ_{1}}, R̂_{ρ_{1}}, B_{ρ_{1}}, and B̂_{ρ_{1}}, because these are the same for all α with |α| = 1.) We then define C_{ρ_{1}} = ω, and C_{α} = ∅ for all other α with |α| = 1.

This will indeed guarantee that ρ = ρ_{1}, and that f_{s}↾1 = ρ_{1} for all s; we will then define A_{s} and B_{s} as above. However, because we have redefined C_{α} for |α| = 1, we now must verify the statements that the definition of C_{α} used to guarantee automatically; that is, we must separately verify the following tree properties:

1. M_{ρ} = F_{λ}^{+},

2. M̂_{ρ} = F̂_{λ}^{+}, and

3. k_{ρ} is a correct guess.

(Again, we do not have to verify that R_{ρ} and R̂_{ρ} are correct guesses, because these are the same for all α with |α| = 1.) We will do this as part of the verification of our construction, in §1.3.1 and §1.3.4.

Since we have now identified A with U_{ρ} and B with Û_{ρ}, we may thus speak of A-states, \overline{A}-states, B-states, and \overline{B}-states, which will be those states including U_{ρ}, not including U_{ρ}, including Û_{ρ}, and not including Û_{ρ}, respectively. We can then speak of the restriction of a list of states to A, \overline{A}, B, or \overline{B}; for any list S (Ŝ), S^{A} (Ŝ^{B}) is the list of all A-states (B-states) in S (Ŝ), and S\overline{A} (Ŝ\overline{B}) is the list of all \overline{A}-states (\overline{B}-states) in S (Ŝ).

So, for example, for any α we can consider M_{α} as a disjoint union of its restriction to A, M_{α}^{A}, and its restriction to \overline{A}, M\overline{A} ; α, and we may treat these two sublists separately; similarly, M̂_{α} can be considered as M̂_{α}^{B} ⊔ M̂\overline{B} ; α. (In particular, when we show that M̂_{ρ} = F̂_{λ}^{+}, we will do so by separately showing that M̂\overline{B} ; ρ = F̂_{λ}^{+,\overline{B}} and that M̂_{ρ}^{B} = F̂_{λ}^{+,B}.)

Our designation of A-states, \overline{A}-states, and so forth also allows us to consider the moves in any RED/BLUE game to be divided into the following three types:

1. “Exterior” move. A enumeration into U_{ρ,s+1} = A_{s+1} or Û_{ρ,s+1} = B_{s+1}. (That is, a move from an A-state into an \overline{A}-state, or from a B-state into a \overline{B}-state.)

2. \overline{A}/\overline{B} move. An enumeration into U_{α} or V̂_{α} (|α| > 1) of some x ∈ \overline{A}_{s} or an enumeration into Û_{α} or V_{α} (|α| > 1) of some x̂ ∈ \overline{B}_{s}. (That is, a movement between \overline{A}-states or between \overline{B}-states.)

3. A/B move. An enumeration into U_{α} or V̂_{α} (|α| > 1) of some x ∈ A_{s} or an enumeration into Û_{α} or V_{α} (|α| > 1) of some x̂ ∈ B_{s}. (That is, a movement between A-states or between B-states.)

However, suppose we only ever consider moves of type 1 and type 2, and completely ignore moves of type 3. This process can be considered a RED/BLUE game that is very much like the RED/BLUE game in [6], except that

1. It is entirely restricted to \overline{A} and \overline{B} (that is, every object in the machinery of [6] is replaced by its restriction to \overline{A} or \overline{B}), and

2. Elements occasionally are removed entirely from the game by exterior moves.

Such a construction would only guarantee a correspondence between the \overline{A}-states and the \overline{B}-states. However, it turns out that if we also can guarantee a correspondence between the exterior moves on the two sides, then this is enough to guarantee the existence of an overall automorphism. The idea is that if we have elements entering A and B in “the same states,” then a suitable set of type 3 moves, taking advantage of this supply of elements, could be added to guarantee a correspondence between A-states and B-states as well.

In order to keep track of this correspondence between exterior moves, we define for every α the sets G_{α}^{A} and Ĝ_{α}^{B}:

G_{α}^{A} = {ν : (∃^{∞}x)(∃s)[x ∈ A_{s+1} − A_{s} & ν = ν(α, x, s) & x ∈ Y_{α,s}]},

and Ĝ_{α}^{B} is defined correspondingly for B. That is, G_{α}^{A} (Ĝ_{α}^{B}) is the set of all α-states ν (ν̂) from which infinitely many elements are enumerated directly into A (B).

To further formalize this idea, we must also introduce the notion of an enumeration:

Definition 1.2.5 Given a computable priority tree T with (infinite) true path f ∈ [T], an enumeration 𝔼 for T is a simultaneous computable enumeration of c.e. sets U_{α}, V_{α}, and Û_{α}, V̂_{α}, for α ∈ T, such that {U_{α}}_{α⊂f} and {V_{α}}_{α⊂f} are both complete collections of the c.e. sets up to finite differences.

The computable enumerations made while playing an \overline{A}/\overline{B} game thus define some enumeration 𝔼, and we want to show that if 𝔼 guarantees a correspondence of \overline{A}- states and \overline{B}-states and of exterior moves on both sides, then we are guaranteed the existence of an enumeration giving rise to a complete automorphism. The New Extension Theorem (NET) states that this is indeed the case:

Theorem 1.2.6 (New Extension Theorem, Soare) If an enumeration 𝔼 satisfies:

(T1) K\overline{A} = K̂\overline{B}, and

(T2) G^{A} = Ĝ^{B},

then A ≅ B by an automorphism of E which extends 𝔼.

The advantage of the NET, then, is that we automatically get an automorphism between A and B if we can play our restricted game, and guarantee that the true path f is infinite, and that on f

1. M\overline{A}, M̂\overline{B}, N \overline{A}, and N̂ \overline{B} are all correct guesses, and 2. G^{A} = Ĝ^{B}.

For the former, we will apply a form the proof used in [6] to show that the overall RED/BLUE game causes M, M̂, N, and N̂ all to be correct on the true path, modified slightly to take into account the occasional removal of elements by exterior moves. The latter we will ensure by an appropriate choice of exterior moves.

1.2.3 Additional Machinery

Our tree construction will employ the following machinery:

1. We have all of the machinery of Chapter 2 of [6], with the given modification to the definitions of “consistent” and of C_{α}, and restricted to \overline{A} and \overline{B}. (Henceforth, when this will not cause confusion, we shall adopt the convention of omitting the superscript \overline{A} and \overline{B} that indicates this restriction; e.g., we shall refer to M\overline{A} ; α as M_{α}. This convention will be adopted in §1.2.4 and §1.3.2.)

2. We have a fixed enumeration {Ã_{s}}_{s∈ω} of A.

3. In the course of our construction we will also be producing an enumeration {A_{s}}_{s∈ω} of our given A and defining B by an enumeration {B_{s}}_{s∈ω}, as described in §1.2.2. A_{s} (B_{s}) will thus be equal to the set of all elements x (x̂) that have been removed from our restricted construction at stage s by exterior moves.

4. We have a list L^{G} of pairs of the form ⟨α, ν̂⟩, used to satisfy the requirement that if ν ∈ G_{α}^{A} then ν̂ ∈ Ĝ_{α}^{B}. Every time an element of some α-state ν_{1} enters A, the pair ⟨α, ν̂_{1}⟩ is added to L^{G}. We also guarantee that if ⟨α, ν̂_{1}⟩ appears infinitely many times in L^{G}, then infinitely many elements from ν̂_{1} are put into B.

5. For every node α, for every \overline{A}-state ν of α, we have the following infinite sets of markers and c.e. sets, which will be used, together with the semilowness of \overline{A}, to guarantee that the removal of elements from \overline{A} does not interfere with our construction (by a technique introduced by Robinson [9], and used for example by Soare in [13]):

(a) For each i ∈ ω, the marker Γ_{ν,i}^{1,α} and c.e. set Q_{ν,i}^{1,α}. One marker of this type will be attached to any element x that enters S_{α} in α-state ν.

(b) For each i ∈ ω, the marker Γ_{ν,i}^{2,α} and c.e. set Q_{ν,i}^{2,α}. One marker of this type will be attached to any element x that enters α-state ν (whether it has just entered S_{α} or not).

(c) For each i ∈ ω, the marker Γ_{ν,i}^{3,α} and c.e. set Q_{ν,i}^{3,α}. One marker of this type will be attached to any element x in S_{α^{−}} if ν^{+}(x, α) becomes equal to α-state ν.

By the Recursion Theorem, we will also be able to assume for this construction that we know indices q_{ν,i}^{1,α}, q_{ν,i}^{2,α}, and q_{ν,i}^{3,α} uniformly for the sets Q_{ν,i}^{1,α}, Q_{ν,i}^{2,α}, and Q_{ν,i}^{3,α} respectively.

6. For every node α, for every \overline{B}-state ν̂ of α, we will be constructing an infinity of c.e. sets J_{ν,i}^{α}. (These will help us find elements of C to permit necessary elements to enter B.) By the Recursion Theorem and the Slowdown Lemma [14, p. 284] we may assume that we know indices j_{ν,i}^{α} uniformly for all these c.e. sets, such that any given element appears in W_{j_{ν,i}^{α}} strictly later than we enumerate it into J_{ν,i}^{α}.

1.2.4 Construction

This construction is based on that in [6]. Throughout this construction, as mentioned in §1.2.3, we will adopt the convention of omitting the superscripts \overline{A} and \overline{B} that indicate restriction to a \overline{A}/\overline{B} game.

Let ĥ be the 0–1 valued function such that for all e, W_{e} ∩ \overline{A} ≠ 0 if and only if ĥ(e) = 1. By semilowness of \overline{A}, ĥ ≡_{T} 0′, so by the Limit Lemma there must exist a computable function h such that lim_{s} h(e, s) exists and equals ĥ(e) (see [14, p. 72]); we fix such a computable function h.

Because C is prompt, by the Promptly Simple Degree Theorem [14, p. 284] there exists a computable function p such that

W_{e} infinite ⟹ (∃x)(∃s)[x ∈ W_{e, at s} & C_{s}↾x ≠ C_{p(s)}↾x].

We fix some such function p.

Every stage s + 1 in our construction will be divided into steps as in [6]. Now, however, we must distinguish two different types of steps:

• Interior steps. These are the same as the corresponding numbered steps in [6], except that they are restricted to \overline{A} and \overline{B}. In other words, a game played with the interior steps alone would be simply a RED/BLUE game played on the \overline{A}- and \overline{B}-states. Steps 1–5, ˆ1–ˆ5, and 11 of the present construction are of this type.

• Exterior steps. These are steps by which elements are moved into A_{s} or B_{s}. That is, if we consider just the RED/BLUE game played on \overline{A}- and \overline{B}-states, elements are allowed to disappear entirely from the game during exterior steps. In the current construction, the exterior steps are Step 0, which moves elements into A_{s} when necessary, and Step ˆ8, which moves elements into B_{s} in order to guarantee that G^{A} = Ĝ^{B}.

Our construction is then as follows:

Stage s = 0. For all α ∈ T define U_{α,0} = V_{α,0} = Û_{α,0} = V̂_{α,0} = ∅, and define m(α, 0) = 0. Define Y_{λ,0} = Ŷ_{λ,0} = ∅, and f_{0} = λ. Define every Q_{ν,i,0}^{α} = ∅ and every marker Γ_{ν,i,0}^{α} to be unassigned. Define every J_{ν,i}^{α} = ∅. Define A_{0} = B_{0} = ∅.

Stage s + 1. Find the least n < 11 such that Step n applies to some x ∈ Y_{α,s} and perform the intended action. If there is no such n, then find the least n < 11 such that Step n̂ applies to some x̂ ∈ Ŷ_{α,s}, and perform the indicated action. If none of these steps applies, then apply Step 11, and go to stage s + 2.

Step 0 (Moving elements into A).

Substep 0.1 (Enumerated elements). If x ∈ (Y_{λ,s} ∩ Ã_{s+1}) − (Y_{λ,s−1} ∩ Ã_{s}), (0.1.1) Where x is in α-state ν, add to L^{G} a pair ⟨β, ν̂↾β⟩ for every β ⊆ α, (0.1.2) Enumerate x into A_{s+1}, and (0.1.3) Designate every Γ-marker attached to x as unassigned.

Substep 0.2 (Assigning a Γ-marker to an x believed not to go into A). In the following, to challenge x with regard to marker type j (= 1, 2, 3) and α-node ν means to do the following:

(i) Where i is the least number such that the marker Γ_{ν,i}^{j,α} is currently unassigned, enumerate x into Q_{ν,i}^{j,α}.

(ii) Find the least t such that either

(a) h(q_{ν,i}^{j,α}, t)↓ = 1 or

(b) x ∈ Ã_{t}.

In case (a), assign marker Γ_{ν,i}^{j,α} to x. In case (b),

(iii) If j = 1 or 2, add the pair to L^{G} a pair ⟨β, ν̂↾β⟩ for every β ⊆ α; if j = 3, add a pair ⟨β, ν̂↾β⟩ for every β ⊆ α^{−};

(iv) Enumerate x into A_{s+1} immediately; and

(v) Designate every Γ-marker attached to x as unassigned.

Then Substep (0.2) consists of repeating the following three steps:

(0.2.1) If some element x is to be moved into some Y_{α} in \overline{A}-state ν by Step 1 or 2, then challenge x with regard to marker type 1 and α-state ν.

(0.2.2) If some element x is to be put into \overline{A}-state ν by one of Steps 1–5 or 11C, then challenge x with regard to marker type 2 and α-state ν.

(0.2.3) If there is some element x such that, as a result of x being enumerated into U_{e_{α}} and/or the action of Steps 1–5, 11C, or 11E, ν^{+}(x, α) will become equal to \overline{A}-state ν, then challenge x with regard to marker type 3 and α-state ν. until none of these three challenges described enters case (b) (that is, none of them causes an element to enter A_{s+1}).

Steps 1–5, ˆ1–ˆ5. As in [6], restricted to \overline{A} and \overline{B}.

Step ˆ8. (Moving elements into B.)

Find the first unmarked pair ⟨α, ν̂⟩ in L^{G} such that there exists some x̂ ∈ Ŝ_{α,s}^{0} in state ν̂. Then

(ˆ8.1) Enumerate the least such x̂ into J_{ν,i}^{α}.

(ˆ8.2) Where x̂ ∈ W_{j_{ν,i}^{α}, at t}, if C_{t}↾ x ≠ C_{p(t)}↾ x, then enumerate x into B_{s+1} and mark the current copy of ⟨α, ν̂⟩.

Step 11. As in [6], restricted to \overline{A} and \overline{B}.

1.3 Verification

1.3.1 Tree Properties (Restricted Version)

As mentioned in §1.2.2, there are certain properties of the tree T (the tree properties) that hold automatically in the construction of [6], but which in our construction must be proved to hold for ρ; namely

1. M_{ρ} = F_{λ}^{+},

2. M̂_{ρ} = F̂_{λ}^{+}, and

3. k_{ρ} is a correct guess.

In order to employ the NET, which holds for an enumeration 𝔼 performed on a tree T defined as in [6], we need to show that these hold as given. However, our verfication of the correctness of M\overline{A}, M̂\overline{B}, N \overline{A}, and N̂ \overline{B} only requires the use of the restrictions to \overline{A} and \overline{B} of these tree properties. It will be most convenient, therefore, to verify the tree properties in separate stages:

1. In this section, we verify the restrictions of these tree properties to \overline{A} and \overline{B}.

2. In §1.3.2 we use these tree properties to verify the correctness of M\overline{A}, etc.

3. In §1.3.3 we use the above verification in our verification that G^{A} = Ĝ^{B}.

4. In §1.3.4, we use the correspondence between G^{A} and Ĝ^{B} to show the full, unrestricted form of these tree properties.

We assume, first of all, that A is infinite and coinfinite, for otherwise A is recursive and Theorem 1.1.6 trivially holds. We now verify the following:

Lemma 1.3.1 M_{ρ} = F_{λ}^{+}

Proof. By Substep 11E, every element x of ω eventually enters Y_{λ}. Every element of the infinite set A eventually enters some A_{s} by Step 0, and no element of the infinite set \overline{A} ever does. Thus, there are infinitely many x such that for some s, x ∈ Y_{λ,s} and x ∈ A_{s}, and there are infinitely many x such that for some s, x ∈ Y_{λ,s} and x ∉ A_{s}, so F_{λ}^{+} = {⟨ρ_{1}, ∅, ∅⟩, ⟨ρ_{1}, {0}, ∅⟩} = M_{ρ_{1}} = M_{ρ}.

(In particular, then, M\overline{A} ; ρ = F_{λ}^{+,\overline{A}}.)

Lemma 1.3.2 M̂\overline{B} ; ρ = F̂_{λ}^{+,\overline{B}}.

Proof. By Substep 11E, every element x̂ of ω̂ eventually enters Y_{λ} without first en-

tering any B_{s}. Thus, ⟨ρ_{1}, ∅, ∅⟩ ∈ F̂_{λ}^{+}, so F̂_{λ}^{+,\overline{B}} = \{⟨ρ_{1}, ∅, ∅⟩\} = M̂\overline{B} ; ρ_{1} = M̂\overline{B} ; ρ.

Lemma 1.3.3 No element of \overline{A} or \overline{B} remains permanently in a non-well-visited ρstate.

Proof. If x ∈ \overline{A} (x̂ ∈ \overline{B}), then x (x̂) is permanently in the ρ-state \{⟨ρ_{1}, ∅, ∅⟩\}, which we have just seen is well-visited.

(In other words, the guess k_{ρ} = 0 is correct.)

We have thus verified the restricted versions of the tree properties for ρ. Since all C_{α}, |α| > 1, are defined as in [6], these properties therefore hold automatically for all α ⊇ ρ; that is, for all α ⊇ ρ,

1. M\overline{A} ; α = F_{α}^{+,\overline{A}},

2. M̂\overline{B} ; α = F̂_{α}^{+,\overline{B}}, and

3. k_{α} is the upper bound for all x ∈ \overline{A} and x̂ ∈ \overline{B} that remain in a non-well-visited α-state.

1.3.2 Correctness of M\overline{A}, M̂\overline{B}, N \overline{A}, and N̂ \overline{B} on f

Throughout this section, we will once again adopt the convention mentioned in §1.2.3 of omitting the superscripts \overline{A} and \overline{B} that indicate restriction to a \overline{A}/\overline{B} game.

It suffices to verify that the versions of Lemmas 5.1 through 5.12 of [6] hold for the \overline{A}/\overline{B} game as they did for the overall game in the Harrington-Soare construction. To aid us in this, we first prove the following additional lemma:

Lemma 5.0. (All markers eventually receive permanent assignments.)

(i) If α-state ν ∈ E_{α} then there exists an infinite set \{x_{i}\}_{i∈ω} ⊆ \overline{A} such that

(∀i)[lim_{s} Γ_{ν,i,s}^{1,α} = x_{i} & (∃s)[x_{i} ∈ S_{α,s} − Y_{α,s−1} & ν(α, x_{i}, s) = ν]].

(ii) If α-state ν ∈ F_{α} then there exists an infinite set \{x_{i}\}_{i∈ω} ⊆ \overline{A} such that

(∀i)[lim_{s} Γ_{ν,i,s}^{2,α} = x_{i} & (∃s)[x_{i} ∈ R_{α,s} & ν(α, x_{i}, s) = ν]].

(iii) If α-state ν ∈ F_{α}^{+} then there exists an infinite set \{x_{i}\}_{i∈ω} ⊆ \overline{A} such that

(∀i)[lim_{s} Γ_{ν,i,s}^{3,α} = x_{i} & (∃s)[x ∈ R_{α,s} & ν^{+}(α, x_{i}, s) = ν]].

Proof. All of these proofs are similar; we therefore give just the proof for (i), which serves with appropriate modifications for the other two:

(i) Assume by induction that this is true for all i′ < i, and let t be a stage by which

(a) lim_{s} Γ_{ν,i′,s}^{1,α} = Γ_{ν,i′,t′}^{1,α} for all t′ ≥ t, i′ < i; and

(b) lim_{s} h(q_{ν,i}^{1,α}, s) = h(q_{ν,i}^{1,α}, t′) for all t′ ≥ t. Then at some stage t′ ≥ t, Γ_{ν,i}^{1,α} must be assigned to some x (either Γ_{ν,i}^{1,α} is already assigned at stage t, or the next x to enter S_{α} in state ν must have Γ_{ν,i}^{1,α} assigned to it by Step (0.2.1)). Thus, lim_{s} h(q_{ν,i}^{1,α}, s) = 1 (for if it were 0, Step (0.2.1) could not assign a marker). Hence Q_{ν,i}^{1,α} ∩ \overline{A} ≠ ∅, so some y eventually goes into Q_{ν,i}^{1,α} that does not eventually go into A. When this y goes into Q_{ν,i}^{1,α}, it has Γ_{ν,i}^{1,α} assigned to it (since y does not go into A), and since y never enters A this marker is permanently assigned to y.

Since only finitely many Γ_{ν}^{1,α} markers may be attached to a given y, the set {x_{i}}_{i∈ω}, where x_{i} is the y to which marker Γ_{ν,i}^{1,α} is permanently assigned, must be infinite.

We now examine Lemmas 5.1–5.12 individually. The first three of these hold just as before:

Lemma 5.1. At stage s + 1, (i) if x enters R_{α}, α ≠ λ, then Step 1 or Step 2 applies to α and x; (ii) if x moves from S_{α} to S_{δ} then one of the following steps must apply to x:

Step 1_{δ} for δ <_{L} α or δ^{−} = α; Step 2_{δ} for δ such that δ^{−} = α; or Step 11_{α} Substep C applying to α, so f_{s+1} <_{L} α; and in the second two cases x enters S_{δ}^{1};

(iii) if x ∈ S_{α,s} is enumerated in a red set U_{α} at stage s + 1 then Step 1 or Step 4 must apply to x;

(iv) if x ∈ S_{α,s} is enumerated in a blue set V̂_{α} then Step 1, Step 3, Step 5, or Step n must apply to x.

Lemma 5.2 (True Path Lemma) f = lim inf_{s} f_{s}.

Lemma 5.3 For all α ∈ T, (i) f <_{L} α ⟹ R_{α,∞} = ∅, (ii) α <_{L} f ⟹ Y_{α} =^{∗} ∅, (iii) α ⊂ f ⟹ Y_{<α} =_{dfn} ⋃ {Y_{δ} : δ <_{L} α} =^{∗} ∅.

Lemma 5.4: (i) through (iv) hold as before. However, since it is now possible for an element x to disappear from the game by being enumerated (by an exterior move) into A (B in the dual lemma), we must slightly modify the statement of (v) by restricting x to elements of \overline{A} (\overline{B} in the dual), as shown:

Lemma 5.4. For every α ∈ T if α ≠ λ and β = α^{−} then (i) Y_{α} \ Y_{β} = ∅ and Y_{α} ⊆ Y_{β}, (ii) (∀x)(∃^{≤1}s)[x ∈ R_{α,s+1} − R_{α,s}], (iii) (∀x)(∃^{≤1}s)[x ∈ S_{α,s+1}^{0} − S_{α,s}^{0}], (iv) U_{α} \ Y_{α} = V̂_{α} \ Y_{α} = ∅, and

(v) α ⊂ f ⟹ (∃v_{α})(∀x ∈ \overline{A})(∀s ≥ v_{α})[x ∈ R_{α,s} ⟹ (∀t ≥ s)[x ∈ R_{α,t}]] (and correspondingly with \overline{B} in the dual).

Lemma 5.5 must be similarly restricted:

Lemma 5.5. For all x ∈ \overline{A} (i) α(x) =_{dfn} lim_{s} α(x, s) exists, and (ii) x is enumerated in at most finitely many r.e. sets U_{γ}, V̂_{γ}, and hence for

α = α(x),

ν(α, x) =_{dfn} lim_{s} ν(α, x, s) exists.

(And similarly with \overline{B} in the dual.)

Lemma 5.6 is the same as before (though now “n” can include 0):

Lemma 5.6. (i) Step 11 applies infinitely often.

(ii) If the hypotheses of some Step 1–5, n (Step ˆ1–ˆ5, n̂) remain satisfied then that step eventually applies.

The statement of Lemma 5.7 is as before:

Lemma 5.7. If α ⊂ f, α ≠ λ, and β = α^{−} then (i) (∀γ <_{L} f)[m(γ) =_{dfn} lim_{s} m(γ, s) < ∞], (ii) m(α) =_{dfn} lim_{s} m(α, s) = ∞, (iii) E_{α} ⊇ M_{α} = F_{β}^{+}, (iv) Ê_{α} ⊇ M̂_{α} = F̂_{β}^{+}, and

(v) E_{α} = E_{α}^{0} = E_{α}^{1} and Ê_{α} = Ê_{α}^{0} = Ê_{α}^{1}. However, the proof requires a slight modification. In the original, the proof of (ii)

required the proof of an additional claim: Claim 1. Every α-entry ⟨α, ν_{1}⟩ on L (⟨α, ν̂_{1}⟩ on L̂) is eventually marked.

The proof of this in the non-dual case must be modified slightly, since it is now possible for elements to leave the \overline{A}/\overline{B} game before they can enter S_{α}. We use Lemma 5.0(iii) to guarantee a supply of elements (\{x_{i}\}_{i∈ω}) that remain in \overline{A} because their Γ^{3}-tags are never removed.

Its second paragraph now reads:

Now ν_{1} ∈ M_{α} since ⟨α, ν_{1}⟩ ∈ L. Also M_{α} = F_{β}^{+}, since α ⊂ f. Hence we have the infinite collection of elements \{x_{i}\}_{i∈ω} ⊂ \overline{A} described in Lemma 5.0(iii). By the choice of s_{1} almost every such x_{i} also satisfies (1.1)–(1.7). Thus, some such x_{i} is moved to S_{α} under Step 1 at some stage s + 1 > s_{1}, and the entry ⟨α, ν_{1}⟩ is then marked, contrary to hypothesis. This establishes the claim for L.

(The proof in the dual case need not be altered, because we never enumerate any element of Ŝ_{β,s}^{1} into B.)

Lemma 5.8: The statement and proof of this lemma must be modified: Lemma 5.8. α ⊂ f ⟹

(i) R_{α,∞} =^{∗} Y_{α} ∩ \overline{A} =^{∗} Y_{λ} ∩ \overline{A} = \overline{A}; and

(ii) Y_{α} is infinite. (And similarly for the dual lemma, with B for A.)

Proof. By Lemma 5.6(i) Step 11E must eventually put every element x ∈ ω into Y_{λ}. By induction we may assume that R_{β,∞} =^{∗} Y_{β} ∩\overline{A} =^{∗} \overline{A} and Y_{β} is infinite, for β = α^{−}. By Lemma 5.7 m(α) = ∞ and m(γ) < ∞ for all γ <_{L} α with γ^{−} = β.

By Lemma 5.3, Y_{<α} =^{∗} 0. For any x that is in S_{β}^{0} at some stage and is never moved into Y_{<α} by Step 11C, x is eventually moved either into A by Step 0, or into S_{β}^{1} by Step 11D. (For the dual case, this should read “x̂ is eventually moved either into B by Step ˆ8, or into Ŝ_{β}^{1} by Step 11D.”) For any x that is in S_{β}^{1} at some stage and is never moved into Y_{<α} by Step 11C, x is eventually moved either into A by Step 0, or into S_{α} by Step 1 or Step 2. (For the dual case, this should read “x̂ is eventually moved into Ŝ_{α} by Step ˆ1 or Step ˆ2, since there is no possibility of x̂ being moved into B from Ŝ_{β}^{1}.)

Thus, almost every x ∈ R_{β} not yet in R_{α} that never enters A will eventually enter S_{α}. By Lemma 5.4(v) almost every such x will remain in R_{α} forever.

To see that Y_{α} is infinite, observe that since Y_{β} is infinite, and there are only finitely many β-states, in particular some β-state ν_{1} must be well-visited. Then by Lemma 5.0(ii), we have an infinite collection {x_{i}}_{i∈ω} of elements of ν_{1} that never enter A. By the above reasoning, almost all of these must eventually enter S_{α}.

The proof of the dual case is nearly the same, except that we make the indicated changes in the second paragraph, and the last paragraph is replaced by the following:

To see that Ŷ_{α} is infinite, observe that since Ŷ_{β} is infinite, infinitely many elements must enter Ŝ_{β} via Step ˆ1 or Step ˆ2. Elements entering Ŝ_{β} in a given β-state ν̂ by Step ˆ1 alternate between going into Ŝ_{β}^{0} and going into Ŝ_{β}^{1}, while all elements entering Ŝ_{β} by Step ˆ2 go into Ŝ_{β}^{1}. Thus, infinitely many elements must enter Ŝ_{β}^{1}. By the above reasoning, almost all of these must eventually enter Ŝ_{α}.

The proof of Lemma 5.9 must be modified somewhat, and the modifications differ slightly in the two cases:

Lemma 5.9. α ⊂ f ⟹ α is M-consistent.

Proof. Let α ⊂ f and β = α^{−}. Assume for a contradiction that α is not M-consistent. Then e_{α} > e_{β} and there exist ν_{0} ∈ M_{α}, ν_{1} ∉ M_{α}, ν_{0} <_{B} ν_{1} and ν_{1}↾ β ∈ M_{β}. By equation (42) of [6] α is a terminal node on T so S_{α} = R_{α}. Thus, by Lemma 5.4(v), for some υ_{α}, no x ∈ S_{α,s} ∩ \overline{A} later leaves S_{α}.

By Lemma 5.7 ν_{0} ∈ E_{α}. Thus, by Lemma 5.0(i), we have an infinite set {x_{i}}_{i∈ω} ⊆ \overline{A} such that

(∀i)(∃s)[x_{i} ∈ S_{α,s+1} − S_{α,s} & ν(α, x_{i}, s + 1) = ν_{0}].

Let x be any such x_{i} with the corresponding s > υ_{α}.

None of Steps 0–2 can move x at any stage t > s. Thus, Step 3_{α} must eventually apply to x at some stage t + 1 > s + 1, moving x from ν_{0} either to ν_{1}, or to some other state ν′_{1} such that ν_{0} <_{B} ν′_{1} and ν′_{1}↾β ∈ M_{β} and ν′_{1} ∉ M_{α}. Then α is provably incorrect at all stages v ≥ t + 1, so α ⊄ f.

The proof of the dual is the same, except that the second paragraph should read as follows:

By Lemma 5.7, ν̂_{0} ∈ Ê_{α}^{1}. Take any x ∈ Ŝ_{α,s+1} − Ŝ_{α,s} such that ν(α, x, s + 1) = ν_{0} and s > υ_{α}.

Lemma 5.10 is just as in [6]:

Lemma 5.10. If α ⊂ f then (i) M̂_{α} = {ν̂ : ν ∈ M_{α}}, (ii) M_{α} = F_{α} = E_{α}, and (iii) M̂_{α} = F̂_{α} = Ê_{α}.

The proof of Lemma 5.11 must be modified much as the proof of Lemma 5.9 was.

Lemma 5.11. α ⊂ f ⟹ α is R-consistent.

Proof. Assume for a contradiction that α ⊂ f and α is not R-consistent. Choose ν_{1} ∈ R_{α} such that for all ν_{2} ∈ M_{α}, ν_{1} ≮_{R} ν_{2}. By equation (42) of [6] α is a terminal node on T so S_{α} = R_{α}. Thus, by Lemma 5.4(v), for some υ_{α}, no x ∈ S_{α,s} ∩ \overline{A} later leaves S_{α}.

Now ν_{1} ∈ R_{α} ⊆ M_{α} = E_{α} by Lemma 5.10. Thus, by Lemma 5.0(i), we have an infinite set \{x_{i}\}_{i∈ω} ⊆ \overline{A} such that

(∀i)(∃s)[x_{i} ∈ S_{α,s+1} − Y_{α,s} & ν(α, x_{i}, s + 1) = ν_{1}].

Let x be any such x_{i} with the corresponding s > υ_{α}. Note that Step 0 will not apply to x at any stage t > s + 1 because x ∈ \overline{A}.

Because x ∈ S_{α,t} for all t > s + 1, neither Step 1 nor Step 2 can apply to x at any stage t > s + 1. Step 3 cannot apply to x ∈ S_{α,t} because α is M-consistent by Lemma 5.9. Furthermore, Step 5 cannot apply to x ∈ S_{α,t} while ν(α, x, t) = ν_{1} because ν_{1} ∈ R_{α} and R_{α} ∩B_{α} = ∅. But if ν(α, x, t) = ν_{1} for all t ≥ s then x witnesses that F (α^{−}, ν_{1}) fails so ν_{1} ∈ R_{α} contradicts α ⊂ f. Hence, Step 4 applies to x ∈ S_{α,t} at some stage t + 1 > s + 1 such that ν_{1} = ν(α, x, s) = ν(α, x, t), ν_{2} = ν(α, x_{i}, t + 1), and ν_{1} <_{R} ν_{2}.

Choose ν_{2} such that this happens for infinitely many x ∈ {x_{i}}_{i∈ω}. Now ν_{2} ∈ F_{α} so ν_{2} ∈ M_{α} by Lemma 5.10.

The proof of the dual requires that we change the second paragraph of this proof to the following:

Now ν̂_{1} ∈ R̂_{α} ⊆ M̂_{α} = Ê_{α} = Ê_{α}^{1} by Lemmas 5.10 and 5.7(v), so

(∃^{∞}x̂)(∃s > υ_{α})[x̂ ∈ Ŝ_{α,s+1}^{1} − Ŷ_{α,s} & ν̂(α, x̂, s + 1) = ν̂_{1}].

Take any such x̂. Note that Step ˆ8 will not apply to x̂ at any stage t > s + 1 because x̂ ∈ Ŝ_{α,t}^{1}.

Finally, we have Lemma 5.12, just as before:

Lemma 5.12. If α ⊂ f and ν_{1} ∈ B_{α} then {x : x ∈ Y_{α} & ν(α, x) = ν_{1}} =^{∗} ∅.

We now reason very much as in the proof of Lemma 5.13 in [6]: Any α ⊂ f is consistent, by Lemmas 5.9, 5.11, and their duals; thus, f is infinite. Now, take any α ⊂ f. Lemma 5.10 and its dual guarantee the correctness of the guesses M_{α} and M̂_{α}. Lemma 5.12 and its dual guarantee the correctness of B_{α} and B̂_{α}, and R_{α} and R̂_{α} are guaranteed to be correct because the (restricted) tree properties hold on our tree T below ρ, so N_{α} and N̂_{α} are also guaranteed to be correct.

Thus, just as we had that M, M̂, N, and N̂ were correct on f, and f was infinite, in [6], we now have (abandoning our superscript convention) that M\overline{A}, M̂\overline{B}, N \overline{A}, and N̂ \overline{B} are correct on f, and f is infinite.

1.3.3 Verifying that G^{A} = Ĝ^{B}

It suffices to verify two lemmas:

Lemma 1.3.4 For any node α and α-state ν_{1}, L^{G} contains infinitely many pairs ⟨α, ν̂_{1}⟩ if and only if ν_{1} ∈ G_{α}^{A}.

Proof. Such a pair is added to L^{G} exactly when Step 0 enumerates some x ∈ ν_{1} into A. Thus, L^{G} contains infinitely many such pairs if and only if infinitely many x ∈ ν_{1} are enumerated into A; that is, if and only if ν_{1} ∈ G^{A}.

Lemma 1.3.5 For any node α ⊂ f and α-state ν_{1}, L^{G} contains infinitely many pairs ⟨α, ν̂_{1}⟩ if and only if ν̂_{1} ∈ Ĝ^{B}.

The proof of 1.3.5 will require the following additional lemma:

Lemma 1.3.6 For any pair ⟨α, ν̂_{1}⟩ on list L^{G}, if ⟨α, ν̂_{1}⟩ is not eventually marked by Step ˆ8 then only finitely many elements x are enumerated into J_{ν,i}^{α} by Step ˆ8.

Proof. [1.3.6] Suppose that this is not the case for some ⟨α, ν̂⟩. Then J_{ν,i}^{α} = W_{j_{ν,i}^{α}} is an infinite c.e. set. Hence, by promptness of C, for some x̂ and t we have that x̂ ∈ W_{j_{ν,i}^{α}, at t} and C_{t}↾ x̂ ≠ C_{p(t)}↾ x̂. But then ⟨α, ν̂⟩ must be marked by (ˆ8.2) when x̂ enters J_{ν,i}^{α} at some stage s < t.

Proof. [1.3.5] To show the “if” part of this statement, we observe that

1. We do not move any element x̂ in α-state ν̂_{1} into B except when required to by some pair ⟨γ, ν̂′_{1}⟩ in L^{G} with α ⊆ γ and ν̂_{1} = ν̂′_{1}↾α, and that

2. If there are infinitely many such pairs in L^{G} then there are infinitely many pairs ⟨α, ν̂_{1}⟩ in L^{G}, since whenever we add one of the former we also add one of the latter.

To show the “only if” part, suppose that for our given α and ν_{1}, L^{G} contains infinitely many pairs ⟨α, ν̂_{1}⟩. We will show that all of these pairs are eventually marked by (ˆ8.2), and that therefore infinitely many elements x̂ in state ν̂ are put by (ˆ8.2) into B, i.e. that ν ∈ Ĝ^{B}.

Suppose that this is not the case, and take the first pair ⟨α, ν_{1}⟩ that never gets marked. By some stage s,

1. Every pair in L^{G} before that pair that will ever be marked already has been, and

2. For any ⟨α′, ν̂′⟩ before ⟨α, ν̂_{1}⟩ that will never be marked, all of the (by Lemma 1.3.6) finitely many x̂ that will ever be enumerated into J_{ν′,i′}^{α′} by (ˆ8.1) have been.

Now, since ν_{1} ∈ G^{A} ⊆ M\overline{A} and thus ν̂_{1} ∈ M̂\overline{B} = Ê^{0,\overline{B}}, we have that for infinitely many stages t + 1 > s, some x̂ is enumerated into Ŝ_{α,t+1}^{0,\overline{B}} by Step ˆ1. Neither Step ˆ1 nor Step ˆ2 can apply to x̂ while it remains in Ŝ_{α}^{0,\overline{B}}, and since α is M̂-consistent (by Lemma 5.ˆ9) Step ˆ3 cannot apply to x̂ either. Hence eventually each such element, still in ν̂_{1}, is enumerated into J_{ν,i}^{α} by ˆ8.2. But then by Lemma 1.3.6 ⟨α, ν̂_{1}⟩ is eventually marked, and we have a contradiction.

1.3.4 Tree Properties (Unrestricted Version)

We proceed as in §1.3.1, showing that the tree properties of §1.2.2 hold for the α = ρ case, from which the rest follow automatically. The first was shown in §1.3.1:

Lemma 1.3.1. M_{ρ} = F_{λ}^{+}.

We now show the other two:

Lemma 1.3.7 M̂_{ρ} = F_{λ}^{+}.

Proof. Since A is infinite, G_{ρ} ≠ ∅, so Ĝ_{ρ} ≠ ∅, so B is infinite. Thus, since infinitely many elements x̂ of Ŷ_{λ} enter B = Û_{ρ}, ⟨ρ_{1}, {0}, ∅⟩ ∈ F̂_{λ}^{+}, so F̂_{λ}^{+,B} = {⟨ρ_{1}, {0}, ∅⟩} = M̂_{ρ_{1}}^{B} = M̂_{ρ}^{B}. By Lemma 1.3.2, we also have that M̂\overline{B} ; ρ = F̂_{ρ}^{+,\overline{B}}; together, these two results prove our lemma.

Lemma 1.3.8 k_{ρ} = 0 is a correct guess.

Proof. Since both ρ-states are well-visited on both the ω and ω̂ sides (by the above two lemmas), there are no elements of ω or ω̂ remaining permanently in a non-well-resided ρ-state (there being no such state), so 0 is indeed the correct upper bound for the set of such elements.

1.3.5 Verifying that B ≤_{T} C

For any x̂, if x̂ ∈ B then x̂ must enter B_{s+1} at some stage s + 1 by Step ˆ8.2. Then for some α, ν, and i, x̂ enters J_{ν,i}^{α} at stage s+1 and enters W_{j_{ν,i}^{α}} at some stage t+1 > s+1 such that C_{t+1}↾ x̂ ≠ C_{p(t+1)}↾ x̂. Thus, given C, to determine if x̂ ∈ B we need only find a stage t + 1 such that C_{t+1}↾ x̂ = C↾ x̂; we then have that x̂ ∈ B if and only if x̂ ∈ B_{t}.

1.4 Proof of Theorem 1.1.11

We wish to prove the following:

Theorem 1.1.11. If A is low (or has semilow complement) and p.s. and C is p.s., then (∃B ≡_{T} C)[A ≃ B].

One way to do this employs Maass’s Theorem 1.1.5, and also the following easy fact, which we prove in this section (after proving it we discovered it to have been previously known to Cholak and perhaps others):

Theorem 1.4.1 For any p.s. set C, there exists a p.s. set B with semilow complement such that B ≡_{T} C.

This gives us Theorem 1.1.11 as a corollary:

Proof. [Theorem 1.1.11.] Take any p.s. set A with semilow complement and any p.s. set C. By Theorem 1.4.1, we can find B ≡_{T} C such that B is p.s. and has semilow complement. Then by Theorem 1.1.5, A ≃ B.

(A more direct proof of Theorem 1.1.11, not employing Theorem 1.1.5 or Theorem 1.4.1, might also be constructed. Briefly sketched, this involves combining the construction used in the proof of Theorem 1.1.6 with a step assigning coding markers permanently to α-witnesses, coding elements chosen from Ŝ_{α}^{0,\overline{B}} to be enumerated into B_{s+1} if |α| = n ∈ C_{s+1}. The verifications that f is infinite and that M\overline{A}, M̂\overline{B}, N \overline{A}, and N̂ \overline{B} are correct guesses proceed approximately as before. The enumeration of αwitnesses into B might seem to raise a potential problem for the proof that G^{A} = Ĝ^{B} by requiring states to exist in Ĝ^{B} that are not matched in G^{A}; this turns out not to be the case, however, because the prompt simplicity of A requires G^{A} to equal all of M\overline{A}, for reasons that will be discussed in §2.5.4. We still have B ≤_{T} C because every element entering B is either permitted by an element of C, as before, or is an α-witness coding an element of C. Finally, the coding guarantees that C ≤_{T} B.)

Theorem 1.4.1 has another corollary, incidentally, which was pointed out by Cholak:

Corollary 1.4.2 (Cholak) For any two prompt degrees a and b, there exist A ∈ a and B ∈ b such that A ≃ B.

Proof. By Theorem 1.4.1 we can find A ∈ a and B ∈ b such that A and B are both p.s. with semilow complement. Then by Theorem 1.1.5, A ≃ B.

We now prove Theorem 1.4.1:

Proof. [Theorem 1.4.1.]

Take any p.s. set C. Fix some enumeration {C_{s}} of C. Then by the Promptly Simple Degree Theorem ([14], p. 284) there exists some computable function p such that for all s, p(s) ≥ s, and for all e

|W_{e}| = ∞ ⟹ (∃x)(∃s)[x ∈ W_{e, at s} & C_{s}↾x ≠ C_{p(s)}↾x].

We now construct B as follows:

Write ω as the disjoint union of finite sets H_{0}, H_{1}, H_{2}, ..., where each H_{n} contains 2n + 1 elements. These will be our coding sets; if n enters C, we will encode this fact in B by enumerating at least one element of H_{n} into B. We will in this way guarantee that C ≤_{T} B.

We also have the following sets of requirements that our construction will fulfill:

N_{e} : |W_{e} \ B| = ∞ ⟹ W_{e} ∩ \overline{B} ≠ ∅

(where by “W_{e}\B” we mean the elements that either are in W_{e}−B or are enumerated into W_{e} before being enumerated into B), and

P_{e} : |W_{e}| = ∞ ⟹ (∃x)(∃s)[x ∈ W_{e, at s} ∩ B_{s}].

Fulfilling all the negative requirements N_{e} will guarantee that B is semilow; fulfilling all the positive requirements P_{e} will guarantee that B is p.s. (with its promptness function being the identity function). We order these requirements in a priority list P_{0}, N_{0}, P_{1}, N_{1}, P_{2}, ...; to fulfill one requirement we are only allowed to injure requirements of lower priority. (In this construction, in fact, only positive requirements are ever injured.)

We also define the sequence of markers Λ_{e,s}. In order to fulfill the requirement N_{e}, we may at stage s + 1 put Λ_{e,s+1} on some element x of W_{e,s+1} − B_{s} − ⋃_{i≤e} E_{i}, and attempt to prohibit x from ever entering B. This prohibition may be injured in order to fulfill P_{i} for some i ≤ e, forcing Λ_{e} to be removed from x. However, if W_{e} \ B is indeed infinite, then eventually some Λ_{e}-prohibition is permanent, and the requirement P_{e} is fulfilled.

Our construction will also be enumerating, for each e, a c.e. set E_{e}. By the Slowdown Lemma [14, p. 284] there exists a computable function h such that E_{e} = W_{h(e)} for all e, and any element enumerated in E_{e} appears strictly later in W_{h(e)}. We may assume, by the Recursion Theorem, that we have this function available for our construction. We also define the speed-up function g(e, s) such that for any e, for any stage s,

x ∈ E_{e,s+1} − E_{e,s} ⟺ x ∈ W_{h(e),g(e,s)+1} − W_{h(e),g(e,s)}.

(Thus g(e, s) > s for all e, s.) These will be used, in conjunction with the p.s. property of C, to find elements of W_{e} that have permission from C to enter B, with which we can fulfill the requirement P_{e} while still keeping B ≤_{T} C.

Finally, in our construction we adopt the usual convention that at any stage s, there exists at most one e such that W_{e,s+1} ≠ W_{e,s}, and in that case |W_{e,s+1}−W_{e,s}| = 1. Construction. Stage s = 0. Let B_{0} = ∅. For all e, let Λ_{e,0} = −1, and E_{e,0} = ∅. Stage s + 1. (In the following, any item not otherwise specified remains the same at stage s + 1 as at stage s.) Step 1 (Fulfilling positive and negative requirements). If there exist x and e such that x ∈ W_{e,s+1} − W_{e,s}, x ∉ ⋃_{j≤e}H_{j}, and x ∉ {Λ_{j,s}}_{j<e}, then Substep 1.1. If requirement P_{e} has not yet been acted on, then

(a) If x ∈ B_{s}, then mark requirement N_{e} as having been acted on, and end Step 1.

(b) Let E_{e,s+1} = E_{e,s} ∪ {x}.

(c) If C_{g(e,s)+1}↾x ≠ C_{p(g(e,s)+1)}↾x, then (i) Enumerate x into B; (ii) If Λ_{j,s} = x for some j ≥ e, then set Λ_{j,s+1} = −1; (iii) Mark requirement P_{e} as having been acted on; and (iv) End Step 1.

Substep 1.2. If Λ_{e,s} = −1, then set Λ_{e,s+1} = x.

Step 2 (Coding). If e ∈ C_{s+1} − C_{s}, enumerate into B every element of H_{e} ∩ \overline{B}_{s} with no attached Λ-marker.

(End of Construction.)

Verification. We must verify the following three lemmas:

Lemma 1.4.3 B is promptly simple and semilow.

Proof. It suffices to verify by induction that the following hold for all e:

(a) P_{e} is satisfied.

(b) Λ_{e} =_{dfn} lim_{s} Λ_{e,s} converges.

(c) N_{e} is satisfied.

(a) Suppose for a contradiction that P_{e} is not satisfied. Then W_{e} is infinite. Also, P_{e} is never marked as having been acted on, for it can only be so marked, by Substep 1.1(a) or (c), if there is some element x in both W_{e,s+1} − W_{e,s} and B_{s+1}. Let s_{0} be some stage such that for all i < e, Λ_{i} = Λ_{i,s_{0}}. Since {Λ_{i}}_{i<e} ∪ ⋃_{i≤e} H_{i} is finite, at infinitely many stages t > s_{0} an element x of W_{e,t+1} − W_{e,t} causes Substep 1.1 to be performed. No such x is in B_{t}, for this would satisfy P_{e}, so each such x is enumerated into E_{e} by Substep 1.1(b). Thus, E_{e} = W_{h(e)} is infinite. But then for some x, s, x ∈ W_{h(e), at s} and C_{s}↾x ≠ C_{p(s)}↾x, and by definition of g this s must equal g(t′) + 1 for some t′ such that x ∈ E_{t′+1} − E_{t′}. But then x must enter B by Substep 1.1(c) at stage t′ + 1, so P_{e} is satisfied.

(b) Let t be a stage at which every P_{i} with i ≤ e that will ever be acted on already has been. Then for any t′ ≥ t, if Λ_{e,t′} ≠ −1 then Λ_{e,t′+1} = Λ_{e,t′}. Thus, either (i) (∀t′ ≥ t)[Λ_{e,t′} = Λ_{e,t} ≠ −1],

(ii) (∀t′ ≥ t)[Λ_{e,t′} = Λ_{e,t} = −1], or

(iii) Λ_{e,t} = −1 and Λ_{e,t_{0}+1} ≠ Λ_{e,t_{0}} = Λ_{e,t} = −1 for some t_{0} ≥ t.

In cases (i) and (ii), Λ_{e} = Λ_{e,t}; in case (iii), Λ_{e,t′} = Λ_{e,t_{0}+1} for all t′ > t_{0} and therefore Λ_{e} = Λ_{e,t_{0}+1}.

(c) Suppose that W_{e} is infinite, and take t as above. Take any t′ ≥ t such that there exists an x ∈ W_{e,t′+1} − W_{e,t′}; then if Λ_{e,t′} = −1, Λ_{e,t′+1} = x by Substep 1.2. Thus, case (ii) above cannot hold.

Let s = t_{0} if case (iii) holds, and if case (i) holds let s < t′ be the earliest stage s such that Λ_{e,t′} = Λ_{e,s+1} for all t′ > s. Then Λ_{e,s} ≠ Λ_{e,s+1} ≠ −1, so Substep 1.2 must act on some x ∈ W_{e,s+1} − W_{e,s} at Stage s + 1. Then x ∉ B_{s}. Moreover, Substep 1.1 does not put x into any B_{t′+1} with t′ ≥ s (for then Λ_{e,t′+1} would equal −1), and neither does Step 2 (since x has a permanently attached Λ-marker). Hence x ∉ B, and thus x satisfies P_{e}.

Lemma 1.4.4 B ≤_{T} C.

Proof. For any x, we can determine from C if x ∈ B as follows:

1. Find t such that C_{t}↾ x = C↾ x. Then at any stage t′ ≥ t, for any i, g(i, t′) > t, so C_{g(i,t′)}↾x = C↾x and therefore x cannot enter B by Step 1.1.

2. Find e such that x ∈ H_{e}. If e ∈ C, find s such that e ∈ C_{s+1} − C_{s}; then x can only enter B by Step 2 at stage s + 1. If e ∉ C, x can never enter B by Step 2; set s = 0. Thus either way x cannot enter B at any stage t′ > s + 1.

Then x ∈ B if and only if x ∈ B_{max{t,s+1}}.

Lemma 1.4.5 C ≤_{T} B.

Proof. For any e, we can determine from B if e ∈ C as follows: Find a stage s such that B_{s} ∩ H_{e} = B ∩ H_{e}. We claim that e ∈ C if and only if e ∈ C_{s}. To show the “only if” part of this statement, suppose that e ∈ C, and let t + 1 be the stage at which e enters C.

Substep 1.1 can only move an element of H_{e} into B in acting on requirement P_{i} for some i < e; thus, at most e elements can be moved in this way. The only Λ-markers that can be assigned to elements of H_{e} by Substep 1.2 are the e markers Λ_{0,s}, ..., Λ_{e−1,s}. Thus, at any stage at most 2e of the 2e + 1 elements of B_{e} are either marked or in B.

In particular, then, at stage t+1 Step 2 has at least one element of H_{e} to enumerate into B, so B_{t+1} ∩ H_{e} ≠ B_{t} ∩ H_{e}. Thus, t + 1 ≤ s, so e ∈ C_{s}.

CHAPTER 2 NONINVARIANCE

2.1 Introduction

Another topic arising from the study of E-automorphisms is the question of invariance of properties of the c.e. sets. That is, for any given property P (A) of sets in E, we may ask whether P (A) is invariant under Aut(E). For instance, computability is an invariant property; this can be seen by observing that a c.e. set A in E is computable if and only if E also contains A’s complement, so that the property of computability is definable purely in terms of the lattice E. (Indeed, any property which is E-definable must also be invariant, and many properties have been proved invariant by showing that they are E-definable.) On the other hand, completeness turns out to be wildly noninvariant; Harrington and Soare have shown [6] that any c.e. set in any prompt degree is automorphic to some set in 0′.

In particular, we can consider the notion of creativity. A set A is said to be creative if there exists a computable function f such that

(∀e)[W_{e} ⊆ \overline{A} ⟹ f(e) ∈ \overline{A} − W_{e}].

This notion was introduced by Post in 1944, as part of his program to find an incomplete noncomputable c.e. set; the creative sets, however, turned out all to be complete, and in fact the creative sets are exactly the m-complete sets. Ever since that time, creative sets have played an important role in computability theory.

In 1967 Rogers [10, p. 228] raised the question of whether creativity is invariant, and with the development in the 1970s of machinery for generating automorphisms, considerable effort was expended in the attempt to show that it is not. The question was finally settled in the mid-1980s in a surprising way, when Harrington [14, p. 339] make the remarkable discovery of an E-definable property exactly characterizing creative sets, thus showing that creativity was indeed invariant.

This in turn raises the question of whether other, similar properties might be invariant. In 1957 Shoenfield [11] introduced the notion of quasicreativity (see also [14, p. 88]). A set A is said to be quasicreative (or q-creative) if there exists a computable function f such that

(∀e)[W_{e} ⊆ \overline{A} ⟹ D_{f(e)} ⊂ \overline{A} & D_{f(e)} ⊈ W_{e}]

(where {D_{e}}_{e∈ω} is an effective indexing of the finite sets). Quasicreativity is similar to creativity in many ways. For instance, quasicreativity guarantees completeness just as creativity does. Also, just as the creative sets are exactly the m-complete sets, the q-creative sets are exactly the q-complete sets (as defined by Shoenfield).

However, unlike creativity, q-creativity is not invariant. In §2.3 we prove the following theorem:

Theorem 2.1.1 There exist a quasicreative set A and a nonquasicreative low set B such that A ≃ B. (Hence quasicreativity is non-invariant.)

Another related set of properties arises from the consideration of the differences between creativity and q-creativity. If A is creative, then for any W_{e} in \overline{A} we can effectively find a single element of \overline{A} not contained in W_{e}. If A is quasicreative, then for any W_{e} in \overline{A} we can effectively find a finite set (of some arbitrary size) of elements of \overline{A} that is not entirely contained in W_{e}. Suppose, then, that we consider a notion in between, in which what we effectively find is a finite set with some particular bound on its size.

We thus introduce, for every n, the property of n-creativity. A set A is said to be n-creative if there exists a computable function f such that

(∀e)[W_{e} ⊆ \overline{A} ⟹ (|D_{f(e)}| ≤ n & D_{f(e)} ⊂ \overline{A} & D_{f(e)} ⊈ W_{e})].

We have thereby introduced infinitely many different properties. In §2.2.2 we show that they are indeed all distinct, by proving the following theorem:

Theorem 2.1.2 For any n, m, if n < m then there exists a c.e. set A that is mcreative but not n-creative.

We thus have a chain of proper implications

Creative = 1-creative \overrightarrow{⇍} 2-creative \overrightarrow{⇍} 3-creative \overrightarrow{⇍} 4-creative ...

In addition, while n-creativity implies q-creativity for any n, we will also show, in §2.2.3, that the q-creative sets are not just the union of the n-creative sets over all n ∈ ω:

Theorem 2.1.3 There exists a c.e. set A such that

1. A is quasicreative, and

2. A is not n-creative for any n.

We may then ask whether n-creativity is invariant. The 1-creative sets are exactly the creative sets, so 1-creativity is certainly invariant. However, it turns out that this is not true for any other value of n. In §2.3 we prove:

Theorem 2.1.4 For all n ≥ 2, there exist an n-creative set A and a non-n-creative low set B such that A ≃ B. (Hence n-creativity is noninvariant for all n ≥ 2.)

Another notion related to creativity is subcreativity. A c.e. set A is said to be subcreative if there exists a computable function h such that

(∀e)[|W_{e} ∩ A| < ∞ ⟹ A ⊂ W_{h(e)} ⊆ A ∪ \overline{W}_{e}].

This notion was introduced by Blum in 1973 [1], and has applications to complexity theory. As with creative sets, q-creative sets, and n-creative sets, all subcreative sets are complete. And as with all but the first, we show (in §2.4) that subcreativity is noninvariant:

Theorem 2.1.5 There exist a subcreative set B and a nonsubcreative low set A such that A ≃ B. (Hence subcreativity is noninvariant.)

One final property we consider arises from the consideration of the orbits of simple sets. In 1996, Cholak [3] answered a question of Herrmann by showing that every simple set is automorphic to some hypersimple set, and indeed every simple set is automorphic to some dense simple set. It is reasonable to examine other notions of simplicity in this connection. For example, there is the notion of an effectively simple set, which arose (like the notion of a creative set) from Post’s seminal 1944 paper [8]. We may ask whether every simple set is automorphic to some effectively simple set. This turns out not to be the case; Harrington and Soare [5] exhibited a simple set that was not automorphic to any complete set, and (as with creative sets) all effectively simple sets are complete.

Jockusch then raised the following question: If we replace simplicity with the stronger property of prompt simplicity, does this additional power enable us to get the desired result? We show in §2.5 that it does.

Theorem 2.1.6 For any promptly simple set A there exists an effectively simple set B such that A ≃ B.

This gives us, as a corollary, one final noninvariance result:

Corollary 2.1.7 Effective simplicity is noninvariant.

Proof. Take any low promptly simple set A, and construct B as in Theorem 2.1.6. Then A ≃ B, A is incomplete and therefore not effectively simple, and B is effectively simple.

2.2 Distinctness of n-creativity Notions

2.2.1 Another Definition of n-creative

We shall find it useful for our exposition to have another, equivalent, definition of n-creativity:

Theorem 2.2.1 The following are equivalent:

(a) (∃ comp f)(∀e)[W_{e} ⊆ \overline{A} ⟹ (|D_{f(e)}| ≤ n & D_{f(e)} ⊂ \overline{A} & D_{f(e)} ⊈ W_{e})]

(that is, A is n-creative).

(b) (∃ comp f)(∀e)[W_{e} ⊆ \overline{A} ⟹ (|D_{f(e)}| = n & D_{f(e)} ⊂ \overline{A} & D_{f(e)} ⊈ W_{e})].

Proof. Clearly, (b) implies (a). Now, suppose that (a) holds for some A. Since A is ncreative, and therefore noncomputable, \overline{A} is infinite. Select n elements \{y_{1}, y_{2}, ..., y_{n}\} in \overline{A}. Then for any i, define the computable function p by

p(i) = \{ \begin{matrix}(μk)[|D_{i} ∪ \{y_{j}\}_{j=1}^{k}| = n] & if |D_{i}| ≤ n, \\ 0 & otherwise. \end{matrix}

Let f be a computable function by which A satisfies (a), and define the computable function f′ so that for all i,

D_{f′(i)} = D_{f(i)} ∪ {y_{j}}_{j=1}^{p(f(i))}.

Then A satisfies (b) by f′.

2.2.2 Proof of Theorem 2.1.2

We now prove Theorem 2.1.2. For any n, m, if n < m then there exists a c.e. set A that is m-creative but not n-creative.

Proof. Given n < m, we will be constructing a c.e. set A that is m-creative but not n-creative. To guarantee the former, our construction will enumerate elements into A in order to satisfy all of the positive requirements

P_{e} : W_{e} ⊆ \overline{A} ⟹ [D_{g(e)} ⊂ \overline{A} & D_{g(e)} ⊈ W_{e}],

where g is a computable function such that

D_{g(e)} = {me, me + 1, me + 2, ..., me + (m − 1)}

(so that |D_{g(e)}| = m for all e).

To guarantee the latter, our construction will satisfy all of the negative requirements

N_{e} :  (∃y)[W_{y} ⊆ \overline{A} &
(0) (φ_{e}(y)↑ ∨ |D_{φ_{e}(y)}| ≠ n ∨ D_{φ_{e}(y)} ⊈ \overline{A} ∨
(1)  D_{φ_{e}(y)} ⊆ W_{y})].

That is, we will attempt to show that for no e can φ_{e} serve as the computable function f in the alternative definition of n-creativity given in §2.2.1. In order to meet the requirement N_{e}, we will use the Recursion Theorem to find some y for which either clause (0) or clause (1) holds. If clause (0) holds, W_{y} will be the empty set, and no action need be taken to guarantee that W_{y} ⊆ \overline{A}. If it appears that clause (1) holds, then W_{y} will equal D_{φ_{e}(y)}, and we must attempt to restrain the elements of W_{y} from entering \overline{A}. A restraint may be injured finitely often, under the following circumstances:

1. When we are called upon to meet some positive requirement P_{i} by putting an element of D_{g(i)} into A, it may be that every possible choice would violate some existing restraint. In this case, we preserve the restraint with highest priority, and may injure any or all of the others.

2. Whenever a new restraint added in order to meet some N_{i}, all existing restraints for N_{e}, e > i, are considered to be injured.

We need the following machinery for this construction:

1. We have two recursive functions a(e) and n(e) defined so that the negative requirement N_{e}, if satisfied, will guarantee that A is not n(e)-creative via function φ_{a(e)}. For the present construction, a(e) = e and n(e) = n for all e. In the next section, in the proof of Theorem 2.1.3, the definition of our negative requirements will be slightly different, and a(e) and n(e) will be defined so that e = ⟨a(e), n(e)⟩ for all e.

2. At every stage s, we have the function p_{s}. For any e, p_{s}(e) is the value of y that is being used at stage s to attempt to guarantee N_{e}.

3. At every stage s we have the binary function f_{s}. For any e, f_{s}(e) equals 0 if we are attempting to satisfy clause (0) of N_{e}, 1 if we are attempting to satisfy clause (1). If f_{s}(e) = 0, then we take no action to restrain any element of W_{p_{s}(e)} from entering A, for W_{p_{s}(e)} currently appears to be ∅. If f_{s}(e) = 1, then W_{p_{s}(e)} equals the n-element set D_{φ_{a(e)}(p_{s}(e))}, and we must attempt to restrain all n of those elements from entering A.

Each p_{s}(e) and f_{s}(e) eventually achieves a permanent value. We denote lim_{s} p_{s} by p and lim_{s} f_{s} by f.

We may now proceed to describe our construction. There will be two additional complexities in our exposition:

1. If an injury occurs at level e at some stage s + 1, for every i ≥ e we set f_{s+1}(i) to 0, but determining what value p_{s+1}(i) will take requires a more involved calculation. For ease of explanation, then, we describe this p-initializing procedure (which is also used to start off our overall construction) separately from the main part of the construction.

2. When we are choosing a new value of p_{s+1}(e) at some stage s+1, we must choose it so that if there is no future injury at level e, W_{p(e)} will equal ∅ if clause (0) holds throughout the rest of our construction, and D_{φ_{a(e)}(p(e))} otherwise. This requires that we be able to speak of a hypothetical continuation of our construction, whose “program code” is used as part of a calculation for p_{s+1}(e) by the Recursion Theorem. In order to avoid confusing this continuation with the real construction, the names A′, f′, and p′ are used for its machinery. This means that both the main part and the p-initalization procedure of our construction must be described in more generality than usual. We must be able to start at any given starting state s_{0} + 1 (so that the same description can be used for a hypothetical continuation that starts at state s_{0} + 1), and we must be able to perform a portion of the construction “with regard to” either A, f, and p or A′, f′, and p′. Then to start everything off, we just initialize everything and perform “the main part of the construction at stage 1, with regard to A, f, and p,” and the A thus constructed is the A we want.

Construction.

p-Initialization. To p-initialize from e at stage s with regard to A, f, and p, we proceed inductively on all i ≥ e. For each i in turn:

1. Define the computable function h_{i} so that for every j, h_{i}(j) is an index of the c.e. set U defined by the following procedure:

(a) Let A′_{s} = A_{s} and f′_{s} = f_{s}.

(b) Define p′_{s} by setting p′_{s}↾i = p_{s}↾i and p′_{s}(i) = j, and p-initializing from i + 1 at stage s with regard to A′, f′, and p′.

(c) Perform the main part of the construction at stage s + 1 with regard to A′, f′, and p′ until the first stage t + 1 such that

(a) N_{i} is injured at stage t + 1, or

(b) f′_{t+1}(i) = 1.

(d) In case (a), let U = ∅. In case (b), where t + 1 = 2q + 2 we have that φ_{a(e),q+1}(j) ↓ = some k; let U = D_{k}. (And if no such t + 1 is ever found, nothing is ever enumerated into U, so U = ∅.)

2. Set p_{s+1}(i) equal to a fixed point of h_{i} (found by the Recursion Theorem).

Main Part of the Construction. To perform the main part of the construction at stage s_{0} with regard to A, f, and p, perform the following procedure for all stages s + 1 starting with s_{0}:

Stage s + 1 = 2q + 1 (Changing strategies for guaranteeing N_{e}). If φ_{a(e),q}(p_{s}(e)) ↑, φ_{a(e),q+1}(p_{s}(e))↓ = k, |D_{k}| = n(e), and D_{k} ⊆ \overline{A}_{s}, then

1. Set f_{s+1}(e) = 1,

2. For all i > e, mark N_{i} as injured at stage s + 1.

3. For all i > e, set f_{s+1}(i) = 0.

4. p-Initialize from e + 1 at stage s + 1 with regard to A, f, and p. Stage s + 1 = 2q + 2 (Guaranteeing P_{e}). If D_{g(e)} ⊆ \overline{A}_{s}, D_{g(e)} ⊈ W_{e,q}, and D_{g(e)} ⊆ W_{e,q+1}, then

1. If there exists some

x ∈ D_{g(e)} − ⋃{D_{φ_{a(i),q+1}(p_{s}(i))} : φ_{a(i),q+1}(p_{s}(i))↓ & f_{2q+1}(i) = 1}, then enumerate the least such x into A_{s+1}, and end Stage 2q + 2.

2. Otherwise, let j = (μi)[φ_{a(i),q+1}(p_{s}(i))↓ & f_{2q+1}(i) = 1 & D_{g(e)} ∩ D_{φ_{a(i),q+1}(p_{s}(i))} ≠ ∅].

3. If there is some x in D_{g(e)} − D_{φ_{a(j),q+1}(p_{s}(j))}, then (a) Enumerate the least such x into A_{s+1}.

(b) For all i > j, mark N_{i} as injured at stage s + 1.

(c) For all i > j, set f_{s+1}(i) = 0.

(d) p-Initialize from j + 1 at stage s + 1 with regard to A, f, and p.

(e) End Stage 2q + 2.

4. Otherwise (Note: this never happens in the construction for Theorem 2.1.2, but it may in the construction for Theorem 2.1.3):

(a) Enumerate the least element of D_{g(e)} into A_{s+1}

(b) For all i ≥ j, mark N_{i} as injured at stage s + 1.

(c) For all i ≥ j, set f_{s+1}(i) = 0.

(d) p-Initialize from j at stage s + 1 with regard to A, f, and p.

(e) End Stage 2q + 2.

Overall Construction of A.

1. Let A_{0} = ∅.

2. For all e, let f_{0}(e) = 0.

3. p-initialize from 0 at stage 0 with regard to A, f, and p.

4. Perform the main part of the construction at stage 1 with regard to A, f, and p. The resulting A is the non-m-creative, n-creative set we are attempting to construct.

(End of Construction.)

Verification. We must verify the following two lemmas:

Lemma 2.2.2 Every P_{e} is satisfied.

Proof. Take any e. If D_{g(e)} ⊈ W_{e}, then no element of D_{g(e)} is ever put into A at any stage 2q+2, so D_{g(e)} ⊂ \overline{A}. If D_{g(e)} ⊆ W_{e}, then for the least q such that D_{g(e)} ⊆ W_{e,q+1}, an element of D_{g(e)} is put into A at stage 2q + 2, so W_{e} ⊈ \overline{A}. So either way P_{e} is satisfied.

Lemma 2.2.3 Every N_{e} is satisfied.

Proof. We will prove by induction that the following hold for every e:

1. N_{e} is marked as injured only finitely many times.

2. f(e) =_{dfn} lim_{s} f_{s}(e)↓.

3. p(e) =_{dfn} lim_{s} p_{s}(e)↓.

4. N_{e} is satisfied.

Take any e and assume that the above hold true for all i < e. Let t be a state by which, for all i < e,

(a) N_{i} will never again be marked as injured,

(b) f(i) and p(i) have converged, and

(c) φ_{a(i)}(p(i)) has converged if it ever will.

Then by (b) neither f_{s}(e) nor p_{s}(e) can change, nor can N_{e} be marked as injured, at any stage 2q + 1 > t.

Now, take r so that for every i < e such that φ_{a(i)}(p(i)) converges, D_{φ_{a(i)}(p(i))} ⊆ ⋃_{z<r} D_{g(z)}. Take t′ > t such that A_{t} ∩ ⋃_{z<r} D_{g(z)} = A ∩ ⋃_{z<r} D_{g(z)}. Suppose that at some stage 2q + 2 > t′, an element x enters A from some D_{g(z)}. Then z ≥ r, so D_{g(z)} ∩ D_{φ_{i}(p(i))} = ∅ for all i < e, so if x enters A by clause 3 or 4 then j ≥ e. Thus,

(i) If x enters A by clause 3, N_{e} is not marked as injured at stage 2q+2, f_{2q+2}(e) = f_{2q+1}(e), and p_{2q+2}(e) = p_{2q+1}(e).

(ii) If x enters A by clause 4, then j ≠ e, for if j = e then |D_{φ_{a(e),q+1}(p_{2q+1}(e))↓} | = n(e) = n, and so D_{g(z)} − D_{φ_{a(e),q+1}(p_{2q+1}(e))} ≠ ∅ because |D_{g(z)}| = m > n. Hence j > e, so again N_{e} is not marked as injured at stage 2q+2, f_{2q+2}(e) = f_{2q+1}(e), and p_{2q+2}(e) = p_{2q+1}(e).

(iii) If x enters A by clause 1, then no negative requirements are marked as injured and neither f nor p changes.

Hence by stage t′ > t, N_{e} will never again be injured (at any stage > t′, whether of the form 2q +1 or 2q +2) and f(e) and p(e) have converged, so the first three parts of our statement are proved.

To show (d), let s be 0 if N_{e} is never injured, or the last stage at which N_{e} is injured otherwise. Then f_{s}(e) = 0, and p_{s}(e) is some fixed point of g_{e} as described in the p-initialization procedure. Let j = p_{s}(e); then W_{j} = W_{h_{e}(j)}. Now, W_{h_{e}(j)} is determined by the results of running the main part of the construction at s + 1 on A′_{s} = A_{s}, f′_{s} = f_{s}, and p′_{s} defined by setting p′_{s}↾ e = p_{s}↾ e, p′_{s}(e) = j = p_{s}(e), and running the p-initialization procedure from e + 1 at stage s with regard to p′, f′, and A′. Since p_{s}(i) for all i > e will in fact be determined by running the p-initialization procedure from e + 1 at stage s with regard to p, f and A, and the real construction will then procede by running the main part of the construction at s + 1 on A_{s}, f_{s}, and p_{s}, these results will be the same as those of the real construction.

In the real construction, N_{e} will never again be injured. Thus, W_{j} = W_{h_{e}(j)} =

(a) D_{φ_{a(e),2q+1}(j)↓} if at some subsequent stage 2q + 1 f_{2q+1}(e) becomes 1, and

(b) W_{j} = W_{h_{e}(j)} = ∅ otherwise.

In case (a), D_{φ_{a(e)}(j)} ⊆ \overline{A}_{2q+1}, and no element of W_{j} = D_{φ_{a(e)}(j)} will ever enter A because N_{e} will never again be injured. Thus, D_{φ_{a(e)}(j)} ⊆ W_{j} ⊆ \overline{A}, and requirement N_{e} is indeed satisfied, via clause (1).

In case (b), f_{2q+1}(e) never becomes 1 at any subsequent stage 2q + 1. Thus, either φ_{a(e)}(j) ↑, or |D_{φ_{a(e)}(j)}| ≠ n(e), or at every stage 2q′ + 1 after φ_{a(e)}(j) converges D_{φ_{a(e)}(j)} ⊈ \overline{A}_{2q′+1} and therefore D_{φ_{a(e)}(j)} ⊈ \overline{A}. Thus, clause (0) of N_{e} must hold, and since W_{j} = ∅ ⊆ \overline{A}, N_{e} is satisfied.

2.2.3 Proof of Theorem 2.1.3

The proof of Theorem 2.1.3. There exists a c.e. set A such that

1. A is quasicreative, and

2. A is not n-creative for any n.

is very similar. The only changes that must be made are the following:

1. We will be constructing a set A that is q-creative, but not n-creative for any n. Thus, we must alter our positive requirements so that they no longer guarantee n-creativity for some particular n, but still guarantee q-creativity. In fact, we will keep the wording of the requirements the same:

P_{e} : W_{e} ⊆ \overline{A} ⟹ [D_{g(e)} ⊂ \overline{A} & D_{g(e)} ⊈ W_{e}],

but will change the definition of the function g employed. We instead take g to be a computable function such that:

(a) (∀e)[|D_{g(e)}| = e + 1], and

(b) (∀i, j)[i ≠ j ⟹ D_{g(i)} ∩ D_{g(j)} = ∅].

2. We need to show that A is not n-creative, not just for one particular n, but for all n ≥ 1. We thus must expand our collection of negative requirements to cover every possible n-creativity function φ_{a} for every n. We therefore employ some suitable pairing function to indentify ω with ω × (ω − {0}), and define our negative requirements as follows:

N_{⟨a,n⟩} :  (∃y)[W_{y} ⊆ \overline{A} &
(0) (φ_{a}(y)↑ ∨ |D_{φ_{a}(y)}| ≠ n ∨ D_{φ_{a}(y)} ⊈ \overline{A} ∨
(1)  D_{φ_{a}(y)} ⊆ W_{y})].

That is, we will attempt to show that for no e = ⟨a, n⟩ can φ_{a} serve as the computable function f in the alternative definition of n-creativity given in §2.2.1.

3. Having changed our definition of N_{e}, we must change our defintion of the two recursive functions a(e) and n(e) so that the negative requirement N_{e}, if satisfied, still guarantees that A is not n(e)-creative via function φ_{a(e)}. We define these functions so that where e = ⟨a, n⟩, a(e) = a and n(e) = n.

4. The description of the construction is now exactly as before.

However, note that Clause 4 of Stage 2q + 2 may now come into play; it is now possible that |D_{g(e)}| = e + 1 ≤ n(j) = |D_{φ_{a(j),q+1}(p_{s}(j))}| and it is therefore possible that D_{g(e)} − D_{φ_{a(j),q+1}(p_{s}(j))} = ∅. Fortunately, for any given j there are only finitely many e for which this can occur, so N_{j} will only be injured by Clause 4 finitely many times.

5. To reflect the fact that Clause 4 may now come into play, we must alter our verification slightly. The third paragraph of the proof of Lemma 2.2.3 should now read: Now, take r ≥ n(e) so that for every i < e such that φ_{a(i)}(p(i)) converges, D_{φ_{a(i)}(p(i))} ⊆ ⋃_{z<r} D_{g(z)}. Take t′ > t such that A_{t} ∩ ⋃_{z<r} D_{g(z)} = A ∩ ⋃_{z<r} D_{g(z)}. Suppose that at some stage 2q + 2 > t′, an element x enters A from some D_{g(z)}. Then z ≥ r, so D_{g(z)} ∩ D_{φ_{i}(p(i))} = ∅ for all i < e, so if x enters A by clause 3 or 4 then j ≥ e. Thus,

(a) If x enters A by clause 3, N_{e} is not marked as injured at stage 2q+2, f_{2q+2}(e) = f_{2q+1}(e), and p_{2q+2}(e) = p_{2q+1}(e).

(b) If x enters A by clause 4, then j ≠ e, for if j = e then |D_{φ_{a(e),q+1}(p_{2q+1}(e))↓} | = n(e), and so D_{g(z)} − D_{φ_{a(e),q+1}(p_{2q+1}(e))} ≠ ∅ because |D_{g(z)}| = z + 1 ≥ r + 1 > n(e). Hence j > e, so again N_{e} is not marked as injured at stage 2q+2, f_{2q+2}(e) = f_{2q+1}(e), and p_{2q+2}(e) = p_{2q+1}(e).

(c) If x enters A by clause 1, then no negative requirements are marked as injured and neither f nor p changes.

The rest of the verification goes through exactly as in the proof of Theorem 2.1.2.

2.3 Noninvariance of Quasicreativity and n-creativity

Both

Theorem 2.1.1. There exist a quasicreative set A and a nonquasicreative low set B such that A ≃ B. (Hence quasicreativity is noninvariant.)

and

Theorem 2.1.4. For all n ≥ 2, there exist an n-creative set A and a non-n-creative low set B such that A ≃ B. (Hence n-creativity is noninvariant for all n ≥ 2.) follow as corollaries of the following lemma:

Lemma 2.3.1 There exists a coinfinite 2-creative set A with semilow complement.

Proof. [Theorems 2.1.1 and 2.1.4.] Let A be as in Lemma 2.3.1, and take any p.s. low set C. Then by Theorem 1.1.6, there exists a c.e. set B ≤_{T} C with A ≃ B. Then A is quasicreative, and n-creative for all n ≥ 2, while B is nonquasicreative and non-n-creative for all n (since B is low, and thus not complete).

Proof. [Lemma 2.3.1.]

Take a computable function f such that for all e, |D_{f(e)}| = {2e, 2e + 1}. In order to make A 2-creative, will be meeting each of the requirements

P_{e} : W_{e} ⊆ \overline{A} ⟹ [D_{f(e)} ⊂ \overline{A} & D_{f(e)} ⊈ W_{e}]

by putting an element of D_{f(e)} into A whenever W_{e} ⊆ \overline{A} has grown to include all of D_{f(e)}.

In order to make \overline{A} semilow, we will also be meeting the negative requirements

N_{e} : |W_{e} \ A| = ∞ ⟹ W_{e} ∩ \overline{A} ≠ ∅.

This will require that we keep elements out of A. As in the proof of Theorem 1.4.1, we will employ for each e the marker Λ_{e,s}, which we attach to an element of W_{e} that we wish to keep out of A. Our attempt to thus satisfy requirement N_{e} may be injured in the process of preserving the truth of N_{i} for any i < e, but this can only result in finitely many injuries, so eventually each marker must come to rest permanently on some element of W_{e} ∩ \overline{A}.

We construct A in stages as follows: Construction. Stage s = 0. Let A_{0} = ∅, and let Λ_{e,0} = −1 for all e. Stage s + 1. Step 1 (Guaranteeing P_{e}). If 1. D_{f(e)} ⊈ W_{e,s},

2. D_{f(e)} ⊆ W_{e,s+1}, and

3. W_{e,s+1} ⊆ \overline{A}, then

1. If at least one element of D_{f(e)} has no attached Λ-marker, then let x be that element if there is only one such, or the lower of the two (i.e., 2e) if there are two. Let A_{s+1} = A_{s} ∪ {x}.

2. If both elements of D_{f(e)} bear one or more markers, then for the least i such that Λ_{i,s} is attached to one element of D_{f(e)}, let x be the element of D_{f(e)} that does not bear the marker Λ_{i,s}. Let A_{s+1} = A_{s} ∪ {x}, and for all j such that Λ_{j,s} = x, let Λ_{j,s+1} = −1.

Step 2 (Guaranteeing N_{e}). If for some x 1. x ∈ W_{e,s+1} − W_{e,s},

2. x ∈ \overline{A}, and

3. Λ_{e,s} = −1, then let Λ_{e,s+1} = x. (End of construction.) Verification. We now demonstrate the following three lemmas: Lemma 2.3.2 A is coinfinite. Proof. All D_{f(e)} are disjoint, and no more than one element of any D_{f(e)} is put into A by Step 1, because if D_{f(e)}∩A_{s} ≠ ∅ then it cannot be the case that D_{f(e)} ⊆ W_{e,s+1} ⊆ \overline{A}. Thus, \overline{A} contains at least one element from each D_{f(e)}.

Lemma 2.3.3 A is 2-creative.

Proof. If D_{f(e)} ⊆ W_{e}, then at the first stage s+1 when D_{f(e)} ⊆ W_{e,s+1} either W_{e,s} ⊈ \overline{A} or we put an element of D_{f(e)} into A, so in either case W_{e,s+1} ⊈ \overline{A} and therefore W_{e} ⊈ \overline{A}. Also, since no element of D_{f(e)} is put into A unless D_{f(e)} ⊆ W_{e,s+1}, if D_{f(e)} ⊈ \overline{A} then W_{e} ⊈ \overline{A}. Thus, if W_{e} ⊆ \overline{A}, we must have that D_{f(e)} ⊈ W_{e} and D_{f(e)} ⊂ \overline{A}.

Lemma 2.3.4 \overline{A} is semilow.

Proof. It suffices to verify by induction that the following hold for all e:

1. Λ_{e} =_{dfn} lim_{s} Λ_{e,s} converges.

2. N_{e} is satisfied.

1. Suppose that Λ_{e} does not converge. Then Step 1 and Step 2 must each act on Λ_{e,s} at infinitely many stages s. Let s_{0} be some stage such that for all i < e, Λ_{i} = Λ_{i,s_{0}}. Let

S = ⋃{D_{f(j)} : (∃i < e)[Λ_{i} ∈ D_{f(j)}]}.

Then for some stage s_{1} > s_{0}, W_{e,s_{1}} ∩ S = W_{e} ∩ S. Take s_{2} > s_{1} such that Step 1 acts on Λ_{e,s_{2}} at stage s_{2} +1; then Λ_{e,s_{2}+1} = −1. Let t+1 be the next stage after s_{2} + 1 at which Step 2 acts on Λ_{e,t}. Then Λ_{e,t+1} = x where x ∈ W_{e,t+1} − W_{e,t}. Then since t + 1 > s_{0}, x ∉ S. Let t′ + 1 be the next stage after t + 1 at which Step 1 acts on Λ_{e,t′}. Since x is tagged by the marker Λ_{e,t′+1}, x can only be enumerated into A if it is in the same D_{f(j)} as some Λ_{i,t′+1}, i < e. But then x ∈ S, and we get a contradiction.

2. By the above, we know that Λ_{e} converges. Suppose that |W_{e} \ A| = ∞. Then for any stage t such that Λ_{e,t} = −1, let t′ + 1 be the first stage > t for which there exists x ∈ W_{e,t′+1} − W_{e,t′} − A_{t′}; then by Step 2, Λ_{e,t′+1} = x ≠ −1. Thus, Λ_{e} does not converge to −1.

Let s + 1 be the first stage such that Λ_{e,s+1} = Λ_{e}. Then Λ_{e,s+1} = some x ∈ W_{e,s+1}−W_{e,s}−A_{s}, and x never enters A at any subsequent stage, so x ∈ W_{e}∩\overline{A}.

Thus if |W_{e} \ A| = ∞ then W_{e} ∩ \overline{A} ≠ ∅.

2.4 Noninvariance of Subcreativity

2.4.1 Proof via Theorem 2.4.1

In order to prove

Theorem 2.1.5. There exist a subcreative set B and a nonsubcreative low set A such that A ≃ B. (Hence subcreativity is noninvariant.)

we will use the Prompt Coding Theorem of [6] to prove the following theorem, of which Theorem 2.1.5 is a corollary:

Theorem 2.4.1 For any coinfinite prompt set A with semilow complement, there exists a subcreative set B such that A ≃ B.

Proof. [Theorem 2.1.5.] Take A a low prompt set (so A is incomplete and thus nonsubcreative), and construct B as in Theorem 2.4.1.

2.4.2 Intuition and Machinery

The proof employs similar techniques to the proof in [6] that every prompt c.e. set is automorphic to a complete set. That is, for every α on the true path we will have a α-state ν̂ containing an element which BLUE can, if desired, place immediately into B; we will use these elements to ensure the subcreativity of B. The promptness of A will guarantee that D̂_{α}, the collection of such states for a given α, is always nonempty when α is on the true path.

In order for ν̂ to be suitable, it must have the following properties:

1. BLUE must be allowed to move a desired element from ν̂ directly into B.

2. ν̂ must be RED-maximal, that is, no move by RED can take an element out of ν̂. Then BLUE can keep a chosen coding element in ν̂ until BLUE needs to move it into B.

3. ν̂ must be in K̂_{α}, that is, ν̂ must be well-resided, to guarantee a supply of coding elements.

In order for these conditions to be met, we need for the corresponding conditions to be true on the A side:

1. RED must be allowed to move elements of ν directly into A; that is, we need ν to be an element of the set W_{α}^{#} defined, as in [6], to consist of all ν_{1} = ⟨α, σ_{1}, τ_{1}⟩ ∈ M_{α} such that

0 ∉ σ_{1} & (∃ν_{2} = ⟨α, σ_{2}, τ_{2}⟩)[ν_{2} ∈ M_{α} & σ_{1} ⊂ σ_{2} & 0 ∈ σ_{2}].

2. ν must be BLUE-maximal.

3. ν must be in K_{α}.

We therefore define D_{α} as in [6] to be the set of all α-states ν that appear to be thus suitable:

Definition 2.4.2 Let D_{α} be the set of all ν_{1} = ⟨α, σ_{1}, τ_{1}⟩ such that ν_{1} ∈ M_{α} and

1. ν_{1} ∈ W_{α}^{#},

2. ¬(∃ν_{2} ∈ M_{α})[ν_{1} <_{B} ν_{2}], and

3. ν_{1} ∉ N_{α}.

Then the promptness of A guarantees that D_{α} ≠ ∅, for all α ⊂ f. Thus, when we define D̂_{α} to be {ν̂ : ν ∈ D_{α}}, we are guaranteed the existence of at least one state ν̂ ∈ D̂_{α} to give us a supply of suitable coding elements. The coding elements for a given α will be enumerated into a d.r.e. set L_{α,s}, from which they will be removed when they either are used or need to be discarded for other reasons. They are also tagged in pairs with markers ŷ_{α,i,s} and ŷ′_{α,i,s}, for all i up to some computable bound g(α, s) that depends on the particular construction being used. (In our construction, as in that of [6, §10], g(α, s) will always equal 1, so we will have at most one such pair of tagged elements for any given α at any time; in fact, unlike the construction in [6], our construction will only actually use the first element of any such pair.)

We then get the Prompt Coding Theorem (Theorem 10.8 of [6]), which, stated in full, is as follows:

Theorem 2.4.3 (Prompt Coding Theorem, Harrington-Soare) Let A = U_{0} be a given prompt set, and let B = Û_{ρ} where ρ = f ↾ 1. Let g(α, s) be a recursive function (to be used in Step ˆ7). Perform the basic coding construction consisting of Steps 1–6, 11, ˆ1–ˆ5, and ˆ7 of [6, §10], and possibly with additional Steps n̂, 9 ≤ n < 11, defined later, which satisfy the conditions (P̂1)–(P̂3):

(P̂1) If α is R̂-inconsistent or M̂-inconsistent then Step n̂ does not apply to α. If α is D̂-inconsistent then Step n̂ applies to α only if n = 6.

(P̂2) Step n̂ cannot enumerate x̂ in any red set V_{α}. If Step n̂ at stage s + 1 enumerates x̂ in a blue set Û_{α}, then x̂ ∈ R̂_{α,s}, and this enumeration must be α-legal, i.e., ν̂(α, x̂, s + 1) ∈ M̂_{α}.

(P̂3) Step n̂ cannot move x̂ from Ŝ_{α} to Ŝ_{γ} for α ≠ γ, or from Ŝ_{α}^{1} to Ŝ_{α}^{0}, but can only appoint some x̂ already in Ŝ_{α}^{0} as an α-witness, and can later cancel x̂ as an α-witness and simultaneously move x̂ from Ŝ_{α}^{0} to Ŝ_{α}^{1}.

Then

(i) (∀γ ⊆ f)[lim inf_{s} g(γ, s) < ∞] ⟹ A is Δ_{3}^{0}-automorphic to B.

In addition, if the Steps n̂, 9 ≤ n < 11, satisfy the following conditions (Q̂1)–(Q̂4) then conclusions (ii), (iii), (vii), and (viii) hold.

(Q̂1) Step n̂ may not put any element x̂ into the witness set L̂_{α}.

(Q̂2) Step n̂ may not remove any element x̂ from the witness set L̂_{α} unless simultaneously x̂ is enumerated in B.

(Q̂3) If Step n̂ puts x̂ into B_{s+1} − B_{s} then x̂ ∈ L̂_{α,s}. (Q̂4) If x̂ ∈ Ŝ_{α,s}^{0} then Step n̂ may not enumerate x̂ ∈ Û_{α,s+1} − Û_{α,s} for any blue

set Û_{α} unless simultaneously x̂ is enumerated in B.

Assume α ⊂ f, α ≠ λ. Then for all x̂ and s and all i ≥ 1, (ii) L̂_{α,s} ⊆ Ŝ_{α,s}^{0}, and L̂_{α} is a d.r.e. set; (iii) [x̂ ∈ (Ŝ_{α,s}^{0} − B_{s}) & ν(α, x̂, s) = ν̂_{1} ∈ D̂_{α}] ⟹ ν(α, x̂, s + 1) = ν̂_{1}; (vii) i ≤ lim inf_{s} g(α, s) ⟹ (∃^{∞}s)[ŷ_{α,i,s} ↓ & ν(α, ŷ_{α,i,s}, s) ∈ D̂_{α}]; (viii) [i ≤ lim inf_{s} g(α, s) & (∃^{<∞}s)[ŷ_{α,i,s} ∈ B_{s+1} − B_{s}]] ⟹ [lim_{s} ŷ_{α,i,s} < ∞].

In addition, if Steps n̂, 9 ≤ n < 11, satisfy the following condition (Q̂5) then conclusion (ix) holds for α and i as above.

(Q̂5) Step n̂ may not put ŷ′_{α,i,s} into B_{s+1} − B_{s}, and may put ŷ_{α,i,s} into B_{s+1} − B_{s} only if ŷ′_{α,i,s} is defined.

(ix) i ≤ lim inf_{s} g(α, s) ⟹ [ (a.e. s)[ŷ_{α,i,s} ↓] & (∃^{∞}s)[ŷ_{α,i,s} ↓ & ŷ′_{α,i,s} ↓]].

In [6, §10], the elements supplied by the states in D̂_{α} were used for coding K into B. We will be using them to fulfill the following requirements:

P_{e} : |W_{e} ∩ B| < ∞ ⟹ [B ⊂ W_{h(e)} ⊆ B ∪ \overline{W}_{e}].

for some h which will be defined by our construction. We employ the following machinery:

1. We have all of the machinery of [6, §10].

2. In the course of our contruction, we will enumerate a collection of c.e. sets {E_{e}}_{e∈ω}. We will thus have a computable function h such that W_{h(e)} = E_{e} ∪ B for all e; this is the h used in the statement of our requirements P_{e}.

3. Where we identify ω with ω × ω by a suitable pairing function, we have the function l defined by l(α) = e if |α| = ⟨e, y⟩ for some y.

2.4.3 Construction

We first let g(α, s) = 1 for all α, s. (That is, only one marker pair will be employed at any node α.) We then employ a modified version of the construction used in [6, §10] as follows: Step 1–6, ˆ1–ˆ5. As in [6, §10]. Step ˆ7. As in [6, §10], with an added accounting step that does not affect any other part of the construction, and therefore does not affect the applicability of the Prompt Coding Theorem:

(ˆ7a) If we have just assigned the marker ŷ_{α,1,s+1} to some x̂, then enumerate x̂ into E_{l(α)}.

Steps ˆ9 and ˆ10 are somewhat modified versions of the corresponding steps in [6, §10]. (Note that since Step ˆ7 only assigns a marker ŷ_{α,1} if α is M̂-consistent, R̂-consistent, and D̂-consistent, Steps ˆ9 and ˆ10 also only apply to nodes that are consistent in all three senses.)

Step ˆ9 puts the elements of E_{e} into B when they go into W_{e}, in order to satisfy requirement P_{e}: Step ˆ9. Suppose |α| = 5i, ŷ_{α,1,s} ↓ = x̂, and ν(α, x̂, s) = ν̂_{1}. If x̂ ∈ W_{e} for some e, perform the action of Step ˆ8 of [6, §7.2] on x̂ at stage s+1. (Namely, choose the least such pair ⟨α, x̂⟩. Let F̂_{α}(ν̂_{1}) = ν̂_{2} = ⟨α, σ̂_{2}, τ̂_{2}⟩. Enumerate x̂ in Û_{δ,s+1} for all δ ⊆ α such that ê_{δ} ∈ σ̂_{2}. Since x̂ ∈ B_{s+1} − B_{s} move x̂ from Ŝ_{α}^{0} to Ŝ_{α}^{1}, and let x̂ be cancelled as an α-witness.)

Step ˆ10 puts witnesses that will be deactivated into B:

Step ˆ10. Suppose ŷ_{α,1,s} ↓ = x̂, and that at stage s+1 either:

(i) x̂ will be removed from Ŝ_{α}^{0} (and from L̂_{α}) because Step 11C applies to α (i.e., f_{s+1} <_{L} α); or

(ii) x̂ will be pulled from Ŝ_{α}^{0} to some Ŝ_{β}, β <_{L} α, under Step ˆ1_{β}.

Then perform the action of Step ˆ8 of [6, §7.2] on x̂, as in Step ˆ9 above. (Note that x̂ will be cancelled as an α-witness at stage s+1 under Step 11C or Step ˆ1_{β} (1.12), as will whatever element x̂′, if any, is tagged with ŷ′_{α,1,s}.)

Substep 11A-F. This is the same as in [6].

2.4.4 Verification

We first note that steps ˆ9 and ˆ10 satisfy all the conditions (P̂1–P̂3) and (Q̂1–Q̂4). Thus, conclusions (i), (ii), (iii), (vii), and (viii) hold. In particular, since (i) holds, the A and B we construct in this way are automorphic. We thus need only verify that B is subcreative; that is, that all the requirements P_{e} are met.

Take any e such that |W_{e} ∩ B| < ∞. Then Steps ˆ9 and ˆ10 put only finitely many elements of E_{e} into B. Take any α such that l(α) = e. Then every element that ever bears the tag ŷ_{α,1} is in E_{e}, so only finitely many such elements are enumerated into B. Thus, by conclusion (viii) for i = 1, we have that lim_{s} ŷ_{α,1,s} < ∞. Also, by conclusion (vii) there are infinitely many s such that ŷ_{α,1,s} ↓. Hence ŷ_{α,1} must eventually be attached permanently to some x̂, which therefore never enters B. Since x̂ ∈ E_{e} ⊆ W_{h(e)}, and B ⊆ W_{h(e)}, then, we have that B ⊂ W_{h(e)}.

To show that W_{h(e)} ⊆ \overline{W}_{e}, we note that any element enumerated into E_{e} gets an attached ŷ-marker simultaneously (in Step ˆ7), any element of E_{e} that loses its ŷ-marker is enumerated into B (in Step ˆ9 or ˆ10), and any element with an attached ŷmarker that is enumerated into W_{e} is enumerated into B. Thus any element of E_{e} that is in W_{e} must also be in B, so E_{e} ⊆ B ∪ \overline{W}_{e} and therefore W_{h(e)} = B ∪ E_{e} ⊆ B ∪ \overline{W}_{e}. Thus, P_{e} is indeed satisfied, and we are done.

2.5 Effective Simplicity

2.5.1 Intuition and Machinery

To prove

Theorem 2.1.6. For any promptly simple set A there exists an effectively simple set B such that A ≃ B.

we will again, as in the proof of Theorem 1.1.6, employ a version of the Harrington-Soare construction restricted to \overline{A} and \overline{B}. However, the modifications we make to the construction of [6] will be different this time, in the following ways:

1. We no longer have that A is semilow, so we can no longer control the enumeration of A_{s} with the help of Γ-markers. Therefore, our construction will no longer have a step that challenges elements x before they change state in any way and assigns them such markers.

2. Because we need no longer challenge elements x before they change state, we can now put the exterior step that enumerates elements into A_{s} where it more naturally goes, as part of Step 4 (that is, with the rest of the moves forced by RED).

3. Also, because we no longer have control of the enumeration into A_{s}, we will not be able to guarantee the correspondence of G^{A} and Ĝ^{B} by the technique we were using previously; that is, using Step 0 to generate our list L^{G} to tell us what elements to enumerate into B for covering purposes. However, it will turn out that the prompt simplicity of A guarantees that G^{A} = M\overline{A} = M̂\overline{B} on the true path. Therefore, we can generate a covering list L^{G} purely from M\overline{B}, and on the true path it will be correct.

4. Finally, our lack of control over the enumeration into A_{s} means that we cannot guarantee R\overline{A} ; α = B̂\overline{B} ; α by the technique of our proof of Theorem 1.1.6 (which was the restriction of the technique used in [6]; that is, ensuring that any α ⊂ f is R\overline{A}-consistent). However, it will turn out that the prompt simplicity of A gives us a much more direct solution: G^{A} = M\overline{A} = M̂\overline{B} on the true path, so there cannot be a problem with BLUE having to empty a state but having no state to send its elements to; it can simply enumerate them into B_{s}. (However, we will still be guaranteeing that B\overline{A} ; α = R̂\overline{B} ; α by ensuring that any α ⊂ f is R̂\overline{B}-consistent.)

5. To guarantee that B is effectively simple, we will satisfy the requirement

P_{e} : |W_{e}| > e ⟹ W_{e} ⊈ \overline{B}

for every e by always enumerating at least one element of any given W_{e} into B if |W_{e}| > e. We can no longer rely on using the elements in some Ŝ_{α}^{0,\overline{B}} for this purpose, because the finite collection of elements we have to chose from may not include any elements in any Ŝ_{α}^{0,\overline{B}}; we may instead have to enumerate elements from anywhere in our tree. We will therefore employ a system of Γ̂-markers to make sure that we choose elements whose enumeration will not interfere with our construction. Specifically, markers will be attached (in Step ˆ0) to elements x̂ entering a node α in any state in R̂\overline{B} ; α, to help us to choose elements that will not interfere with the demonstration that any node α ⊂ f must be R̂\overline{B}-consistent.

6. A version of Step ˆ8 is still used to enumerate elements of Ŝ_{α}^{0,\overline{B}} into B for covering purposes, but an element no longer needs permission from any set C to enter B. This step has also been moved, for technical reasons, to a position between Steps ˆ3 and ˆ4, and has correspondingly been renumbered “Step π̂.”

7. We have a Step ˆ9 that enumerates elements into B to guarantee that B is effectively simple.

Our tree construction will employ the following machinery:

1. We have all of the machinery of Chapter 2 of [6], with the same redefinition of consistency as in §1.2.1, and again restricted to \overline{A} and \overline{B}. (Note, however, that we shall make no use of the notion of R\overline{A}-consistency.) We will henceforth universally adopt the convention, used previously in §1.2.4 and §1.3.2, of omitting the superscript \overline{A} and \overline{B} that indicates this restriction.

2. We again fix an enumeration {Ã_{s}}_{s∈ω} of A.

3. We will again be enumerating {A_{s}}_{s∈ω} and {B_{s}}_{s∈ω} through exterior moves, just as in the proof of Theorem 1.1.6.

4. Also as in that proof, we have a list L^{G} of pairs of the form ⟨α, ν̂⟩, used to satisfy the requirement that ν ∈ G_{α}^{A} implies ν̂ ∈ Ĝ_{α}^{B}. In this construction, however, this list is periodically updated in accordance with M̂_{α}, rather than being updated when elements are enumerated into A_{s}.

5. From our construction we will define (in the proof of Lemma 2.5.1) a collection of c.e. sets {E_{ν,i}^{α}}_{i∈ω} for every node α and α-state ν. Since A is promptly simple, by [14, Proposition XIII.1.3] there exists a computable function q such that

|E_{ν,i}^{α}| = ∞ ⟹ (∃s)(∃x)[x ∈ E_{ν,i, at s}^{α} ∩ Ã_{q(s)}].

By the Recursion Theorem, we can assume that we know this function q in advance.

6. For every node α, for every state ν̂ ∈ R̂_{α}, we have the infinite set of markers {Γ̂_{ν̂,i}^{α}}_{i∈ω}. One marker of this type will be attached to any element x̂ that enters Ŝ_{α} in α-state ν. This marker is removed only if x̂ leaves state ν̂, either by

(a) A RED move of some kind,

(b) An exterior BLUE move, to help guarantee either the correspondence of G^{A} and Ĝ^{B} or the effective simplicity of B, or

(c) Step ˆ1 or 11C.

The Harrington-Soare construction guarantees that for any given α removals of type (c) occur only finitely often, and we will guarantee that for any given marker removals of type (b) occur only finitely often, so eventually each marker rests on an element suitable for use in the proof that an R̂-inconsistent α cannot be on the true path.

7. We define an effective bijection | · | from the set of all possible Γ̂-markers to ω. (This can be done because we can regard the the tree T as a subset of ω^{ω} as in [6, §2.2], so the nodes of T can be given an effective numbering a(α), and for any α the finitely many α-states ν̂ can be given an effective numbering ν̂, so any tag Γ̂_{ν̂,i}^{α} can be effectively identified with a triple ⟨a(α), n(ν̂), i⟩.) We call |Γ̂_{ν̂,i}^{α}| the order of Γ̂_{ν̂,i}^{α}.

2.5.2 Construction

Our construction is as follows:

Stage s = 0. For all α ∈ T define U_{α,0} = V_{α,0} = Û_{α,0} = V̂_{α,0} = ∅, and define m(α, 0) = 0. Define Y_{λ,0} = Ŷ_{λ,0} = ∅, and f_{0} = λ. Define A_{0} = B_{0} = ∅. Every marker Γ̂_{ν,i,0}^{α} is unassigned. Stage s + 1. Find the least n < 11 such that Step n applies to some x ∈ Y_{α,s} and perform the intended action. If there is no such n, then find the least n < 11 such that Step n̂ applies to some x̂ ∈ Ŷ_{α,s}, and perform the indicated action. If none of these steps applies, then apply Step 11, and go to stage s + 2. Steps 1, 2. In the non-dual case, the same as in [6] (restricted to \overline{A} and \overline{B}). In the dual case, each has an added step at the end ((ˆ1.13) or (ˆ2.7), respectively) to add a Γ̂-marker if appropriate:

(ˆ1.13)/(ˆ2.7) Where ν̂_{1} = ν̂(α, x̂, s + 1), the α-state in which x̂ has just entered Ŷ_{α}, if ν̂_{1} ∈ R̂_{α} then attach marker Γ̂_{ν̂_{1},i,s+1}^{α} to x̂, for the least i such that Γ̂_{ν̂_{1},i,s}^{α} is not attached to any element. Step 3. In the nondual case, the same as in [6] (restricted to \overline{A} and \overline{B}). In the dual case, we need to add a step to remove any marker that is no longer applicable:

(ˆ3.6) If any marker Γ̂_{ν̂_{0},i,s}^{α} is attached to the x̂ that we have just moved out of state ν_{0}, remove this marker. Step π̂. (Moving covering elements into B.)

Find the first unmarked pair ⟨α, ν̂⟩ in L^{G} such that for some x̂ ∈ Ŝ_{α,s}^{0}, (π̂.a) x̂ ∈ ν̂, and (π̂.b) No Γ̂-marker on x̂ has ever been detached by Step π̂.

Then (π̂.1) Enumerate the least such x̂ into B, (π̂.2) Mark the current copy of ⟨α, ν̂⟩, and (π̂.3) Detach all Γ̂-markers from x̂.

(In other words, this is just Step ˆ8 from the proof of Theorem 1.1.6, modified to deal with Γ̂-markers, and moved into a position between Steps ˆ3 and ˆ4.)

We must alter Step 4 slightly to include the RED enumeration of elements into A_{s}: Step 4. (Delayed RED enumeration into A_{s+1} and U_{α}.)

(4A) Suppose some x ∈ Y_{λ} and x ∈ Ã_{q(s)}. Enumerate the least such x into A_{s+1}, and end Step 4.

(4) Suppose x ∈ R_{α,s} and (4.1) e_{α} > e_{β}, (4.2) x ∉ U_{α,s}, and (4.3) x ∈ Z_{e_{α},s} =_{dfn} U_{e_{α},s} ∩ Y_{β,s−1}.

Action. Choose the least such pair ⟨α, x⟩ and (4.4) Enumerate x in U_{α,s+1}.

Step ˆ4, however, is just the same as in [6] (restricted to \overline{A} and \overline{B}), with an added action for removing obsolete markers:

(ˆ4.5) For any marker Γ̂_{ν̂_{1},i,s}^{α} attached to x̂ such that we have just moved x̂ out of state ν_{1}, remove that marker.

Step 5. This step, in the non-dual case, is the same as in [6] (restricted to \overline{A} and \overline{B}). Its dual, however, must be changed to reflect the fact that we no longer have any consideration of R-consistency: Step ˆ5. (BLUE emptying of state ν̂ ∈ B̂_{α}.) Suppose for α ∈ T there exists x̂ such that

(5.1) ν̂(α, x̂, s) = ν̂_{0} ∈ B̂_{α}, and

(5.2) x̂ ∈ Ŝ_{α,s}.

Action. Choose the least such pair ⟨α, x̂⟩. Enumerate x̂ into B_{s}. (No marker removal is necessary, because by definition of B̂ and R̂ there cannot exist any δ ⊂ α such that ν̂ ∈ B̂_{α} and ν̂↾δ ∈ R̂_{δ}.)

Step ˆ9. (Guaranteeing that B is effectively simple.) Take the least e such that |W_{e,s} ∩ Ŷ_{λ,s}| > e and W_{e,s} ⊆ \overline{B}_{s}. Take the x̂ ∈ |W_{e,s} ∩ Ŷ_{λ,s}| whose lowest-order marker is of the highest order. Enumerate x̂ into B and remove all of its markers.

Step 11. This is the same as in [6], except that we redefine Substep 11B and 11C:

Substep 11B. (Defining m(α, s + 1), L_{s+1}, L̂_{s+1}, and L_{s+1}^{G}.) For every α ⊆ f_{s+1} if every α-entry ⟨α, ν⟩ on L_{s}, and α-entry ⟨α, ν̂⟩ on L̂_{s}, is marked we say that the lists are α-marked and we

(11.1) Define m(α, s + 1) = m(α, s) + 1.

(11.2) Add to the bottom of list L_{s} (L̂_{s}) a new (unmarked) α-entry ⟨α, ν⟩ (⟨α, ν̂⟩) for every such α and every ν ∈ M_{α}. Let the resulting list be L_{s+1}(L̂_{s+1}).

(11.3) Add to the bottom of list L_{s}^{G} a new (unmarked) α-entry ⟨α, ν̂⟩ for every such α and every ν̂ ∈ M̂_{α}. Let the resulting list be L_{s+1}^{G}.

If lists L_{s} and L̂_{s} are not both α-marked then let m(α, s+1) = m(α, s), L_{s+1} = L_{s}, L̂_{s+1} = L̂_{s}, and L_{s+1}^{G} = L_{s}^{G}.

Substep 11C For every α such that f_{s+1} <_{L} α, remove all markers from all elements of Ŝ_{α,s} and initialize α.

2.5.3 Verifying Correctness of M\overline{A}, M̂\overline{B}, N \overline{A}, and N̂ \overline{B} on f

Just as in §1.3.1, we may assume without loss of generality that A is infinite and coinfinite, and then we have that the tree properties of §1.2.2 hold for our restricted construction. Then it suffices to verify that the versions of Lemmas 5.1 through 5.12 for the \overline{A}/\overline{B} game hold as they did for the overall game in the Harrington-Soare construction.

Lemmas 5.1–5.6 These are stated and proved exactly as in §1.3.2.

Lemma 5.7. This is stated exactly as in [6] and §1.3.2, and is proved exactly as in [6] (rather than as in §1.3.2).

Lemma 5.8. The statement of this lemma is as in §1.3.2. The proof must be altered in a few details, however:

Proof. By Lemma 5.6(i) Step 11E must eventually put every element x ∈ ω into Y_{λ}. By induction we may assume that R_{β,∞} =^{∗} Y_{β} ∩\overline{A} =^{∗} \overline{A} and Y_{β} is infinite, for β = α^{−}. By Lemma 5.7 m(α) = ∞ and m(γ) < ∞ for all γ <_{L} α with γ^{−} = β.

By Lemma 5.3, Y_{<α} =^{∗} 0. For any x that is in S_{β}^{0} at some stage and is never moved into Y_{<α} by Step 11C, x is eventually moved either into A by Step 4A, or into S_{β}^{1} by Step 11D. (For the dual case, this should read “x̂ is eventually moved either into B by Step ˆ5, π̂, or ˆ9, or into Ŝ_{β}^{1} by Step 11D.”) For any x that is in S_{β}^{1} at some stage and is never moved into Y_{<α} by Step 11C, x is eventually moved either into A by Step 4A, or into S_{α} by Step 1 or Step 2. (For the dual case, this should read “x̂ is eventually moved either into B by Step ˆ5 or ˆ9, or into Ŝ_{α} by Step ˆ1 or Step ˆ2.”)

Thus, almost every x ∈ R_{β} not yet in R_{α} that never enters A will eventually enter S_{α}. By Lemma 5.4(v) almost every such x will remain in R_{α} forever. Thus, R_{α,∞} =^{∗} Y_{α} ∩ \overline{A} =^{∗} Y_{β} ∩ \overline{A} =^{∗} \overline{A}.

Also, since Y_{β} is infinite, F_{β}^{+} must contain at least one state ν. By Lemma 5.7(iii) ((iv) in the dual case), ν ∈ E_{α}; that is, infinitely many elements enter Y_{α} in state ν. Thus, Y_{α} is infinite.

Lemma 5.9 is stated exactly as in [6] and §1.3.2, but the proof is very slightly different from the proof in the former (because the statements of Lemmas 5.8 and 5.4(v) are slightly different) and significantly different from the proof in the latter (because now, as in [6], elements only move by RED in Step 4, so we don’t have to worry about elements vanishing into A before Step 3 can act on them):

Lemma 5.9. α ⊂ f ⟹ α is M-consistent.

Proof. Let α ⊂ f and β = α^{−}. Assume for a contradiction that α is not M-consistent. Then e_{α} > e_{β} and there exist ν_{0} ∈ M_{α}, ν_{1} ∉ M_{α}, ν_{0} <_{B} ν_{1} and ν_{1}↾β ∈ M_{β}. Then α is a terminal mode on T so S_{α} = R_{α}. By Lemmas 5.8 and 5.4(v), S_{α,∞} ∩ \overline{A} is infinite and no x ∈ S_{α,s}, s > v_{α}, later leaves S_{α} except possibly to enter A. By Lemma 5.7, E_{α} ⊇ M_{α} so

(∃^{∞}x)(∃s)[x ∈ S_{α,s+1} − S_{α,s} & ν(α, x, s + 1) = ν_{0}].

Choose any such x and s > v_{α}. Now neither Step 1_{γ} nor Step 2_{γ} can apply to x at any stage t > s. Hence, by the ordering of the steps, Step 3_{α} must apply to some such x′ at some stage t + 1 > s + 1 with ν(α, x′, t) = ν_{0} and must cause ν(α, x′, t + 1) = ν_{1}. Thus, α is provably incorrect at all stages v ≥ t + 1, so α ⊄ f.

Lemma 5.10. Just as in [6] and §1.3.2.

We have no Lemma 5.11 in the nondual case, because we have no consideration of R-consistency. Lemma 5. ˆ11, on the other hand, is stated exactly as in [6] and §1.3.2. The proof is somewhat more complicated, because we have to make sure that the disappearance of elements by Steps π̂ and ˆ9 does not cause problems. Lemma 5.ˆ11. α ⊂ f ⟹ α is R̂-consistent.

Proof. Assume for a contradiction that α ⊂ f and α is not R̂-consistent. Choose ν̂_{1} ∈ R̂_{α} such that for all ν̂_{2} ∈ M̂_{α}, ν̂_{1} ≮_{R} ν̂_{2}. By equation (42) of [6] α is a terminal node on T so Ŝ_{α} = R̂_{α}. Thus, by Lemma 5.4(v), for some υ_{α}, no x̂ ∈ Ŝ_{α,s} ∩ \overline{B} later leaves Ŝ_{α}.

Assume for a contradiction that there are only finitely many elements x̂ such that Step ˆ4 applies to x̂ at some stage s when ν̂(α, x̂, s) = ν̂_{1}. Then we can prove the following claim: Claim 1. For every i ∈ ω, there is an element x̂_{i} and a stage s_{i} such that

1. x̂_{i} ∈ Ŷ_{α,s_{i}+1} − Ŷ_{α,s_{i}}, and

2. Γ̂_{ν̂_{1},i,t}^{α} = x̂_{i} for all t ≥ s_{i} + 1.

Proof. [Claim 1] We proceed by induction on i. Suppose we have our statement for all i′ < i. Take s = max{s_{i′} : i′ < i}.

Now, any collection of more than e elements must include one whose lowest order marker is of order ≥ e. Thus, for any e > |Γ̂_{ν̂,i}^{α}|, if Step ˆ9 acts on W_{e} by putting an element of W_{e,s} ∩ Ŷ_{s} into B_{s+1} then that element will not be Γ̂_{ν̂,i}^{α}, because there are |W_{e,s} ∩ Ŷ_{s}| > e elements to choose from, and one of them will have a higher-order lowest-order marker. Thus, Step ˆ9 can remove the marker Γ̂_{ν̂,i}^{α} at most |Γ̂_{ν̂,i}^{α}|+1 times (in acting on W_{e} for e ≤ |Γ̂_{ν̂,i}^{α}| + 1).

Then take any stage t > max{υ_{α}, s} by which

1. Step ˆ9 has removed marker Γ̂_{ν̂_{1},i}^{α} all the times it ever will.

2. Step π̂ has removed marker Γ̂_{ν̂_{1},i}^{α} if it ever will. (Note that Step π̂ can remove a given marker at most once.)

3. Step ˆ4 will never again apply to any x̂ in state ν̂_{1}.

Then after stage t, Γ̂_{ν̂_{1},i}^{α} can never be removed from an element by Step ˆ1 or 11C (since t > υ), or by Step π̂, ˆ4, or ˆ9, or by Step ˆ3 (since by Lemma 5.ˆ9, α is M̂-consistent) or by Step ˆ5 (since there cannot exist any δ ⊂ α such that ν̂ ∈ B̂_{α} and ν̂↾ δ ∈ R̂_{δ}); that is, if Γ̂_{ν̂_{1},i}^{α} is ever attached to an element at some stage > t, it remains attached permanently. Also, since t > s, if any element x̂ ever enters Ŷ_{α} in state ν̂ at any stage > t, it will be marker Γ̂_{ν̂_{1},i}^{α} that will be attached to x̂ unless Γ̂_{ν̂_{1},i}^{α} is already attached to some element. Thus, since ν̂_{1} ∈ R̂_{α} ⊆ M̂_{α} = Ê_{α}, by some stage later than t Γ̂_{ν̂_{1},i}^{α} must be permanently attached to some element x̂, which must have received the marker when entering Ŷ_{α} in state ν̂ at some stage s_{i} + 1.

But if, say, ν̂(α, x̂_{0}, t) = ν̂_{1} for all t > s_{0} then x̂_{0} witnesses that F̂(α^{−}, ν̂_{1}) fails so ν̂_{1} ∈ R̂_{α} contradicts α ⊂ f. Hence, by contradiction we know that Step ˆ4 applies infinitely often to elements x̂ ∈ Ŝ_{α} in state ν̂_{1}. Then there must be some state ν̂_{2} to which infinitely many of these elements are moved. Now ν̂_{2} ∈ F̂_{α}, so ν̂_{2} ∈ M̂_{α} by Lemma 5.10.

The statement of Lemma 5.12 is the same as in [6] and §1.3.2, and so is the proof in the dual case, but in the nondual case it is somewhat different because there is no longer any consideration of R-consistency.

Lemma 5.12. If α ⊂ f and ν_{1} ∈ B_{α} then {x : x ∈ Y_{α} & ν(α, x) = ν_{1}} =^{∗} ∅.

Proof. Fix α ⊂ f and ν_{1} ∈ B_{α}. Let v_{α} be as in Lemma 5.4(v). Assume for a contradiction that x ∈ R_{α,s} for some s > v_{α} and that for all t ≥ s, γ = α(x, t), and ν_{1} = ν(α, x, t). Now γ ⊇ α and α ∈ T so ν′_{1} ∈ B_{γ} for all ν′_{1} ∈ M_{γ} such that ν′_{1}↾α = ν_{1}. Then Step 5 applies to x and γ at some stage t + 1 > s so x is enumerated into B_{t+1}.

Thus, just as in §1.3.2, we now have that M\overline{A}, M̂\overline{B}, N \overline{A}, and N̂ \overline{B} are all correct on f, and f is infinite.

2.5.4 Verifying that G^{A} = Ĝ^{B}.

Since M_{α} = M̂_{α} for any α, it suffices to verify two lemmas:

Lemma 2.5.1 For any α ⊂ f, G_{α}^{A} = M_{α}.

Lemma 2.5.2 For any α ⊂ f, Ĝ_{α}^{B} = M̂_{α}.

Proof. [Lemma 2.5.1.] For any node α, α-state ν, and i ∈ ω, we define the c.e. set E_{ν,i}^{α} to be the set of all elements entering S_{α}^{0} in state ν after stage i (enumerated by enumerating each such element into E_{ν,i}^{α} in the same stage in which it enters S_{α}^{0}). Then take any α ⊂ f. Since G_{α}^{A} ⊆ M_{α}, we need only show that M_{α} ⊆ G_{α}^{A}. Take any ν ∈ M_{α}.

Since ν ∈ M_{α} = E_{α}^{0}, E_{ν,i}^{α} is infinite for every i, so for each i there is some x_{i} ∈ E_{ν,i}^{α} and some stage s_{i} such that x_{i} ∈ E_{ν,i at s_{i}}^{α} ∩ Ã_{q(s_{i})}. Note that such an s_{i} must be greater than i.

We define the sequence i_{0} < i_{1} < i_{2} < ... inductively as follows:

1. Let i_{−1} = 0.

2. Given any i_{n}, we can find x_{i_{n}} and s_{i_{n}} as above. Let i_{n+1} = s_{i_{n}}.

Then x_{i_{n}} enters S_{α}^{0} in state ν at stage i_{n+1}, by Step 1 or 2. Neither Step 1 nor Step 2 can act on any x_{i_{n}} while x_{i_{n}} is in S_{α}^{0}, and Step 3 cannot either because α is M-consistent (by Lemma 5.9). Thus, since each x_{i_{n}} ∈ Ã_{q(s_{i})}, eventually each x_{i_{n}} is enumerated by Step 4A into A_{s} from state ν. Thus, ν ∈ G_{α}^{A}.

Proof. [Lemma 2.5.2.] Take any α ⊂ f. Again, we need only show that M̂_{α} ⊆ Ĝ_{α}^{B}. Take any ν̂ ∈ M̂_{α}. Then since lim_{s} m(α, s) = ∞, infinitely many copies of the pair ⟨α, ν̂⟩ appear in L^{G}. Take any such copy, and let s be a stage such that every element ahead of it in L^{G} that will ever be marked has already been. By Lemma 5.7, ν̂ ∈ Ê_{α}^{0}, so at some stage t > s an element x̂ enters S_{α}^{0} in state ν̂. Then neither Step ˆ1 nor Step ˆ2 can act on x̂ as long as x̂ remains in S_{α}^{0}, and Step ˆ3 cannot either because α is M̂-consistent (by Lemma 5.ˆ9). Thus, the given copy of ⟨α, ν̂⟩ must be marked at some stage t′ > t by Step π̂ acting on x̂, unless it is marked by some other action of Step π̂ on an element of state ν̂.

Hence, every copy of ⟨α, ν̂⟩ is eventually marked, so infinitely many elements enter B from state ν̂, so ν̂ ∈ Ĝ_{α}^{B}.

Having shown that G^{A} = Ĝ^{B}, we also have that the tree properties of §1.2.2 hold for the overall construction, just as in §1.3.4.

2.5.5 Verifying that B is Effectively Simple.

We wish to verify that every requirement P_{e} is satisfied. Take any e such that |W_{e}| > e. Take s such that |W_{e,s}| > e. Let t > s be a stage by which

1. Every i < e that will ever be acted on by Step ˆ9 already has been, and

2. W_{e,s} ⊆ Ŷ_{λ,t}.

Then at the next stage t′ +1 at which Step ˆ9 is reached, we will have W_{e,s} ⊆ W_{e,t′+1} ∩ Ŷ_{λ,t′} and therefore |W_{e,t′+1} ∩ Ŷ_{λ,t′}| > e, so if W_{e,t′+1} ⊆ \overline{B}_{t′} then Step ˆ9 will enumerate an element of W_{e,t′+1} into B. Thus, W_{e,t′+1} ⊈ \overline{B}_{t′+1} and therefore W_{e} ⊈ \overline{B}.

REFERENCES

[1] M. Blum and I. Marques, On complexity properties of recursively enumerable sets, J. Symbolic Logic 38 (1973), 579-593.

[2] P. A. Cholak, Automorphisms of the Lattice of Recursively Enumerable Sets, Memoirs of the Amer. Math. Soc. 113, 1995.

[3] P. A. Cholak, The Dense Simple Sets are Orbit Complete, Proceedings of the Oberwolfach Conference on Computability Theory in 1996, Journal of Pure and Applied Logic 94 (1998), 37–44.

[4] R. Downey and M. Stob, Automorphisms of the lattice of recursively enumerable sets: Orbits Advances in Math. 92 (1992), 237-265.

[5] L. Harrington and R. I. Soare, Post’s Program and incomplete recursively enumerable sets, Proc. Natl. Acad. of Sci. USA 88 (1991), 10242–10246.

[6] L. Harrington and R. I. Soare, The Δ_{3}^{0} automorphism method and noninvariant classes of degrees, Jour. Amer. Math. Soc. 9 (1996), 617–666.

[7] W. Maass, Recursively enumerable generic sets, J. Symbolic Logic 47 (1982), 809–823.

[8] E. L. Post, Recursively enumerable sets of positive integers and their decision problems, Bull. Amer. Math. Soc. 50 (1944), 284–316.

[9] R. W. Robinson, The Inclusion Lattice and Degrees of Unsolvability of the Recursively Enumerable Sets, Ph.D. Dissertation, Cornell University, 1966.

[10] H. Rogers, Jr., Theory of Recursive Functions and Effective Computability, McGraw-Hill, New York, 1967.

[11] J. R. Shoenfield, Quasicreative sets, Proc. Amer. Math. Soc. 8 (1957), 964-967.

[12] R. I. Soare, Automorphisms of the recursively enumerable sets, Part I: Maximal sets, Ann. of Math. (2) 100 (1974), 80–120.

[13] R. I. Soare, Automorphisms of the lattice of recursively enumerable sets, Part II: Low sets, Ann. Math. Logic 22 (1982), 69–107.

[14] R. I. Soare, Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets, Springer-Verlag, Heidelberg, 1987.