PUBLICATIONS DE L’INSTITUT MATHÉMATIQUE Nouvelle série, tome 97(111) (2015), 33–41 DOI: 10.2298/PIM140318001I

GROUPS WITH FINITELY MANY COUNTABLE MODELS

Dejan Ilić, Slavko Moconja, and Predrag Tanović

Abstract. We construct Abelian group with an extra structure whose first order theory has finitely many but more than one countable model.

1. Introduction

In this paper we will deal with the first order structures in a countable language. The theory of a structure M in the language L, denoted by Th_{L}(M), is the set of all L-sentences that M satisfies; it is a complete theory. For any complete theory T having infinite models let I(ℵ_{0}, T) denote the number of isomorphism classes of its countable models. The theory T is called an Ehrenfeucht theory if 1 < I(ℵ_{0}, T) < ℵ_{0}. The first example of such a theory was given by Ehrenfeucht in [11]. It is the theory in the language {<} ∪ {c_{n} | n ∈ ω} describing a dense linear order without endpoints in which C = (c_{n} | n ∈ ω) is a strictly increasing chain. There are three countable models, up to isomorphism: one in which C is unbounded, one in which C is bounded but diverges, and one in which C converges. Ehrenfeucht theories are considered as sporadic among the first order theories and there are not many essentially distinct examples, some of them can be found in [6, 9, 12]. None of the known examples is based on an algebraic structure, for example on a group. In this article by a group we will mean a first order structure (G, ·, …) such that (G, ·) is a group but an additional structure may be added. If no additional structure is added then we say that it is a pure group, even when the neutral element is named.

We will describe a construction which for a given densely ordered, countable, saturated structure produces an Abelian group similar to it; more precisely, the two structures will be bi-interpretable (we use standard notion of interpretation of a structure into another as can be found in [2]). We will start with a countable, saturated structure L in a countable, relational language L containing a binary relation (symbol) < and a unique constant symbol 0. Assuming that the domain is densely linearly ordered we construct a countable, saturated Abelian group G(M) in the language L_{G} = L ∪ {+}. The structure L will be interpretable in G(M) via a canonical, definable mapping π taking the elementary submodels of G(M) onto the elementary submodels of L. It will turn out that π preserve isomorphism in both directions so, by saturation, it determines a bijective correspondence between countable models of Th_{L}(L) and Th_{L_{G}} (G(M)). In particular we have that I(ℵ_{0}, Th_{L}(L)) = I(ℵ_{0}, Th_{L_{G}} (G(M))) and if Th_{L}(L) is an Ehrenfeucht theory, then Th_{L_{G}} (G(M)) is an Ehrenfeucht theory, too. Since Ehrenfeucht’s example can be turned into a densely ordered relational structure, we obtain:

2010 Mathematics Subject Classification: 03C15; 03C64.

The second and the third authors were supported by the Ministry of Education, Science and Technological Development of Serbia, grants ON174018 and ON174026.

Communicated by Žarko Mijajlović.

Theorem 1.1. There is an Abelian group (with additional structure) whose theory is an Ehrenfeucht theory.

The construction is a slight modification of Krupinski’s construction of a minimal, ordered group from [3]; it was used in [4] and described in detail in [1]. A similar construction was used by the third author in [8].

We assume that the reader is familiar with basic model theory concepts, as can be found in [2]. Let M = (M, …) be a first order structure and let A ⊆ M and a ∈ M. By tp(a/A) we denote the set of all formulae with parameters from A that a satisfies. If there is a formula with parameters from A whose unique solution is a, then we say that a is definable over A. The set of all definable elements over A is called the definable closure of A in M and is denoted by dcl_{M} (A). Suppose that N = (N, …) is elementary equivalent to M, B ⊆ N and f : A −→ B is a bijection. If tp(a_{1}, …, a_{n}) = tp(f(a_{1}), …, f(a_{n})) holds for all a_{1}, …, a_{n} ∈ A, then we say that f is a partial elementary mapping. Such a mapping extends (uniquely) to a partial elementary mapping between dcl_{M} (A) and dcl_{N} (B).

2. The construction

