In our proof of the Cell Decomposition Theorem, we took as known the Uniform Finiteness Theorem. In this post, we fill that gap.
Uniform Finiteness Theorem: Let $Y \subseteq R^{n+1}$ be a definable set for which all fibers $Y_a := \{ y \in R : (a,y) \in R \}$ are finite as $a$ ranges through $R^n$. Then there is a number $N = N(Y)$ so that all fibers have size at most $N$.
Proposition: The Uniform Finiteness Theorem is equivalent to the assertion that $\operatorname{Th}(\mathfrak{R})$ is o-minimal.
Proof of Proposition: Suppose that $\operatorname{Th}(\mathfrak{R})$ is o-minimal and suppose that $Y \subseteq R^{n+1}$ is a definable set for which all fibers $Y_a := \{ y \in R : (a,y) \in R \}$ are finite as $a$ ranges through $R^n$. If there is no bound on the size of these fibers, then the following theory in the language of $\mathfrak{R}$ augmented by $n$-constant symbols $a = (a_1, \ldots, a_n)$ is consistent:
$$T := \operatorname{Th}(\mathfrak{R}) \cup \{ (\exists y_1) \ldots (\exists y_m) [y_1 < \ldots < y_m ~\&~ \bigwedge (a,y_i) \in Y ~\&~ (\forall b)(\forall c) (b < c \to (\exists t) [b < t < c ~\&~ (a,t) \notin Y ])] ~:~ m \in \mathbb{N} \}$$
If $(\mathfrak{R}^*,a) \models T$, then $\mathfrak{R}^* \equiv \mathfrak{R}$, the set $Y(\mathfrak{R}^*)_a$ is infinite, and $Y(\mathfrak{R}^*)_a$ does not contain an interval. Hence, $\mathfrak{R}^*$ is not o-minimal, contrary to our hypothesis that every model of $\operatorname{Th}(\mathfrak{R})$ is o-minimal.
In the other direction, let $\mathfrak{R}^* \equiv \mathfrak{R}$ be a structure elementarily equivalent to $\mathfrak{R}$. Let $X \subseteq R^*$ be an $R^*$-definable set in one variable. As such, $X = Z_a(\mathfrak{R}^*)$ for some $\varnothing$-definable subset $Z$ of $R^{n+1}$ and $a \in \mathfrak{R}^*$. Let $Y := \{ (x,y) \in R^n \times R : y \in \partial (Z_x) \} = \{ (x,y) \in R^n \times R : y \in (\exists \epsilon_1 < y < \epsilon_2) Y \cap (\epsilon_1,\epsilon_2) \neq \varnothing ~\&~ (R \smallsetminus Y) \cap (\epsilon_1,\epsilon_2) \neq \varnothing \}$. By the o-minimality of $R$, all of the fibers of $Y$ are finite, and, hence, by our assumption of size at most $N(Y)$. This assertion is part of $\operatorname{Th}(\mathfrak{R})$. Thus, $\# \partial (X) = \# \partial (Z_a(\mathfrak{R}^*)) = \# Y_a(\mathfrak{R}^*) \leq N(Y) < \infty$. It is also part of $\operatorname{Th}(\mathfrak{R})$ that for each $W \subseteq R^{m+1}$ that for every $x \in R^m$ and $y$ and $z$ from $R$, if $(x,y) \in W$ and $(x,z) \notin W$, then there is a point in $\partial(W_x)$ between $y$ and $z$. It follows that $X$ itself is the union of some of its (at most $N(Y)$) boundary points and some of the intervals between the boundary points (and $\pm \infty$). That is, $\mathfrak{R}^*$ is o-minimal. $\Box$
We will prove the Uniform Finiteness Theorem by induction on $n$. To be honest, we are actually proving Cell Decomposition, Uniform Finiteness, and Piecewise Continuity by induction on $n$. The case of $n \leq 1$ is trivial. When proving the inductive case of $n+1$, we will be assuming the inductive hypothesis that Cell Decomposition, Uniform Finiteness, and Piecewise Continuity all hold for all $m \leq n$.
Proof of Uniform Finiteness: Let $Y \subseteq R^{n+1}$ be a definable set so that for every $a \in R^n$ the fiber $Y_a$ is finite. Define $\mu:R^n \to R$ by $\mu(x) := \max Y_x$ (if $Y_x \neq \varnothing$) and $\mu(x)$ is undefined otherwise. Define for each positive integer $n$ the function $\gamma_n:R^n \to R$ by $\gamma_n(x) := $ the $n^\text{th}$ element of $Y_x$ (if $Y_x$ has at least $n$ elements) and $\gamma_n(x)$ is undefined if $Y_x$ has fewer than $n$ elements. Define $\delta_n(x) := $ the $n^\text{th}$ element from the top of $Y_x$ (so that $\delta_1 = \mu$), and, again, $\delta_n(x)$ is undefined if $\# Y_x < n$. By Piecewisewise Continuity and Cell Decomposition in dimension $n$, we may find a cell decomposition $\mathcal{C}$ of $R^n$ so that $\delta_1$, $\delta_2$, $\gamma_2$, and $\gamma_1$ are continuous (or not defined at all) on each cell $C \in \mathcal{C}$. By induction, for each non-open cell $C \in \mathcal{C}$ there is a bound $N = N(Y_C) < \infty$ on the size of $Y_a$ as $a$ ranges through $C$. It suffices to show that we can find such a bound for $Y_C$ when $C \in \mathcal{C}$ is open. Note that if $\gamma_1$ is not defined on $C$, then the bound is zero. Likewise, if $\gamma_1 = \mu$ on $C$, then the bound is one. So, we may restrict our attention to the case that $C$ open and $\gamma_1 < \mu$ on $C$.
For $a \in C$ define $m(a) := $ the maximal $m$ for which there is an open box $U \ni a$ so that $\gamma_i$ restricts to a continuous function on $U$ for $1 \leq i \leq m$. Note that $1 \leq m(a) \leq \#Y_a$. Let us note that because $\gamma_1$ and $\gamma_2$ are continuous on $C$, for all $x \in C$ we have $m(x) \geq 1$.
We say that a point $a \in C$ is good if $a \notin \overline{\operatorname{dom} \gamma_{m(a)+1}}$ and $a$ is bad if it is not good. On the face of it, it is not obvious that the set of good points is definable as our definition depends on the integer parameter $m(a)$. Let us prove definability by analyzing a related concept of normalcy.
We say that a point $(a,b) \in C \times R$ is normal if there is some open neighborbood $U \ni a$ and an open interval $I \ni b$ so that either $(U \times I) \cap Y = \varnothing$ or $(U \times I) \cap Y = \Gamma_U(g)$, the graph of a continuous function $g:U \to I$.
Define $\beta:C \to R$ by $x \mapsto \inf \{ y ~:~ (x,y) $ is not normal $\}$. Let us refine the cell decomposition so that on each cell either $\beta$ is undefined or $\beta$ is continuous.
Claim 1: $\beta(x) < \mu(x)$ (or $\beta(x)$ is not defined)
Proof of Claim 1: If $y > \mu(x)$, then by density we find $\mu(x) < \epsilon < y $ for some $\epsilon$. Using continuity of $\mu$, we may find $U \subseteq C$ so that $\mu(z) < \epsilon$ for all $z \in U$. Then $U \cap (\epsilon,\infty) \cap Y = \varnothing$. Thus, $\beta(x) \leq \mu(x)$. But, $(x,\mu(x))$ is also a normal point as $\mu$ and $\delta_2$ are continuous at $x$: taking $\delta_2(x) < \epsilon < \mu(x)$ we can find $U \ni x$ so that $(U \times (\epsilon,\infty)) \cap Y = \Gamma(\mu \upharpoonright U)$. Thus, $\beta(x) < \mu(x)$. $\maltese$
Claim 2 : $\beta(x) > \gamma_{m(x)}$
Proof of Claim 2: Let $U \subseteq C$ be a neighborhood of $x$ and $I_1, \ldots, I_{m(a)}$ be disjoint open intervals so that $(U \times I_j) \cap Y = \Gamma_U(\gamma_i \upharpoonright U)$ is the graph of a continuous function for $1 \leq i \leq m(x)$. If $y < \sup I_{m(x)}$, then $(x,y)$ is normal as either $y = \gamma_i(x)$ for some $i \leq m(x)$ and $U \times I_i$ witnesses normalcy, or $(x,y)$ belongs to one of these regions but does not lie on $Y$ which is closed in $(U \times (-\infty,\sup I_{m(x)})$ so that we may avoid it. $\maltese$
It follows form Claims 1 and 2 that if $\beta(x)$ is defined, then $\mu(x) > \gamma_{m(x)}$, which means in particular that $m(x) < \# Y_x$. That is, $x \in \operatorname{dom}(\gamma_{m(x)+1})$ so that $x$ is bad.
On the other hand, suppose that $x$ is bad. If $x \in \operatorname{dom}(\gamma_{m(x)+1})$, then $(x,\gamma_{m(x)+1}(x))$ is not normal by the definition of $m(x)$. If $x$ is not in the domain of $\gamma_{m(x)+1}$, then $\gamma_{m(x)}(x) = \mu(x)$. We have reduced to the case that $\mu$ is continuous on an open cell $C$ containgin $x$ and by definition of $m(x)$, there is an open neighborhood of $x$ (which we may assume to be contained insided $C$) and an interval $I$ so that $(U \times I) \cap Y$ is the graph of $\gamma_{m(x)+1} \upharpoonright U$, a continuous function. As $\mu \upharpoonright U$ is also continuous, for some $V \subseteq U$ a smaller neighborhood of $V$, we have $\Gamma(\mu \upharpoonright V) \subseteq (V \times I) \cap Y$. Hence, $\mu = \gamma_{m(x)}$ on $V$, which implies that $\gamma_{m(x)+1}$ is not defined on $V$. In particular, $x$ is not in the closure of the domain of $\gamma_{m(x)}$. That is, with our reductions, the only way for $x$ to be bad is for $x$ to lie in the domain of $\gamma_{m(x)+1}$.
All of this shows that $x$ is bad if and only if $\beta(x)$ is defined. Hence, the set of bad points is definable. We may now refine our cell decomposition so that it is subjacent to the bad points.
Claim 3: It is impossible for all points in one of our open cells to be bad.
Proof of Claim 3: Let $C$ be our open cell. Define $\zeta(x) := \max \{ y \in Y_x : y < \beta(x) \}$ and $\xi(x) := \min \{ y \in Y_x : \beta(x) < y \}$. As $\gamma_1(x) < \beta(x) < \mu(x)$, these are defined. By piecewise continuity again, we may shrink the cell $C$ to another open cell on which $\zeta$, $\xi$, and $\beta$ are continuous. Then using this continuity, $(x,\beta(x))$ is a normal point for every $x \in C$, contradicting the definition of $\beta$. $\maltese$
Finally, we check that the $\# Y_x$ is constant over $x \in C$ where $C$ is an open cell for which no point is bad. For the non-open cells, we already have bounds on $\# Y_x$ by induction.
Let $a \in C$ with $m := m(a)$ minimal. By the definition of $m(a)$, $\gamma_m$ is continuous on all of $C$. Since $a$ is good, $m(a) = \# Y_a$, or put another way, $\mu(a) = \gamma_{m}(a)$. By continuity of these functions, $\{ x \in C : \mu(x) = \gamma_m(x) \}$ is closed in $C$. By normalcy of the points $(x,\gamma_m(x))$, the set $\{ x \in C : \mu(x) = \gamma_m(x) \}$ is also open. Since this set is nonempty and $C$ is definably connected, $\mu = \gamma_m$ on all of $C$. That is, $\# Y_x = m$ for all points $x \in C$. With this we conclude. $\Box$.
In this proof we used the following lemma.
Lemma: Every cell $C \subseteq R^n$ is definably connected. That is, if $U \subseteq C$ and $V \subseteq C$ are definable, relatively open subsets of $C$ with $U \cup V = C$ and $U \cap V = \varnothing$, then one of $U$ or $V$ is empty.
Proof of Lemma: We argue by induction on $n$ with the case of $n = 0$ being trivial.
In the case of $n = 1$, we have $C = (a,b)$ with $- \infty \leq a < b \leq \infty$. The definable open sets $U$ and $V$ are fnite unions of open intervals. Suppose that both $U$ and $V$ are nonempty. Say $U = \bigcup_{i=1}^n (c_i,d_i)$ and $V := bigcup_{j=1}^m (s_i,t_i)$. Using the fact that the union of two overlapping intervals is also an interval, we may assume that the intervals in the decompositoin of $U$ and of $V$ are disjoint. That is, $a \leq c_1 < d_1 \leq c_2 < d_2 \leq \cdots c_n < d_n \leq b$ and $a \leq s_1 < t_1 \leq s_2 < t_2 \leq \cdots s_m < t_m \leq b$. Without loss of generality, $a = s_1$. Since $t_1 \notin V$, we have $t_1 \in U$. So, for some $j$ we have $c_j < t_1 < d_j$. Let $u \in (c_j,t_1)$. Then $s_1 = a < c_j < u < t_1$ which implies that $u \in U \cap V$ contrary to our hypothesis that $U \cap V = \varnothing$.
In the inductive case of $n +1$, if $C = \Gamma_{C’}(f)$ and $\varpi:R^{n+1} \to R^n$ is the projection to the first $n$ coordinates, then $\varpi \upharpoonright C : C \to C’$ is a definable homeomorphism giving a decomposition $C’ = \varpi(U) \cup \varpi(V)$, which by induction implies $U = \varnothing$ or $V = \varnothing$.
If $C = (f,g)_{C’}$ (where we allow $f \equiv -\infty$ or $g \equiv \infty$), then both $\varpi(U)$ and $\varpi(V)$ are open. Indeed, if $(u,v) \in R^n \times R$ lies in $U$, then because $U$ is open, there is some open box $B \times I$ containing $(u,v)$ and contained in $U$, which projectes the open box $B$ contained in $\varpi(U)$. By the one-dimensiosal case we see that for every $x \in C’$, either $U_x = (f(x),g(x)$ or $V_x = (f(x),g(x))$. That is, $\varpi(U) \cap \varpi(V) = \varnothing$. By the inductive hypothesis, $\varpi(U) = \varnothing$ or $\varpi(V) = \varnothing$. That is, $U = \varnothing$ or $V = \varnothing$, as required. $\Box$.