A Computably Categorical Structure Whose Expansion by a Constant Has Infinite Computable Dimension

Denis R. Hirschfeldt^{∗}

Department of Mathematics, University of Chicago, Chicago IL 60637, U.S.A.

Bakhadyr Khoussainov

Department of Computer Science, University of Auckland, Private Bag 92019, Auckland, New Zealand

Richard A. Shore^{∗∗}

Department of Mathematics, Cornell University, Ithaca NY 14853, U.S.A.

Abstract

Cholak, Goncharov, Khoussainov, and Shore [J. Symbolic Logic 64 (1999) 13– 37] showed that for each k > 0 there is a computably categorical structure whose expansion by a constant has computable dimension k. We show that the same is true with k replaced by ω. Our proof uses a version of Goncharov’s method of left and right operations.

∗Partially supported by an Alfred P. Sloan Doctoral Dissertation Fellowship and NSF Grant DMS-0200465.

∗∗Partially supported by NSF Grants DMS-0100035 and INT-9602579. Thanks also to the Mathematics Departments at Harvard and MIT for their hospitality.

1 Introduction

The properties of a structure studied by classical model theory are preserved under isomorphism. Thus, in that context, it makes sense to consider isomorphic structures to be identical. This is not the case, however, in computable model theory, since two isomorphic computable structures might have quite different computability-theoretic properties. (See [10] for examples of this phenomenon, as well as background relevant to this paper.) This leads us to study computable structures up to computable isomorphism, a point of view reflected in the following definition.

1.1 Definition. A structure A in a computable language is computable if both its domain |A| and its atomic diagram are computable. If, in addition, its existential diagram is computable, then A is 1-decidable.

An isomorphism from a structure M to a computable structure is called a computable presentation of M. (We often abuse terminology and refer to the image of a computable presentation as a computable presentation.)

The computable dimension of a structure M is the number of computable presentations of M up to computable isomorphism.

A structure of computable dimension 1 is said to be computably categorical.

The study of the relationships between different computable presentations of a structure is an important theme in computable model theory. It is roughly analogous to the classical study of the relationships between different models of a theory, but the issues and results in these two settings are often quite different. For example, it follows from the Ryll-Nardzweski Theorem that a countably categorical structure remains countably categorical when expanded by finitely many constants. It is natural to ask whether the same is true in the analogous situation in computable model theory. That is, does every computably categorical structure remain computably categorical when expanded by finitely many constants?

Millar [11] showed that, with a relatively small additional amount of decidability, computable categoricity is preserved under expansion by finitely many constants.

1.2 Theorem (Millar). If A is computably categorical and 1-decidable, then any expansion of A by finitely many constants remains computably categorical.

However, preservation of categoricity does not hold in general, as was shown by Cholak, Goncharov, Khoussainov, and Shore [1].

1.3 Theorem (Cholak, Goncharov, Khoussainov, and Shore). For each k > 0, there exists a computably categorical structure A and an a ∈ |A| such that (A, a) has computable dimension k.

This result raises the following question, left open in [1], as well as in [9], where an easier proof of Theorem 1.3 was given: Does there exist a computably categorical structure whose expansion by some set of finitely many constants has computable dimension ω? In this paper we give the following positive answer to this question.

1.4 Theorem. There exists a computably categorical structure A and an a ∈ |A| such that (A, a) has computable dimension ω.

The proof of this theorem, which will be given in Section 3, uses techniques from [7], which in turn builds on [1, 6, 9]. The original source for the method common to all these papers is the work of Goncharov [3, 4]. In Section 2, we will introduce some of the fundamental ideas of the proof in a less complicated setting. We assume basic familiarity with computable model theory and the tree method of organizing priority constructions. References include [2] (especially the paper [5]) and [12], respectively.

The structure built in Section 3 will be a directed graph. Thus, by the results of [8], for each of the following theories, Theorem 1.4 remains true if we also require that the structure mentioned in it be a model of the given theory: symmetric, irreflexive graphs; partial orderings; lattices; rings (with zero-divisors); integral domains of arbitrary characteristic; commutative semigroups; and 2-step nilpotent groups.

Our result is still not quite the final word on what can happen to the computable dimension of a structure under expansion by constants. The computable dimension of a computable structure A is said to be effectively infinite if there is an effective procedure that, given a uniformly computable set 𝔓 of computable presentations of A, produces a computable presentation of A that is not computably isomorphic to any of the structures in 𝔓. It will be easy to see that no expansion of the structure built in Section 3 by finitely many constants has effectively infinite computable dimension.

1.5 Question. Is there a computably categorical structure A whose expansion by some set of finitely many constants has effectively infinite computable dimension?

1.1 Notation

We denote the e^{th} partial computable function by Φ_{e}, and the result of running the machine computing this function for s steps on input x by Φ_{e}(x)[s]. We use ↑ and ↓ for convergence and divergence, respectively.

For a set X, let X ↾ m = X ∩ {0, …, m − 1}. For a function f, let f ↾ m be the restriction of f to dom f ↾ m. For a structure A in a relational language and a subset S of |A|, let A ↾ S be the structure obtained by restricting A to S.

For sequences σ and τ, let σ^{⌢}τ be their concatenation. We write σ^{⌢}x instead of σ^{⌢}(x), where (x) is the sequence consisting of the single element x. If σ = (x_{0}, …, x_{n}) then σ(i) = x_{i} and σ ↾ i = (x_{0}, …, x_{i−1}). We denote the length of σ by |σ|.

Fix a one-to-one function from ω × ω onto ω and let ⟨a, b⟩ denote the image under this function of the ordered pair consisting of a and b. We write ⟨a, b, c⟩ instead of ⟨a, ⟨b, c⟩⟩. For x ∈ ω and i = 0, 1, we write π_{i}(x) for the i^{th} coordinate of the ordered pair coded by x. That is, if x = ⟨a, b⟩ then π_{0}(x) = a and π_{1}(x) = b.

2 The Method of Left and Right Operations

In this section, we sketch a proof of the existence of a structure of computable dimension two. The first example of such a structure is due to Goncharov [4], as is the general method we will employ. Our purpose here is to introduce some of the basic ideas behind the proof of our main result in a less complicated setting. Thus we will be informal and leave details for the next section.

2.1 The Basic Diagonalization Strategy

First suppose we just want to build computable structures A^{0} and A^{1} that are isomorphic but not computably isomorphic. We think of this task as building A^{0} and A^{1} to be isomorphic while satisfying the following requirements:

R_{e} : Φ_{e} total ⇒ Φ_{e} is not an isomorphism from A^{0} to A^{1}.

One strategy for satisfying these requirements is to dedicate some portion of A^{0} to the satisfaction of R_{e} and wait until Φ_{e} converges on that part of A^{0} and looks like a partial isomorphism. We can then change A^{0} and A^{1} in a way that kills that specific potential isomorphism, while still keeping the structures isomorphic.

To give this “bait and switch” idea a concrete form, let us introduce the basic building blocks of the constructions in this paper.

2.1 Definition. Let n ∈ ω. The directed graph [n] consists of n + 3 many nodes x_{0}, x_{1}, …, x_{n+2} with an edge from x_{0} to itself, an edge from x_{n+2} to x_{1}, and an edge from x_{i} to x_{i+1} for each i ⩽ n + 1. We call x_{0} the top of [n] and x_{n+2} the coding location of [n]. (We keep the terminology “coding location” used in [6, 7, 9], although in this paper we will be diagonalizing rather than coding.)

A cycle is a copy of [k] for some k ∈ ω.

Let S ⊂ ω. The directed graph [S] consists of one copy of [s] for each s ∈ S, with all the tops identified.

Figure 2.1 shows [2] and [{2, 3}] as examples.

[figure: •; top; •; •; •; coding location; •]

[figure: •; top; •; •; •; coding location; •; •; •; •; •; coding location; •]

Figure 2.1: [2] and [{2, 3}]

We build A^{0} and A^{1} in stages. We begin by letting A_{0}^{0} and A_{0}^{1} be computable structures with co-infinite domains, each consisting of one copy of [k] for each k ∈ ω. The following definitions will help us describe the kind of changes we make to our structures to satisfy the requirements.

2.2 Definition. Let G be a computable structure in the language of directed graphs whose domain is co-infinite. G consists of the disjoint union of a number of connected components, which from now on we will just call the components of G.

Suppose that G has components K and L isomorphic to [B] and [C], respectively, where B, C ⊂ ω are finite. We define the operation K · L, which takes G to a new computable structure extending G, as follows. Extend K to be a copy of [B ∪ C] using numbers not in the domain of G. Leave every other component of G (including L) unchanged.

We will also use the notation K · L to denote the graph [B ∪ C]. It should always be clear which meaning of K · L is being used.

Given a finite sequence of operations, each of which can be performed on G, so that no two operations in the sequence affect the same component of G, we can perform all the operations in the sequence simultaneously on G to get a structure extending G. In this case we will say that we have performed the sequence of operations on G.

2.3 Definition. Let G be a computable structure in the language of directed graphs whose domain is co-infinite and let X_{0}, …, X_{n} be components of G such that, for each i ⩽ n, X_{i} is isomorphic to [S_{i}] for some finite S_{i} ⊂ ω. We define two operations, each of which takes G to a new computable structure extending G.

• The L-operation L(X_{0}, …, X_{n}) consists of performing the sequence of operations X_{0} · X_{1}, X_{1} · X_{2}, …, X_{n} · X_{0} on G.

• The R-operation R(X_{0}, …, X_{n}) consists of performing the sequence of operations X_{0} · X_{n}, X_{1} · X_{0}, …, X_{n} · X_{n−1} on G.

Note that if H is the structure obtained by performing L(X_{0}, …, X_{n}) on G and H′ is the structure obtained by performing R(X_{0}, …, X_{n}) on G then H ≅ H′.

We can now proceed as follows. For each e, we choose components X_{e}^{0}, Y_{e}^{0}, and Z_{e}^{0} of A_{0}^{0} and let X_{e}^{1}, Y_{e}^{1}, and Z_{e}^{1} be the corresponding components of A_{0}^{1}. (This choice should be made so that no component is chosen for more than one e.) Let x_{e}^{i} be the coding location of X_{e}^{i}.

At stage s, let e be the least number such that we have not yet satisfied R_{e} and Φ_{e}(x_{e}^{0})[s] ↓= x_{e}^{1}. (If there is no such e, we do nothing at this stage.) We perform L(Y_{e}^{0}, X_{e}^{0}, Z_{e}^{0}) on A_{s}^{0} to get A_{s+1}^{0}, perform R(Y_{e}^{1}, X_{e}^{1}, Z_{e}^{1}) on A_{s}^{1} to get A_{s+1}^{1}, and declare R_{e} to be satisfied.

Now let A^{0} = ⋃_{s∈ω} A_{s}^{0} and A^{1} = ⋃_{s∈ω} A_{s}^{1}. It is easy to show, by induction using the definition of the L- and R-operations, that A_{s}^{0} ≅ A_{s}^{1} for each s. It is also true that whenever a component of A_{s}^{i} participates in an operation at stage s + 1, so does the isomorphic component of A_{s}^{1−i}. Since A^{0} and A^{1} have no infinite components, it follows that A^{0} ≅ A^{1}.

It is also easy to argue that each requirement is eventually satisfied. If Φ_{e}(x_{e}^{0})↑ then R_{e} is vacuously satisfied. If Φ_{e}(x_{e}^{0})↓≠ x_{e}^{1} then X_{e}^{0} and X_{e}^{1} are never involved in operations, and hence any isomorphism from A^{0} to A^{1} must take x_{e}^{0} to x_{1}^{e}. If Φ_{e}(x_{e}^{0}) ↓= x_{e}^{1} then, by induction, we eventually act to satisfy R_{e} by making sure that the components containing x_{e}^{0} and x_{e}^{1} are not isomorphic, so that no isomorphism from A^{0} to A^{1} can take x_{e}^{0} to x_{1}^{e}. In any case, Φ_{e} is not an isomorphism from A^{0} to A^{1}.

2.2 Special Components

The above construction ensures that the computable dimension of A^{0} is at least two. To have it be exactly two, we have to modify the construction to guarantee that

(2.1) if G ≅ A^{0} is a computable structure then G is computably isomorphic to either A^{0} or A^{1}.

Let us first discuss one way to satisfy this property for a single fixed G.

Let G[s] denote the stage s approximation to G. Since we only care about G if it is isomorphic to A^{0}, we can assume that G[s] is embeddable in A_{s}^{0} for all s ∈ ω. We will also ensure throughout this construction that, for all s ∈ ω, no component of A_{s}^{i} is embeddable in another component of A_{s}^{i}.

The following is a naive procedure for trying to build a computable isomorphism from A^{i} to G. Given a node x in A^{i}, wait for a stage s such that the component X^{i} of A_{s}^{i} containing x has an isomorphic copy X in G, then map X^{i} to X. The problem is that X^{i} may later participate in an operation, at which point there will be two copies of X^{i} in A^{i} and two in G, and the component of A^{i} containing X^{i} may not be isomorphic to the component of G containing X. (For example, X^{i} and X may both be of the form [1]. After an operation involving components of the form [1], [2], and [3], X^{i} may become part of a component of the form [1] · [2] while X may become part of a component of the form [1] · [3].) If this happens, our original map will no longer be extendable to an isomorphism.

Our strategy for solving this problem is based on the following observation.

Suppose that, at some stage s, A_{s}^{0} has components X^{0}, Y^{0}, Z^{0}, and S^{0}; A_{s}^{1} has isomorphic components X^{1}, Y^{1}, Z^{1}, and S^{1}, respectively; and G[s] has isomorphic components X, Y, Z, and S, respectively. Now suppose we perform L(Y^{0}, X^{0}, Z^{0}, S^{0}) on A_{s}^{0} to get A_{s+1}^{0} and perform R(Y^{1}, X^{1}, Z^{1}, S^{1}) on A_{s}^{1} to get A_{s+1}^{1}. Then A_{s+1}^{0} has components isomorphic to S^{0} · Y^{0}, Y^{0} · X^{0}, X^{0} · Z^{0}, and Z^{0} · S^{0}, and these are the only components of A_{s+1}^{0} that contain copies of X^{0}, Y^{0}, Z^{0}, or S^{0}. So if X, Y, Z, and S do not grow into isomorphic copies of the aforementioned components of A_{s+1}^{0} then we can win immediately by not involving these components in any further operations, thus guaranteeing that G ≇ A^{0}.

So if G ≅ A^{0} then there are only two possibilities. The first is that S grows into a copy of S · Y, Y grows into a copy of Y · X, X grows into a copy of X · Z, and Z grows into a copy of Z · S. In this case we will say that G “goes to the left”. The other possibility is that Y grows into a copy of S · Y, S grows into a copy of Z · S, Z grows into a copy of X · Z, and X grows into a copy of Y · X. In this case we will say that G “goes to the right”.

If G always goes to the left then isomorphic components of A_{s}^{0} and G_{s} always grow into isomorphic components of A^{0} and G, and hence the naive procedure described above succeeds in producing an isomorphism from A^{0} to G. Indeed, it is enough that G almost always go to the left (that is, cofinitely often), since we can always wait a finite amount of time before beginning to build our isomorphism. Similarly, if G almost always goes to the right then we can build a computable isomorphism between A^{1} and G.

To ensure that G either almost always goes to the left or almost always goes to the right, we adopt the strategy of always including copies of a certain fixed component of G, which we will call the special component of G, in our operations.

That is, we first pick some component of G to be its special component. More precisely, we fix some n not otherwise used in the construction and wait until a copy K of [n] appears in G. We declare the component of G that extends K to be the special component of G. Similarly, we call the component of G[s] that extends K the special component of G[s].

At stage 0, we define A_{0}^{i} as before. We also define r_{0} to be 0. The value of r_{s} will code whether G goes to the left or to the right at stage s.

At stage s + 1, we choose e as before and let X_{e}^{i}, Y_{e}^{i}, and Z_{e}^{i} be as above. Let S_{s}^{i} be the isomorphic copy in A_{s}^{i} of the special component S_{s} of G[s]. We wait until copies X_{e}, Y_{e}, and Z_{e} of X_{e}^{i}, Y_{e}^{i}, and Z_{e}^{i}, respectively, are enumerated into G[s] and then perform the same operations as before. We wait until copies of S_{s} · Y_{e}, Y_{e} · X_{e}, X_{e} · Z_{e}, and Z_{e} · S_{s} are enumerated into G. Either the copy of S_{s} · Y_{e} or that of Z_{e} · S_{s} will extend S_{s}. Whichever one it is now becomes S_{s+1}. If S_{s+1} ≅ S_{s} · Y_{e} then r_{s+1} = 0; otherwise r_{s+1} = 1.

The above construction ensures that if G ≅ A^{0} then the special component of G is infinite. On the other hand, it also guarantees that if G changes direction infinitely often (that is, if r_{s} does not have a limit) then no component of A^{0} is infinite, so that G ≇ A^{0}. This latter assertion follows from the fact that, for each s ∈ ω, the copy of the special component of G[s + 1] in A_{s+1}^{1−r_{s+1}} is a component that participates in an operation for the first time at stage s + 1. Figure 2.2 illustrates the case r_{s+1} = 0. In this figure, the special components of G[s] and G[s + 1] and their images are shown in boxes.

\xymatrix{ & Y_{e} \ar[dd] & X_{e} \ar[dd] & Z_{e} \ar[dd] & S_{s} \ar[dd] \\ In G : \\  & Y_{e} · X_{e} & X_{e} · Z_{e} & Z_{e} · S_{s} & S_{s} · Y_{e}}

\xymatrix{ & Y_{e}^{0} \ar[dd] & X_{e}^{0} \ar[dd] & Z_{e}^{0} \ar[dd] & S_{s}^{0} \ar[dd] \\ In A^{0} : \\  & Y_{e}^{0} · X_{e}^{0} & X_{e}^{0} · Z_{e}^{0} & Z_{e}^{0} · S_{s}^{0} & S_{s}^{0} · Y_{e}^{0}}

\xymatrix{ & Y_{e}^{1} \ar[dd] & X_{e}^{1} \ar[dd] & Z_{e}^{1} \ar[dd] & S_{s}^{1} \ar[dd] \\ In A^{1} : \\  & Y_{e}^{1} · S_{s}^{1} & X_{e}^{1} · Y_{e}^{1} & Z_{e}^{1} · X_{e}^{1} & S_{s}^{1} · Z_{e}^{1}}

Figure 2.2: The images of the special component

2.3 Catch-up and Recovery