Throughout this section we fix a countable language L whose unique nonrelational symbol is a constant symbol 0. We assume that L contains a binary relation symbol <. In order to simplify notation we will not distinguish between the < and actual linear orderings that it defines in structures. Fix a countable, saturated L-structure L = (L, <, 0, …) such that (L, <) is a dense, unbounded linear order whose minimum is 0. We will construct a 2-sorted structure M in which one sort L(M) is L, and the other sort G(M) is a group with the L-structure added. The only link between the sorts will be the projection map π^{M} mapping G(M) (the domain of G(M)) onto L (the domain of L(M)).

Let L_{G} := {+}∪{R_{G} | R ∈ L} and let L^{∗} := {L, G}∪L∪L_{G} ∪{π}. Here the unary predicates L and G are reserved for sort names. Let L(M) := L. + will be interpreted as an addition in commutative groups and, to simplify notation, we will not distinguish between the language symbol and actual operations in structures. An L_{G}-structure G(M) is defined in the following way. Let E = (e_{l} | l ∈ L ∖ {0}) be a sequence of pairwise distinct elements and let (G(M), +, 0_{G}) be a group of exponent 2 freely generated by E. For 0 < l_{1} < ⋯< l_{k} define: π^{M} (e_{l_{1}} +⋯ +e_{l_{k}} ) = l_{k}, π^{M} (0_{G}) = 0. Then π^{M} : G(M) −→ L is called the projection of G(M) onto L(M). For each n-ary relation symbol R ∈ L and (a_{1}, …, a_{n}) ∈ G(M)^{n} define:

G(M) ⊧ R_{G}(a_{1}, …, a_{n}) if and only if L ⊧ R(π^{M} (a_{1}), …, π^{M} (a_{n})).

In particular, a <_{G} b holds in G(M) if and only if π^{M} (a) < π^{M} (b) holds in L.

For every N ⊧ Th(M), we denote its domain by N. We assume that N is the disjoint union of G(N) and L(N), where G(N) (L(N)) is the domain of the G-sort (L-sort) of N. The structure G(N) is an L_{G}-group (G(N), +, 0_{G}, …) and L(N) is the L-structure of the L-sort (L(N), <, 0, …). So when we write G(N′) by this we mean the G-sort of some model N′; similarly for L(N′). Note that for each n-ary relation symbol R ∈ L holds:

M ⊧ (∀ x_{1}, x_{2}, …, x_{n} ∈ G)(R_{G}(x_{1}, x_{2}, …, x_{n}) ⇔ R(π(x_{1}), π(x_{2}), …, π(x_{n}))) .

Therefore, the same holds in each N ⊧ Th(M). Hence, for all a_{1}, a_{2}, …, a_{n} ∈ G(N) we have:

(2.1) G(N) ⊧ R_{G}(a_{1}, a_{2}, …, a_{n}) iff L(N) ⊧ R(π^{N} (a_{1}), π^{N} (a_{2}), …, π^{N} (a_{n})).

Lemma 2.1. Let x ∼ y denote G(x) ∧ G(y) ∧ ¬(x <_{G} y ∨ y <_{G} x).

(i) M ⊧ (∀x, y ∈ G)(x ∼ y ⇔ π(x) = π(y)).

(ii) The <_{G}-incomparability is a definable equivalence relation on the G-sort

of any model of Th(M). (iii) The mapping defined by x/ ∼ ↦ π^{M} (x) determines an interpretation of L(M) in G(M). Moreover, for any N ⊧ Th(M) x/∼ ↦ π^{N} (x) defines an interpretation of L(N) in G(N).

Proof. (i) follows from the definition of <_{G} and (ii) follows from (i). (iii) follows from the definition of G(M): whenever a_{i} ∼ b_{i}, for i ⩽ n, a_{i}, b_{i} are elements of G(M), then π^{M} (a_{i}) = π^{M} (b_{i}) and we have

G(M) ⊧ R_{G}(a_{1}, …, a_{n}) iff L(M) ⊧ R(π^{M} (a_{1}), …, π^{M} (a_{n})) iff
L(M) ⊧ R(π^{M} (b_{1}), …, π^{M} (b_{n})) iff G(M) ⊧ R_{G}(b_{1}, …, b_{n}).

