Weak generic types and coverings of groups II

Marcin Petrykowski

Abstract

The notion of a weak generic type in a group was introduced in [4]. In this paper we continue to examine its properties, focussing on groups definable in o-minimal structures. Moreover, some applications of weak generic types to the model theory of groups are given.^{1}

Introduction

In this paper we continue the analysis of the notion of a weak generic type in a group introduced by Newelski in [4]. Our results may be divided into three parts.

First of all, we take a closer look at weak generic sets and types in some particular groups. Note that in a stable group genericity and weak genericity of a definable set are equivalent and the structure of (weak) generic types is well-known. Therefore we focus on cartesian powers of o-minimal groups. Section 2 provides a characterization of their definable weak generic subsets.

Secondly, we give examples where properties of weak generic types are related to well-known model-theoretic properties. In Section 3 we introduce the notion of stationarity of a weak generic type and show (in some special cases) its equivalence with power boundedness.

Finally, in the last section of the paper we use weak generic types to prove some combinatorial properties of countable coverings of ℵ_{0}-saturated groups consisting of 0-type-definable sets. We thus obtain new proofs for some theorems in [4], as well as some new results.

Acknowledgements. The author would like to thank Chris Miller, Ludomir Newelski and Frank Wagner for their helpful suggestions and answering numerous questions.

12000 Mathematics Subject Classification: 03C60, 03C64. Research partially supported by the Polish Government grant no. N201 032 32/2231 and the European Commission Research Training Network project no. MRTN-CT-2004-512234 (MODNET).

1 Preliminaries

In this paper G always denotes a group, possibly with some additional structure, or more generally a definable group in a model M of a complete first order theory T in a language L. We denote the group product of a, b ∈ G by a·b and the group inverse of a by a^{−1}. For the convenience of the reader we recall two definitions from [4].

Definition 1.1 We say that a set X ⊆ G is (left) generic if some finitely many left G-translates of X cover G. We say that a formula φ(x) is (left) generic if the set φ(G) of elements of G realizing φ is (left) generic. Finally, we call a type p(x) of elements of G (left) generic if every formula φ(x) with p(x) ⊢ φ(x) is (left) generic.

Definition 1.2 We say that a set X ⊆ G is weak generic if for some non-generic set Y ⊆ G the set X ∪ Y is generic. We say that a formula φ(x) is weak generic if the set φ(G) is weak generic. Finally, a type p(x) of elements of G is weak generic if every formula φ(x) with p(x) ⊢ φ(x) is weak generic.

Basic properties of weak generic sets and types have been established in [4]. Below we prove some more lemmas that will be used later in the paper. Before doing it we have to make some notational remarks. First of all, for the sake of notational simplicity we shall sometimes assume that |G| = |M| (i.e. the universes of the group G and the model M are the same), especially in Sections 1 and 4. Secondly, for A ⊆ M we denote the set {p ∈ S(A) : p is weak generic in G} by W Gen(A). Finally, if g ∈ G, φ(x) is a formula and p(x) is a type, then g · φ(x) stands for the formula φ(g^{−1} · x) and g · p(x) denotes the type {g · ψ(x) : ψ(x) ∈ p(x)}.

Lemma 1.3 If X ⊆ G is (left) generic, then X is right weak generic.

Proof. Suppose that X is generic. Then we have G = ⋃_{i=1}^{n} g_{i} · X for some finitely many g_{1}, …, g_{n} ∈ G. Since the set G is right weak generic, for some i ∈ {1, …, n} the set g_{i} · X is right weak generic. But this implies that the set X is also right weak generic and we are done. □

Lemma 1.4 Assume that G ≺ H are groups and φ(x) ∈ L(G).

(1) If φ(G) is weak generic in G, then φ(H) is weak generic in H.

(2) If G is ℵ_{0}-saturated and φ(H) is weak generic in H, then φ(G) is weak generic in G.

Proof. (1) If the set φ(G) is weak generic in G, then there is a non-generic formula ψ(x) ∈ L(G) such that the set φ(G) ∪ ψ(G) is generic in G. Since G ≺ H, the set ψ(H) is not generic in H and the set φ(H) ∪ ψ(H) is generic in H. Thus φ(H) is weak generic in H.

(2) There exists a formula ψ(x) ∈ L(H) such that ψ(H) is not generic in H and φ(H) ∪ ψ(H) is generic in H. We have ψ(x) = ψ(x, b̄), where b̄ ⊆ H are all parameters occurring in ψ(x). Let A ⊆ G be a finite set containing all parameters of φ(x).

By ℵ_{0}-saturation of G we are able to find a tuple ā ⊆ G with tp(ā/A) = tp(b̄/A). Then ψ(x, ā) ∈ L(G) has properties which suffice to obtain weak genericity of the set φ(G) in G.

Namely, ψ(G, ā) is not generic in G and φ(G) ∪ ψ(G, ā) is generic in G. We shall show the first assertion only, the second one may be proved in a similar way. For the sake of contradiction assume that the set ψ(G, ā) is generic in G. Then for some n < ω we have

G ⊧ ∃x_{1}, …, x_{n}∀y∃z(ψ(z, ā) ∧ ⋁_{k=1}^{n} y = x_{k} · z)

and the same holds in H since G ≺ H. As tp(ā) = tp(b̄), we have

H ⊧ ∃x_{1}, …, x_{n}∀y∃z(ψ(z, b̄) ∧ ⋁_{k=1}^{n} y = x_{k} · z).

But then ψ(H) = ψ(H, b̄) is generic in H, a contradiction. □

Lemma 1.5 Assume that A ⊆ G. If for every p, q ∈ W Gen(G) there is some g ∈ G with g · p = q, then all weak generic types r ∈ S(A) are generic.

Proof. If not, then we can find a formula φ(x) ∈ L(A) which is weak generic but not generic. Note that {¬g · φ(x) : g ∈ G} is a partial weak generic type over G (because for each m < ω and g_{1}, …, g_{m} ∈ G the set ⋃_{i=1}^{m} g_{i} ·φ(G) is not generic, which implies that the set ⋂_{i=1}^{m}(G \ g_{i} · φ(G)) is weak generic). Extend the type {¬g · φ(x) : g ∈ G} to some q(x) ∈ W Gen(G) and the formula φ(x) to some p(x) ∈ W Gen(G). Then (∀g ∈ G)g · p ≠ q, a contradiction. □

Lemma 1.6 If for some type p ∈ S(G) the orbit {g · p : g ∈ G} is finite, then p is weak generic.

Proof. For the sake of contradiction assume that the type p is not weak generic. Let {g · p : g ∈ G} = {p_{1}, …, p_{n}}. We can find pairwise inconsistent non-weak generic formulas φ_{1}(x), …, φ_{n}(x) such that φ_{i} ∈ p_{i} for each i ∈ {1, …, n}. Put ψ = φ_{1} ∨ … ∨ φ_{n}. Then for every g ∈ G and i ∈ {1, …, n} we have g · ψ ∈ p_{i}. On the other hand, the formula ¬ψ is generic (since ψ is not weak generic) and for some finitely many g_{1}, …, g_{k} ∈ G we have G = ⋃_{j=1}^{k} g_{j} · ¬ψ(G). Hence ⋂_{j=1}^{k} g_{j} · ψ(G) = ∅, contradicting the fact that g_{j} · ψ ∈ p_{1} for every j ∈ {1, …, k}. □

Assume that (X, <) is a totally ordered set and a, b ∈ X. We denote the open interval with the endpoints a and b by (a, b) and the closed one by [a, b]. In contrast, ⟨a, b⟩ stands for the pair of elements a and b. If Y ⊆ X, then (a, b)_{Y} denotes the set {c ∈ Y : a < c ∧ c < b}.

As we shall mainly consider groups definable in o-minimal structures, we conclude this section with a few words about the notion of o-minimality. We call an infinite totally ordered first order structure (M, <, …) o-minimal if every definable subset of M is a union of finitely many intervals and points.

