A QUASI-O-MINIMAL GROUP WITHOUT THE EXCHANGE PROPERTY

OLEG BELEGRADEK, FRANÇOISE POINT, AND FRANK O. WAGNER

Abstract. We construct an example of a quasi-o-minimal group without the Exchange Property.

A structure ⟨M, <, … ⟩ is called quasi-o-minimal [1] if in any structure elementarily equivalent to it the definable subsets are exactly the Boolean combinations of 0definable subsets and intervals. A complete theory T is said to have the Exchange Property if, for any model M of T and for any X ⊆ M and b, c ∈ M,

if b ∈ acl(X ∪ {c}) but b ∉ acl(X), then c ∈ acl(X ∪ {b}).

In general, in contrast to o-minimal theories, the theory of a quasi-o-minimal structure need not satisfy the Exchange Property; an easy counterexample can be found in [1]. However, that example does not carry a group structure; in fact it is also shown there that any quasi-o-minimal expansion of ⟨ℤ, +, <⟩ does have the Exchange Property. In this note we shall prove that the theory of the expansion A of the lexicographically ordered group ℤ × ℤ by the unary operation (x, y) ↦ (0, x) and the constant (1, 0) is quasi-o-minimal and does not have the Exchange Property. It suffices to prove that the theory of a certain definitional expansion M of A is quasi-o-minimal and does not have the Exchange Property.

Let M be the expansion of A in the signature

L = {<, +, −, 0, 1′, 1′′, D_{n}, f}_{n≥1},

where − is subtraction, 1′ and 1′′ are interpreted as (0, 1) and (1, 0), respectively; f is interpreted as the map (x, y) ↦ (0, x), and D_{n}(a) means ‘n divides a’, for any positive integer n. Clearly, M is a definitional expansion of A.

We shall find a set of first order L-sentences T, each of which holds in M, and show that the theory T admits quantifier elimination. We shall prove that M is embeddable into any model of T. Therefore T is complete and hence is an axiom system for Th(M). Using quantifier elimination for T we shall deduce quasi-o-minimality of M. Even though in M itself the Exchange Property trivially holds (as every element of M is definable), we shall construct a model of T in which the Exchange Property fails.

Date: September 30, 1998.

1991 Mathematics Subject Classification. Primary: 03C67; Secondary: 20E36, 06F15, 03C60.

Work partially done while the authors were visiting the Mathematical Sciences Research Institute, Berkeley. Research at MSRI is supported in part by NSF grant DMS-9701755.

Point is a Senior Research Associate at the ”Fonds National de la Recherche Scientifique”.

Wagner is supported by a Heisenberg-Stipendiat der Deutschen Forschungsgemeinschaft (Wa 899/2-1).

Let T be the following set of first-order L-sentences:

1. the axioms of linearly ordered abelian groups;

2. f is an endomorphism of the ordered group;

3. Ker(f) = Rng(f);

4. 1′ is the least positive element;

5. f(1′′) = 1′;

6. for any element a, there are unique integers i, j with 0 ≤ i, j < n such that a and i1′′ + j1′ are congruent modulo n;

7. ∀x (D_{n}(x) ↔ ∃y ny = x). Here 6 and 7 are axiom schemes in which n runs over all positive integers.

Clearly, M is a model of T. From now on, let G be an arbitrary model of T. In particular, G is an expansion of an ordered abelian group, and f is an orderpreserving group endomorphism of G. Let K be the kernel of f in G; it is easy to see that K is a convex pure subgroup of G.

For integers i, j, we will denote the L-term i1′′ + j1′ by c_{ij}. Axioms 3 and 5 imply f(1′) = 0, and so f(c_{ij}) = c_{0i} in G.

Theorem 1. M embeds naturally into G via the map α : (i, j) ↦ c_{ij}.

Proof. Clearly, α preserves +, −, and 0; using Axiom 6, it preserves D_{n}, for every n > 0. Obviously, α preserves 1′ and 1′′.

