CONSTRUCTIVE MODELS OF

UNCOUNTABLY CATEGORICAL THEORIES

Bernhard Herwig Steffen Lempp Martin Ziegler

School of Mathematics University of Leeds Leeds LS2 9JT ENGLAND

Department of Mathematics University of Wisconsin Madison, WI 53706-1388 USA

Institut für mathematische Logik Albert-Ludwigs-Universität Freiburg D-79104 Freiburg GERMANY

Abstract. We construct a strongly minimal (and thus uncountably categorical) but not totally categorical theory in a finite language of binary predicates whose only constructive (or recursive) model is the prime model.

0. Introduction. Effective (or recursive) model theory studies to which degree constructions in model theory and algebra can be made effective. A presentation of a countable model M is an isomorphic copy N with universe N = ω. An effective (or computable, or recursive) presentation is one where all the relations, functions, and constants on N are given by uniformly computable functions. Now, for a countable model M of a first-order theory T, there are various degrees to which the construction of M can be made effective: We call the model M constructive (or recursive, or computable) if it has an effective presentation, or equivalently if its open diagram (i.e., the collection of all quantifier-free sentences true in (M, a)_{a∈M}

Typeset by AMS-TEX

1991 Mathematics Subject Classification. 03C57, 03D45.

Key words and phrases. constructive/recursive/computable model, uncountably categorical first-order theory, strongly minimal set, unsolvable word problem, Cayley graph.

The first author was supported by a grant of the British Engineering and Physical Sciences Research Council (Research Grant no. GR/K60503) The second author’s research was partially supported by NSF grant DMS-9504474 and a grant of the British Engineering and Physical Sciences Research Council (Research Grant no. GR/K60497).

(in some presentation) is computable (or recursive)). We call the model M decidable if its elementary diagram (i.e., the collection of all first-order sentences true in (M, a)_{a∈M}, in some presentation) is decidable (i.e., computable). Obviously, any decidable model is constructive, but the converse fails. In fact, the study of constructive models is much harder than the study of decidable models since in the former case, much less is known about the first-order theory.

Effective model theory has been particularly active in cases where the first-order theory has few countable models. A special case here, which is well-understood classically (i.e., without regard to effectiveness), is that of uncountably categorical theories. Such theories abound in algebra and model theory (e.g., algebraically closed fields, vector spaces, etc.) and were in fact the starting point of modern model theory with Morley’s famous categoricity theorem [Mo65]. By a classical theorem of Baldwin and Lachlan [BL71], the countable models of an uncountably but not totally categorical theory T form an elementary chain {M_{κ}}_{κ≤ω}. (Here, M_{0} is the prime model, and M_{ω} is the countably saturated model of T.) By a theorem of Harrington [Ha74] and Khisamiev (or Hisamiev) [Hi74], any countable model of a decidable uncountably categorical theory is decidable. The situation for constructive models of uncountably (but not totally) categorical theories T is much more difficult: The fact that some countable models of T are constructive does not imply that all are. In order to show how complicated things can become here, let us define the spectrum of constructive models of T by

SCM(T) = {κ ≤ ω | M_{κ} is constructive}.

Now the following subsets of ω + 1 can be realized a spectra of constructive models: (1) easy: SCM(T) = ω + 1.

(2) Gončarov [Go78]: SCM(T) = {0}.

(3) Kudaĭbergenov [Ku80]: SCM(T) = {0, 1, ⋯, n} for arbitrary n ∈ ω.

(4) Khoussainov, Nies, Shore [KNSta]: SCM(T) = ω.

(5) Khoussainov, Nies, Shore [KNSta]: SCM(T) = {1, 2, ⋯, ω}.

It is unknown exactly which subsets of ω + 1 can be realized as spectra of constructive models (see the end of this paper for further comments).

All the above-mentioned results (except (1)) use infinite languages. The question arises whether similar results can also be achieved for finite languages. The main result of this paper is to give a first affirmative answer, namely, an analogue of Gončarov’s result for a finite language of binary predicates. (Note that any uncountably categorical theory in a finite language of unary predicates is actually totally categorical.)