Let (M, <, …) be an o-minimal structure. If a ∈ M ∪ {−∞}, b ∈ M ∪ {+∞}, a < b and f : (a, b) → M is a definable function, then there are a = a_{1} < … < a_{n} = b such that on each interval (a_{i}, a_{i+1}) f is either constant or strictly monotone and continuous in the order topology. In particular, every definable function f : M → M is ultimately continuous and monotone. Every definable subset A of M^{n} (n < ω) has a finite partition into pairwise disjoint cells, which are definable sets of an especially simple nature. For more details on o-minimal structures see [1].

Lemma 1.7 Assume that M is an o-minimal structure, a, b ∈ M and C ⊆ M. If tp(a/C) ≠ tp(b/C), then [a, b] ∩ dcl(C) ≠ ∅.

Proof. As tp(a/C) ≠ tp(b/C), there is a formula φ(x) ∈ L(C) such that M ⊧ φ(a) and M ⊧ ¬φ(b). By o-minimality of M the set φ(M) is a union of some intervals I_{1}, …, I_{m} and points p_{1}, …, p_{n} (where m, n < ω). Both the points p_{1}, …, p_{n} and the endpoints of the intervals I_{1}, …, I_{m} belong to the definable closure of the set C. Since a ∈ φ(M) and b ∉ φ(M), one of them must also belong to the interval [a, b] and we are done. □

Lemma 1.8 Assume G is a definable group in an o-minimal structure M and X is a definable weak generic subset of G. Then the o-minimal dimensions of X and G are equal.

Proof. For the sake of contradiction suppose that dim(X) < dim(G). Take a generic set A and a non-generic set B such that A = B ∪ X (where A and B are definable subsets of G, apply Lemma 1.3 from [4]). Choose a finite set S ⊆ G with S · A = G. Then G \ (S · B) ⊆ S · X and

dim(G \ (S · B)) ≤ dim(S · X) = dim(X) < dim(G).

Hence the set S · B is large in the sense of [5] and it must be generic by Lemma 2.4 there (a subset Y of a group H is said to be large if the o-minimal dimension of the set H \ Y is strictly smaller than that of the group H). But then B is generic too, a contradiction. □

2 A characterization of weak genericity

In this section we consider o-minimal structures of the form (G, <, +, …) where (G, <, +) is an ordered group. We are going to characterize definable weak generic sets in groups (G^{n}, +), n < ω.

We begin with a lemma on weak generic sets. Assume G is a group and X, Y ⊆ G. The set X is said to be translation disjoint from the set Y if for some a ∈ G the sets a · X and Y are disjoint.

Lemma 2.1 Assume G is a group and X is a weak generic subset of G. Then for some finite A ⊆ G there is no finite covering of X by sets that are translation disjoint from the set A · X.

Proof. By weak genericity of X we can find a generic superset Y ⊇ X such that the set Y \ X is not generic. We have G = A · Y for some finite A ⊆ G. We shall prove that the set A meets the conditions of the lemma. For the sake of contradiction assume that for some X_{1}, …, X_{n} ⊆ G and a_{1}, …, a_{n} ∈ G we have

X = ⋃_{i≤n} X_{i} and ⋀_{i≤n}(a_{i} · X_{i}) ∩ (A · X) = ∅.

Then for each i ≤ n we have a_{i} · X_{i} ⊆ G \ A · X ⊆ A · (Y \ X) and consequently X_{i} ⊆ a_{i}^{−1} · A · (Y \ X). This implies that X ⊆ {a_{1}^{−1}, …, a_{n}^{−1}} · A · (Y \ X) and finally

G = A · Y = A · (Y \ X) ∪ A · X ⊆ (A ∪ (A · {a_{1}^{−1}, …, a_{n}^{−1}} · A)) · (Y \ X).

Thus finitely many left translates of the set Y \ X cover G , a contradiction. □

The corollary below shows that weak genericity is related to generating G. A more detailed analysis of this connection appears in Section 4.

Corollary 2.2 Assume G is a group and X is a weak generic subset of G. Then G = A · X · X^{−1} for some finite A ⊆ G.

Proof. Take a finite A ⊆ G such as in Lemma 2.1. Then for each a ∈ G we have a · X ∩ A · X ≠ ∅, which implies that a ∈ A · X · X^{−1}. Therefore G = A · X · X^{−1} and we are done. □

From now on, let (G, <, +, −, 0, …) be an o-minimal expansion of an ordered group (G, <, +, −, 0). By Theorem 2.1 from [7] the group (G, +) is commutative, divisible and torsion-free. This justifies denoting the group action by +. By (G^{n}, +) we mean the product of groups (G, +) × … × (G, +) (n times). The ordering of G is dense since for every a, b ∈ G with a < b we have a < \frac{a+b}{2} < b.

Theorem 2.3 Assume that (G, <, +, …) is an o-minimal expansion of an ordered group (G, <, +), n < ω and φ(x_{1}, …, x_{n}) ∈ L(G). The following are equivalent:

(1) the formula φ(x_{1}, …, x_{n}) is weak generic in (G^{n}, +),

(2) the formula ¬φ(x_{1}, …, x_{n}) is not generic in (G^{n}, +),

(3) the set φ(G^{n}) contains arbitrarily large n-dimensional boxes:

(∀R > 0)(∃a_{1}, …, a_{n} ∈ G)[a_{1}, a_{1} + R] × … × [a_{n}, a_{n} + R] ⊆ φ(G^{n}).

Proof. (3) ⇒ (2) Assume that the condition (3) holds and for the sake of contradiction suppose that for some k < ω and ⟨g_{1}^{1}, …, g_{n}^{1}⟩, …, ⟨g_{1}^{k}, …, g_{n}^{k}⟩ ∈ G^{n} we have

G^{n} = ⋃_{j=1}^{k}(⟨g_{1}^{j}, …, g_{n}^{j}⟩ + (G^{n} \ φ(G^{n}))).

Put M = max{|g_{i}^{j}| : 1 ≤ i ≤ n, 1 ≤ j ≤ k}. Using (3) for R = 2M we are able to find a_{1}, …, a_{n} ∈ G such that

[a_{1} − M, a_{1} + M] × … × [a_{n} − M, a_{n} + M] ⊆ φ(G^{n}).

But then

⟨a_{1}, …, a_{n}⟩ ∉ ⋃_{j=1}^{k}(⟨g_{1}^{j}, …, g_{n}^{j}⟩ + (G^{n} \ φ(G^{n}))),

a contradiction.

(2) ⇒ (1) Since the set G^{n} = φ(G^{n}) ∪ (G^{n} \ φ(G^{n})) is generic in (G^{n}, +) and the set G^{n} \ φ(G^{n}) is not generic in (G^{n}, +), the set φ(G^{n}) is weak generic in (G^{n}, +).

(1) ⇒ (3) Suppose that n = 1. By o-minimality of G the set φ(G) is a union of finitely many intervals and points. Corollary 2.2 implies that the set φ(G) − φ(G) is generic in G so one of these intervals must be of the form (−∞, a) or (b, +∞) and we are done. Therefore we can assume that n ≥ 2.

Take p(x_{1}, …, x_{n}) ∈ S_{n}(G) such that p is a weak generic type in (G^{n}, +) and φ ∈ p. Extend G to a |G|^{+}-saturated group H ≻ G. Choose a tuple ⟨a_{1}, …, a_{n}⟩ ∈ H^{n} realizing p and fix a positive R ∈ G. We shall show that the following condition holds:

(∗) (∀a ∈ H)(a_{n} ≤ a ∧ a ≤ a_{n} + R ⇒ tp(a/Ga_{<n}) = tp(a_{n}/Ga_{<n})),

where a_{<n} stands for ⟨a_{1}, …, a_{n−1}⟩.

For the sake of contradiction assume that for some a ∈ [a_{n}, a_{n} + R]_{H} we have tp(a/Ga_{<n}) ≠ tp(a_{n}/Ga_{<n}). By Lemma 1.7 there is b ∈ [a_{n}, a_{n} + R]_{H} ∩ dcl(Ga_{<n}). Let ψ(x_{1}, …, x_{n−1}, y) ∈ L(G) be such that H ⊧ ψ(a_{<n}, b) ∧ ∃!yψ(a_{<n}, y). Since b − R ≤ a_{n} ≤ b, we have χ ∈ p where

χ(x_{1}, …, x_{n}) = ∃!yψ(x_{<n}, y) ∧ ∀y(ψ(x_{<n}, y) → (y − R ≤ x_{n} ∧ x_{n} ≤ y)).

