Effective Model Theory: The Number of Models and Their Complexity^{1}

Bakhadyr Khoussainov^{2} Cornell University, Ithaca NY 14853 University of Aukland, Aukland New Zealand

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

Abstract

Effective model theory studies model theoretic notions with an eye towards issues of computability and effectiveness. We consider two possible starting points. If the basic objects are taken to be theories, then the appropriate effective version investigates decidable theories (the set of theorems is computable) and decidable structures (ones with decidable theories). If the objects of initial interest are typical mathematical structures, then the starting point is computable structures. We present an introduction to both of these aspects of effective model theory organized roughly around the themes of the number and types of models of theories with particular attention to categoricity (as either a hypothesis or a conclusion) and the analysis of various computability issues in families of models.

1. Basic Notions

The lectures on which this paper is based were intended to be a brief introduction to effective model theory centered around one set of issues: the number

1 This paper is primarily based on the short course on efective model theory given by the second author at the ASL summer meeting, Logic Colloquium ’97, at the University of Leeds. Much of the material was also presented by the authors in invited talks at a special session of the ASL annual meeting, University of California, Irvine, USA, 1995; the Discrete Mathematics, Theoretical Computer Science, and Logic Conference, Victoria University, Wellington, New Zealand, 1996; the Special Session on Feasible Mathematics of the AMS annual meeting, Orlando, USA, 1996; the annual meeting of the ASL, University of Wisconsin, Madison, 1996, USA; and the Special Session on Computable Mathematics and its Applications of the AMS annual meeting, Baltimore, January 1998.

2 Partially supported by ARO through MSI, Cornell University, DAAL03-91-C0027.

3 Partially supported by NSF Grants DMS-9204308, DMS-9503503, INT-9602579 and ARO through MSI, Cornell University, DAAL03-91-C0027.

of models of specified type and, in particular, the notion of categoricity. For more general introductions we refer the reader to The Handbook of Recursive Algebra (Ershov et al. [1998]), especially the articles by Harizanov [1998] and Ershov and Goncharov [1998]. This Handbook also contains other useful survey papers on aspects of effective model theory and algebra and an extensive bibliography. The one most closely related to the theme of this paper is Goncharov [1998]. Another interesting survey is Millar [1999] in The Handbook of Computability Theory (Griffor [1999]). Two books in progress on the subject are Ash and Knight [1999] and Harizanov [2000]. These are all good sources for material and references. An extensive and very useful bibliography prepared by I. Kalantari [1998] can also be found in Ershov et al. [1998].

One might well begin with the question of what effective model theory is about. Of course, it is about investigating the subjects of model theory with an eye to questions of effectiveness. What then is model theory about and what does one mean by effectiveness? As for model theory we simply quote from two standard texts (to which we also refer the reader for the terminology, notation and results of classical model theory). Chang and Keisler [1990] say “Model theory is the branch of mathematical logic which deals with the connection between a formal language and its interpretations, or models.” Hodges [1993] says “Model theory is the study of the construction and classification of structures within specified classes of structures.” We can take these two definitions as expressing two views of the proper subject of model theory. The first starts with formal languages and so we may say with theories. (We take a theory T to be simply a set of sentences in some (first-order) language L, called the language of T. We say that a theory T is complete if T ⊢ σ or T ⊢ ¬σ for every sentence σ of L.) The second starts with mathematical structures. One might think of these views as, respectively, logical and algebraic. They lead to a basic dichotomy in the approach to effective model theory. Should we “effectivize” theories or structures. Of course, the answer is that we should investigate both approaches and their interconnections. As for what one means by “effectiveness,” there are many notions ranging from ones in computer science to ones of descriptive set theory that have some claim to being versions of effectiveness. Most, if not all, of them can be reasonably called in to analyze different model theoretic questions. In this paper, we limit ourselves to what we view as the primary notion of effectiveness: Turing computability (or, equivalently, recursiveness). Thus we are lead to formal definitions of the two basic notions of our subject, effective theories and structures.

Definition 1.1 A theory T is decidable if the theorems of T form a computable set. A structure A (for a language L) with underlying set (or domain) A is decidable if T h(A, a)_{a∈A}, the complete (or elementary) diagram of A, i.e. the set of all sentences (with constant symbols for each element of A) true in A, is computable. A is computable if D(A, a)_{a∈A}, the (atomic) diagram of A, i.e. the set of all atomic sentences or their negations (again with constant symbols for each element of A) true in A, is computable.

Effective Model Theory: The Number of Models and Their Complexity 3

For those whose basic object of interest, or at least starting point, consists of theories, the decidable theories are the natural effective objects of study. In line with standard model theoretic usage a structure whose complete theory has some property P is often said to also have property P and so we have decidable structures. This is the “logical” point of view. On the other hand, the algebraist or general mathematician usually starts with structures. From this point of view, the effective objects are the computable structures. After all, when one thinks of what a computable group should be one thinks that it should be a group structure for which the group operation is computable and similarly for all other typical algebraic structures. One does certainly not assume that even the word problem, let alone the complete diagram, is computable.

Note that we are deliberately avoiding all issues of coding or Gödel numbering. There are two common approaches to this issue. The Eastern, and especially the Russian, school favors numerations. One starts with a classical structure A and provides a numeration (or enumeration), that is a map ν from the natural numbers ℕ onto the underlying set A of the structure A. The numerated (or enumerated) structure ⟨A, ν⟩ is called constructive if the (appropriately coded) atomic diagram of A, with constant symbols i for i ∈ ℕ interpreted as ν(i), is computable (recursive). ⟨A, ν⟩ is strongly constructive if the complete diagram of A with constant symbols i for i ∈ ℕ interpreted as ν(i) is computable. These notions essentially correspond to what we call computable and decidable structures, respectively.

An established Western approach is to say that all elements are natural numbers, all sets are subsets of ℕ and all functions are functions from ℕ to ℕ. In this view, languages are Gödel numbered, structures consist of a set of numbers and relations and functions on that set. The formal definitions of computable or recursive for subsets of, and functions on, ℕ are then simply applied directly to theories and structures. We adopt what might be viewed as a less formal version of the second approach along the lines followed in Shoenfield [1971] and now, we think, prevalent in thinking (if not always in writing) about computability. Given that we are not considering issues raised by the theory of enumerations, we see no reason to explicitly code objects as numbers. After all, we now “know” what effective and computable mean not only for numbers but for all kinds of data structures from strings to arrays on arbitrary finite alphabets. Thus we talk about a computable language without the formalities of Gödel numbering and so about computable theories, types, etc. Similarly, we have computable structures, lists of names for their elements, diagrams and theories. These may or may not “be” sets of, or functions on, ℕ. Any reader who prefers explicit Gödel numbering is certainly able to make the appropriate translations. (We may at times, however, resort to indices to clarify certain uniformity issues.) For those interested in the issues related specifically to numerations we refer the reader to Ershov [1977].

Of course, the notions of effectiveness associated with Turing computability only make sense in the countable setting.

• All languages, sets, structures and the like are assumed to be countable unless explicitly stated otherwise.

Even so, not all sets or structures are computable. Classically, one typically identifies isomorphic structures. Of course, this eliminates all issues of effectiveness and so is often not appropriate here. We will have to distinguish between classically isomorphic models. The following definitions of presentations and presentability help us make these distinctions.

Definition 1.2 A structure A is computably (decidably) presentable if A is isomorphic to a computable (decidable) structure B which we call a computable (decidable) presentation of A.

Before launching into theorems and analyses, we present a few examples of decidable or computable theories and structures. These theories and structures will serve as examples for many of the notions and results we consider below. Proofs for many of the facts we cite about these structures can be found in Chang and Keisler [1990, 3.4].

Example 1.3 Our language here is that of (linear) orders with one binary predicate ≤. We consider two theories DeLO, dense linear orderings with no first or last element and DiLO, discrete linear orderings with first but no last element. DeLO is axiomatizable, ℵ_{0}-categorical (i.e. all countable models are isomorphic) and so complete and decidable. DiLO is axiomatizable and complete and so decidable but not ℵ_{0}-categorical. The standard structures associated with these theories are ℚ and ℕ, respectively, with their natural orderings. Both are decidable. As DeLO is ℵ_{0}-categorical every model (remember we are considering only countable structures) is isomorphic to ℚ and so decidably presentable. DeLO has effective quantifier elimination and so every computable model is actually decidable. On the other hand, not every model of DiLO is even computably presentable nor is every computable model decidable as we shall see below (for example, in Proposition 6.1). (To see that not every model of DiLO is computably presentable, note that at the cost of a couple of jumps we can form the quotient of a given DiLO by the equivalence relation of being finitely far apart. This procedure can produce an arbitrary ordering with first element. If the quotient ordering is not arithmetic, the original model can’t be computably presented.)

Example 1.4 The next theory we mention is ACF_{0}, algebraically closed fields of characteristic 0. The language is that of field theory with 0, 1, + and ×. ACF_{0} is axiomatizable, ℵ_{1}-categorical, i.e. all models of cardinality ℵ_{1} are isomorphic, and so complete and decidable. ACF_{0} also has effective quantifier elimination and so here too every computable model is actually decidable. Even though ACF_{0} is not ℵ_{0}-categorical, every model is decidably presentable and below we prove a general theorem establishing this fact (Theorem 5.2).

Example 1.5 Finally, we briefly discuss P A, Peano Arithmetic or if one prefers any suitable finitely axiomatized subtheory such as Robinson’s Q [1950]. The language has 0, 1, + and × with the usual axioms. Of course P A is axiomatizable but, by Gödel’s incompleteness theorem, it is neither complete nor decidable. It is not ℵ_{0}-categorical (the compactness theorem provides nonstandard models not isomorphic to ℕ). No model is decidable (again by the incompleteness theorem) and only the standard model ℕ is computably presentable.

Proposition 1.6 (Tennenbaum [1959]) No nonstandard model of P A or even of Robinson’s Q is computably presentable.

Proof sketch. We assume that one has developed the theory T in question enough to, say prove unique factorization into primes and that the standard universal partial computable function is representable in that there is a formula F (e, x, s, i) such that, for each e, x, s, i in ℕ, ϕ_{e,s}(x) = i if and only if T ⊢ F (e, x, s, i). (We do not bother to differentiate between a number and the numeral representing it.) One now shows that T proves the simple fact that (∗)∀s∃y∀e([F (e, e, s, 0) → p_{e}|y ∧ p_{2e+1} ∤ y] ∧[¬F (e, e, s, 0) → p_{e} ∤ y ∧ p_{2e+1}|y]) where p_{e}|y is a formula saying that the e^{th} prime divides y.

Now let A be any nonstandard model of T, s any nonstandard element of A and y the element of A guaranteed by (∗). We define the function f on ℕ by f(e) = 1 if A ⊧ p_{e}|y and f(e) = 0 if A ⊧ p_{2e+1}|y. Clearly f(e) is computable from the atomic diagram of A by searching for an element z such that A ⊧ p_{e} × z = y or A ⊧ p_{2e+1} × z = y. (One must exist by (∗).) However, f is clearly not computable. Indeed, f is diagonally noncomputable: ∀e(f(e) ≠ ϕ_{e}(e)). Thus A is not computably presentable. □

2. The Effective Completeness Theorem

A common theme in model theory is the investigation of questions about when given theories have models with specified properties. Typical examples include characterizing when theories have atomic, prime, universal, homogeneous or saturated models. Other questions involve models of various ranks or dimension, with or without indiscernibles or even more ambitiously attempts to characterize all the models of a given theory. In effective model theory one naturally wants to know when theories have decidable or computable models of each type or even to attempt to characterize the decidable or computable models of a given theory. We will investigate a few examples of such questions. We begin with the issue of when a theory has a model at all – Gödel’s completeness theorem.

Theorem 2.1 (Completeness Theorem) If a theory T is consistent it has a model.

We present one effective analog of the completeness theorem for decidable theories with a proof modeled on Henkin’s proof of the classical completeness theorem. This method of construction is simple but basic for many results in both classical and effective model theory and we will see several variants latter on.

Theorem 2.2 (Effective Completeness Theorem) If a theory T is consistent and decidable then it has a decidable model.

Proof. We assume that the classical Henkin construction is known and so provide only a sketch so that we can check its effective content. Let L_{c} be the language L of T extended by infinitely many new constants c_{i} and let σ_{e} be a (computable) list of the sentences of L_{c}. We construct an increasing sequence of finite sets Ψ_{s} of sentences of L_{c} (with ∧Ψ_{s} = ψ_{s}) consistent with T with union Ψ as in the Henkin proof of the completeness theorem. We need to satisfy the requirements P_{e} for each e ∈ ℕ:

• P_{e} : σ_{e} ∈ Ψ or ¬σ_{e} ∈ Ψ and if σ_{e} is of the form ∃xθ(x) and in Ψ then θ(c_{i}) ∈ Ψ for some i.

Construction: At stage s ask if σ_{s} is consistent with T ∪ Ψ_{s}. If so put σ_{s} into Ψ_{s+1} and, if σ_{s} is ∃xθ(x), also put θ(c_{i}) into Ψ_{s+1} for some as yet unmentioned c_{i}. If σ_{s} is not consistent with T ∪ Ψ_{s} put ¬σ_{s} into Ψ_{s+1}.

Verifications: Obviously, Ψ is complete and the standard argument shows that it is consistent. As usual the elements of the desired model M are the equivalence classes of the c_{i} under the equivalence relation ≡ given by c_{i} ≡ c_{j} iff (c_{i} = c_{j}) ∈ Ψ and the relations and functions on M are determined in the natural way by the formulas in Ψ.

The only issue for us now is the effectiveness of the construction. First we note that one can verify that if T is decidable then Ψ is computable. The only question we must answer at stage s is if σ_{s} is inconsistent with T ∪ Ψ_{s}. This is equivalent to whether or not ψ_{s} → ¬σ_{s} (with new free variables z_{i} substituted in for the constants c_{i} appearing in Ψ_{s} or σ_{s}) is a theorem of T. As T is decidable the answer to these questions is a computable function of s. Thus the equivalence relation c_{i} ≡ c_{j} is computable. (Just look at Ψ_{s+1} where c_{i} = c_{j} is σ_{s}.) So the equivalence classes form a computable set (the domain of M) and the relations and functions on M are determined by Ψ. Indeed, as usual, a sentence σ is true in M if and only if σ ∈ Ψ and so M is decidable as required. □

One theme in effective model theory that we will not pursue investigates the question of how hard it is (say in terms of Turing degree or levels of the (hyper)arithmetic hierarchy) to construct models of a given type when it is not possible to produce decidable or even computable ones. We consider the completeness theorem as our only example. In the construction above the only noneffective step was deciding if σ_{s} is consistent with T ∪ Ψ_{s}. As one can always answer this question computably in T′ (the Turing jump of T), every consistent theory T has a model computable, indeed decidable, in T′.

Corollary 2.3 If T is consistent then there is a model M of T such that the elementary theory of M, T h(M, m)_{m∈M}, is computable in T′ (and so Δ_{2}^{0} in T). Indeed by the low basis theorem, there is always one with T′ ≤_{T} (T h(M, m)_{m∈M})′.

Proof. The first assertion follows immediately from the construction and discussion above. For the second, instead of a single Ψ we build a binary tree (of choices of σ_{s} (and Henkin axioms as appropriate) or ¬σ_{s}). We terminate any path that becomes inconsistent when we find a proof of inconsistency from T. This produces an infinite binary tree computable in T (the particular Ψ constructed above is an infinite path through this tree). The low basis theorem (Jockusch and Soare [1972]) says that there is an infinite path P through the tree with P′ ≤_{T} T′. As above we can construct the desired model (and its complete diagram) computably in P as required. □

• For the sake of convenience we assume from now on that all theories are consistent.

We can now say (in some sense) when a theory T has a decidable model.

Corollary 2.4 A complete theory T has a decidable model if and only if it is decidable. An arbitrary theory T has a decidable model if and only if it has a decidable complete extension.

Proof. If M is a model of T and T is complete then the set of theorems of T is simply the intersection of T h(M, m)_{m∈M} with the sentences of the language L of T and so T is decidable if M is decidable. Even if T is not complete, if M is a decidable model of T then this set is a decidable complete extension of T. The other (if) direction of both assertions in the Corollary follow from Theorem 2.2. □

We will not in general assume that theories are complete. However, finite models have little interest from the viewpoint of Turing computability.

• We assume from now on that all theories have only infinite models.

Now that we “know” when a theory T has a decidable model, we might well ask how many decidable models a theory can have. For now we identify models up to classical isomorphisms and so we might better ask how many decidably presentable models can a theory have. The issues of identifying computable models only when there is a computable isomorphism between them will be taken up in §6-7.

