Computable Isomorphisms, Degree Spectra of Relations, and Scott Families

Bakhadyr Khoussainov^{∗} Cornell University, Ithaca NY 14850 USA The University of Auckland, Auckland, New Zealand

Richard A. Shore^{§} Cornell University, Ithaca NY 14853 USA

1 Introduction

In studying effective structures we investigate the effective content of typical notions and constructions in many branches of mathematics including universal algebra and model theory. In particular, we are interested in the possibilities of effectivizing model–theoretic or algebraic constructions and the limits on these possibilities. For instance, we try to understand whether certain results of model theory (or universal algebra) can be carried out effectively. If not, we then try to discover sharp effective counterexamples.

The systematic study of effectiveness in algebraic structures goes back to pioneering papers by Frölich and Shepherdson [11], Malcev [31][32], and Rabin [37] in the early 60s. Later in the early 70s, Nerode and his collaborators initiated combining algebraic constructions with priority arguments from computability theory thus beginning a new era in the development of the subject.

Nowadays, there various approaches to effectiveness in structures. For example, Cenzer, Nerode, Remmel have been developing theory of p-time structures [6]. Khoussainov and Nerode have began the development of the theory of automatic structures [29]. In this paper we are interested in those structures in which the basic computations can be performed by Turing machines.

∗Partially supported by ARO through MSI, Cornell University, DAAL-03-C-0027.

§Partially supported by NSF Grant DMS-9503503 and ARO through MSI, Cornell University, DAAL-03-C-0027.

Definition 1 A structure A for a language L is computable (decidable) if there is a computable enumeration a_{i} of the domain A of A such that the atomic (elementary) diagram of (A, a_{i}) is computable. A structure isomorphic to a computable (decidable) structure is called (decidably) computably presentable. Any isomorphism from a structure A to a computable (decidable) structure is called a computable (decidable) presentation of A.

Here are some examples of computable or computably presentable structures. The natural numbers with addition and multiplication is a computable structure. The ordered field of rational numbers, finitely presented algebras with decidable word problem, free groups, vector spaces over the field of rationals, etc. all have computable presentations.

We also give another, more general, notion of effective structure.

Definition 2 A structure A for a language L is computably enumerable (c.e.) if there is a computable enumeration a_{i} of A such that the positive atomic diagram of (A, a_{i}) is computably enumerable. A structure isomorphic to a computably enumerable structure is called c.e. (computably enumerably) presentable. Any isomorphism from a structure A to a computably enumerable structure is called a computably enumerable (c.e.) presentation of A.

Finitely presented algebras are natural examples of c.e. structures. Note that every computable structure is also computably enumerable.

In model theory and universal algebra we identify isomorphic structures. When introducing effectiveness consideration into the area, we naturally want to understand the relationship between classical isomorphism types and effective isomorphism types. Thus, while model theory and universal algebra identify isomorphic structures, effective model theory is concerned with computable isomorphisms and finding characterizations for structures which have the same computable isomorphism type.

Definition 3 Two computable (c.e.) structures A and B are of the same computable (c.e.) isomorphism type if there is a computable isomorphism taking A to B. The (c.e.) dimension of a structure A is the number of its computable (c.e.) isomorphism types.

Thus the dimension of a structure is the maximal number of noncomputably isomorphic computable (c.e.) presentations of the structure. We would like to stress that the dimension of a structure in the class of computable presentations can differ from the dimension of the structure in the class of c.e. presentations. For example, the dimension of (Q, ≤), where Q is the set of all rationals, is 1 in the class of computable presentation. However, one can show that the dimension of this linear ordering is ω in the class of all c.e. presentations. In this paper we deal mainly with computable presentations. Therefore dimensions are considered with respect to the class of computable presentations of structures unless we specify otherwise. Similarly, all structures considered will be computable unless otherwise mentioned.

How far computable isomorphism types can be from classical ones can be seen in the following result of Goncharov:

Theorem 4 ([14]) For each n ≤ ω there is a computable structure with computable dimension n.

There has been a significant interest in trying to understand the nature of the structures of dimension 1. The basic model-theoretic notion which motivated the consideration of structures of dimension 1 is the notion of countable categoricity. A theory T is countably categorical if all (computable and noncomputable) countable models of T are isomorphic. An arbitrary countable structure A is categorical if its theory is countably categorical. The analogous concept for effective model theory deals only with computable structures and isomorphisms:

Definition 5 A structure A is computably categorical if every computable structure isomorphic to A is computably isomorphic to A.

The following result of Nurtasin was one of the first results about the nature of computably categorical structures:

Theorem 6 ([36]) For a structure A the following two conditions are equivalent:

1. Any two decidable presentations of A are computably isomorphic.

2. There exists a finite number of constants c̄ ∈ A such that (A, c̄) is the prime model of the theory T h(A, c̄) and the set of atoms of this theory is computable.

In the late 70’s, Goncharov–Dzgoev and Remmel independently gave an algebraic characterization of computably categorical Boolean Algebras and Linear Orderings.

Theorem 7 ([38] [13] [17])

1. A Boolean Algebra is computably categorical if and only if it has finitely many atoms.

2. A linear ordering is computably categorical if and only if the number of adjacent pairs in the ordering is finite.

In [15] Goncharov proved that if a structure A has two presentations, one of them computable but not decidable and the other decidable, then the dimension of the structure is ω. In a conversation with Khoussainov, Goncharov asked if an analogous result can be obtained to answer the following question:

If a structure A has two presentations one of them computably enumerable but not computable and the other computable, is the dimension of the structure ω in the class of c.e. presentations?

We answer this question in Theorem 4.1, using the proof of our basic result, Theorem 2.1:

Theorem 4.1 There exists a structure B which has exactly two computably enumerable presentations B_{1} and B_{2} such that the following properties hold:

1. B_{1} is a computably enumerable but not computable structure.

2. B_{2} is a computable structure.

3. Any computably enumerable presentation C of B is computably isomorphic to either B_{1} or B_{2}.

Interestingly, all the structures which have been shown to be computably categorical have one common property. They all have Scott families.

Definition 8 A Scott family for a structure A is a computable sequence

ϕ_{0}(ā, x_{1}, …, x_{n_{0}}), ϕ_{1}(ā, x_{1}, …, x_{n_{1}}), …,

of ∃-formulas satisfiable in A, where ā is a finite tuple of elements from A, such that every n-tuple of elements from A satisfies one these formulas and any two tuples satisfying the same formula from the above sequence can be interchanged by an automorphism of A.

The basic idea behind this definition is the following. If A has a Scott family and B is a computable structure isomorphic to A, then the existence of the Scott family allows one to effectively carry out a back and forth argument to construct a computable isomorphism from A to B. Therefore:

Theorem 9 If a structure A has a Scott family, then A is computably categorical. Moreover, for any n-tuple (c_{1}, …, c_{n}) from A, the expanded structure (A, c_{1}, …, c_{n})also has a Scott family and hence is computably categorical.

Proof. Let ϕ_{0}(ā, x_{1}, …, x_{n_{0}}), ϕ_{1}(ā, x_{1}, …, x_{n_{1}}), … be a Scott family for A, where ā = (a_{0}, …, a_{m−1}). Let A_{1} and A_{2} be computable presentations of A. We define a mapping f : A_{1} → A_{2} by stages. We can assume that for each j ∈ {0, …, m − 1}, a_{j}^{i} is the element in A_{i} corresponding to the constant a_{j} under a classical isomorphism between A_{1} and A_{2}. At even stages we define images of elements from A_{1}, at odd stages we define preimages of elements from A_{2}.

Stage 0. Set f_{1} = {(a_{0}^{1}, a_{0}^{2}), …, (a_{m−1}^{1}, a_{m−1}^{2})}.

Stage 2k. We can suppose that the function f_{2k−1} has been defined. Assume that f_{2k−1} = {(a_{0}^{1}, a_{0}^{2}), …, (a_{m−1}^{1}, a_{m−1}^{2}), (b_{1}, d_{1}), …, (b_{s}, d_{s})} and that f_{2k−1} can be extended to an isomorphism from A_{1} to A_{2}. Let b be the first number not in the domain of f_{2k−1}. Consider the tuple (b_{1}, …, b_{s}, b). Find an i such that ϕ_{i}(ā, b_{1}, …, b_{s}, b) holds in A_{1}. Hence ∃xϕ_{i}(ā, d_{1}, …, d_{s}, x) holds in A_{2}. Find the first d ∈ A_{2} for which ϕ_{i}(ā, d_{1}, …, d_{s}, d) holds. Extend f_{2k−1} by letting f_{2k} = f_{2k−1} ⋃{(b, d)}.

Stage 2k+1. We define f_{2k+1} similarly so as to put the least element of A_{2} not yet in the range of f_{2k} into that of f_{2k+1}.

Finally, let f = ⋃_{i∈ω} f_{i}. Thus, f is a computable isomorphism.