Therefore R is interpreted by R_{G}/∼. By elementary equivalence the same holds in any N ⊧ Th(M). □

It follows from part (iii) of the lemma that the isomorphism type of any model of Th(M) is determined by the L_{G}-isomorphism type of its G-sort. We aim to prove that the isomorphism type of any countable model of Th(M) is uniquely determined by the L-isomorphism type of its L-part among the countable models. We do that in Theorem 2.1 and the key fact used in the proof is the existence of linearly ordered basis (defined below) in the countable case. In Proposition 2.1 we prove that M has an uncountable elementary extension whose L-sort is L, so L(M) does not determine the isomorphism type of M in the class of all models.

We will view G(N) as a vector space over Z_{2} and by span(X) denote the linear span of X ⊆ G(N). A linearly ordered basis is a basis which is totally ordered by <_{G}.

Lemma 2.2. (i) G(M) ⊧ (∀x ≠ 0_{G})(∀y ≠ 0_{G})(x ∼ y ⇔ x + y <_{G} y)
(ii) G(M) ⊧ (∀x_{1}, …, x_{n})(x_{1} <_{G} ⋯<_{G} x_{n} ⇒ x_{1} + ⋯+ x_{n} ∼ x_{n}).

(iii) If N ⊧ Th(M), then every finite totally ordered subset of non-zero ele-

ments in G(N) is linearly independent. (iv) If N ⊧ Th(M) and 0_{G} <_{G} a_{1} <_{G} ⋯<_{G} a_{n} and 0_{G} <_{G} b_{1} <_{G} ⋯<_{G} b_{n}

are elements of G(N), then f(a_{i}) = b_{i} (i ⩽ n) extends to an isomorphism of (span(a_{1}, …, a_{n}), +, <_{G}, 0_{G}) and (span(b_{1}, …, b_{n}), +, <_{G}, 0_{G}).

(v) If N ⊧ Th(M) is countable, then any finite, totally ordered subset of G(N) ∖ {0_{G}} is contained in a linearly ordered basis of G(N).

Proof. (i)–(ii) are easy and left to the reader.

(iii) If a_{1} <_{G} a_{2} <_{G} ⋯<_{G} a_{n} then, by part (ii), we have ∑ _{i=1}^{n} a_{i} ∼ a_{n} so ∑ _{i=1}^{n} a_{i} ≠ 0_{G}. Therefore the sum of elements of a chain is distinct from 0_{G}, so every chain is linearly independent.

(iv) Suppose that a_{1} <_{G} ⋯<_{G} a_{n} and b_{1} <_{G} ⋯<_{G} b_{n} are chains of non-zero elements of G(N) and that f : {a_{1}, …, a_{n}} → {b_{1}, …, b_{n}} sends a_{i} to b_{i} (for each i ⩽ n). To prove that f extends to an isomorphism between (span(a_{1}, …, a_{n}), +, <_{G}, 0_{G}) and (span(b_{1}, …, b_{n}), +, <_{G}, 0_{G}) first note that, by part (iii), a_{i}’s are linearly independent. Further, since part (ii) of the lemma holds for G(N) in place of G(M), we have that whenever both (n_{1}, …, n_{r}) and (m_{1}, …, m_{s}) consist of pairwise distinct natural numbers, we have:

a_{n_{1}} + ⋯+ a_{n_{r}} <_{G} a_{m_{1}} + ⋯+ a_{m_{s}} iff max{n_{1}, …, n_{r}} < max{m_{1}, …, m_{s}}.

It is straightforward to verify that this fact implies that f extends to isomorphism of the ordered spans.