To show that α preserves strict order it suffices to prove that α maps the positive elements into the positive elements. Suppose (i, j) > (0, 0); then either i > 0, or i = 0 and j > 0. If i > 0 we have f(c_{ij}) = i1′ > 0, by Axiom 4, and hence c_{ij} > 0. If i = 0 and j > 0 we have c_{ij} = j1′ > 0 by Axiom 4.

Since the map α preserves strict order, it is injective. Finally, α preserves f because

α(f(i, j)) = α(0, i) = c_{0i} = f(c_{ij}) = f(α(i, j)).

Theorem 2. T admits quantifier elimination.

Proof. For the proof we need a series of lemmata.

Lemma 3. Every L-term t(x_{1}, …, x_{k}) is T -equivalent to a term of the form

∑_{s=1}^{k}(n_{s}x_{s} + m_{s}f(x_{s})) + c_{ij},

where i, j and n_{s}, m_{s} for 1 ≤ s ≤ k are integers.

Proof of Lemma 3. By induction on the complexity of the term t, using the identities f(x ± y) = f(x) ± f(y), f(1′) = 0, and f(1′′) = 1′.

Lemma 4. For a positive integer n, the following equivalences hold in T:

(i) nx + mf(x) = u ≡ n^{2}x = nu − mf(u), (ii) nx + mf(x) < u ≡ nf(x) < f(u) ∨ (nf(x) = f(u) ∧ n^{2}x < nu − mf(u)), (iii) nx + mf(x) > u ≡ nf(x) > f(u) ∨ (nf(x) = f(u) ∧ n^{2}x > nu − mf(u)).

Proof of Lemma 4. (i) As f^{2} = 0, we have

nx + mf(x) = u ≡ n^{2}x + mnf(x) = nu ∧ nf(x) = f(u)
≡ n^{2}x + mf(u) = nu ∧ nf(x) = f(u)
≡ n^{2}x = nu − mf(u).

(ii) Suppose nx + mf(x) < u. Then nf(x) ≤ f(u). If nf(x) = f(u), then n^{2}x < nu − mf(u).

Conversely, first suppose nf(x) < f(u). Then f(nx + mf(x)) < f(u), whence nx + mf(x) < u. Second, suppose nf(x) = f(u) and n^{2}x < nu − mf(u). Then again nx + mf(x) < u.

(iii) Similar to (ii).

Lemma 5. Every L-formula of the form ∃xϕ(x, ȳ), where ϕ is quantifier-free, is T -equivalent to an L-formula of the form ⋁_{i}(ψ_{i}(ȳ) ∧ ∃x ⋀_{j} ϕ_{ij}(x, ȳ)), where ψ_{i} is quantifier-free and each ϕ_{ij} is of one of the forms:

1. nx + mf(x) = v,

2. nx + mf(x) < v,

3. v < nx + mf(x). Here v is an L-term in variables ȳ, and n, m are integers.

Proof of Lemma 5. As for any positive integers n, m and any term t the formula D_{m}(t) is T -equivalent to D_{nm}(nt), we may assume that for all subformulae of ϕ of the form D_{m}(t) the numbers m are the same.

First we prove that for every positive integer m any L-formula of the form D_{m}(t) or ¬D_{m}(t), where t is an L-term in x, ȳ, is T -equivalent to a positive Boolean combination of formulae of the forms D_{m}(p) or D_{m}(x − c_{ij}), where p is an L-term in ȳ. As ¬D_{m}(t) is T -equivalent to

⋁{D_{m}(t − c_{ij}) : 0 ≤ i, j < m, (i, j) ≠ (0, 0)}

by Axioms 6 and 7, we need only consider formulae D_{m}(t). By Lemma 3, we may assume that t has the form nx + kf(x) + s(ȳ), where s(ȳ) is some term in ȳ. Axioms 6 and 7 imply that the formula D_{m}(nx + kf(x) + s(ȳ)) is T -equivalent to