However, there are two problems with the above construction. First, by the same reasoning as in the last paragraph, if G almost always goes to the left then no component of A^{1} is infinite, while if G almost always goes to the right then no component of A^{0} is infinite. In either case, A^{0} and A^{1} are no longer isomorphic. Second, in general we cannot know in advance whether a given computable structure G is isomorphic to A^{0}, nor can we effectively list the computable structures isomorphic to A^{0}, so in the full construction it will not be possible to wait at each stage until the appropriate components are enumerated into G.

The first problem can be fixed by performing a catch-up operation following each standard operation. Remark. For readers familiar with papers such as [6, 7, 9], we note that these catchup operations will take the place of the isomorphism recovery procedure used in those papers. This change will be needed in the proof of our main result, because there each special component will have infinitely many images. The disadvantage of using catch-up operations is that it creates nontrivial automorphisms, but this is not an issue in our main result, since the structure required in that result cannot be rigid anyhow.

We first make a small modification to the definition of A_{0}^{i}. Instead of starting with a copy of [n] for each n ∈ ω, we reserve an infinite and co-infinite set R ⊂ ω and let each A_{0}^{i} consist of one copy of [n] for each n ∈ ω − R.

At each stage s + 1, we define a subgraph T_{s+1} of the special component of G as follows. If r_{s+1} ≠ r_{s} then let T_{s} be the entire special component of G[s], and otherwise let T_{s+1} = T_{s}.

After each stage s operation as described above, let L_{0}^{i}, …, L_{n}^{i} be the components of A_{s+1}^{i} containing copies of T_{s+1} (listed so that L_{j}^{0} ≅ L_{j}^{1}). Let P_{j} be such that L_{j}^{i} = [P_{j}] and let P = ⋃_{j⩽n} P_{j}. Let k_{0}, …, k_{n} ∈ R be distinct numbers such that A_{s+1}^{i} does not contain a k_{j}-cycle for any j ⩽ n. We extend each L_{j}^{i} to a copy of [P ∪ {k_{j}}].

This catch-up procedure ensures that if r_{s} comes to a limit by stage t then the components of A^{0} and A^{1} that contain a copy of T_{t} are all infinite and isomorphic. At the same time, it maintains the essential property that, for each s, no component of A_{s}^{i} is embeddable in another component of A_{s}^{i}. (This property was needed in the argument given above that G has only two options following each operation.)

We deal with the problem of not knowing whether G ≅ A^{0} by using the idea of recovery. Instead of having a single strategy for each diagonalization requirement R_{e}, we have two, R_{0,e} and R_{1,e}, each working with its own set of components Y_{0,e}^{i}, X_{0,e}^{i}, Z_{0,e}^{i} and Y_{1,e}^{i}, X_{1,e}^{i}, Z_{1,e}^{i}, respectively. Roughly speaking (we will be more precise below), the strategy R_{0,e} works under the assumption that G ≅ A^{0} and R_{1,e} works under the assumption that G ≇ A^{0}.

The strategy R_{1,e} is free to perform an operation involving its set of components whenever it wants to, without caring about G and without involving copies of the special component of G in the operation. The strategy R_{0,e}, on the other hand, must wait for G to recover sufficiently often, as we now explain.

Suppose that we perform an operation at stage s + 1 involving copies of the special component of G[s]. To be more specific, suppose the components of G[s] whose copies participate in this operation are Y_{0,k}, X_{0,k}, Z_{0,k}, and S_{s}. Where we would have waited for Y_{0,k}, X_{0,k}, Z_{0,k}, and S_{s} to grow into copies of Y_{0,k} · X_{0,k}, X_{0,k} · Z_{0,k}, Z_{0,k} · S_{s}, and S_{s} · Y_{0,k}, we now just declare that we are waiting for these copies to appear in G, and proceed with the construction.

A recovery stage is then a stage t + 1 such that

1. G[t] contains copies of all the components for which we are currently waiting and

2. for each e less than or equal to the number of recovery stages before stage t + 1, if R_{e} has not yet been satisfied then G[t] contains components isomorphic to Y_{0,e}, X_{0,e}, and Z_{0,e}.

Whenever G recovers, all strategies R_{1,e} are initialized, in the sense that they have to pick new components Y_{1,e}, X_{1,e}, and Z_{1,e}. (This is done in such a way that the old components are never again picked by any strategy, and for each component we can find a stage after which it can never again be picked by any strategy.) If a strategy R_{1,e} ever gets a chance to act to satisfy R_{e} with its currently selected components, it does so. A strategy R_{0,e}, on the other hand, can only act at a recovery stage and after there have been at least e many recovery stages, and must involve copies of the special component of G in the operation it performs.

By following the above strategy, we ensure two crucial things. One is that each R_{e} is eventually satisfied, whether or not G recovers infinitely often. The other is that if G ≅ A^{0} (in which case G must recover infinitely often) then we can still build a computable isomorphism between one of the A^{i} and G. As we now show, the argument that this second fact holds is only slightly more complicated than before.

We still have that G must almost always go to the left or almost always go to the right. Let us assume the first case (the other being symmetric). Then we can split the components of A^{0} into those that participate in operations for the sake of 0strategies (i.e., strategies R_{0,e} which assume that G recovers infinitely often), and those that participate in operations for the sake of 1-strategies. We can build our isomorphism on the former class of components as before, using the fact that G almost always behaves like A^{0}. For each component K in the latter class of components, we can find a stage after which K is guaranteed not to participate in an operation. At this stage, we can simply wait until an isomorphic component L appears in G and map K to L in the obvious way. This isomorphism will be correct, since we are now guaranteed that neither K nor L will ever grow. (To see that L will never grow, suppose otherwise. Then, since we are assuming that G ≅ A^{0}, there is some s such that A_{s}^{0} contains both K and another component strictly containing a copy of K. But we have ensured that this will never be the case.)

2.4 The tree of strategies

We have been discussing satisfying property (2.1) for a single G, but in the full construction we need to consider all computable graphs. Let G_{0}, G_{1}, … be a standard enumeration of all partial computable directed graphs. Remark. We need to consider partial computable graphs because there is no effective listing of all computable directed graphs. For the sake of definiteness, we make the following definition, although we will make no explicit use of it. A partial computable directed graph G consists of two 0, 1-valued partial computable functions Φ and Ψ, the former unary and the latter binary, such that if Φ(x)[s]↓= Φ(y)[s]↓= 1 then Ψ(x, y)[s]↓. The graph G (resp. G[s]) is the graph whose domain has characteristic function Φ (Φ[s]) and whose edge relation has characteristic function Ψ (Ψ[s]).

The above discussion of recovery suggests how to organize our construction using a tree of strategies. For each finite binary string σ, we have a strategy for satisfying (2.1) for G_{|σ|}. The string σ represents a guess as to which G_{m}, m < |σ|, recover infinitely often, with σ(m) = 0 representing a guess that G_{m} recovers infinitely often and σ(m) = 1 representing a guess that it does not.

More precisely, if τ = σ ↾ m then σ(m) = 0 represents a guess that G_{m} τ-recovers infinitely often. We wait until the next section to give a more detailed discussion of τ-recovery. The basic idea is the following. When an operation performed for the sake of a strategy corresponding to a superstring of τ extends certain components of the A^{i} (as in the simpler example above), we then have to wait for G_{|τ|} to provide copies of these extended components before we can allow strategies corresponding to superstrings of τ to act again. Roughly speaking, we have τ-recovery when these components are provided.

We choose a σ-special component of G_{|σ|} for each σ ∈ 2^{<ω}. There are also 2^{e} many strategies for satisfying R_{e}, one strategy R_{σ,e} for each σ of length e. Each R_{σ,e} acts according to the information encoded in σ. That is, when R_{σ,e} wants to act, it has to wait for each G_{|τ|} with τ^{⌢}0 ⊆ σ to τ-recover, and must then involve the τ-special component of each such G_{|τ|} in the diagonalization operation it performs.

We run the construction in the usual way. At each stage, we choose which path to follow based on which σ are currently recovered. The strategies on this path then get to act, and the strategies to the right of this path are initialized. This initialization process includes choosing a new σ-special component of G_{|σ|} for each σ to the right of the current path. The true path of the construction is the leftmost path visited infinitely often. If σ is on the true path then R_{σ,|σ|} succeeds in satisfying R_{|σ|}.

Furthermore, if σ is on the true path and G_{|σ|} ≅ A^{0} then the σ-special component of G_{|σ|} is involved in every operation performed for the sake of strategies corresponding to superstrings of σ. Arguing as above, for some i = 0, 1 we can effectively build an isomorphism between the components of A^{i} that participate in such operations and the corresponding components of G_{|σ|}. This isomorphism can be extended to all of A^{i} much as before. More specifically, let K be a component of A^{i} that does not belong to a strategy corresponding to a superstring of σ. If K belongs to a strategy to the right of the true path then it is eventually guaranteed never again to participate in an operation, and hence we can extend our isomorphism to K as above. Otherwise, K belongs to a strategy above or to the left of σ. Since there are only finitely many substrings of σ, and strategies to the left of σ are active only finitely often, we need only finitely much information to extend our isomorphism to all components belonging to strategies above or to the left of σ.

There are several other details that would need to be added to the above sketch to complete the proof. In particular, we have not discussed exactly how operations involving multiple special components are performed. These compound operations complicate the analysis of the recovery process and the proof that any computable graph isomorphic to A^{0} must either almost always go to the left or almost always go to the right. Since such aspects of the method of operations depend on the particular result being proved, we leave them to the following section, where we will discuss them in the setting of our main result.

3 Proof of Theorem 1.4

We will build a computable structure A and a computable set {a_{i}}_{i∈ℤ} of elements of |A| so that the following properties hold.

(3.1) For every i ∈ ℤ, (A, a_{i}) ≅ (A, a_{0}).

(3.2) For every i, j ∈ ℤ, if i ≠ j then (A, a_{i}) is not computably isomorphic to (A, a_{j}).

(3.3) If G is a computable structure, g ∈ |G|, and (G, g) ≅ (A, a_{0}), then (G, g) is computably isomorphic to (A, a_{i}) for some i ∈ ℤ.

The structure A will include infinitely many isomorphic subgraphs, built using a version of the method of left and right operations described above. These subgraphs will be arranged in levels attached to a “backbone”, as indicated in the following definition.

3.1 Definition. The backbone graph is the directed graph, shown in Figure 3.1, consisting of the following nodes and edges.

1. A root node x.

2. For each i ∈ ℤ, an i-master node x_{i}, with an edge from x to x_{i}.

3. For each i ∈ ℤ, an edge from x_{i} to x_{i+1}.

We will say that a directed graph G is leveled if |G| can be split into two disjoint sets H and I so that the following conditions are satisfied.

1. G ↾ H is isomorphic to the backbone graph.

2. G ↾ I consists of cycles and edges between the tops of some of these cycles.

3. The only edges in G between elements of H and elements of I are edges from i-master nodes, i ∈ ℤ, to tops of cycles.

4. Let i, j ∈ ℤ, i ≠ j. If there is an edge from the i-master node of G ↾ H to an element y of I then there is no edge from the j-master node of G ↾ H to y.

We call the connected components of G ↾ I the components of G. A component isomorphic to [n] for some n is called a singleton component. Let C be a cycle in G ↾ I and let i ∈ ℤ. If there is a node from the i-master node to the top of C then we say that C has level i. Let K be a component of G, in the above sense. If all the cycles in K have the same level i then we say that K has level i, and define level(K) = i. If none of the cycles in K have levels then we say that K has no level. If there are two cycles in K with different levels then we say that K has multiple levels.

For i ∈ ℤ, we denote by G^{i} the subgraph of G consisting of all level-i components of G. We denote by G^{∗} the subgraph of G consisting of those components of G that either have no level or have multiple levels.

Let n, r ∈ ω. Suppose that G is such that every component M of G^{∗} that has multiple levels consists of a cycle K with no level whose top is connected to the tops of infinitely many cycles L_{0}, L_{1}, … such that L_{i} has a level g(i) for each i ∈ ω. For each component M of G^{∗} as above, let M̂_{n,r} be the graph obtained by restricting the domain of M to the union of |K| and |L_{i}| for every i ∈ ω such that |g(i) − r| ⩽ n. We denote by (G^{∗})^{n,r} the union of all M̂_{n,r} such that M is a component of G^{∗}. In case r = 0, we write simply (G^{∗})^{n}.

\xymatrix{ & ⋮ \\  &  & • 2-master node \ar@{->>}[ul] \\  &  & • 1-master node \ar@{->>}[u] \\ root node • \ar@{->>}[uuur] \ar@{->>}[uurr] \ar@{->>}[urr] \ar@{->>}[rr] \ar@{->>}[drr] \ar@{->>}[ddrr] \ar@{->>}[dddr] &  & • 0-master node \ar@{->>}[u] \\  &  & • −1-master node \ar@{->>}[u] \\  &  & • −2-master node \ar@{->>}[u] \\  & ⋮ \ar@{->>}[ur]}

Figure 3.1: The backbone graph

The structure A will be a leveled graph. The components of A^{∗} that have multiple levels will be of the form given in the previous paragraph, so it will make sense to talk about (A^{∗})^{n,r} and (A^{∗})^{n}. The a_{i} mentioned in (3.1)–(3.3) will be the i-master nodes of A.

Before describing the construction of A, we note that we can restrict the class of graphs that must be considered in satisfying property (3.3). Fix a computable presentation B of the backbone graph with co-infinite domain. Every computable leveled graph is computably isomorphic to a computable graph containing B as a subgraph, so it is enough to consider such graphs. It will also be the case that every cycle in A will have a level except for cycles of the form [10k], k ∈ ω, which will not have levels, so it is enough to consider graphs satisfying this property.

Thus, in this section, we will only consider partial computable graphs G satisfying the following conditions for each s ∈ ω.

1. G[s] ↾ (|G[s]| ∩ |B|) ≅ B ↾ (|G[s]| ∩ |B|).

2. If x ∈ |G[s]| then x is contained in a cycle in G[s].

3. Let K be a cycle not of the form [10k], k ∈ ω, in G[s]. There is a unique node x ∈ |G[s]| ∩ |B| with an edge in G[s] from x to the top of K. This node x is an i-master node for some i ∈ ℤ.

4. Let K be a cycle of the form [10k], k ∈ ω, in G[s]. For every x ∈ |B|, there is no

edge in G[s] from x to the top of K.

Clearly, there exists a computable list G_{0}, G_{1}, … of all partial computable graphs that satisfy the above conditions, and this list contains all the computable graphs that must be considered in satisfying property (3.3). We will assume that, for each n, s ∈ ω, there is an embedding of G_{n}[s] into A_{s}.

The fact that G_{n} contains B means that it makes sense to speak of level i of G_{n}. It also makes sense to speak of level i of G_{n}[s], with the understanding that if the i-master node of B is not in |G_{n}[s]| then level i of G_{n}[s] is empty. The reason for conditions 3 and 4 above is that they ensure that the following is true. Let K be a cycle in G_{n}[s]. If K has level i in G_{n}[s] then it has level i in G_{n}, while if K has no level in G_{n}[s] then it has no level in G_{n}. While this fact will not be needed in our formal construction and verification, it is nevertheless useful in clarifying what we mean when we speak of the level of a component of G_{n} or G_{n}[s] in our informal discussion below.

To satisfy (3.2), we will satisfy the following requirement for each e ∈ ω and i ∈ ℤ, i ≠ 0:

R_{⟨e,i⟩} : Φ_{e} is not an isomorphism from (A, a_{0}) to (A, a_{i}).

This will be enough, since for any j, k ∈ ℤ such that j ≠ k, any automorphism of A taking a_{j} to a_{k} takes a_{0} to a_{i} for some i ≠ 0.

The basic idea for satisfying R_{⟨e,i⟩} is simple, and makes use of the concept of left and right operations described above.

We will build A by beginning with a computable leveled graph A_{0} and successively applying operations. Suppose for now that A_{0} is such that all levels are isomorphic and consist of cycles, and no two components of the same level are isomorphic. (This will change later, when we consider the satisfaction of (3.3).)

We choose a singleton component E^{0} of A_{0}^{0}, let E^{i} be the component of A_{0}^{i} isomorphic to E^{0}, and let x and y be the coding locations of E^{0} and E^{i}, respectively. We then wait until Φ_{e}(x) converges. If this never happens then we win by default. If Φ_{e}(x)↓≠ y then we win by doing nothing, thus guaranteeing that any automorphism of A that takes a_{0} to a_{i} must take x to y, which implies that Φ_{e} cannot be such an automorphism.

If Φ_{e}(x) ↓= y then we act to ensure that no automorphism of A can take x to y. We do this by performing operations on E^{0} and E^{i} that guarantee that the components of A that extend each of these components are not isomorphic. Specifically, we first choose components D^{0}, F^{0}, D^{i}, and F^{i} such that D^{0} and F^{0} have level 0, D^{i} and F^{i} have level i, D^{0} ≅ D^{i}, and F^{0} ≅ F^{i}. Then we perform an operation that guarantees that E^{0} is extended by a component containing a copy of E^{0} · F^{0}, while E^{i} is extended by a component containing a copy of D^{i} · E^{i}.

Of course, to keep all the levels of A isomorphic, we also need to perform similar operations on the components of A_{0}^{j} isomorphic to D^{0}, E^{0}, and F^{0} for each j ∈ ℤ. Without any other features to the construction, we could do this simply by performing the operations L(D^{0}, E^{0}, F^{0}) and R(D^{j}, E^{j}, F^{j}) for j ∈ ℤ, j ≠ 0. Proceeding in this fashion simultaneously for each R_{⟨e,i⟩}, we could satisfy both (3.1) and (3.2).

However, as we will see, the satisfaction of (3.3) will require us to involve more components than just the D^{j}, E^{j}, and F^{j} in our operations, and will make it necessary for the sequence of operations performed to satisfy a given requirement to be periodic, in the sense that there is an n > 0 such that, if a row of level-i components participates in a left operation then so does the isomorphic row of level-(i + nj) components for each j ∈ ℤ, and similarly for right operations.

As an illustration, Figure 3.2, which will be explained below, shows the basic diagonalization strategy in the case in which we are satisfying R_{⟨e,i⟩} for some e ∈ ω and i = 3. An arrow from K to L means that the component K is involved in the operation and becomes a copy of L. Since we want the level-0 and level-3 components involved in the operation to go in opposite directions, the period of this operation is 4. As above, we have components D^{0} and E^{0}, but we now need multiple components F_{0}^{0}, F_{1}^{0}, and F_{2}^{0} in place of F^{0}, for reasons that should become clear after examining the figure. For each i ∈ ℤ, D^{i}, E^{i}, F_{0}^{i}, F_{1}^{i}, and F_{2}^{i} are the level-i components isomorphic to D^{0}, E^{0}, F_{0}^{0}, F_{1}^{0}, and F_{2}^{0}, respectively. There is also a component X which acts as the link between different rows of components participating in the operation.

