Recursive Models of Theories with Few Models

Bakhadyr Khoussainov^{∗}

Mathematics Department, Cornell University, Ithaca NY 14850 USA

Andre Nies^{†}

Mathematics Department, The University of Chicago, IL 60637 USA

Richard A. Shore ^{§}

Mathematics Department, Cornell University, Ithaca NY 14853 USA

1 Introduction

We begin by presenting some basic definitions from effective model theory. A recursive structure is one with a recursive domain and uniformly recursive atomic relations. Without lost of generality, we can always suppose that the domain of every recursive structure is the set of all naturall numbers ω and that its language does not contain function symbols. If a structure A is isomorphic to a recursive structure B, then A is recursively presentable and B is a recursive presentation of A. Let σ be an effective signature. Let σ_{0} ⊂ σ_{1} ⊂ σ_{2} ⊂ … be an effective sequence of finite signatures such that σ = ⋃_{t} σ_{t}. It is clear that a structure A of signature σ is recursive if and only if there exists an effective sequence A_{0} ⊂ A_{1} ⊂ A_{2} ⊂ … of finite structures such that for each i the domain of A_{i} is {0, …, t_{i}}, the function i → t_{i} is recursive, A_{i} is a structure of signature σ_{i}, A_{i+1} is an expansion and extension of A_{i}, and the structure A is the union ⋃_{i} A_{i}. The domain of A is denoted by A. For a structure A of signature σ we write P A to denote the interpretation of the predicate symbol P ∈ σ in A. When it does not cause confusion, we write P instead of P A. In this paper we only deal with finite or countable structures.

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

†Partially supported by MSI, Cornell University and the NSF grant DMS 9500983

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

A basic question in recursive model theory is whether a given first order theory T has a recursive model. A standard Henkin type construction shows that each decidable theory has a recursive model. Moreover the satisfaction predicate for this model is recursive. Such recursive models are called decidable. Constructing recursive (decidable) presentations for specific models of T has been an intensive area of research in effective model theory [2], [9], [4]. For example, the recursiveness of homogeneous models, in particular of prime and saturated models has been well studied. In [2], [9] it is proved that the saturated model of T has a decidable presentation if and only if there exists a procedure which uniformly computes the set of all types of T. Goncharov [4] and Harrington [8] gave criteria for prime models to have decidable presentations. It is also known that the decidability of the saturated model of T implies the existence of a decidable presentation of the prime model of T [2], [12]. Thus, a general question arises as to how recursive models of undecidable theories behave in comparison to recursive models of decidable theories. In this paper we investigate recursive models of complete theories with “few countable models” (M. Morley [12]). Examples of such theories are theories with countably many countable models such as ω_{1}–categorical theories and theories with finitely many countable models (Ehrenfeucht theories).

In [1] Baldwin and Lachlan developed the theory of ω_{1}–categoricity in terms of strongly minimal sets. They settled affirmatively Vaught’s conjecture for ω_{1}–categorical complete theories by proving that each complete ω_{1}–categorical theory has either exactly one or ω many countable models up to isomorphisms. Their paper also shows that all the countable models of any ω_{1}–categorical theory T can be listed in an ω + 1 chain:

chain(T) : A_{0} ⪯ A_{1} ⪯ … ⪯ A_{n} ⪯ … A_{ω}

of elementary embeddings with A_{0} and A_{ω} being the prime and saturated models of T, respectively [1]. The results of Baldwin and Lachlan lead one to investiagte the effective content of ω_{1}–categorical theories and their models. Based on the theory developed by Baldwin and Lachlan, Harrington [8] and Khissamiev [6] proved that every countable model of each decidable ω_{1}-categorical theory T has a decidable presentation.

This result of Harrington and Khissamiev motivated the study of recursive models of ω_{1}–categorical undecidable theories. In 1972, S. Goncharov [3] constructed an example of an ω_{1}–categorical but not ω–categorical theory T for which the only model with a recursive presentation is the prime model, that is the first element of chain(T). Later in 1980, K.Kudeiberganov [7] modified Goncharov’s construction to provide an example of an ω_{1}–categorical but not ω–categorical theory T with exactly n recursive models. These models are the first n elements of chain(T). These results lead to the following two questions which have remained open:

Question 1.1 (S.Goncharov [5]) If an ω_{1}–categorical but not ω–categorical theory T has a recursive model, is the prime model of T recursively presentable?

Question 1.2 If all models A_{0}, A_{1}, …, A_{i}, …, i ∈ ω, in chain(T) of an ω_{1}–categorical but not ω–categorical theory T, have recursive presentations, is the saturated model A_{ω} of T recursively presentable?

