On the strong cell decomposition property for weakly o-minimal structures

Roman Wencel^{1}

Instytut Matematyczny Uniwersytetu Wrocławskiego

ABSTRACT

We consider a class of weakly o-minimal structures admitting an o-minimal style cell decomposition, for which one can construct certain canonical o-minimal extension. The paper contains several fundamental facts concerning the structures in question. Among other things, it is proved that the strong cell decomposition property is preserved under elementary equivalences. We also investigate fiberwise properties (of definable sets and definable functions), definable equivalence relations and conditions implying elimination of imaginaries.

0 Introduction

Weak o-minimality for totally ordered structures was introduced by M.A. Dickmann in [Di]. It generalizes the notion of o-minimality and belongs to the family of so called minimality conditions in model theory, widely studied during the recent years. The difference between o-minimality and weak o-minimality is that in the definition of the former one uses convex sets instead of intervals. To be precise, a first order structure equipped with a linear ordering is weakly o-minimal if every set definable in dimension 1 is a finite union of convex sets.

Weakly o-minimal structures in general appear to be much more difficult to handle than the o-minimal ones. The main problem is that they lack so called finiteness properties, and therefore one cannot expect a reasonable cell decomposition for sets definable in them. As weak o-minimality is not preserved under elementary equivalences, one defines a notion of a weakly o-minimal theory, that is a first-order theory whose all models are weakly o-minimal structures. Although in a model of such a theory one can prove a weak form of cell decomposition, the topological dimension for definable sets does not behave as well as it does in the o-minimal setting. For example, it does not satisfy the addition property. One can, for instance, define a set of dimension one whose projection onto some coordinate has infinitely many infinite fibers.

A class of weakly o-minimal structures in which one can smoothly develop an o-minimal style description of definable sets was considered in [MMS]. The authors prove that sets definable in weakly o-minimal expansions of ordered fields without non-trivial definable valuations are finite unions of so called strong cells, which are constructed more or less as cells in the o-minimal setting. It turns out that this result can be generalized to certain weakly o-minimal expansions of ordered groups. It was proved in [We07] that every weakly o-minimal expansion of an ordered group without a non-trivial definable subgroup has the strong cell decomposition property. One of the basic consequences of strong cell decomposition for a given weakly o-minimal structure M is existence of an o-minimal extension of M, closely related to it.

In this paper we explore further consequences of the strong cell decomposition property for weakly o-minimal structures. We generalize several facts (mainly concerning definable sets) known in the o-minimal setting. We also investigate the relation between weakly o-minimal structures with the strong cell decomposition property and their canonical o-minimal extensions.

1Research supported by the Polish Government grant N N201 545938.

The paper is organized as follows. In §1 we mainly fix notation and recall some necessary definitions and facts. In §2 we prove monotonicity theorem and finiteness lemma. We also observe that a model elementarily equivalent to a weakly o-minimal structure with the strong cell decomposition property is weakly o-minimal itself and has the strong cell decomposition property. Another result of §2 is that some relativization of the construction of the canonical o-minimal extension \overline{M} of a weakly o-minimal structure with the strong cell decomposition property M determines a covariant functor between the category of elementary embeddings of M to the category of elementary embeddings of \overline{M}. §3 is devoted to investigation of fiberwise properties of definable sets and functions. In §4 we examine equivalence relations definable in weakly o-minimal structures with the strong cell decomposition property generalizing earlier results of A. Pillay. The final section of the paper is devoted to elimination of imaginaries in weakly o-minimal structures with the strong cell decomposition property.

1 Preliminaries

Let (M, ≤) be a dense linear ordering without endpoints. A set I ⊆ M is called convex in (M, ≤) if for any a, b ∈ I and c ∈ M with a ≤ c ≤ b, we have that c ∈ I. If additionally I ≠ ∅ and I has both infimum and supremum in M ∪ {−∞, +∞}, then I is said to be an interval in (M, ≤). A maximal convex subset of a non-empty set contained in M is called its convex component. An ordered pair ⟨C, D⟩ of non-empty subsets of M is called a cut in (M, ≤) if C < D, C ∪ D = M and D has no lowest element. If I_{1}, …, I_{m} ⊆ M are open intervals with all endpoints in M, then the set I_{1} × … × I_{m} ⊆ M^{m} is called an open box in M^{m}.

A first order structure M = (M, ≤, …) expanding (M, ≤) is said to be weakly o-minimal if every subset of M, definable in M, is a finite union of convex sets. A complete first order theory T whose language contains a binary relational symbol ≤ is called weakly o-minimal if ≤ is interpreted in all models of T as a linear ordering, and all models of T are weakly o-minimal with respect to this ordering.

Assume that M = (M, ≤, …) is a weakly o-minimal structure. A cut ⟨C, D⟩ in (M, ≤) is called definable in M [over A ⊆ M] if the sets C, D are definable in M [over A]. The set of all such cuts will be usually denoted by \overline{M} (note that \overline{M} depends on M, so when necessary, we add the superscript M to \overline{M}). The universe M can be regarded as a subset of \overline{M} by identifying an element a ∈ M with the cut ⟨(−∞, a], (a, +∞)⟩. After such an identification, \overline{M} is naturally equipped with a dense linear ordering without endpoints extending that of (M, ≤), and (M, ≤) is dense in (\overline{M}, ≤). Clearly, if M is o-minimal, then \overline{M} = M.

The linear orderings (M, ≤) and (\overline{M}, ≤) determine Hausdorff topologies on M and \overline{M} respectively in a natural way as well as the product topologies on cartesian powers of these. For m ∈ ℕ_{+} and a set X ⊆ M^{m}, we will denote by cl(X) and int(X) the closure and the interior of X in M^{m}. Note that if X is definable in M over some set A ⊆ M, then also cl(X) and int(X) are definable over A. We will also write CL(X) for the closure of a set X ⊆ \overline{M}^{m} (or of X ⊆ M^{m}) in \overline{M}^{m}. In case of o-minimal M we have cl(X) = CL(X).

For a set X ⊆ M^{m} definable in M [over A ⊆ M], a function f : X ⟶ \overline{M} ∪ \{−∞, +∞\} is said to be definable in M [over A] if the set \{⟨\overline{x}, y⟩ ∈ X × M : f(\overline{x}) > y\} is definable in M [over A]. So in particular the functions identically equal to −∞ and +∞ with domain X are definable over A. If I ⊆ M is a convex open definable set with a = inf(I) ∈ \overline{M} ∪ \{−∞\}, b = sup(I) ∈ \overline{M} ∪ \{+∞\} and f : I ⟶ \overline{M} is a definable function, then (by weak o-minimality of M), the limits lim_{x⟶a^{+}} f(x)

and lim_{x⟶b^{−}} f(x) are both well defined elements of \overline{M} ∪ \{−∞, +∞\}.

A dimension of an infinite definable set X ⊆ M^{m} (notation: dim(X)) is the largest r ∈ ℕ_{+} for which there exists a projection π : M^{m} ⟶ M^{r} such that the set π[X] has non-empty interior. Non-empty finite subsets of M^{m} are said to have dimension 0. We also put dim(∅) = −∞. If X, Y ⊆ M^{m} are definable sets, then X is said to be large in Y if dim(Y \ X) < dim(Y).

If M = (M, ≤, +, …) is a weakly o-minimal expansion of an ordered group, then a cut ⟨C, D⟩ in (M, ≤) is called non-valuational if inf{y − x : x ∈ C, y ∈ D} = 0. The structure M is nonvaluational if all cuts in (M, ≤) definable in M are non-valuational. It is not difficult to show that a weakly o-minimal structure M = (M, ≤, +, …) is non-valuational iff the only subgroups of (M, +) definable in M are {0} and M (see [We07, Lemma 1.5]).

Assume that M = (M, ≤, …) is a weakly o-minimal structure. For every m ∈ ℕ_{+}, we inductively define strong cells in M^{m} and their completions in \overline{M}^{m}. The completion of a strong cell C ⊆ M^{m} in \overline{M}^{m} is denoted by \overline{C}. Note that \overline{C} depends on M, therefore we add a superscript M to \overline{C} when necessary.

(1) A singleton in M is a strong ⟨0⟩-cell in M, equal to its completion.

(2) A non-empty convex open definable subset of M is a strong ⟨1⟩-cell in M. If C ⊆ M is a strong ⟨1⟩-cell in M, then \overline{C} := \{x ∈ \overline{M} : (∃a, b ∈ C)(a < x < b)\}.

Assume that m ∈ ℕ_{+}, i_{1}, …, i_{m} ∈ {0, 1} and suppose that we have already defined strong ⟨i_{1}, …, i_{m}⟩-cells in M^{m} together with their completions in \overline{M}^{m}.

(3) If C ⊆ M^{m} is a strong ⟨i_{1}, …, i_{m}⟩-cell in M^{m} and f : C ⟶ M is a continuous definable function which has a (necessarily unique) continuous extension \overline{f} : \overline{C} ⟶ \overline{M}, then Γ(f) is a strong ⟨i_{1}, …, i_{m}, 0⟩-cell in M^{m+1}. The completion of Γ(f) in \overline{M}^{m+1} is defined as Γ(\overline{f}).

(4) If C ⊆ M^{m} is a strong ⟨i_{1}, …, i_{m}⟩-cell in M^{m} and f, g : C ⟶ \overline{M} ∪\{−∞, +∞\} are continuous definable functions such that

(a) each of the functions f, g assumes all its values in one of the sets M, \overline{M} \ M, \{−∞\}, \{∞\},

(b) f, g have (necessarily unique) continuous extensions \overline{f}, \overline{g} : \overline{C} ⟶ \overline{M} ∪ \{−∞, +∞\},

(c) \overline{f}(\overline{x}) < \overline{g}(\overline{x}) whenever \overline{x} ∈ \overline{C},

then the set

(f, g)_{C} := \{⟨\overline{a}, b⟩ ∈ C × M : f(\overline{a}) < b < g(\overline{a})\}

is called a strong ⟨i_{1}, …, i_{m}, 1⟩-cell in M^{m}. The completion of (f, g)_{C} in \overline{M}^{m+1} is defined as

\overline{(f, g)_{C}} := (\overline{f}, \overline{g})\overline{C} := \{⟨\overline{a}, b⟩ ∈ \overline{C} × \overline{M} : \overline{f}(\overline{a}) < b < \overline{g}(\overline{a})\}.

(5) We say that C ⊆ M^{m} is a strong cell in M^{m} if there are i_{1}, …, i_{m} ∈ {0, 1} such that C is a strong ⟨i_{1}, …, i_{m}⟩-cell in M^{m}.

An example of a strong cell in M^{m} is an open box contained in M^{m}. If C ⊆ M^{m} is a strong cell and f : C ⟶ \overline{M} is a function for which there exists a continuous extension \overline{f} : \overline{C} ⟶ \overline{M}, then f is called strongly continuous. This means that all functions appearing in the construction of a strong cell are strongly continuous.

Note also that if C ⊆ M^{m} is a strong cell, f : C ⟶ \overline{M} is definable in a weakly o-minimal structure M = (M, ≤, …) and \overline{a} ∈ \overline{C}, then it makes sense to talk about a limit of f in \overline{M} ∪ \{−∞, +∞\} at \overline{a}. So f is strongly continuous iff f has a limit in \overline{M} at each \overline{a} ∈ \overline{C} and for \overline{a} ∈ C this limit is equal to f(\overline{a}).