If T is incomplete then every decidable complete extension has a decidable model by Theorem 2.2 and, of course, models of distinct extensions are not isomorphic. Moreover, every decidable model of T is a model of some complete decidable extension of T. Thus if one is interested in the number of decidably presentable models of a theory, it suffices to consider only complete decidable theories. We begin with the possibility that there is only one as in our example DeLO of a decidable ℵ_{0}-categorical theory.

Proposition 2.5 If a theory T is ℵ_{0}-categorical then the following conditions are equivalent:

1. T is decidable.

2. T has a decidable model.

3. All models of T are decidably presentable.

Proof. As ℵ_{0}-categoricity implies completeness, the equivalences all follow directly from the hypothesis, definitions and Theorem 2.2. □

Now, it is a remarkable classical theorem due to Vaught [1961] that no complete theory has exactly two (isomorphism types of) models. The effective analog for decidable models is, however, false.

Theorem 2.6 (Millar [1979], Kudaibergenov [1979]) There is a decidable theory T with exactly two (isomorphism types of) decidably presentable models.

Proof sketch. Let f be a partial computable function whose range is {0, 1} and which does not have a total computable extension. Consider the (computably enumerable but computably inseparable) sets M_{0} = {x|f(x) = 0} and M_{1} = {x|f(x) = 1}. Let f_{0} ⊂ f_{1} ⊂ … be an effective approximation to f such that k ∉ dom(f_{s}) for all k > s.

The language of T contains infinitely many unary and binary predicates P_{i} and R_{i}, respectively, where i ∈ ω. Consider first the theory T_{0} whose axioms are the following set of statements:

1. ∀xP_{0}(x)&∀y(P_{i+1}(y) → P_{i}(y)), where i ∈ ω.

2. If R_{k}(x, y), then x ≠ y and P_{k}(x)&P_{k}(y).

3. If x ≠ y, P_{s}(x)&P_{s}(y) and f_{s}(k) = 0, then R_{k}(x, y).

4. If x ≠ y, P_{s}(x)&P_{s}(y) and f_{s}(k) = 1, then ¬R_{k}(x, y).

One can check that the following four properties hold of T_{0}:

1. T_{0} has a decidable model completion T. Moreover T has a unique 1–type (Definition 3.1) p such that P_{k}(z) ∈ p for all k ∈ ω.

2. If a model A of T has at least two elements realizing p, then A is not decidably presentable.

3. If a model A of T has fewer than two elements realizing p, then A is decidably presentable.

4. If A_{1} and A_{2} are models of T with the same finite number of elements realizing p, then A_{1} and A_{2} are isomorphic.

These properties show that T has exactly two decidably presentable models. □

The above proof can easily be generalized:

Corollary 2.7 For each n ≤ ω, there exists a theory with exactly n nonisomorphic decidable models. □

As for our examples above, an analysis of the structure of models of DiLO as in Chang and Keisler [1990, 3.4] easily implies that there are countably many distinct decidable models. The same is true for ACF_{0} as we shall see in Theorem 5.2.

Although the natural effective version of Vaught’s theorem fails, the proof (properly effectivized) can be used to give a similar result for decidable models (Theorem 4.4 below). We first need to study another aspect of the question of how many decidable models a theory T can have: When are each of the classically studied types of models such as prime, atomic or saturated models of a decidable theory decidably presentable?

3. Decidable Prime Models

We begin our study of specific types of models with prime and atomic models. They will play a crucial role in the next two sections.

Definition 3.1 An n-type Γ or Γ(x_{1}, …, x_{n}) of a theory T is a set of formulas with n free variables in the language of T which is consistent with T such that σ(x_{1}, …, x_{n}) or ¬σ(x_{1}, …, x_{n}) belongs to Γ for each such formula. An n-type Γ(x_{1}, …, x_{n}) of a theory T is principal if there is a formula θ(x_{1}, …, x_{n}) such that T ⊢ θ(x_{1}, …, x_{n}) → σ(x_{1}, …, x_{n}) for every σ ∈ Γ. In this case we say that θ(x_{1}, …, x_{n}) is a complete formula that generates Γ.

Definition 3.2 A model A of a theory T in the language L is a prime model of T if it can be elementarily embedded into every model of T. A is atomic if every n-tuple of elements from A satisfies a complete formula θ(x_{1}, …, x_{n}) of L. (Each of these models is unique (up to isomorphism) if it exists.)

The notions of prime and atomic coincide for countable models and so we motivate our characterization of decidable prime models by two classical characterizations.

Theorem 3.3 A complete theory T in a language L has a prime model if and only if every formula of L consistent with T is a member of a principal type over T.

Theorem 3.4 A complete theory T in a language L has an atomic model if and only if every formula of L consistent with T can be extended to a complete formula.

As the notions of atomic and prime coincide (for countable models), each of these theorems provides a characterization of the theories with prime models. We now consider what might be the appropriate effective versions of these theorems. In one direction, note that every type realized in a prime model of T is principal and all principal types are realized in every model of T. Thus, if T has a decidable prime model, not only is every formula consistent with T a member of a principal type (and so completable) but there is a uniformly computable list of these principal types given by the ones realized in the decidable prime model.

The classical theorems at first glance suggest that this condition might be sufficient. We should use this list of computable types to construct the model. However, an additional possible uniformity is suggested by each classical characterization. The characterization of prime models suggests that we might need to be able to go uniformly effectively from formulas to (indices for) principal types containing them. The characterization of atomic models suggests that one might need to be able to go uniformly effectively from formulas to generating formulas for the principal types containing them. Although the two classical versions are equivalent these two effective versions are not. The first is clearly necessary as given a formula ψ consistent with T and a decidable prime model A we can computably find an n-tuple of elements of A satisfying ψ. The set of formulas satisfied by this n-tuple A is then a computable principal type containing ψ. It turns out that this condition is also sufficient. The second condition clearly implies the first and so is sufficient but not, as it turns out, necessary.

Theorem 3.5 (Harrington [1974]; Goncharov and Nurtazin [1973]) A complete decidable theory T has a decidable prime model if and only if there is a computable function taking each formula to (an index for) a computable principal type containing it.

Proof. We construct the desired model by a priority argument reminiscent of that for the Sacks splitting theorem for computably enumerable sets [1963] but instead producing a Henkin construction that restricts the types realized to the principal ones.

Let σ_{e} list the formulas of L_{c} the language of T extended by new constants c_{i}. We construct in stages a sequence of finite sets Ψ_{s}(c_{1}, …, c_{n_{s}}) of sentences consistent with T with union Ψ as in the proof of Theorem 2.2. Again we let ψ_{s} = ∧Ψ_{s}. At each stage s of the construction Γ_{e,s} will be a principal e-type containing the formula ∃y_{e+1}, …, ∃y_{n_{s}}ψ_{s}(x_{1}, …, x_{e}, y_{e+1}, …, y_{n_{s}}). Our goal is to satisfy the requirements P_{e} of Theorem 2.2 as well as new ones Q_{e} that guarantee that the model constructed is prime by making sure that only principal types are realized. We satisfy Q_{e} by making sure that Γ_{e,s} is eventually constant and so that [c_{1}], … [c_{n}] satisfies the principal type Γ_{e}(= lim_{s} Γ_{e,s}). (We denote the equivalence class of c_{i} in the model built from the constants as in Theorem 2.2 by [c_{i}].)

• P_{e} : σ_{e} ∈ Ψ or ¬σ_{e} ∈ Ψ and if σ_{e} is of the form ∃xθ(x) and in Ψ then θ(c_{i}) ∈ Ψ for some i.

• Q_{e} : ⟨[c_{1}], … [c_{e}]⟩ realizes a principal type Γ_{e} = lim_{s} Γ_{e,s}.

Construction: At stage s, if only one of σ_{s} and ¬σ_{s} is consistent with T ∪ Ψ_{s} put it into Ψ_{s+1}. Suppose it is ρ that is put into Ψ_{s+1} and so T ⊢ ψ_{s} → ρ. As ∃y_{e+1}, …, ∃y_{n_{s}}ψ_{s}(x_{1}, …, x_{e}, y_{e+1}, …, y_{n_{s}}) is in Γ_{e,s} which is a complete type over T, and T ⊢ ψ_{s} → ρ, ∃y_{e+1}, …, ∃y_{n_{s+1}}ψ_{s+1}(x_{1}, …, x_{e}, y_{e+1}, …, y_{n_{s+1}}) is also in Γ_{e,s}. So we can let Γ_{e,s+1} be Γ_{e,s} for all e. If both σ_{s} and ¬σ_{s} are consistent with T ∪ Ψ_{s}, the problem is that adding σ_{s} (or ¬σ_{s}) to Ψ_{s} to form Ψ_{s+1} may make ∃y_{e+1}, …, ∃y_{n_{s+1}}ψ_{s}(x_{1}, …, x_{e}, y_{e+1}, …, y_{n_{s+1}}) not be a member of Γ_{e,s} for various numbers e. This would force us to change our choice of the type realized by ⟨[c_{1}], …, [c_{e}]⟩ and so make Γ_{e,s+1} ≠ Γ_{e,s}. We view this as an injury to requirement Q_{e} (which requires that Γ_{e,s} eventually stabilize). As in the Sacks splitting theorem we act so as to minimize the priority of the first requirement injured.

More precisely, we let ψ_{s+1}^{0} be ψ_{s}∧σ_{s} and ψ_{s+1}^{1} be ψ_{s}∧¬σ_{s}. We let e_{i,s} (for i = 0, 1) be the least e ≤ s such that ∃y_{e+1}, …, ∃y_{n_{s+1}}ψ_{s+1}^{i}(x_{1}, …, x_{e}, y_{e+1}, …, y_{n_{s+1}}) is not in Γ_{e,s}. (If none exists, e_{i,s} = s.) If e_{0,s} ≤ e_{1,s} let ψ_{s+1} = ψ_{s+1}^{1} and otherwise let ψ_{s+1} = ψ_{s+1}^{0}. Let e_{s} = min{e_{0,s}, e_{1,s}}. For e ≤ e_{s} we can let Γ_{e,s+1} = Γ_{e,s} as for such e, ∃y_{e+1}, …, ∃y_{n_{s+1}}ψ_{s+1}(x_{1}, …, x_{e}, y_{e+1}, …, y_{n_{s+1}}) ∈ Γ_{e,s}. For e > e_{s} we redefine Γ_{e,s+1} as the first in our uniformly computable list of principal types which contains ∃y_{e+1}, …, ∃y_{n_{s}+1}ψ_{s+1}(x_{1}, …, x_{e}, y_{e+1}, …, y_{n_{s}+1}).

If we have put ∃xθ(x) into Ψ, we put θ(c_{i}) in as well for some unused c_{i}. This clearly does not require any change in the Γ_{e,s+1} already defined.

Verifications: As T is decidable and the types on our list are uniformly computable, the construction is clearly computable. We clearly satisfy the P_{e} requirements and so construct a decidable model M as in Theorem 2.2. As all sentences σ_{i} involving only c_{1}, …, c_{e} that are put into Ψ_{s} at stage s belong to the principal type Γ_{e,s}, if we can show that lim_{s} Γ_{e,s} exists for each e (and is say Γ_{e}) then we will have shown that, in M, ⟨[c_{1}], … [c_{e}]⟩ realizes the principal type Γ_{e} as required to guarantee that M is a prime model of T.

We prove by induction on e that there is a stage t_{e} such that e_{s} > e for all s ≥ t_{e} and so Γ_{e,s} = Γ_{e,t_{e}} for all s > t_{e}. Suppose that t_{e−1} exists. We need to show that e_{s} is greater than e for all sufficiently large s. Now, by the definition of t_{e−1}, e ≤ e_{s} for every s > t_{e−1} and so by the choice of Ψ_{s+1} in the construction, Γ_{e,s} = Γ_{e,t_{e}} = Γ_{e} for all s > t_{e}. As Γ_{e} is principal, some σ(x_{1}, …, x_{e}) is a generator and so by some stage t ≥ t_{e−1} we have added σ to Ψ_{t}. We claim that e_{s} > e for every s > t. Consider σ_{s} for any s > t. The only way e_{s} could be e is if both σ_{s} and ¬σ_{s} are consistent with T ∪ Ψ_{s} but ∃y_{e+1}, …, ∃y_{n_{s+1}}ψ_{s+1}^{i}(x_{1}, …, x_{e}, y_{e+1}, …, y_{n_{s+1}}) is not in Γ_{e,s} for i = 0 or 1. As ∃y_{e+1}, …, ∃y_{n_{s+1}}ψ_{s}(x_{1}, …, x_{e}, y_{e+1}, …, y_{n_{s+1}}) → σ and σ is complete this would mean that

∃y_{e+1}, …, ∃y_{n_{s+1}}ψ_{s}(x_{1}, …, x_{e}, y_{e+1}, …, y_{n_{s+1}}) →

¬∃y_{e+1}, …, ∃y_{n_{s+1}}σ_{s}(x_{1}, …, x_{e}, y_{e+1}, …, y_{n_{s+1}})

or that ∃y_{e+1}, …, ∃y_{n_{s+1}}ψ_{s}(x_{1}, …, x_{e}, y_{e+1}, …, y_{n_{s+1}}) →

¬∃y_{e+1}, …, ∃y_{n_{s+1}}¬σ_{s}(x_{1}, …, x_{e}, y_{e+1}, …, y_{n_{s+1}})

so that σ_{s} or ¬σ_{s}, respectively, would be inconsistent with Ψ_{s} contrary to our assumption. Thus t is the required stage t_{e}. □

We finish this section with an alternative version of Theorem 3.5 and some remarks about various uniformity conditions.

Corollary 3.6 A complete decidable theory T has a decidable prime model if and only if T has a prime model and the set of all principal types of T is uniformly computable.

Proof. The only if direction of this Corollary is clearly implied by the Theorem. Suppose then that T has a prime model and the set of principal types of T is uniformly computable. As T has a prime model, every formula ψ is a member of a principal type and so the search among those in the given set for one containing ψ terminates and provides the computable function required in the theorem. □

The effective uniformity in the listing of the computable principal types is necessary as an explicit hypothesis:

Theorem 3.7 (Millar[1978]) There is a complete decidable theory T all of whose types are computable with a prime model but no decidable (or even computable) one.

Finally, we show that the possible alternate version of Theorem 3.5 that asks for a computable way to go from a formula to a completion is false and so “uniformly atomic” is stronger than “uniformly prime” even for decidable ℵ_{1}-categor-ical theories.

Proposition 3.8 There is a (complete) decidable ℵ_{1}-categorical theory T with a decidable prime model but with no computable function taking formulas to complete extensions.

Proof. The language of T has infinitely many unary predicates R_{i}. The axioms of T say that the cardinality of each R_{i} is exactly 2 and that R_{i} and R_{j} are disjoint for distinct i and j except for some designated triples ⟨i, j, k⟩ such that R_{k} consists of one element from each of R_{i} and R_{j}. Moreover, no two distinct designated triples have any entry in common. The actual list of axioms for T is thus determined by the list of designated triples. This list will be defined recursively to diagonalize against each possible computable partial function θ_{e} which might be a candidate for a function taking formulas to complete extensions. Thus T will be axiomatizable. It is also ℵ_{1}-categorical. (The part of the model consisting of elements in any R_{i} is uniquely determined by the axioms. The rest just consists of ℵ_{1} many elements not in any R_{i}.) Thus T is complete and decidable.

The list of designated triples is effectively enumerated in increasing order (and so is computable) by waiting to diagonalize each θ_{i} at the formula R_{2i}(x). If θ_{i}(R_{2i}(x)) converges at stage s, we choose j, k larger than any number mentioned already and designate the triple ⟨2i, 2j + 1, 2k + 1⟩. In particular, if θ_{i}(R_{2i}(x)) is the generating formula θ(x) (which implies R_{2i}(x)) then θ cannot mention R_{2k+1}. We claim that T can prove neither that θ(x) implies R_{2k+1}(x) nor that it implies ¬R_{2k+1}(x) and so θ_{i} is not a function taking formulas to complete extensions. To see that no information about R_{2k+1}(x) can be implied by θ(x) consider the theory T′ gotten by restricting T to the language L′ which is L without the predicate R_{2k+1}. T′ is clearly also ℵ_{1}-categorical and consistent with θ(x). Let A be a model of T′ and a an element realizing θ(x). Let b be the other element of R_{2i} in A and c and d the elements of R_{2j+1}. ( R_{2i} and R_{2j+1} are disjoint by construction.) We can easily expand A to a model of T by interpreting R_{2k+1} as either {a, c} or {b, d}. Thus θ(x) cannot imply either R_{2k+1}(x) or ¬R_{2k+1}(x). □

4. Saturated Models and the Number of Decidable Models

Definition 4.1 A model A of a theory T in the language L is a saturated model of T if it realizes every type of T with finitely many parameters from A. (If it exists, the saturated model of T is unique.)