For the second part of the theorem, we slightly change the original Scott family. Namely, set ψ_{i} = ϕ_{i}(ā, x_{1}, …, x_{n_{i}})&∃y_{1} … ∃y_{n}(&_{j}(c_{j} = y_{j}). Then, one can easily check that the sequence ψ_{0}, ψ_{1}, … is a Scott family for the expanded structure (A, c_{1}, …, c_{n}). □

At this point, we would like to make the following two observations about the effect of expanding computably categorical structures by finitely many constants. First, as we mentioned, all the known examples of computably categorical structures have Scott families. Therefore, it is natural to ask whether there exists a computably categorical structure without a Scott family. By the above theorem, one possible way to build a such structure is to provide an example of a computably categorical structure one of whose expansions by finitely many constants is not computably categorical. Second, one of the motivations of computable categoricity comes from the model-theoretic notion of ω–categoricity. It is an easy consequence of the Ryll-Nardzewski Theorem that if a structure A is countably categorical then so is the structure (A, ā) expanded by finitely many constants. It is the analogous situation in effective model theory that we wish to consider.

Goncharov [12] proved that a computable structure whose universalexistential theory is decidable is computably categorical if and only if it has a Scott family. Thus any computably categorical structure with a decidable universal-existential theory remains computably categorical when expanded by finitely many constants. Millar proved that the decidability of the structures existential theory is actually sufficient to show that categoricity is preserved under such expansions:

Theorem 10 ([35]) If a structure A is computably categorical and its existential theory is decidable, then any expansion of A by finitely many constants is also computably categorical.

Informally this theorem states that if we can effectively solve systems of algebraic equation and inequations over a computably categorical structure, then computable categoricity is preserved under expansions by a finite number of constants. However, without this partial decidability assumption the problem, known as Ash–Goncharov problem, had been open for some time.

[9] Is the expansion of every computably categorical structure by finitely many constants computably categorical?

In [7] a negative solution to this problem is given. Our Theorem 4.2 (a corollary of an extension of our main result) gives a new solution which has a much simpler proof when k ≥ 3:

Theorem 4.2 For any natural number k there exists a computably categorical structure A such that, for each element a ∈ A, the expanded structure (A, a) has dimension k.

An immediate consequence of Theorem 4.2 is the following:

Corollary 4.3 There exists a computably categorical structure without a Scott family.

Proof. Consider the structure A whose existence is claimed in Theorem 4.2. This structure is computably categorical. The structure does not have a Scott family as otherwise we would have a contradiction by Theorem 1.10. □

Based on Theorem 1.10, one might suppose that the essential reason that the structure constructed in Theorem 4.2 does not have a Scott family is that its expansion by a finite number of constants is not computably categorical. Therefore one can ask the following question:

Does there exist a computably categorical structure without a Scott family whose expansion by any finite number of constants is computably categorical?

One application of the ideas used in the proof of our basic result (Theorem 2.1) provides a positive answer to Question 1. Indeed, the construction used to prove Theorem 2.1 can be simplified to establish the following:

Theorem 4.4 There exists a computably categorical structure without a Scott family whose expansion by any finite number of constants is computably categorical.

We note that Kudinov [30] has also recently proven a similar result by quite different methods. He slightly modifies a family of computable enumerations constructed by Selivanov [44] and then codes the family as a unary algebra in such a way as to produce a computably categorical structure with a decidable existential theory but no Scott family. Combining this result with Theorem 10 gives our Theorem 4.4. (We thank the referee for directing us to this paper by Kudinov.)

Now we turn to our basic result, Theorem 2.1. This theorem is about the degree spectra of relations on structures.

Definition 11 If U is a relation on a computable structure A, we define the partial ordering

DgSp(U) = ({deg_{T} (U^{B})| B is a computable presentation of A}, ≤_{T}),

where ≤_{T} is Turing reducibility on sets of natural numbers and U_{B} is the image of U in B. We call this partially ordered set the degree spectrum of U. (Recall that a computable presentation B of A includes an isomorphism from A to B and so determines U^{B}.)

There has been an extensive study of the degree spectra of relations on computably structures and related results. We refer readers to papers by Ash and Nerode [1], Ash and Knight [3] [4] [24] [25] [26], Harizanov [19] [20] [21], Ash, Cholak and Knight [5], etc.

Harizanov and Millar suggested investigating relations with finite degree spectra. Their motivations came from the fact that Ash-Nerode type decidability conditions on relations (see [1]) usually imply that the degree spectrum is infinite or a singleton. Another motivation is Goncharov’s examples of structures with finitely many computable isomorphism types. Here is an open question which we call the Degree Spectra Problem:

Is every finite partially ordered set isomorphic to DgSp(U) for some relation U on a structure A?

Modifying Goncharov’s construction from [14], Harizanov was the first to provide examples of relations with finite degree spectra.

Theorem 12 ([20]) There exists a relation U on a structure A with exactly two computable presentations A_{0} and A_{1} such that U^{A_{0}} is computable and U^{A_{1}} is a noncomputable Δ_{2}^{0}–set.

Our Theorem 2.1 improves this result:

Theorem 2.1 There exists a relation U in a structure A which has exactly two computable presentations A_{0} and A_{1} such that U^{A_{0}} is c.e. but not computable while U^{A_{1}} is computable. Moreover, the relation P = {(x, y)|x ∈U^{A_{0}} ∧ y ∈U^{A_{1}} ∧ there is an isomorphism from A_{0} to A_{1} which extends the map x ↦ y} is computable.

Goncharov [18] has announced a construction of a computable structure with dimension two and a relation whose degree spectrum consists of 0 and one noncomputable c.e. degree. This work grew out of earlier work with Khoussainov and is based on the construction of a family of c.e. sets with certain properties. However, the construction does not supply any more and Goncharov poses what we have called the Degree Spectra Problem (Question 1) as Problem 2 of [18]. Our methods enable us to give a positive solution to this problem:

Theorem 3.1 For any computable partially ordered set D there exists a structure A of dimension the cardinality of D and a relation U on A such that DgSp(U) ≅ D. Indeed, we can also guarantee that U^{B} is c.e. for every computable presentation B of A and that, if D has a least element, then the least element in DgSp(U) is 0.

Several natural strengthenings of this result can ruled out by the observation that, for a given relation U on a computable structure A, the set {U^{B}| B is a computable presentation of A} is Σ_{1}^{1} in U. Thus, there are countable partial orderings that cannot be realized in the c.e. degrees as the degree spectrum of any relation U on any computable structure A. (Just consider one that is too complicated to be Σ_{1}^{1}.) Similarly, such a partial ordering with least element cannot be realized anywhere in the Turing degrees as the degree spectrum of a computable relation U on a computable structure A. Nor can it be true that any finite set of degrees be realized as the degree spectrum of any relation U on a computable structure A. Indeed, any degree spectrum containing both a hyperarithmetic degree and a nonhyperarithmetic degree is uncountable as any Σ_{1}^{1} set with a nonhyperarithmetic member is uncountable. (See, for example, Sacks [43] III.6.) A very natural question is whether every c.e. degree can be realized (with 0) as a degree spectrum. Hirschfeldt [23] has just recently answered this question by adapting and extending the methods presented here to show that all n-tuples of c.e. degrees can be realized as degree spectra. Goncharov [18] asks as Problem 1 which pairs or more generally n-tuples of c.e. degrees can be so realized in a structure of dimension precisely 2 (for pairs) or n for n-tuples.

Finally, we note that all the structures considered in this paper are directed graphs and we use elementary notions from graph theory, such as for example, edge relation, component, path, connectedness, etc. We denote the edge relation in any graph G by E(G). Definitions of these notions can be found in any basic text on graph theory.

2 The Basic Result and Construction

Our goal in this section is to prove the following:

Theorem 13 There exists a relation U in a structure A with exactly two computable presentations A_{0} and A_{1} such that the image U^{A_{0}} of U in A_{0} is c.e. but not computable while its image U^{A_{1}} in A_{1} is computable. Moreover, the relation P = {(x, y)|x ∈U^{A_{0}} ∧ y ∈U^{A_{1}} ∧ there is an isomorphism from A_{0} to A_{1} which extends the map x ↦ y} is computable.

Proof. In order to describe the structure A we need some notation. For a natural number n ≥ 1, consider the directed graph

({0, 1, …, n + 1}, E)

such that E(0, 0), E(n + 1, 1), E(1, 0), and E(i, i + 1) hold for all i ∈ {1, …, n}. We denote this graph by [n]. Thus, we see that [n] is a cycle of length n + 1 with a tag. We call 0 the top of [n] and n + 1 the coding location of the graph [n].

Let A be any set not containing 0. Consider a sequence {B_{n}}_{n∈A} of pairwise disjoint graphs such that each B_{n} is isomorphic to [n]. Define a graph by taking the disjoint union of the graphs B_{n} and identifying the top elements of these graphs. We denote this graph by [A]. Note that [n] is isomorphic to [{n}]. (Warning: We abuse notation by confusing the isomorphism type of [A] and individual graphs isomorphic to [A]. Similarly, we leave the details of choosing computable representations of such graphs for computable sets A and associated operations on such representations (such as disjoint union) to the reader.)

Let [A] and [B] be graphs with disjoint domains. Suppose that the set C = B \ A is nonempty. Let a and c be the top elements of [A] and [C], respectively. Suppose also that the domain of [A] has empty intersection with the domain of [C]. We define a new graph [A] · [B] as follows:

1. The domain of [A] · [B] consists of all elements from [A] or [C] except for the top element of [C].

2. The edge relation E is defined as follows. The pair (x, y) belongs to E if and only if

[(x, y) ∈ E([A]) ⋁((x, y) ∈ E([C]) & y ≠ c)] ⋁(y = a & (x, c) ∈ E([C])).

For example, if G_{1} is isomorphic to [{3, 4}] and G_{2} is isomorphic to [{4, 6}], then G_{1} · G_{2} is isomorphic to [{3, 4, 6}]. Note that [A] · [B] is isomorphic to [B] · [A].

On the set of all graphs we also consider the operation + which, when applied to two graphs, produces a graph isomorphic to the disjoint union of the graphs. The operation + can be extended as follows. Let G_{1}, …, G_{n}, … be a sequence of graphs with disjoint domains. Then

G_{1} + ⋯ + G_{n} + ⋯  (1)

is, by definition, the graph whose domain G is ⋃ G_{i} and the edge relation E(G) is ⋃_{i} E(G_{i}). Note that the components of a graph of the form

[B_{1}] + ⋯ + [B_{n}] + ⋯

are [B_{1}], [B_{2}], . . ..

We want to produce two computable presentations A_{0}, A_{1} of a graph A of the form

[B_{1}] + [B_{2}] + ⋯ + [B_{n}] + ⋯

with B_{i} \ B_{j} ≠ ∅ for all i ≠ j. We will, in fact, also guarantee that this property holds at every stage. More precisely, at stage t the presentations A_{k,t} (for k = 0, 1) will be of the form [B_{1,t}] + [B_{2,t}] + ⋯ + [B_{n,t}] + ⋯ with B_{i,t} \B_{j,t} ≠ ∅ for all i ≠ j. Note that since B_{i} \B_{j} ≠ ∅ for all i ≠ j, the graph A is clearly rigid, that is, it has no nontrivial automorphisms. In addition, we also want to produce a unary relation U on A with the following properties:

1. Any element of U is a coding location.

2. The image U^{A_{0}} of U in A_{0} is computably enumerable but not computable.

3. The image U^{A_{1}} of U in A_{1} is computable.

4. Every computable copy of A is computably isomorphic to either A_{0} or A_{1}.

Thus, the dimension of A is two and the degree spectrum, DgSp(U), of U consists of exactly two c.e. degrees one computable and the other not. Since U^{A_{1}} is computable and U^{A^{0}} is not, the structures A_{0} and A_{1} are not computably isomorphic.

Another important aspect of our construction will provide a computable binary predicate P such that P (x, y) holds if and only if x belongs to U^{A_{0}}, y belongs to U^{A_{1}}, and there exists an isomorphism from A_{0} to A_{1} extending the map x → y. We will need this property to construct computably categorical structures whose expansions by constants are not computably categorical.

Let G_{0}, G_{1}, G_{2}, … be a standard enumeration of all partial computable directed graphs. We also consider a standard enumeration Ψ_{0}, Ψ_{1}, Ψ_{2}, … of all computable partial functions. In order to build a structure A and a unary relation U with the properties above we need to satisfy at least the following requirements for e, j ∈ ω, k ∈ {0, 1}:

D_{e} : U^{A^{0}} ≠ Ψ_{e}

and

R_{j} : If G_{j} is isomorphic to A then G_{j} is computably
isomorphic to A_{0} or A_{1}

As we wish to show that any computable graph G isomorphic to A is computably isomorphic to A_{0} or A_{1} and we know about the special form described above that A_{k} must have, we can limit ourselves to computable graphs G_{j} which are of this form: G_{j} = [B_{1}] + [B_{2}] + ⋯ + [B_{n}] + ⋯ with B_{i} \ B_{j} ≠ ∅ for all i ≠ j. Indeed, we can require that this be true at every stage: G_{j,t} = [B_{1,t}] + [B_{2,t}] + ⋯ + [B_{n,t}] + ⋯ with B_{i,t} \ B_{j,t} ≠ ∅ for all i ≠ j.

Moreover, without loss of generality, we can require that the enumerations G_{j,t} be such that for every component [Y_{t}] of G_{j,t} there is one [X_{t}] of each A_{k,t} such that Y_{t} ⊆ X_{t}. (Only enumerate components in G_{j} when they are of the right form, i.e., a top with cycles attached (to which more cycles can be added later) and contained in one of A_{k,t}. If there are components partially enumerated, do not allow any extensions until it is once again possible to make all the components distinct. This can be done so as to add any single desired element to G if it has the required form.) During the construction we will also need to make U^{A_{1}} computable. This will be achieved by effectively listing all the elements of U^{A_{1}} in strictly increasing order.

The action to meet requirement D_{e} is based on the operations on graphs that we now define.

Definition 14 The L–operation applied to [B_{1}]+⋯+[B_{n}] produces a graph denoted by L([B_{1}], …, [B_{n}]) which is isomorphic to

[B_{1}] · [B_{2}] + ⋯ + [B_{n−1}] · [B_{n}] + [B_{n}] · [B_{1}].

We also adopt the important convention that the elements of the component [B_{i}] are the same ones in the corresponding graph in the component [B_{i}]·[B_{i+1}] of L([B_{1}], …, [B_{n}]) while those elements in the new graph corresponding to ones in [B_{i+1}] of the original graph are new elements in [B_{i}] · [B_{i+1}] (with 1 for n + 1 when i = n). The R–operation applied to [B_{1}]+⋯+[B_{n}] produces the graph R([B_{1}], …, [B_{n}]) isomorphic to

[B_{1}] · [B_{n}] + [B_{1}] · [B_{2}] + … + +[B_{n−1}] · [B_{n}].

We will apply an R operation in the construction only when we also apply an L one and we also have the corresponding convention that the elements of the component [B_{i}] are the same ones in the corresponding graph in the component [B_{i−1}] · [B_{i}] of R([B_{1}], …, [B_{n}]) while those elements in the new graph corresponding to ones in [B_{i}] of the original graph are new elements in [B_{i−1}] · [B_{i}] (with n for 0 when i = 1).

From this definition we obtain the following lemma.

Lemma 15 For any graph [B_{1}] + ⋯ + [B_{n}] the graphs L([B_{1}], …, [B_{n}]) and R([B_{1}], …, [B_{n}]) are isomorphic and extend [B_{1}] + ⋯ + [B_{n}]. □

The L and R–operations can also be applied to some components of a graph G to obtain extensions of G. Indeed, suppose that we have a graph G of the form

[C_{1}] + [C_{2}] + ⋯ + [B_{1}] + [B_{2}] + ⋯ + [B_{n}] + ⋯ + [C_{k}].

Then we can consider two extensions of G:

[C_{1}] + [C_{2}] + ⋯ + L([B_{1}], [B_{2}], …, [B_{n}]) + ⋯ + [C_{k}]

and

[C_{1}] + [C_{2}] + ⋯ + R([B_{1}], [B_{2}], …, [B_{n}]) + ⋯ + [C_{k}].

By Lemma 2.1 these two extensions of G are isomorphic.

Now we explain how to meet each of the requirements D_{e} or R_{j} separately. Here is a strategy to meet just one D_{e}. Begin by constructing structures A_{0} and A_{1} of type

[{1}] + [{2}] + [{3}] + ⋯ + [{3e + 1}] + [{3e + 2}] + [{3e + 3}] + ⋯

As soon as Ψ_{e} equals 0 on the number x which is the coding location in [{3e + 2}], the construction acts by extending structure A_{0} to the structure:

[{1}] + [{2}] + [{3}] + ⋯ + L([{3e + 1}], [{3e + 2}], [{3e + 3}]) + ⋯

and by extending structure A_{1} to the structure:

[{1}] + [{2}] + [{3}] + ⋯ + R([{3e + 1}], [{3e + 2}], [{3e + 3}]) + ⋯

The construction then puts x into U^{A_{0}} and puts its image y in A_{1} into U^{A_{1}}. This action meets requirement D_{e}. Note that the number put into U^{A_{1}} is new by our convention on applying the L and R operations. The construction also puts (x, y) into P.

A strategy to meet just one R_{j} is as follows. Begin by constructing structures A_{0} and A_{1} of the type

[{1}] + [{2}] + [{3}] + ⋯ + [{3e + 1}] + [{3e + 2}] + [{3e + 3}] + ⋯

At stage 0 let the partial isomorphism from G_{j} to A_{0} to A_{1} be empty. At stage i wait until G_{j} provides components B_{1}, B_{2} and B_{3} isomorphic to [{3i + 1}], [{3i+2}], and [{3i+3}]. As soon as G_{j} provides such components, say B_{1}, B_{2}, B_{3}, extend the previous partial isomorphism by adding partial isomorphisms from B_{1}, B_{2}, and B_{3} to [{3i + 1}], [{3i + 2}], and [{3i + 3}], respectively. If G_{j} is isomorphic to the structure the construction is building, then the above strategy constructs a computable isomorphism from G_{j} to the structure

[{1}] + [{2}] + [{3}] … [{3e + 1}] + [{3e + 2}] + [{3e + 3}] + …

However, a problem can arise even in the case when the construction tries to satisfy all requirements D_{e} and just one R_{j} simultaneously. Here is a brief and informal explanation of the problem. Suppose that the construction has acted to meet requirement R_{j} on the components [{3e + 1}], [{3e + 2}], and [{3e + 3}] and has not yet acted to meet D_{e}. In other words G_{j} has provided components, say B_{1}, B_{2}, B_{3}, isomorphic to [{3e+1}], [{3e+2}], and [{3e+3}], respectively, and hence the construction has a partial isomorphism, say r_{0}, from G_{j} into A_{0} defined on this coding locations; in addition Ψ_{e} has not yet been defined on the coding location in [{3e + 2}]. Suppose that at a later stage of the construction Ψ_{e} equals 0 on the coding location in [{3e + 2}]. The construction acts to meet D_{e} using R and L–operations. However, the construction now cannot guarantee that r_{0} can be extended to an isomorphism from G_{j} to A_{0}. Indeed, suppose that at a later stage G_{j} provides components isomorphic to the components of A_{0} containing the coding location and that r_{0} cannot be so extended. (Perhaps the component previously isomorphic to [{3e+2}] is now isomorphic to [{3e+1}]·[{3e+2}] and so not to [{3e + 2}] · [{3e + 3}] which is the new isomorphism type of the component to which it had previously been isomorphic.) The construction now changes its mind and attempts to begin constructing a new isomorphism from G_{j} to A_{1}. But, an action to meet another requirement D_{e′} at some later stage can force the construction to change its mind again and begin constructing yet another isomorphism from G_{j} to A_{0}, etc. Thus, one can see that infinitely many D_{e}’s can potentially force the construction to change its mind infinitely many times, and hence, to not satisfy R_{j}.

Now, we define some of the basic notions of our construction. First, we present a module satisfying all requirements D_{e} and just one requirement R = R_{j} for G = G_{j}, the j^{th} partial computable graph of the appropriate form. For t ∈ ω, let G_{t} be the approximation to G at stage t. We always use k to be either 0 or 1, and let k + 1 = 1 if k = 0 and k + 1 = 0 if k = 1. This module will construct isomorphic structures A_{0} and A_{1}, unary relations U^{A_{0}} and U^{A_{1}}, and a binary predicate P. If G is isomorphic to A_{0}, then G will be computably isomorphic to either A_{0} or A_{1}. Our construction proceeds by stages. At stage t of the module, we use the following notions and terminology.

1. Finite Structures A_{0,t} and A_{1,t}. These are approximations to the isomorphic structures A_{0} and A_{1} that the construction is building. That is, for k = 0, 1, we will have

A_{k,t} ⊂ A_{k,t+1} and A_{k} = ⋃_{t} A_{k,t}.

Therefore the structure A_{k} = ⋃_{t} A_{k,t} is computable. The structures A_{0,t} and A_{1,t} are isomorphic to each other. Each A_{k,t} is of the form

[A_{k,t}^{0}] + [A_{k,t}^{1}] + … + [A_{k,t}^{t}],

where, for all n ≠ m, A_{k,t}^{n} \A_{k,t}^{m} ≠ ∅. By construction, we also guarantee that A_{k,t}^{n} ⊂ A_{k,t+1}^{n} and that at the end A is isomorphic to

[A_{k}^{0}] + [A_{k}^{1}] + … + [A_{k}^{n}] + …,

where each A_{k}^{m} = ⋃_{t} A_{k,t}^{m} and A_{k}^{m} \ A_{k}^{s} ≠ ∅ for s ≠ m.

2. To each requirement D_{e} the construction assigns a coding location a_{e} not in U^{A_{0}}. One of the goals of the construction is to put a_{e} into U^{A_{0}} if Ψ_{e}(a_{e}) = 0. (Its image in A_{1} will go into U^{A_{1}} but a_{e} itself will not.) Each of these coding locations will be in a different component of A_{0,t}. Success in such an attempt meets requirement D_{e} on the number put into U^{A_{0}}.

3. Functions r_{t}^{0} and r_{t}^{1}. At stage t each r_{t}^{k} is a partial isomorphism from G_{t} into A_{k,t} one of which is the construction’s (designated) isomorphism. The function r_{t}^{k} may extend its previous isomorphism r_{t−1}^{k}. If r_{t}^{k} does not extend the previous isomorphism, then we say that the construction changes its (designated) isomorphism from r_{t}^{k} to r_{t}^{k+1}.

4. The special G–component. The construction picks a component S_{t}(G) of the structure G called the special G–component. If there exist infinitely many stages at which the construction changes its isomorphism, then the special component S(G) = ⋃_{t} S_{t}(G) becomes infinite, all components in A_{0} (and hence in A_{1}) which can be embedded into S(G) are finite, and therefore G is not isomorphic to A_{0}. (We say a component [Y] can be embedded into one [X] just in case Y ⊆ X.) If, after some stage t_{0}, the construction never changes its (designated) isomorphism from r^{k} and G is isomorphic to A, then G will be computably isomorphic to A_{k} via r^{k} = ∪{r_{t}^{k}|t ≥ t_{0}}.

5. Special Components [S]_{t}^{k}, k = 0, 1. The construction ensures that [S]_{t}^{0} is isomorphic to [S]_{t}^{1}. The special component [S]_{t}^{k} is one of the components of A_{k,t}, that is [S]_{t}^{k} is one of the [A_{k,t}^{j}] for some j ≤ t. At stage t, the special G–component S_{t}(G) in the structure G can be embedded into these components. Moreover, if R recovers at stage t (see the definition of recovery below), then these components satisfy the following properties.

1. If the construction does not change its isomorphism from r^{k}, then [S]_{t−1}^{k} is a substructure of [S]_{t}^{k} and, if it participated in an L or R operation at t, [S]_{t}^{k+1} ⋂[S]_{t−1}^{k+1} = ∅.

2. If the construction changes its isomorphism from r^{k} to r^{k+1}, then [S]_{t−1}^{k+1} is a substructure of [S]_{t}^{k+1} and [S]_{t−1}^{k} ⋂[S]_{t}^{k} = ∅.

3. If, after some stage t′, the construction never changes its isomorphism from r^{k}, recovers infinitely many times, and G is isomorphic to A, then the construction guarantees that the special G–component S(G) is isomorphic to ⋃_{t>t′}[S]_{t}^{k}.

6. Marking with □_{w} and Recovery. If, for a component X in A_{k,t}, there exists a unique component Y in G_{t} such that Y can be embedded into X but not into any other component of A_{k}, then we say that Y is covered by X, or equivalently, X covers Y. During the construction some components in A_{k,t} will be marked with a special symbol □_{w} called a waiting mark. We say that R recovers at stage t, or equivalently that stage t is a recovery stage, if, at the beginning of stage t, for each component X in A_{k,t} marked with a □_{w}, there exists a unique component Y such that X covers Y. We use the notion of recovery to show that if G is isomorphic to A, then G is computably isomorphic to either A_{0} or A_{1}. The idea is the following. Suppose that G is isomorphic to A. By construction, each component X in A_{k,t} marked with a □_{w} waits to cover a component in G. As soon as R recovers at a stage t_{1} ≥ t and a unique component Y in G_{t_{1}} is found such that X covers Y, the construction defines an isomorphic embedding from Y to X and then attempts to guarantee that Y is isomorphic to X. If R does not recover at stage t, then we say that R is in the waiting state. If R is always in the waiting state after stage t, then, by construction, G will not be isomorphic to A_{k}.

In the general construction all the objects, as for example coding locations a_{e}, functions r_{t}^{k}, waiting mark □_{w}, etc., defined above will have additional indices which correspond to the nodes of the priority tree. Now we present a module to satisfy R and all requirements D_{e}.

Stage 0. Let A_{0,0} and A_{1,0} be isomorphic to the graph [2]. Let the partial isomorphisms r_{0}^{0} and r_{0}^{1} be empty with r_{0}^{0} the designated partial isomorphism. Put R into the waiting state and mark the components of A_{0,0} and A_{1,0} with □_{w}. When we first have a recovery stage t we will define S_{t}(G) so that S_{t}(G), [S]_{t}^{0} and [S]_{t}^{1} are isomorphic to the graph [2].

Stage t + 1: Substage 1: If this is not a recovery stage we go on to substage 2. If it is a recovery stage, proceed as follows:

Action. Define the partial isomorphisms r_{t+1}^{0} (and r_{t+1}^{1}) on the components marked with a □_{w}: Partial isomorphism r_{t+1}^{0} ( r_{t+1}^{1}) maps a component Y in G_{t} into a component X in A_{0,t} (A_{1,t}) if and only if Y is covered by X. Suppose r_{t}^{k} was the construction’s previously designated isomorphism. We now have the following two cases.

Case 1. Suppose that r_{t+1}^{k} extends r_{t}^{k}. In this case, set the special component in A_{k,t+1} to be [S]_{t+1}^{k}. This special component extends the special component [S]_{t}^{k} of the previous stage. [[In this case, [S]_{t}^{k+1} ⋂[S]_{t+1}^{k+1} = ∅ if it participated in an L or R operation at t.]]

Case 2. Suppose that r_{t+1}^{k} does not extend r_{t}^{k}. In this case, the construction changes its designated partial isomorphism to r_{t+1}^{k+1}. Set the special component [S]_{t+1}^{k+1} in A_{k+1,t+1} to be the image of the special G–component S_{t}(G) under the partial isomorphism r_{t+1}^{k+1}. [[In this case, [S]_{t}^{k} ⋂[S]_{t+1}^{k} = ∅.]]

Substage 2: Extend both A_{0,t} and A_{1,t} by adding a new component isomorphic to the graph [a], where a ≥ 2 is a new number. This extends A_{0,t} and A_{1,t}. Let a_{t+1} be the coding location in the component isomorphic to [a] in A_{0,t+1}. Find the least e ≤ t + 1 for which Ψ_{e,t+1}(a_{e}) = 0 such that we have not yet acted for D_{e}, a_{e} is not in U^{A_{0}} and one of the following conditions is satisfied. (If there is no such e, then go to Substage 3.)

1. There does not exist a z such that r_{t+1}^{k}(z) = a_{e}.

2. This is a recovery stage and, for some z, r_{t+1}^{k}(z) = a_{e}.

Action for D_{e}. Suppose that the first condition holds. Let X be the component in A_{0,t} containing the coding location a_{e}. Let X′ be the isomorphic image of X in A_{1,t}. Extend A_{0,t} and A_{1,t} by performing operations L(Y, X, Z) in A_{0,t+1} and R(Y′, X′, Z′) in A_{1,t+1}, with Y, Z and Y′, Z′ new components isomorphic to [y], [z], respectively, where y, z are new numbers. Put a_{e} into U^{A_{0}} and its image v in R(Y′, X′, Z′) (which is a new number and hence greater then all the numbers in U^{A_{1}} up to this stage) into U^{A_{1}}. Put (a_{e}, v) into P. Note that we have successfully met requirement D_{e}. Also the structures A_{0,t} and A_{1,t} have been extended to new isomorphic structures A_{0,t+1} and A_{1,t+1}, respectively. Now go to substage 3.

Suppose that the second condition holds. Consider the special components [S]_{t}^{0}, [S]_{t}^{1}, S_{t}(G) in A_{0,t}, A_{1,t}, and G_{t}, respectively. We have two subcases.

Subcase 2.1. There is a sequence of components B_{2}^{0}, X^{0}, C_{2}^{0}, B_{1}^{0}, [S]_{t}^{0}, C_{1}^{0} in A_{0,t} and of their isomorphic images B_{2}^{1}, X^{1}, C_{2}^{1}, B_{1}^{1}, [S]_{t}^{1}, C_{1}^{1} in A_{1,t} such that the following conditions hold:

1. The coding location a_{e} is in X^{0}.

2. The components B_{2}^{k} and C_{2}^{k} have never before participated in any operation.

3. For each k ∈ {0, 1}, the image of r_{t+1}^{k} has nonempty intersection with every component in the corresponding sequence.

4. If [S]_{t}^{0} and [S]_{t}^{1} have participated in an L– or R–operation (respectively) an even number of times (possibly 0) since the construction last changed its isomorphism (e.g., it just changed it now) then the components B_{1}^{k}, C_{1}^{k} have never participated in any L– or R–operations.

5. If [S]_{t}^{0} has participated in an L-operation an odd number of times since the construction last changed its isomorphism and the designated isomorphism is now r_{t}^{0}, then C_{1}^{0} is the component that played the role of B_{1}^{0} the last time a special component participated in an L–operation and B_{1}^{0}, B_{1}^{1} have never participated in any L– or R–operations. (C_{1}^{1} is the component in A_{1} isomorphic to C_{1}^{0} which was [S]^{1} the last time an operation was applied.)

6. If [S]_{t}^{1}has participated in an L-operation an odd number of times since the construction last changed its isomorphism and the designated isomorphism is now r_{t}^{1}, then B_{1}^{1} is the component that played the role of C_{1}^{1} the last time a special component participated in an R–operation and C_{1}^{1}, C_{1}^{0} have never participated in any L– or R–operations. (B_{1}^{0} is the component in A_{0} isomorphic to B_{1}^{1} which was [S]^{0} the last time an operation was applied.)

In this case, extend A_{0,t} by applying an L–operation to the sequence B_{2}^{0}, X^{0}, C_{2}^{0}, B_{1}^{0}, [S]_{t}^{0}, C_{1}^{0} and extend A_{1,t} by applying an R–operation to the sequence B_{2}^{1}, X^{1}, C_{2}^{1}, B_{1}^{1}, [S]_{t}^{1}, C_{1}^{1}. Note that the image of the coding location a_{e} is a new number v in A_{1,t+1}. Put the pair (a_{e}, v) into P, the number a_{e} into U^{A_{0}}, and the number v into U^{A_{1}}. Note that we have successfully met requirement D_{e} and now have extended structures A_{k,t+1} and A_{k+1,t+1}. Go on to substage 3.

Subcase 2.2. Suppose that the previous subcase does not hold. In this case, add new components to A_{0,t+1} and A_{1,t+1} isomorphic to [b_{1}],[b_{2}], [c_{1}], [c_{2}], where b_{1}, b_{2}, c_{1}, c_{2} are new numbers. Go on to substage 3.

Substage 3: If this is not a recovery stage go on to the next stage. If it is, put a mark □_{w} on each component that has participated in an L– or R–operation, on the new components isomorphic to [a] [b_{i}] or [c_{i}] added on to A_{0} and A_{1} and on the component X in A_{0,t+1} (and on its image X′ in A_{1,t+1}) which has the least number in any component not yet marked with a □_{w}. Go on to the next stage.

This concludes the description of the construction. Now we state several claims about the construction and sketch their proofs. It may be helpful in following the construction above and the proofs below to refer to the diagrams of the results of applying the operations to the special sets and their immediate neighbors in the sequences used supplied later in the proof of Lemma 19.

Claim 1. The construction meets all the requirements D_{e}. Moreover, if at some stage the enumeration of G enters the waiting state and never recovers, then G is not isomorphic to A_{0}.

Proof of Claim 1. Suppose that at stage t, G enters the waiting state and never recovers. There is now clearly an e_{0} such that for every e > e_{0} for which Ψ_{e}(a_{e}) = 0 there is a stage t′ such that at all stages t > t′ the construction satisfies condition 1 of substage 2 via e. Therefore Ψ_{e} ≠ U^{A_{0}} by our action at such a stage t. Of course, if Φ_{e}(a_{e}) ≠ 0, then D_{e} is met automatically. Note that, in this case, all components of A_{k} are finite by construction. Thus it follows from the definition of recovery and the description of stages t+1 that G is not isomorphic to A_{0}. (Of course, satisfying D_{e} for all e > e_{0} implies that D_{e} is satisfied for every e.)

Suppose now that G recovers at infinitely many stages. Let e be the smallest number for which D_{e} is not met. Let t_{1} be such that for all e′ < e, all action for the requirements D_{e′} are finished before stage t_{1}. (Clearly we act at most once for each D_{e}.) Then there exists a stage t + 1 > t_{1} at which Ψ_{e,t+1}(a_{e}) = 0 while condition 2 and Subcase 2.1 of Substage 2 holds. It follows that at stage t + 1, the construction must meet requirement D_{e}. This is a contradiction. □

The next claim gives one of the fundamental properties of recovery.

Claim 2. Consider the sequence

Y_{1}, Y_{2}, Y_{3}, Y_{4}, S_{t}(G), Y_{5}

in G_{t}, and the sequences B_{2}^{k}, X^{k}, C_{2}^{k}, B_{1}^{k}, [S]_{t}^{k}, C_{1}^{k} corresponding to it via the maps r_{t}^{k}. Suppose that at stage t an L–operation is applied to B_{2}^{0}, X^{0}, C_{2}^{0}, B_{1}^{0}, [S]_{t}^{0}, C_{1}^{0} in A_{0} and an R–operation is applied to B_{2}^{1}, X^{1}, C_{2}^{1}, B_{1}^{1}, [S]_{t}^{1}, C_{1}^{1} in A_{1}. Let t′ > t be the least stage at which G recovers. Then G_{t′} satisfies one of the following mutually exclusive properties:

1. Components Y_{1}, Y_{2}, Y_{3}, Y_{4}, S_{t}(G), Y_{5} are covered by B_{2}^{0}·X^{0}, X^{0}·C_{2}^{0}, C_{2}^{0}· B_{1}^{0}, B_{1}^{0}·[S]_{t}^{k}, [S]_{t}^{k} ·C_{1}^{k}, C_{1}^{k} ·B_{2}^{0}, respectively, in A_{0} and the corresponding isomorphic components in A_{1}. If r_{t}^{0} was the designated isomorphism at stage t, this covering corresponds to the fact that at stage t′ the construction did not change its isomorphism from r^{0} to r^{1}. If r_{t}^{1} was the designated isomorphism at stage t, this covering corresponds to the fact that at stage t′ the construction changed its isomorphism from r^{1} to r^{0}.

2. Components Y_{1}, Y_{2}, Y_{3}, Y_{4}, S_{t}(G), Y_{5} are covered by C_{1}^{k} · B_{2}^{0}, B_{2}^{0} · X^{0}, X^{0} · C_{2}^{0}, C_{2}^{0} · B_{1}^{0}, B_{1}^{0} · [S]_{t}^{k}, [S]_{t}^{k} · C_{1}^{k}, respectively, in A_{0} and the corresponding isomorphic components in A_{1}. If r_{t}^{0} was the designated isomorphism at stage t, this covering corresponds to the fact that at stage t′ the construction changed its isomorphism from r^{0} to r^{1}. If r_{t}^{1} was the designated isomorphism at stage t, this covering corresponds to the fact that at stage t′ the construction did not change its isomorphism from r^{1} to r^{0}.

Proof of Claim 2. Note first that there are no changes in any component of A_{k} with elements in the range of r_{t}^{k} between t and t′ as these happen only at recovery stages by construction. The claim now follows directly from the fact that B_{2}^{k}, X^{k}, C_{2}^{k} and one of B_{1}^{k} and C_{1}^{k} have never participated in any operations before and so are of the form [{z}] for distinct numbers z and the definitions of recovery, L–operation, and R–operation. (Each Y_{i} in G can grow into one of two components in A_{k} but once one is determined so are all the others by the requirements of uniqueness in the definition of recovery.) □

Claim 3. A_{k} are of the form [A_{0}^{k}]+⋯+[A_{n}^{k}]+⋯; A_{n}^{k}\A_{m}^{k} ≠ ∅ for n ≠ m and k = 0, 1; and, for each stage t, A_{k,t} are of the form [A_{0,t}^{k}] + ⋯ + [A_{n,t}^{k}] + ⋯; A_{n,t}^{k}\A_{m,t}^{k} ≠ ∅ for n ≠ m and k = 0, 1.

Proof of Claim 3. The second version of the claim (for each stage t) follows immediately by induction from the construction. Moreover, the only way that any of the components [A_{n}^{k}] can be infinite is for there to be infinitely many recovery stages and for the construction to never change its isomorphism after some stage t_{0}. In this case, if the isomorphism remains r^{k} then [S]_{t}^{k} becomes the one infinite component of A_{k}. Thus the disjointness condition for the final components follows from the one at each stage. □

Claim 4. Suppose that G recovers at infinitely many stages. If, after a stage t′, the construction never changes its isomorphism from r_{t}^{k}, then the following hold:

1. For each t > t′, the special component [S]_{t+1}^{k} extends [S_{t}^{k}]. Therefore ⋃_{t→∞}[S]_{t}^{k} is an infinite component.

2. If t′ < t_{1} < t_{2} < … is the sequence of all stages such that during each stage t_{i} the partial isomorphism r_{t_{i}}^{k} properly extends the function r_{t_{i−1}}^{k}, then [S]_{t_{2}}^{k+1} extends [S]_{t′}^{k+1} and each [S]_{t_{2(i+1)}}^{k+1} extends [S]_{t_{2i}}^{k+1}. Therefore the components ⋃_{t≥t′}[S]_{t}^{k} and ⋃_{t≥t′}[S_{2t}^{k+1}] are isomorphic.

3. Each component of A_{k} distinct from ⋃_{t→∞}[S]_{t}^{k} is finite.

4. If G is isomorphic to A, then G is computably isomorphic to A_{k}.

Proof of Claim 4. The first part of this claim follows from the definition of [S]_{t}^{k} at stage t and the assumption. The second part follows from Claim 2 about the properties of the L– and R–operations and the description of the construction at stage t+1. The third part was already noted in the last Claim as, for any component X distinct from [S]_{t}^{k}, there exists a stage t > t′ such that after this stage the component X will never be used and so it is finite. To prove the last part of the claim consider the function r^{k} = ⋃_{t>t′} r_{t}^{k}. By construction, every component X in A_{k} is eventually marked with a □_{w} and so there exists a stage t′′ > t′ such that r_{t′′}^{k}Y ⊂ X for some component Y in G and so r^{k}Y ⊆ X (as the construction never changes its isomorphism). As X is the only component of A_{k} contained in X and G is isomorphic to A_{k}, r^{k} must restrict to an isomorphism of Y onto X. Finally, if there were some component Y′ of G not in the domain of r^{k} then as G is assumed isomorphic to A_{k}, Y would be is isomorphic to some component X of A_{k} but each such X is isomorphic to some Y in G. Thus G would have two isomorphic components and so not be isomorphic to A_{k} by the last Claim.

Claim 5. If the construction changes its isomorphism at infinitely many stages, then the special G–component S(G) is infinite and all components in A_{0} are finite. Therefore G is not isomorphic to A_{0}.

Proof of Claim 5. For each component X, if X is distinct from [S]_{t}^{0} for all t, then X is finite. Therefore it is enough to prove that the components in A_{0} which contain [S]_{t}^{0} for some t are also finite. Let t_{1}, t_{2}, … be the sequence of all stages at which the construction changes its isomorphism. We can suppose that at stage t_{1} the construction changes its isomorphism from r_{t_{1}}^{0} to r_{t_{1}}^{1}. Consider [S]_{t_{1}}^{0} and [S]_{t_{1}−1}^{0}. We have [S]_{t_{1}−1}^{0} ⋂[S]_{t_{1}}^{0} = ∅. Hence, by the construction [S]_{t_{1}−1}^{0} will never be used again. At stage t_{2} the construction changes its partial isomorphism from A_{1} to A_{0}. Now [S]_{t_{1}}^{1} ⋂[S]_{t_{2}}^{1} = ∅ but [S]_{t_{2}}^{0} extends [S]_{t_{1}}^{0}. However, after stage t_{3} the component [S]_{t_{2}}^{0} will never be used. Hence the component containing [S]_{t_{1}}^{0} is finite. Continuing this procedure we see that neither A_{0} nor A_{1} contains an infinite component.

Claim 6. A_{0} and A_{1} are isomorphic.

Proof of Claim 6. It is immediate from the construction that A_{0,t} and A_{1,t} are isomorphic for every t. If there are only finitely many recovery stages, then every component of A_{k} is finite and the claim follows. Otherwise, there is exactly one infinite component in each and they are isomorphic by item 2 of Claim 4. Of course, the finite components are again isomorphic by the existence of isomorphisms at each stage. □

Claim 7. The relation P is computable.

Proof of Claim 7. Each time a pair (x, y) is put into P, y is a new number. Thus, the construction enumerates P in increasing order. □

The above claims prove the correctness of the construction with respect to one R and all D_{e}. □

General Construction. We now describe a construction on a priority tree T that satisfies all the requirements. All nodes of a given length will have a fixed set of possible outcomes with a left to right ordering on them.

The induced lexicographical ordering ≤_{L} on the tree T coincides with the usual priority ordering on T .

For every α ∈ T of length 3j +2, we will define an α–strategy to meet the requirement D_{j}. At stage t, the construction guarantees that some coding location is attached to each accessible node α ∈ T of length 3j + 2. One of the goals of the construction is to satisfy D_{j} on one of these coding locations. The strategy to meet the requirement D_{j} employs the L– and R–operations. These strategies (nodes) have two possible outcomes at a stage t: The outcome is c if the construction now acts or has acted at some previous stage (since α was last initialized) to satisfy the requirement D_{j}. Otherwise, it is d. The left-to-right ordering on these outcomes is c <_{L} d.

For every α ∈ T of length 3j +1, we will define an α–strategy R_{α} to meet the requirement R_{j}. As the structure A we are building will be of the form [A^{0}] + [A^{1}] + ⋯ + [A^{n}] + ⋯ with A^{n} ⊈ A^{m} for n ≠ m, we can limit ourselves to computable graphs G_{j} which are of this form. Moreover, without loss of generality, we can require that the enumerations G_{j,t} be such that at no stage are there components [Y_{0}] and [Y_{1}] of G_{j,t} with Y_{0} ⊆ Y_{1} and that for every component [Y] of G_{j,t} there is one [X] of A such that Y ⊆ X. (Only enumerate components in G_{j} when they are of the right form, i.e., a top with cycles attached (to which more cycles can be added later) and contained in one of A. If there are components partially enumerated, do not allow any extensions until it is once again possible to make all the components distinct. This can be done so as to add any single desired element to G if it has the required form.)

The α-strategy to meet the requirement R_{j} is based on a stagewise definition of potential partial isomorphisms r_{α}^{k} which try to define isomorphisms from the structure G_{j} to A_{k} for k = 0, 1. These strategies have four possible outcomes at a stage t: The outcome is w if R_{α} is in the waiting state; the outcome is k if R_{α} recovers at stage t and the construction does not change its isomorphism from r_{α,t}^{k} to r_{α,t}^{k+1}; the outcome is ∞ if R_{α} recovers at stage t and the construction changes its isomorphism from r_{α,t}^{k} to r_{α,t}^{k+1}. (These notions are analogous to the ones in the construction above and are defined precisely in the general construction below.) The outcomes are ordered as follows: ∞ < 0 < 1 < w.

The nodes α ∈ T of length 3j are devoted to guessing the components of G_{j} that are isomorphic to the infinite special components of A_{0} and A_{1} constructed (one each) by nodes β ⊂ α of length 3n + 1 such that βˆ i ⊂ α for i = 0, 1. This information is needed by the nodes γ of length 3j + 1 to successfully define the required isomorphism r_{γ}^{k}. The possible outcomes of a node of length 3j in order are ∞ < 0 < 1 < … < n < … for n ∈ ω. The intention is that each n corresponds to a different guess as to the required components in G_{j} together with the correspondence to the desired components in A_{k} and ∞ is the outcome that there is no “eligible” guess or each such guess is eventually proven false.

We will define the accessible nodes of the priority tree at stage t by induction on their length. The empty sequence ∅ of length 0 is the root of the priority tree and is accessible at every stage t. If β is accessible at stage t and o is the outcome of β at t, then βˆ o is accessible at t. If |β| < t, we deal with βˆ o, otherwise we terminate the stage and go on to the next one.

To cancel a component means to guarantee to never use it again in any L– or R–operation. By construction, any component X in A_{k,t} (and therefore its isomorphic image in A_{k+1,t}) cancelled at stage t, will never be used at later stages of the construction. Therefore the component containing X in A_{k} will be equal to X itself. Hence X will be finite. To initialize a node β of length 3j + 2 at stage t means to cancel all the components associated with β. To initialize a node β of length 3j + 1 at stage t means to cancel the previous isomorphism r_{β,t−1}^{k} and β-special components [S]_{β,t−1}^{k} in A_{k} and the choice of S(G_{β,t−1}) in G_{j} and all other components associated with β that have participated in an L- or R-operation. If a special component [S]_{β,t−1}^{k} is not cancelled or changed to another component at stage t, the construction keeps [S]_{β,t}^{k} an extension of [S]_{β,t−1}^{k}. We will use this convention (of not changing [S]_{β,t}^{k} without explicit mention) for all other parameters as well.

Now we describe the general construction. Remarks enclosed in double brackets [[like this one]] are explanatory only and not part of the formal construction.

Stage 0. Initialize all requirements β. For each α ∈ T take distinct numbers b_{α,t}, c_{α,t}, b_{β,α,t}, c_{β,α,t}, p_{α,t}, q_{α,t} ≥ t + 2 such that the sets {b_{α,t}, c_{α,t}, b_{β,α,t}, c_{β,α,t}, p_{α,t}, q_{α,t}| t ∈ ω} form a uniformly computable collection of disjoint sets for β ⊂ α ∈ T with infinitely many numbers not in any of them. We say that the numbers b_{α,t}, c_{α,t}, b_{β,α,t}, c_{β,α,t}, p_{α,t}, q_{α,t} are associated with α.

Stage t+1. We proceed to act for each accessible node β in turn until the stage is terminated. Let u be the stage at which β was last initialized and s be the last stage after u at which β was accessible (u if there is no such stage). As a node β is declared accessible we initialize all nodes γ to the right of β, i.e., β <_{L} γ but β ⊈ γ.

Case 0: |β| = 3j. If the outcome of β at s was ∞ or s = u, the outcome of β is now the least n that has never been the outcome of β since u and is a code for a sequence of components of G_{j} that is eligible to be isomorphic to the corresponding special components [S]_{γ}^{k} of A_{k} for γˆ k ⊆ β. (If there are no γ of length 3i + 1 with γˆ k ⊆ β for k = 0 or 1, no guessing is needed and the outcome of β is always 0, the code for the empty correspondence.) We say that a component [Y] of G_{j} (which at stage t is [Y_{t}]) is eligible to be isomorphic to [S]_{γ}^{k} at stage t, if q_{γ,v} ∈ Y_{t} where v is the stage at which [S]_{γ}^{k} was last defined after u [[necessarily as [q_{γ,v}]]] and Y_{t} ⊆ X_{t} or Y_{t} ⊆ Z_{t}where [S]_{γ,t}^{k} = [X_{t}] and [Z_{t}] is isomorphic to a component that participated in an L- or R-operation with [S]_{γ}^{k} the last time it participated in one. [[This last option is included because such a set may grow into the desired special component.]] If there is no such n, the outcome of β is ∞. If the outcome of β at s was some n ∈ ω, we see if we have irrefutable evidence that one element of the sequence of components of G_{j} coded by n is not isomorphic to the corresponding special components [S]_{γ}^{k} of A_{k} for γˆ k ⊆ β. If so, the outcome of β is ∞; if not, it is n. We say that we have irrefutable evidence at stage t that a component [Y] of G_{j} (which at stage t is [Y_{t}]) is not isomorphic to [S]_{γ}^{k} if there is a z ∈ Y_{t} which is not associated with γ.

Case 1: |β| = 3j + 1. If β = δˆ ∞, we think that G_{j} is not isomorphic to A and so do not need to do anything for R_{j}. In this case, the outcome of β is w. Suppose then that β = δˆ n for some n ∈ ω. We say that R_{β} recovers at stage t + 1, or equivalently that stage t + 1 is a β-recovery stage, if the following conditions hold:

1. Ignoring the components of G_{j} picked out by the outcome n of δ and the associated special components in A_{0} and A_{1} in the definition of covering, there exists (for each of k = 0, 1), for each component X in A_{k,t+1} marked with a □_{w}^{β}, a unique component Y such that X covers Y.

2. If there has already been a β-recovery stage since u, we also require that, for each component [Z_{t}] in the sequence coded by n that is supposed to correspond to [S]_{γ}^{k} for γˆ k ⊆ β, Z_{t} ⊆ W where [W] = [S]_{γ,v}^{k} for the last β-recovery stage v.

Otherwise, we say that R_{β} is in the waiting state at t + 1. In the latter case, the outcome of β is w. If at t + 1 there is no special component for β, we add components isomorphic to [q_{β,t+1}] to A_{0,t+1} and A_{1,t+1} which we say are associated with β. (Note that when we perform an L- or Roperation the components maintain their association with a node α the same way they maintain their original elements, that is if a component originally associated with α contains various numbers when first added to the graph then the component containing those numbers is associated with α at every later stage.) We declare the components isomorphic to [q_{β,t+1}] to be the special components [S]_{β,t+1}^{k} for β and mark them with □_{w}^{β}. We also let r_{β,t+1}^{0} and r_{β,t+1}^{1} be empty and designate r_{β,t+1}^{0} as the construction’s isomorphism for β at t + 1. In this case, too we let the outcome of β be w.

If t+1 is a recovery stage for R_{β} and there is a special component for β we define the partial isomorphisms r_{β,t+1}^{k} (for k = 0, 1 ) from some components Y of G_{j,t+1} into components X of A_{k} marked with □_{w}^{β} by making r_{β,t+1}^{k}Y ⊂ X if this is correspondence coded by n matches Y and X . If the correspondence does not mention Y or X, we make r_{β,t+1}^{k}Y ⊂ X if and only if Y is covered by X when we ignore the components mentioned by the code n and their corresponding components in A_{0} and A_{1}. If S(G_{β,s}) was not defined, we set it to be the component of G_{j} mapped into [S]_{β}^{0} by r_{β,t+1}^{0}. We now define the outcome of R_{β} as follows:

Subcase 1. Suppose that r_{β,t+1}^{k} extends the previous designated isomorphism r_{β,s}^{k}[[= r_{β,t}^{k} and component [S]_{β,t+1}^{k} extends [S]_{β,t}^{k} (and [S]_{β,t}^{k} = [S]_{β,s}^{k})]]. In this case, the outcome of β is k.

Subcase 2. Suppose that r_{β,t+1}^{k} does not extend the previous designated isomorphism r_{β,t}^{k}. In this case, the construction changes its (designated) isomorphism from r_{β,t}^{k} to r_{β,t+1}^{k+1} and the outcome of β is ∞. [[Note that, in this case, the component [S]_{β,t+1}^{k+1} extends [S]_{β,t}^{k+1} (and [S]_{β,t}^{k+1} = [S]_{β,s}^{k+1}) and [S]_{β,t+1}^{k} ⋂[S]_{β,t}^{k} = ∅.]]

In either subcase of a recovery stage with the special component already defined, we put marks □_{w}^{β} on any component of A_{k} that has participated in an L- or R-operation since s, on any new components added since s and on the component which has the least number of any one without a mark □_{w}^{β}.

Case 2: |β| = 3j + 2. If βˆ c was the outcome of β at s, it is so again. If not, and there is no coding location attached to β, we add components isomorphic to [b_{β,t+1}], [c_{β,t+1}] and [p_{β,t+1}] to each of A_{0,t+1} and A_{1,t+1} which we associate with β and attach the coding location in the copy of [p_{β,t+1}] to β. Let a be the coding location attached to the node β. Let X^{0} be the component in A_{0,t+1} containing the coding location a and X^{1} be the isomorphic image of X^{0} in A_{1,t+1}. Let B_{n+1}^{k} and C_{n+1}^{k} be the components that we associated with β at the stage at which a was attached to it.

Let k_{1} < … < k_{n} ≤ t + 1 be the sequence of numbers i such that β(3i + 1) ≠ w. We let β_{i} denote β ↾(3k_{i} + 1). If there are no such numbers, n = 0 and the corresponding conditions in the description below are vacuous. If it is not the case that Ψ_{j,v}(a) = 0, the outcome of β is d. If this is the first stage v since u at which β is accessible such that Ψ_{j,v}(a) = 0, we add new components to A_{0,t+1} and A_{1,t+1} isomorphic to [b_{β,β_{i},,t+1}] and [c_{β,β_{i},t+1}] associated with β_{i} for each i ≤ n . In this case, the outcome of β is also d. Otherwise, we have two subcases.

Subcase 2.1. There exists a sequence

B_{n+1}^{0}, X^{0}, C_{n+1}^{0}, B_{n}^{0}, [S]_{β_{n},t+1}^{0}, C_{n}^{0}, …, B_{1}^{0}, [S]_{β_{1},t+1}^{0}, C_{1}^{0}

of components in A_{0,t+1} and the corresponding isomorphic image

B_{n+1}^{1}, X^{1}, C_{n+1}^{1}, B_{n}^{1}, [S]_{β_{n},t+1}^{1}, C_{n}^{1}, …, B_{1}^{1}, [S]_{β_{1},t+1}^{1}, C_{1}^{1}

of the sequence in A_{1,t+1} such that B_{i}^{k} and C_{i}^{k} are associated with β_{i} with the following properties:

1. For each i ∈ {1, …, n} and k ∈ {0, 1}, the image of r_{β_{i},t+1}^{k} has nonempty intersection with every component in the sequence B_{n+1}^{k}, X^{k}, C_{n+1}^{k}, B_{n}^{k}, [S]_{β_{n},t+1}^{k}, C_{n}^{k}, …, B_{i}^{k}, [S]_{β_{i1},t+1}^{k}, C_{1}^{k}.

2. If [S]_{β_{i},t+1}^{0} and [S]_{β_{i},t+1}^{1} have participated in an L– or R–operation (respectively) an even number of times (possibly 0) since the construction last changed its isomorphism for β_{i} after u (e.g., it just changed it now and so β_{i}ˆ ∞ ⊆ β) then the components B_{i}^{k}, C_{i}^{k} have never participated in any L– or R–operations and are isomorphic to {b_{β,β_{i},u}} and {c_{β,β_{i},u}}, respectively, for some u < t + 1.

3. If [S]_{β_{i},t+1}^{0} has participated in an L-operation an odd number of times since the construction last changed its isomorphism for β_{i} and the designated isomorphism is now r_{β_{i},t+1}^{0}, then C_{i}^{0} is the component that played the role of B_{i}^{0} the last time a special component for β_{i} [[necessarily [S]_{β,i,u}^{0} for some u < t + 1]] participated in an L–operation and B_{i}^{0}, B_{i}^{1} have never participated in any L– or R–operations and are isomorphic to {b_{β,β_{i},u}} for some u < t + 1. [[C_{i}^{1} is the component in A_{1} isomorphic to C_{i}^{0} which was [S]_{β_{i}}^{1} the last time an operation was applied.]]

4. If [S]_{β_{n},t+1}^{1}has participated in an L-operation an odd number of times since the construction last changed its isomorphism for β_{i} and the designated isomorphism is now r_{β_{i},t+1}^{1}, then B_{i}^{1} is the component that played the role of C_{i}^{1} the last time a special component for β_{i} [[necessarily [S]_{β_{i},,u}^{1} for some u < t + 1]] participated in an R–operation and C_{i}^{1}, C_{i}^{0} have never participated in any L– or R–operations and are isomorphic to {c_{β,β_{i},u}} for some u < t + 1. [[B_{i}^{0} is the component in A_{0} isomorphic to B_{i}^{1} which was [S]_{β_{i}}^{0} the last time an operation was applied.]]

Action for D_{j} at β: In this subcase, extend A_{0,t+1} by applying an L– operation to the sequence

B_{n+1}^{0}, X^{0}, C_{n+1}^{0}, B_{n}^{0}, [S]_{β_{n}}^{0}, C_{n}^{0}, … D_{1}^{0}, B_{1}^{0}, [S]_{β_{1},t+1}^{0}, C_{1}^{0}

and extend A_{1,t+1} by applying an R–operation to the sequence

B_{n+1}^{1}, X^{1}, C_{n+1}^{1}, B_{n}^{1}, [S]_{β_{n}}^{1}, C_{n}^{1}, … D_{1}^{1}, B_{1}^{1}, [S]_{β_{1},t+1}^{1}, C_{1}^{1}.

Note that the image of the coding location a is a new number v in A_{1,t+1}. Put the pair (a, v) into P, the number a into U^{A_{0}}, and the number v into U^{A_{1}}.

In this subcase, the outcome of β is c and we terminate stage t + 1. Subcase 2.2. Otherwise, the outcome of β is d. This concludes the description of the construction.

Thus, we have constructed two structures A_{0} and A_{1}, where

A_{0} = ⋃_{t} A_{0,t} and A_{1} = ⋃_{t} A_{1,t}.

The following two lemmas state several basic obvious facts about the construction.

Lemma 16 The following properties hold of the construction:

1. For any component X^{k}, if X^{k} is cancelled at stage t, then the construction never uses the component X^{k} or X^{k+1} in any L– or R–operation after stage t. Therefore X^{k} and X^{k+1} are finite isomorphic components.

2. Component X is infinite if and only if the set {t| at stage t the set X participated in an L– or R–operation} is infinite. □

Lemma 17 Suppose that at a stage t an L–operation (R–operation) is applied to the sequence

B_{n+1}^{k}, X^{k}, C_{n+1}^{k}, B_{n}^{k}, [S]_{β_{n},t}^{k}, C_{n}^{k}, …, B_{1}^{k}, [S]_{β_{1},t}^{k}, C_{1}^{k}.

Consider the node β_{i}. If there exists a stage t′ > t at which a node to the left of β_{i} is accessible, then the components

B_{n+1}^{k}, X^{k}, C_{n+1}^{k}, B_{n}^{k}, [S]_{β_{n}}^{k}, C_{n}^{k}, …, B_{i}^{k}, [S]_{β_{i},t}^{k}, C_{i}^{k}

never participate in any L– or R–operation at any t_{1} > t′, and therefore the components in A_{k} containing

B_{n+1}^{k}, X^{k}, C_{n+1}^{k}, B_{n}^{k}, [S]_{β_{n,t}}^{k}, C_{n}^{k}, …, B_{i}^{k}, [S]_{β_{i},t}^{k}, C_{i}^{k}

are finite. □

Now in order to prove the correctness of the construction, we need to consider the true path P on the tree T , that is the leftmost path on T whose nodes are accessible infinitely often. Thus, η is on the true path iff there are infinitely many stages at which η is accessible and there exists a stage t after which no β to the left of η is accessible. It is clear that there is a unique true path P on T .

Lemma 18 The relation U^{A_{0}} is computably enumerable but not computable. The relation U^{A_{1}} is computable. In particular, the structures A_{0} and A_{1} are not computably isomorphic.

Proof. Note that at stage t if we put an element v into U^{A_{1}}, then v is new and hence is greater than all elements appearing in U^{A_{1}} before stage t. Therefore the construction effectively lists all the elements in U^{A_{1}} in a strictly increasing order. Hence U^{A_{1}} is computable.

Suppose that U^{A_{0}} is also computable and Ψ_{j} is a characteristic function for U^{A_{0}}. Consider the requirement D_{j} and the node η = a_{0} … a_{3j+1} on the true path corresponding to D_{j}. Let t be the first stage such that η is accessible at t but no β to the left of η is ever accessible after stage t. Let a be the coding location which is attached to the node η at stage t and B_{n+1}^{k}, C_{n+1}^{k} be the components associated with η when a was attached to it. If there is no t_{1} > t such that Ψ_{j,t_{1}}(a) = 0, the requirement is clearly satisfied, so suppose there is such a stage and let t_{1} be the first such at which η is accessible. We add new components isomorphic to [b_{β,β_{i},t_{1}}] and [c_{β,β_{i},t_{1}}] at stage t_{1} by construction that can be used in an operation only when we act to satisfy D_{j} at β. Since η is on the true path there exists a stage t_{2} > t_{1} such that at stage t_{2} the node η is accessible and all of these components as well as B_{i}^{k}, C_{i}^{k}, the components isomorphic to [b_{β,β_{i},t_{1}}] and [c_{β,β_{i},t_{1}}], respectively, where the β_{i} are defined as in the construction, have marks □_{w}^{β_{j}} for each j ≤ i ≤ n. (As there are infinitely many β_{i}-recovery stages for each i ≤ n by assumption, there must be such a stage.) At this stage Subcase 2.1 of Case 2 of the construction must hold if we have not already satisfied D_{j} by acting for β. (None of the new components needed can have been used in other operations by construction.) It follows that the construction must meet the requirement D_{j} at stage t_{2} and so Ψ_{j} can not be the characteristic function of U^{A_{0}}. □

Lemma 19 1. Suppose that at a stage t an L–operation is applied to the sequence

B_{n+1}^{0}, X^{0}, C_{n+1}^{0}, B_{n}^{0}, [S]_{β_{n},t}^{0}, C_{n}^{0}, …, B_{1}^{0}, [S]_{β_{1},t}^{0}, C_{1}^{0}.

(And so each β_{i} in the sequence is accessible at t.) Consider the node β_{i} and suppose that the designated partial isomorphism from G_{k_{i}} to A_{0,t} is r_{β_{i},t}^{0} at t. If t_{1} is the first recovery stage for β_{i} after t (and so, in particular, β_{i} is accessible at t_{1}) and, between stage t_{1} and stage t, no nodes to the left of β_{i} are accessible, then the following hold:

(a) If the construction changes its isomorphism from r_{β_{i}}^{0} to r_{β_{i}}^{1} at stage t_{1}, then [S]_{β_{i,t}}^{0} and so the G_{k_{i}}–special component S(β_{i}, t_{1}) is embedded into B_{i}^{0} · [S]_{β_{i,t}}^{0} (the component corresponding to B_{i}^{0}) which becomes [S]_{β_{i},t_{1}}^{0} and [S]_{β_{i},t_{1}}^{0} has empty intersection with component [S]_{βi,t}^{0}.

(b) If the construction does not change its isomorphism from r_{β_{i}}^{0} to r_{β_{i}}^{1} at stage t_{1}, then [S]_{β_{i,t}}^{0} and so the G_{k_{i}}–special component S(β_{i}, t_{1}) is embedded into [S]_{β_{i},t}^{0}·C_{i}^{0} (the component corresponding to [S]_{β_{i},t}^{0}) which becomes [S]_{β_{i},t_{1}}^{0} and [S]_{β_{i},t_{1}}^{0} extends component [S]_{β_{i},t}^{0}. Moreover, the component B_{i}^{0} becomes B_{i}^{0} · [S]_{β_{i},t}^{0}.

2. Suppose that at a stage t an R–operation is applied to the sequence

B_{n+1}^{1}, X^{1}, C_{n+1}^{1}, B_{n}^{1}, [S]_{β_{n},t}^{1}, C_{s}^{1}, …, B_{1}^{1}, [S]_{β_{1},t}^{1}, C_{1}^{1}.

(And so each β_{i} in the sequence is accessible at t.) Consider the node β_{i} and suppose that the designated partial isomorphism from G_{k_{i}} to A_{1,t} is r_{β_{i},t}^{1} at t. If t_{1} is the first recovery stage for β after t (and so in particular β_{i} is accessible at t_{1}) and no nodes to the left of β_{i} are accessible between stage t_{1} and stage t then the following hold:

(a) If the construction changes its isomorphism from r_{β_{i}}^{1} to r_{β_{i}}^{0} at stage t_{1}, then [S]_{β_{i,t}}^{1} and so the G_{k_{i}}–special component S(β_{i}, t_{1}) is embedded into C_{i}^{1} · [S]_{β_{i,t}}^{1} (the component corresponding to C_{i}^{1}) which becomes [S]_{β_{i},t_{1}}^{1} and [S]_{β_{i},t_{1}}^{1} has empty intersection with component [S]_{β_{i},t}^{1}.

(b) If the construction does not change its isomorphism from r_{β_{i}}^{1} to r_{β_{i}}^{0} at stage t_{1}, then [S]_{β_{i,t}}^{1} and so the G_{k_{i}}–special component S(β_{i}, t_{1}) is embedded into B_{i}^{1}·[S]_{β_{i},t}^{1} (the component corresponding to [S]_{β_{i},t}^{1}) which becomes [S]_{β_{i},t_{1}}^{1} and [S]_{β_{i},t_{1}}^{1} extends component [S]_{β_{i},t}^{1}. Moreover, the component C_{i}^{1} becomes C_{i}^{1} · [S]_{β_{i},t}^{0}.

Proof. This lemma is an analog of Claim 2. It is immediate from the definitions of recovery, L–operation, R–operation, and the construction. To make it easier to see this and later points we schematically display the results of applying the operations in various circumstances. For the sake of simplicity, we omit the subscripts for the node β and the stages t as well as the duplications in the product notation (·) for the results of applying the operations. We also omit the superscripts designating which component is in A_{0} and which in A_{1} and just display first the results in A_{0} and then those in A_{1}.

Here is the result of a sequence of operations when the designated isomorphism remains r^{0}. Note that the B_{i} are new components each time. First on A_{0}:

\begin{aligned}B_{0} & ← & [S]^{0} = S_{0} & ← & C_{0} \\ B_{1} & ← & S_{0} · C_{0} & ← & B_{0} · S_{0} \\ B_{2} & ← & S_{0} · C_{0} · B_{0} & ← & C_{2} \\ B_{3} & ← & S_{0} · C_{0} · B_{0} · B_{1} & ← & B_{2} · S_{0} · C_{0} · B_{0} \end{aligned}  (1a)

Next on A_{1}:

\begin{aligned}B_{0} & → & [S]^{1} = S_{0} & → & C_{0} \\ B_{1} & → & C_{0} · S_{0} & → & S_{0} · B_{0} \\ B_{2} & → & S_{0} · B_{0} · C_{0} & → & C_{2} \\ B_{3} & → & C_{2} · S_{0} · B_{0} · C_{0} & → & S_{0} · B_{0} · C_{0} · B_{2} \end{aligned}  (1b)

Here are the results of applying the operations when the designated isomorphism remains r^{1} with the same conventions. Note here that the C_{i} are new components each time. First on A_{0}:

\begin{aligned}B_{0} & ← & [S]^{0} = S_{0} & ← & C_{0} \\ S_{0} · C_{0} & ← & B_{0} · S_{0} & ← & C_{1} \\ B_{2} & ← & S_{0} · C_{0} · B_{0} & ← & C_{2} \\ S_{0} · C_{0} · B_{0} · C_{2} & ← & B_{2} · S_{0} · C_{0} · B_{0} & ← & C_{3} \end{aligned}  (2a)

Next on A_{1}:

\begin{aligned}B_{0} & → & [S]^{1} = S_{0} & → & C_{0} \\ C_{0} · S_{0} & → & S_{0} · B_{0} & → & C_{1} \\ B_{2} & → & S_{0} · B_{0} · C_{0} & → & C_{2} \\ C_{2} · S_{0} · B_{0} · C_{0} & → & S_{0} · B_{0} · C_{0} · B_{2} & → & C_{3} \end{aligned}  (2b)

And finally, here are the results if the construction starts with r^{0} and then changes its isomorphism at each stage so that all the B_{i} and C_{i} are new. First on A_{0}:

\begin{aligned}B_{0} & ← & [S]^{0} = S_{0} & ← & C_{0} \\ B_{1} & ← & B_{0} · S_{0} & ← & C_{1} \\ B_{2} & ← & B_{0} · S_{0} · C_{1} & ← & C_{2} \\ B_{3} & ← & B_{2} · B_{0} · S_{0} · C_{1} & ← & C_{3} \end{aligned}  (3a)

Next on A_{1}:

\begin{aligned}B_{0} & → & [S]^{1} = S_{0} & → & C_{0} \\ B_{1} & → & S_{0} · B_{0} & → & C_{1} \\ B_{2} & → & C_{1} · S_{0} · B_{0} & → & C_{2} \\ B_{3} & → & C_{1} · S_{0} · B_{0} · B_{2} & → & C_{3} \end{aligned}  (3b)

□

Before we prove the next lemma we again note that each component in A_{0} (A_{1}) is of the form [⋃_{t} A_{0,t}^{n}] ([⋃_{t} A_{1,t}^{m}]) for some n (m). We denote this component by A_{0}^{n} (A_{1}^{m}).

Lemma 20 For any component A_{0}^{n} in A_{0} there is a component A_{1}^{m} in A_{1} such that A_{0}^{n} and A_{1}^{m} are isomorphic. Similarly, for any component A_{1}^{n} in A_{1} there is a component A_{0}^{m} in A_{0} such that A_{1}^{n} and A_{0}^{m} are isomorphic.

Proof. Suppose that A_{0}^{n} is finite. There exists a stage t such that A_{0}^{n} = A_{0,t}^{n}. This component cannot participate in an L–operation at any stage t′ > t . Hence its image, say A_{1,t′}^{m} does not participate in an R–operation. Therefore component A_{0}^{n} is isomorphic to A_{1}^{m}. (Only components in A_{0} participate in L-operations and ones in A_{1} in R-operations.)

Suppose now that the component A_{0}^{n} is infinite. Then the set

{t| at stage t the set A_{0,t}^{n} participates in an L-operation }

is infinite. Let t_{1} < t_{2} < … < t_{n} < … be the list of all elements of this set. Consider stage t_{j} for any j. At this stage A_{0,t_{j}}^{n} participates in an L-operation. Let

B_{v+1}^{0}, X^{0}, C_{v+1}^{0}, B_{v}^{0}, [S]_{β_{v},t_{j}}^{0}, C_{v}^{0}, …, B_{1}^{0}, [S]_{β_{1},t_{j}}^{0}, C_{1}^{0}

be all the components participating in this L–operation including A_{0,t_{j}}^{n}. As the components B_{v+1}^{0}, X^{0}, C_{v+1}^{0} can participate in an L-operation at most once, A_{0,t_{j}}^{n} belongs to the set {B_{i}^{0}, [S]_{β_{i},t_{j}}^{0}, C_{i}^{0}} and is associated with an accessible β_{i} for some i ≤ v (and remains so associated). For any stage t between stages t_{j} and t_{j+1}, no node to the left of β_{i} can be accessible since otherwise, by Lemma 2.3, A_{0,t}^{n} would be cancelled and hence finite.

If the construction changes its isomorphism at β_{i} infinitely often then no component associated with β_{i} can participate in an operation infinitely often: The ones playing the roles of B_{i}^{k} and C_{i}^{k} are new each time the isomorphism changes and the [S]_{β_{i}}^{k} change every other time by Lemma 19 and once changed can never be used again. (See (3a) and (3b) above.) Thus there is a least j such that the construction never changes the isomorphism for β_{i} after t_{j}. There are two cases to consider:

Case 1. Suppose that the designated isomorphism is always r_{t_{k}}^{0} for k ≥ j. In this case, the only component of A_{0} that participates infinitely often is the special component [S]_{t_{k}}^{0} which is increasing in k ≥ j. (See (1a) and (1b) above.) Moreover, the components [S]_{t_{j+2k+2}}^{1} are isomorphic to [S]_{t_{j+2k+2}}^{0} and also form an increasing sequence. Thus the two limits ∪{[S]_{t_{j+2k+2}}^{0}}, which is the given A_{0}^{n}, and ∪{[S]_{t_{j+2k+2}}^{1}}, which is some A_{1}^{m}, are isomorphic as required.

Case 2. Suppose that the designated isomorphism is always r_{t_{k}}^{1} for k ≥ j. In this case, the only component of A_{0} that participates infinitely often is the one that alternates between being [S]_{t_{j+2k}}^{0} and playing the role of B_{i}^{0} in the operations at stages t_{j+2k+1}. (See (2a) and (2b) above.) In this case, the two increasing limits ∪{[S]_{t_{j+2k}}^{0}} which is the given A_{0}^{n} and ∪{[S]_{t_{j+2k}}^{1}} which is some A_{1}^{m} are isomorphic as required.

The proof going from A_{1}^{n} to A_{0}^{m} is similar. □

Lemma 21 For each k = 0, 1 and n ≠ m, A_{k}^{n} ⊈ A_{k}^{m}, Moreover, for each k = 0, 1 and n ≠ m, A_{k,t}^{n} ⊈ A_{k,t}^{m} for every t. In addition, each infinite special component [S]_{α}^{k} = [X] has only numbers associated with α in the set X.

Proof. The stage by stage distinctions follow immediately from the construction by induction. The only additional concern is the infinite components. As there is at most one for each α and they are all clearly differentiated by having only cycles of length some q_{α,t}, b_{α,t}, c_{α,t}, b_{β,α,t} or c_{β,α,t} which are all distinct for different α. □

Lemma 22 The structures A_{0} and A_{1} are isomorphic.

Proof. A back and forth argument constructs the desired isomorphism by the previous two lemmas.□

We now wish to prove that all the requirements R_{j} are satisfied. We first analyze the outcomes of the appropriate nodes on the true path under the assumption that G_{j} is isomorphic to A.

Lemma 23 If G_{j} is isomorphic to A, α is the node of length 3j on P and n is the code of the sequence of components of G_{j} isomorphic to the infinite special sets of higher priority (the [S]_{γ}^{k} for γˆ k ⊆ α and |γ| = 3i+1 for i < j) and the correct correspondence between them and the isomorphic components of A_{0} and A_{1}, then αˆ n is on P.

Proof. Let u be the last stage at which α is initialized. It is clear that n is eventually eligible to be the outcome of α as G_{j} is isomorphic to A. As n represents the correct isomorphism on the relevant components, once eligible it can never later fail to be eligible. As all these components [X] = [S]_{γ}^{k} only have numbers z associated γ in the set X, with we can never have irrefutable evidence that n is not the correct outcome. Thus, we only need to show that we get irrefutable evidence that each code m < n is not correct. Each one must have some correspondence between a component [Y] of G_{j} and one [X] of A that is eligible but not correct. For it to be eligible, Y must contain the number q_{γ,v} for the stage v at which we correctly defined [S]_{γ}^{k}. Thus, if Y is not the component of G_{j} isomorphic to [S]_{γ}^{k}, it must be isomorphic to one of the ones that play the role of B_{i} or C_{i} with [S]_{γ}^{k} when some operation is applied. It is obvious from the definition of the sequence of operations (as displayed above) that each such component eventually gets an addition which includes a number not associated with γ for the desired contradiction. □

Lemma 24 If G_{j} is isomorphic to A and β = αˆ n is the node of length 3j + 1 on P, then βˆ k ∈ P for k = 0 or 1.

Proof. Let u be the last stage at which α is initialized. Suppose first that αˆ ∞ ∈ P. Consider the components [S]_{α,t}^{k} and k ∈ {0, 1}. Let t_{0} < t_{1} < t_{2} < … be the sequence of stages after u at which αˆ ∞ is accessible so the construction changes its isomorphism from r_{α,t_{2n}}^{0} to r_{α,t_{2n}}^{1} at stage t_{2n} and from r_{α,t_{2n+1}}^{1} to r_{α,t_{2n+1}}^{0} at stage t_{2n+1} . Then, by construction, after stage t_{2n+k+3} no extension of [S]_{α,t_{2n+k}}^{k} will ever participate in any L– or Roperations. (See (3a) and (3b) above.) Therefore, by the construction, all components extending [S]_{α,t_{i}}^{k} are finite. Consider the corresponding special G_{j}–component α(S) in the structure G_{j}. Note that this special component is infinite but as we have just argued, all of the components of A_{0} which can be embedded in α(S) are finite. (Only components associated with α can be embedded in α(S) by construction.) Thus, we have contradicted the assumption that A and G_{j} are isomorphic.

Next suppose that αˆ w ∈ P and let t_{0} be that least stage at which αˆ w is accessible but after which no node to its left is accessible. So for all t ≥ t_{0}, R_{α} is in the waiting state. Since n is the correct correspondence between the infinite special sets of higher priority and the appropriate components of G_{j}, the enumeration of G_{j} must eventually put into these components all the members in the ones in those of A at t_{0} and so we cannot be waiting for this part of the desired recovery.

Thus we need only consider the finitely many components X in A_{k,t_{o}} (k = 0, 1) marked with □_{w}^{α} other than those coded by n. (No new marks are put down while R_{α} is in the waiting state.) Moreover, each such component X in this set is finite and so eventually constant. (Any components associated with a node to the right of αˆ w were canceled when α was last accessible before t_{0} by our choice of t_{0} and so are finite. None introduced after that stage can get a □_{w}^{α} mark since these are assigned only at α-recovery stages. Components associated with nodes either extending α or to its left can also never participate in an operation again and so are finite. This leaves only components associated with γˆ k ⊂ α. Of these, the only ones that can possibly become infinite are the special components [S]_{γ}^{k} and their isomorphic images in A_{k+1}but these are excluded from consideration as being coded for by n by the previous Lemma.) As G_{j} is isomorphic to A, there is eventually be a stage t > t_{0} at which G_{j,t} has an isomorphic copy of each such finite marked component X. The only way we would not now get a recovery stage (for the desired contradiction) is for there to be an additional component of G_{j,t} which is also isomorphically embeddable into one of these X’s. However, we explicitly prohibited such a situation from ever occurring in our enumeration of G_{j}. □

Lemma 25 If G_{j} is isomorphic to A, β = αˆ n is the node of length 3j + 1 on P and βˆ k ∈ P for k = 0 or 1, then G_{j} is computably isomorphic to A_{k}.

Proof. Consider the effective sequence

t_{1} < t_{2} < t_{3} < …

such that no γ to the left of βˆ k is accessible after t_{1} and βˆ k is accessible at each stage t_{i}. Since the outcome of the node β at each of these stages is k, it follows that the sequence

r_{β,t_{1}}^{k}, r_{β,t_{2}}^{k}, r_{β,t_{3}}^{k}, …

is a sequence of partial isomorphisms such that r_{β,t_{i}}^{k} ⊂ r_{β,t_{i+1}}^{k} for all i ≥ 1. (The argument is as in the case of only one R_{j} with a few additional remarks: All components associated with nodes to the right of βˆ k are cancelled and so undergo no further changes. None associated with nodes to the left of βˆ k can participate in an operation (and so change) by our choice of t_{1}. None associated with a node extending βˆ k can participate in an operation until βˆ k is again accessible. Finally, the only ones associated with nodes γ ⊆ βˆ k that can participate in operations must participate only with triples one of whose components is the true special set for γ. As the image for this set is fixed by the code n, the other components cannot change their preimage under r^{k} either.)

Moreover, by the assignment procedure for marks □_{w}^{β}, every component eventually gets such a mark. Consider the function r^{k} = ⋃_{i≥1}(r_{β,t_{i}}^{k}) and any component [Y] of G such that [Y] ⋂ dom(r^{k}) ≠ ∅. It is clear that r^{k} is an embedding of [Y] into some component [X] of A_{k}. As G_{j} is isomorphic to A_{k} and there are no two components of A_{k} such that one can be embedded in the other by Lemma 21 nor can there be any proper embedding of any component into itself by construction, r^{k} must restrict to an isomorphism of [Y] into [X]. As every component of A_{k} eventually gets a □_{w}^{β}, r^{k} maps onto A_{k}. If some component [Y] of G_{j} were not in the domain of r^{k} then it would still be isomorphic to some [X] in A_{k} and so there would be two isomorphic components in G_{j} and so in A_{k} again contradicting Lemma 21. Thus r^{k} is the desired computable isomorphism. □

Lemma 26 The relation P is computable.

Proof: Each time a pair (x, y) is put into P, y is a new number. Thus, the construction enumerates P in increasing order. □

The above lemmas prove the correctness of the construction. Thus we have proved Theorem 2.1 □

3 The Degree Spectra Problem

This section gives a positive solution to the The Degree Spectra Problem (Question 1.15). Our proof is based on the ideas of the proof of Theorem 2.1 from the previous section. We give the basic ideas of our proof. However, we do not intend to give the full proof of this result simply because we do not want to repeat the arguments and construction which are similar to the ones from Theorem 2.1.

Theorem 27 For any computable partially ordered set D there exists a structure A of dimension the cardinality of D and a relation U on A whose degree spectrum, DgSp(U), is isomorphic to D. Indeed, we can guarantee that U^{B} is computably enumerable for every computable presentation B of A and that if D contains a least element, then the least element of DgSp(U) is 0. Moreover, we can choose representatives A_{i} of the degree spectrum of A such that the relation P = {(x, y)| there are i and j such that d_{i} ≰ d_{j} ∧ x ∈U^{A_{i}} ∧ y ∈U^{A_{j}} ∧ there is an isomorphism from A_{i} to A_{j} which extends the map x ↦ y} is computable where the isomorphism between DgSp(U) and D takes d_{i} to U^{A_{i}}.

Sketch of the Proof. Let d_{0}, d_{1}, … be an effective list, without repetitions, of all elements of the partially ordered set D. The goal is to construct a computable sequence A_{0}, A_{1}, … of computable structures (actually digraphs) each one isomorphic to a single rigid structure A which has a relation U such that the following properties hold:

1. Any computable presentation B of A is computably isomorphic to one of A_{0}, A_{1}, . . ..

2. The isomorphic images U^{A_{0}}, U^{A_{1}}, … of the relation U in A_{0}, A_{1}, …, respectively, are such that for all i, j ∈ ω, d_{i} ≤ d_{j} in D if and only if U^{A_{i}} ≤_{T} U^{A_{j}}.

3. The predicate P, such that for all (x, y) the pair (x, y) ∈ P if and only if there are i, j such that d_{i} ≰ d_{j} with x ∈ U^{A_{i}}and y ∈ U^{A_{j}} for which the mapping x → y can be extended to an isomorphism from A_{i} to A_{j}, is computable.

Let G_{0}, G_{1}, G_{2}, … be a standard enumeration of all computably enumerable digraphs. In order to build a structure A and a unary relations U with the properties above we need to satisfy at least the following requirements:

D_{n,m} : d_{m} ≤ d_{n} if and only if U^{A_{m}} ≤_{T} U^{A_{n}}

and

R_{j} : If G_{j} is isomorphic to A then G_{j} is computably
isomorphic to one of A_{0}, A_{1}, …

where n, m, j ∈ ω, and n ≠ m. Let Ψ_{0}^{X}, Ψ_{1}^{X}, … be an effective enumeration of all computable partial functions with oracle X. For all n, m ∈ ω, in order to satisfy requirement D_{n,m}, our construction needs to divide the requirement into infinitely many (sub)requirements:

1. If d_{m} ≤ d_{n}, then D_{e,n,m} : U^{A_{n}} ≤_{T} U^{A_{m}}.

2. If d_{m} ≰ d_{n}, then D_{e,n,m}: U^{A_{m}} ≠ Ψ_{e}^{U^{An}} where e, n, m ∈ ω.

Thus, our construction must satisfy requirements R_{j} and D_{e,n,m} for all j, n, m, e ∈ ω with n ≠ m.

A construction of the sequence A_{0}, A_{1}, A_{2}, … and unary predicates U^{A_{0}}, U^{A_{1}}, U^{A_{2}}, … can be carried out in a priority construction on a tree T defined as follows. For each requirement R_{j} there is level l(R_{j}) ≥ j on the tree T such that each node β of this level is devoted to satisfying R_{j} and has exactly j +2 immediate successors βˆ ∞, βˆ 0, βˆ 1, …, βˆ j, βˆ w. For each requirement D_{e,n,m} with d_{m} ≰ d_{n} there is a level l(D_{e,n,m}) on the tree T such that each node β of this level is devoted to satisfy D_{e,n,m} and has exactly 2 immediate successors βˆ c and βˆ d. Moreover, we also assume that l(D_{e,n,m}) > l(R_{n}) and l(D_{e,n,m}) > l(R_{m}) for all e, n, m ∈ ω. Here are the notions and ideas which are used in the construction.

At stage t each accessible node α of length l(R_{j}) has a special component S_{α,t}. The node α also has a potential finite partial isomorphisms r_{α,t}^{0}, …, r_{α,t}^{j} from G_{j} to A_{0,t}, …, A_{j,t} (one of which is the designated one for the construction at t). (As before these partial isomorphisms are based on a guess as to the correct correspondence between the infinite special components of higher priority and the appropriate components of G_{j}.) The idea is that if G_{j} is going to be isomorphic to the graph the construction is building, then the construction attempts to force the graph G_{j} to be computably isomorphic to one of A_{0}, …, A_{j} as follows. Suppose that α is on the true path. Then α can have j + 2 many outcomes. If the outcome is αˆ ∞, then this corresponds to the fact that the construction changes its mind about its potential isomorphism infinitely often. Hence the special component S_{α} becomes infinite, all the components in A which can be embedded into S_{α} are finite, and therefore G_{j} is not isomorphic to A. If the outcome of α is αˆ w, then at node α G_{j} is the waiting state and hence can not be isomorphic to A. If the outcome is αˆ i for some i ≤ j, then G_{j} is computably isomorphic to A_{i}.

At stage t for each node α of length l(D_{e,n,m}) the construction picks a coding location a_{α,t} and attempts to meet requirement D_{e,n,m} of the form U^{A_{m}} ≠ Ψ_{e}^{U^{An}} at this location. The idea is the following. First of all the action to meet any requirement of type D_{e,n,m} is based on performing L as well as R–operations in the structures the construction is building. Suppose that α on the true path. There is a stage t′ such that no β to the left of α is ever accessible after t′. We can assume that the coding location a_{α,t} is attached to the node after this stage. If there exists a stage t_{1} > t′ such that Ψ_{e,t_{1}}^{U^{A_{n,t}}}(a_{α,t}) = 0, then the construction puts a_{α,t} into U^{A_{m}} at some αstage. Moreover, the construction puts the images of a_{α,t} into U^{A_{i}} for i ≠ m. These images of the coding location a_{α,t} are new numbers if d_{m} ≰ d_{i} and are the same number a_{α,t} put into U^{A_{m}} if d_{m} ≤ d_{i}. This is accomplished by performing an L–operation in A_{i,t} when d_{m} ≤ d_{i} and an R–operation in A_{i} when d_{m} ≰ d_{i}. This clearly makes U^{A_{m}} ≤_{T} U^{A_{i}} if d_{m} ≤ d_{i}. It is also basically why the predicate P is computable: whenever a pair is put into P at t, one of its elements and so the pair itself is larger than t. Note, that the requirement D_{e,n,m} is met as all lower priority requirements are initialized and so cannot put a number less than the use of the computation into U^{A_{n}}. No higher priority requirement can act to put in any numbers by our choice of t′. Hence Ψ_{e}^{U^{An}} can not be the characteristic function for U^{A_{m}}. Of course, all the U^{A_{i}} are c.e. by construction. If d_{i} is the least element of D, then there are no diagonalization requirements of the form D_{e,n,i} and so the only new numbers are put into U^{A_{i}} which is therefore computable as desired.

The argument that the requirements R_{j} are all satisfied by the node α on the true path associated with R_{j} is the same as in the construction of the previous section except that there are possible outcomes 0, 1, …, i, …, j corresponding to claim that the map r_{α}^{i} = ∪{r_{α,t}^{i}|t > t_{0}} is a computable isomorphism from G_{j} to A_{i} where αˆ i is on the true path and t_{0} is the least stage at which αˆ i is accessible but no node to its left is ever accessible again. (As before, if the αˆ w or αˆ ∞ is on the true path then G_{j} is not isomorphic to A.) □

4 Applications

In this section we provide several applications of the techniques developed in the previous sections. The first application answers Question 1.8 posed by Goncharov. The second application answers Question 1.12 and thus giving a new solution to the Ash–Goncharov problem. The third application answers Question 1.13 about the connections between Scott families and categoricity. We begin by answering Question 1.8:

Theorem 28 There exists a structure B which has exactly two computably enumerable presentations B_{1} and B_{2} such that the following properties hold:

1. B_{1} is a computably enumerable but not computable structure.

2. B_{2} is a computable structure.

3. Any computably enumerable presentation C of B is computably isomorphic to either B_{1} or B_{2}.

Proof. Consider the structure A constructed in the proof of Theorem 2.1. Let U be the unary relation in A for which U^{A_{0}} is computably enumerable but not computable and U^{A_{1}} is computable. Expand the structure A by adding to the language of A two predicate symbols U and E. Set the interpretation of U to be the unary predicate U constructed in Theorem 2.1. Set the interpretation of E to be a binary predicate E such that for all x, y, (x, y) ∈ E if and only if x ≠ y. Define B to be the expanded structure (A, U, E). Obviously, the structure B_{0} defined as (A_{0}, U^{A_{0}}, E) is a computably enumerable but not computable presentation of B. The structure B_{1} defined as (A_{1}, U^{A_{1}}, E) is a computable presentation of B. The structures B_{0} and B_{1} are isomorphic and are computably enumerable presentations of B. These two presentations are not computably isomorphic. Let C be any other computably enumerable presentation of B. The relation E is a computably enumerable relation in C. The equality relation in C is also computably enumerable. Hence, the equality relation {(x, y)|x = y} of the structure C is computable. Therefore, if we omit the predicate symbols U and E from the language of C, then the structure C′ with the predicates U and E omitted is computably isomorphic to either A_{0} or A_{1}. Hence C is computably isomorphic to either B_{1} or B_{2}. □

Our next result provides a new solution to the Ash–Goncharov problem originally solved in [7]:

Theorem 29 For each natural number k ≥ 2 there exists a computably categorical structure B whose expansion by finitely many constants has exactly k many computable isomorphism types.

Proof. By Theorem 3.1 there is a computable structure A with a unary relation U such that the following properties hold:

1. The structure A has exactly k many computable presentations A_{1}, …, A_{k} whose domains are pairwise disjoint.

2. For all distinct i, j ∈ {1, …, k}, U^{A_{i}} and U^{A_{j}} are Turing incomparable.

3. The binary predicate P, such that for all (x, y), (x, y) ∈ P if and only if there are distinct i, j with x ∈ A_{i} and y ∈ A_{j} for which the mapping x → y can be extended to an isomorphism from A_{i} to A_{j}, is computable.

To see this, simply let D be a set of k pairwise incomparable elements. (So d_{i} ≠ d_{j} is the same as d_{i} ≰ d_{j}.)

Now, define the desired structure B to be the graph

A_{1} + … + A_{k}

expanded by the predicate P and the equivalence relation E whose equivalence classes are A_{1}, …, A_{k}. Clearly B is a computable structure. Now let B′ be a computable presentation of B. Let A′_{1} and A′_{2} be two equivalence classes in B′. These two substructures of B′ considered as graphs are isomorphic to A. Hence A′_{1} is computably isomorphic to one of A_{1}, …, A_{k}. Without lost of generality suppose that A′_{1} is computably isomorphic to A_{1} via a computable function f_{1} : A_{1} → A′_{1}. If A′_{2} were computably isomorphic to A_{1} via computable function f_{2} : A_{1} → A′_{2}, then we would be able to decide U^{A_{1}} in A_{1} as follows: x in A_{1} belongs to U^{A_{1}} if and only if (f_{1}(x), f_{2}(x)) ∈ P. Hence all A′_{1}, …, A′_{k} are pairwise noncomputably isomorphic. Hence B′ is computably isomorphic to B. Thus, B is computably categorical.

Let a be any designated element from A_{1}. Consider the expanded structure (B, a) with a new constant for a. Let a_{i} and a_{j} be the image of a in A_{i} and A_{j}, respectively. It follows that the structures

A_{1} + … + (A_{i}, a_{i}) + … + A_{k}

and

A_{1} + … + (A_{j}, a_{j}) + … + A_{k}

expanded by the predicate P and the equivalence relation E are isomorphic but not computably isomorphic. Thus, (B, a) has exactly k many computable isomorphism types. □

An immediate consequence is

Corollary 30 There exists a computably categorical structure without a Scott family. □

Now our goal is to strengthen this corollary so as to answer Question 1.13.

Theorem 31 There exists a structure without a Scott family such that every expansion of the structure by a finite number of constants is computably categorical.

Proof. The structure required to establish the theorem is constructed by coding certain (uniformly) computably enumerable families of sets of natural numbers.

Definition 32 A family S of sets of natural numbers has a one-to-one computable enumeration if there is a bijection f : ω → S such that {(i, x)|x ∈ f(i)} is computably enumerable. We then call f a (computable) one-to-one enumeration of S.

We wish to consider a standard preordering on the one-to-one computable enumerations of S that naturally induces an equivalence relation corresponding to computable isomorphism:

Definition 33 A computable enumeration f of S is reducible to g, f ≤ g, if there is a computable Φ such that f = gΦ. If f ≤ g and g ≤ f, then we say that f and g are equivalent.

Note that if f is a one-to-one enumeration of S and f = gΦ, then Φ is a permutation of ω and so f ≤ g. Thus the equivalence classes of oneto-one enumerations are minimal elements in the induced partial ordering. These are the enumerations that we need to consider to define the family that supplies the structure required for the theorem. Informally, computable categoricity corresponds to there being a single such equivalence class and the dimension of a structure corresponds to the number of such classes.

Definition 34 Two computable structures A and B are of the same computable isomorphism type if there is computable isomorphism taking A to B. The dimension of a computable structure A is the number of its computable isomorphism types.

Definition 35 A computable sequence D_{0}, D_{1}, … of (canonical indices for) finite sets is a Scott sequence for a family S if the following properties hold:

1. For each D_{i} there exists exactly one M ∈ S, denoted by M_{i}, such that D_{i} ⊂ M.

2. The set S \ {M_{0}, M_{1}, …} is finite.

From this definition the next lemma follows easily:

Lemma 36 If S has a Scott sequence, then any two computable enumerations of S are equivalent. □

For any given family S, we want to construct a structure A_{S} such that A_{S} has a Scott family if and only if S has a Scott sequence. Thus, let S be a family of sets and let f be a one-to-one computable enumeration of S. We assume that each set in S has at least two elements and does not contain 0 or 1. Consider the following structure A_{f}:

[f(0)] + [f(1)] + [f(2)] + [f(3)] + …

We can assume that A_{f} is a computable structure constructed uniformly in f. Note that the set of all top elements of A_{f} is computable in every computable presentation of A_{f} (they are the elements with outdegree at least 2 and also the ones not part of a cycle.) The following lemma describes the relationship between S and A_{f}.

Lemma 37 The structure A_{f} satisfies the following conditions.

1. If g is a one-to-one computable enumeration of S, then A_{f} is isomorphic to A_{g}.

2. The structure A_{f} is rigid, that is it does not have any nontrivial automorphisms.

3. If g is a one-to-one computable enumeration of S, then A_{f} is computably isomorphic to A_{g} if and only if f and g are equivalent.

4. The dimension of the structure A_{f} is equal to the maximal number of nonequivalent one-to-one computable enumerations of S.

5. The structure A_{f} has a Scott family if and only if S has a Scott sequence.

Proof. To prove 1, first, note that for any pair i, j ∈ ω the graphs A_{f,i} and A_{g,j} are isomorphic if and only if f(i) = g(j). Hence, since f and g are one-to-one enumerations of S, we can conclude that A_{f} is isomorphic to A_{g}.

Any automorphism α of A_{f} must be the identity by the construction of A_{f} and the fact that f is a one-to-one mapping. This proves 2.

Suppose that f and g are equivalent. There exists a computable function Φ such that f = gΦ. Hence A_{f} and A_{g} are computably isomorphic. Let B be a computable presentation of A_{f}. Consider an effective sequence e_{0}, e_{1}, e_{2}, … without repetition of all top elements in B. We define a one-to-one computable enumeration f_{B} of S as follows:

f_{B}(i) = {n| e_{i} is connected to a cycle of length n}.

It follows that B is computably isomorphic to A_{g} if and only if g is equivalent to f_{B}

Part 4 follows from the proof of 3.

We are left to prove the last part of the lemma. Suppose that S has a Scott sequence D_{0}, D_{1}, D_{2}, . . .. Without lost of generality we suppose that D_{i} ⊂ f(i). The case S \ {M_{0}, M_{1}, …} ≠ ∅ can be derived easily from our considerations below simply using the fact that S\{M_{0}, M_{1}, …} ≠ ∅ is finite. We have to prove that A_{f} has a Scott family. Take an x ∈ A_{f}. Find a top element d_{i} which is connected to x. Suppose that the length of the path which connects x with d_{i} is n. Define the following formula: ψ(x) = [there exists a path of length n which connects x with a top element y such that for each m ∈ D_{i} the element y is connected to a cycle of length m]. Now for every s–tuple (x_{1}, …, x_{s}) let ϕ_{(x_{1},...,x_{s})} be ψ(x_{1})& … &ψ(x_{s}). It is not hard to check that the sequence {ϕ_{(x_{1},...,x_{s})}} is a Scott family for A_{f}.

Now suppose for simplicity that A_{f} has a Scott family

ϕ_{0}(x_{1}, …, x_{n_{0}}), ϕ_{1}(x_{1}, …, x_{n_{1}}), …

without parameters. The proof below will show that we do not lose any generality by making this assumption. Let d_{0}, d_{1}, d_{2} … be an effective sequence of all top elements from A_{f}. Let

ϕ_{i_{0}}(x_{0}), ϕ_{i_{1}}(x_{1}), …

be an effective subsequence of the original sequence such that ϕ_{i_{k}}(d_{k}) holds for each k ∈ ω. Since the formulas are all existential and the structure is computable, we can effectively find a finite substructure B_{i} of A_{f} such that d_{i} ∈ B_{i} and ϕ_{i_{k}}(d_{k}) holds in B_{i}. Define

D_{i} = {n| d_{i} is connected to a cricle of length n in substructure B_{i}}.

Since we have a Scott family for A_{f} and since the structure A_{f} is rigid, we can see that the sequence D_{0}, D_{1}, … is a Scott sequence for family S. □

Corollary 38 Any two one-to-one computable enumerations of S are equivalent if and only if A_{f} is computably categorical. □

Now, to prove the Theorem 4.4 it suffices, by the lemma, to build a computably enumerable family S of sets without a Scott sequence any two computable one-to-one enumerations of which are equivalent.

Lemma 39 There is a computably enumerable family S of sets with no Scott sequence any two computable one-to-one enumerations of which are equivalent.

Proof. In order to build a such family S and its one-to-one enumeration f, we need to satisfy the following requirements:

D_{e} : F_{e} is not a Scott sequence for S,

R_{j} : g_{j} ≡ f or g_{j} is not a one-to-one enumeration of S,

where each {g_{j}}_{j} is a computable sequence of all potential one-to-one enumerations of a family of sets and {F_{e}}_{e} is a computable sequence of all potential Scott sequences for S. Now one can see that these requirements are similar to the requirements for constructing a computable structure in Theorem 2.1. We briefly explain how to meet one R_{j} and all D_{e}. The verifications for this much and the modifications needed to prove the full theorem are similar to those for Theorem 13 and are left to the reader.

We set g = g_{i}. For t, n ∈ ω and n ≤ t, let g_{t}(n) be

{x| x ≤ t and x appears in g(n) in fewer than t + 1 steps of a fixed computation procedure for g}.

Our construction proceeds by stages. At stage t, we use the following notions and terminology similar to those in the proof of Theorem 2.1.

1. Enumeration f_{t}. This is an approximation to the enumeration f that the construction is building. That is, for each i ∈ ω, we will have

f(i) = ⋃_{t} f_{t}(i).

2. The family S_{t}. The function f_{t} enumerates a family denoted by S_{t}.

3. To each F_{e}, we assign a set {c_{e}} and a number p_{e}, called witnesses, such that D = {c_{e}, p_{e}|e ∈ ω} is a coinfinite computable set and we set f_{0}(c_{e}) = {p_{e}}. One of the goals of the construction is to meet D_{e} on one of these numbers.

4. Potential Reduction Function r_{t}. The map r_{t}, is the function which potentially reduces g_{t} to f_{t} at stage t. The function r_{t} can extend the previous potential reduction r_{t−1}. If r_{t} does not extend the previous potential reduction, then we say that the construction changes its potential reduction.

5. Let i ∈ dom(f_{t}). The construction will guarantee that

f_{t}(i) \ ⋃{ f_{t}(j) | j ≠ i & j ∈ dom(f_{t})} ≠ ∅.

Thus at stage t, each f_{t}(i) possesses an element which does not belong to f_{t}(j) for i ≠ j. The purpose of this property is to ensure that f will be a oneto-one enumeration. We will also guarantee that at the end f(i)\f(j) ≠ ∅ for i ≠ j.

6. A special g–set. The construction needs to pick a set g(s_{g}) in the enumeration g which is called a special g–set. If there exist infinitely many stages at which the construction changes its reduction, then the set g(s_{g}) becomes infinite, all sets in f contained in g(s_{g}) are finite, and therefore g is not a one-to-one enumeration of S. On the other hand, if after some stage the construction never changes its reduction and g is a one-to-one enumeration of the family S, then g will be equivalent to f.

7. Special Numbers s_{t}^{f}. The construction uses these numbers so that r_{t}(s_{g}) = s_{t}^{f}. Thus f_{t}(s_{t}^{f}) is the set in f_{t} which, at stage t, corresponds to g(s_{g}). Moreover, if g recovers at stage t (as defined below), then these numbers satisfy the following properties.

1. If the construction does not change its previous reduction at stage t, then s_{t+1}^{f} = s_{t}^{f}.

2. If the construction changes its reduction at stage t, then s_{t+1}^{f} ≠ s_{t}^{f}.

3. If, after some stage, the construction never changes its reduction, recovers infinitely often, and g is a one-to-one enumeration of the family S, then the construction guarantees that the set f(lim_{n→∞}s_{n}^{f}) becomes infinite.

8. Marking with □_{w} and Recovery. If, for a f_{t}–index x, there exists a y ≤ t such that g_{t}(y) ⊂ f_{t}(x) and for all z ≠ x the pair g_{t}(y) is not contained in f_{t}(z), then we say that g_{t}(y) is covered by f_{t}(x), or equivalently, f_{t}(x) covers g_{t}(y). During the construction some f_{t}–indices will be marked with a special symbol □_{w} called a mark. We say that the enumeration g recovers at stage t, or equivalently that stage t is a recovery stage, if for each f_{t}– index x marked with a □_{w}, there exists a unique y such that f_{t}(x) covers g_{t}(y). We use the notion of recovery to show that if g is a one-to-one enumeration of the family S, then g is equivalent to f. The idea is the following. Suppose that g is a one-to-one enumeration of S. By construction, each f_{t}(x) marked with a □_{w} waits to cover a set in g. As soon as g recovers at a stage t_{1} ≥ t and a unique g_{t_{1}}–index y is found such that f_{t}(x) covers g_{t_{1}}(y), the construction defines r_{t_{1}}(x) = y and then attempts to guarantee that g(y) = f(x). If the enumeration does not recover at stage t, then we say that g is in the waiting state. If g is always in the waiting state after t, then, by construction, g will not be a one-to-one enumeration of S.

Now we need a definition for an operation which corresponds to the L– operation in the proof of Theorem 2.1. This operation will be needed to meet requirements D_{e}.

Definition 40 Let X_{k}, …, X_{1} be a sequence of sets. The L–operation applied to this sequence gives, by definition, the sequence

X_{k} ⋃ X_{k−1}, …, X_{1} ⋃ X_{k}.

We also say that the sets X_{k}, …, X_{1} participated in the L–operation.

Now we will describe the construction for satisfying all D_{e} and one R.

Stage 0. Let dom(f_{0}) = D ⋃{a}, where a is a new number not in D. Let p also be a new number. We set f_{0}(a) = {p}. Put a mark □_{w} on a. Let the reduction r_{0} be the empty function. Put g into the waiting state. When we first have a recovery stage we will define s_{g} so that s_{0}^{f} = a.

Stage t + 1: Substage 1: If this is not a recovery stage we go on to substage 2. If it is a recovery stage, we proceed as follows:

Action. Define the reductions r_{t+1}^{f} on the indices marked with a □_{w} as follows: Put r_{t+1}^{f}(x) = y if and only if g_{t+1}(y) is covered by f_{t+1}(x). We now have the following two cases.

Case 1. Suppose that r_{t+1}^{f} extends the previous reduction r_{t}^{f}. In this case, set s_{t+1}^{f} = s_{t}^{f}.

Case 2. Suppose that r_{t+1}^{f} does not extend the previous reduction r_{t+1}^{f}. In this case, the construction changes its reduction. Note that s_{t+1}^{f} ≠ s_{t}^{f}.

Substage 2: Compute F_{e,t+1} for all e ≤ t + 1. Let f_{t+1}(a) = {b} where a, b are new numbers. Find the least e ≤ t + 1 for which F_{e,t+1}(q_{e}) = f_{t}(c_{e}) for some q_{2} ≤ t + 1 such that we have not yet acted for D_{e} and one of the following cases is satisfied (If there is no such e, then go on to the next stage).

1. There does not exist j_{1} such that r_{t+1}(c_{e}) = j_{1}.

2. This is a recovery stage and, for some j_{1}, r_{t+1}(c_{e}) = j_{1}.

Action for D_{e}. Suppose that the first case holds. Let f_{t+1}(c_{e}) = {p_{e}, p′_{e}}, f_{t+1}(u) = {p_{e}, p′′_{e}}} where p′_{e}, p′′_{e}, and u, are new numbers. Note that we have successfully met the potential reduction D_{e}. Also the family S_{t} has been changed to a new family S_{t+1} in such a way that f_{t} can naturally be extended to an enumeration f_{t+1} of the family S_{t+1}.