Any finite partition of M into singletons and convex open sets definable in M will be called a strong cell decomposition of M. A finite partition C of M^{m+1} into strong cells is said to be a strong cell decomposition of M^{m+1} if π[C] := {π[C] : C ∈ C} is a strong cell decomposition of M^{m} (here π : M^{m+1} ⟶ M^{m} denotes the projection dropping the last coordinate). We say that a strong cell decomposition C of M^{m} partitions X ⊆ M^{m} if for every C ∈ C, either C ⊆ X or C ∩ X = ∅. A strong cell decomposition of M^{m} is called definable over A ⊆ M if all its members are definable over A. Note that whenever A ⊆ M and C is an A-definable strong cell decomposition of M^{m+n} partitioning X ⊆ M^{m+n} and π : M^{m+n} ⟶ M^{m} is the projection onto the first m coordinates, then π[C] := {π[C] : C ∈ C} is an A-definable strong cell decomposition of M^{m} partitioning π[X]. Moreover, for every \overline{a} ∈ M^{m}, the family C\overline{a} := \{C\overline{a} : C ∈ C\} is an A\overline{a}-definable strong cell decomposition of M^{n} partitioning X\overline{a}. Another easy observation is that if C, D are A-definable strong cell decompositions of M^{m} and M^{n} respectively, then {C × D : C ∈ C, D ∈ D} is an A-definable strong cell decomposition of M^{m+n}. In particular, a cartesian product of strong cells is a strong cell. Whenever C ⊆ M^{m} and D ⊆ M^{n} are strong cells, then the completion of C × D is equal to \overline{C} × \overline{D}. So in particular, \overline{M^{m}} = \overline{M}^{m} for m ∈ ℕ_{+}.

A weakly o-minimal structure M = (M, ≤, …) is said to have the strong cell decomposition property if for any m ∈ ℕ_{+}, A ⊆ M and A-definable sets X_{1}, …, X_{k} ⊆ M^{m}, there exists an A-definable strong cell decomposition of M^{m} partitioning each of the sets X_{1}, …, X_{k}. As proved in [We07], a weakly o-minimal expansion of an ordered group has the strong cell decomposition property iff it is non-valuational. By [KPS] (see also [vdD2, Chapter 3]), every o-minimal structure expanding a dense linear ordering without endpoints has the strong cell decomposition property. Weakly o-minimal structures with the strong cell decomposition property have the cell decomposition property in the sense of [Ma].

Remark that the above definition of strong cells slightly differs from that introduced in [We07]. More precisely, in [We07] we allow that the functions used to construct strong cells assume values both in M and in \overline{M} \M. Strong cells defined here are exactly the refined strong cells in the sense of [We07]. Nevertheless, it is not difficult to demonstrate that the notions of strong cell decomposition property defined with both types of strong cells coincide. More precisely, one can easily show that if M = (M, ≤, …) is a weakly o-minimal structure with the strong cell decomposition property in the sense of [We07] and A ⊆ M, then for every A-definable strong cell decomposition C of M^{m} (in the sense of [We07]), there exists an A-definable strong cell decomposition of M^{m} (in the above sense) partitioning each member of C.

Unlike in the o-minimal setting, strong cells in weakly o-minimal structures in general are not definably connected. One can even construct a weakly o-minimal structure whose universe is totally definably disconnected.

Let R_{alg} = (ℝ_{alg}, ≤, +, ·) be the ordered field of all real algebraic numbers. For every real transcendental α, let P_{α} = {x ∈ ℝ_{alg} : x < α}. Then by [BP] (or [Bz]), the structure (R_{alg}, (P_{α})_{α∈ℝ\ℝ_{alg}}) has weakly o-minimal theory and (by [MMS] or [We07]) the strong cell decomposition property. All definably connected components of ℝ_{alg} are singletons.

Assume that m ∈ ℕ_{+} and C, D are strong cell decompositions of M^{m}. We say that D refines C (notation: C ≺ D or D ≻ C) if every cell from D is a subset of some cell from C (equivalently: if every cell from C is a union of some cells from D). Note that the relation ≺ partially orders the family of all strong cell decompositions of M^{m}, whose smallest element is {M^{m}}. It is a routine to prove by induction on m the following fact.

Fact 1.1 Assume that A ⊆ M and k, m ∈ ℕ_{+}.

(a) If X_{1}, …, X_{k} ⊆ M^{m} are A-definable sets, then there exists a smallest strong cell decomposition of M^{m} partitioning each of X_{1}, …, X_{k}. Such D is definable over A.

(b) If C_{1}, …, C_{k} are strong cell decompositions of M^{m}, then there exists a smallest strong cell decomposition D of M^{m} refining each of C_{1}, …, C_{k}. Such D is definable over A.

(c) If X_{1}, …, X_{k} ⊆ M^{m} are A-definable sets and f_{1} : X_{1} ⟶ \overline{M}, …, f_{k} : X_{k} ⟶ \overline{M} are A-definable functions, then there exists a smallest strong cell decomposition D of M^{m} partitioning each of X_{1}, …, X_{k} and such that for i ∈ {1, …, k} and any C ∈ D with C ⊆ X_{i}, f_{i} ↾ C is strongly continuous. Such D is definable over A.

Following [We07], for any m ∈ ℕ_{+} and i_{1}, …, i_{m} ∈ {0, 1}, we inductively define so called basic ⟨i_{0}, …, i_{m}⟩-cells in \overline{M}^{m} and elementary functions on them (with values in \overline{M}). If 1 ≤ j_{1} < … < j_{k} ≤ m, then ϱ_{j_{1},...,j_{k}}^{m} : M^{m} ⟶ M^{k} and \overline{ϱ}_{j_{1},...,j_{k}}^{m} : \overline{M}^{m} ⟶ \overline{M}^{k} are projections onto the coordinates j_{1}, …, j_{k}.

(1) A one-element subset of \overline{M}^{m} is called a basic ⟨0, …, 0⟩-cell in \overline{M}^{m}, where ⟨0, …, 0⟩ is a tuple of m zeros.

(2) If C ⊆ M is a strong ⟨1⟩-cell, then \overline{C} is called a basic ⟨1⟩-cell in \overline{M}. Note that \overline{ϱ}_{1}^{1}[\overline{C}] ∩ M = \overline{C} ∩ M = C is an open strong cell in M.

(3) If C = \{\overline{a}\} ⊆ \overline{M}^{m} and I is a basic ⟨1⟩-cell in \overline{M}, then C × I is a basic ⟨0, …, 0, 1⟩-cell in \overline{M}^{m+1}. Clearly, ϱ_{m+1}^{m+1}[C × I] ∩ M = I ∩ M is an open strong cell in M.

Assume now that i_{1}, …, i_{m} ∈ {0, 1}, i_{1} +…+i_{m} > 0 and suppose that we have already defined basic ⟨i_{1}, …, i_{m}⟩-cells in \overline{M}^{m}. Let \{j_{1}, …, j_{k}\} = \{j ∈ \{1, …, m\} : i_{j} = 1\}, j_{1} < … < j_{k} and suppose we know that if C ⊆ \overline{M}^{m} is a basic ⟨i_{1}, …, i_{m}⟩-cell, then ϱ_{j_{1},...,j_{k}}^{m}[C] ∩ M^{k} is an open strong cell in M^{k}.

(4) Let C ⊆ \overline{M}^{m} be a basic ⟨i_{1}, …, i_{m}⟩-cell and consider D := \overline{ϱ}_{j_{1},...,j_{k}}^{m}[C] ∩ M^{k}, an open strong cell in M^{k}. If f is a strongly continuous definable function from D to M or a strongly continuous definable function from D to \overline{M} \M, then Γ(\overline{f} ∘(\overline{ϱ}_{j_{1},...,j_{k}}^{m} ↾ C)) is a basic ⟨i_{1}, …, i_{m}, 0⟩-cell

in \overline{M}^{m+1}. Note that \overline{ϱ}_{j_{1},...,j_{k}}^{m+1}[Γ(\overline{f} ∘ (\overline{ϱ}_{j_{1},...,j_{k}}^{m} ↾ C))] ∩ M^{k} = D is an open strong cell in M^{k}.

(5) Let C ⊆ \overline{M}^{m} be a basic ⟨i_{1}, …, i_{m}⟩-cell and consider D := \overline{ϱ}_{j_{1},...,j_{k}}^{m}[C] ∩ M^{k}, an open strong cell in M^{k}. If f, g : D ⟶ \overline{M} ∪ \{−∞, +∞\} are strongly continuous definable functions such that

• all values of f, g lie in one of the sets: \{−∞\}, M, \overline{M} \ M, \{+∞\},

• \overline{f}(\overline{x}) < \overline{g}(\overline{x}) for \overline{x} ∈ \overline{D},

then the set

(\overline{f} ∘ \overline{ϱ}_{j_{1},...,j_{k}}^{m}, \overline{g} ∘ \overline{ϱ}_{j_{1},...,j_{k}}^{m})_{C} := \{⟨\overline{a}, b⟩ ∈ C × \overline{M} : (\overline{f} ∘ \overline{ϱ}_{j_{1},...,j_{k}}^{m})(\overline{a}) < b < (\overline{g} ∘ \overline{ϱ}_{j_{1},...,j_{k}}^{m})(\overline{a})\}

is called a basic ⟨i_{1}, …, i_{m}, 1⟩-cell in \overline{M}^{m+1}. Note that \overline{ϱ}_{j_{1},...,j_{k},m+1}^{m+1}[(\overline{f}∘\overline{ϱ}_{j_{1},...,j_{k}}^{m}, \overline{g}∘\overline{ϱ}_{j_{1},...,j_{k}}^{m})_{C}]∩ M^{k} = (f, g)_{D} is an open strong cell in M^{k+1}.

In a standard way we introduce the notion of cell decomposition of \overline{M}^{m} into basic cells in \overline{M}^{m} [partitioning a given set].

Assume now that M = (M, ≤, …) is a weakly o-minimal L-structure with the strong cell decomposition property. For any m ∈ ℕ_{+} and any strong cell C ⊆ M^{m}, denote by R_{C} the m-ary relation in M^{m} determined by C, i.e. if \overline{a} ∈ M^{m}, then R_{C}(\overline{a}) holds iff \overline{a} ∈ C. The structure

M′ := (M, ≤, (R_{C} : C is a strong cell))

has exactly the same definable sets as M. Moreover, T h(M′) admits elimination of quantifiers.

Proposition 1.2 If m ∈ ℕ_{+}, then every basic cell contained in \overline{M}^{m} is a finite Boolean combination of completions of strong cells in M^{m}.

Proof. If a ∈ \overline{M}, then \{a\} = \overline{M} \ (\overline{\{x ∈ M : x < a\}} ∪ \overline{\{x ∈ M : x > a\}}).

Assume now that m ∈ ℕ_{+} and C ⊆ \overline{M}^{m+1} is a basic ⟨i_{1}, …, i_{m}⟩-cell. Suppose also that every basic cell contained in \overline{M}^{m} is a Boolean combination of completions of strong cells in M^{m}. We consider three cases.

Case 1. i_{1} = … = i_{m+1} = 1. Then C is a completion of an open strong cell.

Case 2. i_{1} = … = i_{m} = 1 and i_{m+1} = 0. Then there are an open strong cell D ⊆ M^{m} and a strongly continuous function f : D ⟶ \overline{M} (assuming all its values in one of the sets M, \overline{M} \ M) with a continuous extension \overline{f} : \overline{D} ⟶ \overline{M} such that C = Γ(\overline{f}). Note that then (−∞, f)_{D} and (f, +∞)_{D} are strong cells in M^{m+1} and C = \overline{M^{m+1}} \ [\overline{(−∞, f)_{D}} ∪ \overline{(f, +∞)_{D}}].

Case 3. There exists j ∈ \{1, …, m\} with i_{j} = 0. Let π, ϱ : \overline{M}^{m+1} ⟶ \overline{M}^{m} be projections such that π drops the last coordinate and ϱ drops the j-th coordinate. Denote also by ϱ_{0} the projection from M^{m+1} onto M^{m} dropping the j-th coordinate. By our inductive assumption, ϱ[C] is a Boolean combination of completions of strong cells D_{1}, …, D_{k} ⊆ M^{m}. Then ϱ^{−1}[ϱ[C]] is a Boolean combination of \overline{ϱ_{0}^{−1}[D_{1}]}, …, \overline{ϱ_{0}^{−1}[D_{k}]}. Similarly, π[C] is a Boolean combination of completions of strong cells E_{1}, …, E_{l} ⊆ M^{m}. Hence π[C] × M is a Boolean combination of \overline{E_{1} × M}, …, \overline{E_{l} × M}. Note that C = ϱ^{−1}[ϱ[C]] ∩ (π[C] × M). This finishes the proof.