The characterization of decidable theories with decidable saturated models is somewhat easier than for prime ones.

Theorem 4.2 (Morley [1976], Millar [1978], Goncharov [1978a]) A decidable theory T has a decidable saturated model if and only if the types of T are uniformly computable.

Proof sketch. If T has a decidable saturated model A then the types of T are uniformly computable as we can simply list the n-tuples from A and, for each of them the set of formulas it satisfies. For the other direction, we can use the uniformly computable list of types to do an effective Henkin construction. As the construction proceeds, we designate new constants to realize each potential type over previously introduced constants. As all the potential types over new constants are given uniformly computably as restrictions to a subset of their free variable of ones on our given list this procedure can be effectively organized. Roughly speaking, the plan is to continue to make the designated constants realize the appropriate type until an inconsistency is reached. We can check for inconsistencies with previously assigned types since they are all uniformly computable. We use a priority ordering to guarantee that, despite the need to cancel attempts at realizing certain potential types, each actual type over the constants introduced is in fact realized. Thus the model constructed is saturated as required. □

By Millar [1978], the explicit assumption of uniformity is necessary even if one assumes that the decidable theory T has a saturated model and all its types are computable. Millar [1978, p. 63] suggests that the proof of this results can be modified to show that there is no connection between the decidability of the saturated and prime models (when both exist). We now show that, in fact, if there is a decidable saturated model then there is a decidable prime model.

Proposition 4.3 (Ershov [1980, 381-382], see also Goncharov [1997, Theorem 3.4.4]) If a complete theory T has a decidable saturated model then it has a decidable prime model.

Proof. As T has a decidable model it is itself decidable by Corollary 2.4. As it has a decidable saturated model, Theorem 4.2 gives us a uniformly computable list Γ_{e} of all the types of T. By Theorem 3.5, it suffices to prove that, given any formula ϕ consistent with T, we can go effectively to a principal type Γ containing ϕ. We begin with the first type Γ_{n_{0}} on our list containing ϕ = ϕ_{0}. We proceed recursively to extend ϕ to ϕ_{i} and define a type Γ_{n_{i}} containing ϕ_{i}. Given ϕ_{i}, Γ_{n_{i}} and σ_{i} (from the list of all formulas with the same number of free variables as ϕ), we ask if both σ_{i} and ¬σ_{i} are consistent with T ∪ {ϕ_{i}}. If not, ϕ_{i+1} = ϕ_{i} and n_{i+1} = n_{i}. If so, we find the first e_{0} and e_{1} such that ϕ_{i} ∧ σ_{i} ∈ Γ_{e_{0}} and ϕ_{i} ∧ ¬σ_{i} ∈ Γ_{e_{1}}, respectively. We let n_{i+1} be the larger of e_{0} and e_{1} and let ϕ_{i+1} be ϕ_{i} ∧ σ_{i} or ϕ_{i} ∧ ¬σ_{i} accordingly. It is clear that the sequence n_{i} is nondecreasing as at step i of the construction if e_{0} and e_{1} are defined then one of them is n_{i} and we always take the larger. As this procedure is effective, {ϕ_{i}|i ∈ ω} generates a computable type Γ containing ϕ. If n_{i} is not eventually constant, Γ would be a type of T not equal to any Γ_{e} for a contradiction. Once n_{i} has stabilized say at n we can define e_{0} and e_{1} at only finitely many stages s as each time we do so we extend ϕ_{s} and eliminate one possible Γ_{j} for j < n from future consideration. Thus ϕ_{i} also eventually stabilizes say at ϕ_{e}. It is now clear that ϕ_{e} generates the type Γ_{n} which is therefore the required principal type containing ϕ. □

We now see what the proof of Vaught’s theorem that a complete theory cannot have exactly two models gives us.

Corollary 4.4 If a complete but not ℵ_{0}-categorical theory T has a decidable saturated model then it has at least three decidable models.

Proof. Let A be a decidable saturated model of T. By Proposition 4.3, T has a decidable prime model B. As T is not ℵ_{0}-categorical, the decidable saturated model A of T is not a prime model and so A and B are not isomorphic. Thus A realizes a nonprincipal (but computable) type Γ(\overline{x}). A can clearly be expanded to a saturated model of T ∪ Γ(\overline{c}) by properly interpreting the constants \overline{c} and so T ∪ Γ(\overline{c}) has a decidable saturated model and hence a decidable prime model C by Proposition 4.3. Of course, the restriction of C is a decidable model of T. As in the proof of Vaught’s theorem (as in Chang and Keisler [1990, Theorem 2.3.15]), this model cannot be isomorphic to either A or B. □

On the other hand, if a decidable theory T has no decidable prime model (and so no decidable saturated model) then it has infinitely many decidable prime models. To see this, we quote a simple case of Millar’s effective omitting types theorem.

Theorem 4.5 (Millar [1983]) If T is a decidable theory and {Γ_{i}|i < n} a finite set of computable nonprincipal types of T then there is a decidable model of T omitting every (i.e. not realizing any) Γ_{i}.

Corollary 4.6 If a decidable theory T does not have a decidable prime model then T has infinitely many decidable models.

Proof. By Theorem 2.2, T has a decidable model A. As A is not a prime model it realizes some nonprincipal type Γ_{1}. By Theorem 4.5, there is a decidable model A_{1} of T omitting Γ_{1}. As A_{1}is not prime, it realizes a nonprincipal type Γ_{2} distinct from Γ_{1} by construction. We now get a decidable A_{2} omitting both Γ_{1} and Γ_{2}. Continuing in this way we get an infinite sequence Γ_{i} of computable nonprincipal types of T and decidable nonisomorphic models A_{i} of T as required. (Each A_{i} realizes Γ_{i+1} but not Γ_{j} for any j ≤ i.) □

Another variation on the question of how many decidable models a decidable theory can have asks when is every model of T decidably presentable. One obvious necessary condition is that all types in T are computable. (Every type is realized in some model and only computable types can be realized in a decidable model.) Thus, in particular, T can have only countably many types. This condition is not sufficient and the problem remains open in general. There are a couple of partial answers. The answer is simple for ℵ_{0}-categorical theories and is supplied by Proposition 2.5. The nicest result is for ℵ_{1}-categorical theories to which we now turn.

5. ℵ_{1}-Categorical Theories

If a theory T is ℵ_{1}-categorical (and so complete) but not ℵ_{0}-categorical then the Baldwin-Lachlan theorem [1971] supplies us with a full classification of the models of T in terms of a well defined notion of dimension. There are countably many models A_{i} of T and they are arranged in a liner order of type ω + 1 with respect to elementary embedding ascending with increasing dimension:

A_{0} ⪯ A_{1} ⪯ A_{2} ⪯ … ⪯ A_{n} ⪯ … ⪯ A_{∞}.

A_{0}, the model of dimension zero is the prime model of T and A_{∞}, the unique model of infinite dimension, is the saturated model of T. The model A_{i} for i > 0 is the model of dimension i.

The classic example of an ℵ_{1} but not ℵ_{0}- categorical theory is ACF_{0}. Here the dimension of a model is its transcendence degree over the prime field ℚ. A_{0}, the prime model, is the algebraic closure of ℚ. A_{∞}, the saturated model, is the algebraic closure of the rationals extended by infinitely many transcendental elements. Each A_{i} for i > 0 is the algebraic closure of ℚ extended by i many transcendentals.

The general problem we wish to address is the following:

Question 5.1 If T is ℵ_{1} but not ℵ_{0}-categorical theory when (and which of) its models are decidably or computably presentable?

5.1 Decidable Models of ℵ_{1}-Categorical Theories

Of course, if T is ℵ_{1}-categorical and so complete, it has a decidable model if and only if it is itself decidable (Theorem 2.4). Actually, the decidability of T is enough to guarantee that every model is decidably presentable:

Theorem 5.2 (Harrington[1974], Khisamiev [1974]) If T is ℵ_{1}-categorical and decidable then every model of T is decidably presentable.

Proof. We first use the results of Baldwin and Lachlan [1971] to show that we can reduce the problem to that of the existence of decidable prime models for a decidable theory T. (All the model theoretic facts we cite in this proof can be found in Baldwin and Lachlan [1971].)

As T is ℵ_{1}-categorical, there is a principal n-type Γ(x_{1}, …, x_{n}) such that T′ = T ∪ Γ(c_{1}, …, c_{n}) (with c_{i} new constants) has a strongly minimal formula, i.e. a formula ϕ(x) of L′ (the language L of T expanded by new constants c_{i}) such that for every model A of T′ and every formula ψ(x) of L′, exactly one of {a ∈ A|A ⊧ ϕ(a) ∧ ψ(a)} and {a ∈ A|A ⊧ ϕ(a) ∧ ¬ψ(a)} is finite. Of course, T′ is ℵ_{1}-categorical. Note that as T is decidable and Γ is principal, T′ is also decidable (T′ ⊢ ϕ ⇔ ϕ ∈ Γ ⇔ T ⊢ θ → ϕ where θ is a generator of Γ). As all models of T can be extended to ones of T′, we can assume for the proof of our theorem that T has a strongly minimal formula ϕ.

Now each model of an ℵ_{1}-categorical theory T with a strongly minimal formula ϕ is the prime model of an extension T′ of T by constants d_{i} satisfying a type Δ which says that ϕ(d_{i}) holds for each i and that the d_{i} are algebraically independent, i.e. there is no formula ψ(x, \overline{y}) ∈ Δ such that for some n, ∃^{≤n}x(ϕ(x) ∧ ψ(x, \overline{y})) ∈ Δ. (In fact, the cardinality of the set of d_{i} is the dimension of the model and uniquely determines it.) Again T′ is clearly ℵ_{1}-categorical. We must verify that it is also decidable, i.e. Δ is computable. We prove by induction on the number n of d_{i} that the corresponding types Δ_{n} and theories T_{n} = T ∪ Δ_{n}(d_{1}, …, d_{n}) are uniformly decidable. (They are complete by definition.) For n + 1, consider any formula ψ(x, d_{1}, …, d_{n}). In each model A of T_{n} exactly one of {a ∈ A|A ⊧ ϕ(a) ∧ ψ(a, d_{1}, …, d_{n})} and {a ∈ A|A ⊧ ϕ(a) ∧ ¬ψ(a, d_{1}, …, d_{n})} is finite by the strong minimality of ϕ. By compactness, there is then an m ∈ ℕ such that T_{n} ⊢ ∃^{≤m}x(ϕ(x) ∧ ψ(x, \overline{d})) or T_{n} ⊢ ∃^{≤m}x(ϕ(x) ∧ ¬ψ(x, \overline{d})). As T_{n} is decidable, we can search for and find such an m for ψ or ¬ψ. The other is in Δ, i.e. if T_{n} ⊢ ∃^{≤m}x(ϕ(x)∧ψ(x, \overline{d})) then ¬ψ(x, \overline{d}) ∈ Δ and if T_{n} ⊢ ∃^{≤m}x(ϕ(x)∧¬ψ(x, \overline{d})) then ψ(x, \overline{d}) ∈ Δ. Thus each T_{n} and T_{∞} = ∪T_{n} is decidable and the models of T are precisely the prime models of these theories. To prove our theorem it therefore suffices to show that each of these theories has a decidable prime model.

By Theorem 3.5, it suffices to show that if T is a decidable ℵ_{1}-categorical theory with a strongly minimal formula ψ then there is a computable function taking any formula σ(\overline{x}) to a computable principal type Γ_{σ} containing σ.

Given σ, we construct a computable type Γ in stages e by starting with σ and adding on each σ_{e} in turn if it is consistent with what we have put in Γ so far and, if σ_{e} is ∃y(ψ(y) ∧ θ(y, \overline{x})), we also add in ∃y(ψ(y) ∧ θ(y, \overline{x}) ∧ ϕ(y)) for some algebraic ϕ, i.e. one such that T ⊢ ∃^{≤n}y(ψ(y) ∧ ϕ(y)) for some n ∈ ω. Of course, if σ_{e} is not consistent with what we have so far we add on ¬σ_{e}. The point here is that if ∃y(ψ(y) ∧ θ(y, \overline{x})) is consistent with what we have so far then the formula gotten by adding it on is realized in the prime model of T say by \overline{c}. Now that model has only algebraic realizations of ψ and so whatever element witnessed ∃y(ψ(y)∧θ(y, \overline{c})) is algebraic and so also satisfies some algebraic formula ϕ. Thus ∃y(ψ(y) ∧ θ(y, \overline{x}) ∧ ϕ(y)) can be consistently added on as desired.

We claim that Γ is principal and so the required Γ_{σ}. Consider the prime model A of T ∪ Γ(\overline{c}) and any a ∈ A such that A ⊧ ψ(a). As A is a prime model of T ∪ Γ(\overline{c}), a realizes a principal type over T ∪ Γ(\overline{c}) generated say by θ(y, \overline{c}). If a is not algebraic then for every formula ϕ and every n ∈ ω, T ∪ Γ(\overline{c}) ⊢ θ(y, \overline{c}) → [ϕ(y) → ¬∃^{≤n}y(ψ(y) ∧ ϕ(y))]. On the other hand, as A ⊧ ψ(a) ∧ θ(a, \overline{c}), ∃y(ψ(y)∧θ(y, \overline{x})) ∈ Γ and so by construction ∃y(ψ(y)∧θ(y, \overline{x})∧ϕ(y)) ∈ Γ for some ϕ such that T ⊢ ∃^{≤n}y(ψ(y) ∧ ϕ(y)) for some n for a contradiction. Thus A has only algebraic solutions of ψ, i.e. it is the model of dimension 0, and so A is actually the prime model of T. As Γ is realized in A, it must be principal over T as required.

(This last argument is attributed to Lachlan in Harrington [1974]. Harrington’s own proof is also instructive. It begins with the observation that the function taking a formula σ to its rank as defined in Baldwin [1973] can be seen to be a computable map from formulas into ℕ by the arguments presented in that paper. Thus, given a formula σ consistent with T, we may computably define a type Γ = ∪Γ_{e} containing σ by putting in, for each e in turn, either σ_{e} or ¬σ_{e} so as to always preserve consistency and to reduce the rank of ⋀ Γ_{e} if possible. Eventually, the rank must stabilize and so we produce a principal type Γ containing σ.) □

5.2 Computable Models

We now turn to the question of which models of an ℵ_{1}-categorical but not ℵ_{0}- categorical theory T are computably presentable if T is not decidable. It is easy to find such a theory with no computable models by coding a noncomputable set S into every model. (For example, extend ACF_{0} by adding on new unary predicates P_{i} and, for each i ∈ ω, axioms ∀x(P_{i}(x) → x = 0) and P_{i}(0) if i ∈ S but ¬P_{i}(0) if i ∉ S.) Thus the question is, if T has a computable but no decidable model, which of the models A_{i} of T can or cannot be computable. Only a few facts are known.

Theorem 5.3 (Goncharov [1978], Kudaibergenov [1980]) For every n ∈ ℕ there is an ℵ_{1}-categorical but not ℵ_{0}-categorical theory T such that A_{0}, …, A_{n} are all computably presentable but not A_{i} for i > n.

Proof. Fix n ∈ ℕ. The language for the required theory T will consist of a unary predicate P_{k} and an n-ary predicate R_{k} for each k ∈ ℕ. The axioms for T will code a computably enumerable but not computable set B = ∪B_{s} into each model of dimension greater than n while maintaining the possibility that the models of dimension less than or equal to n are computably presentable. Axioms:

• The P_{k} are nested downward with respect to k and exactly one element drops

out at each k, i.e. for each k ∈ ℕ we have the following axioms: *∀x(P_{k+1}(x) → P_{k}(x)) *∃!x(P_{k}(x) ∧ ¬P_{k+1}(x))

• For each k ∈ ℕ we wish to require that

R_{k}(x_{1}, …, x_{n}) ⇔ ⋀{x_{i} ≠ x_{j}|i ≠ j} ∧ ∃s(k ∈ B_{s} ∧ x_{1}, …, x_{n} ∈ P_{s}).

We enforce this requirement by the following axioms:

*R_{k}(x_{1}, …, x_{n}) → x_{i} ≠ x_{j} for i ≠ j.

*For each s ∈ ℕ and k ∈ B_{s} :

⋀{x_{i} ≠ x_{j}|i ≠ j} ∧ x_{1}, …, x_{n} ∈ P_{s} → R_{k}(x_{1}, …, x_{n}).

*For each s ∈ ℕ and k ∉ B_{s} : ⋁{x_{i} ∉ P_{s}|i ≤ n} → ¬R_{k}(x_{1}, …, x_{n}).