As χ ∈ p, the set χ(G^{n}) is weak generic in (G^{n}, +).

We define a function f : G^{n−1} → G as follows. Take ⟨c_{1}, …, c_{n−1}⟩ ∈ G^{n−1}. If there is c_{n} ∈ G such that G ⊧ χ(c_{1}, …, c_{n}), then there exists just one d ∈ G with G ⊧ ψ(c_{1}, …, c_{n−1}, d) and we put f(c_{1}, …, c_{n−1}) = d − R. Otherwise we put f(c_{1}, …, c_{n−1}) = 0 (the neutral element of G). Then the map f is definable over G and we consider the following formula over G:

δ(x_{1}, …, x_{n}) = f(x_{1}, …, x_{n−1}) ≤ x_{n} ∧ x_{n} ≤ f(x_{1}, …, x_{n−1}) + R.

Since χ(G^{n}) ⊆ δ(G^{n}), the set δ(G^{n}) is weak generic in (G^{n}, +). Let A ⊆ G^{n} be a finite set chosen for δ(G^{n}) as in Lemma 2.1. Consider any ⟨h_{1}, …, h_{n−1}⟩ ∈ H^{n−1}. Choose M_{h_{<n}} ∈ G such that

{⟨h_{1}, …, h_{n}⟩ : f(h_{<n}) + M_{h_{<n}} ≤ h_{n} ≤ f(h_{<n}) + M_{h_{<n}} + R} ∩ (A + δ(H^{n})) = ∅.

If tp(⟨h_{1}, …, h_{n−1}⟩/G) = tp(⟨h′_{1}, …, h′_{n−1}⟩/G), then M_{h_{<n}} is appropriate also for ⟨h′_{1}, …, h′_{n−1}⟩. Thus for each q(x_{1}, …, x_{n−1}) ∈ S_{n−1}(G) we can find a formula φ_{q}(x_{1}, …, x_{n−1}) ∈ L(G) and M_{q} ∈ G such that for every ⟨h_{1}, …, h_{n−1}⟩ ∈ H^{n−1} with H ⊧ φ_{q}(h_{1}, …, h_{n−1}) we have

{⟨h_{1}, …, h_{n}⟩ : f(h_{<n}) + M_{q} ≤ h_{n} ≤ f(h_{<n}) + M_{q} + R} ∩ (A + δ(H^{n})) = ∅.

By compactness S_{n−1}(G) = [φ_{q_{1}}]∪…∪[φ_{q_{k}}] for some k < ω and q_{1}, …, q_{k} ∈ S_{n−1}(G). For each i ∈ {1, …, k} put X_{i} = (φ_{q_{i}}(G^{n−1}) × G) ∩ δ(G^{n}) and e_{i} = ⟨0, …, 0, M_{q_{i}}⟩ (e_{i} ∈ G^{n}). Then δ(G^{n}) = X_{1} ∪ … ∪ X_{k} and for every i ∈ {1, …, k} we have (e_{i} + X_{i}) ∩ (A + δ(G^{n})) = ∅. This contradicts the choice of A and finishes the proof of (∗).

By (∗) we have

H ⊧ ∀y((a_{n} ≤ y ∧ y ≤ a_{n} + R) → φ(a_{1}, …, a_{n−1}, y)).

Therefore the formula

∀y((x_{n} ≤ y ∧ y ≤ x_{n} + R) → φ(x_{1}, …, x_{n−1}, y))

belongs to p(x_{1}, …, x_{n}) = tp(⟨a_{1}, …, a_{n}⟩/G). More generally, for every R ∈ G and formula ψ(x_{1}, …, x_{n}) ∈ p(x_{1}, …, x_{n}), k ∈ {1, …, n} the formula

∀y((x_{k} ≤ y ∧ y ≤ x_{k} + R) → ψ(x_{1}, …, x_{k−1}, y, x_{k+1}, …, x_{n}))

belongs to p(x_{1}, …, x_{n}).

We inductively create formulas φ_{k}(x_{1}, …, x_{n}) ∈ p(x_{1}, …, x_{n}), k ∈ {1, …, n}. Provided that φ_{1}(x_{1}, …, x_{n}),…,φ_{k−1}(x_{1}, …, x_{n}) have already been defined, we let φ_{k}(x_{1}, …, x_{n}) be the formula

∀y((x_{k} ≤ y ∧ y ≤ x_{k} + R) → (φ ∧ φ_{1} ∧ … ∧ φ_{k−1})(x_{1}, …, x_{k−1}, y, x_{k+1}, …, x_{n})).

Finally, we take any ⟨g_{1}, …, g_{n}⟩ ∈ (φ ∧ φ_{1} ∧ … ∧ φ_{n})(G^{n}) and see that

[g_{1}, g_{1} + R] × … × [g_{n}, g_{n} + R] ⊆ φ(G^{n}),

which finishes the proof. □

We conclude this section with two corollaries of Theorem 2.3.

Corollary 2.4 Assume that (G, <, +, …) is an o-minimal expansion of an ordered group (G, <, +), n, k < ω and φ(x_{1}, …, x_{n}, y_{1}, …, y_{k}) ∈ L.

(1) There is ψ_{1}(y_{1}, …, y_{k}) such that for every ⟨a_{1}, …, a_{k}⟩ ∈ G^{k} we have G ⊧ ψ_{1}(ā) if and only if the set φ(G^{n}, ā) is weak generic in (G^{n}, +).

(2) There is ψ_{2}(y_{1}, …, y_{k}) such that for every ⟨a_{1}, …, a_{k}⟩ ∈ G^{k} we have G ⊧ ψ_{2}(ā) if and only if the set φ(G^{n}, ā) is generic in (G^{n}, +).

(3) There exists N < ω such that for every φ-definable X ⊆ G^{n} the set X is generic in (G^{n}, +) if and only if G^{n} may be covered by at most N left translates of X.

Proof. (1) We let ψ_{1}(y_{1}, …, y_{k}) be the formula

∀r∃z_{1}, …, z_{n}∀x_{1}, …, x_{n}((⋀_{i=1}^{n} z_{i} ≤ x_{i} ∧ x_{i} ≤ z_{i} + r) → φ(x_{1}, …, x_{n}, y_{1}, …, y_{k}))

and apply Theorem 2.3.

(2) By Theorem 2.3 the set φ(G^{n}, ā) is generic in (G^{n}, +) if and only if the set ¬φ(G^{n}, ā) is not weak generic in (G^{n}, +). Now it suffices to make use of (1).

(3) To simplify the notation assume that n = 1. Let ψ_{2}(y_{1}, …, y_{k}) be such as in (2). For the sake of contradiction suppose that for every N < ω we can find ⟨a_{1}, …, a_{k}⟩ ∈ G^{k} such that the set φ(G, a_{1}, …, a_{k}) is generic in G but not N-generic. Then the set of formulas

⋃_{N<ω}{ψ_{2}(y_{1}, …, y_{k}) ∧ ∀z_{1}, …, z_{N}∃t∀x(φ(x, y_{1}, …, y_{k}) → ⋀_{i=1}^{N} t ≠ z_{i} · x)}

is a consistent type in variables y_{1}, …, y_{k} and has a realization ⟨b_{1}, …, b_{k}⟩ ∈ H^{k} in some ℵ_{0}-saturated elementary extension H of G. We reach a contradiction as the set φ(H, b_{1}, …, b_{k}) is simultaneously generic and not generic in H. □

Corollary 2.5 Assume that (G, <, +, …) is an o-minimal expansion of an ordered group (G, <, +), n < ω and p(x_{1}, …, x_{n}) ∈ S_{n}(G). The following are equivalent:

(1) the type p(x_{1}, …, x_{n}) is weak generic in (G^{n}, +),

(2) ⟨g_{1}, …, g_{n}⟩ + p(x_{1}, …, x_{n}) = p(x_{1}, …, x_{n}) for every ⟨g_{1}, …, g_{n}⟩ ∈ G^{n}.

Proof. (1) ⇒ (2) For the sake of contradiction suppose that

⟨g_{1}, …, g_{n}⟩ + p(x_{1}, …, x_{n}) ≠ p(x_{1}, …, x_{n})