The above result of Harrington and Khissamiev also inspired Nerode to ask whether the hypothesis of ω_{1}–categoricity of T can be replaced by the hypothesis that T has only finitely many countable models, that is whether every countable model of a decidable Ehrenfeucht theory has a decidable presentation. Morley noted that if the countable saturated model of a such theory is decidable, then the theory has at least three recursive models [12]. Lachlan answered Nerode’s question by giving an example of a decidable theory with exactly 6 models of which only the prime one has a recursive presentation. Later, for each natural number n > 3, Peretyatkin constructed an example of decidable theory with exactly n models such that the prime model of the theory is recursive and none of the other models of the theory has recursive presentations [13]. In [7] Kudeiberganov constructed an example of a theory with exactly 3 models such that the theory has only one recursive model and that model is prime. The saturated model of the theory can not be decidable since, otherwise, all 3 model of the theory would have recursive presentations. These results lead Morley to ask as whether any countable model of a decidable Ehrenfeucht theory T with a decidable saturated model has a decidable presentation [12]. There is a natural anolog of this question for recursive models:

Question 1.3 If the saturated model of an Ehrenfeucht theory is recursive, does there exist a nonsaturated, recursive model of the theory?

In this paper we answer the above three questions by providing appropriate counterexamples. Our examples of models which answer the first two questions have infinite signatures. However these questions remain open for theories of finite signatures.

The general problem suggested by these results is to characterize the spectrum of recursive models of ω_{1}–categorical theories: Let T be an ω_{1}–categorical but not ω–categorical complete theory. Consider chain(T). The spectrum of recursive models of T, denoted by SRM(T), is the set

{i ≤ ω| the model A_{i} in chain(T) has a recursive presentation } .

Problem. Describe all subsets of ω which are of the form SRM(T) for some ω_{1}–categorical theory T.

The result of Harrington and Khissamiev shows that if T is decidable, then SRM(T)= ω ⋃{ω}. The results of Goncharov and Kudeiberganov show that the sets {1, …, n}, where n ∈ ω, are spectra of recursive models of ω_{1}–categorical theories. In this paper we show that the sets ω − {0} ⋃{ω} and ω are also spectra of recursive models of ω_{1}–categorical theories.

2 Main Results

The results of this paper are based on the idea of coding Σ_{2}^{0} or Π_{2}^{0} sets with certain recursion-theoretic properties into ω_{1}–categorical theories. Our first result is the following theorem which answers Question 1.1.

Theorem 2.1 There exists an ω_{1}–categorical but not ω categorical theory T such that all the countable models of T except its prime model have recursive presentations (and so SRM(T)= ω − {0} ⋃{ω}).

Before proving this theorem we would like to give the basic idea of our proof. For an infinite subset S ⊂ ω we construct a structure A_{S} of infinite signature (P_{0}, P_{1}, P_{2}, …), where each P_{i} is a binary predicate symbol. We will show that the theory T_{S} of the structure A_{S} is ω_{1}–categorical and A_{S} is the prime model of T_{S}. The countable models of T_{S} will have the following property: Every non prime model A of T_{S} has a recursive presentation if and only if the set S is a Σ_{2}^{0}–set. The existence of a recursive presentation of the prime model will imply that the set S has a certain recursion-theoretic property. Our recursion-theoretic lemma (Lemma 2.1.) will show that there exists a Σ_{2}^{0}–set S which does not have this properties.

The Construction of Cubes. Let n be a nonzero natural number. Let σ_{n} = (P_{0}, …, P_{n−1}) be a signature such that each P_{i} is a binary predicate symbol. For each nonzero natural number n we define a finite structure of signature σ_{n}, called an n–cube, as follows.

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.

Suppose that n-cubes have been defined. Let A = (A, P A_{0}, …, P A_{n−1}) and B = (B, P B_{0}, …, P B_{n−1}) be n-cubes such that A ⋂ B = ∅. These two n–cubes are isomorphic. Let f be an isomorphism from A to B. Then a n + 1–cube C_{n+1} is

(A ⋃ B, P A_{0} ⋃ P B_{0}, …, P A_{n−1} ⋃ P B_{n−1}, P_{n}),

where P_{n}(x, y) holds if and only if f(x) = y or f^{−1}(x) = y. It follows that we can naturally define an ω–cube C_{ω} = ⋃_{i∈ω} C_{i} as an increasing union of n–cubes formed in this way.

An ω–cube C_{ω} is a structure of the infinite signature σ = (P_{0}, P_{2}, …). From these definitions of cubes it follows

Claim 2.1 For each n ≤ ω any two n–cubes are isomorphic. □

