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

Our goal is to prove the

**Cell Decomposition Theorem**

(Knight, Pillay and Steinhorn)

- (I)$_n$
*Let $S_1, \dots, S_k \subseteq M^n$ be definable. Then there exists a cell decomposition $\C$ of $M^n$ compatible with each $S_i$.*- (II)$_n$
*Let $f:S \into M$ be definable, with $S \subseteq M^n$. Then there exists a cell decomposition $\C$ of $M^n$ compatible with $S$ such that, for each $C \in \C$, the restriction of $f$ to $C$ is continuous.*

The proof of the cell decomposition theorem proceeds by induction on $n$, mimicking the proof in the case $n=2$. (I)$_1$ is of course just the definition of o-minimality, and we proved (II)$_1$ in the form of the Monotonicity Theorem. So we assume $n \ge 2$ and that the cell decomposition theorem holds for lower values of $n$.

**Exercise**

Let $S \subseteq M^n$ be definable, and assume (I)$_{n-1}$ and (II)$_{n-1}$. Show that $S$ is sparse if and only if the set $S’$ of all $x \in M^{n-1}$ such that $S_x$ is infinite is sparse.

**Uniform finiteness lemma**

*Let $S \subseteq M^n$ be definable and sparse, and assume (I)$_{n-1}$ and (II)$_{n-1}$. Then there exist a cell decomposition $\C$ of $M^{n-1}$ such that, for each open $C \in \C$, the cardinality $\left|S_x\right|$ is constant for $x \in C$.*

**Proof.** The proof of uniform finiteness for sparse subsets of the plane goes through with the corresponding modifications, such as using “sparse” in place of “finite”, “open cell in $M^{n-1}$” in place of “open interval” and “not sparse” in place of “infinite”, and using (I)$_{n-1}$ in place of the o-minimality axiom and (II)$_{n-1}$ in place of the Monotonicity Theorem. $\qed$

The proof of the cell decomposition theorem is in the next post.