Let $\M$ be an o-minimal expansion of a dense linear order $(M,\lt)$, and let $n \in \NN$.

We now prove the cell decomposition theorem by induction on $n$, assuming that $n \ge 2$ and that (I)$_{n-1}$ and (II)$_{n-1}$ hold.

**Proof of (I)$_n$.** As in the proof of the decomposition theorem for planar sets, we may assume that each $S_i$ is sparse and that the $S_i$-s are pairwise disjoint. For each $i$, let $\C_i$ be a cell decomposition of $M^{n-1}$ obtained from the uniform finiteness lemma with $S_i$ in place of $S$. By (I)$_{n-1}$, there is a cell decomposition $\D$ of $M^{n-1}$ that is a refinement of each $\C_i$. Since the $S_i$-s are pairwise disjoint, for each open $C \in \D$, we now obtain a cell decomposition $\D_C$ of $C \times M$, as in the proof of the decomposition theorem for planar sets, that is compatible with each $S_i$.

On the other hand, let $C \in \D$ be such that $C$ is not open, so that $C$ is a $\sigma$-cell for some $\sigma \in \{0,1\}^{n-1}$ with $\sigma(j) = 0$ for some $j$. Denote by $$\Pi_\sigma:M^n \into M^{\sum\sigma+1}$$ the projection $$\Pi_\sigma(x_1, \dots, x_n):= (\pi_\sigma(x_1, \dots, x_n),x_n).$$ By the inductive hypothesis, there is a cell decomposition $\D’_C$ of $C^\sigma \times M$ compatible with each $\Pi_\sigma(S_i \cap (C \times M))$. Now set $$\D_C:= \set{\Pi_\sigma^{-1}(D’) \cap (C \times M):\ D’ \in \D’_C};$$ then $\D_C$ is a cell decomposition of $C \times M$ compatible with each $S_i$. Finally, we take $\C:= \bigcup \{\D_C:\ C \in \D\}$. $\qed$

For $S \subseteq M^n$ and $y \in M$, we set $$S^y:= \set{x \in M^{n-1}:\ (x,y) \in S},$$ and we denote by $\Pi^1:M^n \into M$ the projection on the last coordinate. For a function $f:S \into M$, with $S \subseteq M^n$, and for $x \in \Pi_{n-1}(S)$ and $y \in \Pi^1(S)$, we define $f_x:S_x \into M$ and $f^y:S^y \into M$ by $$f_x(y):= f(x,y)$$ and $$f^y(x):= f(x,y).$$

The key to proving (II)$_n$ is the following

**Exercise 5**

Let $U \subseteq M^n$ be open, $I \subseteq M$ be an open interval and $f:U \times I \into M$ be such that

- for each $x \in U$, the function $f_x$ is continuous and strictly monotone;
- for each $y \in I$, the function $f^y$ is continuous.

Prove that $f$ is continuous.

**Proof of (II)$_n$.** By (I)$_n$, there is a cell decomposition $\C$ of $M^n$ compatible with both $S$ and the definable set $$T:= \big\{(x,y) \in S:\ f_x \text{ is continuous and strictly monotone at } y,$$ $$\text{and } f^y \text{ is continuous at } x\big\}.$$ If $C \in \C$ is open, then $f \rest{C}$ is continuous by Exercise 5. If $C \in \C$ is not open we obtain, along the lines of the proof of (I)$_n$, a cell decomposition $\D_C$ of $C$ such that $f \rest{D}$ is continuous for each $D \in \D_C$. $\qed$

**Corollary**

*Let $S \subseteq M^n$ be definable.*

*$S$ has finitely many definably connected components, and each of them is definable.**If $m \le n$, there exists $k \in \NN$ such that $S_x$ has at most $k$ definably connected components, for each $x \in M^m$.**If $m \le n$, the set $\{x \in M^m:\ S_x$ is finite$\}$ is definable.**If $\N \equiv \M$, then $\N$ is o-minimal.*

The proof of this corollary is left as an exercise.