Each binary predicate P_{i} in any cube A is a partial function and sets up a one-to-one mapping from dom(P_{i}) onto range(P_{i}). Therefore we can also write P_{i}(x) = y instead P_{i}(x, y). Moreover by the definition of P_{i}, dom(P_{i}) = range(P_{i}).

Construction of A_{S}. For each natural number n ∈ ω consider an n– cube denoted by A_{n}. Assume that A_{n} ⋂ A_{t} = ∅ for all n ≠ t. Let S be a subset of ω. Define a structure A_{S} by

A_{S} = ⋃_{n∈S} A_{n}.

Thus the structure A_{S} is the disjoint union of all cubes A_{n}, n ∈ S, with the natural interpretations of predicate symbols of signature σ. Let T_{S} be the theory of the structure A_{S}.

Claim 2.2 If S is an infinite set, then the theory T_{S} is ω_{1} categorical but not ω–categorical.

Proof. The model A_{S} satisfies the following list of statements. It is easy to see that this list of statements can be written as an (infinite) set of statements in the first order logic.

1. ∀x∃yP_{0}(x, y) and for each n, P_{n} is a partial one to one function.

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}, for all elements 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. Then for each n ∈ S, M must have an n–cube which is not contained in an n + 1–cube. Moreover if an x ∈ M does not belong to any n–cube for n ∈ S, then x is in an ω–cube. Note that each ω–cube is countable. Using the previous claim it can be seen that any two models which satisfy the above list of axioms are isomorphic if and only if these two models have the same number of ω–cubes.

Suppose that M_{1} and M_{2} are models of T_{S} and their cardinalities are ω_{1}. Since each cube is a countable set it follows that the number of ω–cubes in M_{1} and M_{2} is ω_{1}. Therefore the models M_{1} and M_{2} are isomorphic. Hence T_{S} is an ω_{1}–categorical but not ω–categorical theory. □

Claim 2.3 The set S is in Σ_{2}^{0} if and only if every nonprime model of T_{S} possesses a recursive presentation.

Proof. Each ω–cube has a recursive presentation. Therefore it suffices to prove that S ∈ Σ_{2}^{0} if and only if the nonprime model M of T_{S} with exactly one ω–cube has a recursive presentation. If M is recursive, then s ∈ S if and only if ∃x∃y∀z(P_{s}(x, y)&¬P_{s+1}(x, z)). Therefore S ∈ Σ_{2}^{0}.

Now suppose that S ∈ Σ_{2}^{0}. There exists a recursive function f such that for every n ∈ ω, n ∈ S if and only if W_{f(n)} is finite. We construct an effective sequence

M_{0} ⊂ M_{1} ⊂ M_{2} ⊂ …

of finite structures by stages such that

1. The model M is isomorphic to ⋃_{n} M_{n},

2. Each M_{t} has exactly t + 1 cubes and the function t → card(M_{t}) is recursive,

3. Each M_{t} is a structure of signature (P_{0}, …, P_{n_{i}}), where i → n_{i} is a recursive function.

Stage 0. Construct a 1–cube M_{0} and mark this structure with the symbol □_{ω}.

Stage s+1. Suppose that M_{s} has been constructed as the disjoint union

M_{s,0} ⋃ M_{s,1} ⋃ … ⋃ M_{s,s} ⋃ M_{s,ω},

where each M_{s,i}, i ≤ s is a i–cube, and M_{s,ω} is the cube marked with □_{ω} at the previous stage. Compute W_{f(0),s+1}, … W_{f(s),n+1}, W_{f(s+1),s+1}. For each i ≤ s + 1 define M_{i,s+1} and M_{s+1,ω} as follows:

1. If W_{f(i),s+1} = W_{f(i),s}, then let M_{i,s+1} = M_{i,s}.

2. If W_{f(i),s+1} ≠ W_{f(i),s}, then construct a new i–cube and let M_{i,s+1} be this new cube.

3. Extend the cube M_{s,ω} to a finite cube denoted by M_{s+1,ω} such that for each i ≤ s if W_{f(i),s+1} ≠ W_{f(i),s}, then M_{s+1,ω} contains M_{s,i}.

Let M_{s+1} be M_{s+1,0} ⋃ M_{s+1,1} ⋃ … ⋃ M_{s+1,s+1} ⋃ M_{s+1,ω}. Define

M_{ω} = ⋃_{s} M_{s}.

By the construction, the structure M_{ω} is recursive. The construction of M_{ω} guarantees that the structure M_{ω} is isomorphic to the model M. □

Now we need the following definition and recursion theoretic lemma. We will prove the lemma at the end of this section.

Definition 1 A function f is limitwise monotonic if there exists a recursive 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 2.1 (Recursion Theoretic Lemma) There exists a Δ_{2}^{0} set A which is not the range of any limitwise monotonic function. □

