A first set of axioms for o-minimality

Let $\Lambda = (\Lambda_n)_{n \in \NN}$ be a system of collections $\Lambda_n$ of subsets of $\RR^n$.

A set $A \subseteq \RR^n$ is a $\Lambda$-set if $A \in \Lambda_n$. We let $\RR(\Lambda)$ be the expansion of the real field by all $\Lambda$-sets.

We assume the following axioms for $\Lambda$:

$(\Lambda 1)$

all semialgebraic sets are $\Lambda$-sets;

$(\Lambda 2)$

if $A,B \in \Lambda_n$, then so is $A \cap B$;

$(\Lambda 3)$

if $A \in \Lambda_m$ and $B \in \Lambda_n$, then $A \times B \in \Lambda_{m+n}$;

$(\Lambda 4)$

if $A \in \Lambda_n$ and $B$ is obtained from $A$ by a permutation of coordinates, then $B \in \Lambda_n$;

$(\Lambda 5)$

if $A \in \Lambda_n$, there exist $n’ \ge n$ and a closed $B \in \Lambda_{n’}$ such that $A = \Pi_n(B)$;

$(\Lambda 6)$

if $A \in \Lambda_n$, and $m \le n$, there exists $N \in \NN$ such that each fiber $A_x$, for $x \in \RR^m$, has at most $N$ connected components;

$(\Lambda 7)$

if $A \in \Lambda_n$, then there are $k \in \NN$ and manifolds $B_1, \dots, B_k \in \Lambda_n$ in standard position such that $A = B_1 \cup \cdots \cup B_l$.

Let $\R$ be an o-minimal expansion of the real field and, for $n \in \NN$, let $\Lambda_n$ be the collection of all Rolle sets over $\R$ in $\RR^n$. Then, by this post, the system $\Lambda := \left(\Lambda_n\right)_{n \in \NN}$ satisfies Axioms $(\Lambda 1)$–$(\Lambda 7)$.

Our next goal is to prove:

The structure $\RR(\Lambda)$ is o-minimal.

The main ingredient in proving this theorem is a variation on an idea first proposed by Charbonnel and carried to completion by Wilkie in this paper.

To describe the sets definable in $\RR(\Lambda)$ we use, in addition to the basic geometric operations corresponding to the logical connectives and quantifiers, the topological operation of taking Hausdorff limits of fibers of definable sets. While it is not clear that these limits are definable in $\RR(\Lambda)$, this will follow from the o-minimality and the Marker-Steinhorn Theorem (see also van den Dries’s chpater in this book).

In the meantime, we consider the following sets:

A set $X \subseteq \RR^n$ is a basic $\Lambda^\infty$-set if there are $k,l \in \NN$, parameters $z(i,j) \in \RR^k$ for $i,j \in \NN$ and a $\Lambda$-set $W \subseteq \RR^{k+n+l}$ such that

  • each set $X(i,j):= \Pi_nW_{z(i,j)}$ is bounded;
  • for each $i$, the sequence $X(i,j)$ converges to some compact set $X(i) \subseteq \RR^{n}$ in the sense of Hausdorff;
  • we have $X(1) \subseteq X(2) \subseteq \cdots$ and $X = \bigcup_{i \in \NN} X(i)$.

In this situation, we say that $X$ is obtained from $W$.

A $\Lambda^\infty$-set is a finite union of basic $\Lambda^\infty$-sets. We let $\RR\left(\Lambda^\infty\right)$ be the expansion of the real field by all $\Lambda^\infty$-sets.

Lemma 1

  1. Let $X \subseteq \RR^n$ be a basic $\Lambda^\infty$-set obtained from $W \subseteq \RR^{k+n+l}$, and let $m \le n$. Then $\Pi_m(X)$ is a basic $\Lambda^\infty$-set obtained from $W$.
  2. Every $\Lambda$-set is a $\Lambda^\infty$-set.

Proof. For part 1, let $W$, $X(i,j)$ and $X(i)$ be as in the above definition. Since each $X(i,j)$ is bounded, we have $$\cl\left(\Pi_mW_{z(i,j)}\right) = \Pi_m\left(\cl X(i,j)\right).$$ Also, for a convergent sequence $(A_i)$ in $\K_n$, we have $$\lim_i (\Pi_m A_i) = \Pi_m(\lim_i A_i).$$ Since projection also commutes with taking unions, part 1 follows.

For part 2, let $W \subseteq \RR^n$ be a $\Lambda$-set; by $(\Lambda 5)$ and part 1, we may assume that $W$ is closed. Now set $$V:= \set{(t,x) \in \RR^{1+n}:\ x \in W \text{ and } |x| \le t}.$$ Then $V$ is a $\Lambda$-set, each fiber $V_t$ is compact, and $W = \bigcup_{i \in \NN} V_i$. $\qed$

In view of part 2 of this lemma, it suffices to show that $\RR\left(\Lambda^\infty\right)$ is o-minimal.

Let $W \in \Lambda_n$. Then there exists $N \in \NN$ such that every basic $\Lambda^\infty$-set obtained from $W$ has at most $N$ connected components.

Proof. For $m \le n$, let $N_m \in \NN$ be obtained for $W$ by $(\Lambda 6)$, and set $N:= \max\{N_1, \dots, N_n\}$; we claim that this $N$ works.

By the exercise in this post, every set $X(i)$ obtained from $W$ as in the above definition has at most $N$ connected components.