To understand Figure 3.2, we need to define two new kinds of basic operations.

3.2 Definition. Let G be a computable leveled graph whose domain is co-infinite. Let L, K_{0}, K_{1}, … be components of G isomorphic to [x], [y_{0}], [y_{1}], …, respectively, where x, y_{0}, y_{1}, … ∈ ω, such that K_{0}, K_{1}, … have levels and L has no level. Let S = {K_{i} | i ∈ ω}. We define two operations, each of which takes G to a new co-infinite computable structure extending G.

• The operation S·L consists of performing the following steps, and otherwise leaving G unchanged. Create a new copy of [x] using numbers not in the domain of G. For each i ∈ ω, add an edge from the top of this new copy of [x] to the top of K_{i}.

• The operation L·S consists of performing the following steps, and otherwise leaving G unchanged. For each i ∈ ω, create a new copy of [y_{i}] using numbers not in the

\xymatrix{D^{0} \ar[d] & E^{0} \ar[d] \\ D^{0} · E^{0} & E^{0} ⊙ (F_{0}^{0}, F_{1}^{0}, F_{2}^{1})}

similarly for all levels ≡ 0 mod 4

\xymatrix{E^{1} \ar[d] & F_{0}^{1} \ar[d] \\ E^{1} · D^{1} & F_{0}^{1} ⊙ (E^{1}, F_{1}^{1}, F_{2}^{1})}

similarly for all levels ≡ 1 mod 4

\xymatrix{E^{2} \ar[d] & F_{1}^{2} \ar[d] \\ E^{2} · D^{2} & F_{1}^{2} ⊙ (E^{2}, F_{0}^{2}, F_{2}^{2})}

similarly for all levels ≡ 2 mod 4

\xymatrix{E^{3} \ar[d] & F_{2}^{3} \ar[d] \\ E^{3} · D^{3} & F_{2}^{3} ⊙ (E^{3}, F_{0}^{3}, F_{1}^{3})}

similarly for all levels ≡ 3 mod 4

[figure: X; ⋮; F_{2}^{7}; F_{1}^{6}; F_{0}^{5}; D^{4}; X; F_{2}^{3}; F_{1}^{2}; F_{0}^{1}; D^{0}; ⋮; \underbrace{…, F_{2}^{0}, D^{1}, F_{0}^{2}, F_{1}^{3}, F_{2}^{4}, D^{5}, F_{0}^{6}, F_{1}^{7}, …}; ⋮; F_{1}^{7}; F_{0}^{6}; D^{5}; F_{2}^{4}; X; F_{1}^{3}; F_{0}^{2}; D^{1}; F_{2}^{0}; ⋮]

Figure 3.2: The basic diagonalization strategy

Figure 3.2 (Continued)

[figure: \underbrace{…, F_{1}^{0}, F_{2}^{1}, D^{2}, F_{0}^{3}, F_{1}^{4}, F_{2}^{5}, D^{6}, F_{0}^{7}, …}; ⋮; F_{0}^{7}; D^{6}; F_{2}^{5}; F_{1}^{4}; X; F_{0}^{3}; D^{2}; F_{2}^{1}; F_{1}^{0}; ⋮]

[figure: \underbrace{…, F_{0}^{0}, F_{1}^{1}, F_{2}^{2}, D^{3}, F_{0}^{4}, F_{1}^{5}, F_{2}^{6}, D^{7}, …}; ⋮; D^{7}; F_{2}^{6}; F_{1}^{5}; F_{0}^{4}; X; D^{3}; F_{2}^{2}; F_{1}^{1}; F_{0}^{0}; ⋮]

domain of G. For each i ∈ ω, add an edge from the top of L to the top of the new copy of [y_{i}] and add an edge from the level(K_{i})-master node to the top of the new copy of [y_{i}].

3.3 Definition. Let G be a computable leveled graph whose domain is co-infinite. Let L and K_{0}, K_{1}, …, K_{n} be components of G isomorphic to [x] and [y_{0}], [y_{1}], …, [y_{n}], respectively, where x, y_{0}, y_{1}, …, y_{n} ∈ ω, such that K_{0}, K_{1}, …, K_{n} have levels. (It does not matter for this definition whether L has a level, although this will always be the case when we apply it.)

The operation L⊙(K_{0}, K_{1}, …, K_{n}), taking G to a new computable structure extending G, consists of performing the following steps, and otherwise leaving G unchanged. For each i ⩽ n, create a new copy of [y_{i}] using numbers not in the domain of G. For each i ⩽ n, add an edge from the top of L to the top of the new copy of [y_{i}], an edge from the top of the new copy of [y_{i}] to the top of L, and an edge from the level(K_{i})-master node to the top of the new copy of [y_{i}]. For each i, j ⩽ n, i ≠ j, add an edge from the top of the new copy of [y_{i}] to the top of the new copy of [y_{j}].

As an example of the operation in Definition 3.3, suppose that K_{0}, K_{1}, and K_{2} are copies of [2], [3], and [4], respectively. Let i, j, k be such that {i, j, k} = {0, 1, 2}. The operation K_{i} ⊙ (K_{j}, K_{k}) consists of extending K_{i} to a copy of the graph shown in Figure 3.3, adding an edge from the level(K_{j})-master node to the new copy of K_{j}, and adding an edge from the level(K_{k})-master node to the new copy of K_{k}.

[figure: •; top; •; •; •; coding location; •; •; top; •; •; •; •; coding location; •; •; top; •; •; •; •; •; coding location; •]

Figure 3.3: The result of any of [2] ⊙ ([3], [4]), [3] ⊙ ([2], [4]), or [4] ⊙ ([2], [3])

In Figure 3.2, the result of either of the operations L · S or S · L is represented by L with a line to each element of S, while the result of the operation L ⊙ (K_{0}, K_{1}, …, K_{n}) is represented simply by L ⊙ (K_{0}, K_{1}, …, K_{n}).

As we have just seen, we will be performing infinite operations in our construction. Thus, at a stage s + 1, we might add infinitely many new nodes and edges to A_{s} to obtain A_{s+1}. We will do this in such a way that the only edges in A = ⋃_{t∈ω} A_{t} between nodes of A_{s+1} are those already present in A_{s+1}.

As in Section 2, we will use special components to satisfy (3.3). The idea is similar to what we outlined above. For each finite binary string σ, there will be a strategy for satisfying (3.3) for G_{|σ|}. As before, the string σ will represent a guess as to which G_{m}, with m < |σ|, (σ ↾ m)-recover infinitely often, with σ(m) = 0 representing a guess that G_{m} (σ ↾ m)-recovers infinitely often and σ(m) = 1 representing a guess that it does not. The concept of σ-recovery will be similar to what was discussed above, although we will of course eventually give a formal definition in this case. We will not allow σ-recovery unless there is τ-recovery for all τ such that τ^{⌢}0 ⊆ σ.

For each σ ∈ 2^{<ω}, G_{|σ|} will have a σ-special component, which will change each time σ is initialized. At each stage s in the construction, we will have a guess r_{σ,s} as to which level of A behaves like level 0 of G_{|σ|}, in the same sense that, in Section 2, r_{s} was a guess as to which copy of the structure constructed in that section behaved like G.

Suppose that copies of the σ-special component of G_{|σ|} participate in an operation at a stage s+1 (we say that σ is active at stage s+1) and t+1 is the next σ-recovery stage after stage s + 1. If the component of A_{t} that is isomorphic to the special component of G_{|σ|}[t] extends the component of A_{s} that is isomorphic to the special component of G_{|σ|}[s] then r_{σ,t+1} = r_{σ,s+1}; otherwise, r_{σ,t+1} ≠ r_{σ,s+1}.

By performing operations involving the images in A of the σ-special component of G_{|σ|} (one image for each level of A), we will ensure that, for σ on the true path of the construction, if G_{|σ|} ≅ A then the σ-special component of G_{|σ|} is infinite. We will also ensure that either for some i ∈ ℤ there is a level-i component that, from some point in the construction on, always goes in the same direction as the special component of G_{|σ|}, or there is no component in A isomorphic to the special component of G_{|σ|}. As we will see, this will mean that if G_{|σ|} ≅ A then, for each j ∈ ℤ, from some stage s_{j} in the construction on, the j^{th} level of G_{|σ|} will go in the same direction as (j + i)^{th} level of A at all stages at which σ is active.

The reason that s_{j} will depend on j is that the operations in this construction will involve infinitely many components at a time. Thus, we cannot make it a requirement for σ-recovery that G_{|σ|} provide all components that will be used in the next operation to be performed at a stage at which σ is active. Instead, we will only require that G_{|σ|} provide the necessary components for a finite number of levels; each time σ recovers, the number of levels that must be provided for the next recovery will increase.

To illustrate the recovery process, consider Figure 3.4, which presents an operation that might be performed at some stage s + 1 of our construction, ignoring for now all components indexed by τ, whose role will be explained later.

Our construction will be such that A_{s} will have the following properties. For each i, j ∈ ℤ, A_{s}^{i} ≅ A_{s}^{j}. For each i ∈ ℤ, no component K of A_{s}^{i} is embeddable in another component L of A_{s} unless, for some j ∈ ℤ, L is the (unique) component of A_{s}^{j} isomorphic to K. No singleton component of A_{s}^{∗} is embeddable in another component of A_{s}.

In Figure 3.4, we are assuming that each of Z_{σ}^{0}, B_{σ}^{0}, C_{σ}^{0}, Y_{σ,0}^{0}, Y_{σ,1}^{0}, Y_{σ,2}^{0}, D^{0}, E^{0}, F_{0}^{0}, F_{1}^{0}, and F_{2}^{0} are singleton components of A_{s}^{0}, X is a singleton component of A_{s} that has no level, and S_{σ}^{0} is the copy of the σ-special component of G_{|σ|}[s] in A_{s}^{0}. For each i ∈ ℤ, Z_{σ}^{i}, B_{σ}^{i}, S_{σ}^{i}, C_{σ}^{i}, Y_{σ,0}^{i}, Y_{σ,1}^{i}, Y_{σ,2}^{i}, D^{i}, E^{i}, F_{0}^{i}, F_{1}^{i}, and F_{2}^{i} are the components of A_{s}^{i} isomorphic to Z_{σ}^{0}, B_{σ}^{0}, S_{σ}^{0}, C_{σ}^{0}, Y_{σ,0}^{0}, Y_{σ,1}^{0}, Y_{σ,2}^{0}, D^{0}, E^{0}, F_{0}^{0}, F_{1}^{0}, and F_{2}^{0}, respectively.

Suppose that s + 1 is a σ-recovery stage such that r_{σ,s+1} = 0 and we perform the operation pictured in Figure 3.4 on A_{s} to obtain A_{s+1}, and then wait for G_{|σ|} to σrecover at some stage t + 1 > s + 1. Notice that this operation preserves the relevant automorphisms of A. That is, if (A_{s}, a_{0}) ≅ (A_{s}, a_{i}) then (A_{s+1}, a_{0}) ≅ (A_{s+1}, a_{i}).

The definition of σ-recovery will be such that G_{|σ|}[s] contains a component X̂ isomorphic to X and, for some k ∈ ω and all i ∈ ℤ with |i| ⩽ k, G_{|σ|}[s] contains level-i components Ẑ^{i}, B̂^{i}, Ŝ^{i}, Ĉ^{i}, Ŷ_{0}^{i}, Ŷ_{1}^{i}, Ŷ_{2}^{i}, D̂^{i}, Ê^{i}, F̂_{0}^{i}, F̂_{1}^{i}, and F̂_{2}^{i} isomorphic to Z_{σ}^{i}, B_{σ}^{i}, S_{σ}^{i}, C_{σ}^{i}, Y_{σ,0}^{i}, Y_{σ,1}^{i}, Y_{σ,2}^{i}, D^{i}, E^{i}, F_{0}^{i}, F_{1}^{i}, and F_{2}^{i}, respectively.

Let \overline{A}_{t} be the union of (A_{t}^{∗})^{k} and A_{t}^{i} for each i ∈ ℤ such that |i| ⩽ k. Let \overline{G}_{|σ|}[t] be the union of (G_{|σ|}^{∗}[t])^{k} and G_{|σ|}^{i}[t] for each i ∈ ℤ such that |i| ⩽ k.

For i ∈ ℤ, |i| ⩽ k, let X̃, Z̃^{i}, B̃^{i}, S̃^{i}, C̃^{i}, Ỹ_{0}^{i}, Ỹ_{1}^{i}, Ỹ_{2}^{i}, D̃^{i}, Ẽ^{i}, F̃_{0}^{i}, F̃_{1}^{i}, and F̃_{2}^{i} be the intersection of the components of G_{|σ|}[t] that extend X̂, Ẑ^{i}, B̂^{i}, Ŝ^{i}, Ĉ^{i}, Ŷ_{0}^{i}, Ŷ_{1}^{i}, Ŷ_{2}^{i}, D̂^{i}, Ê^{i}, F̂_{0}^{i}, F̂_{1}^{i}, and F̂_{2}^{i}, respectively, with \overline{G}_{|σ|}[t].

The fact that G_{|σ|} σ-recovers at stage t + 1 will mean that X̃, Z̃^{i}, B̃^{i}, S̃^{i}, C̃^{i}, Ỹ_{0}^{i}, Ỹ_{1}^{i}, Ỹ_{2}^{i}, D̃^{i}, Ẽ^{i}, F̃_{0}^{i}, F̃_{1}^{i}, and F̃_{2}^{i} for |i| ⩽ k must all be isomorphic to components of \overline{A}_{t}.

Thus, since σ is not active in the interval (s + 1, t + 1), there are two possibilities. Either the σ-special component S̃^{0} of G_{|σ|}[t] is isomorphic to S_{σ}^{0} · B_{σ}^{0} or it is isomorphic to S_{σ}^{0} · C_{σ}^{0}.

In the first case, r_{σ,t+1} ≠ 0, and the copy of the σ-special component of G_{|σ|}[t] in A_{t} extends a singleton component of A_{s}. In fact, every time we have an action at stage u + 1 involving copies of the σ-special component of G_{|σ|}[u] and, for the next σrecovery stage v + 1, we have r_{σ,v+1} ≠ r_{σ,u+1}, then the copy of the σ-special component

\xymatrix{D^{0} \ar[d] & E^{0} \ar[d] \\ D^{0} · E^{0} & E^{0} ⊙ (F_{0}^{0}, F_{1}^{0}, F_{2}^{1})}

similarly for all levels ≡ 0 mod 4

\xymatrix{E^{1} \ar[d] & F_{0}^{1} \ar[d] \\ E^{1} · D^{1} & F_{0}^{1} ⊙ (E^{1}, F_{1}^{1}, F_{2}^{1})}

similarly for all levels ≡ 1 mod 4

\xymatrix{E^{2} \ar[d] & F_{1}^{2} \ar[d] \\ E^{2} · D^{2} & F_{1}^{2} ⊙ (E^{2}, F_{0}^{2}, F_{2}^{2})}

similarly for all levels ≡ 2 mod 4

\xymatrix{E^{3} \ar[d] & F_{2}^{3} \ar[d] \\ E^{3} · D^{3} & F_{2}^{3} ⊙ (E^{3}, F_{0}^{3}, F_{1}^{3})}

similarly for all levels ≡ 3 mod 4 Figure 3.4: A 3, (0, 1)-operation

Figure 3.4 (Continued)

\xymatrix{Z_{σ}^{0} \ar[d] & B_{σ}^{0} \ar[d] & S_{σ}^{0} \ar[d] & C_{σ}^{0} \ar[d] \\ Z_{σ}^{0} · B_{σ}^{0} & B_{σ}^{0} · S_{σ}^{0} & S_{σ}^{0} · C_{σ}^{0} & C_{σ}^{0} ⊙ (Y_{σ,0}^{0}, Y_{σ,1}^{0}, Y_{σ,2}^{0})}

similarly for all levels ≡ 0 mod 4

\xymatrix{B_{σ}^{1} \ar[d] & S_{σ}^{1} \ar[d] & C_{σ}^{1} \ar[d] & Y_{σ,0}^{1} \ar[d] \\ B_{σ}^{1} · Z_{σ}^{1} & S_{σ}^{1} · B_{σ}^{1} & C_{σ}^{1} · S_{σ}^{1} & Y_{σ,0}^{1} ⊙ (C_{σ}^{1}, Y_{σ,1}^{1}, Y_{σ,2}^{1})}

similarly for all levels ≡ 1 mod 4

\xymatrix{B_{σ}^{2} \ar[d] & S_{σ}^{2} \ar[d] & C_{σ}^{2} \ar[d] & Y_{σ,1}^{2} \ar[d] \\ B_{σ}^{2} · Z_{σ}^{2} & S_{σ}^{2} · B_{σ}^{2} & C_{σ}^{2} · S_{σ}^{2} & Y_{σ,1}^{2} ⊙ (C_{σ}^{2}, Y_{σ,0}^{2}, Y_{σ,2}^{2})}

similarly for all levels ≡ 2 mod 4

\xymatrix{B_{σ}^{3} \ar[d] & S_{σ}^{3} \ar[d] & C_{σ}^{3} \ar[d] & Y_{σ,2}^{3} \ar[d] \\ B_{σ}^{3} · Z_{σ}^{3} & S_{σ}^{3} · B_{σ}^{3} & C_{σ}^{3} · S_{σ}^{3} & Y_{σ,2}^{3} ⊙ (C_{σ}^{3}, Y_{σ,0}^{3}, Y_{σ,1}^{3})}

similarly for all levels ≡ 3 mod 4

Figure 3.4 (Continued)

\xymatrix{B_{τ}^{0} \ar[d] & S_{τ}^{0} \ar[d] & C_{τ}^{0} \ar[d] & Y_{τ,2}^{0} \ar[d] \\ B_{τ}^{0} · Z_{τ}^{0} & S_{τ}^{0} · B_{τ}^{0} & C_{τ}^{0} · S_{τ}^{0} & Y_{τ,2}^{0} ⊙ (C_{τ}^{0}, Y_{τ,0}^{0}, Y_{τ,1}^{0})}

similarly for all levels ≡ 0 mod 4

\xymatrix{Z_{τ}^{1} \ar[d] & B_{τ}^{1} \ar[d] & S_{τ}^{1} \ar[d] & C_{τ}^{1} \ar[d] \\ Z_{τ}^{1} · B_{τ}^{1} & B_{τ}^{1} · S_{τ}^{1} & S_{τ}^{1} · C_{τ}^{1} & C_{τ}^{1} ⊙ (Y_{τ,0}^{1}, Y_{τ,1}^{1}, Y_{τ,2}^{1})}