Denote for m ∈ ℕ_{+} and a strong cell C ⊆ M^{m} by \overline{R}_{C} the m-ary relation determined by the completion of C, i.e. if \overline{a} ∈ \overline{M}^{m}, then \overline{R}_{C}(\overline{a}) holds iff \overline{a} ∈ \overline{C}. Consider the structure

\overline{M} := (\overline{M}, ≤, (\overline{R}_{C} : C is a strong cell)).

Proposition 1.2 implies that every basic cell in \overline{M}^{m} is definable in \overline{M} without quantifiers. By §3 of [We07], \overline{M} is o-minimal and every set X ⊆ \overline{M}^{m} definable in \overline{M} is a finite union of basic cells. So T h(\overline{M}) admits elimination of quantifiers. Moreover, if C ⊆ \overline{M}^{m} is a basic cell definable in \overline{M}, then C ∩ M^{m} is either a strong cell definable in M or an empty set. Consequently, if X ⊆ \overline{M}^{m} is a set definable in \overline{M}, then X ∩ M^{m} is definable in M. If additionally Y ⊆ M^{m} is definable in M, then X ∩ Y is definable in M. The structure \overline{M} is called the canonical o-minimal extension of M.

We end this section with a couple of observations concerning strong cells definable in M and basic cells definable in \overline{M}.

Proposition 1.3 Assume that M = (M, ≤, …) is a weakly o-minimal structure with the strong cell decomposition property and \overline{M} = (\overline{M}, ≤, …) is its canonical o-minimal extension. Let also m, k ∈ ℕ_{+} and n ∈ ℕ.

(a) If X_{1}, …, X_{k} ⊆ \overline{M}^{m} are sets definable in \overline{M}, then there is a cell decomposition C of \overline{M}^{m} partitioning each of the sets X_{1}, …, X_{k} and such that every member of C is a basic cell.

(b) If C ⊆ M^{m} is an n-dimensional strong cell definable in M and X ⊆ \overline{M}^{m} is a set definable in \overline{M}, with dim(X ∩ \overline{C}) = n, then X ∩ C is definable in M and dim(X ∩ C) = n.

(c) If X ⊆ M^{m} is a set definable in M and Y ⊆ \overline{M}^{m} is a set definable in \overline{M} such that dim(Y ∩ CL(X)) = n, then the set Y ∩ X is definable in M and dim(Y ∩ X) = n.

Proof. (a) We use induction on m. The case m = 1 is trivial by o-minimality of \overline{M}. So fix m ∈ ℕ_{+} and suppose that the assertion of (a) holds for dimension m. Let X_{1}, …, X_{k} ⊆ \overline{M}^{m+1} be sets definable in \overline{M}. Each of the sets X_{1}, …, X_{k}, \overline{M}^{m+1} \ (X_{1} ∪ … ∪ X_{k}) is a union of finitely many basic cells. Let C_{1}, …, C_{l} be all basic cells that appear in these unions. For \overline{a} ∈ \overline{M}^{m}, denote by C(\overline{a}) the cell decomposition of \overline{M} partitioning (C_{1})\overline{a}, …, (C_{l})\overline{a} and such that |C(\overline{a})| is as small as possible. Clearly, C(\overline{a}) partitions (X_{1})\overline{a}, …, (X_{k})\overline{a} and |C(\overline{a})| = 2r(\overline{a}) + 1 for some r(\overline{a}) ∈ \{0, …, 2l\}. Let also C(\overline{a}) = \{I_{1}(\overline{a}), …, I_{2r(\overline{a})+1}(\overline{a})\}, where I_{1}(\overline{a}) < … < I_{2r(\overline{a})+1}(\overline{a}). For every \overline{a} ∈ \overline{M}^{m} we define a function

f\overline{a} : \{1, …, 2r(\overline{a}) + 1\} ⟶ P (\{1, …, k\}) × P (\{1, …, l\})

as follows:

f\overline{a}(j) = ⟨\{α ∈ \{1, …, k\} : \overline{M}^{m} × I_{j}(\overline{a}) ⊆ X_{α}\}, \{β ∈ \{1, …, l\} : \overline{M}^{m} × I_{j}(\overline{a}) ⊆ C_{β}\}⟩.

Denote by f_{1}, …, f_{s} all functions that one can obtain in this way and let Z_{i} = \{\overline{a} ∈ \overline{M}^{m} : f\overline{a} = f_{i}\} for i = 1, …, s. By the inductive assumption, there is a cell decomposition D of \overline{M}^{m} into basic cells which partitions each of the sets Z_{1}, …, Z_{s}. Then

E := \{ ⋃_{\overline{a}∈D}(\{\overline{a}\} × I_{j}(\overline{a})) : D ∈ D, j ∈ \{1, …, 2r(\overline{a}) + 1\}\}

is a cell decomposition of \overline{M}^{m+1} partitioning X_{1}, …, X_{k}. All members of E are basic cells.

(b) The n-dimensional set X ∩\overline{C} contains a basic cell D of dimension n. But then D ∩C ⊆ M^{m} is an n-dimensional strong cell definable in M. Hence dim(X ∩ C) = n.

(c) Suppose that X and Y satisfy our assumptions. The set X can be presented as a disjoint union of strong cells C_{1}, …, C_{k} ⊆ M^{m}. Note that

CL(X) = CL(C_{1}) ∪ … ∪ CL(C_{k}) = CL(\overline{C_{1}}) ∪ … ∪ CL(\overline{C_{k}}).

Thus dim(Y ∩CL(\overline{C_{i}})) = n for some i ∈ \{1, …, k\}. But dim(CL(\overline{C}_{i})\\overline{C_{i}}) < n, so dim(Y ∩\overline{C_{i}}) = n. By (b), the set Y ∩ C_{i} is definable in M and dim(Y ∩ C_{i}) = n. Hence dim(Y ∩ X) = n.

2 Fundamental results

From now on, throughout the paper we assume that M = (M, ≤, …) is a weakly o-minimal Lstructure with the strong cell decomposition property. Unless otherwise stated, by “definable” (set, function, relation) we mean “definable with parameters in the language of M”.

As proved in [Ar], in the context of arbitrary weakly o-minimal structures the domain of a unary A-definable function f assuming values in \overline{M} may be partitioned into some finite set and finitely many A-definable convex open sets I_{1}, …, I_{n} so that on each I_{i}, f is either locally strictly increasing, locally strictly decreasing or locally constant. It turns out that for weakly ominimal structures with the strong cell decomposition property, we can prove an o-minimal style monotonicity theorem. In fact this is a special case of so called regular cell decomposition theorem (see Proposition 2.5).

Proposition 2.1 Assume that A ⊆ M, U ⊆ M is an infinite A-definable set and f : U ⟶ \overline{M} is an A-definable function. Then U is a disjoint union of a finite set X and A-definable convex open sets I_{1}, …, I_{n} such that for every i ∈ {1, …, n}, (a) f ↾ I_{i} is either constant or strictly monotone and strongly continuous,

(b) f ↾ I_{i} assumes all its values in one of the sets M, \overline{M} \ M.

Proof. Let f : U ⟶ \overline{M} be an A-definable function, where U ⊆ M is an A-definable infinite set. There is an A-definable strong cell decomposition C of M^{2} partitioning the set {⟨a, b⟩ ∈ U × M : f(a) > b}. Clearly, for every C ∈ C, f ↾ π[C] is strongly continuous and assumes all its values in one of the sets M, \overline{M} \ M (here π : M^{2} ⟶ M is the projection onto the first coordinate).

Suppose now that C ∈ C and I = π[C] ⊆ U is a convex open set. Then the unique continuous extension \overline{f} : \overline{I} ⟶ \overline{M} of f is definable in \overline{M}. As \overline{M} is o-minimal, the open interval \overline{I} ⊆ \overline{M} may be partitioned into a disjoint union of a finite set X\overline{I} and open intervals \overline{J_{1}}, …, \overline{J_{l}} such that for each i, J_{i} ⊆ M is convex open and definable in M, and \overline{f} ↾ \overline{J_{i}} is either constant or strictly monotone and continuous. Then f ↾ J_{i} is either constant or strictly monotone and strongly continuous whenever i ∈ \{1, …, l\}. Apart of this, all values of each f ↾ J_{i} belong to one of the sets M, \overline{M} \ M. In this way we obtain a partition of U satisfying all our demands except A-definability of sets of which such a partition consists.

Define the following sets:

X_{1} = {a ∈ U : (∃b, c ∈ M)(a ∈ (b, c) ⊆ U ∧ f ↾ (b, c) is strictly increasing)},
X_{2} = {a ∈ U : (∃b, c ∈ M)(a ∈ (b, c) ⊆ U ∧ f ↾ (b, c) is strictly decreasing)},
X_{3} = {a ∈ U : (∃b, c ∈ M)(a ∈ (b, c) ⊆ U ∧ f ↾ (b, c) is constant)}.

Clearly, X_{1}, X_{2} and X_{3} are open in M, pairwise disjoint and definable over A. By the previous paragraph, π[C] \ (X_{1} ∪ X_{2} ∪ X_{3}) is finite for every C ∈ C. So let D be an A-definable strong cell decomposition of M^{2} refining C and partitioning each of the sets X_{i} × M (i ∈ {1, 2, 3}). Let I_{1}, …, I_{n} be all convex open sets contained in U which are of the form π[D] for D ∈ D. Then the sets I_{1}, …, I_{n} and X := U \ (I_{1} ∪ … ∪ I_{n}) satisfy all our demands.

Proposition 2.1 easily implies that the definable (equivalently: algebraic) closure has the exchange property in M. In other words, (M, dcl) is a pregeometry. So given a set A ⊆ M and a tuple \overline{a}, it makes sense to define rk(\overline{a}/A) as the maximal length of a tuple \overline{b} ⊆ \overline{a} such that \overline{b} is algebraically independent over A.

It is easy to observe that for any i_{1}, …, i_{m} ∈ {0, 1}, the dimension of every strong ⟨i_{0}, …, i_{m}⟩- cell is equal to i_{1} + … + i_{m}. Thus for r ∈ ℕ_{+}, a non-empty definable set X ⊆ M^{m} has dimension at least r iff X contains some ⟨i_{1}, …, i_{m}⟩-strong cell with i_{1} + … + i_{m} ≥ r. Moreover, if X ⊆ M^{m} is a non-empty definable set and C is a strong cell decomposition of M^{m} partitioning X, then dim(X) = max{dim(C) : C ∈ C, C ⊆ X}.

Proposition 2.1 together with Theorem 4.2 from [We06] imply that the topological dimension dim has the addition property. Therefore, by results of [MMS], dim is a dimension function in the sense of [vdD1]. Note also that addition property of dim and hence (by [We06, Theorem 4.2]) the strong monotonicity property are elementary properties of weakly o-minimal structures.

Directly from the strong cell decomposition property we can also obtain the following proposition.

Proposition 2.2 Assume that A ⊆ M and m ∈ ℕ_{+}.

(a) If X ⊆ M^{m} is a non-empty A-definable set and f : X ⟶ \overline{M} is an A-definable function, then there is a decomposition D of M^{m} into finitely many A-definable strong cells such that for every D ∈ D, D ⊆ X, the restriction f ↾ D is strongly continuous and f ↾ D assumes all its values in one of the sets M, \overline{M} \ M.

(b) If X ⊆ M^{m+1} is a definable set, then there exists a positive integer k such that for every \overline{a} ∈ M^{m}, the fibre X\overline{a} = \{b ∈ M : ⟨\overline{a}, b⟩ ∈ X\} has at most k convex components.

Proof. (a) Assume that X ⊆ M^{m} is a non-empty A-definable set and f : X ⟶ \overline{M} an A-definable function. Let π : M^{m+1} ⟶ M^{m} be the projection dropping the last coordinate. By assumption, there is a decomposition C of M^{m+1} into finitely many strong cells partitioning the A-definable set \{⟨\overline{x}, y⟩ ∈ M^{m+1} : y < f(\overline{x})\}. Then D := \{π[C] : C ∈ C\} is an A-definable strong cell decomposition of M^{m} satisfying our demands.