for some tuple ⟨g_{1}, …, g_{n}⟩ ∈ G^{n}. Then for some φ(x_{1}, …, x_{n}) ∈ p(x_{1}, …, x_{n}) we have (⟨g_{1}, …, g_{n}⟩ + φ(G^{n})) ∩ φ(G^{n}) = ∅. The set φ(G^{n}) is weak generic in (G^{n}, +) and hence contains arbitrarily large n-dimensional boxes (by Theorem 2.3).

Take any R ∈ G with R > max(|g_{1}|, …, |g_{n}|) and choose a_{1}, …, a_{n} ∈ G such that

B = [a_{1}, a_{1} + R] × … × [a_{n}, a_{n} + R] ⊆ φ(G^{n}).

We obtain

∅ ≠ (⟨g_{1}, …, g_{n}⟩ + B) ∩ B ⊆ (⟨g_{1}, …, g_{n}⟩ + φ(G^{n})) ∩ φ(G^{n}) = ∅,

a contradiction.

(2) ⇒ (1) This follows from Lemma 1.6. □

3 Stationarity

In this section we introduce and examine the notion of stationarity of a weak generic type in a group.

Recall that in a stable group all weak generic types are generic. Moreover, all of them are stationary over any model M. This means that every (weak) generic type p ∈ S(M) has a unique extension to a (weak) generic type q ∈ S(A) for each A ⊇ M. Stationarity of generic types plays an important role in the theory of stable groups.

Definition 3.1 We call a weak generic type p over a set A stationary if for every B ⊇ A the type p has just one extension to a complete weak generic type over B.

As in the previous section we assume (G, <, +, −, 0, …) to be an o-minimal expansion of an ordered group (G, <, +, −, 0). We are going to discuss stationarity of weak generic types in the groups (G, +) and (G, +) × (G, +).

Example 3.2 We shall prove that the types p_{1}(x) = {x < a : a ∈ G} and p_{2}(x) = {x > a : a ∈ G} are the only two weak generic types in (G, +) complete over G and that both of them are stationary.

By o-minimality of (G, <, +, …) every definable subset of G is a union of finitely many points and intervals. By Theorem 2.3 for every a, b ∈ G the interval (a, b) is not weak generic in (G, +). Thus no type in S_{1}(G) but p_{1} and p_{2} is weak generic in (G, +).

On the other hand, all intervals of the form (−∞, a) or (b, +∞) are weak generic in (G, +) since their complements in G are not generic in (G, +). This gives us weak genericity of the types p_{1} and p_{2}.

If H is any elementary extension of G, then there are also two complete (over H) weak generic types in (H, +). This means that p_{1} and p_{2} are stationary.

In general, weak generic types need not be stationary. Later in this section we shall give examples of groups where some weak generic types are not stationary (see Theorem 3.9 and Corollary 3.11).

Definition 3.3 We call an o-minimal structure (M, <, …) stationary if for every elementary extension N of M and N-definable function g : N → N there exists an M-definable function f : N → N such that g(x) ≤ f(x) for all sufficiently large x ∈ N.

Remark 3.4 Assume (M, <, …) is a stationary o-minimal structure and N ≻ M. For every N-definable map g : N → N with lim_{x→+∞} g(x) = +∞ we can find an M-definable map f : N → N such that lim_{x→+∞} f(x) = +∞ and f(x) ≤ g(x) for all sufficiently large x ∈ N.

Proof. First of all, assume that g is a bijection. Then g^{−1} (the compositional inverse of g) exists and by stationarity of (M, <, …) we can find an M-definable function f : N → N such that ultimately g^{−1} ≤ f. We have lim_{x→+∞} g^{−1}(x) = +∞, which implies that lim_{x→+∞} f(x) = +∞. By o-minimality of M we can choose a ∈ M such that f ↾ M is strictly increasing on (a, +∞)_{M}. Since M ≺ N, f is strictly increasing on (a, +∞)_{N}. We define a function f_{1} : N → N as follows:

f_{1}(x) = \{ \begin{matrix}f(x) & , when x > a \\ f(a) + x − a & , otherwise. \end{matrix}

Then f_{1} is an M-definable bijection so f_{1}^{−1} exists and is also M-definable. Moreover, lim_{x→+∞} f_{1}^{−1}(x) = +∞ and ultimately f_{1}^{−1} ≤ g so f_{1}^{−1} has the desired properties.

If g is not a bijection, then proceeding as above we can find an N-definable bijection g_{1} : N → N such that ultimately g_{1} = g. The rest of the proof remains the same. □

Now we turn our attention to weak generic sets and types in the group (G, +)×(G, +). By o-minimality of (G, <, +, …) every definable subset of the set G × G is a union of finitely many cells of dimension 0, 1 or 2. By Lemma 1.8 we are interested only in cells of dimension 2. They are of the form

C_{a,b}^{f,g} = {⟨x, y⟩ ∈ G × G : a < x ∧ x < b ∧ f(x) < y ∧ y < g(x)},

where {−∞} ∪ G ∋ a < b ∈ G ∪ {+∞} and f, g : (a, b) → G ∪ {−∞, +∞} are definable maps such that f(x) < g(x) for each x ∈ (a, b). If a, b ∈ G, then the cell C_{a,b}^{f,g} is not weak generic in (G, +) × (G, +) by Theorem 2.3. Since we shall consider only weak generic types p(x, y) in (G, +)×(G, +) such that {x > a : a ∈ G} ⊆ p(x, y), we shall be interested only in weak generic cells of the form C_{a,b}^{f,g}, where a ∈ G and b = +∞.

Definition 3.5 Assume that functions f, g : G → G are definable.

(1) We say that f ≪ g if f(x) < g(x) for all sufficiently large x ∈ G and the set

{⟨x, y⟩ ∈ G × G : x > 0 ∧ f(x) < y ∧ y < g(x)}

is weak generic in (G, +) × (G, +).

(2) We say that f ∼ g if the set

{⟨x, y⟩ ∈ G × G : x > 0 ∧ f(x) < y ∧ y < g(x)}

is not weak generic in (G, +) × (G, +).

Replacing 0 by any other element of the group G does not change the meaning of the definition above since for every a, b ∈ G the cell C_{a,b}^{f,g} is not weak generic in (G, +) × (G, +).

It is easy to see that ∼ is an equivalence relation on the set of all definable functions from G to G and that equivalence classes of ∼ are convex (i.e. if f, g, h : G → G are definable, f ∼ h and ultimately f(x) ≤ g(x) ≤ h(x), then f ∼ g and g ∼ h). Moreover, for all definable maps f, g : G → G either f ∼ g or f ≪ g or f ≫ g.

Definition 3.6 Let f : G → G be a definable function.

1) Let p_{f}^{+}(x, y) denote the only extension of the type

{x > a : a ∈ G} ∪ {y > f(x)} ∪ {y < g(x) : g ≫ f}

to a type which is complete over G and weak generic in (G, +) × (G, +).

2) Let p_{f}^{−}(x, y) denote the only extension of the type

{x > a : a ∈ G} ∪ {y < f(x)} ∪ {y > g(x) : g ≪ f}

to a type which is complete over G and weak generic in (G, +) × (G, +).

3) Let p_{+∞}(x, y) denote the only extension of the type

{x > a : a ∈ G} ∪ {y > f(x) : f : G → G definable}

to a complete type over G.

4) Let p_{−∞}(x, y) denote the only extension of the type

{x > a : a ∈ G} ∪ {y < f(x) : f : G → G definable}

to a complete type over G.

The next theorem shows that stationarity of the weak generic types defined above is equivalent to stationarity of the o-minimal group G. It also provides us with many examples of stationary weak generic types.

Theorem 3.7 Assume that (G, <, +, …) is an o-minimal expansion of an ordered group (G, <, +). The following are equivalent:

(1) the types p_{f}^{+}(x, y) and p_{f}^{−}(x, y) are stationary for each definable map f : G → G,

(2) the type p_{+∞}(x, y) (or p_{−∞}(x, y)) is stationary,

(3) the structure (G, <, +, …) is stationary.

Proof. (1) ⇒ (2) Let z : G → G denote the map constantly equal to 0. It follows from (1) that the type p_{z}^{+}(x, y) (and thus p_{z}^{+}(y, x)) is stationary. But p_{+∞}(x, y) = p_{z}^{+}(y, x) and therefore p_{+∞}(x, y) is stationary as well.