(v) Suppose that {a_{0}, …, a_{n}} is totally ordered by <_{G}. Then, by (iii), it is linearly independent, so it can be extended to a basis A = {a_{i} | i ∈ ω} of G(N). Inductively we will define a new basis {b_{i} | i ∈ ω} satisfying our requirements. Let b_{i} = a_{i} for i ⩽ n. Consider a_{n+1} + span(b_{0}, …, b_{n}) and let b_{n+1} be its <_{G}-minimal element. Then b_{n+1} is ∼-equivalent to no element b of span(b_{0}, …, b_{n}) as otherwise, by (ii), we would have b_{n+1} >_{G} b_{n+1} +b and b_{n+1} +b ∈ a_{n+1} +span(b_{0}, …, b_{n}) would contradict the minimality of b_{n+1} . Thus, {b_{0}, …, b_{n+1} } is <_{G}-totally ordered and span(a_{0}, …, a_{n+1} ) = span(b_{0}, …, b_{n+1} ). Continuing in this way, we get a totally ordered basis {b_{i} | i ∈ ω} containing {a_{0}, …, a_{n}}. □

Lemma 2.3. Suppose that N ⊧ Th(M).

(i) Any linearly ordered base of G(N) contains exactly one representative from each non-zero ∼-class. Non-zero ∼-classes are densely linearly ordered; In particular if N is countable, they are ordered in the order type of the rationals.

(ii) Any order-preserving bijection between linearly ordered bases of G(N) ex-

tends to an automorphism of (G(N), +, <_{G}, 0_{G}). (iii) If ā = (a_{1}, …, a_{n}) and b̄ = (b_{1}, …, b_{n}) are chains of non-zero elements

of G(N), then tp_{{<_{G} ,+}} (ā) = tp_{{<_{G} ,+}} (b̄).

Proof. (i) From the definition of linearly ordered base no pair of its elements are ∼-equivalent, so it remains to show that it has at least one representative in each non-zero ∼-class. Let a ∈ G(N) ∖ {0_{G}} and let B be a linearly ordered basis of G(N). To show that a ∼ b holds for some b ∈ B, note that a is a finite sum of elements of B. By Lemma 2.2(ii) a is in the ∼-class of the largest element b ∈ B appearing in the sum. Hence a ∼ b holds.

Non-zero classes are <_{G}-ordered in the same way as their projections are ordered in L(N), so the order is dense.

(ii) Follows from Lemma 2.2(iv).

(iii) If the conclusion fails then it fails in a countable model. So it suffices to prove the lemma assuming that N is countable. By Lemma 2.2(v), each of ā and b̄ is contained in a linearly ordered basis of G(N). By part (i) these bases are ordered in the order type of the rationals. Hence they are isomorphic (as linear orders) and the isomorphism can be chosen mapping each a_{i} to b_{i} (1 ⩽ i ⩽ n). By part (ii) this isomorphism extends to an automorphism of (G(N), <_{G}, +, 0_{G}). In particular tp_{{<_{G} ,+}} (ā) = tp_{{<_{G} ,+}} (b̄). □

According to part (i) of the lemma every linearly ordered base A ⊂ G(N) contains exactly one representative from each non-zero ∼ -class. Hence the elements of A can be indexed by the elements of L(N) ∖ {0}:

A = {a_{l} | l ∈ L(N) ∖ {0}} and π^{N} (a_{l}) = l holds for all relevant l. This condition does not imply that A is a base. In the proof of Proposition 2.1 we will find A which satisfies this condition but which is not a basis of G(M).

Lemma 2.4. Suppose that N ⊧ Th(M) and that (a_{i} | i ∈ I) and (b_{i} | i ∈ I) are sequences of pairwise <_{G}-comparable, non-zero elements of G(N) such that (π^{N} (a_{i}) | i ∈ I) ≡_{L} (π^{N} (b_{i}) | i ∈ I). Then (a_{i} | i ∈ I) ≡_{L_{G}} (b_{i} | i ∈ I); in other words, the mapping defined by f(a_{i}) = b_{i} is a partial elementary mapping.

Proof. Clearly, it suffices to prove the lemma assuming that I is finite and N is countable. Further, we may assume that L(N) ≅ L: if the conclusion fails in N, then by replacing N by the union of an appropriately formed ω-chain of countable, elementary extensions of N, we get a countable model of Th(M) such that L(N) is countable and saturated (saturation of L is relevant here). So assume that L(N) ≅ L.