⋁_{0≤i,j<m}(D_{m}(x − c_{ij}) ∧ D_{m}(nc_{ij} + kf(c_{ij}) + s(ȳ)).

Now, using Lemma 3, the equivalences of the theory of linear orderings

u ≠ v ≡ u < v ∨ v < u,
u ≮ v ≡ u = v ∨ v < u,

and standard equivalences of the first order logic, it is easy to show that ∃xϕ(x, ȳ) is T -equivalent to an L-formula of the form ⋁_{i}(ψ_{i}(ȳ) ∧ ∃x ⋀_{j} ϕ_{ij}(x, ȳ)), where ψ_{i} is quantifier-free and each ϕ_{ij} is of one of the forms 1–3, or of the form

4. D_{k}(x − c_{pq}).

We may assume that ⋀_{j} ϕ_{ij} contains at most one conjunct of the form 4, because D_{k}(x − t) ∧ D_{k}(x − t′) is T -equivalent to D_{k}(x − t) ∧ D_{k}(t − t′).

Suppose ⋀_{j} ϕ_{ij} is of the form θ(x, ȳ) ∧ D_{k}(x − c_{pq}). Then ∃x ⋀_{j} ϕ_{ij} is T -equivalent to ∃xθ(c_{pq} +kx, ȳ). Clearly, θ(c_{pq} +kx, ȳ) is T -equivalent to a conjunction of formulae of the forms 1–3.

So ∃xϕ(x, ȳ) is T -equivalent to a formula of desired form.

Now, in order to prove Theorem 2, it suffices to show that any formula ∃x ⋀_{i} ϕ_{i}(x, ȳ), where each ϕ_{i} is of one of the forms 1–3, is equivalent to a quantifier-free L-formula. By Lemma 4 we may assume that in each ϕ_{i} exactly one of the coefficients n, m is nonzero. So we may assume ϕ_{i} to be of one of the forms

(i) nx = v, (ii) nf(x) = v, (iii) nx < v, (iv) nf(x) < v,

(v) nx > v, (vi) nf(x) > v, where n > 0. Since y = z is T -equivalent to my = mz, and y < z is T -equivalent to my < mz, for any positive m, we may assume that the coefficient n in ϕ_{i} does not depend on i. Further, we may assume that, for each of the six forms, at most one of ϕ_{i} is of this form. This last observation is seen easily, e.g. in case (iii) from the T -equivalence of nx < u ∧ nx < u′ and

(nx < u ∧ u ≤ u′) ∨ (nx < u′ ∧ u′ ≤ u).

Lemma 6. For every n < ω there is a quantifier-free L-formula ϑ_{n}(y, z) which is T -equivalent to ∃x (y < nx < z).

Proof. The assertion is obvious for n = 0, so assume n ≥ 1. Put ϑ_{n} := ϕ ∨ ψ, where

\begin{aligned}ϕ(y, z) & := ⋁_{j=1}^{n}(D_{n}(y + j1′) ∧ y + j1′ < z) \\ ψ(y, z) & := ⋁_{i=1}^{n−1} ⋁_{j=1}^{n}(D_{n}(y + c_{ij}) ∧ 2(y + c_{ij}) < 2z + 1′′). \end{aligned}

Suppose y < nx < z for elements x, y, z in a model of T. By Axiom 6 there are unique 0 ≤ i < n and 0 < j ≤ n such that y + c_{ij} is divisible by n. If y + c_{ij} < z, then ϑ_{n}(y, z) holds (either ϕ or ψ, depending on whether i = 0 or not). Otherwise 0 < z − nx ≤ y + c_{ij} − nx < y + c_{ij} − y = c_{ij}; since j ≤ n and y + c_{ij} − nx is divisible by n, necessarily i > 0 by Axiom 4. But f(y + c_{ij} − nx) is also divisible by n, and

f(y + c_{ij} − z) ≤ f(y + c_{ij} − nx) ≤ f(y + c_{ij} − y) = i1′;

as i < n, we get f(y + c_{ij} − nx) ≤ 0 by Axiom 4. It follows that 2f(y + c_{ij} − z) ≤ 0, whence 2(y + c_{ij} − z) < 1′′ and ψ(y, z) holds.

Conversely, suppose ϑ_{n}(y, z) for some y, z in a model of T. If ϕ(y, z) holds, we immediately obtain ∃x (y < nx < z). Suppose ψ(y, z) holds, and let 0 < i < n and 0 < j ≤ n be such that D_{n}(y+c_{ij})∧2(y+c_{ij}) < 2z+1′′ holds. Put u := y+c_{ij} −z+1′. If u ≤ 0, then y + c_{ij} < z and we are done. Suppose u > 0. We have 2f(u) ≤ 1′, whence f(u) ≤ 0 by Axiom 4, so f(nu) ≤ 0 and nu < 1′′. Clearly y + c_{ij} − nu is divisible by n; furthermore

y < y + 1′′ − nu ≤ y + c_{ij} − nu = z − 1′ − (n − 1)u < z,

and we are done again.

Remark. The result of Lemma 6 can be also extracted from [2]. There, Weispfennig gives an explicit axiom set T_{0} for the theory of the (L \ {f})-reduct of M and proves quantifier elimination for T_{0}; it can then be checked that T proves T_{0}. However, in order to make the proof of Theorem 2 self-contained, we have prefered to give a direct argument.

Lemma 7. If among the formulae ϕ_{i} there is a formula of the form (i) or (ii), then ∃x ⋀_{i} ϕ_{i}(x, ȳ) is T -equivalent to a quantifier-free L-formula.

Proof of Lemma 7. First suppose that among the formulae ϕ_{i} there is a formula of the form (i). The formula ∃x ⋀_{i} ϕ_{i}(x, ȳ) is of the form ∃x(nx = v ∧ ψ(nx, ȳ)), where ψ is a quantifier-free formula, and so is T -equivalent to the quantifier-free L-formula D_{n}(v) ∧ ψ(v, ȳ).

Now suppose that among the formulae ϕ_{i} there is no formula of the form (i); so one of the formulae ϕ_{i} is of the form (ii). We may assume that among the formulae ϕ_{i} there is no formula of the forms (iv), (vi). Indeed, say, nf(x) = v ∧ nf(x) < u is T -equivalent to nf(x) = v ∧ v < u.

Thus, we assume that among the ϕ_{i} exactly one is of the form (ii), all others are of the forms (iii) or (v), and there is at most one of each of these forms. So it suffices to prove that the formula ϕ := ∃x (nf(x) = v ∧ u < nx < w) is T -equivalent to the quantifier-free L-formula

θ := D_{n}(v) ∧ f(v) = 0 ∧ f(u) ≤ v ≤ f(w) ∧ ϑ_{n}(u, w),

where ϑ_{n} is the quantifier-free formula obtained in Lemma 6. Here we allow u = −∞ or w = ∞ (and mean that the corresponding inequality and ϑ_{n} are omitted; in these cases the proofs are just simplier).

As f^{2} = 0, clearly ϕ implies θ. Conversely, suppose θ holds. Since Ker(f) is a pure subgroup, and Ker(f) = Rng(f), there is y with v = nf(y), due to the first two conjuncts of θ. If f(u) < v < f(w), then u < ny < w and ϕ holds. Suppose v = f(u). Axiom 6 implies that u + c_{ij} is divisible by n, for some 0 ≤ i < n and 1 ≤ j ≤ n. Then f(u + c_{ij}) = v + i1′ is also divisible by n, and so i = 0 by Axiom 4. Therefore n divides u + j1′. We have u + j1′ < w; otherwise, due to ϑ_{n}(u, w), there is z with u + j1′ > nz > u, and the interval (0, j1′) contains the element u + j1′ − nz divisible by n, in contradiction to Axiom 4. As f(u + j1′) = v and v < u + j1′ < w, the formula ϕ holds. The case v = f(w) is similar.

Lemma 8. If each ϕ_{i} is of one of the forms (iii)–(vi) then ∃x ⋀_{i} ϕ_{i}(x, ȳ) is T -equi-valent to a quantifier-free L-formula.

Proof of Lemma 8. First note that we may assume that among the ϕ_{i} there is no formula of the forms (iii) and (v). Indeed, the formula y < z is T -equivalent to

(f(y) < f(z)) ∨ (f(y) = f(z) ∧ y < z).

Therefore, say, ∃x(θ ∧ nx < u) is T -equivalent to

∃x(θ ∧ nf(x) < f(u)) ∨ ∃x(θ ∧ nf(x) = f(u) ∧ nx < u).

The second disjunct of the latter formula is T -equivalent to a quantifier-free L-for-mula by Lemma 7.

So it suffices to prove that the formula ϕ := ∃x(u < nf(x) < w) is T -equivalent to the quantifier-free formula

θ := f(u) ≤ 0 ≤ f(w) ∧ ϑ_{n}(u, w),

where again we allow u = −∞ or w = ∞, and ϑ_{n} is the formula from Lemma 6.

As f^{2} = 0, clearly ϕ implies θ. Conversely, assume θ. If u < 0 < w then ϕ obviously holds; so we may assume that 0 ≤ u or w ≤ 0.

Suppose 0 ≤ u; then f(u) = 0. If f(w) = 0 then ϕ holds because ϑ_{n}(u, w) is true, and Ker(f) = Rng(f) is a convex pure subgroup. Suppose f(w) ≠ 0. Axiom 6 implies that y = u + 1′ + c_{ij} is divisible by n for some 0 ≤ i, j < n; since f(y) = f(u) + i1′ = i1′ is also divisible by n, we get i = 0 by Axiom 4, and f(y) = f(u) = 0. As Ker(f) = Rng(f) is a pure subgroup, y = nf(x), for some x. Since f(y) = 0 and Ker(f) is convex, u < y < w, and so the formula ϕ holds. The case w ≤ 0 is similar.

The proof of Theorem 2 is completed.

From Theorems 1 and 2 we immediately obtain

Theorem 9. The theory T is complete.

Theorem 10. The theory T is quasi-o-minimal. Moreover, every definable set in a model G of T is a Boolean combination of intervals and 0-definable sets of the form

c_{ij} + {x : D_{k}(nx + mf(x))}.

Remark. The set {x : D_{k}(nx + mf(x))} is a 0-definable subgroup, so the definable sets in G are exactly the Boolean combinations of intervals and cosets of definable subgroups.

Proof. By Lemmata 3, 4, and quantifier elimination for T, it suffices to prove the result for the subsets of G which are defined by the formulae of the following forms:

(a) nx = a,

(b) nx > a,

(c) nf(x) = a,

(d) nf(x) > a,

(e) D_{k}(nx + mf(x) + a).

Here a ∈ G, and k, n, m are integers, k > 0.

Let L_{0} = L \ {f}, and M_{0} be the L_{0}-reduct of M. It had been proven in [1] that every definable set in a model G_{0} of the L_{0}-theory of M_{0} is a Boolean combination of intervals and 0-definable sets of the form c_{ij} + nG_{0}. So in cases (a) and (b) the desired result holds.

Consider case (c). If a ∉ Rng(f) then nf(x) = a defines the empty set. Suppose a = f(b). Then in G the formula nf(x) = a is equivalent to f(nx−b) = 0. Note that in M (and so in G, due to completeness of T) the formula f(x) = 0 is equivalent to the L_{0}-formula −1′′ < 2x < 1′′. Therefore nf(x) = a is equivalent to −1′′ < 2(nx − b) < 1′′, and the result follows from case (b).

Consider case (d). We may assume that both of the sets {x : nf(x) > a} and {x : nf(x) ≤ a} are non-empty. Then f(a) = 0, as we see by applying f to the inequalities. As Ker(f) = Rng(f), we have a = f(b) for some b. Then nf(x) > a is equivalent in G to nx > b ∧ nf(x) ≠ a, and the result follows from cases (b) and (c).

Finally, consider case (e). As the difference of any two elements in the set {x : D_{k}(nx + mf(x) + a)} lies in the subgroup {x : D_{k}(nx + mf(x))}, and that subgroup has the set {c_{ij} : 0 ≤ i, j < k} as coset representatives by Axiom 6, the formula D_{k}(nx + mf(x) + a) defines either the empty set, or one of those cosets.

Theorem 11. The theory T does not have the Exchange Property.

Proof. Let B be the lexicographically ordered group ℚ × ℤ, and C be the lexicographically ordered group B × B. Expand C to an L-structure G by defining D_{n}(x) as ‘n divides x’, putting f(x, y) = (0, x) for x, y ∈ B, and setting 1′ = ((0, 0), (0, 1)) and 1′′ = ((0, 1), (0, 0)). It is easy to see that G is a model of T.

Let a = (α, n), where α ∈ ℚ \ {0} and n ∈ ℤ; then a ∈ B. Let b = (0, a) and c = (a, 0); then b, c ∈ G. We have f(c) = b, whence b ∈ acl(c) in G. We will show that in G we have c ∉ acl(b), even though b is not algebraic.

First we prove that b is non-algebraic. For each positive rational β, the map

g_{β} : (γ, m) ↦ (βγ, m)

is an automorphism of the ordered group B. It is easy to check that the map

h_{β} : (x, y) ↦ (g_{β}(x), g_{β}(y))

is an automorphism of the structure G. If β ≠ γ then g_{β}(a) ≠ g_{γ}(a) and so

h_{β}(b) = (0, g_{β}(a)) ≠ (0, g_{γ}(a)) = h_{γ}(b).

Thus the Aut(G)-orbit of b is infinite, and hence b is not algebraic.

Now we prove that c ∉ acl(b). For each positive rational β, the map

q_{β} : (γ, m) ↦ (βγ, 0)

is an endomorphism of the ordered group B, and q_{β}(0, 1) = (0, 0). It is easy to check that the map

s_{β} : (x, y) ↦ (x, y + q_{β}(x))

is an automorphism of the structure (G, b). If β ≠ γ then q_{β}(a) ≠ q_{γ}(a) and so

s_{β}(c) = (a, q_{β}(a)) ≠ (a, q_{γ}(a)) = s_{γ}(c).

Thus the Aut(G, b)-orbit of c is infinite, and hence c ∉ acl(b).

Remark. Since σ_{β} : (x, y) ↦ (x, g_{β}(y)) is an automorphism of C (i.e. the pure ordered group) with f(σ_{β}(x, y)) = (0, x) and σ_{β}(f(x, y)) = (0, g_{β}(x)), it is clear that f is not definable in the pure group language.

.

References

[1] Oleg Belegradek, Ya’akov Peterzil and Frank Wagner, Quasi-o-minimal structures, to appear in the Journal of Symbolic Logic.

[2] Volker Weispfenning, Elimination of quantifiers for certain ordered and lattice-ordered groups, Bull. Soc. Math. Belg., Ser. B, 33 (1981), 131–155.

Oleg Belegradek, Kemerovo University, Kemerovo 650043, Russia

  E-mail address: beleg@kaskad.uucp.stanet.ru

Françoise Point, Institut de Mathématique et Informatique, Université de Mons-Hainaut, Le Pentagone, 6, avenue du Champ de Mars, B-7000 Mons, Belgium

  E-mail address: point@logique.jussieu.fr

Frank Wagner, Mathematical Institute, University of Oxford, 24–29 St Giles’, Oxford OX1 3LB, UK

  E-mail address: wagner@maths.ox.ac.uk