Suppose that the second case holds. In this case, we have two subcases. Subcase 2.1. There exist distinct numbers a_{1}, a_{2}, a_{3} not in D such that

for some x_{1}, x_{2}, x_{3}, r_{t}(a_{i}) = x_{i}, and none of the numbers a_{i} have previously participated in any L–operation. In this case, consider the sequence

a_{1}, c_{e}, a_{2}, s_{t}^{f}, a_{3}.

and the corresponding finite sequence

f_{t}(a_{1}), f_{t}(c_{e}), f_{t}(a_{2}), f_{t}(s_{t}^{f}), f_{t}(a_{3}).

Perform L–operations on the sequence. Put into each of these changed sets new elements. Thus the family S_{t} has been changed to a new family S_{t+1} in such a way that f_{t} can naturally be extended to an enumeration f_{t+1} of the family S_{t+1}. Put a mark □_{w} on each f_{t+1}–index that participated in the L-operation, on a, on the least number x which has not yet been marked with a □_{w}. Go on to the next stage.

Subcase 2.2. Suppose that the previous subcase does not hold.

In this case, take distinct new elements a_{1}, a_{2}, a_{3}. Set f_{t}(a_{j}) to be {u_{j}}, where u_{j} are new distinct numbers, j = 1, 2, 3. Add these sets to S_{t}. Thus, the family S_{t} has been changed to a new family S_{t+1} in such a way that f_{t} can naturally be extended to an enumeration f_{t+1} of the family S_{t+1}.