By induction on the complexity of L_{G}-formula ϕ(x̄) we prove that G(N) ⊧ ϕ(ā) and G(N) ⊧ ϕ(b̄) are equivalent, whenever ā = (a_{1}, …, a_{n}) and b̄= (b_{1}, …, b_{n}) are increasing chains of non-zero elements of G(N) satisfying π^{N} (ā) ≡_{L} π^{N} (b̄). First we prove it for atomic ϕ(x̄). Assume that ā = (a_{1}, …, a_{n}) and b̄ = (b_{1}, …, b_{n}) are increasing chains of non-zero elements of G(N) satisfying π^{N} (ā) ≡_{L} π^{N} (b̄). By Lemma 2.3(iii) ā and b̄ have the same {<_{G}, +}-type. Further note that every L_{G}- term is {+, 0_{G}}-term so, if ϕ(x̄) is an atomic formula of the form t(x̄) = s(x̄), then the equality of {<_{G}, +} -types of ā and b̄ implies the equivalence of G(N) ⊧ ϕ(ā) and G(N) ⊧ ϕ(b̄). Assume that ϕ(x̄) is atomic of the form R_{G}(t_{1}(x̄), …, t_{m}(x̄)) where R ∈ L is m-ary. Then

G(N) ⊧ R_{G}(t_{1}(ā), …, t_{m}(ā)) iff L(N) ⊧ R(π^{N} (t_{1}(ā)), …, π^{N} (t_{m}(ā))) iff

L(N) ⊧ R(π^{N} (t_{1}(b̄)), …, π^{N} (t_{m}(b̄))) iff G(N) ⊧ R_{G}(t_{1}(b̄), …, t_{m}(b̄)).

Here the first and the third equivalence follow from the fact (2.1) before Lemma 2.1. The second is a consequence of tp_{L}(π^{N} (ā)) = tp_{L}(π^{N} (b̄)): indeed, if t(x̄) is any {+, 0_{G}}-term then, without loss of generality, t(x̄) = ∑ _{i∈I_{0}} x_{i}, for some I_{0} ⊆ {1, 2 …, n}. We have

t(ā) ∼ max{a_{i} | i ∈ I_{0}} and t(b̄) ∼ max{b_{i} | i ∈ I_{0}}; hence
π^{N} (t(ā)) = max{π^{N} (a_{i}) | i ∈ I_{0}} and π^{N} (t(b̄)) = max{π^{N} (b_{i}) | i ∈ I_{0}}.

It follows that π^{N} (t(ā)) = π^{N} (a_{k}) and π^{N} (t(b̄)) = π^{N} (b_{k}) hold for the same k ∈ I_{0}. Therefore tp_{L}(π^{N} (ā)) = tp_{L}(π^{N} (b̄)) implies:

tp_{L} (π^{N} (t_{1}(ā)), …, π^{N} (t_{m}(ā))) = tp_{L} (π^{N} (t_{1}(b̄)), …, π^{N} (t_{m}(b̄))).

This proves the equivalence of G(N) ⊧ ϕ(ā) and G(N) ⊧ ϕ(b̄) for atomic formulae. The induction step is trivial when ϕ(x̄) is either a conjunction or a negation and it remains to consider the case when ϕ(x̄) is ∃y ψ(y, x̄). So assume that G(N) ⊧ ψ(c, ā) holds and we prove G(N) ⊧ ∃y ψ(y, b̄).

First suppose that c ∈ span(ā) and let c = ∑ _{i∈I_{0}} a_{i} for some I_{0} ⊆ {1, …, n}. Apply the induction hypothesis to ψ(∑ _{i∈I_{0}} x_{i}, x̄), ā and b̄. Then we have that G(N) ⊧ ψ(∑ _{i∈I_{0}} a_{i}, ā) implies G(N) ⊧ ψ(∑ _{i∈I_{0}} b_{i}, b̄), so G(N) ⊧ ∃y ψ(y, b̄).

