First theorem of the complement

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

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

We assume the following axioms for $\Sigma$:

$(\Sigma 1)$

all semialgebraic sets are $\Sigma$-sets;

$(\Sigma 2)$

$\Sigma$ is closed under taking finite unions, finite intersections, projections and cartesian products;

$(\Sigma 3)$

if $A \in \Sigma_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;

$(\Sigma 4)$

if $A \in \Sigma_n$ is bounded, then $\cl(A) \in \Sigma_n$ and there exists a sparse, closed $B \in \Sigma_n$ such that $\bd(A) \subseteq B$.

Examples

1. Let $\R$ be an o-minimal expansion of the real field, and let $\Sigma_n$ be the collection of all definable subsets of $\RR^n$. Then $\Sigma = (\Sigma_n)_{n \in \NN}$ satisfies Axioms $(\Sigma 1)$–$(\Sigma 4)$.
2. At this point, our main example of such a system is $\Sigma = (\Sigma_n)_{n \in \NN}$, where $\Sigma_n$ is the collection of all $\Lambda^\infty$-subsets of $\RR^n$ obtained from the $\Lambda$-sets. In this case, Axioms $(\Sigma 1)$–$(\Sigma 4)$ hold for $\Sigma$.

Our goal here is to prove the

First theorem of the complement
The complement of a $\Sigma$-set is a $\Sigma$-set.

Assuming the theorem of the complement, it follows that:

Corollary
Every set definable in $\RR(\Sigma)$ is a $\Sigma$-set; in particular, the structure $\RR(\Sigma)$ is o-minimal. $\qed$

In view of Example 2 above, the corollary in turn finishes the proof of this theorem as well.

Before proving the theorem of the complement, we need a few observations. For $n \in \NN$, we let $\tau_n:\RR^n \into (-1,1)^n$ be the semialgebraic diffeomorphism defined by $$\tau_n(x_1, \dots, x_n):= \left(\frac{x_1}{\sqrt{1+x_1^2}}, \dots, \frac{x_n}{\sqrt{1+x_n^2}}\right).$$

Exercises

1. Show that the system $\Sigma$ is closed under permutation of coordinates.
2. Let $A \subseteq \RR^n$. Show that $A \in \Sigma_n$ if and only if $\tau_n(A) \in \Sigma_n$.
3. Show that every sparse $\Sigma$-set is nowhere dense.

Fiber Lemma
Let $A \subseteq \RR^n$ be a bounded $\Sigma$-set and $m \le n$. Then the set $$S:= \set{a \in \RR^m:\ \cl\left(A_a\right) \ne \cl(A)_a}$$ is sparse.

Proof. It suffices to show that the lemma holds with $$A \cap \big((-R,R)^m \times \RR^{n-m}\big)$$ in place of $A$, for each $R>0$; so we assume that $\Pi_m(A)$ is bounded. For each $a \in S$ there is an open box $U \subseteq \RR^{n-m}$ such that $\cl(A_a) \cap U = \emptyset$, but $\cl(A)_a \cap U \neq \emptyset$. Hence $S = \bigcup_U S_U$, where $U$ ranges over all open boxes in $\RR^{n-m}$ with rational vertices and $$S_U:= \set{a \in \RR^m:\ \cl(A_a) \cap U = \emptyset,\ \cl(A)_a \cap U \neq \emptyset}.$$ Each $S_U$ is contained in the frontier, hence the boundary, of the bounded $\Sigma$-set $\Pi_m\left(A \cap \left(\RR^m \times U\right)\right)$. So by $(\Sigma 4)$, we have $S_U \subseteq Y_U$ for some sparse, compact $\Sigma$-set $Y_U$. Since any countable union of sparse compact sets is sparse, it follows that $S$ is sparse. $\qed$

We set $I:= [-1,1]$. A set $C \subseteq I^n$ is a $\Sigma$-cylinder if $D:= \Pi_{n-1}(C)$ is a $\Sigma$-set and there are continuous $f,g:D \into I$ such that $f(x) \lt g(x)$ for $x \in D$, the graphs $\gr(f)$ and $\gr(g)$ are $\Sigma$-sets and $$C = \set{(x,y):\ f(x) \lt y \lt g(x)}.$$

Proof of the theorem of the complement.
Let $A \subseteq \RR^n$ be a $\Sigma$-set. By the exercises above, we may assume $A \subseteq I^n$ and show that $I^n \setminus A$ is a $\Sigma$-set.

In this situation, we establish the following two statements by induction on $n$ (see also Lion and Rolin’s paper):

(I)$_n$

If $A$ is sparse, then $A$ can be partitioned into finitely many $\Sigma$-sets $G_1, \dots, G_k$ such that, for $i =1, \dots, k$, there is a permutation $\pi_i$ of coordinates such that $\pi_i(G_i)$ is the graph of a continuous function $f_i:\Pi_{n-1}(\pi_i(G_i)) \into \RR$.

(II)$_n$