(2) ⇒ (3) For the sake of contradiction suppose that the structure (G, <, +, …) is not stationary. Then there exist an H ≻ G and an H-definable function g : H → H such that no G-definable map f : H → H dominates g.

Consider the following partial types over H:

p_{1}(x, y) = p_{+∞}(x, y) ∪ {y < g(x)}

and

p_{2}(x, y) = p_{+∞}(x, y) ∪ {y > g(x)}.

In order to reach a contradiction, it is sufficient to prove that both of the types above are weak generic in (H, +) × (H, +).

Let us begin with p_{1}. We have to show that each formula of the form

(⋀_{i=1}^{m} x > a_{i}) ∧ (⋀_{j=1}^{n} y > f_{j}(x)) ∧ y < g(x)

is weak generic in (H, +)×(H, +), where a_{1}, …, a_{m} ∈ G and f_{1}, …, f_{n} are functions from H to H definable over G. Taking a = max(a_{1}, …, a_{n}) and f = max(f_{1}, …, f_{n}), we can confine our attention to the sets of the form

X = {⟨x, y⟩ ∈ H × H : x > a ∧ y > f(x) ∧ y < g(x)},

where a ∈ G and f : H → H is definable over G. Without loss of generality we can assume that f is ultimately non-decreasing.

Consider the map h : H → H defined as follows: h(a) = f(2a) + a for each a ∈ H. Since h is G-definable, g dominates h. Therefore for every sufficiently large M ∈ H the region between the graphs of f and g in H × H contains the square whose vertices are

⟨M, f(2M)⟩, ⟨M, f(2M) + M⟩, ⟨2M, f(2M)⟩ and ⟨2M, f(2M) + M⟩.

By Theorem 2.3 the set X is weak generic in (H, +) × (H, +). As a result, the type p_{1} is weak generic in (H, +) × (H, +).

It is not difficult to prove that so is p_{2}, which contradicts stationarity of the type p_{+∞}(x, y).

(3) ⇒ (1) Assume stationarity of the structure (G, <, +, …) and consider any definable function f : G → G. We shall show that both p_{f}^{+} and p_{f}^{−} are stationary weak generic types.

By o-minimality of G the map f is either ultimately non-negative or ultimately non-positive. It is easy to see that p_{f}^{+} is stationary if and only if p_{−f}^{−} is stationary and p_{f}^{−} is stationary if and only if p_{−f}^{+} is stationary. Therefore without loss of generality we can assume that f is ultimately non-negative. Moreover, f is either ultimately non-increasing or ultimately non-decreasing. If f is ultimately non-increasing (and non-negative), then p_{f}^{+} = p_{z}^{+} and p_{f}^{−} = p_{z}^{−}, where z : G → G is constantly equal to 0. Since z is ultimately non-decreasing, we can confine our attention to the case where f is ultimately non-decreasing (and non-negative).

Consider the following definable sets:

A = {a ∈ G : (∃b > a)(∀c ∈ (a, b))f(c) − f(a) ≤ c − a}

and

B = {a ∈ G : (∃b > a)(∀c ∈ (a, b))f(c) − f(a) > c − a}.

Note that by o-minimality of G we have G = A ∪ B and for some M ∈ G either (M, +∞) ⊆ A or (M, +∞) ⊆ B. Enlarge M in order to ensure that f is continuous on (M, +∞).

Case 1. (M, +∞) ⊆ A. Then f grows “slowly” on (M, +∞):

(∗) (∀a > M)(∃b > 0)(∀c ∈ (0, b))f(a + c) ≤ f(a) + c.

By (∗) and continuity of f we have

(∗∗) (∀a > M)(∀c > 0)f(a + c) ≤ f(a) + c.

Because if not, then the opposite holds: (∃a > M)(∃c > 0)f(a + c) > f(a) + c. Fix a and let C_{a} = {c > 0 : f(a+c) > f(a)+c}. Then C_{a} ≠ ∅ so we can define c_{0} = inf(C_{a}). Assertion (∗) implies that c_{0} > 0. We have (∀c ∈ (0, c_{0}))f(a + c) ≤ f(a) + c. Since f is continuous at a + c_{0}, f(a + c_{0}) ≤ f(a) + c_{0} and c_{0} ∉ C_{a}. By o-minimality of G we can choose d > c_{0} with (c_{0}, d) ⊆ C_{a}. So (∀c ∈ (c_{0}, d))f(a + c) > f(a) + c and continuity of f at a+c_{0} implies that f(a+c_{0}) ≥ f(a)+c_{0}. Hence f(a+c_{0}) = f(a)+c_{0} and for every e ∈ (0, d − c_{0}) we have

f(a + c_{0} + e) > f(a) + c_{0} + e = f(a + c_{0}) + e,

which implies that a + c_{0} ∉ A. But a + c_{0} ∈ (M, +∞) ⊆ A, a contradiction. Thus (∗∗) holds.

Now for the sake of contradiction assume that p_{f}^{+} is not stationary. Then for some H ≻ G and H-definable g : H → H we have f ≪ g and g ≪ h for each Gdefinable h : H → H with f ≪ h. Since lim_{x→+∞}(g(x) − f(x)) = +∞, there exists an increasing to +∞ G-definable function h : H → H such that ultimately h ≤ g −f (Remark 3.4). Enlarging M we can assume that h is increasing on (M, +∞).

Fix any positive R ∈ H and choose a ∈ H with a > M and h(a) ≥ 2R. By (∗∗) we have f(a + R) ≤ f(a) + R. So the region between the graphs of f and f + h contains the square whose vertices are

⟨a, f(a) + R⟩, ⟨a, f(a) + 2R⟩, ⟨a + R, f(a) + R⟩ and ⟨a + R, f(a) + 2R⟩.

As R was arbitrary, we can use Theorem 2.3 to conclude that the region between the graphs of f and f + h is weak generic in (H, +) × (H, +). Since f ≪ f + h and f + h is G-definable, we have g ≪ f + h, which contradicts the fact that ultimately g ≥ f + h. Hence the type p_{f}^{+} is stationary.

The proof that the type p_{f}^{−} is stationary is analogous and we omit it.

Case 2. (M, +∞) ⊆ B. Then f grows “quickly” on (M, +∞), which implies that lim_{x→+∞} f(x) = +∞. Proceeding as in the proof of Remark 3.4, we are able to find a definable bijection f_{1} : G → G such that f_{1}(a) = f(a) for each a ∈ (M, +∞). If g = f_{1}^{−1}, then g grows “slowly” on (f_{1}(M), +∞) and from the previous case we know that the types p_{g}^{+} and p_{g}^{−} are stationary. The proof is complete since p_{f}^{+}(x, y) = p_{f_{1}}^{+}(x, y) = p_{g}^{−}(y, x) and p_{f}^{−}(x, y) = p_{f_{1}}^{−}(x, y) = p_{g}^{+}(y, x). □

Example 3.8 If (G, <, +) is an o-minimal ordered group, then every definable function f : G → G is ultimately equal to f_{q}(x) + a for some a ∈ G and q ∈ ℚ, where f_{q}(x) = q · x for each x ∈ G (see [1], Corollary 1.7.6). Below we list all weak generic types in (G, +) × (G, +) that are complete over G and contain the formula (x > 0).

(1) p_{−∞}(x, y) and p_{+∞}(x, y).

(2) p_{f_{q}}^{−}(x, y) and p_{f_{q}}^{+}(x, y), q ∈ ℚ.

(3) {x > a : a ∈ G} ∪ {y > q · x : q ∈ ℚ ∧ q < r} ∪ {y < q · x : q ∈ ℚ ∧ q > r}, r ∈ ℝ \ ℚ.

The structure (G, <, +) is stationary since its elementary extensions are all linearly bounded. By Theorem 3.7 weak generic types of the form (1) and (2) are stationary. It is easy to see that so are those of the form (3).

Recently Ramakrishnan has proved that all o-minimal structures are stationary (the reader is referred to [9] for more details). By Theorem 3.7 the weak generic types from Definition 3.6 are always stationary.