similarly for all levels ≡ 1 mod 4

\xymatrix{B_{τ}^{2} \ar[d] & S_{τ}^{2} \ar[d] & C_{τ}^{2} \ar[d] & Y_{τ,1}^{2} \ar[d] \\ B_{τ}^{2} · Z_{τ}^{2} & S_{τ}^{2} · B_{τ}^{2} & C_{τ}^{2} · S_{τ}^{2} & Y_{τ,0}^{2} ⊙ (C_{τ}^{2}, Y_{τ,1}^{2}, Y_{τ,2}^{2})}

similarly for all levels ≡ 2 mod 4

\xymatrix{B_{τ}^{3} \ar[d] & S_{τ}^{3} \ar[d] & C_{τ}^{3} \ar[d] & Y_{τ,1}^{3} \ar[d] \\ B_{τ}^{3} · Z_{τ}^{3} & S_{τ}^{3} · B_{τ}^{3} & C_{τ}^{3} · S_{τ}^{3} & Y_{τ,1}^{3} ⊙ (C_{τ}^{3}, Y_{τ,0}^{3}, Y_{τ,2}^{3})}

similarly for all levels ≡ 3 mod 4

[figure: X; ⋮; ⋮; F_{2}^{7}; Y_{τ,1}^{7}; Y_{σ,2}^{7}; F_{1}^{6}; Y_{τ,0}^{6}; Y_{σ,1}^{6}; F_{0}^{5}; Z_{τ}^{5}; Y_{σ,0}^{5}; D^{4}; Y_{τ,2}^{4}; Z_{σ}^{4}; X; F_{2}^{3}; Y_{τ,1}^{3}; Y_{σ,2}^{3}; F_{1}^{2}; Y_{τ,0}^{2}; Y_{σ,1}^{2}; F_{0}^{1}; Z_{τ}^{1}; Y_{σ,0}^{1}; D^{0}; Y_{τ,2}^{0}; Z_{σ}^{0}; ⋮; ⋮]

[figure: \underbrace{{…, F_{2}^{0}, D^{1}, F_{0}^{2}, F_{1}^{3}, F_{2}^{4}, D^{5}, F_{0}^{6}, F_{1}^{7}, … \atop …, Y_{σ,2}^{0}, Z_{σ}^{1}, Y_{σ,0}^{2}, Y_{σ,1}^{3}, Y_{σ,2}^{4}, Z_{σ}^{5}, Y_{σ,0}^{6}, Y_{σ,1}^{7}, …} ; …, Y_{τ,1}^{0}, Y_{τ,2}^{1}, Z_{τ}^{2}, Y_{τ,0}^{3}, Y_{τ,1}^{4}, Y_{τ,2}^{5}, Z_{τ}^{6}, Y_{τ,0}^{7}, …}]

[figure: ⋮; ⋮; F_{1}^{7}; Y_{τ,0}^{7}; Y_{σ,1}^{7}; F_{0}^{6}; Z_{τ}^{6}; Y_{σ,0}^{6}; D^{5}; Y_{τ,2}^{5}; Z_{σ}^{5}; F_{2}^{4}; Y_{τ,1}^{4}; Y_{σ,2}^{4}; X; F_{1}^{3}; Y_{τ,0}^{3}; Y_{σ,1}^{3}; F_{0}^{2}; Z_{τ}^{2}; Y_{σ,0}^{2}; D^{1}; Y_{τ,2}^{1}; Z_{σ}^{1}; F_{2}^{0}; Y_{τ,1}^{0}; Y_{σ,2}^{0}; ⋮; ⋮]

[figure: \underbrace{{…, F_{1}^{0}, F_{2}^{1}, D^{2}, F_{0}^{3}, F_{1}^{4}, F_{2}^{5}, D^{6}, F_{0}^{7}, … \atop …, Y_{σ,1}^{0}, Y_{σ,2}^{1}, Z_{σ}^{2}, Y_{σ,0}^{3}, Y_{σ,1}^{4}, Y_{σ,2}^{5}, Z_{σ}^{6}, Y_{σ,0}^{7}, …} ; …, Y_{τ,0}^{0}, Y_{τ,1}^{1}, Y_{τ,2}^{2}, Z_{τ}^{3}, Y_{τ,0}^{4}, Y_{τ,1}^{5}, Y_{τ,2}^{6}, Z_{τ}^{7}, …}]

[figure: ⋮; ⋮; F_{0}^{7}; Z_{τ}^{7}; Y_{σ,0}^{7}; D^{6}; Y_{τ,2}^{6}; Z_{σ}^{6}; F_{2}^{5}; Y_{τ,1}^{5}; Y_{σ,2}^{5}; F_{1}^{4}; Y_{τ,0}^{4}; Y_{σ,1}^{4}; X; F_{0}^{3}; Z_{τ}^{3}; Y_{σ,0}^{3}; D^{2}; Y_{τ,2}^{2}; Z_{σ}^{2}; F_{2}^{1}; Y_{τ,1}^{1}; Y_{σ,2}^{1}; F_{1}^{0}; Y_{τ,0}^{0}; Y_{σ,1}^{0}; ⋮; ⋮]

[figure: \underbrace{{…, F_{0}^{0}, F_{1}^{1}, F_{2}^{2}, D^{3}, F_{0}^{4}, F_{1}^{5}, F_{2}^{6}, D^{7}, … \atop …, Y_{σ,0}^{0}, Y_{σ,1}^{1}, Y_{σ,2}^{2}, Z_{σ}^{3}, Y_{σ,0}^{4}, Y_{σ,1}^{5}, Y_{σ,2}^{6}, Z_{σ}^{7}, …} ; …, Z_{τ}^{0}, Y_{τ,0}^{1}, Y_{τ,1}^{2}, Y_{τ,2}^{3}, Z_{τ}^{4}, Y_{τ,0}^{5}, Y_{τ,1}^{6}, Y_{τ,2}^{7}, …}]

[figure: ⋮; ⋮; D^{7}; Y_{τ,2}^{7}; Z_{σ}^{7}; F_{2}^{6}; Y_{τ,1}^{6}; Y_{σ,2}^{6}; F_{1}^{5}; Y_{τ,0}^{5}; Y_{σ,1}^{5}; F_{0}^{4}; Z_{τ}^{4}; Y_{σ,0}^{4}; X; D^{3}; Y_{τ,2}^{3}; Z_{σ}^{3}; F_{2}^{2}; Y_{τ,1}^{2}; Y_{σ,2}^{2}; F_{1}^{1}; Y_{τ,0}^{1}; Y_{σ,1}^{1}; F_{0}^{0}; Z_{τ}^{0}; Y_{σ,0}^{0}; ⋮; ⋮]

of G_{|σ|}[v] in A_{v} will extend a singleton component of A_{u}. We will make sure that if r_{σ,u} has no limit then, for each i ∈ ℤ, there are infinitely many stages u such that r_{σ,u} = i. This will guarantee that if σ is on the true path of the construction, G_{|σ|} ≅ A, and r_{σ,u} has no limit, then there is no component of A isomorphic to the σ-special component of G_{|σ|}[t].

In the second case, we can check that, for each i ∈ ℤ such that |i| ⩽ k, level i of G_{|σ|} must have gone in the same direction as level i of A with respect to those components involved in the operation under consideration.

That is, let X̌, Ž^{i}, B̌^{i}, Š^{i}, Č^{i}, Y̌_{0}^{i}, Y̌_{1}^{i}, Y̌_{2}^{i}, Ď^{i}, Ě^{i}, F̌_{0}^{i}, F̌_{1}^{i}, and F̌_{2}^{i} be the intersection of the components of A_{t} that extend X, Z_{σ}^{i}, B_{σ}^{i}, S_{σ}^{i}, C_{σ}^{i}, Y_{σ,0}^{i}, Y_{σ,1}^{i}, Y_{σ,2}^{i}, D^{i}, E^{i}, F_{0}^{i}, F_{1}^{i}, and F_{2}^{i}, respectively, with \overline{A}_{t}. All the components of A_{t} that contain copies of C_{σ}^{0} are isomorphic to either Š^{0} or Č^{0}. Since S̃^{0} and C̃^{0} have the same level, it cannot be the case that S̃^{0} ≅ C̃^{0}. Thus, since we are assuming that S̃^{0} ≅ Š^{0}, it follows that C̃^{0} ≅ Č^{0}.

Continuing to argue in this way, we see that Ỹ_{l}^{0} ≅ Y̌_{l}^{0} for each l < 3, which implies that X̃ ≅ X̌, which implies that Z̃^{0} ≅ Ž^{0}, which implies that B̃^{0} ≅ B̌^{0}.

Now, using the fact that X̃ ≅ X̌, we can check that, for i ≡ 0 mod 4 such that |i| ⩽ k, we have Z̃^{i} ≅ Ž^{i}, which implies that B̃^{i} ≅ B̌^{i}, which implies that S̃^{i} ≅ Š^{i}, which implies that C̃^{i} ≅ Č^{i}, which implies that Ỹ_{l}^{i} ≅ Y̌_{l}^{i} for each l < 3.

If i ≡ l + 1 mod 4 with l < 3 and |i| ⩽ k then, again using the fact that X̃ ≅ X̌, we can check that Ỹ_{l}^{i} ≅ Y̌_{l}^{i}, which implies that Ỹ_{m}^{i} ≅ Y̌_{m}^{i} for each m < 3, and also that C̃^{i} ≅ Č^{i}. This in turn implies that S̃^{i} ≅ Š^{i}, which implies that B̃^{i} ≅ B̌^{i}, which implies that Z̃^{i} ≅ Ž^{i}.

Similar arguments show that, for all i ∈ ℤ such that |i| ⩽ k, we have D̃^{i} ≅ Ď^{i}, Ẽ^{i} ≅ Ě^{i}, and F̃_{l}^{i} ≅ F̌_{l}^{i} for each l < 3.

Thus we see that, for each i ∈ ℤ such that |i| ⩽ k, level i of G_{|σ|} goes in the same direction as level i of A with respect to those components involved in the operation under consideration. (Since k increases with each σ-recovery, the fact that the above argument only works for the level-i components such that |i| ⩽ k will not be a problem.)

In the previous argument, the fact that r_{σ,s+1} = 0 was crucial. Indeed, suppose that r_{σ,s+1} = 1, we perform the operation described above at stage s + 1, σ then recovers at stage t+1, and r_{σ,t+1} = 1. We could not then argue as above, because from the fact that S̃^{1} ≅ Š^{1} it does not follow that X̃ ≅ X̌. Thus, to argue that, for each i ∈ ℤ, there is a stage after which level i of G_{|σ|} always goes in the same direction as level i + lim_{s} r_{σ,s} of A at stages at which σ is active, we need to make sure that, whenever we involve copies of the σ-special component of G_{|σ|} in an operation at stage s+1, the row of level-(r_{σ,s+1}) components of A that contains a copy of the σ-special component of G_{|σ|} goes to the left.

This is illustrated in Figure 3.4. Here we are assuming that the operation pictured is happening at a stage s + 1 such that r_{σ,s+1} = 0 and r_{τ,s+1} = 1 (that is why we call this a 3, (0, 1)-operation). Now if σ recovers at a stage t + 1 > s + 1 and r_{σ,t+1} = 0 then we can argue as above that if |i| is sufficiently small then level i of G_{|σ|} goes in the same direction as level i of A as far as the components involved in this operation are concerned. But also, if τ recovers at a stage t + 1 > s + 1 and r_{τ,t+1} = 1 then we can argue in much the same way that if |i| is sufficiently small then level i of G_{|τ|} goes in the same direction as level i + 1 of A as far as the components involved in this operation are concerned.

In general, whenever we perform an operation at a stage s + 1 at which the strings σ_{0}, …, σ_{k−1} are active, that operation will be an n, (r_{σ_{0},s+1}, …, r_{σ_{k−1},s+1})-operation for some n > 0, as defined below.

3.4 Definition. Let G be a computable leveled graph whose domain is co-infinite.

Let n > 0, k ⩾ 0, and d_{0}, …, d_{k−1} ∈ ℤ. Suppose that, for each i ∈ ℤ, j < k, and m < n, we have defined components Y_{j,m}^{i}, X, Z_{j}^{i}, B_{j}^{i}, S_{j}^{i}, C_{j}^{i}, D^{i}, E^{i}, and F_{m}^{i}, of which all but S_{j}^{i} are singleton components, all but X have levels, and X has no level.

The n, (d_{0}, …, d_{k−1})-operation

O_{n,(d_{0},...,d_{k−1})} ({Y_{j,m}^{i}} , X, {Z_{j}^{i}} , {B_{j}^{i}} , {S_{j}^{i}} , {C_{j}^{i}} , {D^{i}} , {E^{i}} , {F_{m}^{i}})

consists of applying the following sequences of operations to G.

• X · S_{0}, S_{1} · X, S_{2} · X, …, S_{n} · X, where

S_{m} = {Z_{j}^{d_{j}+m+p(n+1)} | j < k, p ∈ ℤ} ∪ {D^{m+p(n+1)} | p ∈ ℤ} ∪

{Y_{j,q}^{d_{j}+m+q+1+p(n+1)} | j < k, p ∈ ℤ, q < n} ∪
{F_{q}^{m+q+1+p(n+1)} | p ∈ ℤ, q < n} .

• For each i ≡ 0 mod (n + 1) in ℤ:

D^{i} · E^{i}, E^{i} ⊙ (F_{0}^{i}, …, F_{n−1}^{i}) .

• For each j < k and i ≡ d_{j} mod (n + 1) in ℤ:

Z_{j}^{i} · B_{j}^{i}, B_{j}^{i} · S_{j}^{i}, S_{j}^{i} · C_{j}^{i}, C_{j}^{i} ⊙ (Y_{j,0}^{i}, …, Y_{j,n−1}^{i}) .

• For each i ∈ ℤ such that i ≡ l + 1 mod (n + 1) with l < n:

E^{i} · D^{i}, F_{l}^{i} ⊙ (E^{i}, F_{0}^{i}, …, F_{l−1}^{i}, F_{l+1}^{i}, …, F_{n−1}^{i}) .

• For each j < k and i ∈ ℤ such that i ≡ l + d_{j} + 1 mod (n + 1) with l < n:

B_{j}^{i} · Z_{j}^{i}, S_{j}^{i} · B_{j}^{i}, C_{j}^{i} · S_{j}^{i}, Y_{j,l}^{i} ⊙ (C_{j}^{i}, Y_{j,0}^{i}, …, Y_{j,l−1}^{i}, Y_{j,l+1}^{i}, …, Y_{j,n−1}^{i}) .

Note that this definition allows for the case k = 0, in which the only components involved in the operation are X and the D^{i}, E^{i}, and F_{m}^{i}.

We now discuss the version of the catch-up procedure that will be used in our construction. For each stage s, we define a subgraph T_{σ,s} of the σ-special component of G_{|σ|}. Whenever r_{σ,s+1} ≠ r_{σ,s}, we define T_{σ,s+1} to be the entire σ-special component of G_{|σ|}[s]. Otherwise, we define T_{σ,s+1} = T_{σ,s}. Whenever copies of the σ-special component of G_{|σ|} are involved in an operation and σ later recovers at a stage t + 1, we perform a T_{σ,t+1}-catch-up operation on A_{s}, as defined below. (Copies of [10m + 9] will not be used for any other purpose in the construction.)

3.5 Definition. Let G be a computable leveled graph with co-infinite domain that contains copies of [10m + 9] for only finitely many m ∈ ω.

Let T be a subgraph of G. Suppose that there are finitely many level-0 components L_{0,0}, …, L_{0,n} of G that contain a copy of T and that each L_{0,m}, m ⩽ n, is a copy of [P_{m}] for some finite P_{m} ⊂ ω. Let P = ⋃_{m⩽n} P_{m}.

For i ∈ ℤ, let L_{i,0}, …, L_{i,n} be the components of G^{i} isomorphic to L_{0,0}, …, L_{0,n}, respectively.

Let l_{0}, …, l_{n} be the n + 1 least numbers of the form 10m + 9, m ∈ ω, such that G does not contain copies of any of [l_{0}], …, [l_{n}].

The T -catch-up operation taking G to a new computable structure extending G consists of extending each L_{i,m}, i ∈ ℤ, m ⩽ n, to a copy of [P ∪ {l_{m}}], using numbers not in the domain of G.

Performing a T_{σ,t+1}-catch-up operation on A_{s} will count as σ being active, which means that we must then wait for σ-recovery before allowing σ to be active again.

If σ is on the true path of the construction and r_{σ,s} comes to a limit, then T_{σ,s} comes to a limit T. It is not hard to see that, in this case, by performing catch-up operations as described, we guarantee that every component of A that contains a copy of T is infinite, and that all such components are isomorphic. This will be enough to ensure that (3.2) is satisfied, while at the same time helping us to construct the computable isomorphisms needed to satisfy (3.3), because it will mean that if G_{|σ|} ≅ A then any embedding of a copy of T in A into G_{|σ|} can be extended to an isomorphism from A to G_{|σ|}.

We will separate the stages at which we attempt to satisfy the R-requirements from the stages at which we perform catch-up operations, reserving the even stages for the former purpose and the odd ones for the latter. To guarantee that every σ on the true path is active at infinitely many even stages and infinitely many odd stages, we will call recovery at odd stages phase-1 recovery and recovery at even stages phase-2 recovery, and will require that phase-1 σ-recovery stages and phase-2 σ-recovery stages alternate.

There will be multiple strategies for satisfying each requirement R_{⟨e,i⟩}, one strategy R_{σ} for each σ ∈ 2^{<ω} such that |σ| = ⟨e, i⟩. Each of these strategies will work with a different set of components, which will be subject to initialization. If σ is accessible at some stage 2s + 2 in the construction and no requirements of stronger priority require attention, then R_{σ} will have a chance to act as described above. If it does, then copies of the τ-special components of G_{|τ|}[2s + 1] will be involved in the operation performed at stage 2s + 2 if and only if τ^{⌢}0 ⊆ σ, that is, if and only if 2s + 2 is a τ-recovery stage.

We now give a few more definitions and conventions which will be used below.

Fix a computable one-to-one function from 2^{<ω} onto ω and let ⌜σ⌝ denote the image under this function of the string σ. Fix a computable function ξ from ω onto ℤ such that, for each i ∈ ℤ, there are infinitely many n ∈ ω for which ξ(n) = i.

3.6 Definition. Let G be a directed graph. We denote by (G)_{σ} the subgraph of G consisting of those components C of G that satisfy both of the following conditions.

1. C is not isomorphic to [x] for any x ∈ ω.

2. C contains a copy of [10⟨⌜σ⌝, j⟩ + l], j ∈ ω, l ∈ {2, 3, 4, 5, 6, 7}, or a copy of [10⟨⌜σ⌝, j, k⟩ + l], j, k ∈ ω, l ∈ {1, 8}.