Proof of Theorem 2.1. We need the following

Lemma 2.2 If the prime model A_{S} is recursive, then the set S is the range of a limitwise monotonic function.

Proof. Let x ∈ A_{S}. Note that each cube in A_{S} is finite. Define ϕ(x) to be an s such that x is in an s–cube and this cube is not contained in a s + 1–cube. It is clear that ϕ witnesses that S is the range of a limitwise monotonic function. □

By the Recursion Theoretic Lemma there exists an S ∈ Δ_{2}^{0} which is not the range of any limitwise monotonic function. Consider the structure A_{S} and its theory T_{S}. The claims above and Lemma 2.2 show that T_{S} is the required theory and so prove Theorem 1.1. □

Now we give an answer to Question 1.2. The idea of our proof is the following. We take a Π_{2}^{0} but not Σ_{2}^{0} set S and code this set into a theory T_{S}.

The language of T_{S} will contain infinitely many unary predicates P_{0}, P_{1}, …, and infinitely many predicates of arity n for each n ∈ ω. We will prove that T_{S} is an ω_{1}–categorical but not ω–categorical theory. Our construction of T_{S} guarantees that all the countable models of T_{S}, except the saturated model, have recursive presentations. The existence of a recursive presentation for the saturated model will imply that the set S is a Σ_{2}^{0} set. This will contradict with the choice of S.

Theorem 2.2 There exist an ω_{1}–categorical but not ω–categorical theory T such that all the countable models of T except the saturated model, have recursive presentations.

Proof. We construct a structure of the infinite signature

(P_{0}, P_{1}, …, R_{1,0}, R_{1,1}, R_{1,2}, …, R_{k,0}, R_{k,1}, R_{k,2}, …),

where each P_{i} is a unary predicate and each R_{k,s} is a predicate of arity k.

Let S be a (Π_{2}^{0} \ Σ_{2}^{0}) set. There exists a recursive predicate H such that n ∈ S if and only if ∀x∃yH(x, y, n) holds. Below we present a step by step construction of a recursive structure denoted by A_{S} and prove that the theory T_{S} of this structure satisfies the requirements of the theorem.

Stage 0. Let A_{0} = ({0}, P_{0}), where P_{0}(0) holds.

Stage t+1. The domain A_{t+1} of A_{t+1} is {0, …, t + 1}. The signature of A_{t+1} is

σ_{t+1} = (P_{0}, …, P_{t+1}, R_{1,0}, …, R_{1,t+1}, …, R_{t+1,0}, …, R_{t+1,t+1}).

For each i ≤ t + 1 let P_{i}(x) hold if and only if x ≥ i. For k, s ≤ t + 1, let R_{k,s}(x_{1}, …, x_{k}) hold if and only if x_{1}, …, x_{k} are pairwise different and for the maximal number j ≤ t + 1 such that all P_{j}(x_{1}), …, P_{j}(x_{k}) hold we have ∀n ≤ s∃m ≤ jH(n, m, k). We have defined the model A_{t+1}.

Thus we have an effective sequence A_{0}, A_{1}, A_{2} … of finite structures such that each A_{i+1} is an extension and expansion of A_{i}. Therefore we can define A_{S} by

A_{S} = ⋃_{i} A_{i}.

It is clear that the model A_{S} is recursive.

Claim 2.4 The theory T_{S} of the model A_{S} is a ω_{1}–categorical but not ω– categorical.

Proof. The model A_{S} satisfies the following list of properties which can be written as an infinite set of stetements in the language of the first order logic.

1. For all x if P_{i+1}(x) holds, then P_{i}(x) also holds. Moreover ∀xP_{0}(x) is true.

2. For each i ∈ ω there exists a unique x such that P_{i}(x)&¬P_{i+1}(x), i ∈ ω.

3. For all k, s ∈ ω, if R_{k,s}(x_{1}, …, x_{k}) holds, then x_{1}, …, x_{k} are pairwise distinct.

4. Let k ∈ S. For every s ∈ ω there exists a j ∈ ω such that ∀n ≤ s∃m < jH(n, m, s). Let j_{s} be the minimal number which has this property. Then for all pairwise distinct x_{1} … x_{k} if P_{j_{s}}(x_{1})& … P_{j_{s}}(x_{k}) holds, then R_{k,s}(x_{1}, …, x_{k}) holds.

5. Let k ∉ S. There exists an s_{0} such that for all s ≥ s_{0} and for all x_{1}, …, x_{k}, R_{k,s}(x_{1}, …, x_{k}) does not hold.

