For the sake of building a dimension theory for definable sets in o-minimal structures, we will follow a more model theoretic approach, due to Pillay, to dimensions than what appears in van den Dries’ book. That is, we will show that o-minimal structures are geometric which means that algebraic closure endows the universe of such a structure with a pregeometry, or what is sometimes called a matroid. In the following post we will explain how to define dimensions in pregeometries.
Let us recall the definitions of definable and algebraic closure in arbitrary structures.
Definition 1: Let $\mathfrak{M}$ be an $\mathcal{L}$-structure for some first-order language $\mathcal{L}$. If $A \subseteq M$ is any subset and $a \in M$, then we say that $a$ is definable over $A$ if there is a formula $\phi(x) \in \mathcal{L}_A(x)$ so that $\phi(\mathfrak{M}) = \{ a \}$. We say that $a$ is algebraic over $A$ if there is a formula $\phi(x) \in \mathcal{L}_A(x)$ so that $\phi(\mathfrak{M}) $ is finite and $\mathfrak{M} \models \phi(a)$. We define the definable closure of $A$ to be $\text{dcl}(A) := \{ a \in M : a \text{ is definable over } A \}$ and the algebraic closure of $A$ is $\text{dcl}(A) := \{ a \in M : a \text{ is algebraic over } A \}$.
Remark 2: It follows from Galois theory that if $\mathfrak{M}$ is an algebraically closed field considered in the language of rings with prime subfield $k$ (so either $\mathbb{F}_p$ for some some prime number $p$ or $\mathbb{Q}$), and $A \subseteq M$, then $\text{dcl}(A) = k(A)^\text{perf}$, the perfection of the field generated by $A$, and $\text{acl}(A) = k(A)^\text{alg}$, the algebraic closure in the usual field theoretic sense of the field generated by $A$.
Remark 3: If $\mathfrak{M}$ carries a definable total ordering $<$, which, of course, is the case for the o-minimal structures we consider, then $\text{dcl} = \text{acl}$. Indeed, if $A \subseteq M$ and $a \in \text{acl}(a)$ witnessed by $\phi(x) \in \mathcal{L}_A(x)$ with $\phi(\mathfrak{M})$ finite and $a \in \phi(\mathfrak{M})$, then because $\phi(\mathfrak{M})$ is finite, $a$ will be the $m^\text{th}$ element of this set for some $m$ and then the formula $$\psi(x) := \phi(x) \land (\exists y_1) \ldots (\exists y_{m-1} [x_1 < x_2 < \ldots < x_{m-1} < y \land \bigwedge_{i=1}^{m-1} \phi(y_i) \land (\forall z) ([\phi(z) \land z < y] \to \bigvee_{i=1}^{m-1} z = y_i)]$$ belongs to $\mathcal{L}_A(x)$ and defines $\{ a \}$.
With the next proposition we verify that algebraic and definable closures may be computed accurately in elementary extensions.
Proposition 4: If $\mathfrak{M} \preceq \mathfrak{N}$ is an elementary extension and $A \subseteq M$ is a subset of $M$, the algebraic (respectively, definable) closure of $A$ computed in $\mathfrak{M}$ is the same as the algebraic (respectively, definable) closure of $A$ computed in $\mathfrak{N}$.
Proof: We will write the proof for the algebraic closure. Suppose that $a$ is algebraic over $A$ as computed in $\mathfrak{M}$ witnessed by some formula $\phi(x)$. In particular, $a \in M$. As $\mathfrak{M} \preceq \mathfrak{N}$ and $Aa \subseteq M$, we have $\mathfrak{M} \models \phi(a) \Longrightarrow \mathfrak{N} \models \phi(a)$. Since $\phi(\mathfrak{M})$ is finite, it has some finite size $m \in \mathbb{Z}_+$. Let $$\psi := (\exists y_1) \ldots (\exists y_m) [\bigwedge_{1 \leq i < j \leq m} y_i \neq y_j \land \bigwedge_{i=1}^m \phi(y_i) \land (\forall z) (\phi(z) \to \bigvee_{i=1}^m z = y_i)]$$ Then $\mathfrak{M} \models \psi$, so that again because $\mathfrak{N}$ is an elementary extension of $\mathfrak{M}$, we have $\mathfrak{N} \models \psi$, which means that $|\phi(\mathfrak{N})| = m < \infty$. That is, $\mathfrak{N} \models \phi(a)$ and $\phi(\mathfrak{N})$ is finite so that $a$ is algebraic over $A$ as computed in $\mathfrak{N}$. Thus, we have shown that the algebraic closure of $A$ as computed in $\mathfrak{M}$ is contained in the algebraic closure of $A$ as computed in $\mathfrak{N}$.
For the other inclusion, consider some $b \in N$ which is algebraic over $A$ as computed in $\mathfrak{N}$. Let $\phi(x) \in \mathcal{L}_A(x)$ witness this algebraicity. That is, $\phi(\mathfrak{N})$ is finite (say, of size $m$) and $b \in \phi(\mathfrak{N})$. Consider again the sentence $\psi$ of the above paragraph. We have $\mathfrak{N} \models \psi$, so that because $\mathfrak{M}$ is an elementary substructure of $\mathfrak{N}$ containing the parameters appearing in $\psi$, we have $\mathfrak{M} \models \psi$ as well. That is, $\phi(\mathfrak{M})$ also has size $m$. List the distinct elements as $\phi(\mathfrak{M}) = \{ a_1, \ldots, a_m \}$. Since $Aa_1\ldots a_m \subseteq M$ and $\mathfrak{M} \preceq \mathfrak{N}$ we have $\mathfrak{N} \models \phi(a_i)$ for each $i \leq m$. That is, $\phi(\mathfrak{M}) = \{ a_1, \ldots, a_m \} \subseteq \phi(\mathfrak{N})$. As $|\phi(\mathfrak{N})| = m$, we have $\{ a_1, \ldots, a_m \} = \phi(\mathfrak{N})$. As $b \in \phi(\mathfrak{N})= \phi(\mathfrak{M})$, we must have $b = a_j \in M$ for some $j \leq m$. Hence, $b$ is algebraic over $A$ as computed in $\mathfrak{M}$. $\Box$
For us the key property of algebraic/definable closure on an o-minimal structure is that it gives a pregeometry.
Definition 5: A pregeometry $(X,\text{cl})$ consists of a set $X$ and “closure operator” $\text{cl}:\mathcal{P} X \to \mathcal{P} X$ satisfying the following conditions.
- $A \subseteq \text{cl}(A)$ for every set $A \subseteq X$,
- if $A \subseteq B \subseteq X$, then $\text{cl}(A) \subseteq \text{cl}(B)$
- for every $A \subseteq X$ we have $\text{cl}(A) = \bigcup_{A_0 \subseteq A, \text{ finite }} \text{cl}(A_0)$,
- $\text{cl}(\text{cl}(A)) = \text{cl}(A)$ for every set $A \subseteq X$, and
- if $a, b \in X$, $A \subseteq X$, and $b \in \text{cl}(Aa) \smallsetminus \text{cl}(A)$, then $a \in \text{cl}(Ab)$ [where here we write $Aa := A \cup \{ a \}$].
In fact, for any structure, algebraic closure satisfies the first four axioms for a pregeometry.
Proposition 6: For any first-order language $\mathcal{L}$ and $\mathcal{L}$-structure $\mathfrak{M}$, the pair $(M,\text{acl})$ satisfies the first four axioms of a pregeometry.
Proof: The first three axioms are straightforward. For the sake of completeness, we write out the proofs.
- Let $A \subseteq M$. Consider any $a \in A$. Then the formula $x = a$ defines $a$ and is over $A$. Hence, $A \subseteq \text{dcl}(A) \subseteq \text{acl}(A)$.
- Suppose that $A \subseteq B \subseteq M$. If $a \in \text{acl}(A)$ (respectively, $\text{dcl}(A)$) witnessed by some formula $\phi(x) \in \mathcal{L}_A(x)$, then because $\mathcal{L}_A(x) \subseteq \mathcal{L}_B(x)$, $\phi$ also witnesses that $a \in \text{acl}(B)$ (respectively, $\text{dcl}(B)$). Thus, $\text{acl}(A) \subseteq \text{acl}(B)$ (respectively, $\text{dcl}(A) \subseteq \text{dcl}(B)$).
- Suppose that $A \subseteq M$ and $a \in \text{acl}(A)$ (respectively, $\text{dcl}(A)$) witnessed by some formula $\phi(x) \in \mathcal{L}_A(x)$. We may write $\phi(x) = \psi(x,b_1, \ldots, b_m)$ for some $m \in \mathbb{N}$, $\psi \in \mathcal{L}(x,y_1, \ldots, y_m)$, and $b_1, \ldots, b_m \in A$. Set $A_0 := \{ b_1, \ldots, b_m \}$. Then $\phi \in \mathcal{L}_{A_0}(x)$ witnesses that $a \in \text{acl}(A_0)$ (respectively, $\text{dcl}(A_0)$). Thus, $\text{acl}(A) = \bigcup_{A_0 \subseteq A, \text{ finite }} \text{acl}(A_0)$ (respectively, $\text{dcl}(A) = \bigcup_{A_0 \subseteq A, \text{ finite }} \text{dcl}(A_0)$).
- Let $A \subseteq M$. We have already seen by 1. that $\text{acl}(A) \subseteq \text{acl}(\text{acl}(A))$ (respectively, $\text{dcl}(A) \subseteq \text{dcl}(\text{dcl}(A))$ ). Thus, we need only establish the reverse inclusion. To avoid cluttering the text, we write out the details just for $\text{acl}$. Suppose that $a \in \text{acl}(\text{acl}(A))$. This is witnessed by some $\phi(x) \in \mathcal{L}_{\text{acl}(A)}(x)$. Let us set $m := |\phi(\mathfrak{M})|$. Reasoning as in 3., there is finite sequence $b_1, \ldots, b_\ell$ of elements of $\text{acl}(A)$ so that $\phi(x) = \psi(x,b_1, \ldots, b_\ell)$ for some $\psi(x,y_1, \dots, y_\ell) \in \mathcal{L}_a(x,y_1,\ldots,y_\ell)$. For each $i \leq m$ let $\theta_i(y_i) \in \mathcal{L}_A(y_i)$ witness that $b_i \in \text{acl}(A)$. In particular, for each $i \leq m$ the set $\theta(\mathfrak{M})$ is finite. Consider the formula $\vartheta(y_1, \ldots, y_\ell) := \bigwedge_{i=1}^\ell \theta_i(y_i)$. Then $\vartheta(\mathfrak{M}) = \prod_{i=1}^\ell \theta_i(\mathfrak{M})$ is also finite and contained $\langle b_1, \ldots, b_\ell \rangle$. Let $\varpi(y_1, \ldots, y_\ell) \in \mathcal{L}_A(y_1,\ldots,y_\ell)$ be a formula for which $\mathfrak{M} \models \varpi(b_1, \ldots, b_\ell)$ and the cardinalit of $\varpi(\mathfrak{M})$ is as small as possible. Since $\mathfrak{M} \models \vartheta(b_1, \ldots, b_\ell)$ and $\vartheta(\mathfrak{M})$ is finite, we see that such a $\varpi$ must exist. We note that $\varpi$ isolates $\text{tp}(b_1, \ldots, b_\ell/A)$ for if $\eta(y_1,\ldots,y_\ell) \in \text{tp}(b_1, \ldots,b_\ell/A)$, then so is $\zeta :=\varpi \land \eta$. Of course, $\zeta$ implies $\varpi$, so $|\zeta(\mathfrak{M})| \leq |\varpi(\mathfrak{M})|$. Since this finite cardinality is minimized by $\varpi$, we must have $\zeta(\mathfrak{M}) =\varpi(\mathfrak{M})$. That is, $\mathfrak{M} \models \zeta \leftrightarrow \varpi$. Hence, $\mathfrak{M} \models \varpi \to \eta$, as claimed. One formula in $\text{tp}(b_1, \ldots, b_\ell/A)$ is the assertion that $\phi(x,y_1,\ldots,x_\ell)$ (as a formula in $\mathcal{L}_{A y_1,\ldots,y_m}(x)$) has exactly $m$ realizations. Let us set $$\xi(x) := (\exists y_1) \ldots (\exists y_\ell) [ \varpi(y_1, \ldots, y_\ell) \land \psi(x,y_1,\ldots,y_\ell) ]$$ By construction, $\xi \in \mathcal{L}_A(x)$. The size of $\xi(\mathfrak{M})$ is atmost $|\varpi(\mathfrak{M}| \cdot m$, which is finite. Moreover, $\mathfrak{M} \models \xi(a)$ witnessed by $\langle y_1, \ldots, y_\ell \rangle = \langle b_1, \ldots, b_\ell \rangle$. Hence, $a \in \text{acl}(A)$. As $a \in \text{acl}(\text{acl}(A))$ was arbitrary, this establishes that $\text{acl} (\text{acl}(A)) \subseteq \text{acl}(A)$, and, hence, the desired equality. $\Box$.
Definition 7: A first-order theory $T$ is geometric if for every $\mathfrak{M} \models T$, the structure $(M,\text{acl})$ is a pregeometry.
Remark 8: From Proposition 6, we see that that an equivalent condition to a theory being geometric is that $\text{acl}$ satisfies the exchange axiom, the fifth axiom in the definition of a pregeometry, in every model of that theory.
Theorem 9: If $\mathfrak{R}$ is o-minimal, then $\text{Th}(\mathfrak{R})$ is geometric.
Proof: We have seen that if a structure is o-minimal, then so is its theory. Thus, it suffices to check that $(R,\text{acl})$ is a pregeometry. By Remark 3, we may replace $\text{acl}$ by $\text{dcl}$ and then by Remark 8, it suffices to check the exchange axiom. Suppose now that $A \subseteq R$, $a, b \in R$, and $b \in \text{dcl}(Aa) \smallsetminus \text{dcl}(A)$. Let $\phi(x) \in \mathcal{L}_{Aa}(x)$ witness that $b \in \text{dcl}(Aa)$. Write $\phi(x) = \psi(x,a)$ for some $\psi(x,y) \in \mathcal{L}_A(x,y)$. Since $\phi(\mathfrak{R}) = \{ b \}$ is a singleton, by compactness, there is a formula $\theta(y) \in \text{tp}(a/A)$ so that $\mathfrak{R} \models (\forall y) [\theta(y) \to (\exists ! x) \psi(x,y)]$. That is, $\psi$ defines a (possibly partial) function $f:R \dashrightarrow R$ with $a \in \text{dom}(f)$ and $f(a) = b$ via the rule $x = f(y) \Longleftrightarrow \mathfrak{R} \models \phi(x,y)$.
By the monotonicity theorem, there is some $n \in \mathbb{N}$ and $n$ elements of $R \cup \{\pm \infty \}$ with $-\infty = c_0 < c_2 < \ldots < c_n = \infty$ so that for each $i$ exactly one of
- $f$ is not defined at any point in $(c_i,c_{i+1})$,
- $f$ is constant on $(c_i,c_{i+1})$,
- $f$ is continuous and strictly increasing on $(c_i,c_{i+1})$, or
- $f$ is continuous and strictly decreasing on $(c_i,c_{i+1})$
holds. Let us note that we may take the $c_i$’s to be $A$-definable. Indeed, we start by observing that the boundary of the set on which $f$ is defined and continuous is $A$-definable and finite so that each of its elements is $A$-definable. Likewise, on each of these intervals, the set of points at which $f$ is not locally constant or locally monotone is finite and $A$-definable. So once again we may decompose $R$ into $A$-definable intervals (and a finite $A$-definable set) so that on each such interval $f$ is continuous and locally constant or locally monotone. We have seen that a definable continuous function on an interval which is locally constant or locally monotone is actually constant or monotone.
The element $a$ is not equal to $c_i$ for any $i \leq n$. Indeed, if it were, then $b \in \text{dcl}(Aa) = \text{dcl}(Ac_i) \subseteq \text{dcl}(\text{dcl}(A)) = \text{dcl}(A)$ contrary to our hypothesis. So there is some $i \leq n$ for which $c_i < a < c_{i+1}$. Since $a \in \text{dom}(f)$ and there are no boundary points of $\text{dom}(f)$ between $c_i$ and $c_{i+1}$, we have that $f$ is defined, continuous, and constant or monotone on $(c_i,c_{i+1})$. We cannot be in the case that $f$ is constant on $(c_i,c_{i+1})$ for if it where then the formula $$\theta(x) := (\exists y) [c_i < y < c_{i+1} \land \phi(x,y)]$$ would define $b$ and is a formula over $\text{dcl}(A)$, implying that $b \in \text{dcl}(\text{dcl}(A)) = \text{dcl}(A)$, contrary to our hypothesis. Thus, $f \upharpoonright (c_i,c_{i+1})$ is monotone, and, in particular, one-to-one. We may then define $a$ as $a = \left( f \upharpoonright (c_i,c_{i+1}) \right)^{-1}(b)$. That is, we may use $$\vartheta(y) := \phi(y,b) \land c_i < u < c_{i+1}$$ which is a formula over $\text{dcl}(A) b$, showing that $a \in \text{dcl}(\text{dcl}(A)b) \subseteq \text{dcl}(\text{dcl}(Ab)) = \text{dcl}(Ab)$, as required. $\Box$