The Cell Decomposition Theorem might be called the “Fundamental Theorem of O-minimality”.\u00a0 \u00a0With 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.<\/p>\n
<\/p>\n
As is our wont, we work in a fixed o-minimal structure $\\mathfrak{R}$.\u00a0 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.<\/p>\n
<\/p>\n
Let us define the cells in $R^n$ by recursion on $n$.<\/p>\n
For $n = 0$, the single point $R^0$ itself is a cell.\u00a0 \u00a0Given 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}$.\u00a0 \u00a0If $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) <\u00a0 x_{n+1} < g(x_1,\\ldots,x_n) \\}$$ is a cell in $R^{n+1}$.\u00a0 The infinite parameterized intervals $$(-\\infty,g)_X := \\{ (x_1, \\ldots, x_{n+1}) \\in R^{n+1} : (x_1, \\ldots, x_n) \\in X ~\\&~\u00a0 x_{n+1} < g(x_1,\\ldots,x_n) \\}$$<\/p>\n
$$(-\\infty,g)_X := \\{ (x_1, \\ldots, x_{n+1}) \\in R^{n+1} : (x_1, \\ldots, x_n) \\in X ~\\&~\u00a0 x_{n+1} < g(x_1,\\ldots,x_n) \\}$$<\/p>\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)\u00a0 < x_{n+1}\u00a0 \u00a0\\}$$<\/p>\n
and<\/p>\n
$$(-\\infty,\\infty)_X := X \\times R$$<\/p>\n
are all cells in $R^{n+1}$.<\/p>\n
The cells are precisely the sets obtained via this process.<\/p>\n
We may now state the Cell Decomposition Theorem.<\/p>\n
Cell Decomposition Theorem<\/strong>:\u00a0 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$.<\/p>\n The set $\\mathcal{C}$ is called a cell decomposition of $R^n$<\/em> and we say that it is subjacent to $X_1, \\ldots, X_n$<\/em>.<\/p>\n We prove the Cell Decomposition Theorem in tandem with a theorem on the piecewise continuity of definable functions.<\/p>\n Piecewise Continuity Theorem<\/strong>:\u00a0 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.<\/p>\n 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$.\u00a0 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)$.\u00a0 That is, the cells in $R^1$ are just the points and intervals.\u00a0 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.\u00a0 \u00a0Likewise, the Piecewise Continuity Theorem is trivial for $n = 0$ and is contained in the Monotonicity Theorem for $n = 1$.<\/p>\n We will prove the Cell Decomposition Theorem and the Piecewise Continuity Theorem by simultaneous induction on $n$.\u00a0 As we have noted, we have already dealt with the cases of $n \\leq 1$.\u00a0 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.<\/p>\n Uniform Finiteness Theorem<\/strong>: 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$.<\/p>\n We delay the proof of the Uniform Finiteness Theorem to another post.\u00a0 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)]$.<\/p>\n Inductive case for Cell Decomposition<\/strong>:\u00a0 We assume that Cell Decomposition, Piecwise Continuity, and Uniform Finiteness all hold for $n$.\u00a0 Let $X_1, \\ldots, X_m \\subseteq R^{n+1}$ be a finite list of definable subsets of $R^{n+1}$.\u00a0 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$.\u00a0 \u00a0Define (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.<\/p>\n For a point $x \\in R^n$ we define its combinatorial datum to be<\/p>\n There is a finite set of such possible combinatorial data given that the first tuple lies in $\\{0, \\ldots, N \\}^m$.\u00a0 For each such combinatorial datum $\\Delta$ let $D_\\Delta := \\{ x \\in R^n ~:~ $ the combinatorial datum of $x$ is $\\Delta \\}$.<\/p>\n By Cell Decomposition and Piecewise Continuity in\u00a0 $R^n$, we may find a cell decomposition $\\mathcal{C}$ of $R^n$ so that<\/p>\n We now define a cell decompostion $\\mathcal{C}$ of $R^{n+1}$.\u00a0 For each $C \\in \\mathcal{C}$ by Condition 2, the finitely many $f_{i,j}$ which are defined on $C$ ar linearly ordered.\u00a0 List these a $g_{C,1} < g_{C,2} < \\cdots < g_{C,\\ell(C)}$.\u00a0 Note that it is possible that $\\ell(C) = 0$.\u00a0 Let us extend this list by formally defining $g_{C,0} :\\equiv -\\infty$ and $g_{C,\\ell(C)+1} :\\equiv \\infty$.\u00a0 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)$.<\/p>\n By Condition 1, each of these is a cell.\u00a0 By construction, these cells are disjoint and partition $R^{n+1}$.\u00a0 By Condition 3, this cell decomposition is subjacent to $Y_1, \\ldots, Y_m$.\u00a0 \u00a0$\\Box$<\/p>\n Now we handle the inductive case for Pieceeise Continuity.\u00a0 Here, we allow ourselves Piecewise Continuity for $n$ and Cell Decompostion for $n+1$.<\/p>\n Proof of Inductive Case $n+1$ of Piecewise Continuity<\/strong>:\u00a0 Consider the definable function $f:R^{n+1} \\to R$.\u00a0 \u00a0By Cell Decompostion in $R^{n+1}$, we may find a cell decomposition $\\mathcal{C}$ of $R^{n+1}$ subjacent to<\/p>\n 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}$.\u00a0 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.\u00a0 That is, $f$ is constinuous on each of the $(\\varpi \\upharpoonright C)^{-1} C’$ as $C’$ ranges through this cell decomposition.\u00a0 \u00a0Thus, 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’$.<\/p>\n Claim<\/strong>:\u00a0 $C$ is contained in the sets of clauses 1 and 5 and one of the sets in clauses 2, 3, and 4.<\/p>\n Proof of Claim<\/strong>:\u00a0 \u00a0Let $\\langle x_1, \\ldots, x_{n+1} \\rangle \\in C$.\u00a0 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))$.\u00a0 In particular, there are only finitely many\u00a0 $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.\u00a0 Let $s$ be one of the other points.\u00a0 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).<\/p>\n 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}) \\}$.\u00a0 Let $\\langle u_1, \\ldots, u_n \\rangle$ be one such point.\u00a0 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.\u00a0 $\\maltese$<\/p>\n There are three cases to consider depending on whether Clause 2, 3, or 4 holds on $C$.\u00a0 We will write a proof that handles the cases of Clause 2 and 3 simultaneously.\u00a0 The case of Clause 4 is handled by reversing the inequalities.<\/p>\n Consider a point $\\langle a_1, \\ldots, a_n, a_{n+1} \\rangle \\in C$.\u00a0 Let $\\epsilon_1 < f(a_1,\\ldots,a_n,a_{n+1}) < \\epsilon_2$.\u00a0 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$.\u00a0 By continuity of $f$, $g$, $\\langle u_1, \\ldots, u_n \\rangle \\mapsto f(u_1,\\ldots,u_n,b)$, and\u00a0 $\\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<\/p>\n Consider $\\langle u_1, \\ldots, u_n, u_{n+1} \\rangle \\in U \\times (b,c)$.\u00a0 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$.\u00a0 \u00a0In 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$.<\/p>\n 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$.\u00a0 With this we conclude. $\\Box$<\/p>\n <\/p>\n <\/p>\n <\/p>\n <\/p>\n <\/p>\n <\/p>\n","protected":false},"excerpt":{"rendered":" The Cell Decomposition Theorem might be called the “Fundamental Theorem of O-minimality”.\u00a0 \u00a0With 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 … Continue reading \n
\n
\n
\n