Let A be a model of T_{S}. Consider the set ⋂_{i} P A_{i}. For any two elements a, b ∈ ⋂_{i} P A_{i} there exists an automorphism α of the model A such that α(a) = b. Thus a proof of ω_{1}–categoricity can be based on the following observation. Two models B and C of the theory T_{S} are isomorphic if and only if the cardinalities of the sets ⋂_{i} P B_{i} and ⋂_{i} P C_{i} are equal. Hence if B and C are models of cardinality ω_{1}, then both ⋂_{i} P B_{i} and ⋂_{i} P C_{i} have exactly ω_{1} elements. It follows that B and C are isomorphic. □

¿From the proof of Claim 2.4, it follows that if B is a countable unsaturated model of the theory T_{S}, then ⋂ P B_{i} has a finite number of elements.

Claim 2.5 If C is a countable and unsaturated model of T_{S}, then C has a recursive presentation.

Proof. Let C be a countable, unsaturated model of T_{S}. The set ⋂_{i} P C_{i} has a finite number of elements, say n. We construct a recursive presentation of C by stages.

Let a_{1}, …, a_{n} be new symbols. In our construction of a recursive presentation A of C we put the elements a_{1}, …, a_{n} into ⋂_{i} P A_{i}. Let p_{1}, …, p_{n} be the all elements of S ⋂{0, 1, …, n}.

Stage 0. Define A_{0} = ({0, a_{1}, …, a_{n}}, P_{0}), letting P_{0}(0), P_{0}(a_{1}), …, P_{0}(a_{n}) hold.

Stage t+1. The domain A_{t+1} of A_{t+1} is {0, …, t + 1, a_{1}, …, a_{n}}. The signature of the A_{t+1} is

σ_{t+1} = (P_{0}, …, P_{t+1}, R_{1,0}, …, R_{1,t+1}, …, R_{t+1,0}, …, R_{t+1,t+1}).

For each i ≤ t + 1 let P_{i}(x) hold if and only if x ≥ i or x ∈ {a_{1}, …, a_{n}}. For k, s ≤ t + 1, let R_{k,s}(x_{1}, …, x_{s}) hold if and only if one of the followings holds:

1. k ∈ {p_{1}, …, p_{n}}, (x_{1}, …, x_{k}) ∈ {a_{1}, …, a_{n}}^{n}, and x_{1}, …, x_{k} are pairwise distinct.

2. {x_{1}, …, x_{k}} \ {a_{1}, …, a_{n}} ≠ ∅, the elements x_{1}, …, x_{k} are pairwise different, and for the maximal number j ≤ t + 1 such that all P_{j}(x_{1}), …, P_{j}(x_{k}) hold we have ∀n ≤ s∃m ≤ jH(n, m, k).

Thus this stage defines the structure A_{t+1}. For each i ∈ ω A_{i+1} is an extension and expansion of A_{i}. Define A by A = ⋃_{i} A_{i}. It is clear that the structure A is recursive and isomorphic to the model C. □

Claim 2.6 The countable saturated model B of T does not have a recursive presentation.

Proof. Suppose that B is recursive. Since B is saturated the number of elements in ⋂_{i} P B_{i} is infinite. It can be checked that for each k ∈ ω, k ∈ S if and only if there exist different elements y_{1}, …, y_{k} from ⋂_{i} P B_{i} such that for all s ≥ 1, R_{k,s}(y_{1}, …, y_{k}) holds. The set S would then be a Σ_{2}^{0}–set. This contradicts with our assumption that S ∈ Π_{2}^{0} \ Σ_{2}^{0}. □

These claims prove Theorem 3. □

Thus the above theorems prove the following corollary about spectra of recursive models (SRM) of ω_{1} categorical theories.

Corollary 2.1 1. There exists an ω_{1}–categorical but not ω categorical theory T such that SRM(T) = ω − {0} ⋃{ω}.

2. There exists an ω_{1}–categorical but not ω categorical theory T such that SRM(T) = ω. □

In the next theorem, which answers Question 1.3, we provide an example of a theory T_{S} with exactly 3 countable models of which only the saturated model is recursively presentable. To prove that T_{S} has exactly 3 countable models, we use the known ideas which show that the theory of the model (Q, ≤, c_{0}, c_{1}, …), where ≤ is the linear ordering of rationals, and the constants are such that c_{0} > c_{1} > c_{2} > …, has exactly 3 countable models [14].

Theorem 2.3 There exists a theory T with exactly 3 countable models such that the only model of T which has a recursive presentation is the saturated model.

Proof. Let Q be the set of all rational numbers. For each cardinal number m ∈ ω ⋃{ω} define a structure Q_{0}(m) as follows. The domain of the structure is