The complement $I^n \setminus A$ is a $\Sigma$-set, and each component of $A$ and of $I^n \setminus A$ is a $\Sigma$-set.

Here we interpret (I)$_1$ as stating that “if $A$ is sparse, then $A$ is finite”. Thus, the case $n=1$ follows from $(\Sigma 3)$, so we assume $n>1$ and that both (I)$_m$ and (II)$_m$ hold for $m \lt n$. We first show the following:

Claim
Assume there is a sparse $\Sigma$-set $B \subseteq I^n$ such that $A \subseteq B$ and (I)$_n$ and (II)$_n$ hold with $B$ in place of $A$. Then (I)$_n$ and (II)$_n$ hold.

We now distinguish two cases.

Case 1: $A$ is sparse. Consider the $\Sigma$-sets $$C_i:= \set{a \in I^{n-1}:\ |A_a| \geq i}$$ for $i \in \NN$; by (II)$_{n-1}$, the sets $$D_i:= C_i \setminus C_{i+1} = \set{a \in I^{n-1}:\ |A_a| = i}$$ are also $\Sigma$-sets. By $(\Sigma 3)$, there is an $N \in \NN$ such that $C_i = C_{N+1}$ for $i \gt N$. We set $$A_1:= A \cap ((C_0 \setminus C_{N+1}) \times I)$$ and $$A_2:= A \cap (C_{N+1} \times I);$$ by the inductive hypothesis, both $A_1$ and $A_2$ are $\Sigma$-sets.

To deal with $A_1$, we decompose $(C_0 \setminus C_{N+1}) \times I)$ into finitely many $\Sigma$-cylinders compatible with $A_1$. Note that $\left|(A_1)_a\right| \leq N$ for $a \in \Pi_{n-1}(A_1)$. For $1 \leq j \leq i \leq N$, we define the $\Sigma$-sets $$A_{i,j} := \set{(a,y) \in D_i \times I:\ y \text{ is the } j^{\text{th}} \text{ element of } (A_1)_a},$$ $$S_{i,j} := \set{a \in D_i:\ \left|(\cl(A_{i,j}))_a\right| \geq 2},$$ and we put $$S:= \bigcup_{1 \leq j \leq i \leq N} S_{i,j}.$$ Note that, by $(\Sigma 4)$, each $S_{i,j}$ is a $\Sigma$-set and $$S_{i,j} \subseteq \set{a \in \RR^{n-1}:\ \cl\left((A_{i,j})_a\right) \ne \left(\cl(A_{i,j})\right)_a};$$ therefore, by the above fiber lemma, $S$ is a sparse $\Sigma$-set.

Now note that each $A_{i,j}$ is, by construction, the graph of a function on $D_i$ that is continuous away from $T$, that is, the set $(D_i \setminus T) \times I)$ is a finite union of $\Sigma$-cylinders compatible with $A_1$. Thus, (I)$_n$ and (II)$_n$ hold with $A_1 \setminus (T \times I)$ in place of $A$.

On the other hand, by the inductive hypothesis and because $T$ is sparse, (I)$_{n-1}$ and (II)$_{n-1}$ hold with $T$ in place of $A$, so that (I)$_n$ and (II)$_n$ hold with $T \times I$ in place of $A$. Claim 1 now implies that (I)$_n$ and (II)$_n$ also hold with $A_1 \cap (T \times I)$ in place of $A$, and with $(T \times I) \setminus A_1$ in place of $A$.

Therefore, (I)$_n$ and (II)$_n$ hold with $A_1$ in place of $A$ and with $((C_0 \setminus C_{N+1}) \times I) \setminus A_1$ in place of $A$.

To deal with $A_2$, note that $C_{N+1} = \Pi_{n-1}(A_2)$. Thus, every fiber $(A_2)_a \subseteq I$ with $a \in C_{N+1}$ is infinite and hence (by $(\Sigma 3)$) contains an interval. Since $A_2$ is sparse, it follows from Exercise 3 above that $C_{N+1}$ is sparse. (I)$_n$ and (II)$_n$, with $A_2$ as well as with $(C_{N+1} \times I) \setminus A_2$ in place of $A$, now follow from Claim 1 by a similar argument as used to deal with $A_1$.

Case 2: $A$ is not sparse. By $(\Sigma 4)$, there is a closed, sparse $\Sigma$-set $B \subseteq I^n$ such that $\bd(A) \subseteq B$. By Case 1 applied to $B$, both (I)$_n$ and (II)$_n$ hold with $B$ in place of $A$.

Note that if $C$ is a connected component of $I^n \setminus B$ and $C \cap A \neq \emptyset$, then $C \subseteq A$. It follows that each connected component of $I^n \setminus B$ is either contained in $A \setminus B$ or is disjoint from $A \cup B$.

On the other hand, by Claim 1, the statements (I)$_n$ and (II)$_n$ hold with $A \cap B$ in place of $A$. Statement (II)$_n$ now follows. $\qed$