Now assume that c ∉ span(ā) and let c′ = c + ∑ _{i∈I_{0}} a_{i} be the smallest element of c+span(ā). Then c′ is <_{G}-comparable to each element of span(ā); otherwise, by Lemma 2.2(i) their sum would be strictly smaller than c′, contradicting the minimality of c′. Therefore (c′, ā) can be arranged into a strictly increasing sequence:

a_{1} <_{G} ⋯<_{G} a_{k} <_{G} c′ <_{G} a_{k+1} <_{G} ⋯<_{G} a_{n}.

Then π^{N} (a_{1}) < ⋯< π^{N} (a_{k}) < π^{N} (c′) < π^{N} (a_{k+1} ) < ⋯< π^{N} (a_{n}).

tp_{L}(π^{N} (ā)) = tp_{L}(π^{N} (b̄)) coupled with saturation of L(N) implies that there is f ∈ Aut(L(N)) such that f(π^{N} (a_{i})) = π^{N} (b_{i}) for all 1 ⩽ i ⩽ n. Let d′ ∈ G(N) be such that f(π^{N} (c′)) = π^{N} (d′). Then

b_{1} <_{G} ⋯<_{G} b_{k} <_{G} d′ <_{G} b_{k+1} <_{G} ⋯<_{G} b_{n}.

By Lemma 2.3(iii) we have tp_{{+,<_{G} }} (d′, b̄) = tp_{{+,<_{G} }} (c′, ā). By the induction hypothesis G(N) ⊧ ψ(c′+ ∑ _{i∈I_{0}} a_{i}, ā) implies G(N) ⊧ ψ(d′+ ∑ _{i∈I_{0}} b_{i}, b̄). Hence G(N) ⊧ ∃y ψ(y, b̄), completing the proof of the lemma. □

Theorem 2.1. (i) Two countable models of Th(M) are isomorphic iff their L-sorts are isomorphic iff their G-sorts are isomorphic.

(ii) I(ℵ_{0}, Th(G(M))) = I( ℵ_{0}, Th(L(M))) = I(ℵ_{0}, Th(M)).

(iii) The structure M is saturated.

Proof. (i) Let U be an ℵ_{1}-saturated model of Th(M). Since any countable model embeds into U, it suffices to prove the claim for elementary submodels of U. We have already noted that isomorphism of G-sorts implies isomorphism of full L^{∗}-structures. Trivially, isomorphism of full L^{∗}-structures implies isomorphism of their L-parts. It remains to prove that isomorphism of L-parts implies isomorphism of L^{∗}-structures. So assume that N_{1} ≺ U and N_{2} ≺ U are countable and that L(N_{1}) and L(N_{2}) are isomorphic. Let f : L(N_{1}) → L(N_{2}) be an isomorphism.

Choose a linearly ordered base A = (a_{l} | l ∈ L(N_{1}) ∖ {0}) of G(N_{1}) such that π^{N_{1}} (a_{l}) = l, and choose a linearly ordered base B = (b_{f(l)} | l ∈ L(N_{1}) ∖ {0}) of G(N_{2}) such that π^{N_{2}} (b_{f(l)} ) = f(l). Since f is an isomorphism, we have

π^{U} (a_{l} | l ∈ L(N_{1}) ∖ {0}) ≡_{L} π^{U} (b_{f(l)} | l ∈ L(N_{1}) ∖ {0}).

By Lemma 2.4 the mapping F : A → B defined by F (a_{l}) = b_{f(l)} is partial elementary. It extends to a partial elementary mapping of their definable closures (in U). The extension maps span(A) onto span(B) and is an isomorphism of G(N_{1}) and G(N_{2}). Hence N_{1} and N_{2} are isomorphic.

(ii) Follows from part (i).

(iii) By assumption L(M) is saturated, so we prove that G(M) is saturated, too. Let A ⊂ G(M) be finite and let p be a complete L_{G}-type over A in one variable. After replacing A by a linearly ordered base of span(A) we may assume that A = (a_{l_{0}} , …, a_{l_{n}} ) is an increasing chain of non-zero elements of G(M) such that π^{M} (a_{l_{i}} ) = l_{i}. Suppose that N_{0} ≻ M is countable and that p is realized in G(N_{0}). By taking the union of an appropriately formed ω-chain of countable, elementary extensions of N_{0}, we get a countable N such that L(N) is saturated. Since L(M) and L(N) are countable and saturated, there is an isomorphism f between them fixing pointwise {l_{0}, …, l_{n}}.

