The Cell Decomposition Theorem might be called the “Fundamental Theorem of O-minimality”. With this theorem we show that from the hypothesis that the definable sets in one variable are particularly simply, i.e. those which admit a quantifier-free definition in the reduct to the language of ordered sets with parameters, it follows that the higher dimensionsal sets are also tame.
As is our wont, we work in a fixed o-minimal structure $\mathfrak{R}$. The proof of the Cell Decomposition Theorem is easier under the hypothesis that the theory of $\mathfrak{R}$ is o-minimal, that is, that every structure elementarily equivalent to $\mathfrak{R}$ is o-minimal, but as we will use this theorem to show that it follows that if a structure is o-minimal so is its theory, we will not allow ourselves this extra assumption.
Let us define the cells in $R^n$ by recursion on $n$.
For $n = 0$, the single point $R^0$ itself is a cell. Given a cell $X \subseteq R^n$ and a definable continuous function $f:X \to R$, the graph $$\Gamma_X(f) := \{ (x_1, \ldots, x_{n+1}) \in R^{n+1} : (x_1, \ldots, x_n) \in X ~\&~ f(x_1, \ldots, x_n) = x_{n+1} \}$$ is a cell in $R^{n+1}$. If $g:X \to R$ is another definable continuous function, for which $f(x) < g(x)$ for all $x \in X$, then the parameterized interval $$(f,g)_X := \{ (x_1, \ldots, x_{n+1}) \in R^{n+1} : (x_1, \ldots, x_n) \in X ~\&~ f(x_1, \ldots, x_n) < x_{n+1} < g(x_1,\ldots,x_n) \}$$ is a cell in $R^{n+1}$. The infinite parameterized intervals $$(-\infty,g)_X := \{ (x_1, \ldots, x_{n+1}) \in R^{n+1} : (x_1, \ldots, x_n) \in X ~\&~ x_{n+1} < g(x_1,\ldots,x_n) \}$$
$$(-\infty,g)_X := \{ (x_1, \ldots, x_{n+1}) \in R^{n+1} : (x_1, \ldots, x_n) \in X ~\&~ x_{n+1} < g(x_1,\ldots,x_n) \}$$
$$(f,\infty)_X := \{ (x_1, \ldots, x_{n+1}) \in R^{n+1} : (x_1, \ldots, x_n) \in X ~\&~ f(x_1,\ldots,x_n) < x_{n+1} \}$$
and
$$(-\infty,\infty)_X := X \times R$$
are all cells in $R^{n+1}$.
The cells are precisely the sets obtained via this process.
We may now state the Cell Decomposition Theorem.
Cell Decomposition Theorem: For any natural number $n$ and finite list $X_1, \ldots, X_m$ of definable subsets of $R^n$ there is a finite set $\mathcal{C}$ of cells in $R^n$ so that $\mathcal{C}$ partitions $R^n$ and for each $i \leq m$ there is a subset $\mathcal{C}_i \subseteq \mathcal{C}$ so that $X_i = \bigcup \mathcal{C}_i$.
The set $\mathcal{C}$ is called a cell decomposition of $R^n$ and we say that it is subjacent to $X_1, \ldots, X_n$.
We prove the Cell Decomposition Theorem in tandem with a theorem on the piecewise continuity of definable functions.
Piecewise Continuity Theorem: If $f:R^n \to R$ is a definable function, then it is piecewise continuous in the sense that there is a cell decomposition $\mathcal{C}$ of $R^n$ so that for each $C \in \mathcal{C}$ the function $f \upharpoonright C:C \to R$ is continuous.
A continuous definable function $f:R^0 \to R^1$ is given by the value $a$ of $f$ on the unique element of $R^0$. Thus, a cell of the form $\Gamma_{R^0}(f)$ is simply the singleton $\{ a \}$ and if $g:R^0 \to R^1$ takes the value $b$ 0n the unique element of $R^0$, then $(f,g)_{R^0} = (a,b)$, $(-\infty,g)_{R^0} = (-\infty,b)$, $(f,\infty)_{R^0} = (a,\infty)$, and $(-\infty,\infty)_{R^0} = (-\infty,\infty)$. That is, the cells in $R^1$ are just the points and intervals. Thus, the Cell Decomposition Theorem for $n = 0$ is trivial and for $n=1$ it is precisely the statement that $\mathfrak{R}$ is o-minimal. Likewise, the Piecewise Continuity Theorem is trivial for $n = 0$ and is contained in the Monotonicity Theorem for $n = 1$.
We will prove the Cell Decomposition Theorem and the Piecewise Continuity Theorem by simultaneous induction on $n$. As we have noted, we have already dealt with the cases of $n \leq 1$. We shall show that if Cell Decomposition and Piecewise Continuity hold for $n$, then Cell Decomposition holds for $n+1$ and that if Cell Decomposition holds for $n+1$ and Piecewise Continuity holds for $n$, then Piecewise Continuity holds for $n+1$. To be totally honest, we require a third theorem which should also be proven during the same induction.
Uniform Finiteness Theorem: If $Y \subseteq R^{n + 1}$ is a definable set such that for every $a \in R^n$ the fiber $Y_a$ is finite, then there is a number $N = N(Y)$ so that for all $a \in R^n$ the size of $Y_a$ is at most $N$.
We delay the proof of the Uniform Finiteness Theorem to another post. If one assumes that the theory of $\mathfrak{R}$ is o-minimal, then the Uniform Finiteness Theorem may be deduced by compactness using the observation that in an o-minimal structure the condition that the definable set $X \subseteq R$ is infinite may be expressed by $(\exists a)(\exists b)[a < b ~\&~ (\forall t) (a < t < b \to t \in X)]$.
Inductive case for Cell Decomposition: We assume that Cell Decomposition, Piecwise Continuity, and Uniform Finiteness all hold for $n$. Let $X_1, \ldots, X_m \subseteq R^{n+1}$ be a finite list of definable subsets of $R^{n+1}$. By o-minimality and uniform finiteness, there is some number $N$ so that for all $x \in R^n$ the boundaries of each of $(X_1)_x, \ldots, (X_m)_x$ have size at most $N$. Define (partial) functions $\gamma_{i,j}:R^n \dashrightarrow R$ by $\gamma_{i,j}(x)$ is the $j^\text{th}$ element of $\partial (X_i)_x$ if $\partial (X_i)_x$ has at least $j$ elements, and is undefined otherwise.
For a point $x \in R^n$ we define its combinatorial datum to be
- the $m$-tuple of numbers $\langle \# \partial(Y_1)_x, \ldots, \# \partial(Y_m)_x \rangle$,
- the $m$-tuple of functions $\chi_i:\{ 1, \ldots, \# \partial(Y_i)_x \} \to 2$ given by $\chi_i(j) = 1$ if $\gamma_{i,j}(x) \in (Y_i)_x$ and $\chi_i(j) = 0$ if $\gamma_{i,j}(x) \notin (Y_i)_x$, and
- the $m$-tuple of functions $\xi_i:\{0,\ldots,\# \partial(Y_i)_x \} \to 2$ given by $\xi_i(j) = 1$ if $(\gamma_{i,j}(x),\gamma_{i,j+1}(x)) \cap (Y_i)_x \neq \varnothing$ and $0$ otherwise. Here we define $\gamma_{i,0} \equiv -\infty$ and $\gamma_{i,\# (Y_i)_x + 1} \equiv \infty$.
There is a finite set of such possible combinatorial data given that the first tuple lies in $\{0, \ldots, N \}^m$. For each such combinatorial datum $\Delta$ let $D_\Delta := \{ x \in R^n ~:~ $ the combinatorial datum of $x$ is $\Delta \}$.
By Cell Decomposition and Piecewise Continuity in $R^n$, we may find a cell decomposition $\mathcal{C}$ of $R^n$ so that
- each $f_{i,j}$ is continuous (or not defined at all) on each $C \in \mathcal{C}$,
- for each pair of pairs $(i,j)$ and $(i’,j’)$ one of the three conditions $f_{i,j} < f_{i’,j’}$, $f_{i,j} = f_{i’,j’}$, or $f_{i,j} > f_{i’,j’}$ holds everywhere on $C$, and
- the cell decomposition is subjacent to the $D_\Delta$.
We now define a cell decompostion $\mathcal{C}$ of $R^{n+1}$. For each $C \in \mathcal{C}$ by Condition 2, the finitely many $f_{i,j}$ which are defined on $C$ ar linearly ordered. List these a $g_{C,1} < g_{C,2} < \cdots < g_{C,\ell(C)}$. Note that it is possible that $\ell(C) = 0$. Let us extend this list by formally defining $g_{C,0} :\equiv -\infty$ and $g_{C,\ell(C)+1} :\equiv \infty$. In $\widetilde{C}$ we have the cells $\Gamma_C(g_{C,j})$ for $1 \leq j \leq \ell(C)$ and $(g_{C,j},g_{C,j+1})_C$ for $0 \leq j \leq \ell(C)$.
By Condition 1, each of these is a cell. By construction, these cells are disjoint and partition $R^{n+1}$. By Condition 3, this cell decomposition is subjacent to $Y_1, \ldots, Y_m$. $\Box$
Now we handle the inductive case for Pieceeise Continuity. Here, we allow ourselves Piecewise Continuity for $n$ and Cell Decompostion for $n+1$.
Proof of Inductive Case $n+1$ of Piecewise Continuity: Consider the definable function $f:R^{n+1} \to R$. By Cell Decompostion in $R^{n+1}$, we may find a cell decomposition $\mathcal{C}$ of $R^{n+1}$ subjacent to
- $\{ (x_1, \ldots, x_{n+1}) \in R^{n+1} : t \to f(x_1,\ldots,x_n,t) $ is continuous at $ x_{n+1} \}$,
- $\{ (x_1, \ldots, x_{n+1}) \in R^{n+1} : t \to f(x_1,\ldots,x_n,t) $ is constant near $ x_{n+1} \}$,
- $\{ (x_1, \ldots, x_{n+1}) \in R^{n+1} : t \to f(x_1,\ldots,x_n,t) $ is strictly increasing near $ x_{n+1} \}$,
- $\{ (x_1, \ldots, x_{n+1}) \in R^{n+1} : t \to f(x_1,\ldots,x_n,t) $ is strictly decreasing near $ x_{n+1} \}$, and
- $\{ (x_1, \ldots, x_{n+1}) \in R^{n+1} : \langle u_1, \ldots, u_n \rangle \to f(x_1,\ldots,x_n,t) $ is continuous at $ \langle x_1, \ldots, x_n \rangle \}$.
If $C \in \mathcal{C}$ is a non-open cell, then we have seen that there is a coordinate projection $\varpi:R^{n+1} \to R^n$ which restricts to a definable homeomorphism between $C$ and the cell $\varpi(C) \subseteq R^{n}$. By Piecewisewise continuity in $R^n$ we can express $\varpi(C)$ as a disjoint union of cells so that on each one $f \circ (\varpi \upharpoonright C)^{-1}$ is continuous. That is, $f$ is constinuous on each of the $(\varpi \upharpoonright C)^{-1} C’$ as $C’$ ranges through this cell decomposition. Thus, it suffices to show for each open $C \in \mathcal{C}$ that $f$ restricts to a continuous function. Let us fix such a cell $C$ and write it as $C = (g,h)_{C’}$ where $C’ \subseteq R^n$ is an open cell and $g$ and $h$ are continuous definable functions on $C’$ (possibly $\equiv -\infty$ or $\infty$ with $g < h$ on $C’$.
Claim: $C$ is contained in the sets of clauses 1 and 5 and one of the sets in clauses 2, 3, and 4.
Proof of Claim: Let $\langle x_1, \ldots, x_{n+1} \rangle \in C$. By the Monotonicity Theorem, the function $t \mapsto f(x_1,\ldots,x_n,t)$ is piecewise continuous and constant or striclty monotone on the interval $(g(x_1,\ldots,x_n),h(x_1,\ldots,x_n))$. In particular, there are only finitely many $t \in (g(x_1,\ldots,x_n),h(x_1,\ldots,x_n))$ at which this function is discontinuous and not locally constant or locally monotone. Let $s$ be one of the other points. Then $\langle x_1, \ldots, x_n, s \rangle$ lies in $C$ and the set of Clause 1 (so that by subjacency $C$ is contained in that set) and also one of the sets of Clauses 2, 3, or 4 (giving again the claimed inclusion).
By Piecewise Continuity in $R^n$, the function $\langle u_1, \ldots, u_n \rangle \mapsto f(u_1, \ldots, u_n, x_{n+1})$ is piecewise continuous, which implies in particular that it is continuous on a dense open subset of $\{ \langle u_1, \ldots, u_n \rangle \in C’ : g(u_1, \ldots, u_n) < x_{n+1} < h(u_1,\ldots,u_n,x_{n+1}) \}$. Let $\langle u_1, \ldots, u_n \rangle$ be one such point. Then $\langle u_1, \ldots, u_n, x_{n+1} \rangle \in C$ and also in the set of Clause 5, once again giving the claimed inclusion. $\maltese$
There are three cases to consider depending on whether Clause 2, 3, or 4 holds on $C$. We will write a proof that handles the cases of Clause 2 and 3 simultaneously. The case of Clause 4 is handled by reversing the inequalities.
Consider a point $\langle a_1, \ldots, a_n, a_{n+1} \rangle \in C$. Let $\epsilon_1 < f(a_1,\ldots,a_n,a_{n+1}) < \epsilon_2$. By continuity and (not necessarily strict) increasingness of $t \mapsto f(a_1,\ldots,a_n,t)$, there are $g(a_1,\ldots,a_n) < b < a_{n+1} < c < h(a_1,\ldots,a_n)$ for which $\epsilon_1 < f(a_1,\ldots,a_n,b) \leq f(a_1,\ldots,a_n,a_{n+1}) \leq f(a_1,\ldots,a_n,c) < \epsilon_2$. By continuity of $f$, $g$, $\langle u_1, \ldots, u_n \rangle \mapsto f(u_1,\ldots,u_n,b)$, and $\langle u_1, \ldots, u_n \rangle \mapsto f(u_1,\ldots,u_n,c)$, we can find an open neighborhood $U \ni \langle a_1, \ldots, a_n \rangle$ contained in $C’$ (here we use the fact that $C’$ is open) so that
- $g(u_1,\ldots,u_n) < b < c < h(u_1,\ldots,u_n)$ for $\langle u_1, \ldots, u_n \rangle \in U$,
- $f(u_1,\ldots,u_n,b) > \epsilon_1$ for $\langle u_1, \ldots, u_n \rangle \in U$, and
- $g(u_1,\ldots,u_n,c) < \epsilon_2$ for $\langle u_1, \ldots, u_n \rangle \in U$.
Consider $\langle u_1, \ldots, u_n, u_{n+1} \rangle \in U \times (b,c)$. Then $\epsilon_1 < f(u_1,\ldots,u_n,b) \leq f(u_1,\ldots,u_n,u_{n+1}) \leq f(u_1,\ldots,u_n,c) < \epsilon_2$. In this computation, we are using the fact that the entire cell $C$ is contained in the set of Clause 2 or 3 and that $U \times (b,c) \subseteq C$.
With these inequalities established we see that $f$ is continuous at $\langle a_1, \ldots, a_{n+1} \rangle$ and hence on all of $C$. With this we conclude. $\Box$