Computably Categorical Structures and Expansions by Constants

Peter Cholak^{∗} University of Notre Dame, Notre Dame, IN, 46556

Sergey Goncharov^{†} Novosibirsk University, Novosibirsk, Russia.

Bakhadyr Khoussainov^{‡} Cornell University, Ithaca NY 14853 USA

University of Aukland, Aukland, New Zealand Richard A. Shore^{§} Cornell University, Ithaca NY 14853 USA

1 Introduction

Effective model theory is the subject that analyzes the typical notions and results of model theory to determine their effective content and counterparts. The subject has been developed both in the former Soviet Union and in the west with various names (recursive model theory, constructive model theory, etc.) and divergent terminology. (We use “effective model theory” as the

∗Partially supported by a Mathematical Sciences Postdoctoral Research Fellowship and ARO through MSI, Cornell University, DALL03-91-C0027

†Partially supported by ISF, NQ6000 and NQ6300, and by ARO through MSI, Cornell University, DAAL03-91-C0027.

‡Partially supported by ARO through MSI, Cornell University, DAAL03-91-C0027. §Partially supported by NSF Grant DMS-9204308, DMS-9503503 and ARO through

MSI, Cornell University, DAAL-03-C-0027.

most general and descriptive designation. Harizanov [6] is an excellent introduction to the subject as is Millar [14].) The basic subjects of model theory include languages, structures, theories, models and various types of maps between these objects. There are many ways to introduce considerations of effectiveness into the area. The two most prominent derive from starting, on the one hand, with the notion of a theory and its models or, on the other, with just structures.

If one begins with theories, then a natural version of effectiveness is to consider decidable theories (i.e., ones with a decidable (equivalently, computable or recursive) set of theorems). When one moves to models and wants them to be effective, one might start with the requirement that the model A (of any theory) have a decidable theory (i.e., T h(A), the set of sentences true in A, is decidable). Typically, however, one wants to be able to talk about the elements of the model as well as its theory in the given language. Thus one naturally considers the model as a structure for the language expanded by adding a constant a_{i} for each element a_{i} of A. Of course, one requires that the mapping from the constants to the corresponding elements of A be effective (computable). We are thus lead to the following basic definition:

Definition 1.1 A structure or model A is decidable if there is a computable enumeration a_{i} of A, the domain of A, such that T h(A, a_{i}) is decidable. (Of course, a_{i} is interpreted as a_{i} for each i ∈ ω.)

A typical basic result about decidable models is then the effective version of the completeness theorem:

Theorem 1.2 Every complete decidable theory has a decidable model.

The proof consists of noting that the standard Henkin construction can be done effectively.

A deeper result is that of Harrington [8] and Khissamiev [9]

Theorem 1.3 ([8],[9]) If T is a decidable ℵ_{1}-categorical theory, then every countable model of T is isomorphic to a decidable model of T.

There are many other results on decidable models concerning prime, homogeneous and saturated models of decidable theories. We refer again to [6] and [14] for surveys and extensive bibliographies.

If one begins simply with languages and structures, then one is essentially in the realm of general effective mathematics. The effective versions of various branches of mathematics have been extensively developed beginning with Fröhlich and Shepherdson [3], Malcev [12], Rabin [15], Nerode and his collaborators (see [16]) in algebra and Grzegorczyk [5], Lacombe [11] and others in analysis. In line with these investigations, we begin with a computable language L. An effective structure for the language should have a computable domain and we should be able to calculate the relevant functions and relations on this domain:

Definition 1.4 A structure A for a language L is computable if its domain A is a computable subset of ω and its functions and relations are uniformly computable, i.e., there is a computable enumeration a_{i} of A such that the atomic diagram of (A, a_{i}) is computable.

Obviously, the requirements of computability are significantly weaker than those for decidability. Indeed, it usually seems to be the case that far less is provable about computable than decidable models. For example, if one views a theory T simply as a set of sentences (rather than the associated set of theorems), then a computable theory need not have a computable model (e.g., there is no computable nonstandard model of Peano Arithmetic). Nonetheless, the definition captures what one normally means in mathematical discourse by an effective structure or presentation. Again, this notion has been extensively investigated in the settings of particular mathematical subjects as well as in general model theoretic terms. It is this notion of effective structure with which we shall be concerned in this paper.

Just as one insists on computable structures in effective model theory, one is primarily interested in computable maps between the structures whether they be homomorphism, monomorphism or elementary embeddings. Thus while classical mathematics and model theory identify isomorphic structures, effective model theory is concerned with computable isomorphism. A fundamental concept is therefore that of computable isomorphism type.

Definition 1.5 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 structure A is the number of computable isomorphism types of computable structures (classically) isomorphic to A.

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

Theorem 1.6 [4] For each n ∈ ω ∪{ω} there is a computable structure with dimension n.

We shall primarily be concerned with the effect of expanding a structure by naming (finitely many) constants on its dimension. Of course, this cannot decrease the dimension but to what extent it can increase it has been an open problem that we deal with in this paper. The basic model theoretic notion with which we begin is (countable) categoricity. A theory T is (countably) categorical (in classical model theory) if all (countable) models of T are isomorphic. A (countable) structure A is (countably) categorical if its theory T h(A) is (countably) categorical. The analogous concept for effective model theory deals only with computable structures and isomorphisms:

Definition 1.7 A computable structure A is computably categorical if every computable structure isomorphic to A is computably isomorphic to A. (Equivalently, the dimension of A is 1.)

Example 1.8 (Q, ≤), the rationals with their usual linear order, is a computably categorical structure: The standard back and forth argument showing that the theory of dense linear orderings without endpoints is countably categorical is effective and so produces computable isomorphisms between any two such orderings. Similarly, each computable atomless Boolean algebra is computably categorical.

Classically, it is an easy consequence of the Ryll-Nardzewski Theorem that if the theory of an arbitrary structure A is countably categorical then so is the theory of any expansion of A by finitely many constants. It is the analogous situation in effective model theory that we wish to consider. Millar [13] proved that a small amount of decidability is enough to guarantee that categoricity is preserved under such expansions:

Theorem 1.9 [13] If a structure A is computably categorical and its existential theory is decidable (i.e., the set of existential sentences (with constants for each element of A) true in A is computable), then the expansion of A by finitely many constants is also computably categorical.

Without this partial decidability assumption the problem has remained open. It is presented as the Ash–Goncharov problem in [2]:

Question 1.10 [2] Is the expansion of every computably categorical structure by finitely many constants computably categorical?

We solve this problem negatively, indeed, we show that the dimension of a structure can be increased from 1 (computable categoricity) to k ∈ ω by the addition of even a single constant naming any element of the structure. Thus our main theorem is as following:

Theorem 4.4 For each k ∈ ω there is a computably categorical structure A such that the expansion of A gotten by adding on a constant naming any element of A has dimension k.

We would like to add that this theorem does not answer the case when k = ω. We do not know whether there exists a computably categorical structure whose expansion by a finite number of constants has ω many computable isomorphism types.

The structures required to establish the theorem are constructed by coding certain (uniformly) computably enumerable families of k-tuples of sets. We now present the basic notions about such families needed when k = 2. The model theoretic coding of the appropriate families is presented in §2. We give the constructions of the required family itself in §3. Finally, in §4 we explain how to generalize the notions and constructions to establish the full result for all k ∈ ω.

Definition 1.11 We use r and l as the right and left projections from pairs, i.e., l((A, B)) = A and r((A, B)) = B.

Definition 1.12 Let S be a family of pairs (A, B) of nonempty sets. S is symmetric if (A, B) ∈ S implies that (B, A) ∈ S. S is a computably enumerable family if there is a mapping f : ω → S such that {(i, x, y)|x ∈ lf(i), y ∈ rf(i)} is computably enumerable. We then call f a (computable) enumeration of S. If f is one-to-one we say it is a one-to-one enumeration of S. We also say that i is an f index for f(i) = (A_{i}, B_{i}).

We wish to consider a preordering on the computable enumerations of a family S that naturally induces an equivalence relation that corresponds to computable isomorphism:

Definition 1.13 Let f and g be computable enumerations of a family S. We say that f is reducible to g, f ≤ g, if there is a computable Φ such that f = gΦ. In this case, we say that f is reducible to g via Φ. If f ≤ g and g ≤ f then we say that f and g are equivalent and denote this relation by f ∼ g.

Note that if f is a one-to-one enumeration of S and g ≤ f then Φ must be 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 model required for our theorem. Informally, computable categoricity corresponds to there being a single such equivalence class and dimension corresponds to the number of such classes.

Now if f is a one-to-one computable enumeration of a symmetric family S of pairs of sets then there is one other natural computable enumeration f̃ of S: If f(i) = (A_{i}, B_{i}) then f̃(i) = (B_{i}, A_{i}). Thus we can phrase the required notion of dimension in the case of interest as follows:

Definition 1.14 If f is a one-to-one computable enumeration of a symmetric family S of pairs of sets, we say that S has dimension 2 if f and f̃ are not equivalent and every computable one-to-one enumeration of S is equivalent to either f or f̃.

The crucial ingredient in the construction of the structures we need is precisely such a family.

Theorem 3.1 There exists a computably enumerable symmetric family of dimension 2.

§3 is devoted to a proof of this theorem. In §2 we show how to use such a family to build the desired structure to prove the case k = 2 of our main theorem. We mention that in [4] and [7] Goncharov and Harizanov used similar coding ideas.

2 Structures of Dimension 2

In this section we show how to use a family of dimension 2 (as provided by Theorem 3.1) to prove the main theorem for k = 2.

Theorem 2.1 There exists a computably categorical model A such that for each a ∈ A the expanded model (A, a) has dimension 2.