Substage 3: If this is a recovery stage, put a mark □_{w} on each new f_{t+1}– index and on the least number x which has not yet been marked with a □_{w}. In any case, we now go on to the next stage.

This concludes the description of the construction.

For each i ∈ ω, define f(i) = ⋃_{t} f_{t}(i). Define the family S by S = {f(i)|i ∈ ω}. We leave to the reader the verification of the correctness of this construction as well as the details of the general construction. □

References

[1] C. J. Ash, and A. Nerode, Intrinsically Recursive Relations, in [8], 26-41.

[2] C. J. Ash, Categoricity in the Hyperarithemetical Degrees, Ann. Pure and Appl. Logic 34 (1987), 1-14.

[3] C. J. Ash and J. Knight, Pairs of Recursive Structures, Ann. Pure and Appl. Logic 46 (1990), 211-234.

[4] C. J. Ash, J. Knight, M. Manasse and T. Slaman, Generic Copies of Countable Structures, Ann. Pure and Appl. Logic 42 (1989) 195-205.

[5] C. J. Ash, P. Cholak and J. Knight, Permitting, Forcing, and Copies of a Given Recursive Relation, to appear.

[6] D. Cenzer and J. Remmel, Polynomial Time versus Recursive Models, Ann. Pure and Appl. Logic 54 (1991), 17-58.