Verifications: It is easy to see that the cardinality of ∩P_{s}^{A} uniquely determines the isomorphism type of any model A of T and that all models A of size ℵ_{1} have ℵ_{1} many elements in ∩P_{s}^{A}. Thus T is ℵ_{1}-categorical. Indeed, the cardinality of ∩P_{s}^{A} is the dimension of A.

We claim that a model A of T is computably presentable if and only if there are fewer than n distinct elements in ∩P_{s}^{A}. For one direction, suppose that there are distinct c_{1}, …, c_{n} in ∩P_{s}^{A}. In that case, k ∈ B ⇔ A ⊧ R_{k}(c_{1}, …, c_{n}) and so A cannot be computably presentable as B is not computable.

For the other direction, we wish to construct a computable model A of T with m < n many elements c_{1}, …, c_{m}, in ∩P_{s}^{A}. We let the other elements of the desired model be the natural numbers and we put i in P_{k} if and only if i ≥ k. We now only have to computably define the predicates R_{k}. Given distinct elements a_{1}, …, a_{n} from A, not all of them are from among the c_{i} and so we can effectively find an s and indeed the smallest s such that one of them is not in P_{s}. We then let R_{k}(a_{1}, …, a_{n}) hold if and only if k ∈ B_{s−1}. This clearly defines a computable model A of T with | ∩ P_{s}^{A}| = m as required. □

Thus any initial segment of the models of T can be the computably presentable ones. The obvious questions arise as to what else is possible.

Question 5.4 Which subsets of ω + 1 can be the set of computably presentable models of an ℵ_{1}-categorical but not ℵ_{0}-categorical theory T with a computable model? In particular, must the prime model always be computably presentable? Must the saturated model be computably presentable if all the others are?

The following theorem answers the two specific questions asked. All other instances of the general question are open.

Theorem 5.5 (Khoussainov, Nies and Shore [1997]) There are ℵ_{1}-categorical but not ℵ_{0}-categorical theories T_{1} and T_{2} such that

i)All models of T_{1} except the prime one are computably presentable. ii)All models of T_{2} except the saturated one are computably presentable.

Proof (For T_{1}). Given S ⊂ ω we construct a structure A_{S} of signature L = (P_{0}, P_{1}, P_{2}, …), where each P_{i} is a binary predicate symbol having the following properties:

• The theory T_{S} of the structure A_{S} is ℵ_{1}- but not ℵ_{0}–categorical and A_{S} is the prime model of T_{S}.

• Each nonprime model A of T_{S} has a computable presentation if and only if S is Σ_{2}^{0}.

• A computable prime model provides S with a certain recursion-theoretic property but there exists a Σ_{2}^{0}–set which does not have this property.

The building blocks of our structures A_{S} will be finite structures that we call n-cubes and now define by induction on n.

Definition 5.6 A 1–cube C_{1} is a structure ({a, b}, P_{0}) such that P_{0}(x, y) holds in C_{1} if and only if (x = a and y = b) or (y = a and x = b). Given two disjoint n-cubes we get an n + 1-cube as an expansion of their union by letting P_{n} be an isomorphism between the n-cubes. An ω–cube is an increasing union of n–cubes, n ∈ ω with signature (P_{0}, P_{1}, P_{2}, …)

Definition 5.7 If S ⊆ ω, A_{S} is the disjoint union of n-cubes for n ∈ S and T_{S} = T h(A_{S}).

Lemma 5.8 If S is infinite, then T_{S} is ℵ_{1}- but not ℵ_{0}–categorical and the model with no ω-cubes is its prime model.

Proof. It is easy to see that the model A_{S} satisfies the following conditions which are all expressible by a set of axioms in the language L:

1. ∀x∃yP_{0}(x, y) and for each n, P_{n} defines a partial one-to-one function. (We abuse notation by also denoting this partial function by P_{n}.)

2. For all n ≠ m and for all x, P_{n}(x) ≠ P_{m}(x).

3. For each n and for all x if P_{n}(x) is defined, then P_{0}(x), P_{1}(x), …, P_{n−1}(x) are also defined.

4. For all n, m and for all x if P_{n}(x) and P_{m}(P_{n}(x)) are defined, then P_{m}(P_{n}(x)) = P_{n}(P_{m}(x)).

5. For all k, n > n_{1} ≥ n_{2} ≥ … ≥ n_{k−1} ≥ n_{k}, ∀x(P_{n_{1}}(… (P_{n_{k}}(x) …) ≠ P_{n}(x)).

6. For each n ∈ ω, n ∈ S if and only if there exists exactly one n–cube which is not contained in an n + 1–cube.

Let M be a model which satisfies all the above statements. For each n ∈ S, M must have an n–cube which is not contained in an n + 1–cube. If an x ∈ M does not belong to any n–cube for n ∈ S, then x is in an ω–cube. Thus any two models which satisfy this list of axioms are isomorphic if and only if they have the same number of ω–cubes. In particular, if M_{1} and M_{2} are models of T_{S} of cardinality ℵ_{1}, each has ℵ_{1} many ω–cubes (as each cube is countable). Thus M_{1} and M_{2} are isomorphic and T_{S} is an ℵ_{1}- but not ℵ_{0}–categorical theory. It is clear that the prime model is the one with no ω-cubes. □

Lemma 5.9 Each nonprime model of T_{S} is computably presentable if and only if S is Σ_{2}^{0}.

Proof. If M is a model of T_{S}, s ∈ S if and only if M ⊧ ∃x∃y∀z(P_{s}(x, y)& ¬P_{s+1}(x, z)). Thus if M is computably presentable S is Σ_{2}^{0}. For the other direction, note that it suffices to construct a computable model M_{1} with one ωcube when S ∈ Σ_{2}^{0}. (We can computably add on more ω-cubes as desired.) We build M by putting in an n-cube when, according to the Σ_{2}^{0} representation of S as {n|∃x∀yH(x, y, n)}, we seem to have a witness x that n ∈ S. When the witness fails, we merge this n-cube into the ω-cube that we are building. More formally, at stage 0 we start to build a substructure B that will be an m-cube for some m at every stage s and will at the end of the construction be an ω-cube. At stage s, we first put into M an n-cube for each n < s for which we do not have one and associate the cube with the first number x that has not yet been associated with n. Then, we merge B and the existing n-cubes for those n < s for which there is a y < s such that H(x, y, n) fails for the x currently associated with n into an m-cube for some m larger than any number yet used in the construction. Clearly the substructure B becomes the only ω-cube of M. Moreover, for n ∈ ω, there is an n-cube in the final structure M if and only if ∃x∀yH(x, y, n), i.e. if and only if n ∈ S as required. □

We now provide the recursion theoretic property of S that is guaranteed by the existence of a computable prime model of T_{S} (but not by any of the other models being computably presentable).

Definition 5.10 A function f is limitwise monotonic if there exists a computable function ϕ(x, t) such that ϕ(x, t) ≤ ϕ(x, t + 1) for all x, t ∈ ω, lim_{t} ϕ(x, t) exists for every x ∈ ω and f(x) = lim_{t} ϕ(x, t).

Lemma 5.11 If the prime model of T_{S} is computably presentable then S is the range of a limitwise monotonic function.

Proof. Suppose M is a computable prime model of T_{S}. Define ϕ(x, s) for each x ∈ M and s ∈ ℕ as the largest n < s such that P_{n}(x, y) holds for some y < s. It is clear that ϕ(x, s) is monotonic in s. As every x ∈ M is in an n-cube for some n, ϕ(x, s) is equal to this n for all sufficiently large s. □

Lemma 5.12 There exists a Δ_{2}^{0} set A which is not the range of any limitwise monotonic function.

Proof. Let ϕ_{e}(x, t) be a list of all candidates for representations of limitwise monotonic functions f_{e}. At stage s we define a finite set A_{s} so that A(y) = lim_{s}A_{s}(y) exists for all y (and hence A is Δ_{2}^{0}). We also satisfy the following requirements to guarantee that A is not the range of a limitwise monotonic function.

R_{e} : If f_{e}(x) = lim_{t}ϕ_{e}(x, t) < ω for all x, then range(f_{e}) ≠ A.

The strategy to satisfy a single R_{e} works as follows: At stage s, pick a witness m_{e}, enumerate m_{e} into A (i.e. set A_{s}(m_{e}) = 1). Now R_{e} is satisfied (since m_{e} remains in A) unless at some later stage t_{0} we find an x such that ϕ_{e}(x, t_{0}) = m_{e}. If so, R_{e} ensures that A(ϕ_{e}(x, t)) = 0 for all t ≥ t_{0}. Thus, either f_{e}(x) ↑ or f_{e}(x) ↓ and f_{e}(x) ∉ A.

Keeping ϕ_{e}(x, t) out of A for all t ≥ t_{0} can conflict with a lower priority (i > e) requirement R_{i} since it maybe the case that m_{i} = ϕ_{e}(x, t′) for some t′ > t_{0}. However, if f_{e}(x) ↓, then from some point on there is only one number that R_{e} prevents from being a candidate for m_{i}. If f_{e}(x) ↑, then the restriction is transitory, i.e. as ϕ_{e}(x, t) is monotonic in t each candidate for m_{i} is eventually released and never prevented from being chosen as the final value of m_{i}.Thus each lower priority R_{i} will eventually be able to choose a witness m_{i} that it will never have to change because of the actions of R_{e}. In this way, every requirement can be satisfied by a typical finite injury priority argument. □

Proof sketch (For T_{2}). We take a Π_{2}^{0} set S defined by k ∈ S ⇔ ∀n∃mH(n, m, k) which is not Σ_{2}^{0}. (H is some computable predicate on ℕ^{3}.) We now code S into a computable structure A with unary predicates P_{i} and predicates R_{k,s} of arity k for i, k, s ∈ ℕ. The relevant properties of A that can be guaranteed by axioms in this language are as follows:

• The P_{i}^{A} form a descending chain of sets with one element dropping out at each i.

• The R_{k,s}^{A} code the approximation H(n, m, k) to k ∈ S by requiring that if j is least such that ∀n ≤ s∃m ≤ j(H(n, m, k)) and x_{1}, …, x_{k} ∈ P_{j} are distinct for i ≤ k then R_{k,s}(x_{1}, …, x_{k}) holds and not otherwise. (In particular, if k ∉ S then for some s_{0} we have axioms saying that R_{k,s}(x_{1}, …, x_{k}) does not hold for any s ≥ s_{0} and any x_{1}, …, x_{k}.)

The theory T_{S} of A_{S} is ℵ_{1}- but not ℵ_{0}-categorical with the dimension of a model A being once again determined by the cardinality of ∩P_{i}^{A}. The intuition is that the more elements there are in ∩P_{i}^{A} for a model A of T_{S}, the more of the Π_{2}^{0}- approximation to S that we can “recover” from the diagram of A. In particular, if A is the saturated model of T_{S}, ∩P_{i}^{A} is infinite and S is Σ_{2} in A: k ∈ S ⇔ ∃x_{1}, … x_{k} ∈ A[(∀i)(A ⊧ P_{i}(x_{1}) ∧ … P_{i}(x_{k}) ) ∧ (∀s)(A ⊧ R_{k,s}(x_{1}, … x_{k}))]. As S is not Σ_{2}^{0}, the saturated model of T_{S} is not computably presentable. For each t < ω, however, we can (nonuniformly) build a computable model A_{t} of T_{S} with t many elements in ∩P_{i}^{A_{t}}. The information needed is S ∩ (t + 1) and, for each k ≤ t which is not in S the least n for which there is no m such that H(n, m, k) holds. □

All the theorems in this subsection about computable models of ℵ_{1}-categorical theories use infinite signatures. Not too much is known about the existence of such structures and theories in finite signatures or for ones that are extensions of standard algebraic theories. One interesting example is Herwig, Lempp and Ziegler [1999] who have established Theorem 5.3 for n = 0 with T an extension of the theory of groups in the standard signature.

6. Computable Dimension and Categoricity

Until now we have taken the classical approach of identifying models up to classical isomorphism. However, it is not obvious that even two computable (or decidable) models that happen to be isomorphic should be identified when one is interested in effective procedures. There could well be (and indeed, as we shall see, there are) structures with presentations A and B such that the two presentations have different effective properties. For example, there are computable presentations of ⟨ℕ, ≤⟩ on which the successor function is not computable.

Proposition 6.1 There is a computable presentation A = ⟨A, ≤_{A}⟩ of ⟨ℕ, ≤⟩ such that the successor function on A is not computable.

Proof. A will consist of the even numbers in their usual order plus an infinite set of odd numbers determined and placed in the ordering by a procedure designed to guarantee that no computable function ϕ_{e} is the successor function on A. At stage s we check, for each e < s, if ϕ_{e}(2e) has converged at stage s and is equal to 2e + 2. If so we put 2s + 1 into A and place it between 2e and 2e + 2. It is obvious that A is computable and that ϕ_{e}(2e) is not the successor of 2e in A for any e. □

The natural approach to the issue raised by such examples is to identify structures or presentations only when there is a computable isomorphism between them. Of course, this only makes sense when the structures themselves are computable.

• Henceforth all structures will be computable.

Definition 6.2 A is computably isomorphic to B, A ≅_{c} B, if there is a computable f : A → B which is an isomorphism. We also say then that A and B are of the same computable isomorphism type.

Definition 6.3 The (computable) dimension of a structure A is number of its computable isomorphism types. A is computably categorical if its computable dimension is 1, i.e. every B isomorphic to A is computably isomorphic to A.

Note that in a computably categorical structure A every definable relation that is computable in any presentation of A is computable in every presentation of A and so for such structures the effectiveness of definable properties is independent of the presentation.

Example 6.4 ℚ (the rationals) with its usual linear order is computably categorical: 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.

Example 6.5 ℕ as a model or P A or indeed as a structure with only the successor function s(x) (given as x + 1 in the language of arithmetic) is computably categorical: Given any B isomorphic to ℕ, one defines the required computable f : ℕ → B by recursion. f(0) is the first element of B and if f(n) is defined as b ∈ B then f(n + 1) = s^{B}(b). However, it is easy to see from Proposition 6.1 that ⟨ℕ, ≤ ⟩ is not computably categorical. (If s is the successor function on ℕ and f : ℕ →A were a computable isomorphism into the A of Proposition 6.1, fsf^{−1} would be a computable successor function on A.)

Example 6.6 Every finitely generated structure is computably categorical by the natural generalization of the preceding argument for ⟨ℕ, s⟩.

Example 6.7 \overline{ℚ}, the algebraic closure of the rationals and so the prime model of ACF_{0}, is computably categorical but ℚ̃, the countable saturated model of ACF_{0} (i.e. the algebraic closure of the rationals extended by infinitely many transcendentals) has computable dimension ω (Corollary 6.12).

All of these examples have dimension 1 or ω but, actually, every n ≤ ω is possible.

Theorem 6.8 (Goncharov [1980a]) For each n, 1 ≤ n ≤ ω there is a structure of dimension n.

Goncharov uses a priority argument to construct families of uniformly computably enumerable sets with (in a precise sense) exactly n many distinct enumerations and then codes them into structures so as preserve the dimension. We will see other approaches to these results in Theorem 6.22 and Corollary 7.16. Although there are interesting codings of these families into familiar types of mathematics structures such as groups and rings (see §9), we do not know of any “natural” structures with dimension n for 1 < n < ω. Indeed, for many classes of structures it is possible to prove that they are computably categorical or have dimension ω. In most of these cases it is actually possible to characterize the structures that are computably categorical.

Theorem 6.9 (Goncharov [1973], LaRoche [1977], Remmel [1981], Goncharov and Dzgoev [1980]) A Boolean algebra is computably categorical if it has finitely many atoms. If not, it has dimension ω.

Theorem 6.10 (Remmel [1981a], Goncharov and Dzgoev [1980]) A linear order is computably categorical if it has only finitely many pairs of adjacent elements. If not, it has dimension ω.

We can deduce a similar result on algebraically closed fields from a general theorem about computable categoricity among decidable presentations of a structure.

Theorem 6.11 (Nurtazin [1974]) Suppose A is a decidable structure. If there are finitely many elements c̄ ∈ A such that (A, c̄) is the prime model of the theory T h(A, c̄) and the set of complete formulas of this theory is computable, then any two decidable presentations of A are computably isomorphic. On the other hand, if there are no such \overline{c}, then there are infinitely many decidable presentations of A no two of which are computably isomorphic.

Corollary 6.12 (Nurtazin [1974]; Metakides and Nerode [1979]) An algebraically closed field of finite transcendence degree over its prime field is computably categorical. One of infinite transcendence degree has dimension ω.

Proof. Let T be the theory of algebraically closed fields of characteristic 0. As T has quantifier elimination every computable model A of T is decidable. (Given a sentence with quantifiers (in the expanded language with constants for elements of A) find the quantifier free equivalent. Its truth can be decided by the computability of A. As T is ℵ_{1}-categorical every model A is the prime model of T′ = T ∪ Γ(\overline{c})∪Δ(\overline{d}) for a computable principal type Γ providing the theory with a strongly minimal formula and the type Δ of a sequence of transcendentals (independent elements) as described in the proof of Theorem 5.2. (Actually, for this particular T, Γ is not needed as it is already strongly minimal.) The sequence \overline{d} is finite if and only if the transcendence degree of A over its prime field is finite. In particular if the transcendence degree is infinite, there is no finite sequence as required and so A would have infinite computable dimension. On the other hand, if the sequence is actually finite, we can effectively decide if a given formula ϕ(\overline{d}, \overline{x}) is an atom. As in the proof of Theorem 5.2, we can go effectively to a computable principal type Γ of T′ containing ϕ(\overline{d}, \overline{x}). For this particular theory, however, we can enumerate the complete formulas. (In characteristic 0, they just say that (for some ordering of the x’s), each x in turn satisfies some irreducible polynomial over the previous ones.) We can thus find such a generating formula γ in Γ and then ask if ϕ → γ. If so ϕ is complete and not otherwise. (Metakides and Nerode [1979] give a direct proof of this Corollary.) □

An important program is thus to characterize or at least classify computably categorical structures and theories whose models are computably categorical. One major success along these lines is the characterization by Goncharov [1975] of computably categorical structures whose two quantifier theory is decidable in terms of Scott families.

Definition 6.13 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, i.e. prenex ones with only existential quantifiers, 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.

Definition 6.14 A structure A is n-decidable (for n ∈ ℕ) if the set of prenex sentences of T h(A, a)_{a∈A} with n − 1 alternations of quantifiers is computable. So, for example, A is 1-decidable if the set of prenex sentences of T h(A, a)_{a∈A} with either only existential or only universal quantifiers is decidable.

Proposition 6.15 If a structure A has a Scott family, then A 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}. 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_{0} = {(a_{0}^{1}, a_{0}^{2}), …, (a_{m−1}^{1}, a_{m−1}^{2})}.

Stage 2k>0. 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 in A_{1} 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}. Clearly, f is a computable isomorphism. □