Proof. Let S be a symmetric family of dimension 2 and let f be a oneto-one computable enumeration of S. Based on the enumeration f, we will construct a computable structure A_{f} = (ω ⋃{u_{f}, v_{f}}, P_{f}), where u_{f} and v_{f} are symbols not belonging to ω and P_{f} is a computable binary predicate on ω ⋃{u_{f}, v_{f}}. When defining the predicate P_{f} in our structure, we abuse notation and write P_{f}(a) = b instead of P_{f}(a, b).

Consider uniformly computably enumerable, possibly finite, sequences

a_{i,0}, a_{i,1}, a_{i,2}, … and b_{i,0}, b_{i,1}, b_{i,2}, …

without repetitions such that for each i ∈ ω

lf(i) = {a_{i,0}, a_{i,1}, a_{i,2}, …} and rf(i) = {b_{i,0}, b_{i,1}, b_{i,2}, …}.

For each i ∈ ω, we can consider the computable structure G_{i}^{f} on a computable subset of ω plus two additional symbols u_{f} and v_{f} with one binary relation P_{i}^{f} determined by the following procedure: We begin by setting

P_{i}^{f}(0) = u_{f}, P_{i}^{f}(1) = v_{f}, P_{i}^{f}(0) = 1, P_{i}^{f}(1) = 0,

and for all m ∈ ω

P_{i}^{f}(4(m + 1)) = 4m, P_{i}^{f}(4(m + 1) + 1) = 4m + 1,
P_{i}^{f}(4m + 2) = 4m + 2, P_{i}^{f}(4m + 3) = 4m + 3.

When some element a_{i,m} is enumerated at stage s we set P_{i}^{f}(4s + 2) = 4(a_{i,m}+1) and when b_{i,m} is enumerated at s we set P_{i}^{f}(4s+3) = 4(b_{i,m}+1)+1. (We enumerate at most one number at each stage.) The domain of G_{i}^{f} is the domain of the relation P_{i}^{f} and is clearly computable.

A picture of a fragment of this structure is in Figure 1 in the case when 1 is enumerated in lf(i) at stage 1 and 3 at stage 4, while 2 is enumerated in

[figure: 20; 16; 12; 8; 4; 0; u_{f}; 18; 6; 17; 13; 9; 5; 1; v_{f}; 23] Figure 1:

rf(i) at stage 5. In this picture a → b means that P_{i}^{f}(a) = b, or equivalently P_{i}^{f}(a, b) holds. For example, P_{i}^{f}(6) = 8 as well as P_{i}^{f}(18) = 16.

The structure G_{i}^{f} is computable and satisfies the following properties:

1. For every number t, t belongs to lf(i) if and only if there exist pairwise distinct elements y, z, x_{0}, x_{1}, …, x_{t+1} of the structure G_{i}^{f} such that P_{i}^{f}(y) = x_{0} & P_{i}^{f}(z) = x_{0} and the formula

P_{i}^{f}(x_{0}) = x_{1} & … &P_{i}^{f}(x_{t}) = x_{t+1} & P_{i}^{f}(x_{t+1}) ≠ x_{t} & P_{i}^{f}(x_{t+1}) = u_{f}

holds in the structure G_{i}^{f}.

2. For every number t, t belongs to rf(i) if and only if there exist pairwise distinct elements y, z, x_{0}, x_{1}, …, x_{t+1} of the structure G_{i}^{f} such that P_{i}^{f}(y) = x_{0} & P_{i}^{f}(z) = x_{0} and the formula

P_{i}^{f}(x_{0}) = x_{1} & … &P_{i}^{f}(x_{t}) = x_{t+1} & P_{i}^{f}(x_{t+1}) ≠ x_{t} & P_{i}^{f}(x_{t+1}) = v_{f}

holds in the structure G_{i}^{f}.

Informally, the structure G_{i}^{f} codes the pair f(i). By the uniformity in the construction of G_{i}^{f} and the computability of f, we can conclude (by relabeling the computable sets involved as necessary) that there exists a computable sequence

A_{0}^{f} = (A_{0}^{f}, P_{0}), A_{1}^{f} = (A_{1}^{f}, P_{1}), A_{2}^{f} = (A_{2}^{f}, P_{2}), …

of computable structures such that:

1. For each i the structure A_{i}^{f} is isomorphic to the structure G_{i}^{f},

2. For all i ≠ j, A_{i}^{f} ⋂ A_{j}^{f} = {u_{f}, v_{f}},

3. ω ⋃{u_{f}, v_{f}} = ⋃_{i} A_{i}^{f},

4. The relation P_{f} = ⋃_{i} P_{i} is computable,

5. The structures A_{i}^{f} and A_{j}^{f} are isomorphic if and only if ĩ = j or i = j.

Consider the computable structure

A_{f} = (ω ⋃{u_{f}, v_{f}}, P_{f}).

The next lemma shows that the structure A_{f} provides the example needed to prove Theorem 2.1.

Lemma 2.2 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. There exists only one nontrivial automorphism α of the structure A_{f} and α(u_{f}) = v_{f}.

3. The expanded structures (A_{f}, u_{f}) and (A_{f}, v_{f}) are isomorphic but not computably isomorphic.

4. The dimension of the expanded structure (A_{f}, u_{f}) is 2.

5. The structure A_{f} is computably categorical.

Proof. Let g be a one-to-one computable enumeration of S. Then for each i there exists exactly one j such that g(i) = f(j). Therefore, the structures G_{i}^{g} and G_{j}^{f} are isomorphic. It follows that the structures A_{f} and A_{g} are also isomorphic. The second part of the lemma follows from the construction of A_{f} and the fact that S is a symmetric family. To prove the third part notice that the structures (A_{f}, u_{f}) and (A_{f}, v_{f}) are isomorphic by Part 2. If these structures were computably isomorphic, then the enumerations f and f̃ would be equivalent. This would be a contradiction. To prove the fourth part, suppose that (B, b) is a computable presentation of (A_{f}, u_{f}). Having the structure (B, b), one can effectively construct a one-to-one enumeration g such that (B, b) and (A_{g}, u_{g}) are computably isomorphic. Since the dimension of S is two, the enumeration g is equivalent to either f or f̃. If g is equivalent to f, then (A_{f}, u_{f}) is computably isomorphic to (A_{g}, u_{g}). Otherwise (A_{g}, u_{g}) is computably isomorphic to (A_{f}, v_{f}). By Part 3, the dimension of (A_{f}, u_{f}) is 2. To prove the last part of the lemma suppose that B is a computable presentation of A_{f}. Let b be such that (B, b) is isomorphic to (A_{f}, u_{f}). By the previous part, the structure (B, b) is either computably isomorphic to (A_{f}, u_{f}) or to (A_{f}, v_{f}). Hence B is computably isomorphic to A_{f}. □

To complete the proof of Theorem 2.1 from Lemma 2.2, take any a ∈ A_{f}. Consider the structure (A_{f}, a). Let α be the nontrivial automorphism of A_{f}. The expanded structure (A_{f}, a) is isomorphic to the structure (A_{f}, α(a)). Repeating the proof of the lemma with respect to the expanded structure (A_{f}, a), we see that the dimension of (A_{f}, a) is 2. □

3 Symmetric Families of Dimension 2

Our goal in this section is to prove the following:

Theorem 3.1 There exists a computably enumerable symmetric family of dimension 2.

Let Φ_{j}, j ∈ ω, be a standard enumeration of all partial computable functions. Let g_{j}, j ∈ ω, be a standard enumeration of all computable enumerations of families of pairs of computably enumerable sets. To construct the desired one-to-one computable enumeration f of a symmetric family S, we need to satisfy the following requirements:

Q_{j} : f is not reducible to f̃ via Φ_{e},

and

R_{j} : (g_{j} ∼ f) ⋁(g_{j} ∼ f̃) ⋁ g_{j} is not a one-to-one enumeration of S.

The U-operation defined below is important in our construction. An ordered finite sequence

X_{k}, …, X_{1}, Y_{1}, …, Y_{k}

of pairs of sets is symmetric if X̃_{i} = Y_{i} for each i. A pair (A, B) is selfsymetric if A = B.

Definition 3.2 Let X_{k}, …, X_{1}, Y_{1}, …, Y_{k} be a symmetric sequence of pairs of sets. The U-operation applied to this sequence gives the sequence

Z_{k}, …, Z_{1}, T_{1}, …, T_{k}

where

Z_{k} = X_{k} ⋃ X_{k−1}, …, Z_{1} = X_{1} ⋃ Y_{1},
T_{1} = Y_{1} ⋃ Y_{2}, …, T_{k−1} = Y_{k−1} ⋃ Y_{k}, T_{k} = X_{k} ⋃ Y_{k}.

We also say that the pairs of sets X_{k}, …, X_{1}, Y_{1}, …, Y_{k} participated in the U-operation. (The union operation on pairs is defined componentwise: (A_{1}, B_{1}) ⋃(A_{2}, B_{2}) = (A_{1} ∪ A_{2}, B_{1} ∪ B_{2}). )

Note that if, in the above definition, X_{i} = (A_{i}, B_{i}), then Y_{i} = (B_{i}, A_{i}) and so, for example, Z_{k} = (A_{k} ∪ A_{k−1}, B_{k} ∪ B_{k−1}), Z_{2} = (A_{2} ∪ A_{1}, B_{2} ∪ B_{1}), Z_{1} = (A_{1}∪B_{1}, B_{1}∪A_{1}), T_{1} = (B_{1}∪B_{2}, A_{1}∪A_{2}), T_{k−1} = (B_{k−1}∪B_{k}, A_{k−1}, A_{k}) and T_{k} = (A_{k} ∪ B_{k}, B_{k} ∪ A_{k}). The following lemma describes the main properties of this operation. The proof of the lemma follows easily from the definitions.

Lemma 3.3 Let X_{k}, …, X_{1}, Y_{1}, …, Y_{k} be a symmetric sequence of pairs of sets. The sequence Z_{k}, …, Z_{1}, T_{1}, …, T_{k} obtained via the U-operation has the following properties:

1. The pairs Z_{1} and T_{k} are selfsymmetric.

2. For each i, where 1 ≤ i < k, T_{i} is symmetric to Z_{i+1}. □

Before we present a general construction, we would like to show how to satisfy a single R_{j} requirement R. Remarks in double brackets [[such as this one]] are explanatory and not part of the formal construction. Parameters indexed by the stage number t, such as a_{1,t},that are not explicitly redefined at stage t + 1 remain the same.

How to satisfy one R and all Q_{j}. We set g = g_{j}. For t, n ∈ ω and n ≤ t, let g_{t}(n) be the pair of finite sets whose elements have been enumerated by stage t in a fixed approximation to g(n) (which is a pair of computably enumerable sets).

Let χ ∈ {f, f̃}. Our construction proceeds by stages. We use the following notions and terminology in which the subscript t indicates the stage number.

1. Enumerations f_{t} and f̃_{t}. These are approximations to the enumerations f and f̃ that the construction is building. That is, for each i ∈ ω, we will have

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

As the enumeration f̃ is uniquely determined by f, we will usually only specify f. Warning: For notational convenience, we will define f(i) only for some computable set of i’ s and make sure that f(i) ≠ f(j) for i ≠ j in the domain of f. Correspondingly, we construct reductions defined on this domain. Of course, formally we then could relabel the domain so as to make it all of ω to make f a one-to-one enumeration (on all of ω) but we omit this detail in our constructions and proofs.

2. The Family S_{t}. The functions f_{t} and f̃_{t} enumerate the same symmetric family denoted by S_{t}.

3. Diagonalization Witnesses. To each partial computable function Φ_{j}, we assign pairwise distinct witness numbers c_{j}, d_{j}, x_{j}, y_{j} and corresponding distinct finite sets C_{j}, D_{j}, X_{j} and Y_{j}, called witnesses, such that D = {c_{j}, d_{j}, x_{j}, y_{j}|j ∈ ω} is a coinfinite computable set and we set f_{0}(c_{j}) = (C_{j}, D_{j}), f_{0}(d_{j}) = (D_{j}, C_{j}), f_{0}(x_{j}) = (X_{j}, Y_{j}), f_{0}(y_{j}) = (Y_{j}, X_{j}). One of the goals of the construction is to diagonalize against the potential reduction Φ_{j} at c_{j}.

4. Potential Reduction Functions r_{t}^{f}, rf̃ ; t. Each r_{t}^{χ} (for χ ∈ {f, f̃}) is a function which potentially reduces χ_{t} to g_{t} at stage t. In the construction we call the functions r_{t}^{f}, rf̃ ; t (potential) reduction functions. At each stage one of these (potential) reductions will be the designated (potential) reduction for the construction. The function r_{t}^{χ} may extend the previous designated reduction r_{t−1}^{χ}. If r_{t}^{χ} does not extend the previous designated reduction, then we say that the construction changes its (designated) reduction.

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

lχ_{t}(i) \ ⋃{ lχ_{t}(j) | j ≠ i & j ∈ dom(χ_{t})} ≠ ∅

and

rχ_{t}(i) \ ⋃{ rχ_{t}(j) | j ≠ i & j ∈ dom(χ_{t})} ≠ ∅

Thus at stage t, each coordinate of every pair in f_{t} possesses an element which does not belong to any set in the same coordinate of any other pair in the enumeration f_{t}. Moreover, the same will be true of the final enumerations χ. The purpose of this property is to ensure that f will be a one-to-one enumeration.

6. A Special g–Pair. The construction needs to pick a pair g(s_{g}) in the enumeration g which is called a special g–pair. If there exist infinitely many stages at which the construction changes its reduction, then the pair g(s_{g}) becomes infinite, all pairs 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 either f or f̃.

7. Special Numbers s_{t}^{f}, s̃_{t}^{f}, sf̃ ; t, s̃f̃ ; t. The construction uses these numbers so that

s_{t}^{f} = s̃f̃ ; t, sf̃ ; t = s̃_{t}^{f}, r_{t}^{f}(s_{t}^{f}) = s_{g}, r_{t}^{f}(s̃_{t}^{f}) = s̃_{g}, rf̃ ; t(sf̃ ; t) = s_{g}, rf̃ ; t(s̃f̃ ; t) = s̃_{g}.

Thus f_{t}(s_{t}^{f}) and f̃_{t}(sf̃ ; t) are the pairs of sets in f_{t} and f̃_{t}, respectively, which, at stage t, correspond to g(s_{g}). Therefore f_{t}(s̃_{t}^{f}) and f̃_{t}(s̃f̃ ; t) are the pairs of sets in f_{t} and f̃_{t} respectively which, at stage t, correspond 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 previously designated reduction from χ to χ̃ at stage t, then s_{t+1}^{χ} = s_{t}^{χ} and, if s_{t}^{χ} participated in a U-operation at the last recovery stage, s̃_{t+1}^{χ} ≠ s̃_{t}^{χ}.

2. If the construction changes its reduction from χ to χ̃ at stage t, then s_{t}^{χ} participated in a U-operation at the last recovery stage, s_{t+1}^{χ} ≠ s_{t}^{χ}

and s̃_{t+1}^{χ} = sχ̃ ; t+1 = s̃_{t}^{χ}.

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 pair χ(lim_{n→∞}s_{n}^{χ}) is infinite and selfsymmetric.