[7] P. Cholak, S. S. Goncharov, B. Khoussainov and R. A. Shore, Computably Categorical Structures and Expansions by Constants, to appear.

[8] J. N. Crossley (ed.), Aspects of Effective Algebra, Proceedings of a Conference at Monash University, 1979, Upside Down A Book, Yarra Glen, Australia, 1981.

[9] Yu. Ershov and S. S. Goncharov (eds.), Logic Notebook, Novosibirsk University, 1986.

[10] Yu. Ershov, S. S. Goncharov, A. Nerode and J. Remmel (eds.), Handbook of Computable Algebra, to appear.

[11] A. Frölich and J. Shepherdson, Effective Procedures in Field Theory, Philos. Trans. Roy. Soc., London, ser. A 248 (1955), 432-487.

[12] S. S. Goncharov, Autostability and Computable Families of Constructivizations, Algebra and Logic 14 (1975), 392-409.

[13] S. S. Goncharov, Autostability of Models and Abelian Groups, Algebra and Logic 19 (1980), 13-27.

[14] S. S. Goncharov, The Problem of the Number Of Non-Self-Equivalent Constructivizations, Algebra and Logic 19 (1980), 411-414.

[15] S. S. Goncharov, Effectively Infinite Classes of Weak Constructivizations of Models, Algebra and Logic 32 (1993), 342-360.