In the remainder of this section we assume (R, <, +, ·, 0, 1, …) to be an o-minimal expansion of an ordered ring (R, <, +, ·, 0, 1). As noted in [7] (Theorem 2.3), such a ring must be a real closed field. We shall make use of a result of Miller from [2] which we briefly describe below.

A power function is a definable endomorphism of the group (R_{+}, ·) (by R_{+} we denote the set {a ∈ R : a > 0}). Every power function is differentiable on R_{+}. For each r ∈ R there is at most one power function f with f′(1) = r. We denote such a map by x^{r} and write a^{r} for f(a). The field

K = {f′(1) : f is a power function} ⊆ R

is called the field of exponents of R. We say that the structure R is power bounded if for every definable f : R → R there exists an r ∈ K such that ultimately |f(x)| ≤ x^{r}. An exponential function is an isomorphism of the ordered groups (R, <, +, 0) and (R_{+}, <, ·, 1).

The main result of [2] says that either R defines (without parameters) an exponential function or R is power bounded and for each ultimately non-zero definable function f : R → R there exist an a ∈ R \ {0} and a 0-definable power function x^{r} such that lim_{x→+∞} \frac{f(x)}{a·x^{r}} = 1.

Theorem 3.9 If R = (R, <, +, ·, …) is an o-minimal expansion of a real closed field, then the following are equivalent:

(1) all complete (over R) weak generic types in (R_{+}, ·) × (R_{+}, ·) are stationary,

(2) the structure R is power bounded.

Proof. (1) ⇒ (2) For the sake of contradiction assume that R is not power bounded. As we mentioned above, this implies that some exponential function exp : R → R_{+} is 0-definable in R. Thus the map

(exp, exp) : (R, +) × (R, +) → (R_{+}, ·) × (R_{+}, ·)

is a 0-definable isomorphism of groups. Hence the groups (S, +)×(S, +) and (S_{+}, ·)× (S_{+}, ·) are definably isomorphic for every S ≻ R and it suffices to show that some weak generic type in (R, +) × (R, +) is not stationary. To do this, consider arbitrary S ≻ R, a ∈ S \ R and let f : S → S be such that f(x) = a · x for every x ∈ S. We shall prove that the weak generic types p_{f}^{−} and p_{f}^{+} are extensions of the same complete weak generic type over R.

Since the structure R does not need to be ℵ_{0}-saturated, Lemma 1.4 itself is not sufficient to ensure that the restrictions of the types p_{f}^{−} and p_{f}^{+} to the complete types over R are weak generic in (R, +) × (R, +). Nevertheless, this follows from the characterization of definable weak generic sets provided by Theorem 2.3.

It is enough to show that f ≁ g for each g : S → S definable over R. Suppose otherwise. Then for some R-definable g : S → S we have S ⊧ g ∼ f. Indeed, there is a first order formula φ ∈ L(S), which expresses the fact that g ∼ f. Namely, φ says that the region defined by the formula

x > 0 ∧ ((f(x) < y ∧ y < g(x)) ∨ (f(x) > y ∧ y > g(x)))

does not contain arbitrarily large squares (we apply Theorem 2.3 again). Since S ⊧ g(x) ∼ a · x and R ≺ S, we have

S ⊧ ∃c(g(x) ∼ c · x) and R ⊧ ∃c(g(x) ∼ c · x).

Choose b ∈ R such that R ⊧ g(x) ∼ b · x. Then S ⊧ g(x) ∼ b · x. Hence a · x ∼ b · x, a contradiction (since a ≠ b implies that arbitrarily large squares may be put into the region between the graphs of the linear maps x ↦ a · x and x ↦ b · x).

(2) ⇒ (1) Note that it is enough to examine those weak generic types in (R_{+}, ·)× (R_{+}, ·) which contain the formula (x ≥ 1 ∧ y ≥ 1). To prove this, consider F, G : R_{+} × R_{+} → R_{+} × R_{+} defined as follows: F (x, y) = ⟨x, \frac{1}{y}⟩ and G(x, y) = ⟨\frac{1}{x}, y⟩ for every x, y ∈ R_{+}. We see that F, G and F ∘ G are 0-definable automorphisms of the group (R_{+}, ·) × (R_{+}, ·) that map the set {⟨x, y⟩ : x ≥ 1 ∧ y ≥ 1} respectively onto the sets

(a) {⟨x, y⟩ : x ≥ 1 ∧ 0 < y ≤ 1},

(b) {⟨x, y⟩ : 0 < x ≤ 1 ∧ y ≥ 1} and

(c) {⟨x, y⟩ : 0 < x ≤ 1 ∧ 0 < y ≤ 1}.

The same holds for an arbitrary elementary extension S of R, which enables us to “translate” an example of a non-stationary weak generic type to the set of types containing the formula (x ≥ 1 ∧ y ≥ 1).

In order to show that every complete weak generic type in (R_{+}, ·) × (R_{+}, ·) containing the formula (x ≥ 1 ∧ y ≥ 1) is stationary, we shall prove that for every S ≻ R and every S-definable function f : S → S ∩ [1, +∞) we are able to find an R-definable map g : S → S such that the set

{⟨x, y⟩ ∈ S × S : x ≥ 1 ∧ y ≥ 1 ∧ (f(x) ≤ y ≤ g(x) ∨ f(x) ≥ y ≥ g(x))}

is not weak generic in (S_{+}, ·) × (S_{+}, ·). So take such S and f. Let a, r ∈ S be such that lim_{x→+∞} \frac{f(x)}{a·x^{r}} = 1. Then a > 0 and r ≥ 0. The power function x^{r} : S → S is R-definable (as it is definable over ∅) and we put g = x^{r}.

Choose any c ∈ S_{+} such that \frac{1}{c} · x^{r} ≤ f(x) ≤ c · x^{r} for all sufficiently large x ∈ S. Without loss of generality we can assume that it is so on the whole interval [1, +∞), because for every M ≥ 1 the set X_{M} = [1, M] × [1, +∞) is not weak generic in (S_{+}, ·) × (S_{+}, ·) (otherwise, by Corollary 2.2 the set X_{M} · X_{M}^{−1} = [\frac{1}{M} , M] × S_{+} would be generic in (S_{+}, ·) × (S_{+}, ·), which is not the case).

Now it suffices to prove that the set

X = \{⟨x, y⟩ ∈ S × S : x ≥ 1 ∧ y ≥ 1 ∧ \frac{1}{c} · x^{r} ≤ y ∧ y ≤ c · x^{r}\}

is not weak generic in (S_{+}, ·) × (S_{+}, ·). Suppose otherwise. Then the set X · X^{−1} is generic in (S_{+}, ·) × (S_{+}, ·) by Corollary 2.2. We claim that

X · X^{−1} ⊆ Y = \{⟨x, y⟩ ∈ S × S : x > 0 ∧ \frac{1}{c^{2}} · x^{r} ≤ y ∧ y ≤ c^{2} · x^{r}\}.

To show this, take arbitrary ⟨x_{1}, y_{1}⟩, ⟨x_{2}, y_{2}⟩ ∈ X. We have \frac{1}{c} · x_{1}^{r} ≤ y_{1} ≤ c · x_{1}^{r} and \frac{1}{c} · x_{2}^{r} ≤ y_{2} ≤ c · x_{2}^{r}. Hence

\frac{1}{c^{2}} · (\frac{x_{1}}{x_{2}} )^{r} ≤ \frac{y_{1}}{y_{2}} ≤ c^{2} · (\frac{x_{1}}{x_{2}} )^{r}

and ⟨x_{1}, y_{1}⟩ · ⟨x_{2}, y_{2}⟩^{−1} = ⟨u, v⟩, where u = \frac{x_{1}}{x_{2}} and \frac{1}{c^{2}} · u^{r} ≤ v ≤ c^{2} · u^{r}. Thus ⟨u, v⟩ ∈ Y and X · X^{−1} ⊆ Y.

Finally, since c^{2} · x^{r} ≤ c^{2} for each x ∈ (0, 1), we have

Y ⊆ Z = (S_{+} × S_{+}) \ ((0, 1) × (c^{2}, +∞)).

But this implies that the set Z is generic in (S_{+}, ·) × (S_{+}, ·), a contradiction. □