{q ∈ Q|1 ≤ q} ⋃{c_{q,1}, …, c_{q,m}|q ∈ Q},

where {c_{q,i}|q ∈ Q, 1 ≤ i ≤ m} is a set of new elements. The signature of the model is (≤, f), where ≤ is a binary predicate and f is a unary function symbol. The predicate ≤ and the function f are defined as follows. For all x, y we have x ≤ y if and only if x, y ∈ Q and x is less or equal to y as rational numbers. For all z, y define f(z) = y if and only if for some rational number q, y = q and z ∈ {c_{q,1}, …, c_{q,m}} or y = z = q. Let Q(m) be the structure obtained from Q_{0}(m) by removing the elements 1, c_{1,1}, …, c_{1,m} from the domain of Q_{0}(m).

If A and B are isomorphic copies of the structures Q_{0}(n) and Q_{0}(m), respectively, and A ⋂ B = ∅, then one can naturally define the isomorphism type of the structure Q_{0}(n) + Q_{0}(m) as follows. The domain of the new structure is A ⋃ B. The predicate ≤ in the new structure is the least partial ordering which contains the partial orderings of A, the partial ordering of B, and the relation {(x, y)|x ∈ A&fA(x) = x& y ∈ B&fB(y) = y}. The unary function f in the new structure is the union of the unary operations of the first and the second structures.

If n_{0}, n_{1}, n_{2}, …, n_{i}, …, i < ω is a sequence of natural numbers, then as above we can define the structure

Q_{0}(n_{0}) + Q_{0}(n_{1}) + Q_{0}(n_{2}) + ….

Let S be a set in Δ_{2}^{0} which is not the range of a limitwise monotonic function. There exists a recursive function g such that, for all n h(n) = lim_{s} g(n, s) exists and range(h) = S. Consider the model Q_{0}(S) defined by

Q_{0}(h(0)) + Q_{0}(h(1)) + Q_{0}(h(2)) + ….

Define the theory T_{S} to be the theory of the structue Q_{0}(S).

Claim 2.7 . The theory T_{S} has exactly three countable models.

Proof. The first model of T_{S} is Q_{0}(S). This model is the prime model of the theory T_{S}. The second model of T_{S} is

Q′(S) = Q_{0}(h(0)) + Q_{0}(h(1)) + Q_{0}(h(2)) + … + Q_{0}(ω).

The third model M of T_{S} is

Q(h(0)) + Q_{0}(h(1)) + Q_{0}(h(2)) + … + Q(ω).

These structures are indeed models of T_{S}. To see this, note that Q_{0}(S) is a submodel of Q′(S), and Q′(S) is a submodel of M. It can be checked that for any formula ∃xϕ(x, a_{1}, …, a_{n}) and all a_{1}, …, a_{n} ∈ Q_{0}(S) (a_{1}, …, a_{n} ∈ Q′(S)) if the formula ∃xϕ(x, a_{1}, …, a_{n}) is true in Q′(S) (in M) then there exists a b ∈ Q_{0}(S) ( b ∈ Q′(S) ) such that ϕ(b, a_{1}, …, a_{n}) is true in Q_{0}(S) (in Q′(S)). Therefore the embeddings are elementary.

We have to prove that any countable model of T_{S} is isomorphic to one of the three models described above. Let A be a model of T_{S}. For each i ∈ ω we define by induction an element a_{i} ∈ A as follows.

The element a_{0} is the minimal element with respect to the partial ordering in A. Note that the set {b|b ≠ a_{0}&f(b) = a_{0}} has exactly h(0) elements. Also put k_{0} = 0.

Suppose that the elements a_{0}, …, a_{i−1} ∈ A and the numbers k_{0}, …, k_{i−1} have been defined. Let k_{i} be the least element such that h(k_{i}) ≠ h(k_{j}) for j = 1, …, i − 1. The element a_{i} is the one such that the following properties hold:

1. The set {b|b ≠ a_{i}&f(b) = a_{i}} has exactly h(k_{i}) elements,