[16] S. S. Goncharov, Limiting Equivalent Constructivizations (Russian), Tr. Inst. Mat. Sib. Akad. Nauk SSSR 2, 1982, 4-12.

[17] S. S. Goncharov and V. D. Dzgoev, Autostability of Models, Algebra and Logic 19 (1980), 28 -38.

[18] S. S. Goncharov and B. Khoussainov, On the Spectrum of Degrees of Decidable Relations, Doklady Mathematics 55 (1997), 55-57.

[19] V. Harizanov, Some Effects of Ash–Nerode and Other Decidability Conditions on Degree Spectra, Ann. Pure and Appl. Logic 55 (1991), 51-65.

[20] V. Harizanov, The Possible Turing Degree of Nonzero Member in Two Element Degree Spectrum, Ann. Pure and Appl. Logic 60 (1993), 1-30.

[21] V. Harizanov, Pure Recursive Model Theory, in Recursive Mathematics, Yu. Ershov, S. Goncharov, A. Nerode, and J. Remmel (eds.), to appear.

[22] G. Hird, Recursive Properties of Relations on Recursive Models, Ph.D. Thesis, Monash University, 1983.

[23] D. Hirschfeldt, On the Degree Spectrum Problem, in preparation.

[24] J. Knight, A Metatheorem for Construction by Finitely Many Workers, Journal of Symbolic Logic 55 (1990), 787-804.