Definition 3.10 We call a structure (R, <, +, ·, …) polynomially bounded if for every definable function f : R → R there is n ∈ ℕ_{+} such that |f(x)| ≤ x^{n} for all sufficiently large x ∈ R.

Corollary 3.11 If R = (R, <, +, ·, …) is an o-minimal expansion of an archimedean real closed field, then the following are equivalent:

(1) all complete (over R) weak generic types in (R_{+}, ·) × (R_{+}, ·) are stationary,

(2) the structure R is polynomially bounded.

Proof. Recall [2] that R is polynomially bounded if and only if R is power bounded and its field of exponents K is archimedean. But K is archimedean as a subfield of the archimedean field R. Thus the equivalence stated in the corollary follows from Theorem 3.9. □

The pure field of real numbers (ℝ, <, +, ·) is archimedean and polynomially bounded. By the corollary above all weak generic types in (ℝ_{+}, ·)×(ℝ_{+}, ·) derived in the theory T h(ℝ, <, +, ·) are stationary.

On the other hand, the field of reals with exponentation (ℝ, <, +, ·, e^{x}) is an example of an o-minimal structure where some weak generic types in the group (ℝ_{+}, ·) × (ℝ_{+}, ·) are not stationary (o-minimality of the structure (ℝ, <, +, ·, e^{x}) was proved in [10]).

4 Coverings of groups

In this section we assume G to be an ℵ_{0}-saturated group and H to be a |G|^{+}-saturated elementary extension of G. We begin with new proofs of results from [3] and [4]. They show that weak generic types may be a useful tool in model theory of groups.

For a type or formula s(x), [s(x)] denotes the set of types containing s(x). If V is a type-definable set defined by a type s(x), then we identify [V] with the set [s(x)].

Theorem 4.1 ([3], Theorem 2.1) Assume G is an ℵ_{0}-saturated group covered by countably many 0-type-definable sets X_{n}, n < ω. Then G = {g_{1}, …, g_{m}} · X_{n} · X_{n}^{−1} for some m, n < ω and g_{1}, …, g_{m} ∈ G.

Proof. Since

W Gen(G) = ⋃_{n<ω}(W Gen(G) ∩ [X_{n}])

and each of the sets W Gen(G) ∩ [X_{n}] is closed in W Gen(G), by the Baire category theorem we can find n < ω and φ(x) ∈ L(G) such that

(∗) ∅ ≠ W Gen(G) ∩ [φ(x)] ⊆ [X_{n}].

Since W Gen(G)∩[φ(x)] ≠ ∅, the formula φ(x) is weak generic and there exist a nongeneric formula ψ(x) ∈ L(G) and g_{1}, …, g_{m} ∈ G with G = {g_{1}, …, g_{m}} · (φ ∨ ψ)(G).

Formulas {¬g · ψ(x) : g ∈ G} form a partial weak generic type over G (see the proof of Lemma 1.5). We can extend it to some p(x) ∈ W Gen(G). Let j ∈ {1, …, m} be such that g_{j} · (φ ∨ ψ)(x) ∈ p. Then g_{j} · φ(x) ∈ p since g_{j} · ψ(x) ∉ p. As a result, φ(x) ∈ g_{j}^{−1}·p ∈ W Gen(G) and (∗) implies that q ∈ [X_{n}] for q = g_{j}^{−1}·p. Fix a ∈ q(H).

Choose any g ∈ G. For some i ∈ {1, …, m} the formula g_{i} · (φ ∨ ψ)(x) belongs to the type g · q. If g_{i} · ψ(x) ∈ g · q, then

ψ(x) ∈ g_{i}^{−1} · g · q = g_{i}^{−1} · g · g_{j}^{−1} · p and g_{j} · g^{−1} · g_{i} · ψ(x) ∈ p,

which contradicts the choice of p. So we have g_{i} · φ(x) ∈ g · q. Therefore φ(x) ∈ g_{i}^{−1}·g·q ∈ W Gen(G), which implies that g_{i}^{−1}·g·q ∈ [X_{n}] and g_{i}^{−1}·g·a ∈ X_{n}(H). Now we write g as g_{i}(g_{i}^{−1} · g · a)a^{−1} and conclude that g ∈ {g_{1}, …, g_{m}} · X_{n}(H) · X_{n}(H)^{−1}.

So far we proved that G ⊆ {g_{1}, …, g_{m}} · X_{n}(H) · X_{n}(H)^{−1} for some m, n < ω and g_{1}, …, g_{m} ∈ G. But this implies that

G ⊆ {g_{1}, …, g_{m}} · X_{n}(G) · X_{n}(G)^{−1} = {g_{1}, …, g_{m}} · X_{n} · X_{n}^{−1}.

Namely, consider an arbitrary g ∈ G. Let i ∈ {1, …, m} and h_{1}, h_{2} ∈ X_{n}(H) be such that g = g_{i} · h_{1} · h_{2}^{−1}. Then

r(x, y) = X_{n}(x) ∪ X_{n}(y) ∪ {g = g_{i} · x · y^{−1}}

is a partial type over {g, g_{i}}. By ℵ_{0}-saturation of G we are able to find some ⟨h′_{1}, h′_{2}⟩ ∈ r(G × G). Finally, g = g_{i} · h′_{1} · h_{2}^{′−1} ∈ {g_{1}, …, g_{m}} · X_{n} · X_{n}^{−1}. □

Lemma 4.2 Assume G is an ℵ_{0}-saturated group covered by countably many 0-type-definable sets X_{n}, n < ω. Then

G = ⋃_{i=1}^{m} g_{i} · X_{n} · p_{i}(G) · g_{i}^{−1}

for some m, n < ω, g_{1}, …, g_{m} ∈ G and p_{1}, …, p_{m} ∈ S(∅).

Proof. We proceed as in the proof of Theorem 4.1. Again, for every g ∈ G we can find i ∈ {1, …, m} such that g_{i}^{−1} · g · a ∈ X_{n}(H). As g = g_{i}(g_{i}^{−1} · g · a)(a^{−1} · g_{i})g_{i}^{−1}, we obtain the inclusion G ⊆ ⋃_{i=1}^{m} g_{i} · X_{n}(H) · p_{i}(H) · g_{i}^{−1} where p_{i} = tp(a^{−1} · g_{i}/∅) for each i ∈ {1, …, m}. Finally, we get

G ⊆ ⋃_{i=1}^{m} g_{i} · X_{n}(G) · p_{i}(G) · g_{i}^{−1} = ⋃_{i=1}^{m} g_{i} · X_{n} · p_{i}(G) · g_{i}^{−1},

which completes the proof. □

Theorem 4.3 ([4], Theorem 2.4) Assume G is an ℵ_{0}-saturated group covered by countably many 0-type-definable sets X_{n}, n < ω. Then

G = ⋃_{i=1}^{m} g_{i} · X_{≤n} · X_{≤n}^{−1} · g_{i}^{−1} = ⋃_{i=1}^{m}(X_{≤n} · X_{≤n}^{−1})^{g_{i}}

for some m, n < ω and g_{1}, …, g_{m} ∈ G.

Proof. Take m, n < ω, g_{1}, …, g_{m} ∈ G and p_{1}, …, p_{m} ∈ S(∅) as in the lemma above. For each i ∈ {1, …, m} find n_{i} < ω such that p_{i}^{−1} ∈ [X_{n_{i}}]. Finally, replace n with max(n, n_{1}, …, n_{m}). □

For the convenience of the reader we recall two definitions from [3].

Definition 4.4 Assume G is a group, A ⊆ G and k < ω. We say that A generates G in k steps if every g ∈ G is of the form g = a_{1}·. . .·a_{k} for some a_{1}, …, a_{k} ∈ A∪A^{−1}.

Definition 4.5 Assume G is an ℵ_{0}-saturated group. Let k_{G} be the minimal number k such that whenever G is covered by countably many 0-type-definable sets X_{n}, n < ω, then finitely many of them generate G in k steps.

It has been shown in [3] that for each ℵ_{0}-saturated group G we have k_{G} ≤ 3 and there are some groups G with k_{G} = 3. Moreover, it has been proved that k_{G} ≤ 2 for every group G which is either stable or commutative. In [4] we improved this result by showing that k_{G} ≤ 2 for each definably amenable group G.