Theorem 6.16 (Goncharov [1975]) If A is 2-decidable then it is computably categorical if and only if it has a Scott family.

Of course, the if direction of this Theorem follows from the preceding Proposition. For the other direction, one uses a priority argument to build a B and a Δ_{2}^{0} isomorphism between A and B. Attempts are made to make sure that no ϕ_{e} is an isomorphism between A and B. If one of the attempts fails, the construction builds a Scott family for A. (See Ash and Knight [1999] for the details of an ingenious but relatively simple proof.)

Note that the definition of computable categoricity is on its face a Π_{1}^{1} property. This theorem gives a Σ_{1}^{1} equivalent (having a Scott family). Actually, the property of having a Scott family can easily be seen to be arithmetic as the requirement for an isomorphism can be replaced by the existence of a set of finite partial isomorphisms with the back and forth property. Thus, for 2-decidable structures, Theorem 6.16 gives a characterization that is significantly simpler than the underlying definition of computable categoricity.

We now turn to the specific issue of persistence of computable categoricity under expansions by constants that will turn out to be a route into various results and examples of the sorts listed above. In particular, it will lead us to a proof that the existence of a Scott family is not necessary for computable categoricity.

6.1 Persistence of Computable Categoricity

Classically, it is an easy consequence of the Ryll-Nardzewski Theorem that having a countably categorical theory is persistent, i.e. preserved under expansions by finitely many constants.

Theorem 6.17 If T h(A), the theory of a structure A, is countably categorical then so is the theory of any expansion of A by finitely many constants.

The natural question for computable categoricity has been considered by Millar, Goncharov and others. It is posed as the Millar-Goncharov problem in Ershov and Goncharov [1986]:

Question 6.18 (Millar,Goncharov) Is computable categoricity persistent, i.e. if A is computably categorical is also every expansion of A by finitely many constants?

It is not hard to see that if a structure A has a Scott family ϕ_{i}(ā, x_{1}, …, x_{n_{i}}) then every expansion by finitely many constants c_{1}, … c_{m} also has one. We simply slightly modify the original Scott family. (Essentially, one replaces each formula ϕ_{i}(ā, x_{1}, …, x_{n_{i}}) by ϕ_{i}(ā, c_{1}, …, c_{m}, x_{1}, … x_{n_{i}−m}) and then lists only the satisfied formulas. Then, one can easily check that the sequence ψ_{0}, ψ_{1}, … is a Scott family for the expanded structure (A, c_{1}, …, c_{m}).) Thus Theorem 6.16 gives us an answer when A is 2-decidable.

Corollary 6.19 (Goncharov [1975]) If A is 2-decidable then the expansion of A by finitely many constants is also computably categorical.

Millar has improved this result by one quantifier by a quite different proof. So, roughly speaking, it suffices to be able to solve systems of equalities and inequalities.

Theorem 6.20 (Millar [1986]) If A is 1-decidable then the expansion of A by finitely many constants is also computably categorical.

Proof (Hirschfeldt). Suppose we are given A and B isomorphic, computably categorical and 1-decidable with ⟨A, a⟩ ≅ ⟨B, b⟩. We will build C via a Henkin construction, a sequence g_{s} of partial isomorphisms from C to B and, for each potential isomorphism Φ_{e} : C → A, a partial map h_{e} : C → B such that

• either there is an e such that h_{e} is total and h_{e}Φ_{e}^{−1} is an isomorphism from ⟨A, a⟩ to ⟨B, b⟩,

• or g = lim_{s} g_{s} exists and is an isomorphism from C to B but no Φ_{e} is an isomorphism from C to A.

As the second alternative contradicts the hypothesis that A is computably categorical, we will have the desired computable isomorphism between ⟨A, a⟩ and ⟨B, b⟩. In the construction we actually act, when we can, to guarantee that Φ_{e} is not an isomorphism from C to A (and so we do not have to worry about it). Thus we let R_{e} be the requirement that Φ_{e} is not an isomorphism from C to A. As the construction proceeds, we say that R_{e} is satisfied (or not) depending on whether we have a certain type of witness to Φ_{e}’s not being an isomorphism from C to A.

For convenience, we assume that the domain of each model considered here is ℕ. Let {θ_{n}}_{n∈ω} be an effective list of all atomic sentences in the language of A expanded by adding a constant i for each i ∈ ω. By θ_{n}^{0} and θ_{n}^{1} we mean ¬θ_{n} and θ_{n}, respectively.

For any conjunction Γ of literals containing no constant i for i > m and partial computable function Φ with computable domain, we let f(k) = n if Φ(k) ↓= n, f(k) = x_{k} if Φ(k) ↑, and denote by Γ[Φ] the formula ∃x_{0} ⋯ ∃x_{m}Γ(0/f(0), … …, m/f(m)). So, for example, if θ_{n} is the sentence P (0, 1, 2, 3) and Φ = {⟨1, 7⟩, ⟨3, 5⟩}, then θ_{n}^{1}[Φ] = ∃x_{0}∃x_{1}∃x_{2}∃x_{3}P (x_{0}, 7, x_{2}, 5), while, on the other hand, θ_{n}^{0}[Φ] = ∃x_{0}∃x_{1}∃x_{2}∃x_{3}¬P (x_{0}, 7, x_{2}, 5).

We note a few immediate consequences of this definition. In what follows, ε will always be either 0 or 1.

Proposition 6.21

1. If M ⊨ Γ[Φ] and Φ is an extension of Ψ then M ⊨ Γ[Ψ].

2. If M ⊨ Γ[Φ] and S ⊃ dom Φ then there is an extension Ψ of Φ with domain S such that M ⊨ Γ[Ψ].

3. If M ⊨ Γ[Φ] and M ⊨ ¬((Γ ∧ θ_{n}^{ε})[Φ]) then M ⊨ (Γ ∧ θ_{n}^{1−ε})[Φ].

4. Let a_{0}, …, a_{m} and b_{0}, …, b_{m} be two sequences of natural numbers. If M ⊨ ¬(Γ[{⟨n, a_{n}⟩ | n ≤ m}]) and N ⊨ Γ[{⟨n, b_{n}⟩ | n ≤ m}]) then ⟨M, a_{0}, …, a_{n}⟩ ≇ ⟨N , b_{0}, …, b_{n}⟩.

5. Suppose that Φ is total and surjective, dom Ψ = {0, …, r − 1}, M ⊨ θ[Φ ↾ r] and N ⊨ ¬(θ[Ψ]) for some literal θ. Then there is a total computable f which is the identity on {0, …, r − 1} such that M ⊨ θ[Φ ∘ f]. Let θ′ = ¬θ[f]. Then M ⊨ ¬(θ′[Φ]) and N ⊨ ¬((¬θ′)[Ψ]). □

We now describe our construction.

Construction. At each stage s, we define partial computable functions g_{s} and h_{i,s}, i ∈ ω.We also construct the atomic diagram Δ_{C} of C by adding on one of the literals θ_{s}^{0} or θ_{s}^{1} at each stage s. We use the following notations: Γ_{s} is the conjunction of all the literals in Δ_{C} at the end of stage s; z_{e,s} is the least number such that Φ_{e,s}(z_{e,s}) = a, if one exists, z_{e,s} = 0 otherwise; r_{e,s} = sup((⋃_{i<e} dom h_{i,s})∪{z_{i,s} | i ≤ e} ∪ {e}).

We say that a stage s is e-expansionary if Φ_{e,s} is injective, Φ_{e,s}(z_{e,s}) ↓= a, {0, …, r_{e,s}} ⊆ dom Φ_{e,s}, dom Φ_{e,s} ⊋ {0, …, sup(dom Φ_{e,s−1})}, and rng Φ_{e,s} ⊋ {0, …, sup(rng Φ_{e,s−1})}. (Thus, if there are infinitely many e-expansionary stages, Φ_{e} is total, injective, and surjective.)

We begin at s = 0 with Γ_{0} = ∅, g_{0} = ∅ and h_{e,0} = ∅ for each e ∈ ω. We assume by induction that B ⊨ Γ_{s}[g_{s}] and for each e ∈ ω, B ⊨ Γ_{s}[h_{e,s}]. At stage s + 1 we find the least e ≤ s, if any, such that R_{e} is not satisfied and one of the following conditions holds.

1. For some ε, B ⊨ (Γ_{s} ∧ θ_{s}^{ε})[g_{s}↾r_{e,s} + 1] and A ⊨ ¬((Γ_{s} ∧ θ_{s}^{ε})[Φ_{e,s}]) or B ⊨ ¬(Γ_{s} ∧ θ_{s}^{ε})[g_{s}↾r_{e,s} + 1] and A ⊨ ((Γ_{s} ∧ θ_{s}^{ε})[Φ_{e,s}]).

2. Not 1 and for some ε, (a) B ⊨ (Γ_{s} ∧ θ_{s}^{ε})[g_{s} ↾r_{e,s} + 1],

(b) B ⊨ (Γ_{s} ∧ θ_{s}^{ε})[h_{e,s}], and

(c) s + 1 is an e-expansionary stage.

3. Not (1 or 2 a and b), and for some ε, (a) B ⊨ (Γ_{s} ∧ θ_{s}^{ε})[g_{s} ↾ r_{e,s} + 1],

(b) B ⊨ ¬((Γ_{s} ∧ θ_{s}^{1−ε})[g_{s} ↾ r_{e,s} + 1]), and

(c) B ⊨ ¬((Γ_{s} ∧ θ_{s}^{ε})[h_{e,s}]).

If such an e exists, we say that e is active at stage s + 1. Let r = r_{e,s} + 1. For each i > e, let h_{i,s+1} = ∅. For each i < e, let h_{i,s+1} = h_{i,s}. Declare all R_{i}, i > e, to be unsatisfied.

If 1 or 3 holds we must abandon the current attempt at the isomorphism h and so let h_{e,s+1} = ∅. If 1 holds, we have a witness to fact that Φ_{e} is not an isomorphism from C to A and we declare R_{e} to be satisfied.

If 2 holds, there are two cases. If h_{e,s} = ∅, we restart our definition of h_{e} using the assumed isomorphism between ⟨A, a⟩ and ⟨B, b⟩: Find the least tuple ⟨a_{0}, …, a_{r−1}⟩ of distinct numbers such that a_{z_{e,s}} = b and if we define h_{e,s+1} to be the partial function mapping each n < r to a_{n}, then

1. B ⊨ Γ_{s+1}[h_{e,s+1}] and

2. for all t ≤ s and δ ∈ {0, 1}, B ⊨ (Γ_{t} ∧ θ_{t}^{δ})[h_{e,s+1}] ⇒ A ⊨ (Γ_{t} ∧ θ_{t}^{δ})[Φ_{e,s} ↾ r_{e,s} + 1],

and define h_{e,s+1} in this manner. (Such a tuple exists because, since R_{e} is not satisfied, A ⊨ Γ_{s+1}[Φ_{e,s}], so that A ⊨ Γ_{s+1}[{⟨z_{e,s}, a⟩}], and ⟨A, a⟩ ≅ ⟨B, b⟩.)

If h_{e,s} ≠ ∅, we extend h_{e} so as to keep h_{e} and h_{e}Φ_{e}^{−1} looking like isomorphisms. If |dom h_{e,s}| is even, let k be the least number not in rng h_{e,s}, let n be a number larger than any previously appearing in the construction, and define h_{e,s+1} = h_{e,s} ∪ {⟨n, k⟩}. If |dom h_{e,s}| is odd, let p be the least number not in dom h_{e,s}, let m be such that B ⊨ Γ_{s+1}[h_{e,s} ∪ {⟨p, m⟩}], and let h_{e,s+1} = h_{e,s} ∪ {⟨p, m⟩}.

If no such e exists, let ε be such that B ⊨ (Γ_{s} ∧θ_{s}^{ε})[g_{s}] and let max(dom g_{s})+1 = r. For each i ∈ ω, let h_{i,s+1} = h_{i,s}.

In any case, we continue to extend the diagram Δ_{C} and the isomorphism g. We add θ_{s}^{ε} to Δ_{C} and let Γ_{s+1} = Γ_{s} ∧ θ_{s}^{ε}. If |dom(g_{s} ↾r)| is even, let k be the least number not in rng(g_{s} ↾ r), let n be a number larger than any previously appearing in the construction, and let g_{s+1} = g_{s} ↾ r∪{⟨n, k⟩}. If |dom(g_{s} ↾r)| is odd, let p be the least number not in dom(g_{s} ↾r), let m be such that B ⊨ Γ_{s+1}[g_{s} ↾r ∪ {⟨p, m⟩}], and set g_{s+1} = g_{s} ↾r ∪ {⟨p, m⟩}.

Notice that, whichever case holds, B ⊨ Γ_{s+1}[g_{s+1}] and for each e ∈ ω, B ⊨ Γ_{s+1}[h_{e,s+1}], which are the induction hypotheses needed for the next stage of the construction.

Verifications. Since at each stage s + 1 we added either θ_{s} or its negation to Δ_{C}, Δ_{C} is the atomic diagram of a structure C. Because A and B are 1-decidable, the construction is effective and so C is computable.

Suppose first that there is an e such that R_{e} is active infinitely often and let e be the least such number. We wish to show that h_{e}Φ_{e}^{−1} is the desired computable isomorphism from ⟨A, a⟩ to ⟨B, b⟩. Let s_{0} be a stage such that no R_{i} is active for i < e at any stage t ≥ s_{0}. It follows from the definition of r_{e,s} that there exists an s_{1} ≥ s_{0} such that r_{e,t} = r_{e,s_{1}} for all t ≥ s_{1}. Let r_{e} = r_{e,s_{1}}. It follows from the definition of g_{s} that there exists s_{2} ≥ s_{1} such that g_{t} ↾ r_{e} + 1 = g_{s_{2}} ↾ r_{e} + 1 for all t ≥ s_{2}. As R_{e} is active infinitely often it is never satisfied after stage s_{2}. So condition 1 never holds after this stage. Thus A ⊨ Γ_{s}[Φ_{e}] for every s ≥ s_{2}, and hence Φ_{e} is an isomorphism from C to A.

We claim that it is not possible for condition 3 to hold infinitely often. Suppose otherwise. Let s_{3} ≥ s_{2} be such that dom Φ_{e,s_{3}} ⊇ {0, …, r_{e}}. Inspecting the way h_{e,s+1} is defined when case 2 holds and h_{e,s} = ∅, we see that there is an s ≥ s_{3} such that h_{e,s+1} = {⟨n, a_{n}⟩ | n ≤ r_{e}} for a tuple ⟨a_{0}, …, a_{r_{e}}⟩, a_{z_{e,s}} = b, such that for all t > s,

1. B ⊨ Γ_{t+1}[{⟨n, a_{n}⟩ | n ≤ r_{e}}] and