1. Strongly minimal theories in a binary language. We begin with a definition.

Definition. Let L = {R_{1}, …, R_{k}} be a finite relational binary language and M be an L-structure. M carries in a natural sense the structure of a graph: there is an edge between two distinct points a and b if there exists i such that R_{i}ab or R_{i}ba holds. We freely use graph-theoretic notions and refer thereby to this graph. E.g., we say M has finite valence if every point has only finitely many neighbors in the graph. The distance d(a, b) between a, b ∈ M is the length of the shortest path connecting the points. For a ∈ M, B_{i}(a) is the set {c ∈ M|d(a, c) ≤ i} and the connected component of a is the set B(a) = ⋃_{i∈ω} B_{i}(a).

The following lemma is partially contained in Ivanov [Iv89, Iv89’]:

Lemma. Let L be a finite language consisting of binary relation symbols. Let M be an infinite L-structure of finite valence.

a) M is strongly minimal iff for every i ∈ ω there exists a finite L-structure C_{i} and c_{i} ∈ C_{i} such that for almost all a ∈ M, (B_{i}(a), a) ≅ (C_{i}, c_{i}).

b) If M is strongly minimal and the structures C_{i} are as in a), then there exists up to isomorphism a unique connected L-structure C such that for every d ∈ C and i ∈ ω (B_{i}(d), d) ≅ (C_{i}, c_{i}).

c) If M is strongly minimal and C is as in b), then every elementary extension of M is a disjoint union of M and copies of C.

Proof. Suppose first that M is strongly minimal and fix i ∈ ω. For a ∈ M the isomorphism type of (B_{i}(a), a) is a first order property of a. As there are only finitely many such isomorphism types, there must be a structure (C_{i}, c_{i}) such that for infinitely many a ∈ M (B_{i}(a), a) ≅ (C_{i}, c_{i}). By strong minimality this must hold for almost all a ∈ M.

Now let us suppose that the right hand side of a) holds. On the way to proving that M is strongly minimal, we will prove b) and c). For every i there exists an embedding from (C_{i}, c_{i}) into (C_{i+1}, c_{i+1}). Thus we can suppose that C_{i} ⊆ C_{i+1} and c_{i} = c_{i+1}. Let C = ⋃_{i∈ω} C_{i} and c = c_{i} ∈ C. Then for every i ∈ ω we have (B_{i}(c), c) ≅ (C_{i}, c). In fact (C, c) is uniquely determined by this property: If D is a connected structure and d ∈ D satisfies for every i ∈ ω: (B_{i}(d), d) ≅ (C_{i}, c_{i}), then (D, d) ≅ (C, c). To see this look at the set {p | ∃i ∈ ω such that p : (B_{i}(d), d) ≅ (B_{i}(c), c)} ordered by extension. This set is a finitely branching tree with infinite height and by Königs Lemma it has an infinite branch in it, which gives rise to an isomorphism (D, d) ≅ (C, c). This proves uniqueness in b).

Now let us take an elementary extension M_{1} of M. Let i ∈ ω. As there are only finitely many exceptional points b in M not satisfying (B_{i}(b), b) ≅ (C_{i}, c), the same number of points, and in fact the same points, are exceptional in M_{1} in this sense. That means for every a ∈ M_{1} − M, (B_{i}(a), a) ≅ (C_{i}, c), which implies that (B(a), a) ≅ (C, c). As all the points in B(a) are also in M_{1} − M we have proved that for every d ∈ B(a) and therefore also for every d ∈ C: (B_{i}(d), d) ≅ (C_{i}, c), which finishes the proof of b) and c).

Furthermore, for every a, b ∈ M_{1} − M there is an automorphism fixing M and mapping a to b. Thus all the points in M_{1} − M have the same type over M, which means that there exists only one non-algebraic type over M. This implies that M is strongly minimal. □