Now we are going to introduce the notion of a generically symmetric group. It is similar to the notion of a definably amenable group in the following sense: generical symmetry of a group G implies that k_{G} ≤ 2, and is implied both by stability and by commutativity of G.

Definition 4.6 A group G is generically symmetric if for every definable X ⊆ G the set X is left generic if and only if the set X is right generic.

Remark 4.7 If G is generically symmetric, then the following are equivalent for a definable set X ⊆ G:

(1) X is left generic,

(2) X is right generic,

(3) G = A · X · B for some finite sets A, B ⊆ G.

Proof. (1) ⇒ (2) Straightforward.

(2) ⇒ (3) We have G = X · B for some finite set B ⊆ G and it suffices to put A = {e}.

(3) ⇒ (1) Since G = A·X ·B, the set A·X is right generic. By generical symmetry of G it is also left generic and we have G = C · A · X for some finite C ⊆ G. Finally, the finite set C · A witnesses that X is left generic. □

Theorem 4.8 If G is an ℵ_{0}-saturated generically symmetric group, then k_{G} ≤ 2.

Proof. As in the proof of Theorem 4.1 we find n < ω and a weak generic formula φ(x) ∈ L(G) with

(∗) ∅ ≠ W Gen(G) ∩ [φ(x)] ⊆ [X_{n}].

Next we choose a non-generic formula ψ(x) ∈ L(G) such that the formula φ(x)∨ψ(x) is (left) generic. By generical symmetry of G it is also right generic and we have

G = {g_{1}, …, g_{m}} · (φ ∨ ψ)(G) = (φ ∨ ψ)(G) · {h_{1}, …, h_{k}}

for some g_{1}, …, g_{m}, h_{1}, …, h_{k} ∈ G.

Formulas {¬g · ψ(x) · h : g, h ∈ G} form a partial weak generic type over G (to show this we use generical symmetry of G once again). We can extend it to some p(x) ∈ W Gen(G). Let j ∈ {1, …, m} be such that g_{j} · (φ ∨ ψ)(x) ∈ p. Then g_{j} · φ(x) ∈ p since ¬g_{j} · ψ(x) ∈ p. As a result, φ(x) ∈ g_{j}^{−1} · p ∈ W Gen(G) and (∗) implies that q ∈ [X_{n}] for q = g_{j}^{−1} · p. Fix a ∈ q(H).

Choose any g ∈ G. For some i ∈ {1, …, k} the formula (φ ∨ ψ) · h_{i} belongs to the type g · q. If ψ(x) · h_{i} ∈ g · q, then

ψ(x) ∈ g · q · h_{i}^{−1} = g · g_{j}^{−1} · p · h_{i}^{−1} and g_{j} · g^{−1} · ψ(x) · h_{i} ∈ p,

which contradicts the choice of p. So we have φ(x) · h_{i} ∈ g · q. Therefore φ(x) ∈ g · q · h_{i}^{−1} ∈ W Gen(G), which implies that g · q · h_{i}^{−1} ∈ [X_{n}] and g · a · h_{i}^{−1} ∈ X_{n}(H). Now we write g as (g ·a·h_{i}^{−1})(h_{i} ·a^{−1}) and conclude that g ∈ X_{≤N}(H)·X_{≤N}(H)^{−1} for N < ω such that n ≤ N and tp(a · h_{l}^{−1}/∅) ∈ [X_{≤N}] for each l ∈ {1, …, k}. Finally, G ⊆ X_{≤N}(H) · X_{≤N}(H)^{−1} implies that G = X_{≤N} · X_{≤N}^{−1} and we are done. □

Lemma 1.6.6.10 from [6] states that every stable group is generically symmetric. Therefore by the theorem above for each ℵ_{0}-saturated stable group we have k_{G} ≤ 2. Another proof of this result may be found in [3] (Theorem 2.3). Theorem 4.8 can be also used to show that for each ℵ_{0}-saturated commutative group G we have k_{G} ≤ 2 ([3], Theorem 3.1). Finally, using Theorem 4.8 we can prove that if an ℵ_{0}-saturated group G has some complete generic types, then k_{G} ≤ 2. It immediately follows from the lemma below.

Lemma 4.9 If Gen(G) ≠ ∅, then G is generically symmetric.

Proof. Suppose that φ(x) is a right generic formula in G. Then by Lemma 1.3 the formula φ(x) is left weak generic. Moreover, by Lemma 1.5(1) from [4] we have

Gen(G) ≠ ∅ ⇒ W Gen(G) = Gen(G).

Thus φ(x) is left generic and we are done. □

We shall examine the stable case in more detail. Theorem 2.4 from [3] says that in the case where the group G is stable with bounded finite weight we get “k_{G} = 1.5” (which means that whenever G is covered by countably many 0-type-definable sets, a union of finitely many of them is generic in G). The following example shows that the assumption on weight is essential.

Example 4.10 We give an example of a stable group H with “k_{H} > 1.5”. Namely, let G = (ℤ^{ω}, +, {P_{n} : n < ω}), where P_{n}(G) = {f ∈ ℤ^{ω} : f(n) = 0}. Put

P_{∞} = G \ ⋃_{n<ω} P_{n}(G) = ⋂_{n<ω}(G \ P_{n}(G))

and note that the set P_{∞} is 0-type-definable. Let H be an ℵ_{0}-saturated elementary extension of G. The group H is stable since it is an example of an abelian structure (see Section 3.A in [8] for more details on abelian structures).

We shall prove that for every N < ω the set P_{∞}(H) ∪ ⋃_{n<N} P_{n}(H) is not generic in H. Note that for each K < ω we have

(∀f_{0}, …, f_{K} ∈ G)(∃h ∈ G) ⋀_{k≤K}(P_{N+k}(f_{k} + h) ∧ ⋀_{n<N} ¬P_{n}(f_{k} + h)).

To show this, choose arbitrary f_{0}, …, f_{K} ∈ G. Find an element h ∈ G such that h(n) > max(|f_{0}(n)|, …, |f_{K}(n)|) for n < N and h(N + k) = −f_{k}(N + k) for k ≤ K. Then h has the required properties.

Since G ≺ H, for every K < ω we have

(∀f_{0}, …, f_{K} ∈ H)(∃h ∈ H) ⋀_{k≤K}(P_{N+k}(f_{k} + h) ∧ ⋀_{n<N} ¬P_{n}(f_{k} + h)),

which implies that the set P_{∞}(H) ∪ ⋃_{n<N} P_{n}(H) is not generic in H. Thus there exists a countable family of 0-type-definable sets covering H such that unions of its finite subfamilies are all non-generic in H.

References

[1] Lou van den Dries, Tame topology and o-minimal structures, Cambridge University Press, Cambridge 1998.

[2] Chris Miller, A growth dichotomy for o-minimal expansions of ordered fields, Logic: from foundations to applications, 385-399, Oxford Science Publications, The Clarendon Press, Oxford University Press, New York 1996.

[3] Ludomir Newelski, Marcin Petrykowski, Coverings of groups and types, Journal of the London Mathematical Society 71 (2005), 1-21.

[4] Ludomir Newelski, Marcin Petrykowski, Weak generic types and coverings of groups I, Fundamenta Mathematicae 191 (2006), 201-225.

[5] Anand Pillay, On groups and fields definable in o-minimal structures, Journal of Pure and Applied Algebra 53 (1988), 239-255.

[6] Anand Pillay, Geometric stability theory, Oxford Science Publications, The Clarendon Press, Oxford University Press, New York 1996.

[7] Anand Pillay, Charles Steinhorn, Definable sets in ordered structures. I, Transactions of the American Mathematical Society 295 (1986), 565-592.

[8] Mike Prest, Model theory and modules, Cambridge University Press, Cambridge 1988.

[9] Janak Ramakrishnan, All o-minimal structures are stationary, preprint 2007.

[10] Alex Wilkie, Model completeness results for expansions of the ordered field of real numbers by restricted Pfaffian functions and the exponential function, Journal of the American Mathematical Society 9 (1996), 1051-1094.

Institute of Mathematics University of Wrocław Pl. Grunwaldzki 2/4 50-384 Wrocław, Poland E-mail: petryk@math.uni.wroc.pl