2. B ⊨ (Γ_{t} ∧ θ_{t}^{1−ε})[{⟨n, a_{n}⟩ | n ≤ r_{e}}] ⇒ A ⊨ (Γ_{t} ∧ θ_{t}^{1−ε})[Φ_{e} ↾ r_{e} + 1].

Such a tuple exists because ⟨A, a⟩ ≅ ⟨B, b⟩ and Φ_{e}(z_{e,s}) = a.

Now suppose that t + 1 is the first stage after s + 1 at which condition 3 holds, and let ε be as in that condition. Then B ⊨ ¬((Γ_{t} ∧ θ_{t}^{ε})[h_{e,t}]). On the other hand, B ⊨ Γ_{t}[h_{e,t}]. Thus B ⊨ (Γ_{t} ∧ θ_{t}^{1−ε})[h_{e,t}]. Since h_{e,t} is an extension of h_{e,s+1}, B ⊨ (Γ_{t} ∧ θ_{t}^{1−ε})[h_{e,s+1}]. But then by 2 above, A ⊨ (Γ_{t} ∧ θ_{t}^{1−ε})[Φ_{e} ↾ r_{e} + 1]. But by part b of condition 3, B ⊨ ¬((Γ_{t} ∧ θ_{t}^{1−ε})[g_{t} ↾ r_{e} + 1]). By Proposition 6.21(5), there exists a u and an ε such that A ⊨ ¬(θ_{u}^{ε}[Φ_{e}]) and B ⊨ ¬(θ_{u}^{1−ε}[g_{t} ↾ r_{e} + 1]). But then θ_{u}^{ε} must be in Γ_{u+1}, so that A ⊭ Γ_{u+1}, contrary to our assumption.

So condition 3 holds only finitely often. Say it never holds after stage s_{4} ≥ s_{3}. Since condition 2 holds infinitely often, there are infinitely many e-expansionary stages. Thus, since R_{e} is never satisfied, Φ_{e} is a computable isomorphism from C to A. Furthermore, h_{e} = lim_{s} h_{e,s} is well-defined, and in fact h_{e}(x) = h_{e,s}(x) for the least s > s_{4} for which h_{e,s}(x) is defined. Since B ⊨ Γ_{s}[h_{e,s}] for all s > s_{4}, h_{e} is a computable isomorphism from C to B.

Thus h_{e} ∘ Φ_{e}^{−1} is a computable isomorphism from A to B. But if we let z = lim_{s} z_{e,s}, then h_{e} ∘ Φ_{e}^{−1}(a) = h_{e}(z) = b. Thus in fact h_{e} ∘ Φ_{e}^{−1} is the desired computable isomorphism from ⟨A, a⟩ to ⟨B, b⟩.

Finally, suppose for the sake of a contradiction that every e is active only finitely often. It is not hard to see that at any e-expansionary stage, one of conditions 1, 2, or 3 must hold. Thus, if there are infinitely many e-expansionary stages then R_{e} is eventually permanently satisfied.

As we have mentioned, if s is a stage such that, for each i < e and each t ≥ s, R_{i} is not active at stage t and r_{e,t} = r_{e,s}, then for all t ≥ s, g_{t} ↾ r_{e,s} + 1 = g_{s} ↾ r_{e,s} + 1 and B ⊨ Γ_{t}[g_{t} ↾ r_{e,s} + 1]. So the fact that each e is active only finitely often implies that g = lim_{t} g_{t} exists and is an isomorphism from C to B.

Thus C is isomorphic, but not computably isomorphic, to A, contradicting the computable categoricity of A. □

Thus 1-decidability suffices to guarantee the persistence of computable categoricity. We will see in the next section that, without such an assumption, computable categoricity need not be persistent. Moreover, the equivalence of computable categoricity with having a Scott family established by Goncharov under the assumption of 2-decidability does not hold for all 1-decidable structures (Theorem 7.19).

6.2 Nonpersistence of Computable Categoricity

We now see that the addition of even a single constant for any element of a computably categorical structure can change its dimension.

Theorem 6.22 (Cholak, Goncharov, Khoussainov and Shore [1999]) For each k ∈ ω there is a computably categorical A such that the expansion A′ of A gotten by adding on a constant naming any element of A has dimension exactly k.

Idea of Proof (for k = 2). We first construct a (uniformly) computably enumerable family of distinct pairs of sets S = {f(i)|i ∈ ω} = {(A_{i}, B_{i})|i ∈ ω} which is symmetric, i.e. for every i ∈ ω there is a j ∈ ω such that f(i) = (A_{i}, B_{i}) = (B_{j}, A_{j}). In addition to the computable enumeration f, there is one other natural computable enumeration of this family, f̃ defined by f̃(i) = (B_{i}, A_{i}). This family S is constructed (by a 0′′ type priority argument) to have dimension 2 in the sense that there is no computable function g such that f = f̃g but, for every one-one computable enumeration h of the family, there is a computable function g such that f = hg or f̃ = hg. The two enumerations of this family are then coded symmetrically into a graph so that the whole structure is computably categorical. If one adds on a constant, however, it distinguishes between the two coded enumerations and so one has a structure of dimension 2. □

For k̇ > 2, one can generalize the notion of symmetric family to one-one enumerations f of families S of k-tuples of sets. The combinatorial details become fairly complicated. A simpler approach to a proof of the general theorem is provided in the next section as a corollary to some results on degree spectra.

7. Degree Spectra of Relations

Another important topic in computable model theory that turns out to be closely connected to computable categoricity is that of the dependence of the computability properties of relations not included in the language of a given structure on its presentation. For example, in “standard” presentations of ⟨ℕ, ≤⟩ the successor function is computable but it is not computable in every presentation (Proposition 6.1). Similarly, standard presentations of the algebraically closed field ℚ̃ of characteristic 0 and infinite transcendence degree make the relation of algebraic dependence computable but not all presentations do. (Indeed, if algebraic dependence is computable in both of two isomorphic computable algebraically closed fields then they are computably isomorphic. However, Corollary 6.12 says that if they have infinite transcendence degree their dimension is infinite.) On the other hand, these particular relations are easily seen to always be co-computably enumerable and computably enumerable respectively. Others remain computable or computably enumerable in every presentation. Such relations were singled out and studied by Ash and Nerode [1981].

Definition 7.1 (Ash and Nerode) If R ⊆ A^{n} is an n-ary relation on a structure A, R is intrinsically computable (computably enumerable) if f[R] is computable (computably enumerable) for every isomorphism f : A → B.

Example 7.2 ⟨ℕ, ≤⟩: Successor is not intrinsically computable.

Example 7.3 ⟨ℕ, s⟩: Every computable relation is intrinsically computable.

We know that the two structures discussed above, ⟨ℕ, ≤⟩ and ℚ̃, are not computably categorical while similar ones (such as ⟨ℕ, s⟩ and algebraically closed extension of ℚ of finite transcendence degree) are computably categorical and in each of them this phenomena (of a relation being computable in one presentation and not in another) does not arise. One might naturally ask if computable categoricity guarantees that a relation computable in one presentation is computable in all. The answer is both yes and no. If we restrict our attention to relations that are definable or even invariant under all automorphisms the answer is yes.

Proposition 7.4 If a structure A is computably categorical then every definable relation R (or one invariant under automorphisms) on A that is computable in any presentation of A is intrinsically computable, i.e. computable in every presentation of A.

Proof. Suppose A is computably categorical, R^{A} is computable, and g is an isomorphism from A to B. We wish to show that g[R^{A}] is computable. As A is computably categorical, there is a computable isomorphism f : A → B. R^{A} and \overline{R}^{A} are computable and so their images under f are computably enumerable and complementary and hence computable. As R is invariant under automorphisms, in particular under g^{−1}f, f[R^{A}] = g[R^{A}] and so g[R^{A}] is also computable. □

So for computably categorical structures the effectiveness of definable properties is independent of the presentation. If we ask instead that every computable relation on A (definable or not) be intrinsically computable, the answer to our question is no. Computable categoricity does not suffice to guarantee that every computable relation is intrinsically computable. (See Example 7.7 below.) Instead we are led to a stronger notion.

Definition 7.5 A is computably stable if every isomorphism f : A → B is computable.

Example 7.6 ⟨ℕ, s⟩ is computably stable. Indeed, every isomorphism between two presentations is uniquely determined by the computable procedure of sending the least element in one presentation to the least one in the other and then proceeding by recursion as in Example 6.5.

Example 7.7 ⟨ℚ, ≤⟩ is computably categorical but not computably stable. In fact, given any two presentations of ⟨ℚ, ≤⟩, the usual back and forth argument shows that there are continuum many isomorphisms between them. Moreover, the usual back and forth argument can be run in each of countably many intervals to, for example, construct an automorphism taking a computable subset (such as ℤ) to a noncomputable one (any set consisting of one element from each interval (x, x + 1) for x ∈ ℤ).

Proposition 7.8 (Ash and Nerode [1981]) A is computably stable if and only if every computable relation on A is intrinsically computable.

Proof. As every isomorphism between presentations of A is computable, the argument of Proposition 7.4 shows that the image of any computable relation R on A under any isomorphism is computable. For the other (if) direction, consider A as a structure on the set ℕ and the relation R giving, in A, the successor function on ℕ. If f : A → B is an isomorphism and R^{B} = f[R^{A}] is computable then the construction of Example 6.5 computes f. □

One can, in fact, give a more informative characterization of computable stability like that provided for computable categoricity in terms of Scott families by Theorem 6.16. In place of a sequence of formulas each of which determines a sequence of elements of the given structure A up to automorphisms, one needs a sequence of formulas that uniquely define the elements of A. On the other hand, we now only need the 1-decidability of A for the characterization.

Theorem 7.9 (Ash and Nerode [1981], Goncharov [1975]) If A is 1-decidable then A is computably stable if and only if there are constants \overline{c} ∈ A and a computable sequence ϕ_{i}(\overline{c}, x) of existential formulas such that for each i there is a unique a ∈ A satisfying ϕ_{i} and each a ∈ A satisfies some ϕ_{i}.

Proof sketch. It is easy to see that the existence of a family as described insures that every isomorphism f : A → B is computable as, once the image of the constants \overline{c} are fixed, f must send the unique solution of each ϕ_{i}(\overline{c}, x) in A to the solution of the same formula in B. The proof of the other direction (only if) of this theorem involves a finite injury priority argument. One attempts to build a B isomorphic to the given A by a Δ_{2} isomorphism but not by any computable isomorphism. The least failure of this diagonalization requirement occurs only because the elements on which we might diagonalize are uniquely defined from those fixed by higher priority requirements. These already fixed elements are the constants \overline{c} required. The portions of the diagram of B to which we have committed ourselves at various stages of the construction provide the desired formulas ϕ_{i} when various extra parameters are replaced by existentially quantified variables. □

More generally, we would like to know when a specified computable (or computably enumerable) relation is intrinsically computable or computably enumerable. An examination of the two examples considered above, ⟨ℕ, ≤⟩ and ℚ̃, gives us a clue as to when a relation is intrinsically c.e. The relation P (x, y) on ℕ saying that y is not the immediate successor of x is definable in the structure ⟨ℕ, ≤⟩ by the existential formula ∃z((x < z < y)∨(y < z < x)∨(x = y)) and so is computably enumerable in any presentation of ⟨ℕ, ≤⟩. The binary relation D(x, y) saying that x and y are algebraically dependent is equivalent to the disjunction of an infinite computable list of existential formulas ϕ_{n} each asserting (in the language of fields) that there is a nonzero polynomial of degree n in x and y which equals 0. Any such relation is again clearly computably enumerable in any presentation of a field. To enumerate the dependent pairs, one simply dovetails the searches for witnesses for each of the existential formulas ϕ_{n}. These phenomena suggest a definition.

Definition 7.10 A relation R(x_{1}, …, x_{n}) on a structure A is formally computably enumerable if it is equivalent to a disjunction ⋁ ϕ_{i}(x_{1}, …, x_{n}) of a computable sequence of existential formulas ϕ_{i} with free variables x_{1}, …, x_{n}. R is formally computable if both R and \overline{R} are formally computably enumerable.

Clearly, any formally computable (computably enumerable) relation is intrinsically computable (computably enumerable). Ash and Nerode [1981] prove that, under mild decidability conditions, this condition is also necessary.

Theorem 7.11 (Ash and Nerode [1981]) If R ⊆ A^{n} and ⟨A, R⟩ is 1-decidable, then R is intrinsically computably enumerable if and only if it is formally computably enumerable. R is intrinsically computable if and only if it is formally computable.

Actually, the 1-decidability of ⟨A, R⟩ is a bit stronger than what Ash and Nerode need. They only need to be able to decide for each \overline{c} in A and each existential ϕ(\overline{c}, \overline{x}) if there is an \overline{a} ∉ R such that A ⊧ ϕ(\overline{c}, \overline{a}). However, some conditions are necessary as Goncharov [1980a] and Manasse [1982] have constructed examples of intrinsically c.e. relations which are not formally c.e. There has been a lot of work, primarily by Ash, Ash and Knight and their students generalizing these results (under stronger decidability conditions) to syntactic characterizations of relations being intrinsically Σ_{α} or Δ_{α} for all levels α of the hyperarithmetic hierarchy. They also provide similar generalizations of the notions and results on computable categoricity and stability to higher levels of the hierarchy of computable infinitary formulas. These papers include Ash [1986], [1986a], [1987]; Ash and Knight [1990], [1994], [1995], Barker [1988] and Chisholm [1990a]. Related results when the notions are relativized to the degree of noncomputable models can be found in Ash, Knight, Manasse and Slaman [1989], Ash, Knight and Slaman [1993] and Chisholm [1990]. Here the results are proven by forcing arguments and the extra decidability hypotheses are not needed.

Faced with a computable (or c.e.) relation R on A which is not intrinsically computable (or c.e.), what can we say about its image under isomorphisms? In particular, how complicated can f[R] be for a (computable) relation R on A and an arbitrary isomorphism f : A → B (with B computable, of course). An approach to this question is suggested by the following definition.

Definition 7.12 If R ⊆ A^{n} is an n-ary relation on A, the degree spectrum of R, DgSp(R), is {deg_{T} (f[R]) | f : A → B is an isomorphism}.

There are a number of results giving conditions under which the degree spectrum of a computable relation consists of precisely some particular standard class of degrees such as all the degrees, the c.e. degrees, etc. We concentrate on the issue of finding instances where the spectrum is finite and the connections between this issue and the dimension of the given structure. The first results of this sort are due to Harizanov. Here is one example.

Theorem 7.13 (Harizanov [1993]) There is an A and an R on A such A has exactly two computable presentations and DgSp(R) = {0, c} with c noncomputable and Δ_{2}^{0}.

The next problem (that remained open for some time) was whether Δ_{2}^{0} could be replaced by c.e. in this result or, more generally, what is possible for intrinsically c.e. relations especially for structures of finite dimension. Goncharov has announced a solution, based on work with Khoussainov, constructing a structure A of dimension 2 with a relation R on A with degree spectrum consisting of 0 and a nonzero c.e. c. He constructs families of c.e. sets and codes them into a structure. Khoussainov and Shore have independently directly constructed directed graphs of each finite dimension n with relations having various degree spectra. Moreover, these structures can be simply modified to provide examples of ones for each n which are computably categorical but when expanded by a constant have dimension n. We first state the main result for dimension 2.

Theorem 7.14 (Khoussainov and Shore [1998]) There is a rigid directed graph A (i.e. one with no nontrivial automorphisms) of dimension 2 and a subset R of A such that DgSp(R) = {0, c} with c noncomputable and c.e. Moreover, the relation P = {(x, y)|x ∈ R^{A_{0}} ∧ y ∈ R^{A_{1}} ∧ there is an isomorphism from A_{0} to A_{1} which extends the map x ↦ y} is computable.

We sketch the proof of this theorem in §9. For now we give some generalizations and corollaries.