From the above lemma it follows that if M is as above, and if a_{1}, …, a_{n} are elements in M, then the algebraic closure of these elements is acl(∅) ∪ B(a_{1}) ∪ … ∪ B(a_{n}). Thus the geometry of the strongly minimal set M is disintegrated. In fact, the assumption that M has finite valence is not essential: Let L = {R_{1}, …, R_{n}} be the binary language. Let x, y be a generic pair of elements. For every R_{i}, if xR_{i}y holds, we replace R_{i} by ¬R_{i}. So we can assume that for generic x, y ¬xR_{i}y holds. This means by strong minimality that for generic x there exists only finitely many y such that xR_{i}y holds. Therefore there are only finitely many points in M which have infinitely many neighbors and in fact we can assume there are no such points, i.e. we can assume that M has finite valence. In fact a similar argument works also in the case of an infinite language. So we have the following proposition.

Proposition. Let T be a strongly minimal theory in a binary relational language. Then the geometry of the theory is disintegrated.

2. The theorem and proof. The following theorem is the main result of this paper.

Theorem. There is a first-order theory T in a language L of three binary relation symbols such that

(i) T is an uncountably but not totally categorical theory;

(ii) the prime model of T is constructive; and

(iii) all the other countable models of T are not constructive; in fact, given any non computable Δ_{2}^{0}-degree a, there is such a theory T such that the nonprime models have presentations exactly of any degree ≥ a.

Moreover, T is strongly minimal.

Proof. We construct a prime model M_{0} in a language L = {R_{0}, R_{1}, R_{2}} of three binary relation symbols and show that T = Th(M_{0}) and L satisfy the claims of our theorem. The prime model will consist of the disjoint union of an infinite number of finite so-called Cayley graphs; the other countable models M_{κ} will then consist of M_{0} plus the disjoint union of κ many copies of a fixed infinite Cayley graph. The main idea is that the word problem in the finite groups corresponding to the finite Cayley graphs will be uniformly computable while the word problem in the infinite group corresponding to the infinite Cayley graph will be unsolvable.

To this end, we first establish a group-theoretical lemma.

Lemma. Let F be a free group of rank 3 (generated by g_{0}, g_{1}, and g_{2}, say). Then for every Δ_{2}^{0}-degree a there is a sequence {N_{k}}_{k∈ω} of subgroups of F such that

(i) {N_{k}}_{k∈ω} is a uniformly computable sequence of normal subgroups of finite index in F, so F/N_{k} has uniformly solvable word problem;

(ii) for each w ∈ F, the set {k ∈ ω | w ∈ N_{k}} is either finite or cofinite, so that the pointwise limit N = {w ∈ F | {k ∈ ω | w ∈ N_{k}} is cofinite} of the N_{k} exists and is again a normal subgroup of F; and

(iii) N has Turing degree a.

Proof of lemma. Fix a Δ_{0}^{2}-subset A of natural numbers that belongs to a and assume that 0 ∈ A. Also fix an effective sequence (A_{s})_{s∈ω} of finite sets of natural numbers, such that A is the pointwise limit of the A_{s}. Assume further that for every s, A_{s} is contained in [0, s] and 0 ∈ A_{s}.

For the following we need two notions from group theory, the definition of which we include (see, e.g., Rotman [Ro95]):

Definition. 1. If A and B are groups and φ : B →Aut(A) is a group automorphism (that is, B acts on A), we define the semidirect product of A and B (which also depends on φ) to be the set A × B equipped with the group operation

(a_{1}, b_{1}) · (a_{2}, b_{2}) = (a_{1} · (a_{2})^{φ(b_{1}^{−1})}, b_{1} · b_{2})

Stated differently, the semidirect product of A and B is the group generated by A and B subject to the relations a^{b} = a^{φ(b)} for a ∈ A and b ∈ B.

2. If C is a group, Ω a set, and ψ : B → Sym(Ω) a group homomorphism (that is, an action of B on Ω), then we define the wreath product C wr B of C and B to be the semidirect product of C^{Ω} and B. Here, C^{Ω} is the group of functions from Ω to C where group multiplication is defined componentwise, and if we write an element of C^{Ω} as (c_{i})_{i∈Ω}, then the action φ of B on C^{Ω} is given by ((c_{i})_{i∈Ω})^{φ(b)} = (c_{(i^{ψ(b^{−1})})})_{i∈Ω}.