Define (G)_{⊇σ} = ⋃_{τ⊇σ}(G)_{τ}.

In the particular case of G^{∗}, we will wish to define (G^{∗})_{σ} somewhat differently.

3.7 Definition. Let G be a leveled graph. We denote by (G^{∗})_{σ} the subgraph of G consisting of the non-singleton components of G^{∗} that contain a copy of [10⟨⌜σ⌝, j⟩], j ∈ ω. Let n, r ∈ ω. We denote by (G^{∗})_{σ}^{n,r} the subgraph of G consisting of the nonsingleton components of (G^{∗})^{n,r} that contain a copy of [10⟨⌜σ⌝, j⟩], j ∈ ω. If r = 0 then we write simply (G^{∗})_{σ}^{n}.

Define (G^{∗})_{⊇σ} = ⋃_{τ⊇σ}(G^{∗})_{τ} and (G^{∗})_{⊇σ}^{n,r} = ⋃_{τ⊇σ}(G^{∗})_{τ}^{n,r}. If r = 0 then we write simply (G^{∗})_{⊇σ}^{n}.

Let k be the number of times σ has been initialized before stage t. Suppose there is a least stage s ⩽ t such that G_{|σ|}[s] has a level-0 component K isomorphic to [10⟨⌜σ⌝, k⟩+3]. We call the component of G_{|σ|}[t] that extends K the σ-special component of G_{|σ|}[t]. If σ is initialized only finitely often, say k many times, and there is a least stage s such that G_{|σ|}[s] has a level-0 component K isomorphic to [10⟨⌜σ⌝, k⟩ + 3] then we call the component of G_{|σ|} that extends K the σ-special component of G_{|σ|}.

3.1 The Construction

We now proceed with the construction of A. We will start with a computable structure A^{0} with co-infinite domain. To ensure that we can carry out the construction, we require that, when we add elements to the domain of A_{s} at stage s + 1 to get A_{s+1}, we do this in such a way that A_{s+1} remains co-infinite. To ensure that A is computable, we require that the collection of sets (|A_{s+1}| − |A_{s}|)_{s∈ω} be uniformly computable.

stage 0. Let A_{0} be a computable leveled graph with co-infinite domain consisting of the following nodes and edges in addition to the ones required by Definition 3.1.

1. For each i ∈ ℤ, k ∈ ω, and 0 < l < 9, a copy of [10k + l] with an edge from the i-master node to its top.

2. For each k ∈ ω, a copy of [10k].

For each σ ∈ 2^{<ω}, let r_{σ,0} = 0 and T_{σ,0} = ∅.

stage 2s + 1. For σ ∈ 2^{<ω}, let recov(σ, 2s) be the number of σ-recovery stages before stage 2s + 1. Define the string σ[2s + 1] ∈ 2^{[0,s]} by recursion as follows, beginning with n = 0. Let σ = σ[2s + 1] ↾ n. Say that 2s + 1 is a phase-1 σ-recovery stage and that σ is semi-recovered if all of the following conditions hold.

1. σ is not currently semi-recovered.

2. Every τ such that τ^{⌢}0 ⊆ σ has fully recovered (defined below) at least |σ| + 1 many times.

3. G_{n}[2s] has a σ-special component isomorphic to some component of A_{2s}^{0}.

4. For each i ∈ ℤ such that |i| ⩽ recov(σ, 2s), (G_{n}^{i}[2s])_{σ} ≅ (A_{2s}^{0})_{σ}.

5. For each i ∈ ℤ such that |i| ⩽ recov(σ, 2s), (G_{n}^{i}[2s])_{⊇σ^{⌢}0} ≅ (A_{2s}^{0})_{⊇σ^{⌢}0}.

6. (G_{n}^{∗}[2s])_{⊇σ^{⌢}0}^{recov(σ,2s)} ≅ (A_{2s}^{∗})_{⊇σ^{⌢}0}^{recov(σ,2s)}.

If 2s + 1 is a σ-recovery stage then let σ[2s + 1](n) = 0. Otherwise, let σ[2s + 1](n) = 1.

For each σ such that 2s + 1 is a σ-recovery stage, proceed as follows. Let i = r_{σ,2s}. Let S_{σ,2s} be the component of A_{2s}^{i} that is isomorphic to the σ-special component of G_{|σ|}[2s]. If 2s + 1 is either the first σ-recovery stage ever or the first σ-recovery stage since the last time σ was initialized then let r_{σ,2s+1} = 0 and T_{σ,2s+1} = S_{σ,2s}. Otherwise, proceed as follows. Let 2t + 2 be the last σ-recovery stage before stage 2s + 1. If S_{σ,2s} extends S_{σ,2t+1} then let r_{σ,2s+1} = i and T_{σ,2s+1} = T_{σ,2s}; otherwise, declare 2s + 1 to be a σ-change stage, let n be the number of σ-change stages before stage 2s + 1, let r_{σ,2s+1} = ξ(n), and let T_{σ,2s+1} = S_{σ,2s}.

For each σ ∈ 2^{<ω} such that 2s + 1 is not a σ-recovery stage, let r_{σ,2s+1} = r_{σ,2s} and T_{σ,2s+1} = T_{σ,2s}.

Declare each σ to the right of σ[2s + 1] to have been initialized. This includes declaring σ to be neither semi-recovered nor fully recovered.

Proceed as follows to obtain A_{2s+1} from A_{2s}. For each σ ∈ 2^{<ω} such that 2s + 1 is a σ-recovery stage, perform the T_{σ,2s+1}-catch-up operation and say that σ is active at stage 2s + 1.

stage 2s + 2. For σ ∈ 2^{<ω}, let recov(σ, 2s + 1) be the number of σ-recovery stages before stage 2s + 2, let init(σ, 2s + 1) be the number of times σ has been initialized before stage 2s + 2, and let c(σ, 2s + 1) = max(recov(σ, 2s + 1), init(σ, 2s + 1)).

Define the string σ[2s + 2] ∈ 2^{[0,s]} by recursion as follows, beginning with n = 0. Say that 2s + 2 is a phase-2 σ-recovery stage and that σ is fully recovered (and hence not semi-recovered) if all of the following conditions hold.

1. σ is currently semi-recovered.

2. The σ-special component of G_{n}[2s + 1] is isomorphic to some component of A_{2s+1}^{0}.

3. For each i ∈ ℤ such that |i| ⩽ recov(σ, 2s + 1), (G_{n}^{i}[2s + 1])_{σ} ≅ (A_{2s+1}^{0})_{σ}.

4. For each i ∈ ℤ such that |i| ⩽ recov(σ, 2s + 1), (G_{n}^{i}[2s + 1])_{⊇σ^{⌢}0} ≅ (A_{2s+1}^{0})_{⊇σ^{⌢}0}.

5. If τ ⊇ σ^{⌢}0 has not yet fully recovered since the last time it was initialized and |τ| ⩽ recov(σ, 2s+1) then, for each i ∈ ℤ such that |i| ⩽ recov(σ, 2s+1), G_{n}^{i}[2s+1] has a component isomorphic to [10⟨⌜τ⌝, init(τ, 2s + 1)⟩ + 3].

6. Let τ be such that either τ = σ or both τ ⊇ σ^{⌢}0 and |τ| ⩽ recov(σ, 2s + 1). Let i ∈ ℤ be such that |i| ⩽ recov(σ, 2s + 1). For each m < c(σ, 2s + 1), there is a component of G_{n}^{i}[2s + 1] isomorphic to [10⟨⌜τ⌝, c(τ, 2s + 1), m⟩ + 1]. For each l ∈ {2, 4, 5}, there is a component of G_{n}^{i}[2s + 1] isomorphic to [10⟨⌜τ⌝, c(τ, 2s + 1)⟩ + l].

7. Let τ be such that R_{|τ|} has not yet been satisfied (defined below), τ ⊇ σ^{⌢}0, and |τ| ⩽ recov(σ, 2s + 1). Let i ∈ ℤ be such that |i| ⩽ recov(σ, 2s + 1). There is a component of G_{n}[s] isomorphic to [10⟨⌜τ⌝, init(τ, 2s+1)⟩]. For each l ∈ {6, 7}, there is a component of G_{n}^{i}[s] isomorphic to [10⟨⌜τ⌝, init(τ, 2s + 1)⟩ + l]. For each m < π_{1}(⌜τ⌝), there is a component of G_{n}^{i}[s] isomorphic to [10⟨⌜τ⌝, init(τ, 2s+1), m⟩+8].

If 2s + 2 is a σ-recovery stage then let σ[2s + 2](n) = 0. Otherwise, let σ[2s + 2](n) = 1.

For each σ such that 2s + 2 is a σ-recovery stage, proceed as follows. Let i = r_{σ,2s+1}. Let S_{σ,2s+1} be the component of A_{2s+1}^{i} that is isomorphic to the σ-special component of G_{|σ|}[2s + 1]. Let 2t + 1 be the last σ-recovery stage before stage 2s + 2. If S_{σ,2s+1} extends S_{σ,2t} then let r_{σ,2s+2} = i and T_{σ,2s+2} = T_{σ,2s+1}; otherwise, declare 2s+2 to be a σ-change stage, let n be the number of σ-change stages before stage 2s + 2, let r_{σ,2s+2} = ξ(n), and let T_{σ,2s+2} = S_{σ,2s+1}.

For each σ ∈ 2^{<ω} such that 2s + 2 is not a σ-recovery stage, let r_{σ,2s+2} = r_{σ,2s+1} and T_{σ,2s+2} = T_{σ,2s+1}.

Declare each σ to the right of σ[2s + 2] to have been initialized. This includes declaring σ to be neither semi-recovered nor fully recovered.

Say that R_{σ}, σ ⊆ σ[2s + 2], requires attention if R_{|σ|} has not yet been satisfied, π_{1}(|σ|) ⩽ c(τ, 2s + 1) for all τ such that τ^{⌢}0 ⊆ σ, and, for the coding locations x and y of the (unique) copies of [10⟨⌜σ⌝, init(σ, 2s + 1)⟩ + 7] in A_{2s+1}^{0} and A_{2s+1}^{π_{1}(|σ|)}, respectively, Φ_{π_{0}(|σ|)}(x)[s]↓= y.

Let e be the least number less than s such that R_{σ[2s+2](e)} requires attention. (If no such e exists then end the stage.) If σ^{⌢}0 ⊆ σ[2s + 2] then say that σ is active at stage 2s + 2.

Let X_{2s+1} be the component of A_{2s+1} isomorphic to [10⟨⌜σ[2s + 2](e)⌝, init(σ[2s + 2](e), 2s + 1)⟩]. For each i ∈ ℤ and m < π_{1}(e), let D_{2s+1}^{i}, E_{2s+1}^{i}, and F_{m,2s+1}^{i} be the components of A_{2s+1}^{i} isomorphic to [10⟨⌜σ[2s + 2](e)⌝, init(σ[2s + 2](e), 2s + 1)⟩ + 6], [10⟨⌜σ[2s+2](e)⌝, init(σ[2s+2](e), 2s+1)⟩+7], and [10⟨⌜σ[2s+2](e)⌝, init(σ[2s+2](e), 2s+ 1), m⟩ + 8], respectively.

Let σ_{0}, …, σ_{k−1} be all the strings that are active at stage 2s + 2. For each j < k, i ∈ ℤ, and m < π_{1}(e), let Y_{σ_{j},m,2s+1}^{i}, Z_{σ_{j},2s+1}^{i}, B_{σ_{j},2s+1}^{i}, and C_{σ_{j},2s+1}^{i} be the level-i components of A_{2s+1} isomorphic to [10⟨⌜σ_{j}⌝, c(σ_{j}, 2s + 1), m⟩ + 1], [10⟨⌜σ_{j}⌝, c(σ_{j}, 2s + 1)⟩ + 2], [10⟨⌜σ_{j}⌝, c(σ_{j}, 2s + 1)⟩ + 4], and [10⟨⌜σ_{j}⌝, c(σ_{j}, 2s + 1)⟩ + 5], respectively. For each j < k and i ∈ ℤ, let S_{σ_{j},2s+1}^{i} be the level-i component of A_{2s+1} isomorphic to S_{σ_{j},2s+1}.

For j < k, let d_{j} = r_{σ_{j},2s+2}. Perform

O_{π_{1}(e),(d_{0},...,d_{k−1})}({Y_{σ_{j},m,2s+1}^{i}}, X_{2s+1}, {Z_{σ_{j},2s+1}^{i}}, {B_{σ_{j},2s+1}^{i}}, {S_{σ_{j},2s+1}^{i}}, {C_{σ_{j},2s+1}^{i}}, {D_{2s+1}^{i}}, {E_{2s+1}^{i}}, {F_{m,2s+1}^{i}})

on A_{2s+1} to get A_{2s+2}. Declare R_{e} to be satisfied.

This completes the construction. Let A = ⋃_{s∈ω} A_{s}. Since the collection of sets (|A_{s+1}| − |A_{s}|)_{s∈ω} is uniformly computable, A is computable. We now wish to argue that properties (3.1)–(3.3) are satisfied. Theorem 1.4 will then follow immediately.

3.2 Verification

Define the true path TP of the construction to be the leftmost path of 2^{ω} such that there are infinitely many stages s with σ[s] ∈ TP. For each i ∈ ℤ, let a_{i} be the i-master node of A.

We begin by showing that property (3.2) is satisfied.

3.8 Lemma. If σ ∈ TP then R_{σ} requires attention only finitely often.

Proof. Assume by induction that there is a stage s such that, for all τ ⊊ σ, R_{τ} does not require attention after stage s. Let 2t + 2 > s be such that R_{σ} requires attention at stage 2t+2. Then, by definition, σ ⊆ σ[2t+2], and hence R_{|σ|} is satisfied at stage 2t+2, which implies that R_{σ} will never again require attention.

3.9 Lemma. Let e = ⟨j, i⟩. If R_{e} is ever satisfied then Φ_{j} is not an isomorphism from (A, a_{0}) to (A, a_{i}).

Proof. Suppose that R_{e} is satisfied at stage 2s + 2. Let σ = σ[2s + 2](e). Let K and L be the components of A_{2s+1}^{0} and A_{2s+1}^{i}, respectively, that are isomorphic to [10⟨⌜σ⌝, init(σ, 2s + 1)⟩ + 7], and let x and y be the coding locations of K and L, respectively. Since R_{σ} requires attention at stage 2s + 2, Φ_{j}(x)↓= y.

Let K′ and L′ be the components of A^{0} and A^{i} that extend K and L, respectively. The operation performed at stage 2s + 2 guarantees that K′ ≇ L′, so no isomorphism from (A, a_{0}) to (A, a_{i}) can take x to y.

3.10 Lemma. For every i, j ∈ ℤ such that i ≠ j, (A, a_{i}) is not computably isomorphic to (A, a_{j}).

Proof. Since, given k, l ∈ ℤ such that k ≠ l, any automorphism of A taking a_{k} to a_{l} takes a_{0} to a_{i} for some i ≠ 0, it is enough to show that, for each j ∈ ω and i ∈ ℤ, i ≠ 0, Φ_{j} is not an isomorphism from (A, a_{0}) to (A, a_{i}).

Fix j ∈ ω and let e = ⟨j, i⟩. Let σ = TP(e), let s be a stage after which no R_{τ}, τ ⊊ σ, requires attention and such that σ is not initialized after stage s, and let k be the total number of times σ is initialized. If R_{e} is ever satisfied then, by Lemma 3.9, we are done. So suppose that R_{e} is never satisfied.

This means that the components K and L of A_{0}^{0} and A_{0}^{i}, respectively, isomorphic to [10⟨⌜σ⌝, k⟩ + 7] never participate in operations. Let x and y be the coding locations of K and L, respectively. Since R_{e} is never satisfied, R_{σ} never requires attention after stage s. So it cannot be the case that Φ_{j}(x) ↓= y. But K and L are the unique copies of [10⟨⌜σ⌝, k⟩ + 7] in A^{0} and A^{i}, respectively, so any isomorphism from (A, a_{0}) to (A, a_{i}) must take x to y.

In showing that (3.1) and (3.3) are satisfied, we will need a few easily checked facts about the construction. We say that a component of A participates in an operation at stage s + 1 if it extends a component of A_{s} that participates in an operation at stage s + 1.

Let G and H be leveled graphs, let K and L be components of G and H, respectively, and let i ∈ ℤ. We say that K is i-isomorphic to L if there is an isomorphism f : K ≅ L such that, for all x ∈ K and j ∈ ℤ, if there is an edge from the j-master node of G to x then there is an edge from the (j + i)-master node of H to f(x).

3.11 Lemma. Let K and L be distinct components of A_{s}. If K is not a copy of [10k+l] for any k ∈ ω and l ∈ {1, 2, 6, 8} then K and L are not extended by the same component of A. If K and L are extended by the same component M of A then M is a component of A^{∗}.

3.12 Lemma. Every component of A has a level unless it contains a copy of [10k] for some k ∈ ω.

3.13 Lemma. For each s ∈ ω and i, j ∈ ℤ, (A_{s}, a_{i}) ≅ (A_{s}, a_{j}) and no component K of A_{s} is embeddable in another component L of A_{s} unless K is k-isomorphic to L for some k ∈ ℤ, k ≠ 0. Furthermore, if a component of A_{s}^{i} participates in an operation at stage s + 1 then so does the (unique) isomorphic component of A_{s}^{j}.

3.14 Lemma. A component of A that does not contain a copy of [10k] for any k ∈ ω is infinite if and only if it participates in operations infinitely often.

3.15 Lemma. Let k, j ∈ ω and σ ∈ 2^{<ω}. Any component of A containing a copy of [10k], [10⟨⌜σ⌝, j, k⟩ + l], l ∈ {1, 8}, or [10⟨⌜σ⌝, j⟩ + l], l ∈ {2, 6, 7}, can participate in an operation at most once. Any component of A^{i} containing a copy of [10⟨⌜σ⌝, j⟩ + l], l ∈ {3, 4, 5}, can participate in operations only at stages at which σ is active.

Note that, since A_{0} contains only one copy of each [10k], k ∈ ω, Lemma 3.15 implies that, for each k ∈ ω, there is at most one stage at which a copy of [10k] participates in an operation.

3.16 Lemma. Let K be an infinite component of A that contains a copy of [10k] for some K ∈ ω and let m ∈ ω. Then K ∩ (A^{∗})^{m} is not embeddable in any component L ≠ K of A unless K and L are i-isomorphic for some i ∈ ℤ, i ≠ 0.