[25] J. Knight, Constructions for Transfinitely Many Workers, Ann. Pure and Appl. Logic 46 (1990), 211-234.

[26] J. Knight, Degrees Coded in Jumps Orderings, Journal of Symbolic Logic 51 (1986), 1034-1042.

[27] B. M. Khoussainov, Spectrum of Algorithmic Dimensions of Homomorphisms of Models, Algebra and Logic ?? (1992), ??.

[28] B. Khoussainov, Recursive Unary Algebras and Trees, Ann. Pure and Appl. Logic 67 (1994), 213-268.

[29] B. Khoussainov and A. Nerode, Automatic Presentations of Structure, in Logic and Computational Complexity, Proceedings of the International Conference on LCC, D. Leivant (ed.), LNCS 960, Springer- Verlag, Berlin, 367-393.

[30] O. V. Kudinov, An Autostable 1-Decidable Model without a Computable Scott Family of ∃-Formulas, Algebra and Logic 35 (1996), 255-260.

[31] A. I. Mal‘cev, Recursive Abelian Groups, Dokl. Akad. Nauk SSSR (Russian) 146 (1962), 1009-1012.

[32] A. I. Mal‘cev A. I., Constructive Algebras, Uspekhi Matem. Nauk. 16 (1961), 3-60, tr. in Russian Math. Surveys 16 (1961), 77-129.