By Lemma 2.2(v) there exists a linearly ordered base A′ ⊃ A of G(M) with A′ = (a_{l} | l ∈ L(M) ∖ {0}) such that π^{M} (a_{l}) = l. Similarly, there is a linearly ordered base B′ ⊃ A of G(N) such that: B′ = (b_{f(l)} | l ∈ L(M) ∖ {0}) and π^{N} (b_{f(l)} ) = f(l). Since {l_{0}, …, l_{n}} is fixed pointwise by f and A ⊂ B′, we have b_{f(l_{i} )} = a_{l_{i}} for all i ⩽ n. By Lemma 2.4 we conclude that F : B′ → A′ defined by F (b_{f(l)} ) = a_{l} is a partial elementary mapping. It extends to a partial elementary mapping F′ of dcl_{M} (B′) onto dcl_{N} (A′), and F′ is a bijection of span(B′) = G(N) and span(A′) = G(M). Hence F′ is an isomorphism of G(N) and G(M).

The type p is realized in N because N_{0} ≺ N. Let c ∈ G(N) realize p. Then F′(c) realizes p (because A is fixed pointwise by F′) so p is realized in G(M). We have just shown that all 1-types over a finite sub-domain of G(M) are realized in G(M). Hence G(M) is saturated. □

Now we can easily prove Theorem 1.1:

Proof of Theorem 1.1. Let Q_{0} be the set of all non-negative rational numbers and let (c_{n} | n ∈ ω) be an increasing sequence of positive rationals converging to \sqrt{2}. Consider the structure L = (Q_{0}, <, R_{n})_{n∈ω} where < is a natural ordering and each R_{n} is a unary predicate satisfied exclusively by c_{n}. Then Th(L) is a modification of the Ehrenfeucht’s example, having three countable models, and L is saturated. Let M be two sorted structure constructed as above. Then, by Theorem 2.1(ii), G(M) is an Abelian group with an Ehrenfeucht theory. □

Proposition 2.1. There is an uncountable M′ ≻ M such that L(M′) = L(M).

Proof. First of all we prove that M has a proper, saturated, elementary submodel N such that L(N) = L(M). Fix a decreasing sequence I = (l_{i} | i ∈ ω) of elements of L(M). For i ∈ ω let a_{l_{i}} = e_{l_{i}} + e_{l_{i+1}} , otherwise let a_{l} = e_{l}. Let A = (a_{l} | l ∈ L(M)). Then A is linearly independent and contains one representative from each non-zero ∼-class. Let N be the submodel of M whose G-sort is span(A).

We claim that e_{l_{i}} ∉ G(N) for all i ∈ ω. Towards contradiction assume that e_{l_{i}} ∈ G(N) for some i ∈ ω. Then e_{l_{i}} ∈ span(A) so there are finite sets J_{0} ⊂ ω and J_{1} ⊂ L(M) ∖ I such that:

e_{l_{i}} = ∑_{j∈J_{0}} a_{l_{j}} + ∑_{k∈J_{1}} e_{k} = ∑_{j∈J_{0}} (e_{l_{j}} + e_{l_{j+1}} ) + ∑_{k∈J_{1}} e_{k}.

Since {e_{l} | l ∈ L(M)} is linearly independent, all the e’s, but one e_{l_{i}} cancel in the sum on the right-hand side. If k ∈ J_{1}, then e_{k} does not appear in the first sum, so it cannot be canceled, so e_{k} ≠ e_{l_{i}} implies J_{1} = ∅. Hence e_{l_{i}} = ∑ _{j∈J_{0}} e_{l_{j}} + e_{l_{j+1}} . The sum on the right-hand side has even number of summands and after all possible cancelations the number remains even. A contradiction.