8. Marking with □_{w} and Recovery. If, for a χ_{t}–index x, there exists a y ≤ t such that g_{t}(y) ⊂ χ_{t}(x) and, for all z ≠ x, the pair g_{t}(y) is not contained in χ_{t}(z), then we say that g_{t}(y) is covered by χ_{t}(x), or equivalently, χ_{t}(x) covers g_{t}(y). During the construction some χ_{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 χ_{t}–index x marked with a □_{w}, there exists a unique y such that χ_{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 either f or f̃. The idea is the following. Suppose that g is a one-to-one enumeration of S. By construction, each pair f_{t}(x) marked with a □_{w} waits to cover a pair 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 χ_{t}(x) covers g_{t_{1}}(y), the construction defines r_{t_{1}}^{χ}(x) = y and then attempts to guarantee that g(y) = χ(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 will describe the construction for satisfying all Q_{j} and one R. Construction:

Stage 0. Let dom(f_{0}) = D ⋃{s, s̃, a_{1,0}, b_{1,0}, a_{2,0}, b_{2,0}}, where s, s̃, a_{1,0}, b_{1,0}, a_{2,0}, b_{2,0} are new numbers not in D (where D is defined in (3) above). Let p_{i}, q_{i} for 0 ≤ i ≤ 2 also be new numbers. We set f_{0}(s) = ({p_{0}}, {q_{0}}) and f_{0}(a_{i,0}) = ({p_{i}}, {q_{i}}) for i = 1, 2 and let s̃, b_{1,0}, b_{2,0} be the indices of the corresponding symmetric pairs. Put a mark □_{w} on each of these six numbers. Let the reductions r_{0}^{f} and rf̃ ; 0 be empty and declare r^{f} to be the construction’s designated reduction. Put g into the waiting state. When we first have a recovery stage we will define s_{g} so that r^{f}(s) = s_{g} and rf̃(s̃) = s_{g} and so have s^{f} = s and sf̃ = s̃. [[s_{g} will never change.]]

Stage t + 1: Define the reductions r_{t+1}^{f} and rf̃ ; t+1 on the indices marked with a □_{w} as follows: Put r_{t+1}^{f}(x) = y if and only if g_{t}(y) is covered by f_{t}(x) and not by f_{t}(z) for any z ≠ x. Similarly, put rf̃ ; t+1(x) = y if and only if g_{t}(y) is covered by f̃_{t}(x) and not by f̃_{t}(z) for any z ≠ x. If this is not a recovery stage, i.e., r_{t+1}^{f} is not defined for some x marked with a □_{w}, we see if there is a j such that c_{j}, d_{j}, x_{j} and y_{j} are not in the domain of r_{t+1}^{f}, Φ_{j,t+1}(c_{j}) = d_{j} and we have not yet acted for Q_{j}. If there is no such j, go on to stage t + 2. If there is one, let j be the least such. Act to satisfy Q_{j} by performing a U-operation on the pairs f_{t}(x_{j}), f_{t}(c_{j}), f_{t}(d_{j}), f_{t}(y_{j}) to define f_{t+1}. Now go on to stage t + 2.

If this is a recovery stage, we have two cases:

Case 1. Suppose that r_{t+1}^{χ} extends the previous designated reduction r_{t}^{χ}. In this case, set s_{t+1}^{χ} = s_{t}^{χ}. This defines the number s̃_{t+1}^{χ} with respect to the enumeration χ_{t+1}. [[Note that if we performed a U-operation at the last recovery stage, s̃_{t+1}^{χ} ≠ s̃_{t}^{χ} by Claim 2 below.]]

Case 2. Suppose that r_{t+1}^{χ} does not extend the previous designated reduction r_{t}^{χ}. In this case the construction changes its designated reduction to rχ̃ ; t+1. Set sχ̃ ; t+1 = s̃_{t}^{χ}. This defines the number s̃χ̃ ; t+1 = s_{t+1}^{χ} with respect to the enumeration χ̃_{t+1}. [[Note that s_{t+1}^{χ} ≠ s_{t}^{χ}.]]

In either case, we see if there is a j such that c_{j}, d_{j}, x_{j} and y_{j} are in the domain of r_{t+1}^{f}, Φ_{j,t+1}(c_{j}) = d_{j} and we have not yet acted for Q_{j}. If so let j be the least such number and act for Q_{j} by performing a U-operation on the following pairs:

f_{t}(b_{1,t}), f_{t}(s_{t+1}^{χ}), f_{t}(b_{2,t}), f_{t}(x_{j}), f_{t}(c_{j}),

f_{t}(d_{j}), f_{t}(y_{j}), f_{t}(a_{2,t}), f_{t}(sχ̃ ; t+1), f_{t}(a_{1,t}).

[[Note that all these indices are marked with □_{w} and so are in the domain of r^{χ}.]]

Now extend l(f_{t}(s_{t+1}^{χ})) by adding on the least number in r(f_{t}(s_{t+1}^{χ})) which does not belong to l(f_{t}(s_{t+1}^{χ})) and vice versa. Of course, the dual actions are performed on f_{t}(s̃_{t+1}^{χ}). Also add new numbers to both the left and right sides of these pairs so as to prevent them from being selfsymmetric. If necessary, add new numbers to the pairs that participated in the U-operation so as to guarantee (5) above while preserving the symmetries existing after the operation was performed. Next, take new numbers a_{1,t+1}, b_{1,t+1}, a_{2,t+1}, b_{2,t+1} to which we assign symmetric pairs of new numbers in the enumeration f_{t+1}.

This finishes the definition of f_{t+1}. Finally, put marks □_{w} on the new numbers a_{1,t+1}, b_{1,t+1}, a_{2,t+1}, b_{2,t+1}.

Whether we found such a j and performed a U-operation or not, we now put a mark □_{w} on the least number not having one and go on to stage t + 2. This concludes the description of the construction. Verifications:

For each i ∈ ω, define f(i) = ⋃_{t} f_{t}(i). Define the family S by

S = {f(i)|i ∈ ω}.

Now we verify the following claims about the construction. Claim 1. For all t ∈ ω and i ∈ dom(f_{t})

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

and

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

Proof of Claim 1. This is clear from the construction by induction. Claim 2. The construction meets all the requirements Q_{j}. Moreover, if at some stage the enumeration g enters the waiting state and never recovers, then g is not a one-to-one enumeration of S. Proof of Claim 2. Suppose first that at a stage t′, the enumeration g enters the waiting state and never recovers. From stage t′ on no new marks □_{w} are placed on any numbers and the pairs so marked never change. There is now clearly a j_{0} such that for every j > j_{0} for which Φ_{j}(c_{j}) = d_{j} there is a stage t′ such that at all stages t > t′ the construction satisfies the conditions considered at nonrecovery stages via j. Therefore f and f̃ are guaranteed not to be equivalent via Φ_{j} by our action at stage t. (f(c) has become selfsymmetric and remains so as it is never used in a U-operation again and so never changes. Thus f(c) = f̃(c) and so any Φ reducing f to f̃ (or vice versa) would have to have Φ(c) = c.) Of course, if Φ_{j}(c_{j}) ≠ d_{j} then Q_{j} is met automatically and meeting requirements Q_{j} for j > j_{0} is equivalent to meeting every Q_{j}. Finally, if g were a one-to-one enumeration of S then each of the finitely many marked pairs would be finite and would eventually cover some unique pair in the enumeration g by Claim 1, and so there would be a recovery stage for the desired contradiction.

Next, suppose that g recovers at infinitely many stages. Let j be the smallest number for which Q_{j} is not met. Let t_{1} be such that for all j′ < j, all action for the requirements Q_{j′} is finished before stage t_{1}. (Clearly we act at most once for each Q_{j}.) Then there exists a stage t + 1 at which Φ_{j,t+1}(c_{j}) = d_{j} and all the indices required to be in the domain of r^{χ} are marked and in the domain as we mark the least unmarked number at each recovery stage. It follows that at stage t + 1, the construction must act for and so meet requirement Q_{j}. This is again a contradiction.□ Claim 3. Suppose that at stage t + 1 the designated reduction is r_{t+1}^{χ} and a U-operation is applied to the pairs

f_{t}(b_{1,t}), f_{t}(s_{t+1}^{χ}), f_{t}(b_{2,t}), f_{t}(x_{j}), f_{t}(c_{j}),

f_{t}(d_{j}), f_{t}(y_{j}), f_{t}(a_{2,t}), f_{t}(sχ̃ ; t+1), f_{t}(a_{1,t}).

and that t′ is the next recovery stage after t + 1. There are then two possibilities at t′:

1. r_{t′}^{χ}(s_{t_{+1}}^{χ}) = r_{t+1}^{χ}(s_{t+1}^{χ}) = s_{g}. In this case, r_{t′}^{χ} remains the designated reduction and extends r_{t+1}^{χ}, s_{t′}^{χ} = s_{t+1}^{χ} which is already marked with □_{w} by induction and s̃_{t′}^{χ} = a_{2,t} which was marked with □_{w} at t + 1.

2. r_{t′}^{χ}(s_{t_{+1}}^{χ}) ≠ r_{t+1}^{χ}(s_{t+1}^{χ}). In this case, the construction changes its designated reduction from χ to χ̃; sχ̃ ; t′ = sχ̃ ; t+1 = s̃_{t+1}^{χ} which is already marked with □_{w} by induction and s̃χ̃ ; t′ = s_{t+1}^{χ} = b_{1,t} which was marked with □_{w}

at t + 1. Also rχ̃ ; t′(sχ̃ ; t′) = s_{g}.

Proof of Claim 3.

The only markings and changes that occur to marked pairs between t + 1 and t′ occur at t + 1. It is clear that the only possible pairs that can cover g_{t′}(s_{g}) at t′ are f_{t+1}(s_{t+1}^{χ}) or f_{t+1}(b_{1,t}) . If it is the second, then r_{t+1}^{χ}(s_{t+1}^{χ}) = s_{g} but r_{t′}^{χ}(b_{1,t}) = s_{g} and so we are in the second case of the claim as r_{t′}^{χ} is oneto-one. Thus we change the designated reduction to χ̃ by construction. As r_{t′}^{χ}(b_{1,t}) = s_{g}, rχ̃ ; t′(sχ̃ ; t+1) = s_{g} by symmetry and Lemma 3.3 and so sχ̃ ; t′ = sχ̃ ; t+1 as required.

If, on the other hand, it is f_{t+1}(s_{t+1}^{χ}) that covers g_{t′}(s_{g}) at t′, then we claim that r_{t′}^{χ} extends r_{t+1}^{χ}. Now the only marked pairs that have changed are the ones participating in the U-operation so we need only argue that r_{t′}^{χ} remains the same on these pairs. It is clear form the definition of the U-operation that the only possible values for r_{t′}^{χ} at each number z in the

sequence b_{1,t}, s_{t+1}^{χ}, b_{2,t}, x_{j}, c_{j}, d_{j}, y_{j}, a_{2,t}, sχ̃ ; t+1, a_{1,t} is either r_{t+1}^{χ}(z) or r_{t+1}^{χ}(w)

where w is the number immediately to the left of z in the sequence (with the understanding that a_{1,t} is immediately to the left of b_{1,t}). As r_{t′}^{χ} must be one-to-one, if r_{t′}^{χ}(s_{t_{+1}}^{χ}) = r_{t+1}^{χ}(s_{t+1}^{χ}) as we are assuming, then r_{t′}^{χ}(z) = r_{t+1}^{χ}(z) for every z in the sequence as required.

The assertions about which numbers are marked follow immediately from the construction. □ Claim 4. Suppose that g recovers at infinitely many stages. If the construction never changes its potential reduction r_{t}^{χ} for all t > t′, then the following hold:

1. For each t > t′, s_{t}^{χ} = s_{t+1}^{χ}. Therefore lim_{t→∞}s_{t}^{χ} exists.

2. Let t′ < t_{1} < t_{2} < … be the sequence of recovery stages immediately following the ones at which a U-operation is performed. Then the elements of the sequence s̃_{t_{1}}^{χ}, s̃_{t_{2}}^{χ}, … are pairwise distinct.

3. If there are infinitely many recovery stages at which we perform Uoperations, the pair χ(s_{t}^{χ}) is selfsymmetric and is infinite.

4. For each x ≠ s_{t}^{χ}, the pair χ(x) is finite.

5. For all i ∈ dom(f), lf(i) \ ⋃{ lf(j) | j ≠ i & j ∈ dom(f)} ≠ ∅ and rf(i) \ ⋃{ rf(j) | j ≠ i & j ∈ dom(f)} ≠ ∅ and so, in particular, f is a one-to-one enumeration of S.

6. If g is a one-to-one enumeration of S, then either f ∼ g or f̃ ∼ g.

Proof of Claim 4. The first part of this Claim follows from the definition of s_{t}^{χ} at stage t and the assumption. The second part of the Claim follows from Claim 3. To prove the third part note that at each recovery stage at which we perform a U-operation we put some new numbers into χ(s_{t}^{χ}) and put the least number in r(χ(s_{t}^{χ})) into l(χ(s_{t}^{χ})) and vice versa. To prove the fourth part note that if x ≠ s_{t}^{χ}, then there exists a stage t > t′ such that after this stage the pair χ_{t}(x) will never be used. Therefore χ(x) = χ_{t}(x). It follows that χ_{t}(x) is finite. The fifth part now follows from Claim 1. To prove the last part of the Claim we argue that r^{χ} = ⋃_{t>t′} r_{t}^{χ} is the desired reduction of χ to g. As there are infinitely many recovery stages, each x in the domain of χ is eventually marked with a □_{w} and so is in the domain of r^{χ}. Thus χ(x) covers g(r^{χ}(x)) and so if g is a one-to-one enumerations of S, χ(x) = g(r^{χ}(x)) as required by parts 3, 4 and 5 of this Claim. □ Claim 5. If the construction changes its reduction at infinitely many stages, then the pair g(s_{g}) is infinite and all pairs in f are finite. Proof of Claim 5. For each number x, if x ≠ s_{t}^{χ} and x ≠ s̃_{t}^{χ} = sχ̃ ; t for all t, then it is immediate that χ(x) is finite. Therefore it is enough to prove that the pairs χ(s_{t}^{χ}) and χ(s̃_{t}^{χ}) are finite for all t and χ ∈ {f, f̃}. Let t_{1}, t_{2}, … be the sequence of stages at which the construction changes its designated reduction. We can suppose that at stage t_{1} the construction changes its reduction from f to f̃. Consider s_{t_{1}}^{f}. We have s_{t_{1}}^{f} ≠ s_{t_{1}−1}^{f} and s̃_{t_{1}−1}^{f} = s̃_{t_{1}}^{f}. At stage t_{2}, we have s̃_{t_{2}}^{f} ≠ s̃_{t_{1}}^{f} and s_{t_{2}}^{f} = s_{t_{1}}^{f}. Continuing this procedure, we see that in the sequences

s_{t_{1}}^{f}, s_{t_{2}}^{f}, … and s̃_{t_{1}}^{f}, s̃_{t_{2}}^{f}, …

each number can appear at most twice. Therefore neither f nor f̃ contains an infinite set. □

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

General Construction. We will construct an enumeration f of a symmetric family S by stages f_{t} such that (Lemma 3.11) the sets lf_{t}(n) are all distinct for distinct n as are each of rf_{t}(n), lf(n) and rf(n), respectively. As the enumeration f̃ is uniquely determined by f, we will usually not describe it explicitly. We will satisfy all the requirement Q_{j} and R_{j}. As we only need to worry about families G_{j} enumerated by functions g_{j} which enumerate families isomorphic to S, we may assume that the sets lg_{t}(n) are all distinct for distinct n as are the rg_{t}(n) and that for, every t and n, g_{t}(n) ⊆ f_{t}(m) for some m. (If there are pairs partially enumerated, do not allow any extensions until it is once again possible to make all the pairs distinct in the required way. This can be done so as to add any single desired element to any one of the pairs in G if it has the required form.)

We now describe some preliminary notions for the construction. Consider the alphabet {c, d, ∞, f, f̃, w} with the ordering c < d < ∞ < f < f̃ < w.

The priority tree T over this alphabet is defined as follows. If α ∈ T and the length of α is even, then αˆ ∞, αˆ f, α ˆ f̃, and αˆ w belong to T . If α ∈ T and the length of α is odd, then αˆ c and αˆ d belong to T . The induced lexicographical ordering ≤_{L} on the tree T coincides with the usual priority ordering on T .

For every α ∈ T of length 2j + 1, we will define an α–strategy to meet the requirement Q_{j}. At stage t, to each node α ∈ T of length 2j + 1 the construction attaches some witness numbers c, d and witness pairs (C, D), (D, C) such that C and D are finite pairwise disjoint sets and f_{t}(c) = (C, D), f_{t}(d) = (D, C). One of the goals of the construction is to diagonalize against the potential reduction Φ_{j} at c. The strategy to meet the requirement Q_{j} is based on the U-operation. Such a node α of length 2j + 1 ≤ t can have one of two outcomes at stage t. Its outcome is c if the construction has acted to satisfy the requirement Q_{j} at this or any previous stage since α was last initialized. Otherwise it is d.

For every α ∈ T of length 2j, we will define an α–strategy to meet the requirement R_{j}. The strategy to meet the requirement R_{j} is based on a stagewise definition of potential reduction functions r_{α,t}^{f} and rf̃ ; α,t which try to reduce the enumerations f and f̃, respectively, to g_{j}. At each stage that they are defined one of these reductions will be the construction’s designated reduction. At stage t, such a node α of length 2j ≤ t can have one of four outcomes: The outcome is w if α is in the waiting state. Otherwise, we say that t is an α-recovery stage at which there are three possible outcomes. The outcome is χ if the reduction r^{χ} extends the previous designated one for χ and so, in particular, the construction does not change its designated reduction. Otherwise, the outcome is ∞ and construction changes its designated reduction from r_{α,t}^{χ} to rχ̃ ; α,t. Associated with this node and procedure is an α-special pair with index s_{α,t} in the enumeration g_{j} and corresponding indices in the enumerations f and f̃.

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.

Suppose that the length of α is 2j + 1. To initialize α at stage t means to cancel all the numbers and pairs attached to α and all prohibitions on the placement of marks issued by α. Any number n, and therefore the pairs f_{t}(n) and f̃_{t}(n), cancelled at stage t, are no longer attached to any node and will never be used at later stages in any U-operations. Therefore f(n) will be equal to f_{t}(n). Suppose that the length of α is 2j. To initialize α at stage t means to cancel the numbers and pairs attached to α as well as the αspecial pair with index s_{α,t−1} and the previous reduction functions r_{α,t−1}^{f} and rf̃ ; α,t−1and to define r_{α,t}^{f} and rf̃ ; α,t to have the empty domain and declare r_{α,t}^{f} to be the construction’s designated reduction for α. Again, as f uniquely determines f̃, we usually only describe the enumeration of f and the earlier warning about only defining f on a computable domain apply here as well. Remarks in double brackets are again only explanatory.

Now we describe the general construction.

Construction:

Stage 0. Initialize all requirements α.

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

Case 1: |α| = 2j + 1. If we have acted to satisfy α at some stage since u, the outcome of α is still c. If not, and there are no numbers attached to α, choose new numbers c, d, x and y and new finite pairwise disjoint sets C, D, X and Y, let f_{t}(c) = (C, D), f_{t}(d) = (D, C), f_{t}(x) = (X, Y), f_{t}(y) = (Y, X) and attach these witness numbers and witness pairs to α with c and d being the numbers on which we intend to meet Q_{j}. In any case, let c, d, x and y be the witness numbers now attached to α. Now see if Φ_{j,t}(c) = d. If not, the outcome of α is d. If so, we let α_{1}, … α_{l} be the nodes β ⊂ α such that |β| is even and βˆ w ⊈ α listed in order of increasing length. (It may be that l = 0, i.e., there is no such β. In this case, the corresponding conditions below are simply empty.) If there are no other numbers attached to α, we choose new numbers a_{1}, b_{1}, …, a_{2l}, b_{2l} and corresponding new pairs (with a_{i} and b_{i} being indices for symmetric pairs) which we attach to α. Our actions will now be directed towards working with the following sequence of numbers (and the corresponding pairs) possibly with replacements put for some of them:

b_{1}, s_{α_{1},t}^{χ}, b_{2} …, b_{2i−1}, s_{α_{i},t}^{χ}, b_{2i}, …, b_{2l−1}, s_{α_{l},t}^{χ}, b_{2l}, y, c,
d, x, a_{2l}, s̃_{α_{l},t}^{χ}, a_{2l−1}, …, a_{2i}, s̃_{α_{i},t}^{χ}, a_{2i−1}, …, a_{2}, s̃_{α_{1},t}^{χ}, a_{1}.

For i ≤ l, we put marks □_{w}^{α_{i}} on all the numbers in this sequence that are between s̃_{α_{i},t}^{χ} and s_{α_{i},t}^{χ} and issue a prohibition on any other marks being put on the numbers in this sequence which are attached to α. This prohibition will be lifted when we act to satisfy α or the number is cancelled. In this case the outcome of α is d. If there are already such numbers attached to α [[which we shall show are all in the range of the appropriate r_{α_{i}}^{χ}]], we perform a U-operation on the following symmetric finite sequence of pairs which corresponds to the above sequence of numbers:

f(b_{1}), f(s_{α_{1},t}^{χ}), f(b_{2}) …, f(b_{2i−1}), f(s_{α_{i},t}^{χ}), f(b_{2i}), …, f(b_{2l−1}), f(s_{α_{l},t}^{χ}),

f(b_{2l}), f(y), f(c), f(d), f(x), f(a_{2l}), f(s̃_{α_{l},t}^{χ}), f(a_{2l−1}), …,
f(a_{2i}), f(s̃_{α_{i},t}^{χ}), f(a_{2i−1}), …, f(a_{2}), f(s̃_{α_{1},t}^{χ}), f(a_{1}).

For each i ≤ l, we now also extend the set l(f_{t}(s_{α_{i},t}^{χ})) in such a way that it contains the least element from r(f_{t}(s_{α_{i},t}^{χ})) which did not previously belong to l(f_{t}(s_{α_{k_{i}},t}^{χ})) and vice versa for r(f_{t}(s_{α_{i},t}^{χ})). We also add new numbers to insure that this pair does not become selfsymmetric. We, of course, extend the set f_{t}(s̃_{α_{i},t}^{χ}) so as to preserve the symmetry between these pairs. Next, as necessary, we put into the pairs that participated in the U-operation new pairwise distinct pairs of numbers not changing the symmetry between the appropriate pairs so as to insure (5) above. The prohibitions on marking numbers issued by α are now lifted and, for i ≤ l, we mark the numbers b_{2i−1} and a_{2i−1} in the sequence with □_{w}^{α_{i}}. We have now satisfied Q_{j} and the outcome of α is c.

Case 2: |α| = 2j. If there are no special numbers and pairs attached to α we choose new numbers s and s̃ on which we put marks □_{w}^{α}. These are the special numbers for α and are designated by s_{α,t}^{f} and s̃_{α,t}^{f}, respectively. We also choose a corresponding new pair of sets (P, Q) and extend the family by letting f(s) = (P, Q) and f(s̃) = (Q, P). We attach these numbers and pairs to α. The potential reductions r_{α,t}^{f} and rf̃ ; α,t (of f and f̃, respectively, to g_{j}) are defined to be empty and r_{α,t}^{f} is declared the construction’s designated potential reduction. In this case, the outcome of α is w. Otherwise, we define the potential reductions r_{α,t}^{f} and rf̃ ; α,t on the numbers marked with □_{w}^{α} by r_{α,t}^{f}(i) = k if and only if g_{j,t}(k) is covered by f_{t}(j) and by no f̃_{t}(i) with i ≠ j and rf̃ ; α,t(i) = k if and only if g_{j,t}(k) is covered by f̃_{t}(j) and by no f̃_{t}(i) with i ≠ j. If these functions are not defined on all numbers marked with □_{w}^{α}, the outcome of α is w and this is a waiting stage for α. Otherwise, t is an α-recovery stage. At the first α-recovery stage v after u, the number x such that r_{α,t}^{f}(s_{α,t}^{f}) = x is declared the index of the α-special set for g_{j} and is denoted by s_{α,v}. It remains fixed until α is initialized. [[We will see that the numbers s_{α,z}^{χ} for later stages z are determined by the requirement that r_{α,z}^{χ}(s_{α,z}^{χ}) = s_{α,z}.]]

If t is an α-recovery stage, we see if r_{α,t}^{χ} extends the previous designated reduction r_{α,s}^{χ}. If so, set s_{α,t}^{χ} = s_{α,s}^{χ}. This defines the number s̃_{α,t}^{χ} with respect to the enumeration χ_{t}. [[Note that if s_{α,s}^{χ} participated in a U-operation then s̃_{α,t}^{χ} ≠ s̃_{α,s}.]] In this case the outcome of α is χ. If r_{α,t}^{χ} does not extend the previous reduction r_{α,s}^{χ}, the construction changes its (designated) reduc-

tion from r_{α,s}^{χ} to rχ̃ ; α,t. Set sχ̃ ; α,t = s̃_{α,t}^{χ} = s̃_{α,s}^{χ} = s̃_{α,s}^{χ} = sχ̃ ; α,s. This defines the

number s̃χ̃ ; α,t = s_{α,t}^{χ} with respect to the enumeration χ̃_{t}. [[Note that if s_{α,s}^{χ} participated in a U-operation then s̃χ̃ ; α,t = s_{α,t}^{χ} ≠ s_{α,s}^{χ} = s̃χ̃ ; α,s.]] In this case the outcome of α is ∞. In every case of an α recovery, attach the numbers s_{α,t}^{χ} = s̃χ̃ ; α,t and sχ̃ ; α,t = s̃_{α,t}^{χ} and the corresponding pairs to α and put marks □_{w}^{α} on all numbers in the domain of f_{t} that do not have them and are not attached to nodes of higher priority or prohibited from getting them. [[We will see that s_{α,t}^{χ} and s̃_{α,t}^{χ} are already so marked.]]

At the end of stage t we see if there are numbers b_{2i−1}, b_{2i}, a_{2i}, a_{2i−1} attached to some α for which we have not acted at stage t. If the corresponding node α_{i} ⊆ α recovers at t, we cancel these numbers (and the corresponding pairs) and appoint new ones b′_{i}, c′_{i} attached to α and associate marks and prohibitions with them as had been done with b_{i} and c_{i}.

This concludes the description of the construction.

Verifications:

For each i ∈ ω, define f(i) = ⋃_{t} f_{t}(i). Define the family S by

S = {f(i)|i ∈ ω}.

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

Lemma 3.4 The following properties holds of the construction:

1. For all n, t ∈ ω, at stage t the pair χ_{t}(n) participates in a U-operation if and only if the pair χ̃_{t}(n) participates in the same U-operation.

2. For any pair χ_{t}(n), if n is cancelled at stage t, then the construction never uses the pairs χ_{t}(n) or χ̃_{t}(n) in any U-operation after stage t. Therefore χ(n) = χ_{t}(n) and χ̃(n) = χ̃_{t}(n).

3. The pair f(n) is infinite if and only if the set {t| at stage t the set f_{t}(n) participated in a U-operation} is infinite. □

Lemma 3.5 Suppose that at a stage t a U-operation is applied by α to the sequences of pairs corresponding to

b_{1}, s_{α_{1},t}^{χ}, b_{2} …, b_{2i−1}, s_{α_{i},t}^{χ}, b_{2i}, …, b_{2l−1}, s_{α_{l},t}^{χ}, b_{2l}, y, c,
d, x, a_{2l}, s̃_{α_{l},t}^{χ}, a_{2l−1}, …, a_{2i}, s̃_{α_{i},t}^{χ}, a_{2i−1}, …, a_{2}, s̃_{α_{1},t}^{χ}, a_{1}.

If there exists a stage t′ > t at which a node to the left of α_{i} is accessible, then the pairs corresponding to numbers between s̃_{α_{i},t}^{f} and s_{α_{i},t}^{f} (inclusively) never participate in any U-operation at any t′′ > t′, and are therefore finite. □

Now 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 if 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 3.6 The enumerations f and f̃ are not equivalent.

Proof. Suppose that f is reducible to f̃ via Φ_{j}. Consider the requirement Q_{j} and the node α of length 2j + 1 on the true path corresponding to Q_{j}. Let t be the first stage at which α is accessible but after which no β left to α is ever accessible again. Let c and d be the witness numbers attached to the node α at stage t on which we intend to meet the requirement Q_{j}. Then f_{t}(c) is symmetric to f_{t}(d). If there is no v > t such that Φ_{j,v}(c) = d, we clearly satisfy the requirement. Otherwise, we eventually attach the appropriate sequence of numbers (and pairs) to α and assure that there are always such numbers attached at every later α-stage. We then eventually return to α without it being initialized in between by our choice of α and t. At such a stage we perform the U-operation which guarantees that Φ_{j} cannot reduce f to f̃. (f(c) has become selfsymmetric and remains so as it is never used in a U-operation again and so never changes. Thus f(c) = f̃(c) and so any Φ reducing f to f̃ (or vice versa) would have to have Φ(c) = c.) □

To prove that we also satisfy the requirements R_{j}, we analyze what can happen between stages at which the requirement α of length 2j on P is accessible. Let u be the last stage at which α is initialized and let t_{0}, …, t_{n}, … be the sequence of stages after u at which α is accessible. At t_{0} we attach special numbers s and s̃ (and the corresponding pairs) to α and mark the numbers with □_{w}^{α}. The outcome of α is w. Let v be the first α-recovery stage and s_{α} = s_{α,v} be the index of the α-special set for g_{j} defined at v. We now consider what can happen in the interval of stages [t_{n}, t_{n+1}].

Lemma 3.7 1. If t_{n} is a waiting stage for α, then no change can take place in any pair whose index is in the domain of r_{α}^{χ} nor in the values of s_{α,t}^{f}, sf̃ ; α,t and no new marks □_{w}^{α} are put on new numbers.

2. If t_{n} is a recovery stage then the only change that can take place at t_{n} is generated by at most a single application of a U-operation by some β ⊃ α. (So if no U-operation is applied, no change occurs.)

3. In any case, no such changes can occur, nor marks be added, between t_{n} and t_{n+1}.

Proof. The first claim is clear from the construction as the only way a pair can get new elements once started is by participating in a U-operation but no pair marked with a □_{w}^{α} can participate in such an operation performed by a node to the right of α. As for the second, note that no U-operation can be performed for any β ⊆ α as then βˆ c would become accessible for the first time since β was last initialized and so t_{n} could not be an α-recovery stage. When we perform a U-operation for some β ⊇ α, βˆ c and so all its extensions becomes accessible for the first time since it was last initialized. Thus none of them can perform a U-operation by construction. The third claim is clear from the fact that only nodes to the right of α can perform a U-operation when α is neither accessible nor initialized. □

Lemma 3.8 Suppose that t_{n} is an α-recovery stage with designated reduction r_{α,t_{n}}^{χ}, some β ⊃ α performed a U-operation (on a sequence as described in the construction with α = α_{i} for some i) at t_{n} and t_{m} is the next α-recovery stage. Note that, by induction, when the U-operation is performed all the numbers between s_{α}^{χ} and s̃_{α}^{χ}, inclusively, and no others in the sequence are marked with □_{w}^{α} (and so in the domain of r_{α,t_{n}}^{χ}) while at the end of stage t_{n} both b_{2i−1} and a_{2i−1} are also so marked and so all are in the domain of r_{α,t_{m}}^{χ}. There are then two possibilities for what happens at t_{m}:

1. r_{α,t_{m}}^{χ}(s_{t_{n}}^{χ}) = r_{α,t_{n}}^{χ}(s_{t_{n}}^{χ}) = s_{α}. In this case, r_{α,t_{m}}^{χ} remains the designated reduction and extends r_{α,t_{n}}^{χ}, s_{α,t_{n+1}}^{χ} = s_{α,t_{n}}^{χ} which is already marked with □_{w}^{α} by induction and s̃_{α,t_{n+1}}^{χ} = a_{2i} which was marked with □_{w}^{α} at t_{n} and the outcome of α is χ.

2. r_{α,t_{m}}^{χ}(s_{t_{n}}^{χ}) ≠ r_{α,t_{n}}^{χ}(s_{t_{n}}^{χ}). In this case, the construction changes its designated reduction from χ to χ̃; sχ̃ ; α,t_{m} = sχ̃ ; α,t_{n} = s̃_{α,t_{n}}^{χ} which is already marked with □_{w}^{α} by induction and s̃χ̃ ; α,t_{n+1} = s_{α,t_{m}}^{χ} = b_{2i−1} which was marked with □_{w}^{α} at t_{n}. Also rχ̃ ; α,t_{m}(b_{2i−1}) = s_{α}.

Proof. Given the previous Lemma, the proof of this Lemma is essentially the same as that of Claim 3 above. □

Lemma 3.9 Consider f(n), n ∈ ω. The following conditions are equivalent:

1. The pair f(n) is infinite.

2. The pair f(n) is infinite and there exists a unique α ∈ P such that n = lim_{t}s_{α,t}^{f} or n = lim_{t}s̃_{α,t}^{f}.

3. The pair f(n) is infinite and selfsymmetric.

Proof. By Lemma 3.4, the only way f(n) can become infinite (1) is by participating in a U-operation infinitely often. It is clear from the list of sets to which U-operations are applied that the only candidates for such indices n are s_{α,t}^{χ} and s̃_{α,t}^{χ} for α on P. Thus, by Lemma 3.8, for any single one to become infinite αˆ χ must be on P and n must be lim_{t}s_{α,t}^{χ} (2). In this case, f(n) becomes selfsymmetric (3) by our action of extending f_{t}(s_{α,t}^{χ}) by adding on the least element of lf_{t}(s_{α,t}^{χ}) not in rf_{t}(s_{α,t}^{χ}) and vice versa each time s_{α,t}^{χ} participated in a U-operation. Of course, (3) implies (1) trivially. □

Lemma 3.10 The family S of pairs of computably enumerable sets is symmetric.

Proof. As S_{t} is symmetric for every t by construction, (Q, P) ∈ S for every finite (P, Q) ∈ S and so the Lemma follows from Lemma 3.9. □

Lemma 3.11 For all t, n ∈ ω there is an x ∈ lf_{t}(n) and a y ∈ rf_{t}(n) such that x ∉ lf_{t}(m) and y ∉ rf_{t}(m) for any n ≠ m. Moreover, for all n ∈ ω, there is an x ∈ lf(n) and a y ∈ rf(n) such that x ∉ lf(m) and y ∉ rf(m) for any n ≠ m. Thus the enumeration f is one-to-one.

Proof. The first claim is clearly true by induction on the stages of the construction. The second follows from the first when one of f(n) and f(m) is finite and from Lemma 3.9 and the fact that, when each s_{α,v} is first defined, it has in each set of the corresponding pair numbers that never appear in any s_{β,z} for β ≠ α when both are infinite. The third claim is an immediate consequence of the second. □

Lemma 3.12 All requirements R_{j} are satisfied.

Proof. We consider the node α of length 2j on the true path P. Assume, possibly for the sake of a contradiction, that g_{j} is a one-to-one enumeration of the family S. Let u be the last stage at which α is initialized and t_{0}, t_{1}, …, t_{n}, … be the sequence of stages after u at which α is accessible. We have the following three cases.

Case 1. Suppose that αˆ w ∈ P. It follows that there exists an n such that αˆ w is accessible at every t_{m} for m ≥ n. There are only finitely many numbers (and so corresponding pairs in S_{t_{n}}) marked with □_{w}^{α} at stage t_{n} and no new ones are ever marked by Lemma 3.8. Thus there is an m > n such that each one of these pairs has an isomorphic copy in the family enumerated by g_{j,t_{m}}. By Lemma 3.11 and our conventions about the enumeration g_{j}, t_{m} would be a recovery stage for α for the desired contradiction.

Case 2. Suppose that αˆ χ ∈ P, where χ ∈ {f, f̃}. In this case, there is an n such that αˆ χ or αˆ w is accessible at every t_{m} for m ≥ n. (The point here is that, once αˆ χ is accessible, α ˆ χ̃ can become accessible only if αˆ ∞ is first accessible but if that happened infinitely often it would contradict our assumption that αˆ χ ∈ P.) By Lemma 3.8, nothing happens to r_{α,t}^{χ} at stages t_{m} at which αˆ w is accessible or between stages t_{m} and t_{m+1}. Thus r_{α,t_{m}}^{χ} ⊆ r_{α,t_{m}+1}^{χ} for every m ≥ n. We let r_{α}^{χ} = ∪{r_{α,t_{m}}^{χ}|m ≥ n} and claim that, on its domain, it is the desired reduction of χ to g_{j}. It is clear from the construction and the proof of Lemma 3.6 and from Lemma 3.8 that the only numbers that never get a mark □_{w}^{α} are lim_{t} s_{β,t}^{χ} for βˆ χ ⊆ α and the finitely many numbers permanently attached to or prohibited from getting marks by nodes γ of higher priority than α. Thus r_{α}^{χ} is defined on all but finitely many indices in the family S enumerated by χ. As g_{j} is a one-to-one enumeration of S, this map is the desired computable reduction on its domain by the definition of covering and Lemma 3.11. It can be computably extended to one on all of the domain of χ since there are only finitely many indices omitted from its domain.

Case 3. Suppose that αˆ ∞ ∈ P. Consider the pairs χ(s_{α,t}^{χ}) and χ(s̃_{α,t}^{χ}) for χ ∈ {f, f̃}. Let v_{1} < v_{2} < … be the sequence of stages after u at which αˆ ∞ is accessible. Without loss of generality, suppose that at stage v_{1} the designated reduction is r_{α,v_{1}}^{f}. Consider s_{α,v_{1}}^{f}. By Lemma 3.8, s_{α,v_{1}}^{f} ≠ s_{α,v_{2}}^{f} and s̃_{α,v_{1}}^{f} = s̃_{α,v_{2}}^{f}. At stage v_{3}, we have s̃_{α,v_{2}}^{f} ≠ s̃_{α,v_{3}}^{f} and s_{α,v_{2}}^{f} = s_{α,v_{3}}^{f}. Continuing this way, we see that in the sequences

s_{α,v_{1}}^{f}, s_{α,v_{2}}^{f}, … and s̃_{α,v_{1}}^{f}, s̃_{α,v_{2}}^{f}, …

each number appears at most twice. Therefore, by the construction, all pairs f(s_{α,v_{i}}) are finite. Consider the corresponding special pair g_{j}(s_{α}) in the enumeration g_{j} (s_{α} = s_{α,v_{1}} and it never changes). Note that the pair g_{j}(s_{α}) is infinite. Suppose that there exists an x such that f(x) = g_{j}(s_{α}). Thus f(x) is an infinite set and, by Lemma 3.9, f(x) is selfsymmetric and equal to lim_{t}s_{β,t}^{χ} for some βˆ χ on the true path P. Suppose that β ⊃ α or β ⊂ α. By Lemma 3.11, β is unique and the pair f(x) has an element which does not belong to g_{j}(s_{α}). Therefore f(x) ≠ g_{j}(s_{α}) which is a contradiction and so α = β. It follows that x = lim_{t}s_{α,t}^{f} or x = lim_{t}s̃_{α,t}^{f}. However, as we noted above, neither of the limits lim_{t}s_{α,t}^{f} and lim_{t}s̃_{α,t}^{f} exist for the desired contradiction. □

4 Families and Structures of Dimension k

In this section we will briefly explain the basic ideas for producing a computably categorical structure which has exactly k computable isomorphism types, k ∈ ω, when expanded by any finite number of constants. The first natural step is to consider families of k-tuples of computably enumerable sets and define an appropriate notion of symmetry. The second natural step is to generalize the notion of U-operation which was a crucial mechanism in meeting diagonalization requirements Q_{e}. We will also need to have an appropriate priority tree for the generalization of our construction. Another technical consideration is to define the special k-tuple of sets for the potential enumerations of the family we would like to build. For example, in the proof of Theorem 3.1, depending on stage t and a node α, the construction needed to have a special g–pair of sets g(s_{α,t}) for each potential enumeration g. As we will explain below, in the general case, for each potential enumeration g the construction will need to have exactly (k − 1) many special k–tuples of sets which depend on stage t and the nodes of the priority tree. It turns out that the generalization of the U-operation requires several technical considerations. We will present these considerations below. A simpler proof of the theorem, however, will appear with more details in a work on degree spectra of relations on computable structures [10].

Let X = (X_{1}, …, X_{k}) be a k–tuple of sets. Define pX to be equal to (X_{k}, X_{1}, …, X_{k−1}). Thus p is a map defined on the set of all k–tuples of sets. A family S of k-tuples of sets is symmetric if X = (X_{1}, …, X_{k}) ∈ S implies that pX = (X_{k}, X_{1}, …, X_{k−1}) ∈ S, that is, if S is closed under p. We call the sequence X, pX, p^{2}X, …, p^{k−1}X the orbit of X and denote it by o(X). It is obvious that p^{k}X = X. We let p^{0}X = X as well.

Suppose that S is a symmetric family of k-tuples. Suppose that f is a one-to-one computable enumeration of S. For each i ≤ k − 1, we define the enumeration f_{i} by setting f_{i}(n) = p^{i}f(n) for all n ∈ ω. In particular, we see from this definition that f_{0} is f.

Definition 4.1 A symmetric family of k-tuples of computably enumerable sets has dimension k if there exists a one-to-one computable enumeration f of S with the following two properties:

1. The enumerations f, f_{1}, …, f_{k−1} are pairwise inequivalent.

2. Each computable one-to-one enumeration of S is equivalent to one of the enumerations f, f_{1}, …, f_{k−1}.

The U-operation defined in §3 on symmetric sequences of pairs was important in our construction of symmetric family of dimension 2. To motivate the analogous operation for sequences of k-tuples of sets, we rephrase the description of the U-operation as follows: For each i ≤ n, consider a pair X_{i}, pX_{i} of pairs of sets. Thus, we have X̃_{i} = pX_{i}. Picture a sequence of pairs arranged as follows:

X_{0}, pX_{0}, X_{1}, pX_{1}, …, X_{n−1}, pX_{n−1}, X_{n}, pX_{n}.

We perform the operation by putting (coordinatewise) all elements of X_{i} into X_{i+1} for i < n, all elements of pX_{i} into pX_{i−1} for i > 0, all elements of X_{n} into pX_{n} and all elements of pX_{0} into X_{0}. This produces a sequence of sets W_{j} for j ≤ 2n + 1 such that W_{0} and W_{2n+1} are selfsymmetric and W̃_{2i+1} = W_{2i+2} for i < n. Informally, one can imagine the original line of sets X_{1}, pX_{1}, …, X_{n−1}, pX_{n−1}, X_{n}, pX_{n} without the first pair as the single spoke of a wheel with center X_{0}, pX_{0}. Thus, in the general case, when we deal with k–tuples of sets, by a spoke we mean a finite sequence

o(X_{1}), …, o(X_{n})

of orbits of k–tuples of sets X_{1}, …, X_{n}. The number n is the length of the orbit. Similarly, a wheel with center o(C) is a sequence

V_{1}, …, V_{k−1}

[figure: Y_{4}; Y_{3}; Y_{2}; Y_{1}; C; X_{1}; X_{2}; X_{3}; X_{4}; pY_{4}; pY_{3}; pY_{2}; pY_{1}; pC; pX_{1}; pX_{2}; pX_{3}; pX_{4}; p^{2}Y_{4}; p^{2}Y_{3}; p^{2}Y_{2}; p^{2}Y_{1}; p^{2}C; p^{2}X_{1}; p^{2}X_{2}; p^{2}X_{3}; p^{2}X_{4}] Figure 2:

of spokes of the same length such that each V_{i} begins with the same orbit o(C). Note that each wheel has exactly k − 1 spokes.

Let o(X_{1}), …, o(X_{n}) be a spoke. Fix an m such that 1 < m ≤ k. Call the sequence p^{m}X_{n}, …, p^{m}X_{1} a designated array. Starting with the orbit X_{1}, …, p^{k−1}X_{1} we put (coordinatewise) all elements of p^{i}(X_{j}) into p^{i}X_{j+1} for i ≠ m. Starting with the last orbit X_{n}, … p^{k−1}X_{n} we put all elements of p^{m}X_{i} into p^{m}X_{i−1} for i > 0. We also put all elements of p^{j}X_{1} into X_{1} and all elements of p^{j}X_{n} into p^{m}X_{n} for j < k − 1. We call this operation a U(m)-operation. The affect of the U(m)-operation is that the first k–tuple X_{1} has become selfsymmetric (all components are equal) and at the end of the spoke the k–tuple p^{m}X_{n} has become self symmetric.

Definition 4.2 Let V_{1}, …, V_{k−1} be a wheel with center o(C). The generalized U-operation applied to this wheel is defined by performing a U(m)- operation on the spoke V_{m} for each m with 1 ≤ m ≤ k − 1.

In Figure 2 we show graphically an example of a generalized U–operation applied to a wheel when k = 3 and n = 5. In this picture C, pC, p^{2}C is the center, V_{1} is the spoke on the right side of the center with pX_{1}, pX_{2}, pX_{3}, pX_{4} being the designated array, and V_{2} is the spoke on the left side of the center with p^{2}Y_{1}, p^{2}Y_{2}, p^{2}Y_{3}, p^{2}Y_{4} being the designated array. In this picture X → Y means that we put coordinatewise all elements in X into Y. The affect of this U-operation in Figure 2 is that the 3–tuples C, pX_{4}, and p^{2}Y_{4} have become selfsymmetric. Now using the above definitions one can prove the next lemma which is the analog of Lemma 3.3.

Lemma 4.3 The generalized U-operation applied to any wheel produces a symmetric family of k-tuples with k many selfsymmetric sets. □

Let g_{i}, i ∈ ω, be a standard enumeration of all computable enumerations of families of k–tuples of computably enumerable sets. To construct a family S of dimension k we need to build a one-to-one enumeration f of S such that the following requirements are met:

Q_{e,i} : f is not equivalent to f_{i} via Φ_{e},

where i = 1, …, k − 1 and

R_{i} : g_{i} ∼ f_{0} ⋁ … ⋁ g_{i} ∼ f_{k−1} or g_{i} is not a one-to-one enumeration of S.

The priority tree T over the alphabet A = {c, d, ∞, f_{0}, f_{1}, …, f_{k−1}, w} with the ordering c < d < ∞ < f_{0} < f_{1} < … < f_{k−1} < w is defined as follows. If α ∈ T and the length of α is even, then αˆ ∞, αˆ f_{i} for all i = 0, …, k − 1 and αˆ w belong to T . If α ∈ T and the length of α is odd, then αˆ c and αˆ d belong to T .

At stage t of the construction, we use the following objects and terminology.

1. Enumerations f_{i,t}, i = 0, …, k − 1, and Families S_{t}. f_{i,t} is the approximation to f_{i} that the construction is building. That is, for each s ∈ ω, we have

f_{i}(s) = ⋃_{t} f_{i,t}(s), i = 0, … k − 1.

Each of the functions f_{0,t}, …, f_{k−1,t} enumerates the same symmetric family which we denote by S_{t}.

2. Functions r_{α,t}^{f_{i}}, i = 0, … k −1. Each r_{α,t}^{χ}, where χ ∈ {f_{0}, …, f_{k−1}}, is the function which reduces χ_{t} to g_{t} at stage t. The function r_{α,t}^{χ} can extend the previous reduction. If r_{α,t}^{χ} does not extend the previous designated reduction, then we say that the construction changes its (designated) reduction.

3. Diagonalization Witnesses. To each partial computable function Φ_{e} and i, i = 0, …, k − 1, the construction assigns an orbit C which depends on stage t and a node of the priority tree. One of the goals of the construction is to diagonalize against the potential reduction Φ_{e} on this orbit. The strategy to meet the requirement Q_{e,i} is based on the generalized U-operation. More precisely, suppose Φ_{e} is a potential function which reduces f to f_{i}. Let o(C) = f_{0,t}(l_{0}), …, f_{0,t}(l_{i}), … f_{0,t}(l_{k−1}) be an orbit assigned to meet Q_{e,i}. Suppose that Φ_{e}(l_{0}) = l_{i}. Then to meet Q_{e,i}, the construction takes a wheel with center C and performs a generalized U-operation on this wheel. This action diagonalizes against Φ_{e} and meets the requirement Q_{e,i}.

4. g–Special k–Tuples. For each potential enumeration g and node α devoted to it, the construction picks (k−1) many k-tuples g(s_{α,1}), …, g(s_{α,k−1}) called α–special k–tuples. The construction will satisfy the following property. If there exist infinitely many stages at which the construction changes its reduction, then there will be a k–tuple among g(s_{α,1}), …, g(s_{α,k−1}) which becomes infinite, while all k-tuples in f_{0} contained in the infinite k–tuple are finite, and therefore g is not a one-to-one enumeration of S. If after some stage the construction never changes its reduction and g is a one-to-one enumeration of the family S, then g is equivalent to one of f_{0}, …, f_{k−1}.

5. Special Numbers s_{α,t}^{f_{i}}, i = 0, …, k − 1. The construction uses these numbers so that r_{α,t}^{f_{i}}(s_{α,t}^{f_{i}}) = s_{α,i} for all i = 0, …, k − 1. Thus f_{t}(s_{α,t}^{f_{i}}) is the k–tuple in f_{i,t} which corresponds to g(s_{α,i}) at stage t. The construction guarantees that the orbits of the k-tuples f_{t}(s_{α,t}^{f_{0}}), …, f_{t}(s_{α,t}^{f_{k−1}}) do not intersect. In addition, the construction also guarantees that if the k–tuples corresponding to these numbers participate in performing a generalized Uoperation on a wheel, then these k–tuples appear in the different spokes of the wheel. In addition, each of these k–tuples will be in the designated arrays of the corresponding spoke. Moreover, if t is an α-recovery stage, then these numbers satisfy the following important properties which are the analogs of those of the special numbers (pairs) s_{α,t}^{f} and sf̃ ; α,t in the construction of a symmetric family of dimension 2.

1. If the construction does not change its reduction, then these special numbers do not change.

2. If the construction changes its reduction, then one of these special numbers will change, that is will be different from the all previous ones.

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 χ(lim_{n→∞}s_{α,n}^{χ}) becomes selfsymmetric and infinite.

Now the reader can see that the construction of a symmetric family of dimension k is similar to the construction of Theorem 3.1. Given a symmetric family S of dimension k, we can code a such family into a structure (as we did in the proof of Theorem 2.1) and so prove our main result:

Theorem 4.4 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. □

References

[1] J. N. Crossley, ed., Aspects of Effective Algebra, Proceedings of a Conference at Monash University, Australia, 1–4 August, 1979, Upside Down A Book, Yarra Glen, 1981.

[2] Yu. Ershov and S. S. Goncharov, eds., Logic Notebook: Problems in Mathematical Logic, Novosibirsk University, 1986.

[3] A. Fröhlich and J. C. Shepherdson, Effective Procedures in Field Theory, Phil. Trans. Roy. Soc. London ser. A 248 (1956), 407-432.

[4] S. S. Goncharov, The Problem of the Number Of Non-Self-Equivalent Constructivizations, Algebra i Logika, 19 (1980), 621-639.

[5] A. Grzegorczyk, On the Definitions of Computable Real Continuous Functions, Fund. Math. 44 (1957), 61-71.

[6] V. Harizanov, Pure Recursive Model Theory, preprint, to appear in Handbook of Recursive Mathematics, Y. Ershov, S. Goncharov, A. Nerode, J. Remmel eds.

[7] V. Harizanov, The possible Turing Degree of a Nonzero Member in a Two Element Degree Spectrum, Annals of Pure and Applies Logic, 60 (1993), 1-30.

[8] L. Harrington, Recursively Presentable Prime Models, J. Symb. Logic 39 (1974), 305-309.

[9] N. Khisamiev, On Strongly Constructive Models of Decidable Theories, Izvestia AN Kaz. SSR no. 1, 1974, 83-94.

[10] B. Khoussainov and R. Shore, Computable Isomorphisms, Degree Spectra of Relations, and Scott Families, Annals of Pure and Applies Logic, to appear.

[11] D. Lacombe, Extension de la Notion de Function Recursive aux Functions d’une ou Plussiers Variables Réelles, C. R. Acad. Sci. Paris: I 240 (1955), 151-153.

[12] A.I. Mal‘cev A.I, Constructive Algebras I, Uspekhi Matem. Nauk, 16 (1961), 3-60.

[13] T. Millar, Recursive Categoricity and Persistence, J. Symb. Logic 51 (1986), 430-434.

[14] T. Millar, Abstract Recursive Model Theory, in Handbook of Recursion Theory, E. Griffor, ed., North-Holland, to appear.

[15] M. O. Rabin, Computable Algebra, General Theory and Theory of Computable Fields, Trans. Am. Math. Soc. 95 (1960), 341-360.

[16] 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.