3.17 Lemma. If σ is initialized at stage s + 1 then no components of (A)_{σ} that participate in operations at stages before stage s + 1 can participate in an operation after stage s.

3.18 Lemma. Suppose that r_{σ,s} = i ≠ r_{σ,s+1}. Of all the components of (A^{i})_{σ} that participate in operations at stages before stage s + 1, the only one that can participate in an operation after stage s is the one that extends S_{σ,s}.

3.19 Lemma. Let u be a stage after which σ is never initialized. Let s + 1 > u be a σ-recovery stage that is not the first such stage after u. Let t + 1 be the last σ-recovery stage before stage s + 1. If r_{σ,s} = i ≠ r_{σ,s+1} then S_{σ,s} extends either B_{σ,2u+1}^{i} or C_{σ,2u+1}^{i} for some 2u + 1 ∈ [t, s).

3.20 Lemma. Let T be a subgraph of A. If components K and L of A, each containing a copy of T, are involved in T -catch-up operations infinitely often, then K and L are infinite and K ≅ L.

3.21 Lemma. Let σ ∈ TP and suppose that lim_{s} r_{σ,s} exists. Then T_{σ,s} comes to a limit T and every infinite component of (A_{s})_{σ} that does not contain a copy of [10k] for any k ∈ ω contains a copy of T.

We now turn to showing that property (3.1) is satisfied. This requires us to characterize the infinite components of A.

3.22 Lemma. Let σ ∈ 2^{<ω}. If σ^{⌢}0 is to the left of TP then no component of (A)_{σ} is infinite unless it contains a copy of [10k] for some k ∈ ω.

Proof. If σ^{⌢}0 is to the left of TP then σ is active only finitely often, so the lemma follows from Lemmas 3.14 and 3.15.

3.23 Lemma. Let σ ∈ 2^{<ω}. If σ is to the right of TP then no component of (A)_{σ} is infinite unless it contains a copy of [10k] for some k ∈ ω.

Proof. This follows immediately from Lemmas 3.14 and 3.17.

3.24 Lemma. Let σ ∈ 2^{<ω} be such that σ^{⌢}0 ∈ TP. If r_{σ,s} does not have a limit then no component of (A)_{σ} is infinite unless it contains a copy of [10k] for some k ∈ ω.

Proof. By Lemma 3.12, it is enough to show that, for each i ∈ ℤ, no component of (A^{i})_{σ} is infinite.

Let i ∈ ℤ. If s is the (n + 1)^{st} σ-change stage then r_{σ,s} = ξ(n). Thus there are infinitely many stages s such that r_{σ,s} = i.

Suppose that r_{σ,s} = i ≠ r_{σ,s+1}, and let t + 1 be the last σ-recovery stage before stage s + 1. By Lemma 3.18, of all the components of (A^{i})_{σ} that have participated in operations at stages before stage s+1, the only one that can participate in an operation after stage s is the component L that extends S_{σ,s}. By Lemma 3.19, L extends either B_{σ,2u+1}^{i} or C_{σ,2u+1}^{i} for some 2u+1 ∈ [t, s). But, for all 2u+1 ∈ [t, s), B_{σ,2u+1}^{i} and C_{σ,2u+1}^{i} are singleton components, and hence did not participate in an operation at any stage before stage t + 1.

Thus, no component of (A^{i})_{σ} that participates in an operation before stage t + 1 can do so again after stage s. The lemma now follows from Lemma 3.14.

3.25 Lemma. Let k ∈ ω. There are finitely many components K_{0}, …, K_{n} of A that contain a copy of [10k], and these can be chosen so that K_{j} is i-isomorphic to K_{k} for all j, k ⩽ n and i ∈ ℤ such that i ≡ k − j mod (n + 1).

Proof. Let K be the copy of [10k] in A_{0}. If K never participates in an operation then the lemma is trivially true with n = 0 and K_{0} = K. Otherwise, there is a stage 2s + 2 such that K participates in an operation at stage 2s + 2 and, by Lemma 3.15, for any t ≠ 2s + 2, no component of A that contains a copy of [10k] participates in an operation at stage t. The lemma now follows easily from the definition of the operation performed at stage 2s + 2.

3.26 Lemma. Let σ be such that σ^{⌢}0 ∈ TP and lim_{s} r_{σ,s} exists. There are infinitely many infinite components of (A)_{σ} that do not contain a copy of [10k] for any k ∈ ω. Let K_{0}, K_{1}, … be all such components. Each K_{j}, j ∈ ω, has a level. For each i ∈ ℤ there are infinitely many j ∈ ω such that level(K_{j}) = i. For all j, k ∈ ω, K_{j} ≅ K_{k}.

Proof. Let u be a stage after which σ is never initialized and such that r_{σ,t} = lim_{s} r_{σ,s} for all t > u. Let 2s + 1 be the first phase-1 σ-recovery stage after stage u and let T = T_{σ,2s+1}. Since the σ-special component of G_{|σ|}[2s] contains a copy of T, for each phase-2 σ-recovery stage 2t + 2 after stage 2s + 1, each level of A_{2t+2} has a component that contains a copy of T and extends a singleton component of A_{2t+1}. Thus there are infinitely many components K_{0}, K_{1}, … that contain a copy of T. Furthermore, each K_{j}, j ∈ ω, has a level, and for each i ∈ ℤ, there are infinitely many j ∈ ω such that level(K_{j}) = i.

For each phase-1 σ-recovery stage 2t+1 > 2s+1, we have T_{σ,2t+1} = T, so K_{0}, K_{1}, … are involved in T -catch-up operations infinitely often. Thus, by Lemma 3.20, K_{0}, K_{1}, … are infinite and K_{j} ≅ K_{k} for all j, k ∈ ω.

We are left with showing that any component of (A)_{σ} that does not contain a copy of T or a copy of [10k] for any k ∈ ω is finite. By Lemma 3.14, it is enough to show that any component of (A)_{σ} that does not contain a copy of T participates in operations only finitely often. But the only components of (A)_{σ} that participate in an operation at an odd stage after stage 2s+1 are ones that contain a copy of T, while for 2t+2 > 2s+1, the only non-singleton components of (A_{2t+1})_{σ} that participate in an operation at stage 2t+2 are the ones that are isomorphic to the special component of G_{|σ|}[2t + 1], and therefore contain a copy of T.

3.27 Lemma. For every i ∈ ℤ, (A, a_{i}) ≅ (A, a_{0}).

Proof. By Lemma 3.13, it is enough to define a 1–1 map f from the set of infinite components of A onto itself such that, for each infinite component K of A, f(K) is i-isomorphic to K.

Let k ∈ ω be such that a copy of [10k] participates in an operation at some point in the construction, and let K_{0}, …, K_{n} be as in Lemma 3.25. For j ⩽ n, let k ⩽ n be such that k − j ≡ i mod (n + 1) and define f(K_{j}) = K_{k}.

Let σ be such that σ^{⌢}0 ∈ TP and lim_{s} r_{σ,s} exists. For each j ∈ ℤ, let K_{0}^{j}, K_{1}^{j}, … be a list of all infinite components of (A^{j})_{σ} that do not contain a copy of [10k] for any k ∈ ω. By Lemma 3.26, each such list is infinite. For j ∈ ℤ and n ∈ ω, define f(K_{n}^{j}) = K_{n}^{j+i}.

By Lemmas 3.22, 3.23, and 3.24, f is defined on all infinite components of A. By Lemmas 3.25 and 3.26, f is 1–1 and onto, and, for each infinite component K of A, f(K) is i-isomorphic to K.

We are left with showing that property (3.3) is satisfied. We begin by showing that if σ ∈ TP and G_{|σ|} ≅ A, then lim_{s} r_{σ,s} is well-defined.

3.28 Lemma. If σ ∈ TP and G_{|σ|} ≅ A, then there are infinitely many σ-recovery stages, and hence the σ-special component of G_{|σ|} is infinite.

Proof. If σ ∈ TP and G_{|σ|} ≅ A, then G_{|σ|} has a σ-special component. Assume for a contradiction that there are only m many σ-recovery stages. Let s_{0} be the last σrecovery stage. (If there are no σ-recovery stages then let s_{0} be the first stage at which G_{|σ|} has a σ-special component.) Since σ is not active at any stage that is not a σrecovery stage, σ is not active at any stage t ⩾ s_{0}. By the definition of TP, there is a stage s ⩾ s_{0} by which every τ such that τ^{⌢}0 ⊆ σ has fully recovered at least |σ| + 1 many times and such that σ is not initialized at any stage greater than or equal to s.

There are two cases.

Case 1. Suppose σ is not semi-recovered at stage s. Then the first condition in the definition of phase-1 σ-recovery stage is met at every stage greater than or equal to s.

By the choice of s, the second condition in the definition of phase-1 σ-recovery stage is met at every stage greater than or equal to s.

Consider the components of A^{0} that contain a copy of the σ-special component of G_{|σ|}. By Lemma 3.15, each such component is finite. Thus if the third condition in the definition of phase-1 σ-recovery stage is not eventually satisfied after stage s, then the σ-special component of G_{|σ|} is not isomorphic to any component of A^{0}.

Now consider (A^{0})_{σ}. Again by Lemma 3.15, (A^{0})_{σ} is finite. So, since there are only finitely many i ∈ ℤ such that |i| ⩽ recov(σ, s), if the fourth condition in the definition of phase-1 σ-recovery stage is not eventually satisfied after stage s, then (G_{|σ|}^{i})_{σ} ≇ (A^{0})_{σ} for some i ∈ ℤ.

Since we are assuming that there are only finitely many σ-recovery stages, σ^{⌢}1 ∈ TP. Thus it follows from Lemmas 3.14 and 3.15 that (A_{s}^{0})_{⊇σ^{⌢}0} is finite. So, since there are only finitely many i ∈ ℤ such that |i| ⩽ recov(σ, s), if the fifth condition in the definition of phase-1 σ-recovery stage is not eventually satisfied after stage s, then (G_{|σ|}^{i})_{⊇σ^{⌢}0} ≇ (A^{0})_{⊇σ^{⌢}0} for some i ∈ ℤ.

Since we are assuming that σ^{⌢}0 is to the left of TP, (A_{s}^{∗})_{⊇σ^{⌢}0}^{recov(σ,s)} is finite. So if the last condition in the definition of phase-1 σ-recovery stage is not eventually satisfied after stage s, then (G_{|σ|}^{∗})_{⊇σ^{⌢}0} ≇ (A^{∗})_{⊇σ^{⌢}0}.

Case 2. Suppose σ is semi-recovered at stage s. Then the first condition in the definition of phase-2 σ-recovery stage is met at every stage greater than or equal to s.

By the same arguments as above, we have the following facts. If the second condition in the definition of phase-2 σ-recovery stage is not eventually satisfied after stage s, then the σ-special component of G_{|σ|} is not isomorphic to any component of A^{0}. If the third condition in the definition of phase-2 σ-recovery stage is not eventually satisfied after stage s, then (G_{|σ|}^{i})_{σ} ≇ (A^{0})_{σ} for some i ∈ ℤ. If the fourth condition in the definition of phase-2 σ-recovery stage is not eventually satisfied after stage s, then (G_{|σ|}^{i})_{⊇σ^{⌢}0} ≇ (A^{0})_{⊇σ^{⌢}0} for some i ∈ ℤ.

Since we are assuming that σ^{⌢}0 is to the left of TP, there is a stage t ⩾ s after which no τ such that τ ⊇ σ^{⌢}0 is initialized. Any such τ that has not fully recovered since the last time it was initialized never again recovers, and hence there is a component of A^{0} isomorphic to [10⟨⌜τ⌝, init(τ, t)⟩+3]. Since there are only finitely many τ and i ∈ ℤ such that |τ| , |i| ⩽ recov(σ, s), if the fifth condition in the definition of phase-2 σ-recovery stage is not eventually satisfied after stage s, then G_{|σ|}^{i} ≇ A^{0} for some i ∈ ℤ.

Now let τ be such that either τ = σ or both τ ⊇ σ^{⌢}0 and |τ| ⩽ recov(σ, s), and let i ∈ ℤ be such that |i| ⩽ recov(σ, s). Clearly, c(τ, t) reaches a limit c(τ). It is easy to see that, for any stage 2t + 2 at which τ is active, c(τ, 2t + 1) < c(τ, s) = c(τ). So, for each l ∈ {2, 4, 5}, there is a unique component of A^{0} that contains a copy of [10⟨⌜τ⌝, c(τ)⟩+l], and it is isomorphic to [10⟨⌜τ⌝, c(τ)⟩+l]. Similarly, for each m < c(σ, s), there is a unique component of A^{0} that contains a copy of [10⟨⌜τ⌝, c(τ), m⟩ + 1], and this component is isomorphic to [10⟨⌜τ⌝, c(τ), m⟩ + 1]. Thus, if the sixth condition in the definition of phase-2 σ-recovery stage is not eventually satisfied after stage s, then for some i ∈ ℤ, there is a component of A^{0} that is not isomorphic to any component of G_{|σ|}^{i}.

Finally, let τ ⊇ σ^{⌢}0 and i ∈ ℤ be such that |τ| , |i| ⩽ recov(σ, s), and consider R_{|τ|}. If this requirement is ever satisfied then the last condition in the definition of phase-2 σ-recovery stage will be satisfied for these particular τ and i at all sufficiently large stages. On the other hand, suppose that R_{|τ|} is never satisfied. It is easy to see that init(τ, t) reaches a limit init(τ), and there is a component of A isomorphic to [10⟨⌜τ⌝, init(τ)⟩]. Similarly, for each l ∈ {6, 7}, there is a component of A^{0} isomorphic to [10⟨⌜τ⌝, init(τ)⟩ + l], and, for each m < π_{1}(⌜τ⌝), there is a component of A^{0} isomorphic to [10⟨⌜τ⌝, init(τ), m⟩ + 8]. Thus, if the last condition in the definition of phase-2 σrecovery stage is not eventually satisfied after stage s then, for some i ∈ ℤ, there is a component of A^{0} that is not isomorphic to any component of G_{|σ|}^{i}.

In either case, G_{|σ|} cannot be isomorphic to A, contrary to hypothesis. So there are infinitely many σ-recovery stages.

Now let v be a stage after which σ is never initialized. Given any two stages 2u+2 > 2t + 2 > v at which σ is active, the σ-special component of G_{|σ|}[2u + 1] properly extends the σ-special component of G_{|σ|}[2t+1]. Thus, to establish the second part of the lemma, it is enough to show that σ is active infinitely often. But it is easy to find infinitely many τ ⊃ σ^{⌢}0 such that R_{τ} eventually requires attention. Each time such an R_{τ} requires attention, σ is active.

3.29 Lemma. If σ ∈ TP and G_{|σ|} ≅ A, then lim_{s} r_{σ,s} is well-defined.

Proof. This follows immediately from Lemmas 3.24 and 3.28.

Now fix σ ∈ TP such that G_{|σ|} ≅ A. Let n = |σ|, and let g be the 0-master node of G_{n}. By Lemma 3.29, r = lim_{s} r_{σ,s} is well-defined. We wish to show that (G_{n}, g) is computably isomorphic to (A, a_{r}). Let b be the unique map from the backbone graph B of A to the backbone graph B of G_{n} that takes a_{r} to g. Note that b is computable.

We will define a computable isomorphism f from A to G_{n} such that f extends b. Our method will be to divide |A| into a finite collection of (not necessarily disjoint) c.e. sets and define f independently on each of these sets. We will need to be somewhat careful here, because A is not rigid (i.e., A has nontrivial automorphisms), but Lemma 3.32 below justifies our approach.

Let ω^{−} = {k ∈ ω | k ≢ 9 mod 10}. Let N_{0} = {(k, i) | k ∈ ω^{−}, k ≢ 0 mod 10, i ∈ ℤ} and N_{1} = {k ∈ ω | k ≡ 0 mod 10}. Let N = N_{0} ∪ N_{1}. For p = (k, i) ∈ N_{0}, let π(p) = k; for k ∈ N_{1}, let π(k) = k.

3.30 Definition. Let p = (k, i) ∈ N_{0} and s ∈ ω. We denote by (p) and (p)_{s} the components of A and A_{s}, respectively, that extend the unique copy of [k] in A_{0}^{i}.

Let k ∈ N_{1} and s ∈ ω. We denote by (k) and (k)_{s} the components of A and A_{s}, respectively, that extend the unique copy of [k] in A_{0}.

For H ⊆ ω^{−}, let H̃ = {(k, i) | k ∈ H, k ≢ 0 mod 10, i ∈ ℤ} ∪ {k ∈ H | k ≡ 0 mod 10}. For S ⊆ N, let P_{S} be the graph obtained by restricting the domain of A to |B| ∪ ⋃_{p∈S} |(p)|.

3.31 Lemma. Let S and S′ be disjoint subsets of N, and let f and f′ be embeddings of P_{S} and P_{S′}, respectively, into G_{n}. Then f and f′ agree on P_{S} ∩ P_{S′}.

Proof. By Lemma 3.11, if p ≠ q ∈ N are such that (p) = (q) then (p) is a component of A^{∗}. This clearly implies that f^{−1} ∘ (f′ ↾ P_{S} ∩ P_{S′}) can be extended to an automorphism of A^{∗}. But it is also easy to check that A^{∗} is rigid. Thus f and f′ must agree on P_{S} ∩ P_{S′}.

3.32 Lemma. Let S_{0}, …, S_{m} be pairwise disjoint computable subsets of N such that ⋃_{i=0}^{m} S_{i} = N. Suppose that, for each i ⩽ m, there exists a computable embedding f_{i} ⊃ b from P_{S_{i}} into G_{n} such that ⋃_{i=0}^{m} rng(f_{i}) = |G_{n}|. Suppose further that, for i, j ⩽ m such that i ≠ j, if K and L are components of P_{S_{i}} and P_{S_{j}}, respectively, and f_{i}(K) = f_{j}(L), then K = L. Then there exists a computable isomorphism f ⊃ b from A to G_{n}.

Proof. Since S_{0}, …, S_{m} are computable, P_{S_{0}}, …, P_{S_{m}} are c.e.. Since ⋃_{i=0}^{m} S_{i} = N, ⋃_{i=0}^{m} P_{S_{i}} = A. Define f as follows. Given x ∈ A, wait until x is enumerated into some P_{S_{i}}, i ⩽ m, and then let f(x) = f_{i}(x). It is easy to check that the conditions imposed on S_{0}, …, S_{m} and f_{0}, …, f_{m}, together with Lemma 3.31, imply that f is an isomorphism from A to G_{n}.