[33] G. Metakides and A. Nerode, Recursion Theory and Algebra, in Algebra and Logic, ed. J. Crossley, Lecture Notes in Mathematics 450, Springer-Verlag, Berlin, 1975, 209-219.

[34] T. Millar, The theory of Recursively Presentable Models, Ph.D. Dissertation, Cornell University, 1976.

[35] T. Millar, Recursive Categoricity and Persistence, Journal of Symbolic Logic 51 (1986), 430-434.

[36] A. Nurtazin, Strong and Weak Constructivizations and Computable Families, Algebra and Logic 13 (1974), 177-184.

[37] M. Rabin, Computable Algebra: General theory and Theory of Computable Fields, Trans. Am. Math. Soc. 95, 1960, 341-360

[38] J. B. Remmel, Recursive Isomorphisms Types of Recursive Boolean Algebras, Journal of Symbolic Logic 46, 1981, 572-593.

[39] J. Remmel, Recursive Boolean Algebras, in Handbook of Boolean Algebras, J. D. Monk (ed.), v.3, North Holland, Amsterdam, 1990, 1097-1066 .

[40] J. B. Remmel and J. N. Crossley, The Work of Anil Nerode: A Retrospective, in Logical Methods, J. N. Crossley, J. B. Remmel, R. A. Shore and M. E. Sweedler (eds.), Birkhäuser, Boston, 1993, 1-91.

[41] H. Rogers Jr., Theory of Recursive Function and Effective Computability, New York, 1967.

[42] G. Sacks, Saturated Model Theory, W. A. Benjamin, Reading, Mass. 1972.

[43] G. Sacks, Higher Recursion Theory, Springer-Verlag, Berlin, 1990.

[44] V. L. Selivanov, Numerations of Families of General Recursive Functions, Algebra and Logic 15 (1976), 205-226.