(b) If X is a union of k strong cells, then for every \overline{a} ∈ M^{m}, the fiber X\overline{a} has at most k convex components.

Corollary 2.3 The theory of M is weakly o-minimal.

Proof. Let N = (N, ≤, …) ≡ M and fix an L-formula φ(x, \overline{y}). By Proposition 2.2, there is a positive integer k such that φ(M, \overline{a}) has at most k convex components whenever \overline{a} ranges over M^{|\overline{y}|}. The same is true in N, so N is weakly o-minimal.

Strong cell decomposition has several improvements (as does cell decomposition in the ominimal setting). Below we state two exemplary results. The proofs are omitted because they are almost exactly the same as for o-minimal structures (see [vdD2], p. 58, exercises 2 and 4).

Proposition 2.4 Assume that m, k ∈ ℕ_{+}.

(a) If X_{1}, …, X_{k} ⊆ M^{m} are definable sets, then there is a strong cell decomposition C of M^{m} partitioning each of the sets X_{1}, …, X_{k}, all of whose members are ∅-definable in the structure (M, ≤, X_{1}, …, X_{k}).

(b) If X ⊆ M^{m} is a definable set and f : X ⟶ \overline{M} is a definable function, then there is a strong cell decomposition C of \overline{M}^{m} partitioning X such that the restriction f ↾ C to each cell C ∈ C with C ⊆ X is strongly continuous, and each cell from C is ∅-definable in the structure (M, ≤, \{⟨\overline{a}, b⟩ ∈ X × M : f(\overline{a}) > b\}).

As in [vdD2] (see p. 58), we can introduce the notions of regularity for open strong cells and definable functions on them. The following fact is proved as in the o-minimal case.

Proposition 2.5 Assume that A ⊆ M and m, k ∈ ℕ_{+}.

(a) If X_{1}, …, X_{k} ⊆ M^{m} are A-definable sets, then there is an A-definable strong cell decomposition of M^{m} partitioning each of the sets X_{1}, …, X_{k}, all of whose open cells are regular.

(b) If X ⊆ M^{m} is an A-definable set and f : X ⟶ \overline{M} is an A-definable function, then there is an A-definable strong cell decomposition C of M^{m} partitioning X, all of whose open cells are regular, and such that for each open cell C ∈ C, the restriction f ↾ C is regular.

Each strong cell decomposition C of M^{m}, where m ∈ ℕ_{+}, has a natural lexicographic ordering <_{C}. More precisely, if C is a strong cell decomposition of M, then for C, D ∈ C we put: C <_{C} D iff (∀x ∈ C)(∀y ∈ D)(x < y). Suppose that we have already defined the ordering <_{C} for any strong cell decomposition C of M^{m}. Let D be a strong cell decomposition of M^{m+1} and denote by π the projection from M^{m+1} onto the first m coordinates. For C, D ∈ D we put C <_{D} D if π[C] <_{π[D]}< π[D], or π[C] = π[D] and for all (equivalently: some) \overline{a} ∈ π[C] = π[D] we have that C\overline{a} <_{D\overline{a}} D\overline{a}.

With a strong cell C ⊆ M^{m} we inductively associate its type, that is some sequence saying how C is constructed. Given a strong cell C ⊆ M, we put γ(C) = 0 if C ia a singleton and γ(C) = 3α(C) + β(C) + 1 otherwise, where α(C), β(C) are defined as follows:

α(C) = \{ \begin{matrix}0 & if & inf C = −∞ \\ 1 & if & inf C ∈ M \\ 2 & if & inf C ∈ \overline{M} \ M \end{matrix} β(C) = \{ \begin{matrix}0 & if & sup C = +∞ \\ 1 & if & sup C ∈ M \\ 2 & if & sup C ∈ \overline{M} \ M. \end{matrix}

The one-element sequence t(C) := ⟨γ(C)⟩ is called the type of C. Let D be a strong cell in M^{m+1} and denote by π the projection from M^{m+1} onto M^{m} dropping the last coordinate. Fix also \overline{a} ∈ π[D]. The type of D is defined as t(D) := ⟨i_{1}, …, i_{m}, γ(D\overline{a})⟩, where ⟨i_{1}, …, i_{m}⟩ = t(π[D]). This definition does not depend on \overline{a}.

We also introduce types of strong cell decompositions, namely some sequences carrying the information how the cells partitioning M^{m} are constructed and in what way they are arranged. Let C = {C_{1}, …, C_{k}} be a strong cell decomposition of M with C_{1} <_{C} … <_{C} C_{k}. The type of C (notation: τ(C)) is defined as the sequence ⟨t(C_{1}), …, t(C_{k})⟩.

Now assume that m ∈ ℕ_{+}, D is a strong cell decomposition of M^{m+1} and π is the projection of M^{m+1} onto the first m coordinates. Assume also that π[D] = {C_{1}, …, C_{n}}, where C_{1} <_{π[D]} … <_{π[C]} C_{n}, and fix tuples \overline{a}_{1} ∈ C_{1}, …, \overline{a}_{n} ∈ C_{n}. We define:

τ(D) = ⟨τ(π[D]), ⟨τ(D_{\overline{a}_{1}}), …, τ(D_{\overline{a}_{n}})⟩⟩.

Proposition 2.6 Assume that m, n ∈ ℕ_{+}, A ⊆ M and S ⊆ M^{m+n} is an A-definable set.

(a) There is k ∈ ℕ_{+} such that the fiber S\overline{a} can be presented as a union of at most k strong cells as \overline{a} ranges over M^{m}. In particular each S\overline{a} has at most k isolated points.

(b) There are types τ_{1}, …, τ_{l} of strong cell decompositions of M^{n} such that for every \overline{a} ∈ M^{m}, there is an A\overline{a}-definable strong cell decomposition of M^{n} partitioning S\overline{a} of type τ_{i} for some i ∈ {1, …, l}.

Proof. Let C be an A-definable strong cell decomposition of M^{m+n} partitioning S and let k = |C|. Denote by π the projection onto the first m coordinates. Then for every \overline{a} ∈ M^{m}, C\overline{a} is an A\overline{a}- definable strong cell decomposition of M^{n} partitioning S\overline{a}. So S\overline{a} can be presented as a union of at most |C\overline{a}| ≤ k strong cells. The number of different types that appear in \{τ(C\overline{a}) : \overline{a} ∈ M^{m}\} does not exceed |π[C]|. This finishes the proof.

Lemma 2.7 Assume that N = (N, ≤, …) ≡ M and m ∈ ℕ_{+}.

(a)_{m} If i_{1}, …, i_{m} ∈ \{0, 1\} and φ(\overline{x}) is an L-formula defining in M a strong ⟨i_{1}, …, i_{m}⟩-cell of type τ, then φ(N^{m}) is also a strong ⟨i_{1}, …, i_{m}⟩-cell in N^{m} of type τ.

(b)_{m} If i_{1}, …, i_{m} ∈ {0, 1}, C ⊆ M^{m} is a ∅-definable strong ⟨i_{1}, …, i_{m}⟩-cell in M^{m} of type τ, f : C ⟶ \overline{M} is a ∅-definable strongly continuous function assuming all its values in one of the sets M, \overline{M} \M and φ(\overline{x}, y) is an L-formula defining in M the set \{⟨\overline{a}, b⟩ ∈ C ×M : f(\overline{a}) > b\} ⊆ M^{m+1}, then the set φ(N^{m+1}) is of the form \{⟨\overline{a}, b⟩ ∈ D × N : g(\overline{a}) > b\}, where D ⊆ N^{m} is a strong ⟨i_{1}, …, i_{m}⟩-cell in N^{m} of type τ, g : D ⟶ \overline{N} is a strongly continuous function assuming all its values in one of the sets N, \overline{N} \ N. Both D and g are ∅-definable in N. Moreover, if all values of f lie in M [in \overline{M} \ M], then all values of g lie in N [in \overline{N} \ N].

Proof. If φ(x) is an L-formula defining in M a strong cell contained in M (i.e. a singleton or a convex open set), then obviously φ(N) is a strong cell of the same type. Thus (a)_{1} holds.

To prove (b)_{1}, fix i ∈ {0, 1} and a ∅-definable strong ⟨i⟩-cell in M. Assume that f : C ⟶ M is a ∅-definable strongly continuous function and φ(x, y) is an L-formula defining in M the set {⟨a, b⟩ ∈ C × M : f(a) > b}. If i = 0, then φ(M^{2}) = {a} × (−∞, b) for some a, b ∈ dcl(∅). It is clear that the set defined by φ(x, y) in N is of the same form. Consider now the case i = 1, i.e. C is convex and open. One could easily see that the set defined in N by φ(x, y) is of the form {⟨a, b⟩ ∈ D × N : g(a) > b}, where D is a convex open ∅-definable set and g : D ⟶ N is a ∅-definable function. The function g is continuous and piecewise monotone. Moreover, by (a)_{1} the types of C and D are equal. Suppose for a contradiction that g is not strongly continuous. Then there is an L(N)-formula ψ(x) such that d := ⟨ψ(N), ¬ψ(N)⟩ is a cut in (N, ≤) which belongs to the completion of D in \overline{N}^{N} and the limits lim_{x⟶d^{−}} g(x) and lim_{x⟶d^{+}} g(x) are different. Since

g is piecewise monotone, by weak o-minimality of N the number of cuts with this property is finite, so d must be definable over ∅. But then the limits lim_{x⟶c^{+}} f(x) and lim_{x⟶c^{−}} f(x) are different,

where c = ⟨ψ(M), ¬ψ(M)⟩ is a cut in (M, ≤) which belongs to the completion of C in \overline{M}^{M}. This contradicts our assumption about f. In a similar manner we analyze the case when f assumes all its values in \overline{M}^{M} \ M.

Assume now that m > 1 and suppose that we have already proved (a)_{k} and (b)_{k} for k < m. (a)_{m} is an immediate consequence of (b)_{m−1}. To prove (b)_{m}, assume that i_{1}, …, i_{m} ∈ {0, 1}, C ⊆ M^{m} is a ∅-definable strong ⟨i_{1}, …, i_{m}⟩-cell in M^{m}, f : C ⟶ M is a ∅-definable strongly continuous function and φ(\overline{x}, y) is an L-formula defining in M the set \{⟨\overline{a}, b⟩ ∈ C × M : f(\overline{a}) > b\} ⊆ M^{m+1}. If i_{1} + … + i_{m} < m, then we can homeomorphically project C onto some ∅-definable strong cell in M^{m−1} and then apply (b)_{m−1}. So suppose i_{1} = … = i_{m} = 1. By (a)_{m}, the formula (∃y)φ(\overline{x}, y) defines in N an open strong cell D ⊆ N^{m} such that τ(D) = τ(C). Also it is clear that φ(\overline{x}, y) defines in N a set of the form \{⟨\overline{a}, b⟩ ∈ D×N : g(\overline{a}) > b\} ⊆ N^{m+1}, where g : D ⟶ N is continuous and ∅-definable in N. Suppose for a contradiction that g is not strongly continuous. Then there are a tuple \overline{a} ∈ \overline{D} and elements b, c ∈ N such that b < c and for any open box B ⊆ D with \overline{a} ∈ \overline{B} and any d ∈ (b, c) we have that (B × {d}) ∩ φ(N^{m+1}) ≠ ∅ and (B × {d}) \ φ(N^{m+1}) ≠ ∅. Let \overline{a} = ⟨a_{1}, …, a_{m}⟩ and a_{i} = ⟨ψ_{i}(N, \overline{c}_{i}), ¬ψ_{i}(N, \overline{c}_{i})⟩ for i = 1, …, m, where ψ(z, \overline{y}_{i}) ∈ L. Denote by Y the set of all tuples \overline{d} = \overline{d}_{1} … \overline{d}_{m} ∈ N^{|\overline{d}|} such that |\overline{d}_{i}| = |\overline{c}_{i}|, each pair e_{i} := ⟨ψ_{i}(N, \overline{d}_{i}), ¬ψ_{i}(N, \overline{d}_{i})⟩ is a cut in (N, ≤) and \overline{e} := e_{1} … e_{m} (a tuple determined by \overline{d}) belongs to \overline{D}. The set Y is defined by some L-formula χ(\overline{y}_{1} … \overline{y}_{m}). Therefore the following statement is true in N:

There exist \overline{d} ∈ χ(N^{|\overline{d}|}) (which determines \overline{e} = e_{1} … e_{m} ∈ \overline{D}^{N}) and elements b, c ∈ N such that b < c and for any d′ ∈ (b, c) and any open box B ⊆ D with \overline{e} ∈ \overline{B}, we have that (B × {d′}) ∩ φ(N^{m+1}) ≠ ∅ and (B × {d′}) \ φ(N^{m+1}) ≠ ∅.

The same statement holds with N, D replaced by M and C respectively. Consequently, f is not strongly continuous. The proof is similar in case f assumes all its values in \overline{M} \ M.

Theorem 2.8 If N ≡ M, then N = (N, ≤, …) is weakly o-minimal and has the strong cell decomposition property.

Proof. Weak o-minimality of N is a consequence of Corollary 2.3. Assume that m ∈ ℕ_{+}, A ⊆ N and X_{1}, …, X_{k} ⊆ N^{m} are definable in N over A. So there are L-formulas φ_{1}(\overline{x}, \overline{y}_{1}), …, φ_{k}(\overline{x}, \overline{y}_{k}) and tuples \overline{a}_{1}, …, \overline{a}_{k} ⊆ A such that |\overline{x}| = m, |\overline{y}_{i}| = |\overline{a}_{i}| and X_{i} = φ_{i}(N^{m}, \overline{a}_{i}) for i = 1, …, k. Put \overline{a} = \overline{a}_{1} … \overline{a}_{k}, \overline{y} = \overline{y}_{1} … \overline{y}_{k} and denote the formula φ_{i}(\overline{x}, \overline{y}_{i}) by ψ_{i}(\overline{y}, \overline{x}) = ψ_{i}(\overline{y}_{1} … \overline{y}_{k}, \overline{x}). Clearly, the sets Y_{i} := ψ_{i}(M^{|\overline{a}|+m}) are ∅-definable whenever i ∈ \{1, …, k\}. So there is a ∅-definable strong cell decomposition C of M^{|\overline{a}|+m} partitioning each of Y_{1}, …, Y_{k}. Denote by τ the type of C. There exists an L-formula E(\overline{y}\overline{x}, \overline{y}′\overline{x}′) defining an equivalence relation on M^{|\overline{a}|+m} whose classes are exactly the cells from C, i.e. E(M^{2(|\overline{a}|+m)}) = ⋃\{C × C : C ∈ C\}. Using the lexicographic order <_{C} of C and Lemma 2.7, we see that E(\overline{y}\overline{x}, \overline{y}′\overline{x}′) also determines a ∅-definable strong cell decomposition of type τ of N^{|\overline{a}|+m}. Let χ(\overline{y}, \overline{x}, \overline{x}′) = E(\overline{y}\overline{x}, \overline{y}\overline{x}′). Then the formula χ(\overline{a}, \overline{x}, \overline{x}′) defines an equivalence relation on N^{m} and determines a strong cell decomposition of N^{m} partitioning each of the sets X_{1}, …, X_{k}. This finishes the proof.

The following proposition is proved as a relevant result for sets definable in o-minimal structures. One uses Theorem 2.8.

Proposition 2.9 Assume that m ∈ ℕ_{+}, k ∈ ℕ, A ⊆ M and X ⊆ M^{m} is a non-empty A-definable set, i.e. X = φ(M^{m}), where φ(\overline{x}) ∈ L(A). Then dim(X) ≥ k iff there exist N ≻ M and a tuple \overline{a} ∈ φ(N^{m}) with rk(\overline{a}/A) ≥ k.

Another consequence of Theorem 2.8 is that it makes sense to relativize the construction of \overline{M} described in the previous section to elementary extensions of M. Assume that N_{1} = (N_{1}, ≤, …) and N_{2} = (N_{2}, ≤, …) are weakly o-minimal L-structures, N_{1} has the strong cell decomposition property and f : N_{1} ⟶ N_{2} is an elementary map. Then, by Theorem 2.8, N_{2} has the strong cell decomposition property too. Clearly, if φ(x, \overline{y}) ∈ L, \overline{a} ∈ N_{1}^{|\overline{y}|} and ⟨φ(N_{1}, \overline{a}), ¬φ(N_{1}, \overline{a})⟩ is a cut in (N_{1}, ≤), then ⟨φ(N_{2}, f(\overline{a})), ¬φ(N_{2}, f(\overline{a}))⟩ is a cut in (N_{2}, ≤). Hence we obtain an order-preserving injective map f^{∗} : \overline{N_{1}} ⟶ \overline{N_{2}}. The map f^{∗} is well defined because N_{1} ≺ N_{2}. Note that the construction of f^{∗} described here works for any models expanding dense linear orderings without endpoints. Apart of this we have f^{∗}(⟨(−∞, a]^{N_{1}}, (a, +∞)^{N_{1}}⟩) = ⟨(−∞, a]^{N_{2}}, (a, +∞)^{N_{2}}⟩.

Denote for m ∈ ℕ_{+} and any f[N_{1}]-definable (in N_{2}) strong cell C ⊆ N_{2}^{m} by \overline{R}_{C} the m-ary relation determined by the completion of C in \overline{N}_{2}^{N_{2}}, i.e. if \overline{a} ∈ N_{2}^{m}, then \overline{R}_{C}(\overline{a}) holds iff \overline{a} ∈ \overline{C}^{N_{2}}. Let

\overline{N_{2}}^{N_{1}} = (\overline{N_{2}}, ≤, (\overline{R}_{C} : C is a strong cell definable over f[N_{1}])).

The structure \overline{N_{2}}^{N_{1}} is o-minimal because it is a reduct of \overline{N_{2}}. We will call it a relative o-minimal extension of N_{2}. Repeating the arguments from the proof of Proposition 1.2, we can see that every basic cell contained in \overline{N_{2}}^{m} [constructed only with functions definable over f[N_{1}]] is a finite Boolean combination of completions of strong cells in \overline{N_{2}}^{m} definable in N_{2} [over f[N_{1}]]. Repeating suitable arguments from [We07], we can prove that every set X ⊆ \overline{N}_{2}^{m} definable in \overline{N_{2}}^{N_{1}} is a finite union of basic cells definable in \overline{N_{2}}^{N_{1}} (and hence a finite Boolean combination of completions of strong cells contained in \overline{N_{2}}^{m} and definable in N_{2} over f[N_{1}]).

Fact 2.10 The map f^{∗} is an elementary embedding of \overline{N_{1}} into \overline{N_{2}}^{N_{1}}.

Proof. Note that if C ⊆ N_{1}^{m} is a strong cell definable in N_{1} by some formula ψ(\overline{x}) ∈ L(N_{1}), then also D := ψ(N_{2}^{m}) is a strong cell whose type is equal to the type of C. Moreover \overline{C}^{N_{1}} ⊆ \overline{D}^{N_{2}}. Thus f^{∗} is an embedding of the o-minimal structure \overline{N_{1}} into \overline{N_{2}}^{N_{1}}.

To prove that f^{∗} is elementary, it is enough to demonstrate that the image of f^{∗} is an elementary substructure of \overline{N_{2}}^{N_{1}}. We will use Tarski-Vaught test. Let X ⊆ \overline{N_{2}}^{N_{1}} be a non-empty set definable in \overline{N_{2}}^{N_{1}} over a tuple \overline{a} ∈ (f^{∗}[\overline{N_{1}}^{N_{1}}])^{m}. We will show that X has a non-empty intersection with f^{∗}[\overline{N_{1}}^{N_{1}}]. There is a set S ⊆ (\overline{N_{2}}^{N_{1}})^{m+1}, ∅-definable in \overline{N_{2}}^{N_{1}}, such that S\overline{a} = X. By the construction of \overline{N_{2}}^{N_{1}}, we can find a basic cell C ⊆ S, definable in \overline{N_{2}}^{N_{1}} over f^{∗}[\overline{N_{1}}^{N_{1}}], such that C\overline{a} = C ∩ (\{\overline{a}\} × S\overline{a}) ≠ ∅. Note that C\overline{a} ⊆ X, so we will be done if we find in C\overline{a} an element b ∈ f^{∗}[\overline{N}_{1}^{N_{1}}]. This is clear in case C\overline{a} is a singleton because C\overline{a} is definable over f^{∗}[\overline{N_{1}}^{N_{1}}]. So assume that C\overline{a} is an open interval in (\overline{N_{2}}^{N_{1}}, ≤) and denote by k the dimension of C. There is a projection π : (\overline{N_{2}}^{N_{2}})^{m+1} ⟶ (\overline{N_{2}}^{N_{2}})^{k} such that π[C] is a completion of an open strong cell D ⊆ N_{2}^{k}, definable over N_{1}. Moreover, π does not drop the last coordinate, π[C] is open in (\overline{N_{2}}^{N_{1}})^{k} and π ↾ C is a homeomorphism. Since N_{1} ≺ N_{2}, there exists b ∈ N_{1} such that π(\overline{a}b) ∈ π[C]. Hence b ∈ C\overline{a}.

Assume now that M is a weakly o-minimal structure with the strong cell decomposition property and f : M ⟶ N_{1}, g : M ⟶ N_{2} and h : N_{1} ⟶ N_{2} are elementary maps such that h ∘ f = g (then, by Theorem 2.8, N_{1} and N_{2} are weakly o-minimal structures with the strong cell decomposition property). The construction described before Fact 2.10 gives us two elementary maps: f^{∗} : \overline{M} ⟶ \overline{N_{1}}^{M} and g^{∗} : \overline{M} ⟶ \overline{N_{2}}^{M}. Apart of this, if ⟨C, D⟩ is a cut in (N_{1}, ≤) definable in N_{1} over f[M], then h^{∗}(⟨C, D⟩) := ⟨h[C], h[D]⟩ is a cut in (N_{2}, ≤) definable in N_{2} over h[f[M]] = g[M]. Reasoning as in the proof of Fact 2.10, one can demonstrate that h^{∗} is an elementary embedding of \overline{N_{1}}^{M} into \overline{N_{2}}^{M}. Also it is easy to check that h^{∗} ∘ f^{∗} = g^{∗}.

For a weakly o-minimal L-structure M with the strong cell decomposition property we define a category C(M) as follows. Objects of C(M) are weakly o-minimal structures N together with elementary embeddings of M into N (necessarily such N has the strong cell decomposition property; if M is o-minimal, then N is o-minimal). A morphism between N_{1} and N_{2} together with elementary embeddings f : M ⟶ N_{1}, g : M ⟶ N_{2} is an elementary map h : N_{1} ⟶ N_{2} such that h ∘ g = f.

Theorem 2.11 The construction of relative o-minimal extension determines a covariant functor F between categories C(M) and C(\overline{M}). If f : M ⟶ N is an elementary map, then F sends N together with f to \overline{N}^{M} with f^{∗} : \overline{M} ⟶ \overline{N}^{M}.

3 Fiberwise properties

The goal of this section is to prove two theorems saying that for a set [function] definable in a weakly o-minimal structure with the strong cell decomposition property, fiberwise open [fiberwise continuous] implies piecewise open [piecewise continuous]. Results of this kind were proved in [BCR] in a special case of sets and functions definable in real closed fields. They appear in [vdD2, Chapter 6] for o-minimal structures expanding an ordered group. Finally, P. Speissegger generalizes them to the context of arbitrary o-minimal structures (see [Sp]).

Definition 3.1 Assume that m, n ∈ ℕ_{+} and X ⊆ M^{m}, S ⊆ M^{m+n} are definable sets.

(a) We say that S has nice closure above a tuple \overline{a} ∈ M^{m} in M^{m+n} if for every \overline{b} ∈ M^{n} with ⟨\overline{a}, \overline{b}⟩ ∈ cl(S), we have that \overline{b} ∈ cl(S\overline{a}).

(b) We say that S has nice closure above X in M^{m+n} if for every \overline{a} ∈ X, S has nice closure above \overline{a} in M^{m+n}.

We will also consider nice closures above tuples and sets for the o-minimal structure \overline{M}.

Lemma 3.2 Assume that m ∈ ℕ_{+}, A ⊆ M and S ⊆ M^{m+1} is an A-definable set such that for every \overline{a} ∈ M^{m}, the fiber S\overline{a} is open in M. Then there is an A-definable strong cell decomposition D of M^{m+1} partitioning S such that for every D ∈ D, (π[D] × M) ∩ S is open in π[D] × M, where π : M^{m+1} ⟶ M^{m} is the projection dropping the last coordinate.

Proof. By Lemma 2.2(b), there exists k ∈ ℕ_{+} such that for every \overline{a} ∈ M^{m}, the fiber S\overline{a} has at most k convex components. For i ≤ k, let X_{i} be the set of all tuples \overline{a} ∈ M^{m} such that S\overline{a} has exactly i convex components. Clearly, the sets X_{0}, …, X_{n} are definable over A. Let D be an A-definable strong cell decomposition of M^{m+1} partitioning each of the sets X_{0} × M, …, X_{k} × M. Such set D satisfies our demands.

Lemma 3.3 Assume that n ∈ ℕ_{+}, I ⊆ M is an open interval and Y ⊆ H ⊆ M^{1+n} are definable sets satisfying:

(1) (∀a ∈ I)(Y_{a} ≠ ∅) and

(2) for every ⟨a, \overline{b}⟩ ∈ Y there is an open box B ⊆ H_{a} such that (\{a\} × B) ∩ Y ≠ ∅. Then there are an open interval J ⊆ I and an open box B ⊆ M^{n} such that I × B ⊆ H and ({a} × B) ∩ Y ≠ ∅ whenever a ∈ J.

Proof. There exists a strong cell decomposition C of M^{1+n} partitioning each of the sets Y, H and I × M^{n}. Let C ∈ C be a strong cell contained in Y and such that the projection π[C] of C onto the first coordinate is infinite. Fix ⟨a, \overline{b}⟩ ∈ C. By assumption, there is an open box B_{0} ⊆ H_{a} containing \overline{b}. Let B ⊆ B_{0} be an open box containing \overline{b} and such that CL(B) ⊆ \overline{B_{0}}. As all functions used to construct strong cells are strongly continuous, we can find an open interval J ⊆ π[C] containing a and such that J × B ⊆ H, (∀c ∈ J)(({c} × B) ∩ C ≠ ∅).

Theorem 3.4 Assume that m, n ∈ ℕ_{+} and A ⊆ M. Let π : M^{m+n} ⟶ M^{m} and \overline{π} : \overline{M}^{m+n} ⟶ \overline{M}^{m} be the projections onto the first m coordinates. If C is an A-definable strong cell decomposition of M^{m+n}, then

(a) there exists an A-definable strong cell decomposition D of M^{m+n} refining C such that every cell D ∈ D has nice closure above π[D] in M^{m+n};

(b) there exists a strong cell decomposition D′ of \overline{M}^{m+n} partitioning \{\overline{C} : C ∈ C\} such that every cell D ∈ D′ has nice closure above \overline{π}[D] in \overline{M}^{m+n}.

Proof. (a) Let A ⊆ M. We proceed inductively on m.

Fix an A-definable strong cell decomposition C of M^{1+n} and let X be the set of all elements a ∈ M such that some cell C ∈ C does not have nice closure above a. Clearly, X is definable over A. We claim that it is finite.

Suppose for a contradiction that X is infinite. Then there exist an A-definable open interval I ⊆ X and an A-definable strong cell C ∈ C such that C does not have nice closure above a whenever a ∈ I. Define

Y = \{⟨a, \overline{b}⟩ ∈ I × M^{n} : ⟨a, \overline{b}⟩ ∈ cl(C), \overline{b} ∉ cl(C\overline{a})\},
H = ⋃_{a∈T} [\{a\} × (M^{n} \ cl(C\overline{a}))] .

Note that the sets Y, H are both A-definable, Y ⊆ H, π[Y] = π[H] = I and (∀a ∈ I)(Y_{a} ≠ ∅). Moreover, for each ⟨a, \overline{b}⟩ ∈ Y we can find an open box B ⊆ M^{n} such that \overline{b} ∈ B ⊆ H\overline{a}. There is an A-definable strong cell decomposition C′ of M^{1+n} partitioning each set from C ∪ {Y, H}. Fix D ∈ C′ with D ⊆ Y and π[D] ⊆ I infinite. By Lemma 3.3, there are an open interval J ⊆ π[D] and an open box B ⊆ M^{n} such that (∀a ∈ J)(({a} × B) ∩ Y ≠ ∅) and {a} × B ⊆ H. But then for a ∈ J, \overline{b} ∈ B with ⟨a, \overline{b}⟩ ∈ Y we have that ⟨a, \overline{b}⟩ ∉ cl(Y), a contradiction.

In case X = ∅ we can take D = C. For X = {a_{1}, …, a_{k}}, where a_{1} < … < a_{k}, let a_{0} = −∞, a_{k+1} = +∞ and let D be the family of all non-empty sets of one of the forms (1), (2):

(1) ({a_{i}} × M^{n}) ∩ C, where i ∈ {1, …, k} and C ∈ C;

(2) ((a_{i}, a_{i+1}) × M^{n}) ∩ C, where i ∈ {0, …, k} and C ∈ C. Then D is an A-definable strong cell decomposition of M^{1+n} refining C. Moreover, every cell D ∈ C has nice closure above π[D] in M^{1+n}. This finishes the proof in case m = 1.

Now assume that m > 1 and the assertion of (a) holds for all l ∈ {1, …, m − 1} and n ∈ ℕ_{+}. Let C be an A-definable strong cell decomposition of M^{m+n}. By the inductive hypothesis, there is an A-definable strong cell decomposition C_{0} of M^{m+n} refining C such that each cell C ∈ C_{0} has nice closure above π′[C], where π′ : M^{m+n} ⟶ M^{m−1} is the projection onto the first m − 1 coordinates. For each C ∈ C_{0}, let X(C) := \{\overline{a} ∈ π[C] : C has nice closure above \overline{a}\}. We claim that X(C) is large in π[C] whenever C ∈ C_{0}.

Suppose for a contradiction that there is a strong cell C ∈ C_{0} such that dim(π[C] \ X(C)) = dim(π[C]). Let C′ be an A-definable strong cell decomposition refining C_{0} and partitioning X(C)× M^{n}. Fix a strong cell D ∈ π[C′] with D ⊆ π[C] ∩ X(C) and dim(D) = dim(π[C]). Then D is open in π[C], (D × M^{n}) ∩ C is open in C and for every \overline{a} ∈ D, (D × M^{n}) ∩ C does not have nice closure above \overline{a}. Below we consider two cases. Note that D′ := π′[(D × M^{n}) ∩ C] is the projection of D onto the first m − 1 coordinates.

Case 1. D = Γ(f) for some strongly continuous A-definable function f : D′ ⟶ M. Then given ⟨\overline{x}, z, \overline{y}⟩ ∈ cl((D × M^{n}) ∩ C) with \overline{x} ∈ D′ and z = f(\overline{x}), we have by hypothesis that ⟨z, \overline{y}⟩ ∈ cl(((D × M^{n}) ∩ C)\overline{x}) = cl(C\overline{x}). One easily verifies that C\overline{x} = \{f(\overline{x})\} × C_{⟨\overline{x},f(\overline{x})⟩}, so \overline{y} ∈ cl(C_{⟨\overline{x},f(\overline{x})⟩}) = cl(C_{⟨\overline{x},z⟩}). Therefore (D × M^{n}) ∩ C has nice closure above D. A contradiction.

Case 2. D = (α, β)_{D′} for some strongly continuous A-definable functions α, β : D′ ⟶ \overline{M} ∪ \{−∞, +∞\} such that: (1) each of α, β assumes all its values in one of the sets M, \overline{M} \ M, \{−∞\}, \{+∞\}, (2) \overline{α}(\overline{x}) < \overline{β}(\overline{x}) for \overline{x} ∈ \overline{D′}. Given \overline{a} ∈ D′, we know from case m = 1 applied to C\overline{a} ∩ (α(\overline{a}), β(\overline{a})) that the A\overline{a}-definable set

S(\overline{a}) := \{c ∈ (α(\overline{a}), β(\overline{a})) : ⟨c, \overline{b}⟩ ∈ cl(C\overline{a}) implies \overline{c} ∈ cl(C_{⟨\overline{a},b⟩})\}

is cofinite in (α(\overline{a}), β(\overline{a})). Let I\overline{a} be the maximal convex open set contained in S(\overline{a}) such that inf I\overline{a} = α(\overline{a}). Note that the set

H := ⋃_{\overline{a}∈D′}(\{\overline{a}\} × I\overline{a})

is A-definable and each fiber H\overline{a} is open in M for \overline{a} ∈ D′. Applying Lemma 3.2 to H we see that there is an A-definable strong cell decomposition E of M^{m+1} partitioning H such that for every cell X ∈ E, (π_{1}[D] × M) ∩ H is open in π_{1}[D] × M, where π_{1} : M^{m+1} ⟶ M^{m} is the projection dropping the last coordinate. So there is an A-definable strong call D′′ ⊆ D′, open in D′, such that (D′′ ×M)∩H is open in D′′ ×M. Then also (D′′ ×M)∩H is open in π[C]. Let E ⊆ (D′′ ×M)∩H be an A-definable strong cell open in (D′′ × M) ∩ H. Then it is easy to see that C has nice closure above E, a contradiction with our choice of D.

Now, let C_{1} be an A-definable strong cell decomposition of M^{m+n} refining C_{0} and partitioning each of the sets X(C) × M^{n}, where C ∈ C_{0}. Then: (1) each cell C ∈ C_{1} has nice closure above π′[C] and (2) each cell C ∈ C_{1} with dim(π[C]) > m−1 (i.e. dim(π[C]) = m) has nice closure above π[C].

Repeating the above procedure for k = 2, …, m with C_{k−1} in place of C_{0}, we obtain A-definable strong cell decompositions C_{2}, …, C_{m} of M^{m+n} such that for every k ∈ {2, …, m}: (1) each cell C ∈ C_{k} has nice closure above π′[C] and (2) each cell C ∈ C_{k} with dim(π[C]) > m − k has nice closure above π[C]. The property (2) for k = m means that each infinite cell from C_{m} has nice closure above π[C]. It is obvious that also every one-element cell from C_{m} has nice closure above its projection onto the first m coordinates. Of course, C_{m} refines C. Thus D := C_{m} satisfies our demands.

(b) Let C′ be a cell decomposition of \overline{M}^{m+n} partitioning each cell C ∈ C. Now, since \overline{M} is o-minimal has the strong cell decomposition property, we are done by [Sp] or by (a).

As in [Sp], using Theorem 3.4, we can easily obtain the following result together with Corollary 3.6.

Theorem 3.5 Assume that A ⊆ M, π : M^{m+n} ⟶ M^{m} is the projection onto the first m coordinates and S ⊆ M^{m+n} is an A-definable set such that for each \overline{a} ∈ M^{m}, the fiber S\overline{a} is open in M^{n}. Then there is an A-definable strong cell decomposition C of M^{m} partitioning π[S] such that S ∩ (C × M^{n}) is open in C × M^{n} whenever C ∈ C. The same is true when we replace “open” with “closed”.

Corollary 3.6 Assume that S′ ⊆ S ⊆ M^{m+n} are definable sets and X ⊆ M^{m} such that S′ ; \overline{a} is open in S\overline{a} for all \overline{a} ∈ X. Then there is a partition of X into definable sets X_{1}, …, X_{k} such that S′ ∩(X_{i} ×M^{n}) is open in S ∩(X_{i} ×M^{n}) for i = 1, …, k. The same is true when we replace “open” with “closed”.

The following generalizes Theorem 3 from [Sp]. The proof is omitted as it looks almost exactly as in the o-minimal setting.

Theorem 3.7 Assume that k, m, n ∈ ℕ_{+}, A ⊆ M and the sets X ⊆ M^{m}, S ⊆ M^{m+n} are definable over A. For every A-definable function f : S ⟶ M^{k} such that f\overline{a} : S\overline{a} ⟶ M^{k} is continuous for all \overline{a} ∈ X, there exists an A-definable strong cell decomposition C of M^{m} partitioning X such that for each C ∈ D with C ⊆ X, the function f ↾ S ∩ (C × M^{n}) : S ∩ (C × M^{n}) ⟶ M^{k} is continuous.

Corollary 3.8 Assume that k, l, m, n ∈ ℕ_{+}, A ⊆ M, the sets X_{1}, …, X_{l} ⊆ M^{m}, S ⊆ M^{m+n} are definable over A and X_{1}, …, X_{l} are pairwise disjoint. For every A-definable function f : S ⟶ M^{k} such that f ↾ S ∩ (X_{i} × M^{n} is injective for i = 1, …, l and f\overline{a} : S\overline{a} ⟶ M^{k} is a homeomorphism for all \overline{a} ∈ X_{i}, then is an A-definable strong cell decomposition D of M^{m} partitioning each of the sets X_{1}, …, X_{l} such that for each C ∈ D, the function f ↾ S ∩ (C × M^{n}) is a homeomorphism.

4 Equivalence relations and imaginaries

In this section we deal with definable equivalence relations. We prove several facts concerning definability of equivalence classes, finiteness of the number of equivalence classes of maximal dimension and uniform finiteness for definable families of definable equivalence relations. Some facts appearing in this section generalize Pillay’s results from [Pi]. We mainly use induction on the dimension. As strong cells in general are not definably connected, one cannot easily transfer the methods from [Pi].

Proposition 4.1 Assume that A ⊆ M and E is an A-definable equivalence relation on M^{m} with only finitely many equivalence classes. Then each class of E is definable over A.

Proof. We proceed inductively on m. Assume first that E is an A-definable equivalence relation on M with k equivalence classes. Let X_{0} = Y_{0} = ∅ and for i = 1, …, k define

X_{i} = {a ∈ M \ (Y_{0} ∪ … ∪ Y_{i−1}) : (∀b ∈ M \ (Y_{0} ∪ … ∪ Y_{i−1}))(b ≤ a ⟶ E(a, b))},
Y_{i} = {a ∈ M : (∃b ∈ X_{i})(E(a, b))}.

Clearly, the sets Y_{1}, …, Y_{k} are A-definable equivalence classes of E. For every i ∈ {1, …, k}, X_{i} is the leftmost convex component of Y_{i}.

Suppose now that the proposition holds for dimension m. Fix an A-definable equivalence relation E on M^{m+1} with finitely many equivalence classes. Let k be the maximal number of classes od E intersecting \{\overline{a}\} × M as \overline{a} ranges over M^{m}. Let X_{0} = Y_{0} = ∅ and for i = 1, …, k define

X_{i} = \{\overline{a}b ∈ M^{m+1} \ (Y_{0} ∪ … ∪ Y_{i−1}) :
(∀c ∈ M)[(\overline{a}c ∈ M^{m+1} \ (Y_{0} ∪ … ∪ Y_{i−1}) ∧ c ≤ b) ⟶ E(\overline{a}b, \overline{a}c)]\},
Y_{i} = \{\overline{a}b ∈ M^{m+1} : (∃c ∈ M)(\overline{a}c ∈ X_{i} ∧ E(\overline{a}b, \overline{a}c))\}.

Clearly, the sets Y_{1}, …, Y_{k} are pairwise disjoint, A-definable and Y_{1} ∪ … ∪ Y_{k} = M^{m+1}. Each Y_{i} is a union of some equivalence classes of E. Moreover, for any \overline{a} ∈ M^{m}, i ∈ \{1, …, k\} and b, c ∈ M, if \overline{a}b, \overline{a}c ∈ Y_{i}, then M ⊧ E(\overline{a}b, \overline{a}c). Hence for each i ∈ \{1, …, k\}, we have an A-definable equivalence relation E_{i} on M^{m} with finitely many equivalence classes: for \overline{a}_{1}, \overline{a}_{2} ∈ M^{m},

\overline{a}_{1}E_{i}\overline{a}_{2} ⟺ (∃b_{1}, b_{2} ∈ M)(\overline{a}_{1}b_{1}, \overline{a}_{2}b_{2} ∈ Y_{i} and M ⊧ E(\overline{a}_{1}b_{1}, \overline{a}_{2}b_{2})) or
(∀b_{1}, b_{2} ∈ M)(\overline{a}_{1}b_{1}, \overline{a}_{2}b_{2} ∉ Y_{i}).

By our inductive assumption, all equivalence classes of E_{i} are A-definable. Note that every equivalence class of E is of the form Y_{i} ∩ (Z × M), where i ∈ {1, …, k} and Z is an equivalence class of E_{i}. This finishes the proof.

Lemma 4.2 Assume that A ⊆ M and E is an A-definable equivalence relation on M. Then E has only finitely many infinite equivalence classes. Each infinite class of E is definable over A.

Proof. Fix an L(A)-formula E(x, y) defining an equivalence relation E on M and denote by E_{0}(x, y) the L(A)-formula saying that either x = y and x ∉ int([x]_{E}), or there exists an open interval I containing {x, y} such that all elements from I are E-equivalent. Clearly, E_{0}(x, y) defines an equivalence relation E_{0} on M and each equivalence class of E is a union of some equivalence classes of E_{0}. Moreover, each equivalence class of E_{0} is either a singleton or a convex open set.

There is an A-definable strong cell decomposition C of M^{2} partitioning E_{0}. Note that if I is an infinite equivalence class of E_{0} and elements a, b ∈ M satisfy one of the inequalities: a < inf I < b, a < sup I < b, b < inf I < a or b < sup I < a, then a, b are not E_{0}-equivalent. Consequently, if C ∈ C is open and C ∩ (I × I) ≠ ∅, then C ⊆ I × I. This means that E_{0} (and thus E) has at most |C\overline{a}| ≤ |C| infinite equivalence classes.

To finish the proof, denote by E_{1}(x, y) the formula saying that either x, y belong to the same infinite E-class or the classes [x]_{E}, [y]_{E} are both finite. Clearly, E_{1}(x, y) determines an A-definable equivalence relation on M with finitely many classes. Moreover, each infinite class of E is a class of E_{1}. By Proposition 4.1, each class of E_{1} is A-definable. Hence each infinite class of E is A-definable.

Lemma 4.3 Let m ∈ ℕ_{+}. If E(x, y, \overline{z}) is an L(A)-formula such that |\overline{z}| = m and for every \overline{a} ∈ M^{m}, E(x, y, \overline{a}) defines an equivalence relation E\overline{a} on M with finitely many equivalence classes, then there exists a positive integer k such that for every \overline{a} ∈ M^{m}, E\overline{a} has at most k equivalence classes.

Proof. Reasoning as in the proof of Lemma 4.2, we can define an L(A)-formula E_{0}(x, y, \overline{z}) with the following properties:

• for every \overline{a} ∈ M^{m}, the formula E_{0}(x, y, \overline{a}) defines an equivalence relation E\overline{a} ; 0 on M;

• for every \overline{a} ∈ M^{m}, each equivalence class of E\overline{a} ; 0 is either a singleton or a convex open set; more precisely: each convex open equivalence class of E\overline{a} ; 0 is the interior of some infinite convex component of some equivalence class of E\overline{a}, the relation defined by E(x, y, \overline{a});

• for every \overline{a} ∈ M^{m}, each equivalence class of E\overline{a} is a union of some equivalence classes of E\overline{a} ; 0.

• for every \overline{a} ∈ M^{m}, the number of equivalence classes of E\overline{a} ; 0 if finite.

Define

S = \{⟨\overline{a}, b, c⟩ ∈ M^{m+2} : M ⊧ E_{0}(b, c, \overline{a})\}.

Let C be a strong cell decomposition of M^{m+2} partitioning S. Then for every \overline{a} ∈ M^{m}, \{C\overline{a} : C ∈ C\} is a strong cell decomposition of M^{2} partitioning S\overline{a}. Note that the fiber S\overline{a} is equal to the equivalence relation E\overline{a} ; 0. As in the proof of Lemma 4.2, if I is a convex open equivalence class of E\overline{a} ; 0 and C ∈ C is a strong cell such that C\overline{a} is open in M^{2} and C\overline{a} ∩ (I × I) ≠ ∅, then C\overline{a} ⊆ I × I. Consequently, each equivalence relation E\overline{a} ; 0 has at most |C\overline{a}| ≤ |C| infinite equivalence classes. Since the E\overline{a} ; 0-classes are either singletons or convex open sets, the number of all E\overline{a} ; 0-classes is not greater than 2|C| − 1. Hence also E\overline{a} has at most 2|C| − 1 equivalence classes as \overline{a} ranges over M^{m}.

Corollary 4.4 Let m ∈ ℕ_{+}. If E(x, y, \overline{z}) is an L(A)-formula such that |\overline{z}| = m and for every \overline{a} ∈ M^{m}, E(x, y, \overline{a}) defines an equivalence relation E\overline{a} on M, then there exists a positive integer k such that for every \overline{a} ∈ M^{m}, the equivalence relation E\overline{a} has at most k infinite equivalence classes.

Proof. Following the last paragraph of the proof of Lemma 4.2, we can define an L(A)-formula E_{1}(x, y, \overline{z}) such that for every \overline{a} ∈ M^{m}, E_{1}(x, y, \overline{a}) defines an equivalence relation E\overline{a} ; 1 on M such that x, y are E\overline{a} ; 1-equivalent if either x, y belong to the same infinite E\overline{a}-class or the classes [x]_{E\overline{a}}, [y]_{E\overline{a}} are both finite. By Lemma 4.2, for every \overline{a} ∈ M^{m}, the equivalence relation E\overline{a} has finitely many infinite equivalence classes. Hence E\overline{a} ; 1 has finitely many equivalence classes whenever \overline{a} ∈ M^{n}. By Lemma 4.3, there is k ∈ ℕ_{+} such that E\overline{a} ; 1 has at most k + 1 equivalence classes as \overline{a} ranges over M^{m}. Since each infinite class of E\overline{a} is also a class of E\overline{a} ; 1, the number of infinite E\overline{a}-classes does not exceed k as \overline{a} ranges over M^{m}.

Below we generalize Proposition 2.1 from [Pi].

Theorem 4.5 Assume that A ⊆ M and E is an A-definable equivalence relation on M^{m}. Then E has only finitely many equivalence classes of dimension m. Moreover, each m-dimensional E-class is definable over A.

Prof. We proceed inductively on m. The case m = 1 is a consequence of Lemma 4.2. So suppose that the theorem holds for all A-definable equivalence relations on M^{m} and fix an A-definable equivalence relation E on M^{m+1}. Let X be the set of all tuples \overline{a} ∈ M^{m+1} with the property that there exists an open box B ⊆ M^{m+1} containing \overline{a} such that B ⊆ E(\overline{a}, M). Clearly, X is open in M^{m+1} and definable over A. Moreover, X is the union of interiors of all m + 1-dimensional equivalence classes of E.

Consider the formula F (x, y, \overline{z}) saying that either we can find an open interval I ⊆ M containing x, y such that \{\overline{z}\} × I is contained in X and in some E-class, or \overline{z}x, \overline{z}y ∉ X. It is easy to see that F (x, y, \overline{a}) defines an equivalence relation F \overline{a} on M whenever \overline{a} ∈ M^{m}. The definition of F guarantees that for every \overline{a} ∈ M^{m}, F \overline{a} has at most one finite class. All F \overline{a}-classes contained in X\overline{a} are convex open sets. By Lemma 4.2, the number of infinite F \overline{a}-classes is finite. Consequently, F \overline{a} has only finitely many equivalence classes, and by Lemma 4.3, this number is bounded by some k ∈ ℕ_{+} as \overline{a} ranges over M^{m}. Note also that the number of convex components of X\overline{a} does not exceed k for \overline{a} ∈ M^{m}.

Now, for \overline{a} ∈ M^{m} and i ∈ \{1, …, k\}, let J_{i}(\overline{a}) be the i-th (convex, open) equivalence class of F \overline{a} contained in X\overline{a} in case F \overline{a} has at least i such classes, and let J_{i}(\overline{a}) = ∅ otherwise. For i = 1, …, k define

X_{i} = ⋃_{\overline{a}∈M^{m}}(\{\overline{a}\} × J_{i}(\overline{a})).

It is easy to see that

• the sets X_{1}, …, X_{k} are A-definable and pairwise disjoint,

• X_{1} ∪ … ∪ X_{k} = X,

• for any i ∈ \{1, …, k\} and \overline{a} ∈ M^{m}, the set \{\overline{a}\}×(X_{i})\overline{a} is contained in some m+1-dimensional E-class.

For i = 1, …, k we can define an equivalence relation F_{i} on M^{m} as follows: the tuples \overline{a}_{1}, \overline{a}_{2} ∈ M^{m} are F_{i}-equivalent if either (X_{i})_{\overline{a}_{1}} = (X_{i})_{\overline{a}_{2}} = ∅ or (X_{i})_{\overline{a}_{1}}, (X_{i})_{\overline{a}_{2}} are non-empty subsets of the same equivalence class of E. Clearly, F_{1}, …, F_{k} are definable over A. By the inductive assumption, each of the equivalence relations F_{1}, …, F_{k} has finitely many m-dimensional equivalence classes. Moreover, each m-dimensional class of each F_{i} is definable over A. For i = 1, …, k, let C_{i} be an A-definable strong cell decomposition of M^{m} partitioning all m-dimensional equivalence classes of F_{i}. Note that if C is an open strong cell from C_{i}, then X_{i} ∩ (C × M) is an open A-definable set contained in some m + 1-dimensional E-class. This implies that E has only finitely many m + 1-dimensional equivalence classes and all of them are A-definable.

Corollary 4.6 Assume that m ∈ ℕ_{+}, n ∈ ℕ, A ⊆ M and S ⊆ M^{m} is an n-dimensional Adefinable set. Every A-definable equivalence relation on S has only finitely many equivalence classes of dimension n. Moreover, each n-dimensional E-class is definable over A.

Proof. Assume that S ⊆ M^{m} is an n-dimensional A-definable set and E is an A-definable equivalence relation on S. As there is nothing to do for n = 0, suppose that n ≥ 1. Let C be an A-definable strong cell decomposition of M^{m} partitioning S. Then for each C ∈ ℂ with C ⊆ S, E ∩ (C × C) is an A-definable equivalence relation on C. For each n-dimensional strong cell C ∈ C, denote by π_{C} the projection from M^{m} onto M^{n} such that π_{C}[C] is an open subset of M^{n} and π_{C} ↾ C is a homeomorphism. Also, let E_{C} be the equivalence relation on M^{n} defined by the following condition:

\overline{a}E_{C} \overline{b} ⟺ [\overline{a}, \overline{b} ∈ π_{C}[C] ∧ (∃\overline{c}, \overline{d} ∈ C)(π_{C}(\overline{c}) = \overline{a} ∧ π_{C}(\overline{d}) = \overline{b} ∧ \overline{c}E\overline{d})] ∨ (\overline{a}, \overline{b} ∉ π_{C}[C]).

Clearly, E_{C} is an A-definable equivalence relation on M^{n}, so by Theorem 4.5, E_{C} has only finitely many n-dimensional classes. Moreover, each E_{C}-class of dimension n is definable over A. Hence the number of n-dimensional E-classes is finite and each each of them is A-definable.

Theorem 4.7 Let m, n ∈ ℕ_{+}. If E(\overline{x}, \overline{y}, \overline{z}) is an L(A)-formula such that |\overline{x}| = |\overline{y}| = n, |\overline{z}| = m and for every \overline{a} ∈ M^{m}, E(\overline{x}, \overline{y}, \overline{a}) defines an equivalence relation E\overline{a} on M^{n}, then there exists k ∈ ℕ_{+} such that for every \overline{a} ∈ M^{m}, the equivalence relation E\overline{a} has at most k equivalence classes of dimension n.

Proof. Suppose for a contradiction that the number of equivalence classes of E\overline{a} is unbounded as \overline{a} ranges over M^{m}. Let N be an ℵ_{1}-saturated elementary extension of M. By Theorem 2.7, N is weakly o-minimal and has the strong cell decomposition property. By ℵ_{1}-saturation we can find a tuple \overline{c} ∈ N^{m} such that the formula E(\overline{x}, \overline{y}, \overline{c}) defines an equivalence relation on N^{n} with infinitely many n-dimensional equivalence classes. This contradicts Theorem 4.5.

Given m ∈ ℕ_{+}, a set A ⊆ M and an A-definable strong cell decomposition C of M^{m}, we can easily see that there is an A-definable equivalence relation on M^{m} whose equivalence classes are exactly the cells from C. On the other hand, it is a routine to check that whenever E(\overline{x}, \overline{y}, \overline{z}) an L-formula such that |\overline{x}| = |\overline{y}| = m and for every \overline{a} ∈ M^{|\overline{z}|}, E(\overline{x}, \overline{y}, \overline{a}) defines an equivalence relation E\overline{a} on M^{m} with finitely many classes, then the set of all tuples \overline{a} ∈ M^{n} for which \{[\overline{x}]_{E\overline{a}} : \overline{x} ∈ M^{m}\} is a strong cell decomposition of M^{m} of a given type is definable over A. Hence, since the number of equivalence classes of E\overline{a} is bounded by some k ∈ ℕ_{+} as \overline{a} ranges over M^{m}, the set of all tuples \overline{a} ∈ M^{n} such that E\overline{a} determines a strong cell decomposition of M^{m} is A-definable. Using these observations we are in a position to prove that the strong cell decomposition property is preserved under elementary equivalence.

5 Elimination of imaginaries

There are easy examples of o-minimal structures that do not admit elimination of imaginaries (see [Pi, §3]). Nevertheless, assuming the modularity law or asserting that every definably closed set is an elementary substructure of the given model, one can prove elimination of imaginaries. It turns out that each of these assumptions implies elimination of imaginaries it the context of weakly o-minimal structures with the strong cell decomposition property.

To obtain the following proposition one can rewrite word by word the proof of Proposition 2.2 from [Pi].

Proposition 5.1 Let A, B, C ⊆ M be such that B and C are independent over A. If X ⊆ M^{n} is B-definable and C-definable, then X is A-definable.

The next proposition generalizes Proposition 2.3 from [Pi].

Proposition 5.2 Assume that B, C ⊆ M, M_{0} = (M_{0}, ≤, …) ≺ M and M_{0} ⊆ B ∩ C. Assume also that every convex subset of M which is definable over B and definable over C is definable over M_{0}. If X ⊆ M^{n} is B-definable and C-definable, then X is M_{0}-definable.

Proof. Suppose that B, C and M_{0} the assumptions and let X ⊆ M^{n} be a set which is Bdefinable and C-definable. There are L-formulas φ(\overline{x}, \overline{y}), ψ(\overline{x}, \overline{z}) and tuples \overline{b} ⊆ B, \overline{c} ⊆ C such that X = φ(M, \overline{b}) = φ(M, \overline{c}). Let E(\overline{y}_{1}, \overline{y}_{2}) = ∀\overline{x}(φ(\overline{x}, \overline{y}_{1}) ⟷ φ(\overline{x}, \overline{y}_{2})). The formula E(\overline{y_{1}, \overline{y}_{2}}) defines an equivalence relation on M^{|\overline{b}|}. Denote by Z the class of E containing \overline{b}. Note that Z = E(M, \overline{b}) = \{\overline{d} ∈ M^{|\overline{b}|} : φ(M, \overline{d}) = ψ(M, \overline{c})\}. Hence Z is B-definable and C-definable.

Let \overline{b} = b_{1} … b_{k}. We will show that Z ∩ M^{k} ≠ ∅. Denote by Z_{1} the projection of Z onto the first coordinate. Then Z is a finite union of convex sets, and each of these is B-definable and C-definable. By assumption, Z_{1} is a union of M_{0}-definable convex sets. Thus Z_{1} ∩ M_{0} ≠ ∅. Fix a_{1} ∈ Z_{1} ∩ M_{0}. Let Z_{2} be the projection of ({a_{1}} × M^{n−1}) ∩ Z onto the second coordinate. Again, Z_{2} is a union of finitely many convex sets, and each of these is B-definable and C-definable. Consequently, Z_{2} is M_{0}-definable and there exists some a_{2} ∈ Z_{2} ∩ M_{0}. Continuing in this way, we obtain a_{1} … a_{k} ∈ Z ∩ M_{0}^{k}.

As the equivalence class Z contains a tuple from M_{0}^{k}, it is definable over M_{0}. Hence also X is definable over M_{0}.

Theorem 5.3 Assume that the weakly o-minimal structure M with the strong cell decomposition property satisfies least one of the following conditions.

(a) For any B, C ⊆ M, B and C are independent over dcl(B) ∩ dcl(C).

(b) For any A ⊆ M, dcl(A) is an elementary substructure of M.

Then M admits elimination of imaginaries.

Proof. The proof goes along the lines of the proof of Proposition 3.2 from [Pi]. One uses Propositions 5.1 and 5.2 to show that every set definable in a weakly o-minimal structure with the strong cell decomposition has smallest definably (equivalently: algebraically) closed defining set together with the following well known facts.

(a) If N is a first order structure such that every set definable in N has smallest algebraically closed defining set, then N admits weak elimination of imaginaries.

(b) If a first order structure N expanding a linear order admits weak elimination of imaginaries, then N admits elimination of imaginaries.

References

[Ar] R. Arefiev, On monotonicity for weakly o-minimal structures, Algebra and Model Theory II, edited by A. G. Pinus and K. N. Ponomarev, Novosibirsk, 1997, pp. 8–15.

[BCR] J. Bochnak, M. Coste and F. Roy, Real algebraic geometry, Springer-Verlag Berlin Heidelberg 1998.

[BP] Y. Baisalov and B. Poizat, Paires de structures o-minimales, J. Symbolic Logic 63 (1998), 570-578.

[Bz] B.S. Baizhanov, Expansion of a model of a weakly o-minimal theory by a family of unary predicates, J. Symbolic Logic 66 (2001), 1382-14 14.

[Di] M.A.Dickmann, Elimination of Quantifiers for Ordered Valuation Rings, J. Symbolic Logic 52 (1987), 116-128.

[vdD1] L. van den Dries, Dimension of Definable Sets, Algebraic Boundedness and Henselian Fields, Ann. Pure Appl. Logic 45 (1989), 189-209.

[vdD2] L. van den Dries, Tame Topology and o-minimal Structures, London Mathematical Society Lecture Notes Series, vol. 248, Cambridge: Cambridge University Press 1998.

[KPS] J. F. Knight, A. Pillay and C. Steinhorn, Definable sets in ordered structures, Trans. Amer. Math. Soc. 295 (1986), 593–605.

[MMS] D. Macpherson, D. Marker, and C. Steinhorn, Weakly o-minimal structures and real closed fields, Trans. Amer. Math. Soc. 352 (2000), 5435–5483.

[Ma] L. Matthews, Cell decomposition and dimension functions in first-order topological structures, Proc. London Math. Soc. 70 (1995), 1-32.

[Pi] A. Pillay, Some remarks on definable equivalence relations in o-minimal structures, J. Symbolic Logic 51 (1986), 709–714.

[Sp] P. Speissegger, Fiberwise properties of definable sets and functions in o-minimal structures, Manuscripta Math. 86 (1995), 283-291.

[We06] R. Wencel, Topological properties of sets definable in weakly o-minimal structures, J. Symbolic Logic 75 (2010), 841–867.

[We07] R. Wencel, Weakly o-minimal non-valuational structures. Ann. Pure Appl. Logic 154 (2008), 139–162.

Mailing adress : Instytut Matematyczny Uniwersytetu Wrocławskiego

pl. Grunwaldzki 2/4, 50-384 Wrocław, POLAND

E-mail:  rwenc@math.uni.wroc.pl