Now, for k > 0, define a finitely generated group as follows. Let the symmetric group S_{3} be presented as ⟨a, ϕ | a^{3} = ϕ^{2} = a^{ϕ}a = 1⟩. Now set

H_{k} = S_{3} wr Z_{2k+1}

= ⟨a, ϕ, b | a^{3}, ϕ^{2}, a^{ϕ}a, b^{2k+1}, [a^{b^{j}}, a^{b^{j′}}], [ϕ^{b^{j}}, ϕ^{b^{j′}}], [a^{b^{j}}, ϕ^{b^{j′}}] (−k ≤ j < j′ ≤ k)⟩.

(Here, the action of Z_{2k+1} under consideration is the natural (regular) action of Z_{2k+1} on a set of size 2k + 1.)

Let L_{k} be the subgroup of H_{k} generated by a, b, and

t = ∏_{j∈A_{k}} ϕ^{b^{j}}.

The subgroup N_{k} of the free group F is now the kernel of the canonical homomorphism of F = ⟨a, b, t⟩ onto L_{k}. (Note here that we have renamed the generators of F to produce a more group-theoretic notation.)

The sequences (H_{k})_{k∈ω} and (L_{k})_{k∈ω} are uniformly computable sequences of finite groups. Namely, H_{k} is just the semidirect product of two groups C = ⨁_{−k≤j≤k} S_{3} and D = Z_{2k+1}, and each element of H_{k} can be uniquely written as c · d with c ∈ C and d ∈ D where the multiplication is effective. Thus (N_{k})_{k∈ω} is uniformly computable, and (i) is verified. The best way to visualize L_{k} is as follows: a together with its conjugates by powers of b generates the base of the group, which is of the form ⨁_{−k≤j≤k} Z_{3}, t acts componentwise as automorphisms on this base swapping a^{b^{j}} and (a^{2})^{b^{j}}, if j is in A_{k}, and b acts as a shift.

We note the following relations holding in L_{k} (in addition to the ones obviously carrying over from H_{k}) for all j, j′ ∈ [−k, k]:

t^{2} = 1
[t^{b^{j}}, t^{b^{j′}}] = 1,

(a^{b^{j}})^{t} = (a^{b^{j}})^{2} (j ∈ A_{k}), (*)

(a^{b^{j}})^{t} = a^{b^{j}} (j ∉ A_{k}). (**)

Note that 0 ∈ A_{k} ⊆ [0, k] implies in particular that

(***)  a^{t} = a^{2} and (a^{b^{j}})^{t} = a^{b^{j}} for all j ∈ [−k, 0).

We say that a word w in a, b, t, and their inverses is in normal form if it is of the form

∏_{i=−d}^{d}(a^{t_{i}})^{b^{i}} · ∏_{i=−d}^{d}(t^{r_{i}})^{b^{i}} · b^{l}

where d ∈ ω, l ∈ Z, and for i ∈ [−d, d], t_{i} ∈ {0, 1, 2} and r_{i} ∈ {0, 1}.

We begin by showing that

(1) Given a “word” w ∈ F, there is a word w′ in normal form such that w = w′ in L_{k} for almost all k ∈ ω.

(2) If w and w′ are two distinct words in normal form then w ≠ w′ in L_{k} for almost all k ∈ ω.

To show (1), fix a word w ∈ F and observe first that we can move the b’s in w to the right (at the expense of conjugating by b’s) to obtain a word of the form w_{0} · b^{l} where w_{0} is a product of conjugates of a and t (by powers of b). Next move all the a-conjugates in w_{0} to the left of all the t-conjugates using the fact that