We will partition ω^{−} into the pairwise disjoint computable sets H_{0}, …, H_{5} shown in Table 1. This will induce a partition of N into H̃_{0}, …, H̃_{5}. We will further partition H̃_{3} into H̃_{3}^{0} = {p ∈ H̃_{3} | (p) is infinite and does not contain a copy of [10k] for any k ∈ ω} and H̃_{3}^{1} = H̃_{3} − H̃_{3}^{0}.

The following two lemmas give us a useful tool for computing f.

3.33 Lemma. Let p ∈ N, and suppose there is a stage s such that, for each t ⩾ s, (p)_{t} does not participate in an operation at stage t + 1. Then (p) ≅ (p)_{s}.

Proof. Clearly, if (p)_{t} does not participate in an operation at stage t + 1 then (p)_{t+1} ≅ (p)_{t}. So, by induction, (p)_{t} ≅ (p)_{s+1} for all t ⩾ s. Since (p) = ⋃_{t∈ω}(p)_{t}, the lemma follows.

Table 1: H_{0}, …, H_{5}

H_{0} {10⟨⌜τ⌝, k, j⟩ + 1, 10⟨⌜τ⌝, k⟩ + l | τ to the left of σ or τ^{⌢}1 ⊆ σ;

j, k ∈ ω; l ∈ {2, 3, 4, 5}}

H_{1} {10⟨⌜τ⌝, k, j⟩ + 8, 10⟨⌜τ⌝, k⟩ + l | τ to the left of σ; j, k ∈ ω; l ∈ {0, 6, 7}} H_{2} {10⟨⌜τ⌝, k, j⟩ + d, 10⟨⌜τ⌝, k⟩ + l | τ to the right of σ^{⌢}0; j, k ∈ ω;

d ∈ {1, 8}; l ∈ {0, 2, 3, 4, 5, 6, 7}}

H_{3} {10⟨⌜τ⌝, k, j⟩ + 1, 10⟨⌜τ⌝, k⟩ + l | τ^{⌢}0 ⊆ σ; j, k ∈ ω; l ∈ {2, 3, 4, 5}}
H_{4} {10⟨⌜τ⌝, k, j⟩ + 8, 10⟨⌜τ⌝, k⟩ + l | τ ⊆ σ; j, k ∈ ω; l ∈ {0, 6, 7}}
H_{5} {10⟨⌜τ⌝, k, j⟩+1, 10⟨⌜τ⌝, k⟩+l | τ = σ or σ^{⌢}0 ⊆ τ; j, k ∈ ω; l ∈ {2, 3, 4, 5}}∪ ; {10⟨⌜τ⌝, k, j⟩ + 8, 10⟨⌜τ⌝, k⟩ + l | σ^{⌢}0 ⊆ τ; j, k ∈ ω; l ∈ {0, 6, 7}}

3.34 Lemma. Let H ⊆ ω^{−}, h : H → ω, and S ⊆ H̃ all be computable. Suppose that, for each p ∈ S and t ⩾ h(π(p)), (p)_{t} does not participate in an operation at stage t + 1. Then there is a unique embedding f ⊃ b of P_{S} into G_{n}, and f is computable.

Proof. Let x ∈ P_{S} and let p ∈ S be such that x ∈ (p). By Lemma 3.33, (p)_{h(π(p))} ≅ (p), so either (p) is finite or it contains a copy of [10k] for some k ∈ ω.

First suppose that (p) is finite. By Lemma 3.13, no finite component K of A is embeddable in another component L of A unless K and L are i-isomorphic for some i ∈ ℤ, i ≠ 0, so there is a unique finite set T ⊂ G_{n} for which there is an isomorphism g_{x} : A ↾ (|(p)| ∪ |B|) ≅ G_{n} ↾ (|T | ∪ |B|) extending b, and this isomorphism is unique.

Now suppose that (p) contains a copy of [10k] for some k ∈ ω. If (p) does not participate in an operation before stage h(π(p)) + 1 then (p) is finite, so the previous case applies. Otherwise, let m be such that x ∈ (p)∩(A^{∗})^{m}. By Lemma 3.16, (p)∩(A^{∗})^{m} is not embeddable in any component L ≠ K of A unless (p) and L are i-isomorphic for some i ∈ ℤ, i ≠ 0, so there is a unique finite set T ⊂ G_{n} for which there is an isomorphism g_{x} : A ↾ (|(p) ∩ (A^{∗})^{m}| ∪ |B|) ≅ G_{n} ↾ (|T | ∪ |B|) extending b, and this isomorphism is unique.

In either case, define f(x) = g_{x}(x). By the uniqueness of T and g_{x}, f is the unique embedding of P_{S} into G_{n} such that f extends b. Furthermore, it is easy to see that g_{x} can be computably determined given x ∈ P_{S}, which implies that f is computable.

3.35 Lemma. Let H_{0} consist of all numbers of the form 10⟨⌜τ⌝, k, j⟩+1 or 10⟨⌜τ⌝, k⟩+l, with either τ to the left of σ or τ^{⌢}1 ⊆ σ; j, k ∈ ω; and l ∈ {2, 3, 4, 5}. Then there is a unique embedding f_{0} ⊃ b of PH̃_{0} into G_{n}, and f_{0} is computable.

Proof. Let T be the set of all τ which are either to the left of σ or such that τ^{⌢}1 ⊆ σ. Since σ ∈ TP, only finitely many elements of T ever recover, and the ones that do recover, do so only finitely often. So there exists a stage s such that if τ ∈ T then τ is not active after stage s. If we let h(m) = s for all m ∈ H_{0} then the hypotheses of Lemma 3.34 are satisfied for S = H̃_{0}.

3.36 Lemma. Let H_{1} consist of all numbers of the form 10⟨⌜τ⌝, k, j⟩+8 or 10⟨⌜τ⌝, k⟩+l, with τ to the left of σ; j, k ∈ ω; and l ∈ {0, 6, 7}. Then there is a unique embedding f_{1} ⊃ b of PH̃_{1} into G_{n}, and f_{1} is computable.

Proof. Since σ ∈ TP, there exists a stage s such that if τ is to the left of σ then τ is not accessible after stage s. If we let h(m) = s for all m ∈ H_{1} then the hypotheses of Lemma 3.34 are satisfied for S = H̃_{1}.

3.37 Lemma. Let τ be to the right of σ^{⌢}0. Let m be of the form 10⟨⌜τ⌝, k, j⟩ + d or 10⟨⌜τ⌝, k⟩ + l, with j, k ∈ ω; d ∈ {1, 8}; and l ∈ {0, 2, 3, 4, 5, 6, 7}. Let s + 1 be the stage at which τ is initialized for the (k + 1)^{st} time. Let i ∈ ℤ. If m ∈ N_{1} then let p = m; otherwise, let p = (m, i). Then (p) does not participate in an operation after stage s.

Proof. If a singleton component of A_{t} of the form [10⟨⌜τ⌝, q⟩ + l], with l ∈ {0, 3, 6, 7}, or [10⟨⌜τ⌝, q, j⟩ + 8] participates in an operation at a stage t + 1 > s then q = init(τ, t) > k. If a singleton component of A_{t} of the form [10⟨⌜τ⌝, q⟩ + l], with l ∈ {2, 4, 5}, or [10⟨⌜τ⌝, q, j⟩ + 1] participates in an operation at a stage t + 1 > s then q = c(τ, t) ⩾ init(τ, t) > k. So if (p) does not participate in an operation before stage s + 1 then it does not participate in an operation after stage s.

On the other hand, if (p) participates in an operation before stage s+1 then the fact that it does not participate in an operation after stage s follows from Lemma 3.17.

3.38 Lemma. Let H_{2} consist of all numbers of the form 10⟨⌜τ⌝, k, j⟩+d or 10⟨⌜τ⌝, k⟩+l, with τ to the right of σ^{⌢}0; j, k ∈ ω; d ∈ {1, 8}; and l ∈ {0, 2, 3, 4, 5, 6, 7}. Then there is a unique embedding f_{2} ⊃ b of PH̃_{2} into G_{n}, and f_{2} is computable.

Proof. If m ∈ H_{2} is of the form 10⟨⌜τ⌝, k, j⟩ + d or 10⟨⌜τ⌝, k⟩ + l then define h(m) to be the first stage by which τ has been initialized k + 1 many times (which exists, since σ^{⌢}0 ∈ TP). Then, by Lemma 3.37, the hypotheses of Lemma 3.34 are satisfied for S = H̃_{2}.

Let H_{3} be the set of all numbers of the form 10⟨⌜τ⌝, k, j⟩ + 1 or 10⟨⌜τ⌝, k⟩ + l, with τ^{⌢}0 ⊆ σ; j, k ∈ ω; and l ∈ {2, 3, 4, 5}. Let H̃_{3}^{0} be the set of all p ∈ H̃_{3} such that (p) is infinite and does not contain a copy of [10k] for any k ∈ ω. Let H̃_{3}^{1} = H̃_{3} − H̃_{3}^{0}.

3.39 Lemma. H̃_{3}^{0} is computable.

Proof. By Lemmas 3.15, 3.22, and 3.24, every element of H̃_{3}^{0} must be of the form (10⟨⌜τ⌝, k⟩ + l, i), where τ^{⌢}0 ⊆ σ; lim_{s} r_{τ,s} exists; k, i ∈ ω; and l ∈ {3, 4, 5}. Let p ∈ N be of this form. We will describe an effective procedure for deciding whether p ∈ H̃_{3}^{0}.

First suppose that l = 3. Since lim_{s} r_{τ,s} exists, T_{τ,s} comes to a limit T by some stage u. Since τ ∈ TP, init(τ, s) comes to a limit init(τ). If k ≠ init(τ) then p ∉ H̃_{3}^{0}. Otherwise, by Lemma 3.21, p ∈ H̃_{3}^{0} if and only if (p)_{u} contains a copy of T.

Now suppose that l ∈ {4, 5}. Let t ⩾ u be a stage by which τ has recovered k + 1 many times, which must exist, since τ^{⌢}0 ∈ TP. Arguing as in the proof of Lemma 3.37, we see that if (p) has not participated in an operation by stage t then it will never participate in an operation, in which case p ∉ H̃_{3}^{0}. On the other hand, if (p) has participated in an operation by stage t then, by Lemma 3.21, p ∈ H̃_{3}^{0} if and only if (p)_{t} contains a copy of T.

For τ ⊂ σ, let S_{τ} be the set of all p ∈ H̃_{3}^{0} such that (p) is a component of (A)_{τ}. The following lemma is easily checked.

3.40 Lemma. For each τ ⊂ σ, P_{S_{τ}} is c.e..

For τ ⊂ σ, let M_{τ} be the union of all infinite components of (G_{n})_{τ} that do not contain a copy of [10k] for any k ∈ ω. Let M = ⋃_{τ⊂σ} M_{τ}.

3.41 Lemma. For each τ ⊂ σ, M_{τ} is c.e..

Proof. By Lemmas 3.15, 3.22, and 3.24, it is enough to show that M_{τ} is c.e. for each τ such that τ^{⌢}0 ⊆ σ and lim_{s} r_{τ,s} exists.

Fix such a τ. Since lim_{s} r_{τ,s} exists, T_{τ,s} comes to a limit T. By Lemma 3.21, the components of M_{τ} are exactly those that contain a copy of T. Since T is finite, we can effectively enumerate such components.

3.42 Lemma. There exists a computable isomorphism f_{3}^{0} ⊃ b from PH̃_{3}^{0} to the graph obtained by restricting the domain of G_{n} to |B| ∪ |M|.

Proof. Let τ ⊂ σ. By Lemma 3.40, P_{S_{τ}} is c.e.. By Lemma 3.41, so is M_{τ}. Thus there exists a computable 1–1 and onto map d_{τ} from the tops of components of P_{S_{τ}} to the tops of components of M_{τ} such that if x is the top of a level-i component of P_{S_{τ}}, i ∈ ℤ, then d_{τ}(x) is the top of a level-(i − r) component of M_{τ}. By Lemma 3.26, d_{τ} can be extended to a computable isomorphism f_{3}^{τ} from P_{S_{τ}} to M_{τ}. Now define f_{3}^{0} = b ∪ ⋃_{τ⊂σ} f_{3}^{τ}.

3.43 Lemma. There is a unique embedding f_{3}^{1} ⊃ b of PH̃_{3}^{1} into G_{n}, and f_{3}^{1} is computable.

Proof. First let p = (m, i) ∈ H̃_{3}^{1}, where m is of the form 10⟨⌜τ⌝, k⟩ + 3. Note that in this case (p) cannot contain a copy of [10k′] for any k′ ∈ ω. Let init(τ) = lim_{s} init(τ, s).

If k < init(τ) then let s be the least stage by which τ has been initialized k +1 many times. Arguing as in the proof of Lemma 3.37, we see that (p) does not participate in an operation after stage s. In this case, let h(m) = s.

If k > init(τ) then (p) never participates in an operation. In this case, let h(m) = 0. If k = init(τ) then it must be the case that r_{τ,s} has no limit, since otherwise (p)

would be infinite, which would imply that p ∈ H̃_{3}^{0}. Thus T_{τ,s} has no limit, which means that we can find a stage s such that (p)_{s} does not contain a copy of T_{τ,s}. It is not hard to check that (p) does not participate in an operation after stage s. In this case, let h(m) = s.

Now let p = (m, i) ∈ H̃_{3}^{1}, where m is of the form 10⟨⌜τ⌝, k, j⟩+1 or 10⟨⌜τ⌝, k⟩+l, with l ∈ {2, 4, 5}. Let 2s + 2 be the least phase-2 τ-recovery stage such that c(τ, 2s + 1) > k,

(p) does not participate in an operation at stage 2s + 2, and (p)_{2s+1} does not contain a copy of T_{τ,2s+1}. Such a stage must exist, since otherwise (p) would be infinite but would not contain a copy of [10k′] for any k′ ∈ ω, which would imply that p ∈ H̃_{3}^{0}. It is not hard to check that (p) does not participate in an operation after stage s. In this case, let h(m) = s.

Now the hypotheses of Lemma 3.34 are satisfied for S = H̃_{3}^{1}.

Let f_{3} = f_{3}^{0} ∪ f_{3}^{1}.

3.44 Lemma. Let H_{4} consist of all numbers of the form 10⟨⌜τ⌝, k, j⟩+8 or 10⟨⌜τ⌝, k⟩+l, with τ ⊆ σ; j, k ∈ ω; and l ∈ {0, 6, 7}. Then there is a unique embedding f_{4} ⊃ b of PH̃_{4} into G_{n}, and f_{4} is computable.

Proof. Let m ∈ H_{4} be of the form 10⟨⌜τ⌝, k, j⟩ + 8 or 10⟨⌜τ⌝, k⟩ + l. Let i ∈ ℤ. If m ∈ N_{1} then let p = m; otherwise, let p = (m, i). If R_{|τ|} is never satisfied then (p) never participates in an operation. In this case, let h(m) = 0. If R_{|τ|} is satisfied at stage s then (p) never participates in an operation after stage s. In this case, let h(m) = s. Since there are only finitely many τ ⊆ σ, h is computable, and hence the hypotheses of Lemma 3.34 are satisfied for S = H̃_{4}.

Let H′_{5} consist of all numbers of the form 10⟨⌜τ⌝, k, j⟩+1 or 10⟨⌜τ⌝, k⟩+l, with either τ = σ or σ^{⌢}0 ⊆ τ; j, k ∈ ω; and l ∈ {2, 3, 4, 5}. Let H′′_{5} consist of all numbers of the form 10⟨⌜τ⌝, k, j⟩ + 8 or 10⟨⌜τ⌝, k⟩ + l, with σ^{⌢}0 ⊆ τ; j, k ∈ ω; and l ∈ {0, 6, 7}. Let H_{5} = H′_{5} ∪ H′′_{5}.

3.45 Lemma. Let τ be such that τ = σ or σ^{⌢}0 ⊆ τ. Let u be a stage after which σ is never initialized and such that r_{σ,s} = r for all s ⩾ u. Let 2s + 1 > u be a phase-1 τ-recovery stage, and let 2t + 2 be the next phase-2 σ-recovery stage after stage 2s + 1. Let i ∈ ℤ be such that |i − r| ⩽ recov(σ, 2s + 1). Let K_{0}, …, K_{m} be the components of (A_{2s}^{i})_{τ} that participate in an operation at stage 2s+1. Let K′_{0}, …, K′_{m} be the components of A_{2t+1} that extend K_{0}, …, K_{m}, respectively. Then the following hold.

1. There exist components K̂_{0}, …, K̂_{m} of G_{n}^{i−r}[2s] such that K̂_{0} ≅ K_{0}, …, K̂_{m} ≅ K_{m}.

2. Let K̂′_{0}, …, K̂′_{m} be the components of G_{n}[2t + 1] that extend K̂_{0}, …, K̂_{m}, respectively. Then K̂′_{0} ≅ K′_{0}, …, K̂′_{m} ≅ K′_{m}.

Proof. Since 2s + 1 is a τ-recovery stage, it is also a σ-recovery stage, so the first part of the lemma follows from the definition of phase-1 σ-recovery stage; we prove the second part.

Let j ⩽ m. Since no component of (A)_{τ} participates in an operation in the interval (2s + 1, 2t + 2), the definition of the catch-up operation performed at stage 2s + 1 guarantees that K′_{j} is the unique component of A_{2t+1}^{i} that contains a copy of K_{j}. This means that K̂′_{j} is the unique component of G^{i−r}[2t + 1] that contains a copy of K̂_{j}. By the definition of phase-2 σ-recovery stage, there must exist a component of G^{i−r}[2t + 1] isomorphic to K′_{j}, so it must be the case that K̂′_{j} ≅ K′_{j}.

3.46 Lemma. Let τ be such that τ = σ or σ^{⌢}0 ⊆ τ. Let u be a stage after which σ is never initialized and such that r_{σ,s} = r for all s ⩾ u. Let 2s + 2 > u be a phase-2 τ-recovery stage, and let 2t + 1 be the next phase-1 σ-recovery stage after stage 2s + 2. Let \overline{A}_{2t} be the union of (A_{2t}^{∗})^{recov(σ,2s+1),r} (see page 14) and A_{2t}^{i} for each i ∈ ℤ such that |i − r| ⩽ recov(σ, 2s + 1). Let \overline{G}_{n}[2t] be the union of (G_{n}^{∗}[2t])^{recov(σ,2s+1)} and G_{n}^{i}[2t] for each i ∈ ℤ such that |i| ⩽ recov(σ, 2s + 1).