Finally, if $X(i) \subseteq \RR^m$, for $i \in \NN$, is such that $X(1) \subseteq X(2) \subseteq \cdots$ and each $X(i)$ has at most $N$ connected components, then $\bigcup X(i)$ has at most $N$ connected components. $\qed$

In view of this proposition, the o-minimality of $\RR\left(\Lambda^\infty\right)$ follows once we show that the collection of all $\Lambda^\infty$-sets forms a first-order structure; that is, once we show that it is closed under finite intersections, finite unions, complements, projections and cartesian products.

Exercise 12
Show that the collection of all $\Lambda^\infty$-sets if closed under finite unions, projections, cartesian products and permutations of coordinates.

So it remains to show that the collection of all $\Lambda^\infty$-sets is closed under taking finite intersections and complements. Both are tricky; we deal here with intersections and leave complements for the next post.

For finite intersections, let us fix a $\Lambda$-set $W \subseteq \RR^{k+n+l}$ and a closed semialgebraic set $C \subseteq \RR^n$. We define the $\Lambda$-set $$V:= \set{(z,t,x,y) \in \RR^{k+1+n+l}:\ (z,x,y) \in W \text{ and } d(x,C) < t}.$$ Note that $$\tag{i} \Pi_n V_{z,t} = \Pi_nW_z \cap T(C,t)$$ for $z \in \RR^k$ and $t \in \RR$, and that $$\tag{ii} C = \bigcap_{t >0} T(C,t),$$ because $C$ is closed.

Lemma 2
Let $z(i) \in \RR^k$, for $i \in \NN$, and a compact set $Z \subseteq \RR^n$ be such that $\lim_i \Pi_nW_{z(i)} = Z$. Then there exist $t(j) > 0$ and $i(j) \in \NN$ such that $t(j) \to 0$, $i(j) \to \infty$ and $$Z \cap C = \lim_j \Pi_n V_{z(i(j)),t(j)}.$$

Show proof
Proof. Note first that $$\tag{I} Z \cap C = \bigcap_{t\gt 0} (Z \cap T(C,t)) = \lim_{t \to 0^+} (Z \cap T(C,t)).$$

By (i) and since $\lim_i \Pi_n W_{z(i)} = Z$ there exists, for $t\gt 0$, a Hausdorff limit $Z_t$ of the sequence $\left(\Pi_n V_{z(i),t}\right)_i$. Since $T(C,t)$ is an open set, it follows from the definition of $V$ that $$\tag{II} Z_t \cap T(C,t) = Z \cap T(C,t).$$ Now choose a decreasing sequence $t(j)\gt 0$ such that $t(j) \to 0$ and, for each $j$, choose $i(j) \in \NN$ such that $$\tag{III} d\left(\Pi_n V_{z(i(j)),t(j)}, Z_{t(j)}\right) \lt t(j).$$ Passing to a subsequence if necessary, we may assume that both $\lim_j Z_{t(j)}$ and $\lim_j \Pi_n V_{z(i(j)),t(j)}$ exist; it follows from (III) that $$\tag{IV} Y:= \lim_j Z_{t(j)} = \lim_j \Pi_n V_{z(i(j)),t(j)}.$$ We now prove that $Z \cap C = Y$, which then proves the lemma.

From (i) and (ii), we get $Y \subseteq Z \cap C$.

For the converse inclusion, we have $$Z \cap C = \lim_j (Z \cap T(C,t(j))) \quad\text{by (I)}$$ $$= \lim_j \left(Z_{t(j)} \cap T(C,t(j))\right) \quad\text{by (II)}$$ $$\subseteq \lim_j Z_{t(j)} = Y \quad\text{by (IV)},$$ as required. $\qed$

Let $X, Y \subseteq \RR^n$ be $\Lambda^\infty$-sets. Then $X \cap Y$ is a $\Lambda^\infty$-set.

Proof. Since $X \cap Y = \Pi_n((X \times Y) \cap \Delta)$, where $\Delta:= \set{(x,y):\ x=y}$, we may assume by Exercise 12 that $Y$ is a closed semialgebraic set.

Let $W \subseteq \RR^{k+n+l}$ be a $\Lambda$-set, $z(i,j) \in \RR^k$ and $X(i,j):= \Pi_nW_{z(i,j)}$ for $i,j \in \NN$, $X(i) \subseteq \RR^{n}$ be compact such that $X(1) \subseteq X(2) \subseteq \cdots$, and assume that $\lim_j X(i,j) = X(i)$ for each $i$ and $X = \bigcup_i X(i)$. Let $V$ be defined for $W$ as above and, for $i,j \in \NN$ and $t\gt 0$, we set $$X'(i,j,t):= \Pi_nV_{z(i,j),t}.$$ By Lemma 2, for each $i$ and $p \in \NN$, there exist $t(i,p)\gt 0$ and $j(i,p) \in \NN$ such that $\lim_p t(i,p) = 0$, $\lim_p j(i,p) = \infty$ and $$X(i) \cap Y = \lim_p X'(i,j(i,p)),t(i,p)).$$ But the sequence of sets $X(i) \cap Y$ is increasing with union $X \cap Y$, so $X \cap Y$ is a $\Lambda^\infty$-set obtained from $V$, as required. $\qed$

By the corollary, it now suffices to show that the collection of all $\Lambda^\infty$-sets is closed under taking complements.

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.