t^{b^{s}}a^{b^{r}} = \{ \begin{matrix}(a^{2})^{b^{r}}t^{b^{s}} & if (r − s) ∈ A \\ a^{b^{r}}t^{b^{s}} & otherwise \end{matrix}

holds in L_{k} for all r, s and all sufficiently large k. We thus obtain a word w_{1} · w_{2} · b^{l} where w_{1} is a product of conjugates of a by powers of b and w_{2} is a product of conjugates of t by by powers of b. Finally use a^{3} = t^{2} = 1 to obtain the desired w′ in normal form. w = w′ holds in L_{k} for k big enough as A is the pointwise limit of the A_{k}.

To show (2), fix two distinct words w = w_{1} ·w_{2} ·b^{l} and w′ = w′_{1} ·w′_{2} ·b^{l′} in normal form (where the w_{1}’s and w_{2}’s contain only a’s and t’s, respectively, conjugated by powers of b). We have to show that w ≠ w′ holds in almost all L_{k} or equivalently in almost all H_{k}.

Remember that H_{k} is the semidirect product of C = ⨁_{−k≤i≤k} S_{3} and Z_{2k+1}. We can write each of the involved groups S_{3} as a semidirect product Z_{3} and Z_{2}, where Z_{3} is generated by a^{b^{j}} for an appropriate j. So we can also write C as a semidirect product of ⨁_{−k≤i≤k} Z_{3} and ⨁_{−k≤i≤k} Z_{2}. w_{1} is a product of conjugates of a and therefore always belongs to the first group, while w_{2} belongs to the second group and b^{l} belongs to Z_{2k+1}. This implies that w_{1} · w_{2} · b^{l} = w′_{1} · w′_{2} · b^{l′} holds in H_{k} iff w_{1} = w′_{1} and w_{2} = w′_{2} and b^{l} = b^{l′} holds in H_{k}. If therefore the words w_{1} and w′_{1}, or the words b^{l} and b^{l′}, are distinct, then obviously w_{1} · w_{2} · b^{l} ≠ w′_{1} · w′_{2} · b^{l′} in almost all H_{k}.

So assume l = l′ and w_{1} = w′_{1} from now on, and we simply have to show that w_{2} ≠ w′_{2} in F implies w_{2} ≠ w′_{2} in almost all H_{k}’s. For this, it suffices to show that any nontrivial word of the form

v = ∏_{i=e}^{f}(t^{r_{i}})^{b^{i}}

does not equal 1 in almost all H_{k}’s (where e ≤ f are integers, r_{i} ∈ {0, 1} for i ∈ [e, f], and r_{e} = r_{f} = 1). Now note that by (***) above, for k ≥ f − e the following holds in H_{k}:

∏_{i=e}^{f}(t^{r_{i}})^{b^{i}} · a^{b^{e}} = t^{b^{e}} · a^{b^{e}} · ∏_{i=e+1}^{f}(t^{r_{i}})^{b^{i}} = (a^{2})^{b^{e}} · ∏_{i=e}^{f}(t^{r_{i}})^{b^{i}}.

But this means that for k ≥ f − e, (a^{b^{e}})^{v} = (a^{b^{e}})^{2} which implies v ≠ 1 as a ≠ a^{2} in H_{k}.

We can now verify the remaining claims of the Lemma as follows:

(ii) holds by (1) and (2) above.

(iii) holds since x ∈ A iff ta^{b^{x}}ta^{b^{x}} ∈ N = lim_{k} N_{k} (see (*) and (**)) and as the process of getting a word in normal form is computable in A.

This concludes the proof of the lemma. □

Given the lemma, we can now easily finish the proof of the theorem. For each k ∈ ω, define the Cayley graph C_{k} of F/N_{k} by setting the universe C_{k} = F/N_{k} and defining three binary relations R_{0}, R_{1}, and R_{2} on C_{k} by setting R_{i}(v, w) iff v = wg_{i} in F/N_{k} (for i ≤ 2). Similarly, we define the Cayley graph C of F/N. We then define M_{0} as the disjoint union of the Cayley graphs C_{k} (for all k ∈ ω). For any cardinal κ > 0, we define M_{κ} to be the disjoint union of M_{0} and κ many copies of the Cayley graph C. Let c ∈ C.

By (ii) of the group-theoretical Lemma, for any fixed r > 0, B_{r}(x) is isomorphic to B_{r}(c) for almost all x ∈ M_{0}, and thus by the Lemma in Section 1, M_{0} is strongly minimal, the other models of the theory being the M_{κ}.

This establishes (i) of the Theorem. It is clear from the above construction and (i) and (iii) of the group-theoretical Lemma, respectively, that for κ ≤ ω, M_{κ} is constructive iff κ = 0.

We finish the proof by showing how A is computable from any representation of M_{κ} for 1 ≤ κ ≤ ω. (Recall that by an observation of Knight [Kn86], the set of degrees of presentations of a countably infinite model is upward closed iff its automorphism group does not contain the stabilizer (in the symmetric group) of a finite subset of the model.) Pick c ∈ M_{κ} − M_{0}. Let x ∈ ω. To decide if x ∈ A compute B_{2k+3}(x) (that is effective in the given presentation of M_{κ}), which is part of the Cayley graph of F/N and decide if ta^{b^{x}} = (a^{2})^{b^{x}}t. □

3. Concluding remarks. We remark that our theorem leaves open the question of exactly which subsets S of ω +1 can be realized as spectra of constructive models of uncountably categorical theories. In fact, it is even unclear whether all such sets S must be arithmetical.

Closely related to this is the question of how complicated the other countable models of an uncountably categorical theory of a constructive model can be. By an observation (jointly with T. Millar), if the language L is finite, contains only binary relation symbols, and the prime model M_{0} is constructive and strongly minimal, then the other countable models of Th(M_{0}) must have presentations computable in 0′′, the second Turing jump of the computable Turing degree. Since the geometry of models in relations of higher arity can be much more complicated, the situation is unclear in this case and appears quite hard.

If we content ourselves with an uncountably categorical theory as opposed to a strongly minimal theory, then we can find a theory of graphs satisfying the three conditions of our theorem. In fact this is true for all the questions of similar type, e.g. for the ones posed above in this section: We could as well restrict our attention to graphs.

This is true, because standard techniques in model theory allow one to interpret any given structure of finite signature in a graph in a way that respects features like categoricity or computability (but not strong minimality). For an example of this technique see, e.g., chapter 10.3 in Ebbinghaus, Flum [EF95]. In fact the interpretation can be chosen to be a bi-interpretation in the sense of Ahlbrandt, Ziegler [AZ86]. In the present context we need an interpretation which is effective in both directions. By an effective interpretation of one countable structure in another we mean that the domain and relations of the first structure are computable in any presentation of the second structure. In particular, in the case of an effective biinterpretation, any presentation of one structure leads to a presentation of the second structure of the same Turing degree.

Let us sketch how this can be done:

Proposition. Let M be a countable structure in a finite language. There exists a graph N, that is bi-interpretable with M; both interpretations are effective.

Proof. We can easily suppose that the language of the original structure M is relational and that the unary predicates give a partition of the domain of M. First we introduce for every n-ary relation symbol R (for n > 1) and for every n-tuple ā from M a new point p_{R,ā}. The domain of the new structure M_{1} now consists of all the points from M and the new points. Let V be the set of points from M. We replace every n-ary symbol R of the old language by unary predicates Y_{R} and N_{R} the interpretation of Y_{R} in M_{1} is {p_{R,ā}|M ⊧ Rā} and of N_{R} is {p_{R,ā}|M ⊧ ¬Rā} (Y and N for Yes and No). We keep the unary predicates already present in M and their interpretations. Moreover, if n is the maximal arity of the old language, we introduce n many binary symbols {T_{j}}_{0≤j<n} and T_{j} is interpreted by the relation {(b, p_{R,ā})|b is the j-th component of the tuple ā}. We can interpret M in M_{1} in a computable fashion. E.g., Rx_{0} … x_{n−1} can be defined by the formula ∃y(Y_{R}y∧T_{0}x_{0}y∧…∧T_{n−1}x_{n−1}y), which is computable in the structure M_{1} as for every x_{0}, …, x_{n−1} exactly one of ∃y(Y_{R}y ∧T_{0}x_{0}y ∧…∧T_{n−1}x_{n−1}y) and ∃y(N_{R}y ∧ T_{0}x_{0}y ∧ … ∧ T_{n−1}x_{n−1}y) holds. We can consider the structure M_{1} as a directed colored graph, where the edges and the vertices are colored. Furthermore, every edge connects a point belonging to V to one not belonging to V.

Now we apply the same procedure to M_{1}, except that we only introduce new points p_{S,(a,b)} for each binary relation S in the language of M_{1} and each a ∈ V and b ∉ V. This suffices, as only between such points can a relation hold in M_{1}. Furthermore, we can replace the only two relation symbols T_{0} and T_{1} of the new structure by the symbol T with the defining clause T xy ↔ (T_{0}xy ∨ T_{1}xy ∨ T_{0}yx ∨ T_{1}yx) without losing any information. We call the resulting structure M_{2}. M_{2} is a colored graph (where only the vertices are colored), which is bipartite, and which does not have any isolated points.

Let {U_{1}, …, U_{r}} be the unary predicates in the language of M_{2}. In the final step, for every point a of M_{2} if M_{2} ⊧ U_{j}a, we introduce 2j many new points a_{1}, …, a_{2j} and we enlarge the interpretation of T by the pairs (a_{i}, a_{j}), where (i − j) ≡ 1 mod 2j + 1 or (i − j) ≡ −1 mod 2j + 1 (where a_{0} = a). In other words, we add a loop of size 2j + 1. Let N be the resulting {T }-structure. N is a graph and it is easy to see that M_{2} is interpretable in an effective way in N. The clue is that M_{2} is bi-partite, so there are no odd cycles in M_{2}. The newly introduced loops are the only odd cycles in N without repetition. Every point of N belongs to exactly one such cycle as the unary predicates of M_{2} give a partition of M_{2}. In every such cycle there is exactly one point with more than two neighbors.

Now M and N are bi-interpretable, and the interpretations are effective. □

References

[AZ86] Ahlbrandt, G. and Ziegler, M., Quasi-finitely axiomatizable totally categorical theories, Stability in model theory (Trento, 1984), Ann. Pure Appl. Logic 30 (1986), 63–82.

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

[EF95] Ebbinghaus, H.-D. and Flum, J., Finite model theory, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1995.

[Go78] Gončarov, S. S., Constructive models of ℵ_{1}-categorical theories, Mat. Zametki 23 (1978), 885–888. (Russian)

[Ha74] Harrington, L., Recursively presented prime models, J. Symbolic Logic 39 (1974), 305-309.

[Hi74] Hisamiev, N. G., On strongly constructive models of decidable theories, Izv. Akad. Nauk Kazakh. SSR Ser. Fiz.-Mat. 35 (1974), no. 1, 83-84. (Russian)

[Iv89] Ivanov, A. A., The problem of finite axiomatizability for strongly minimal theories of graphs, and groups with more than one end, Algebra i Logika 28 (1989), 160–173. (Russian)

[Iv89’] Ivanov, A. A., The problem of finite axiomatizability for strongly minimal theories of

graphs, Algebra i Logika 28 (1989), 280–297. (Russian)

[KNSta] Khoussainov, B., Nies, A., and Shore, R. A., Recursive models of theories with few models (to appear).

[Kn86] Knight, J. F., Degrees coded in jumps of orderings, J. Symbolic Logic 51 (1986), 1034– 1042.

[Ku80] Kudaĭbergenov, K. Ž., Constructivizable models of undecidable theories, Sibirsk. Mat. Zh. 21 (1980), no. 5, 155–158, 192.

[Mo65] Morley, M., Categoricity in power, Trans. Amer. Math. Soc. 114 (1965), 514–538.

[Ro95] Rotman, J., An introduction to the theory of groups, 4th edition, Graduate Texts in Mathematics No. 148, Springer-Verlag, New York, 1995.