Theorem 7.15 (Khoussainov and Shore [1998]) For any computable partially ordered set D there is a rigid directed graph A of dimension the cardinality of D and a subset R of A such that DgSp(R) ≅ D. (The ordering on DgSp(R) is given by Turing reducibility.) Indeed, we can also guarantee that R^{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(R) is 0. Moreover, there is a uniformly computable sequence A_{i} of representatives of the computable isomorphism types of A such that the relation P = {(x, y)|x ∈ R^{A_{i}} ∧ y ∈ R^{A_{j}} ∧ there is an isomorphism from A_{i} to A_{j} which extends the map x ↦ y} is computable.

Corollary 7.16 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. Take the structure A given by Theorem 7.15 for the partial order consisting of k many incomparable elements. Let A_{i}, 1 ≤ i ≤ k be the computable representatives of the computable isomorphism types of A. So, in particular the sets R^{A_{i}} are Turing incomparable. We use the computability of P to paste the A_{i} together to produce a B as required. More precisely, B consists of the disjoint union of the A_{i} and the edges of B are the ones in each A_{i}. In addition, B has an extra binary predicate defined by the relation P in the theorem and an equivalence relation E whose equivalence classes are the A_{i}.

Clearly B is a computable structure. Now let B′ be any 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 loss 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 a computable function f_{2} : A_{1} → A′_{2}, then we would be able to decide R^{A_{1}} in A_{1} as follows: x in A_{1} belongs to R^{A_{1}} if and only if (f_{1}(x), f_{2}(x)) ∈ P. Hence all the structures A′_{1}, …, A′_{k} are pairwise noncomputably isomorphic and so represent all the computable isomorphism types of A, i.e. are computably isomorphic to A_{1}, …, A_{k} (in some order). Hence B′ is clearly computably isomorphic to B and so B is computably categorical.

Now let a be any element from A_{1}. Consider the expanded structures B_{i} consisting of B with the new constant interpreted as a_{i}, the image of a in A_{i}. It is clear that all the B_{i} are isomorphic but not computably so. Thus the dimension of B_{i} is at least k. On the other hand, as A is rigid there are no choices other than the a_{i} as the interpretation of a in B. Thus, by the computable categoricity of B, any structure isomorphic to say B_{1} must be computably isomorphic to one of the B_{i} and so the dimension of these structures is precisely k as required. □

Corollary 7.17 (Khoussainov and Shore [1998]) There exists a computably categorical structure without a Scott family.

Proof. If structure of previous corollary had a Scott family it would remain computably categorical when constants were added. □

A similar construction provides an example showing that even if the structure is persistently computably categorical it need not have a Scott family.

Theorem 7.18 (Khoussainov and Shore [1998]) There exists a structure without a Scott family such that every expansion of the structure by a finite number of constants is computably categorical.

Kudinov independently proved more.

Theorem 7.19 (Kudinov [1996]) There is a computably categorical 1-decidable structure A with no Scott family.

Proof sketch. Kudinov slightly modifies a family of computable enumerations constructed by Selivanov [1976] 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. □

Of course, this Theorem shows that the assumption of 2-decidability was necessary in Goncharov’s characterization (Theorem 6.16) of computably categorical structures as ones with Scott families. By Millar’s result on persistence (Theorem 6.20), Kudinov’s structure is persistently computably categorical and so is also a witness to Theorem 7.18.

A very natural question is whether every c.e. degree can be realized (with 0) as a degree spectrum. Hirschfeldt has recently answered this question by adapting and extending the methods presented here.

Theorem 7.20 (Hirschfeldt [1999]) For every c.e. degree c there is an A and a relation R on A such that DgSp(R) = {0, c}. Indeed c can be replaced by any uniformly c.e. array of c.e. degrees.

Hirschfeldt’s construction precisely controls the degree spectrum of the relation R but does not control dimension of A. Thus the following question is still open.

Question 7.21 (Goncharov and Khoussainov [1997]) Which n-tuples of c.e. degrees can be realized as the degree spectrum of a relation on a structure of dimension n?

If we move beyond the c.e. degrees there are a few results by Harizanov on possible degree spectra but not much is known. However, we should point out that several natural strengthenings of these results can ruled out by classical descriptive set theoretic results.

Remark 1 For a given relation R on a computable structure A, the set {R^{B}| B is a computable presentation of A} is Σ_{1}^{1} in R. Thus, there are countable partial orderings that cannot be realized in the c.e. degrees as the degree spectrum of any relation R 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 R on a computable structure A. Nor can it be true that any finite set of degrees can be realized as the degree spectrum of any relation R 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.

8. Algebraic Examples

In §6 we saw several examples of theories whose models all have dimension 1 or ω and algebraic conditions characterizing the models in each class. The theories of this sort considered there were linear orderings, Boolean algebras and algebraically closed fields. We cite two more.

Theorem 8.1 A real closed field of finite transcendence degree over ℚ is computably stable. One of infinite transcendence degree has dimension ω.

Proof. If a real closed field A has finite transcendence degree over ℚ and f : A → B is an isomorphism, let a_{1}, …, a_{n} be a transcendence basis for A over ℚ and b_{1}, …, b_{n} be their image in B. Calculate f(a) for any element a of A by first finding an equation over ℚ[a_{1}, …, a_{n}] satisfied by a. Find all its solutions and the place of a among these solutions in the order of A. Now, f(a) must be the solution of the same equation over ℚ[b_{1}, …, b_{n}] which lies in the same place among all the solutions in B listed in order. Thus f is computable. On the other hand, if A is of infinite transcendence degree then by Theorem 6.11, it has dimension ω. (Note that as the theory of real closed fields has effective quantifier elimination, every computable model is decidable. Moreover, the prime model of T h(A, \overline{c}) for any finite list \overline{c} of elements of A is of finite transcendence degree and so not A itself.) □

Theorem 8.2 (Goncharov [1981]) If A is an abelian group then it has dimension 1 or ω.

The proof of this result is particularly interesting because it relies on important sufficient condition for a structure to have dimension ω.

Theorem 8.3 (Goncharov [1982]) If there is a Δ_{2}^{0} isomorphism between A and B but no computable one then A has dimension ω.

On the other hand, the results described in §6.2 and §7, as well as many earlier papers, supply examples of structures of dimension n for each n ∈ ω. Indeed, our results supply examples of structures of dimension n whose presentations are characterized by the Turing degree of a specific relation on the structure. Moreover, representatives of the n many computable isomorphism types of these structures can be pasted together to produce a single computably categorical structure such that an expansion by constants yields a structure of dimension n. Of course, when there are characterization theorems that show that the dimension must be 1 or ω such constructions are not possible. On the other hand, for many familiar algebraic theories for which we cannot provide such a dichotomy and characterization, it is possible to construct examples of models not only of each finite dimension but also ones exhibiting the additional properties enjoyed by the examples in §7.

Theorem 8.4 (Goncharov [1980a], [1981]; Goncharov and Dobrotun [1989], Goncharov, Molokov and Romanovski [1989]; Kudinov (personal communication); Hirschfeldt, Khoussainov, Slinko and Shore [1999]) For each of the following theories and each n ∈ ω, there is a model A with a subset R such that the dimension of A is n and the degree spectrum of R consists of n different c.e. degrees. Moreover, for each n there is a model A which is computably categorical but some expansion by constants has dimension n: graphs, lattices, partial orders, nilpotent groups, rings (with zero divisors) and integral domains. In each case the subset R can be taken to be a substructure of the appropriate type.

The results on the existence of models of each of these theories of each finite dimension are due to various people (most to Goncharov and his coauthors, the one for integral domains is due to Kudinov). They were typically first proved by codings of families of c.e. sets. For graphs, the results involving degree spectra and extensions by constants are due to Khoussainov and Shore and are described in §7. (Actually, the original paper used directed graphs but an examination of the construction shows that it is possible to use undirected graphs instead.) All the other ones involving degree spectra and extensions by constants have been proven by Hirschfeldt, Khoussainov, Slinko and Shore [1999].

Although direct constructions are sometimes possible, these results can all be derived from the results on graphs by finding a sufficiently effective coding of graphs into models of each theory. The idea is that, if the coding is sufficiently effective, all the computability properties involved carry over. Thus all these theories are not only undecidable but the codings (of say graphs) needed to prove that they are universal (i.e. code all of predicate logic) are highly effective. (In addition to simple codings of the domain and edge relation on the initial graph, an important issue is the effective reversibility of the coding. That is, one wants the model coding a given graph to effectively determine the original graph.) On the other hand, the theories discussed in §6 whose models are all either computably categorical or of dimension ω are decidable and have strong structure theorems that are used in the proofs. We expect that there are natural theories that are neither “so decidable” as those of §6 nor “so undecidable” as the ones in Theorem 8.4. In particular, we suggest the theory of fields as a good test case as it is undecidable but the proofs of undecidability (that we know) interpret ℕ in a rather specific way rather than arbitrary structures.

9. The Basic Theorem on Degree Spectra

In this section we sketch the proof of the Theorem 7.14, the case n = 2 of our main theorem on degree spectra.

Theorem 7.14 (Khoussainov and Shore [1998]) There is a rigid directed graph A of dimension 2 with computable (but not computably isomorphic) presentations A_{0} and A_{1}and a subset R of A such that DgSp(R) = {0, c} with c noncomputable and c.e. Moreover, the relation P = {(x, y)|x ∈ R^{A_{0}} ∧ y ∈ R^{A_{1}} ∧ there is an isomorphism from A_{0} to A_{1} which extends the map x ↦ y} is computable.

Proof sketch. Our directed graph A will consist of disjoint components [B_{i}] all of one special type. The graph we denote by [B] is uniquely determined by the set B ⊆ {n|n ≥ 5}. It consists of one 3-cycle and one n-cycle for each n ∈ B. In addition, there is one element of the 3-cycle, called the top of the graph, from which there is an edge to one element of each n-cycle for n ∈ B. This element of the n-cycle is called the coding location for n. For convenience, we also denote [{n}] by [n]. We build up our graph using two operations, + and ·. The sum [A] + [B] of two graphs is simply their disjoint union. The product, [A] · [B], of two graphs of our special form is gotten by taking disjoint copies of [A] and [B − A] and identifying the top elements (and the associated 3-cycles) in each of the two graphs. For example [5] · [6] ≅ [{5, 6}] and [{5, 6, 7}] · [{6, 7, 8, 9}] ≅ [{5, 6, 7, 8, 9}]. Note that [A] · [B] ≅ [B] · [A].

Our plan is to construct our graph A = [B_{0}] + [B_{1}] + ⋯ + [B_{n}] + ⋯ together with enumerations of the sets B_{i} so that B_{i} − B_{j} ≠ ∅ for i ≠ j (and indeed we guarantee that B_{i,s} − B_{j,s} ≠ ∅ for every s and i ≠ j). So clearly

• A is rigid.

The required R will be a subset of the coding points in A. We enumerate two presentations A_{0} and A_{1} of A as A_{0,s} and A_{1,s} each isomorphic to [B_{0,s}]+[B_{1,s}]+ ⋯ and the interpretations R_{i} (as R_{i,s}) of R in A_{i} so that

• R_{0} is computably enumerable but not computable: As the construction proceeds we enumerate the elements x of R_{0} so as to make the set enumerated noncomputable by a standard diagonalization procedure.

• R_{1} is computable: As we enumerate a number x into R_{0}, we make sure that the corresponding element y of A_{1} is a new large number. Thus R_{1} is enumerated in increasing order.

• P = {⟨x, y⟩ |x ∈ R_{0} ∧ y ∈ R_{1} ∧ (∃f : A_{0} ≅ A_{1})(f(x) = y)} is computable: By the procedure alluded to above for choosing the y ∈ R_{1} corresponding to a given x ∈ R_{0}, the pairs ⟨x, y⟩ ∈ P are enumerated in increasing order.

• A_{0} ≇_{c} A_{1}: This is guaranteed by the previous requirements that R_{0} is computable but R_{1} is not. By the rigidity of A, there is only one isomorphism from A_{0} to A_{1} and it must take R_{0} to R_{1}. If it were computable it would preserve the computability of the interpretation of R.

• Every computable presentation G_{j} of A is computably isomorphic to A_{0} or A_{1}: Our plan here is to define maps r_{j,s} so that at every stage s of the construction at which it still looks as if G_{j} might be isomorphic to A, r_{j,s} is a monomorphism from G_{j,s} into A_{i,s} (for i = 0 or 1) and that, at the end of stage s, if we cannot extend the current map r_{j,s} then we switch so that r_{j,s+1} is a monomorphism from G_{j,s+1} into A_{1−i,s+1}. If, after some stage t, we never switch our potential isomorphism then ∪{r_{j,s}|t ≤ s} is, in fact, the desired computable isomorphism from G_{j} to A_{i}. On the other hand, if we switch infinitely often we guarantee that there is a special component S_{j} of G_{j} which is not a component of A and so G_{j} is not isomorphic to A.

The crucial idea needed for the construction is how to diagonalize to make R_{0} noncomputable while its isomorphic image R_{1} remains computable and also maintain control over the potential isomorphisms between G_{j} and A_{i}. The diagonalization procedure is based on two symmetric operations L (left) and R (right) on sequences of graphs [B_{i}].

Definition 9.1 L([B_{1}], …, [B_{n}]) is the graph

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

R([B_{1}], …, [B_{n}]) is the graph [B_{1}] · [B_{n}] + [B_{1}] · [B_{2}] + … + +[B_{n−1}] · [B_{n}].

We apply the L operation, for example, to a graph G whose components include the [B_{i}] by removing all the [B_{i}] and inserting L([B_{1}], …, [B_{n}]). We also adopt the convention that the elements of the component [B_{i}] are the same ones in the corresponding subgraph 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). This convention is important for establishing computability properties of the graphs being constructed.

We will apply an R operation in the construction (to A_{1}) only when we also apply an L one (to A_{0}). We also have the corresponding convention that the elements of the component [B_{i−1}] 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 0 for n when i = 1).

The following lemma is immediate from the definitions.

Lemma 9.2 For any sequence [B_{1}], …, [B_{n}] of graphs, L([B_{1}], …, [B_{n}]) and R([B_{1}], …, [B_{n}]) are isomorphic and extend [B_{1}] + ⋯ + [B_{n}]. Moreover, if G has the [B_{i}] as components then replacing their sum with L([B_{1}], …, [B_{n}]) or R([B_{1}], …, [B_{n}]) produces two isomorphic graphs each extending G. □

The plan for diagonalization is now easily described. To make sure that R_{0} ≠ ϕ_{e}, we choose numbers a_{e}, b_{e} and c_{e} and insert copies of [a_{e}], [b_{e}] and [c_{e}] into A_{0} and A_{1}. For definiteness, say that x_{e} is the (number which is) the coding location for a_{e} in these graphs. We now wait for ϕ_{e}(x_{e}) to converge to 0. If it never does we do nothing and so win as x_{e} is not in R_{0}. If ϕ_{e}(x_{e}) converges to 0 at stage s, we replace the components [a_{e}], [b_{e}] and [c_{e}] in A_{0} and A_{1} by L([b_{e}], [a_{e}], [c_{e}]) and R([b_{e}], [a_{e}], [c_{e}]), respectively; put x_{e} into R_{0} and its image in A_{1} into R_{1}. The crucial point here is that, by our conventions, the image of x_{e} (as an element of L([b_{e}], [a_{e}], [c_{e}]) in A_{0}) in R([b_{e}], [a_{e}], [c_{e}]) and so in A_{1} is a new large number. Thus we diagonalize for R_{0} but keep R_{1} computable.

The remaining issue is how to simultaneously satisfy the requirements that, if isomorphic to A, G_{j} is computably isomorphic to A_{0} or A_{1}. Consider the requirement for a single G. Following the idea described above, we choose a special component [S] of G and make its image in the A_{i} participate in infinitely many of the left and right operations done for diagonalizations. We have some definition of expansionary stage that measures the extent of a possible isomorphism between G and A. If there are only finitely many such expansionary stages then G is not isomorphic to A and no other actions are necessary. So suppose there are infinitely many expansionary stages.

At each expansionary stage s we have a monomorphism r_{s} from G into A_{i} and components [S_{i,s}] of A_{i} (for i = 0 or 1) corresponding to the special component [S] of G. If we wish to diagonalize at a coding location x_{e} in the range of r, we wait for the next expansionary stage s and perform L and R operations in A_{0} and A_{1}, respectively, on the sequence [b_{e}], [a_{e}], [c_{e}], [P_{e}], [S_{i,s}], [Q_{e}]. Here P_{e} and Q_{e} are either numbers chosen in advance for the requirement for G or sets that have participated in one of these two locations in a previous operation for G. In any case, all of these components are in the range of r_{s} when we perform the operations. Suppose r_{s} mapped G into A_{i}. The crucial point is that when we next get an expansionary stage at t and it is possible to extend r_{s} so as to keep [S] mapped into [S_{i,s}] then it is possible to extend r_{s} to be a map of G into A_{i} at t. The key idea here is that each component in the original sequence can “grow into” only one of two components in the final one, itself or the one immediately to its left (or right depending on whether i = 0 or 1). Thus if the image of one of the components remains fixed then we can see (in the reverse order of the operation performed) that each component in turn remains fixed as it has no other place to go. In this case, we extend r_{s} to r_{t} still mapping G into A_{i}. If it is not possible to keep [S] mapped into [S_{i,s}] then we change r so as to define r_{t} as a map from G into A_{1−i}. This also means that [S_{i,t}] is not the same component in A_{i} as was [S_{i,s}] (or we could have kept it fixed). (Actually it is the component that had been [P_{e}] or [Q_{e}] depending on the specifics of the situation.) We now guarantee never to use the old [S_{i,s}] component in any future operation.