2. For each x < a_{i} the cardinality of the set {b|b ≠ x&f(b) = x} is in {h(k_{0}), …, h(k_{i−1}}.

Consider the sequence a_{0}, a_{1}, a_{2}, . . .. Clearly a_{0} < a_{1} < a_{2} < . . .. Thus we have three cases:

Case 1. lim_{i} a_{i} does not exists and for any x ∈ A such that f(x) = x there exists an i such that a_{i} ≥ x,

Case 2. lim_{i} a_{i} exists,

Case 3. lim_{i}a_{i} does not exists and there exists an x such that f(x) = x and x ≥ a_{i} for all a_{i}.

In the first case A is isomorphic to Q_{0}(S). In the second case A is ismorphic to Q′(S). In the third case A is isomorphic to M. Note that Q_{0}(S) is the prime model. The model Q′(S) is not saturated since it does not realize the type containing {x > a_{i}&c > x|i ∈ ω}, where c = lim_{i}a_{i}. Hence M is the saturated model of T_{S}. □

Claim 2.8 The unsaturated models of the theory T_{S} do not have recursive presentations.

Proof. Consider the prime model Q_{0}(S). Suppose Q_{0}(S) is a recursive model. Then it can be easily checked that the set S is the range of a limitwise monotonic function. This contradicts the assumption on S. If the other unsaturated model

Q′(S) = Q_{0}(h(0)) + Q_{0}(h(1)) + Q_{0}(h(2)) + … + Q_{0}(ω)

were recursive, then Q_{0}(S) would be a recursively enumerable submodel of the model Q′(S). Hence Q_{0}(S) would have a recursive presentation. This is again a contradiction. □

Claim 2.9 The saturated model M of the theory T has a recursive presentation.

Proof. We present a constuction of the saturated model M by stages. The construction will clearly show that the saturated model has a recursive presentation.

Stage 0. Consider the structure Q_{0}(g(0, 0)) + Q(ω). Denote this model by A_{0}.

Stage n+1. Suppose that A_{n} has been defined and is isomorphic to

Q_{0}(g(0, n)) + … + Q_{0}(g(n, n)) + Q(ω).

Compute g(0, n + 1), …, g(n + 1, n + 1). Let i ≤ n be the minimal number such that g(i, n) ≠ g(i, n + 1). A_{n} can be extended to a structure A_{n+1} isomorphic to

Q_{0}(g(0, n+1))+…+Q_{0}(g(i−1, n+1))+Q_{0}(g(i, n+1))+… Q_{0}(g(n+1, n+1))+Q(ω).

To see this, take the substructure

Q_{0}(g(i, n)) + … Q_{0}(g(n, n)) + Q(ω)

of A_{n}; extend this substructure to Q(ω); insert the new structure

Q_{0}(g(i, n + 1)) + … Q_{0}(g(n + 1, n + 1))

between the structures Q_{0}(g(0, n + 1)) + … + Q_{0}(g(i − 1, n + 1)) and the extended structure Q(ω). The structure obtained in this way is A_{n+1}.

Thus we have the sequence

A_{0} ⊂ A_{1} ⊂ A_{2} ⊂ ….

Define A_{ω} = ⋃_{i} A_{n}. It is easy to see that the model A_{ω} is ismorphic to

Q_{0}(h(0)) + Q_{0}(h(1)) + … + Q_{0}(h(n)) + … + Q(ω).

Now it is clear that the above description can be effectivized. □

These claims prove the theorem. □

Finally we have to prove the promissed recursion theoretic lemma.

Proof of the Recursion Theoretic Lemma. Let ϕ_{e}(x, t), e ∈ ω, be a uniform enumeration of all partial recursive functions ϕ such that for all t′ ≥ t if ϕ(x, t′) is defined, then ϕ(x, t) is defined and ϕ(x, t) ≤ ϕ(x, t′). At stage s of our construction we define a finite set A_{s} in such a way that A(y) = lim_{s}A_{s}(y) exists for all y. We satisfy the requirement R_{e} asserting that, if f_{e}(x) = lim_{t}ϕ_{e}(x, t) < ω for all x, then range(f_{e}) ≠ A.

The strategy for a single R_{e} is as follows: At stage s pick a witness m_{e}, enumerate m_{e} into A (i.e. 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) requrement R_{i} since it maybe the case that m_{i} = ϕ_{e}(x, t′) for some t′ > t_{0}. However, if f_{e}(x) ↓, then this holds permanently for just one number, and if f_{e}(x) ↑, then the restriction is transitory for each number. So each lower priority R_{i} will be able to choose a stable witness at some stage.

Construction. At stage s we try to determine the values of parameters m_{e}, x_{e}, and n_{e} = ϕ_{e}(x_{e}, s) for R_{e}. Each parameter may remain undefined. Moreover we define the approximation A_{s} to A at stage s.

Sate 0. Let A_{0} = ∅, and declare all parameters to be undefined.

Stage s. For each e = 0, … s − 1 in turn go through substage e by performing the following actions.

1. If m_{e} is undefined, let m_{e} be the least number in ω^{[e]} greater than all m_{i} (i < e) which is not equal to any n_{i}. Let A_{s}(m_{e}) = 1 and proceed to the next sustage, or to stage s + 1 if e = s − 1.

2. If x_{e} is undefined and ϕ_{e}(x, s) = m_{e} for some x, let x_{e} = x, n_{e} = m_{e}, and A_{s}(n_{e}) = 0, and proceed to the next stage s + 1 if e = s − 1.

3. Let n_{e} = ϕ_{e}(x_{e}, s) and A_{s}(n_{e}) = 0. If n_{e} = m_{i} for some i > e, declare all the parameters of the R_{j}, j ≥ i, to be undefined.

For each y, if A_{s}(y) is not determined by the end of stage s, then assign to A_{s}(y) its previous value A_{s−1}(y). The stage is now completed.

Now we will verify that the construction succeeds.

Claim 2.10 Each m_{e} is defined and is constant from some stage on.

Proof. Suppose inductively that the claim holds for each i < e. Let s_{0} be a stage such that each m_{i} has reached its limit for i < e, and if x_{i} ever becomes defined after s_{0}, and lim_{s} n_{i,s} < ∞, then the limit has been reached at s_{0}. Moreover, let k ≥ e be the least number which does not equal any of these limits and is greater than all m_{i} for i < e. Also suppose that n_{i,s_{0}} > k if lim_{s}n_{j,s} = ∞, (j < e). If m_{e} is cancelled after stage s_{0}, then m_{e} = k is permanent from the next stage on. This proves the claim.

Claim 2.11 For each y, lim_{s} A_{s}(y) exists. Therefore the set A = lim_{s} A_{s} is a Δ_{2}^{0}–set.

Proof. Suppose that y ∈ ω^{[e]}, and let s_{0} be a stage at which m_{e} has reached its limit. Since y can only be enumerated into A if y = m_{e}, after stage s_{0} A(y) can change at most once. This proves the claim.

Claim 2.12 Suppose that f_{e}(x) = lim_{t} ϕ_{e}(x, t) exists for each x. Then A ≠ range(f_{e}).

Proof. Suppose that A = range(f_{e}). Let s_{0} be the stage at which m_{e} reaches its limit. Then at some stage s > s_{0} we must reach the second instruction of the construction, otherwise A(m_{e}) = 1 but m_{e} ∉ range(f_{e}). Suppose that ϕ_{e}(x, s) = m_{e} for the minimal s ≥ s_{0} at which we reach the second instruction of the construction. It follows that for t ≥ s, n_{e} = ϕ_{e}(x, t) and A_{t}(n_{e}) = 0. So A(f_{e}(x)) = 0. This contradiction proves the claim and hence the lemma. □

Remark. It is possible to make A d.r.e, i.e. A = B − C for some r.e. sets B, C. To do so, we have to set aside an interval I_{e}, roughly of size 2^{e}, for R_{e}, I_{0} < I_{1} < . . .. As a first choice for m_{e}, we take the maximal element of I_{e}, and then we proceed downward. The point is that, if R_{e} is injured by R_{i}, i < e, via n_{i} = m_{e}, then all further values of n_{i} are above the next values of m_{e} (unless R_{i} injured itself later). Obviously A can be neither r.e. nor co-r.e.

References

[1] J. Baldwin, A. Lachlan, On Strongly Minimal Sets, Journal of Symbolic Logic, v.36, no 1, 1971.

[2] Yu. Ershov, Constructive Models and Problems of Decidability, Moskow, Nauka, 1980.

[3] S.Goncharov,Constructive Models of ω_{1}–categorical Theories, Matematicheskie Zametki, v.23, no 6, 1978.

[4] S. Goncharov, Strong Constructivability of Homogeneous Models, Algebra and Logic, v.17, no 4, 1978.

[5] Logic Notebook, Novosibirsk University, Editors Yu.Ershov, S.Goncharov, 1986.

[6] N.Khissamiev, On Strongly Constructive Models of Decidable Theories, Izvestiya AN Kaz. SSR, no 1, 1974.

[7] K.Kudeiberganov,On Constructive Models of Undecidable Theories, Siberian Mathematical Journal, v.21, no 5, 1980.

[8] L.Harrington, Recursively Presentable Prime Models, Journal of Symbolic Logic, v.39, no 2, 1973.

[9] T. Millar, Ph.D. Dissertation, Cornell University, 1976.

[10] T. Millar, Omitting Types, Type Spectrums, and Decidability, Journal of Symbolic Logic, v.48, no 1, 1983.

[11] T. Millar, Foundations of Recursive Model Theory, Annals of Mathematical Logic, v. 13, 1978.

[12] M.Morley, Decidable Models, Israel Journal of Mathematics, v.25, 1976.

[13] M.Peret’ytkin, On Complete Theories with Finite Number of Countable Models, Algebra and Logic, v.12, no 5, 1973.

[14] J. Rosenstein, Linear Orderings, New York, Academic Press, 1982.

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