In our proof of the Cell Decomposition Theorem, we took as known the Uniform Finiteness Theorem.\u00a0 In this post, we fill that gap.<\/p>\n
Uniform Finiteness Theorem<\/strong>:\u00a0 \u00a0Let $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$.\u00a0 Then there is a number $N = N(Y)$ so that all fibers have size at most $N$.<\/p>\n <\/p>\n Proposition<\/strong>:\u00a0 The Uniform Finiteness Theorem is equivalent<\/em> to the assertion that $\\operatorname{Th}(\\mathfrak{R})$ is o-minimal.<\/p>\n Proof of Proposition:\u00a0 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$.\u00a0 \u00a0If 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:<\/p>\n $$T\u00a0 := \\operatorname{Th}(\\mathfrak{R}) \\cup \\{ (\\exists y_1) \\ldots\u00a0 (\\exists y_m)\u00a0 [y_1 < \\ldots < y_m\u00a0 ~\\&~ \\bigwedge (a,y_i) \\in Y ~\\&~ (\\forall b)(\\forall c)\u00a0 \u00a0(b < c \\to (\\exists t) [b < t < c ~\\&~ (a,t) \\notin Y ])] ~:~ m \\in \\mathbb{N} \\}$$<\/p>\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.\u00a0 Hence, $\\mathfrak{R}^*$ is not o-minimal, contrary to our hypothesis that every model of $\\operatorname{Th}(\\mathfrak{R})$ is o-minimal.<\/p>\n In the other direction, let $\\mathfrak{R}^* \\equiv \\mathfrak{R}$ be a structure elementarily equivalent to $\\mathfrak{R}$.\u00a0 Let $X \\subseteq R^*$ be an $R^*$-definable set in one variable.\u00a0 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 :\u00a0 y \\in\u00a0 \\partial (Z_x) \\} =\u00a0 \\{ (x,y) \\in R^n \\times R :\u00a0 y \\in\u00a0 (\\exists \\epsilon_1\u00a0 < y < \\epsilon_2)\u00a0 Y \\cap (\\epsilon_1,\\epsilon_2) \\neq \\varnothing\u00a0 ~\\&~ (R \\smallsetminus Y) \\cap (\\epsilon_1,\\epsilon_2) \\neq \\varnothing \\}$.\u00a0 \u00a0By the o-minimality of $R$, all of the fibers of $Y$ are finite, and, hence, by our assumption of size at most $N(Y)$.\u00a0 This assertion is part of $\\operatorname{Th}(\\mathfrak{R})$.\u00a0 Thus, $\\# \\partial (X) = \\# \\partial (Z_a(\\mathfrak{R}^*)) = \\# Y_a(\\mathfrak{R}^*) \\leq N(Y) < \\infty$.\u00a0 \u00a0It 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$.\u00a0 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$).\u00a0 That is, $\\mathfrak{R}^*$ is o-minimal.\u00a0 $\\Box$<\/p>\n We will prove the Uniform Finiteness Theorem by induction on $n$.\u00a0 To be honest, we are actually proving Cell Decomposition, Uniform Finiteness, and Piecewise Continuity by induction on $n$.\u00a0 \u00a0The case of $n \\leq\u00a0 1$ is trivial.\u00a0 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$.<\/p>\n Proof of Uniform Finiteness<\/strong>: Let $Y \\subseteq R^{n+1}$ be a definable set so that for every $a \\in R^n$ the fiber $Y_a$\u00a0 is finite.\u00a0 Define $\\mu:R^n \\to R$ by $\\mu(x) := \\max Y_x$ (if $Y_x \\neq \\varnothing$) and $\\mu(x)$ is undefined otherwise.\u00a0 \u00a0Define 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.\u00a0 \u00a0Define $\\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$.\u00a0 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}$.\u00a0 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$.\u00a0 \u00a0It suffices to show that we can find such a bound for $Y_C$ when $C \\in \\mathcal{C}$ is open.\u00a0 \u00a0Note that if $\\gamma_1$ is not defined on $C$, then the bound is zero.\u00a0 Likewise, if $\\gamma_1 = \\mu$ on $C$, then the bound is one.\u00a0 \u00a0So, we may restrict our attention to the case that $C$ open and $\\gamma_1 < \\mu$ on $C$.<\/p>\n 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$.\u00a0 Note that $1 \\leq m(a) \\leq \\#Y_a$.\u00a0 \u00a0 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$.<\/p>\n We say that a point $a \\in C$ is good<\/em> if $a \\notin \\overline{\\operatorname{dom} \\gamma_{m(a)+1}}$ and $a$ is bad<\/em> if it is not good.\u00a0 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)$.\u00a0 \u00a0Let us prove definability by analyzing a related concept of normalcy.<\/p>\n We say that a point $(a,b) \\in C \\times R$ is normal<\/em> 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$.<\/p>\n Define $\\beta:C \\to R$ by $x \\mapsto \\inf \\{ y ~:~ (x,y) $ is not normal $\\}$.\u00a0 Let us refine the cell decomposition so that on each cell either $\\beta$ is undefined or $\\beta$ is continuous.<\/p>\n Claim<\/strong> 1: $\\beta(x) < \\mu(x)$ (or $\\beta(x)$ is not defined)<\/p>\n Proof of Claim 1<\/strong>:\u00a0 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$.\u00a0 Then $U \\cap (\\epsilon,\\infty) \\cap Y = \\varnothing$.\u00a0 Thus, $\\beta(x) \\leq \\mu(x)$.\u00a0 But,\u00a0 $(x,\\mu(x))$ is also a normal point as $\\mu$ and $\\delta_2$ are continuous at $x$:\u00a0 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)$.\u00a0 \u00a0 Thus, $\\beta(x) < \\mu(x)$. $\\maltese$<\/p>\n Claim 2<\/strong> : $\\beta(x) > \\gamma_{m(x)}$<\/p>\n Proof of Claim 2<\/strong>:\u00a0 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)$.\u00a0 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\u00a0 $(U \\times (-\\infty,\\sup I_{m(x)})$ so that we may avoid it.\u00a0 \u00a0$\\maltese$<\/p>\n 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$.\u00a0 That is, $x \\in \\operatorname{dom}(\\gamma_{m(x)+1})$ so that $x$ is bad.<\/p>\n On the other hand, suppose that $x$ is bad.\u00a0 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)$.\u00a0 If $x$ is not in the domain of $\\gamma_{m(x)+1}$, then $\\gamma_{m(x)}(x) = \\mu(x)$.\u00a0 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.\u00a0 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$.\u00a0 Hence, $\\mu = \\gamma_{m(x)}$ on $V$, which implies that $\\gamma_{m(x)+1}$ is not defined on $V$.\u00a0 In particular, $x$ is not in the closure of the domain of $\\gamma_{m(x)}$.\u00a0 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}$.<\/p>\n All of this shows that $x$ is bad if and only if $\\beta(x)$ is defined.\u00a0 Hence, the set of bad points is definable.\u00a0 We may now refine our cell decomposition so that it is subjacent to the bad points.<\/p>\n Claim 3<\/strong>: It is impossible for all points in one of our open cells to be bad.<\/p>\n Proof of Claim 3<\/strong>:\u00a0 Let $C$ be our open cell.\u00a0 \u00a0 \u00a0Define $\\zeta(x) := \\max \\{ y \\in Y_x : y < \\beta(x) \\}$ and $\\xi(x) := \\min \\{ y \\in Y_x : \\beta(x) < y \\}$.\u00a0 As $\\gamma_1(x) < \\beta(x) < \\mu(x)$, these are defined.\u00a0 By piecewise continuity again, we may shrink the cell $C$ to another open cell on which $\\zeta$, $\\xi$, and $\\beta$ are continuous.\u00a0 Then using this continuity, $(x,\\beta(x))$ is a normal point for every $x \\in C$, contradicting the definition of $\\beta$. $\\maltese$<\/p>\n 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.\u00a0 For the non-open cells, we already have bounds on $\\# Y_x$ by induction.<\/p>\n Let $a \\in C$ with $m := m(a)$ minimal. By the definition of $m(a)$, $\\gamma_m$ is continuous on all of $C$.\u00a0 Since $a$ is good, $m(a) = \\# Y_a$, or put another way, $\\mu(a) = \\gamma_{m}(a)$.\u00a0 By continuity of these functions, $\\{ x \\in C : \\mu(x) = \\gamma_m(x) \\}$ is closed in $C$.\u00a0 \u00a0By normalcy of the points $(x,\\gamma_m(x))$, the set $\\{ x \\in C : \\mu(x) = \\gamma_m(x) \\}$ is also open.\u00a0 Since this set is nonempty and $C$ is definably connected, $\\mu = \\gamma_m$ on all of $C$.\u00a0 That is, $\\# Y_x = m$ for all points $x \\in C$.\u00a0 \u00a0With this we conclude.\u00a0 $\\Box$.<\/p>\n In this proof we used the following lemma.<\/p>\n Lemma:<\/strong>\u00a0 Every cell $C \\subseteq R^n$ is definably connected.\u00a0 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.<\/p>\n Proof of Lemma<\/strong>:\u00a0 We argue by induction on $n$ with the case of $n = 0$ being trivial.<\/p>\n In the case of $n = 1$, we have $C = (a,b)$ with $- \\infty \\leq a < b \\leq \\infty$.\u00a0 The definable open sets $U$ and $V$ are fnite unions of open intervals.\u00a0 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)$.\u00a0 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.\u00a0 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$.\u00a0 Since $t_1 \\notin V$, we have $t_1 \\in U$.\u00a0 So, for some $j$ we have $c_j < t_1 < d_j$.\u00a0 Let $u \\in (c_j,t_1)$. Then $s_1 = a < c_j\u00a0 < u < t_1$ which implies that $u \\in U \\cap V$ contrary to our hypothesis that $U \\cap V = \\varnothing$.<\/p>\n 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$.<\/p>\n If\u00a0 $C = (f,g)_{C’}$ (where we allow $f \\equiv -\\infty$ or $g \\equiv \\infty$), then both $\\varpi(U)$ and $\\varpi(V)$ are open.\u00a0 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)$.\u00a0 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))$.\u00a0 That is, $\\varpi(U) \\cap \\varpi(V) = \\varnothing$.\u00a0 By the inductive hypothesis, $\\varpi(U) = \\varnothing$ or $\\varpi(V) = \\varnothing$.\u00a0 That is, $U = \\varnothing$ or $V = \\varnothing$, as required.\u00a0 $\\Box$.<\/p>\n <\/p>\n","protected":false},"excerpt":{"rendered":" In our proof of the Cell Decomposition Theorem, we took as known the Uniform Finiteness Theorem.\u00a0 In this post, we fill that gap. Uniform Finiteness Theorem:\u00a0 \u00a0Let $Y \\subseteq R^{n+1}$ be a definable set for which all fibers $Y_a := … Continue reading