Therefore, although A contains a representative of each non-zero ∼-class, it is not a basis of G(M). In particular N ⊊ M. As in the proof of Theorem 2.1 we show that the inclusion is elementary: by Lemma 2.4 F (a_{l}) = e_{l} defines a partial elementary mapping from A onto E (within M) which extends to an elementary embedding of span(A) onto span(E). The embedding is an isomorphism of G(N) and G(M).

By induction one constructs a continuous, strictly increasing, elementary chain (M_{ξ} | ξ ∈ ω_{1}) of countable, saturated models such that M_{0} = N, M_{1} = M, and L(M_{ξ}) = L(M) holds for all ξ < ω_{1}. Let M′ be the union of the chain. Clearly, M′ is an uncountable elementary extension of M and L(M) = L(M′). □

3. Questions

By an Ehrenfeucht group we will mean a group whose theory is an Ehrenfeucht theory. The following question is quite natural:

Question 3.1. Is there a pure Ehrenfeucht group?

Mekler’s construction [5] suggests the possibility of constructing such a group. Namely, he proved that any structure in a finite relational language can be interpreted in a (pure) nilpotent group. However, the major problem is that it is not clear whether there is an Ehrenfeucht theory in a finite relational language. We also note that there is no such pure Abelian group: it is well known that the theory of any pure Abelian group is stable and 1-based. By [7] there is no such Ehrenfeucht theory.

Our construction produces groups of exponent 2 and it cannot be modified to produce groups without torsion. That raises questions:

Question 3.2. Is every Ehrenfeucht group a torsion group?

Question 3.3. Does every Abelian Ehrenfeucht group have finite exponent?

Finally, our construction relies on the existence of a linear order. It is interesting to know whether any such group has a definable ordering.

Question 3.4. Does every Ehrenfeucht group have the strict order property?

According to Theorem 2 from [10], any Ehrenfeucht theory with infinitely many definable elements has the strict order property. Therefore, if an Ehrenfeucht group has a 0-definable element of infinite order, then dcl(∅) is infinite and the theory has the strict order property. This suggests that the answer to Question 3.4 may be affirmative.

References

1. T. Gogacz, K. Krupinski, On regular groups and fields, arXiv:1211.3852

2. W. Hodges, Model Theory, Cambridge University Press (1993)

3. K. Krupinski, On minimal and quasiminimal groups and fields, preprint (2009)

4. K. Krupinski, P. Tanović, F. O. Wagner, Around Podewski’s conjecture, Fund. Math. (to appear); arXiv:1201.5709

5. A. H. Mekler, Stability of nilpotent groups of class 2 and prime exponent, J. Symbolic Logic 46 (1981), 781–788.

6. M. G. Peretyatkin, On complete theories with a finite number of denumerable models, Algebra and Logic 12 (1973), 310–326.

7. A. Pillay, Stable theories, pseudoplanes and the number of countable models, Ann. Pure Appl. Logic 43 (1989), 147–160.

8. A. Pillay, P. Tanović, Generic stability, regularity, and quasiminimality, in: B. Hart, T. G. Kucera, A. Pillay, P. J. Scott, R. A. G. Seely (eds.), Models, Logics and Higher-Dimensional Categories, A Tribute to the Work of Mihály Makkai, CRM Proc. Lect. Notes 53 (2011), pp. 189–211; arXiv:0912.1115v1

9. S. Sudoplatov, The Lachlan Problem, Novosibirsk, 2008

10. P. Tanović, On constants and the strict order property, Arch. Math. Logic 45 (2006), 423–430.

11. R. L. Vaught, Denumerable models of complete theories, in: Infinitistic Methods: Proceedings of the Symposium on Foundations of Mathematics, Panstwowe Wydawnictvo Naukowe, 1961, pp. 303–321.

12. R. E. Woodrow, Theories with a finite number of countable models, J. Symbolic Logic 43 (1978), 442–455.

Faculty of Transport and Traffic Engineering (Received 11 02 2014) University of Belgrade Serbia

d.ilic@sf.bg.ac.rs

Faculty of Mathematics University of Belgrade Serbia

slavko@matf.bg.ac.rs

Mathematical Institute SANU and Faculty of Mathematics University of Belgrade Serbia

tane@mi.sanu.ac.rs