Let i ∈ ℤ be such that |i − r| ⩽ recov(σ, 2s + 1). Let e be such that R_{e} is satisfied at stage 2s + 2 and let m = π_{1}(e). Let Y_{0}, …, Y_{m−1}, X, Z, B, S, C, D, E, and F_{0}, …, F_{m−1} be Y_{τ,0,2s+1}^{i}, …, Y_{τ,m,2s+1}^{i}, X_{2s+1}, Z_{τ,2s+1}^{i}, B_{τ,2s+1}^{i}, S_{τ,2s+1}^{i}, C_{τ,2s+1}^{i}, D_{2s+1}^{i}, E_{2s+1}^{i}, and F_{0,2s+1}^{i}, …, F_{m,2s+1}^{i}, respectively. Let Y′_{0}, …, Y′_{m−1}, X′, Z′, B′, S′, C′, D′, E′, and F′_{0}, …, F′_{m−1} be the intersection of the components of A_{2t} that extend Y_{0}, …, Y_{m−1}, X, Z, B, S, C, D, E, and F_{0}, …, F_{m−1}, respectively, with \overline{A}_{2t}. Then the following hold.

1. There exists a component X̂ of G_{n}^{i−r}[2s + 1] such that X̂ ≅ X. There exist components Ŷ_{0}, …, Ŷ_{m−1}, Ẑ, B̂, Ŝ, Ĉ, D̂, Ê, and F̂_{0}, …, F̂_{m−1} of G_{n}^{i−r}[2s + 1] such that Ŷ_{0} ≅ Y_{0}, …, Ŷ_{m−1} ≅ Y_{m−1}, Ẑ ≅ Z, B̂ ≅ B, Ŝ ≅ S, Ĉ ≅ C, D̂ ≅ D, Ê ≅ E, and F̂_{0} ≅ F_{0}, …, F̂_{m−1} ≅ F_{m−1}.

2. Let Ŷ′_{0}, …, Ŷ′_{m−1}, X̂′, Ẑ′, B̂′, Ŝ′, Ĉ′, D̂′, Ê′, and F̂′_{0}, …, F̂′_{m−1} be the intersection of the components of G_{n}[2t] that extend Ŷ_{0}, …, Ŷ_{m−1}, X̂, Ẑ, B̂, Ŝ, Ĉ, D̂, Ê, and F̂_{0}, …, F̂_{m−1}, respectively, with \overline{G}_{n}[2t]. Then Ŷ′_{0} ≅ Y′_{0}, …, Ŷ′_{m−1} ≅ Y′_{m−1}, X̂′ ≅ X′, Ẑ′ ≅ Z′, B̂′ ≅ B′, Ŝ′ ≅ S′, Ĉ′ ≅ C′, D̂′ ≅ D′, Ê′ ≅ E′, and F̂′_{0} ≅ F′_{0}, …, F̂′_{m−1} ≅ F′_{m−1}.

Proof. Since 2s + 2 is a τ-recovery stage, if τ ≠ σ then σ must have fully recovered at least |τ| + 1 many times by stage 2s + 1, so the first part of the lemma follows from the definition of phase-2 recovery stage; we prove the second part. There are several cases.

We begin with the τ = σ and i = r case. (We need to treat this case separately to show that X̂′ ≅ X′, which will be needed for the other cases.) Since i = r_{σ,2s+2}, the row of level-i components corresponding to σ in the operation performed at stage 2s + 2 goes to the left. That is, Z′ is a copy of Z · B; B′ is a copy of B · S; S′ is a copy of S · C; C′ is a copy of C ⊙ (Y_{0}, …, Y_{m−1}); each Y_{j}, j < m, contains a copy of Y_{j} · X; and X contains a copy of X · Z.

By definition, Ŝ and Ŝ′ are the σ-special components of G_{n}[2s + 1] and G_{n}[2t], respectively. Thus, since r_{σ,2t+1} = r_{σ,2t} = r and 2t + 1 is a σ-recovery stage, Ŝ′ ≅ S′.

All the components of A_{2t} that contain a copy of C are isomorphic to either S′ or C′. Since Ŝ′ ≅ S′, it must be the case that Ĉ′ ≅ C′.

Let j < m. All the components of A_{2t} that contain a copy of Y_{j} are isomorphic to either C′ or Y′_{j}. Since Ĉ′ ≅ C′, it must be the case that Ŷ′_{j} ≅ Y′_{j}.

The only components of A_{2t} that contain a copy of X are Y′_{0}, …, Y′_{m−1} and X′. Since Ŷ′_{j} ≅ Y′_{j} for each j < m, it must be the case that X̂′ ≅ X′.

The only components of A_{2t} that contain a copy of Z are X′ and components isomorphic to Z′. Since X̂′ ≅ X′, it must be the case that Ẑ′ ≅ Z′.

All the components of A_{2t} that contain a copy of B are isomorphic to either Z′ or B′. Since Ẑ′ ≅ Z′, it must be the case that B̂′ ≅ B′.

We now deal with the i ≡ r_{τ,2s+2} mod (m + 1) case. As in the first case, the row of level-i components corresponding to τ in the operation performed at stage 2s + 2 goes to the left.

The previous case shows that X̂′ ≅ X′.

The only components of A_{2t} that contain a copy of Z are X′ and components isomorphic to Z′. Since X̂′ ≅ X′, it must be the case that Ẑ′ ≅ Z′.

All the components of A_{2t} that contain a copy of B are isomorphic to either Z′ or B′. Since Ẑ′ ≅ Z′, it must be the case that B̂′ ≅ B′.

All the components of A_{2t} that contain a copy of S are isomorphic to either B′ or S′. Since B̂′ ≅ B′, it must be the case that Ŝ′ ≅ S′.

All the components of A_{2t} that contain a copy of C are isomorphic to either S′ or C′. Since Ŝ′ ≅ S′, it must be the case that Ĉ′ ≅ C′.

Let j < m. All the components of A_{2t} that contain a copy of Y_{j} are isomorphic to either C′ or Y′_{j}. Since Ĉ′ ≅ C′, it must be the case that Ŷ′_{j} ≅ Y′_{j}.

We now deal with the i ≢ r_{τ,2s+2} mod (m + 1) case. Let l < m be such that i ≡ l + r_{τ,2s+2} +1 mod (m+1). In this case, the row of level-i components corresponding to σ in the operation performed at stage 2s+2 goes to the right. That is, B′ is a copy of B·Z; S′ is a copy of S·B; C′ is a copy of C·S; Y′_{l} is a copy of Y′_{l}⊙(C, Y_{0}, …, Y_{l−1}, Y_{l+1}, …, Y_{m−1}); each Y′_{j}, with j < m and j ≠ l, contains a copy of Y_{j} · X; X′ contains a copy of X · Y_{l}; and Z′ contains a copy of Z · X.

As before, the first case shows that X̂′ ≅ X′.

The only components of A_{2t} that contain a copy of Y_{l} are X′ and components isomorphic to Y′_{l}. Since X̂′ ≅ X′, it must be the case that Ŷ′_{l} ≅ Y′_{l}.

Let j < m, j ≠ l. All the components of A_{2t} that contain a copy of Y_{j} are isomorphic to either Y′_{l} or Y′_{j}. Since Ŷ′_{l} ≅ Y′_{l}, it must be the case that Ŷ′_{j} ≅ Y′_{j}.

All the components of A_{2t} that contain a copy of C are isomorphic to either Y′_{l} or C′. Since Ŷ′_{l} ≅ Y′_{l}, it must be the case that Ĉ′ ≅ C′.

All the components of A_{2t} that contain a copy of S are isomorphic to either C′ or S′. Since Ĉ′ ≅ C′, it must be the case that Ŝ′ ≅ S′.

All the components of A_{2t} that contain a copy of B are isomorphic to either S′ or B′. Since Ŝ′ ≅ S′, it must be the case that B̂′ ≅ B′.

All the components of A_{2t} that contain a copy of Z are isomorphic to either B′ or Z′. Since B̂′ ≅ B′, it must be the case that Ẑ′ ≅ Z′.

Finally, we deal with the case of D, E, and F_{0}, …, F_{m−1}. First suppose that i ≡ 0 mod (m + 1). In this case, the row of components containing E in the operation performed at stage 2s + 2 goes to the left. That is, D′ is a copy of D · E; E′ is a copy of E ⊙ (F_{0}, …, F_{m−1}); each F′_{j}, j < m, contains a copy of F_{j} · X; and X′ contains a copy of X · D.

As before, the first case shows that X̂′ ≅ X′.

The only components of A_{2t} that contain a copy of D are X′ and components isomorphic to D′. Since X̂′ ≅ X′, it must be the case that D̂′ ≅ D′.

All the components of A_{2t} that contain a copy of E are isomorphic to either D′ or E′. Since D̂′ ≅ D′, it must be the case that Ê′ ≅ E′.

Let j < m. All the components of A_{2t} that contain a copy of F_{j} are isomorphic to either E′ or F′_{j}. Since Ê′ ≅ E′, it must be the case that F̂′_{j} ≅ F′_{j}.

Now suppose that i ≢ 0 mod (m + 1). Let l < m be such that i ≡ l + 1 mod (m + 1). In this case, the row of components containing E in the operation performed at stage 2s + 2 goes to the right. That is, E′ is a copy of E · D; F′_{l} is a copy of F′_{l} ⊙ (E, F_{0}, …, F_{l−1}, F_{l+1}, …, Y_{m−1}); each F′_{j}, with j < m and j ≠ l, contains a copy of F_{j} · X; X′ contains a copy of X · F_{l}; and D′ contains a copy of D · X.

As before, the first case shows that X̂′ ≅ X′.

The only components of A_{2t} that contain a copy of F_{l} are X′ and components isomorphic to F′_{l}. Since X̂′ ≅ X′, it must be the case that F̂′_{l} ≅ F′_{l}.

Let j < m, j ≠ l. All the components of A_{2t} that contain a copy of F_{j} are isomorphic to either F′_{l} or F′_{j}. Since F̂′_{l} ≅ F′_{l}, it must be the case that F̂′_{j} ≅ F′_{j}.

All the components of A_{2t} that contain a copy of E are isomorphic to either F′_{l} or E′. Since F̂′_{l} ≅ F′_{l}, it must be the case that Ê′ ≅ E′.

All the components of A_{2t} that contain a copy of D are isomorphic to either E′ and D′. Since Ê′ ≅ E′, it must be the case that D̂′ ≅ D′.

The following lemma can be easily checked.

3.47 Lemma. Let p ∈ H̃_{5} and suppose that (p)_{2s+1} participates in an operation at stage 2s + 2. Then (p)_{2s+1} is one of Y_{τ,m,2s+1}^{i}, X_{2s+1}, Z_{τ,2s+1}^{i}, B_{τ,2s+1}^{i}, S_{τ,2s+1}^{i}, C_{τ,2s+1}^{i}, D_{2s+1}^{i}, E_{2s+1}^{i}, or F_{m,2s+1}^{i}, where either τ = σ or σ^{⌢}0 ⊆ τ, m ∈ ω, and i ∈ ℤ. Furthermore, σ is active at stage 2s + 2.

3.48 Lemma. Let u be a stage after which σ is never initialized and such that r_{σ,s} = r for all s ⩾ u. Let s + 1 > u be a σ-recovery stage and let t + 1 be the next σ-recovery stage after stage s + 1. Let p ∈ H̃_{5}. Suppose there exists a component L of G_{n}[s] that is (−r)-isomorphic to (p)_{s}. Then the component L′ of G_{n}[t] that extends L is isomorphic to (p)_{t}.

Proof. If (p) does not participate in an operation in the interval (s, t] then (p)_{t} ≅ (p)_{s}. Since L′ ⊇ L, (p)_{t} is not properly embeddable in any component of A_{t}, and, by convention, G_{n}[t] is embeddable in A_{t}, this means that L′ ≅ (p)_{t}.

Otherwise, the lemma follows from Lemmas 3.45, 3.46, and 3.47.

3.49 Lemma. Let u be a stage after which σ is never initialized and such that r_{σ,s} = r for all s ⩾ u. Let x ∈ PH̃_{5}. There exists a σ-recovery stage s + 1 > u such that x is contained in (p)_{s} for some p ∈ H̃_{5} and there exists a (−r)-isomorphic component L of G_{n}[s]. For any such s, if we let d be the unique isomorphism from (p)_{s} to L and let L′ be the component of G_{n} that extends L then d can be extended to an isomorphism from (p) to L′.

Proof. If x is contained in a finite component of A then the existence of s and L follows from the fact that G_{n} ≅ A. Otherwise, there is a σ-recovery stage s + 1 > u such that x is contained in (p)_{s}, p ∈ H̃_{5}, and (p)_{s} is involved in an operation at stage s + 1. Now it follows from Lemmas 3.45 and 3.46 that there is a component L of G_{n}[s] isomorphic to (p)_{s}.

Let s + 1 = s_{0} + 1 < s_{1} + 1 < ⋯ be the σ-recovery stages greater than or equal to s + 1. Let L_{i} be the component of G_{n}[s_{i}] that extends L and let L′ be the component of G_{n} that extends L. Using Lemma 3.48 and induction, we see that, for each i ⩾ 0, there is a unique isomorphism g_{i} : (p)_{s_{i}} ≅ L_{i}. Note that g_{0} = g. Clearly, if j > i then g_{j} extends g_{i}. Thus the limit g′ of the g_{i} is well-defined and is an isomorphism from (p) to L′.

Let T be the graph obtained by restricting the domain of G_{n} to the union of |B| with the domain of the set of all components of G_{n} that contain a copy of [m] for some m ∈ H_{5}.

3.50 Lemma. There exists a computable isomorphism f_{5} ⊃ b from PH̃_{5} to T.

Proof. We begin by defining f_{5} ↾ B ≡ b. Now let u be a stage after which σ is never initialized and such that r_{σ,s} = r for all s ⩾ u. Given x ∈ PH̃_{5}, find the least σ-recovery stage s + 1 > u such that x is contained in a component (p)_{s}, p ∈ H̃_{5}, of A_{s} and there exists a component L of G_{n}[s] that is (−r)-isomorphic to (p)_{s}. Such a stage exists by Lemma 3.49. Let d_{x} be the unique isomorphism from (p)_{s} to L and define f_{5}(x) = d_{x}(x).

We need to show that f_{5} is computable, that it is an embedding, and that its range is all of T.

Since d_{x} can be computably determined given x ∈ PH̃_{5}, f_{5} is computable.

By Lemma 3.49, all we need to do to show that f_{5} is an embedding is to show that if x and y are both contained in a component (p), p ∈ H̃_{5}, then f_{5}(x) and f_{5}(y) are contained in the same component of G_{n}. But this follows from Lemma 3.48, which implies, by induction, that if the least σ-recovery stage s+1 > u such that x is contained in (p)_{s} is greater than or equal to the least σ-recovery stage t + 1 > u such that y is contained in (p)_{t} then d_{x} extends d_{y}.

Finally, notice that, for any s ∈ ω, if K is a component of A_{s} that contains a copy of [m] for some m ∈ H_{5} then K is (p)_{s} for some p ∈ H̃_{5}.

Let L be a component of T. If L is a singleton component then the fact that G_{n} ≅ A implies that, for some σ-recovery stage s + 1 > u, there is a component K of A_{s} that is r-isomorphic to L. Since K is (p)_{s} for some p ∈ H̃_{5}, L is in the range of f_{5}.

If L is not a singleton component then it is in (G_{n})_{τ} or (G_{n}^{∗})_{τ} for some τ such that τ = σ or σ^{⌢}0 ⊆ τ. Let x ∈ L and let t > u be a stage such that x is contained in a component of G_{n}[s] that contains a copy of [m] for some m ∈ H_{5}. By the definition of σ-recovery stage, there is some σ-recovery stage s + 1 ⩾ t and components L′ and K of G_{n}[s] and A_{s}, respectively, such that x ∈ L′ and K is r-isomorphic to L′. Since K is (p)_{s} for some p ∈ H̃_{5}, x is in the range of f_{5}. Thus L is in the range of f_{5}.

Now H̃_{0}, …, H̃_{5} are computable subsets of N such that ⋃_{i=0}^{5} H̃_{i} = N. It is not hard to check that, for i, j ⩽ 5 such that i ≠ j, if K and L are components of PH̃_{i} and PH̃_{j}, respectively, and f_{i}(K) = f_{j}(L), then K and L are components of A^{∗}, from which it follows that K = L. Furthermore, the uniqueness of f_{0}, f_{1}, f_{2}, f_{3}^{1}, and f_{4}, together with the surjectivity of f_{3}^{0} and f_{5}, imply that ⋃_{i=0}^{m} rng(f_{i}) = |G_{n}|. So, combining Lemmas 3.35, 3.36, 3.38, 3.42, 3.43, 3.44, and 3.50 with Lemma 3.32, we have the following result.

3.51 Lemma. There exists a computable isomorphism from (A, a_{r}) to (G_{n}, g).

Theorem 1.4 follows from Lemmas 3.10, 3.27, and 3.51.

References

[1] P. Cholak, S. S. Goncharov, B. Khoussainov, and R. A. Shore, Computably categorical structures and expansions by constants, J. Symbolic Logic 64 (1999) 13–37.

[2] Y. L. Ershov, S. S. Goncharov, A. Nerode, and J. B. Remmel (eds.), Handbook of Recursive Mathematics, vol. 138–139 of Studies in Logic and the Foundations of Mathematics (Elsevier Science, Amsterdam, 1998).

[3] S. S. Goncharov, Computable single-valued numerations, Algebra and Logic 19 (1980) 325–356.

[4] S. S. Goncharov, Problem of the number of non-self-equivalent constructivizations, Algebra and Logic 19 (1980) 401–414.

[5] V. S. Harizanov, Pure computable model theory, in Ershov et al. [2] 3–114.

[6] D. R. Hirschfeldt, Degree spectra of intrinsically c.e. relations, J. Symbolic Logic 66 (2001) 441–469.

[7] D. R. Hirschfeldt, Degree spectra of relations on structures of finite computable dimension, Ann. Pure Appl. Logic 115 (2002) 233–277.

[8] D. R. Hirschfeldt, B. Khoussainov, R. A. Shore, and A. M. Slinko, Degree spectra and computable dimension in algebraic structures, Ann. Pure Appl. Logic 115 (2002) 71–113.

[9] B. Khoussainov and R. A. Shore, Computable isomorphisms, degree spectra of relations, and Scott families, Ann. Pure Appl. Logic 93 (1998) 153–193.

[10] B. Khoussainov and R. A. Shore, Effective model theory: the number of models and their complexity, in S. B. Cooper and J. K. Truss (eds.), Models and Computability, vol. 259 of London Mathematical Society Lecture Note Series (Cambridge University Press, Cambridge, 1999) 193–239.

[11] T. Millar, Recursive categoricity and persistence, J. Symbolic Logic 51 (1986) 430– 434.

[12] R. I. Soare, Recursively Enumerable Sets and Degrees, Perspect. Math. Logic (Springer–Verlag, Heidelberg, 1987).