The ultimate consequence of such a procedure is that, if we change the range of r_{t} infinitely often, [S] becomes infinite in G but each component [S_{i,s}] that is a potential image of [S] in A_{i} is involved in only finitely many operations and so is itself finite. Thus, in this case, G is not isomorphic to A. On the other hand, if G actually is isomorphic to A, we keep extending r_{s} from some stage on while never changing the A_{i} to which it maps G. In this case, we arrange the definition of r_{s} so that if it eventually maps onto A_{i} and so determines the required computable isomorphism from G to A_{i}.

We have, of course, omitted some of the combinatorics (particularly the way in which we extend the domain of r) even in this case of one G requirement. The full construction consists of using a module of this sort for each requirement on a typical 0′′ priority tree. Of course, the precise actions for a diagonalization requirement at a node α (e.g. which special components have to go into the sequence on which the operations are performed and in what order they go on this list) depend on the outcome of nodes β of higher priority contained in α which are devoted to various G_{j}. (The choices here are whether there are infinitely many expansionary stages or not and if so whether the range of r_{s} is fixed as i from some point on or we change it infinitely often.) The details can be found in Khoussainov and Shore [1998].

We take this opportunity to point out two corrections that should be made to the details of the general construction found in Khoussainov and Shore [1998]. The first is that whenever one applies (or considers the application of) an operation for a node β to a sequence of the form

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

one should instead use its β-transform which is defined to be the sequence B_{i_{1}}^{k}, [S]_{β_{i_{1}},t+1}^{k}, C_{i_{1}}^{k}, B_{i_{2}}^{k}, [S]_{β_{i_{2}},t+1}^{k}, C_{i_{2}}^{k}, …, B_{i_{m}}^{k}, [S]_{β_{im},t+1}^{k}, C_{i_{m}}^{k}, B_{n+1}^{k}, X^{k}, C_{n+1}^{k}, B_{j_{1}}^{k}, [S]_{β_{j_{1}},t+1}^{k}, C_{j_{1}}^{k}, B_{j_{2}}^{k}, [S]_{β_{j_{2}},t+1}^{k}, C_{j_{2}}^{k}, …, B_{j_{r}}^{k}, [S]_{β_{jr} ,t+1}^{k}, C_{j_{r}}^{k} where i_{1}, i_{2}, …, i_{m} list, in order, the i such that the designated isomorphism for the β_{i} = β ↾ (3i + 1) such that β(3i + 1) ≠ w at t + 1 is r_{β_{i},t+1}^{0} and j_{1}, j_{2}, …, j_{r} list, in order, the j such that the designated isomorphism for the β_{j} = β ↾ (3j + 1) such that β(3j + 1) ≠ w is r_{β_{i,t+1}}^{1}.

The second concerns the marking of numbers with the symbols □_{w}^{β}. No numbers should be marked in Case 1 of the construction. As a result, condition 1 in Subcase 2.1 should be weakened by not requiring that the image of r_{β_{i},t+1}^{k} has nonempty intersection with B_{i}^{k} if the designated isomorphism for β_{i} is r_{β_{i},t+1}^{0} or with C_{i}^{k} if the designated isomorphism for β_{i} is r_{β_{i},t+1}^{1}. Instead, the marking take place at the end of each stage of the construction as follows:

At the end of stage t + 1 we do some additional cancelation and marking. Suppose t + 1 is a γ recovery stage. If there are any uncancelled components isomorphic to [b_{β,γ,u}] or [c_{β,γ,u}] for u ≤ t (and β ⊇ γ) which, necessarily, have not participated in any operation, we cancel them and appoint new ones [b_{β,γ,t+1}] or [c_{β,γ,t+1}], respectively. We now mark all of the following with □_{w}^{γ} if they are not already so marked:

1. Any cancelled component.

2. Any component associated with a node β to the left of γ.

3. Any component of the form [q_{β,t+1}] with β ⊇ γ.

4. Any components of the form [b_{β,t+1}], [c_{β,t+1}] or [p_{β,t+1}] for β ⊇ γ.

5. Any components of the form [b_{β,β_{i},t+1}] or [c_{β,β_{i},t+1}] for β ⊇ β_{i} ⊃ γ.

6. Any components of the form [b_{β,γ,t+1}] if β ⊇ γ and the designated isomorphism for γ is r_{γ,t+1}^{1}or of the form [c_{β,t+1}] if β ⊇ γ and the designated isomorphism

for γ is r_{γ,t+1}^{0}.

7. If, at t + 1, we performed an operation on the β-transform of a 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 so γ ⊆ β), then, for k = 0, 1, we mark B_{i}^{k} or C_{i}^{k} if β_{i} ⊆ γ and it has previously participated in an operation; we mark B_{i}^{k} if β_{i} ⊆ γ and the designated isomorphism for β_{i} is r_{β_{i},t+1}^{1}; we mark C_{i}^{k} if β_{i} ⊆ γ and the designated isomorphism for β_{i} is r_{β_{i},t+1}^{0}; and we mark both B_{i}^{k} and C_{i}^{k} for β_{i} = γ.

The changes needed in the verifications to take advantage of these corrections are straightforward. A complete corrected version of the paper can be found at http://math.cornell.edu/~shore/.□

10. Bibliography

Ash, C. J. [1986], Recursive labeling systems and stability of recursive structures in hyperartihmetical degrees, Trans. Amer. Math. Soc. 298, 497-514.

Ash, C. J. [1986a], Stability of recursive structures in arithmetical degrees, Ann. Pure Appl. Logic 32, 113–135.

Ash, C. J. [1987], Categoricity in hyperartihmetical degrees, Ann. Pure Appl. Logic 34, 1–14.

Ash, C. J., Cholak, P. and Knight, J. F. [1997], Permitting, forcing, and copying of a given recursive relation, Ann. Pure Appl. Logic 86, 219–236.

Ash, C. J. and Knight, J. F. [1990], Pairs of recursive structures, Ann. Pure Appl. Logic 46, 211–234.

Ash, C. J. and Knight, J. F. [1994], A completeness theorem for certain classes of recursively infinitary formulas, Math. Logic Quart. 40, 173–181.

Ash, C. J. and Knight, J. F. [1995], Possible degrees in recursive copies, Ann. Pure Appl. Logic 75, 215–221.

Ash, C. J. and Knight, J. F. [1997], Possible degrees in recursive copies II, Ann. Pure Appl. Logic 87, 151–165.

Ash, C. J. and Knight, J. F. [1999], Computable Structures and the Hyperartihmetical Hierarchy, in preparation.

Ash, C., Knight, J., Manasse, M. and Slaman, T. [1989], Generic copies of countable structures, Ann. Pure Appl. Logic 42, 195–205.

Ash, C. J., Knight, J. F. and Slaman, T. A. [1993], Relatively recursive expansions. II, Fund. Math. 142, 147–161.

Ash, C. J. and Nerode, A. [1981], Intrinsically recursive relations, in Aspects of Effective Algebra (Clayton, 1979), Upside Down A Book Co., Yarra Glen, Vic., 26–41.

Baldwin, J. T. [1973], α_{T} is finite for ℵ_{1}-categorical T, Trans. A.M.S. 181, 37-51.

Baldwin, J. T. and Lachlan, A. H. [1971], On strongly minimal sets, J. Symbolic Logic 36, 79–96.

Barker, E. J. [1988], Intrinsically Σ_{α}^{0}-relations, Ann. Pure Appl. Logic 39, 105–130.

Chang, C. C. and Keisler, H. J. [1990], Model Theory, Third edition, Studies in Logic and the Foundations of Mathematics 73, North-Holland, Amsterdam-New York.

Chisholm, J. [1990], Effective model theory vs. recursive model theory, Journal of Symb. Logic 55, 1168-1191.

Chisholm, J. [1990a], The complexity of intrinsically r.e. subsets of existentially decidable models, Journal of Symb. Logic 55, 1213-1232.

Cholak, P., Goncharov S. S., Khoussainov, B. and Shore R. A. [1999], Computably Categorical Structures and Expansions by Constants, Journal of Symb. Logic, to appear.

Ershov, Yu. L. [1977], Teoriya Numeratsii (Russian) [Theory of Numerations], Matematicheskaya Logika i Osnovaniya Matematiki. [Monographs in Mathematical Logic and Foundations of Mathematics] “Nauka”, Moscow.

Ershov, Yu. L. [1980], Problemy Razreshimosti i Konstruktivnye Modeli (Russian)[Decision Problems and Constructivizable Models], Matematicheskaya Logika i Osnovaniya Matematiki [Monographs in Mathematical Logic and Foundations of Mathematics] “Nauka”, Moscow.

Ershov, Yu. L. and Goncharov, S.S. eds. [1986], Logicheskaya Tetrad’ (Russian) [Logic Notebook], Nereshennye voprosy matematicheskoĭ logiki. [Unsolved problems in mathematical logic] Akad. Nauk SSSR Sibirsk. Otdel., Inst. Mat., Novosibirsk, 1986.

Ershov, Yu. L. and Goncharov, S. S. [1998], Elementary theories and their constructive models, in Ershov et al. [1998].

Ershov, Yu. L., Goncharov, S. S., Nerode, A. and Remmel, J. B. eds., Marek, V. W. assoc. ed. [1998], Handbook of Recursive Mathematics, Elsevier, New York.

Goncharov, S. S. [1973], Constructivizability of superatomic Boolean algebras (Russian), Algebra i Logika 12, 31-40; translation in Algebra and Logic 12 (1973), 17–22.

Goncharov, S. S. [1975], Autostability, and computable families of constructivizations (Russian), Algebra i Logika 14, 647–680; translation in Algebra and Logic 14 (1975), 392–409.

Goncharov, S. S. [1978], Constructive models of ℵ_{1}-categorical theories (Russian), Mat. Zametki (Akad Nauk SSR) 23, 885–888; translation in Math. Notes (Acad. Sci. USSR) 23 (1978), 486–487.

Goncharov, S. S. [1978a], Strong constructivizability of homogeneous models (Russian), Algebra i Logika 17, 363–388, 490; translation in Algebra and Logic 17 (1978), 247–263.

Goncharov, S. S. [1980], Autostability of models and abelian groups (Russian), Algebra i Logika 19, 23–44, 132; translation in Algebra and Logic 19 (1980), 13–27.

Goncharov, S. S. [1980a], The problem of the number of nonautoequivalent constructivizations (Russian), Alglebra i Logika 19, 621–639, 745; translation in Algebra and Logic 19 (1980), 401–414.

Goncharov, S. S. [1981], Groups with a finite number of constructivizations (Russian), Dokl. Akad. Nauk SSSR 256, 269–272; translation in Sov. Math. Dokl. 23 (1981), 58-61.

Goncharov, S. S. [1982], Limit equivalent constructivizations (Russian), in Mathematical Logic and the Theory of Algorithms, Trudy Inst. Mat. 2, “Nauka” Sibirsk. Otdel., Novosibirsk, 4–12.

Goncharov, S. S. [1997], Countable Boolean Algebras and Decidaility, Consultants Bureau, New York.

Goncharov, S. S. [1998], Autostable models and their algorithmic dimension, in Ershov et al. [1998].

Goncharov, S. S. and Dzgoev, V. D. [1980], Autostability of models (Russian), Algebra i Logika 19, 45–58; translation in Algebra and Logic 19 (1980), 28–37.

Goncharov, S. S. and Drobotun, B. N. [1989], The algorithmic dimension of nilpotent groups (Russian), Sibirsk. Mat. Zh. 30, 52–60, 225; translation in Siberian Math. J. 30 (1989), 210–217.

Goncharov, S. S. and Khoussainov, B. [1997], On the spectrum of the degrees of decidable relations (Russian), Dokl. Akad. Nauk 352, 301–303; translation in Dokl. Math. 55 (1997), 55-57.

Goncharov, S. S., Molokov, A. V. and Romanovski, N. S. [1989], Nilpotent groups of finite algorithmic dimension (Russian), Sibirsk. Mat. Zh. 30, 82–88; translation in Siberian Math. J. 30 (1989), 63–68.

Goncharov, S. S. and Nurtazin, A. T. [1973], Constructive models of complete decidable theories (Russian), Algebra i Logika 12, 125–142, 243; translation in Algebra and Logic 12 (1973), 67–77.

Griffor, E. ed. [1999], Handbook of Computability Theory, North-Holland. Harizanov, V. S. [1993], The possible Turing degree of the nonzero member

in a two element degree spectrum, Ann. Pure Appl. Logic 60, 1–30.

Harizanov, V. S. [1998], Pure computable model theory, in Ershov et al. [1998], Harizanov, V. S. [2000], Computable Model Theory, in preparation. Harrington, L. [1974], Recursively presentable prime models, J. Symbolic

Logic 39, 305–309.

Herwig, B., Lempp, S. and Ziegler, M. [1999], Proc. Amer. Math. Soc., to appear.

Hirschfeldt, D. [1999], Ph. D. Thesis, Cornell University.

Hirschfeldt, D., Khoussainov, B., Slinko, A. and Shore R. A. [1999], Degree spectra and computable categoricity in algebraic structures, in preparation.

Hodges, W. [1993], Model Theory, Encyclopedia of Mathematics and its Applications 42, Cambridge University Press, Cambridge, England.

Kalantari, I. [1998], A bibliography of recursive algebra and model theory, in Ershov et al. [1998].

Khisamiev, N. G. [1974], Strongly constructive models of a decidable theory (Russian), Izv. Akad. Nauk Kazah. SSR Ser. Fiz.-Mat., 83–84.

Khoussainov, B., Nies, A. and Shore, R. A. [1997], Computable models of theories with few models, Notre Dame J. Formal Logic 38, 165–178.

Khoussainov, B. and Shore, R. [1998], Computable Isomorphisms, Degree Spectra of Relations, and Scott Families, Ann. of Pure and Applied Logic, to appear.

Kudaibergenov, K. Ž. [1979], A theory with two strongly constructible models (Russian), Algebra i Logika 18, 176–185, 253; translation in Algebra and Logic 18 (1979), 111–117.

Kudaibergenov, K. Ž. [1980], Constructivizable models of undecidable theories (Russian), Sibirsk. Mat. Zh. 21, 155–158, 192.

Kudinov, O. V. [1996], An autostable 1-decidable model without a computable Scott family of ∃-formulas (Russian), Algebra i Logika 35 , 458–467, 498; translation in Algebra and Logic 35 (1996), 255–260.

LaRoche, P. [1977], Recursively represented Boolean algebras, Notices Amer. Math. Soc. 24, A-552.

Manasse, M. [1982], Techniques and Counterexamples in Almost Categorical Recursive Model Theory, Ph. D. Thesis, University of Wisconsin, Madison.

Metakides, G. and Nerode, A. [1979], Effective content of field theory, Ann. Math. Logic 17, 289–320.

Millar, T. [1978], Foundations of recursive model theory, Ann. Math. Logic 13, 45–72.

Millar, T. [1979], Complete, decidable theory with two decidable models, J. Symbolic Logic 44, 307–312.

Millar, T. [1983], Omitting types, type spectrums, and decidability, J. Symbolic Logic 48, 171–181.

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

Millar, T. [1999], Abstract recursive model theory, in Griffor [1999]. Morley, M. [1976], Decidable models, Israel J. Math. 25, 233–240. Nurtazin, A. T. [1974], Strong and weak constructivizations and computable

families (Russian), Algebra i Logika 13, 311–323, 364; translation in Algebra and Logic 13 (1974), 177–184.

Remmel, J. B. [1981], Recursive isomorphism types of recursive Boolean algebras, J. Symbolic Logic 46, 572–594.

Remmel, J. B. [1981a], Recursively categorical linear orderings, Proc. Amer. Math. Soc. 83, 387–391.

Robinson, R. M. [1950], An essentially undecidable axiom system, Proc. Intl. Cong. Math., Cambridge 1950, v. 1, 729-730.

Sacks, G. E. [1963], On the degrees less than 0′, Ann. of Math. (2) 77, 211– 231.

Selivanov, V. L. [1976], Numerations of families of general recursive functions, Algebra and Logic 15, 205-226, 1976; translation in Algebra and Logic 15 (1976), 128–141.

Shoenfield, J. R. [1971], Degrees of Unsolvability, Mathematical Studies 2, North-Holland, Amsterdam.

Tennenbaum, S. [1959], Non-Archimedian models of arithmetic, Notices Amer. Math. Soc. 6, 270.

Vaught, R. L. [1961], Denumerable models of complete theories, in Infinitistic Methods, Proceedings of the Symposium on the Foundations of Mathematics, Warsaw 2-9, September 1959, Pegamon Press, Oxford, 301-321.