We have seen how to assign a natural number valued dimension to definable sets in o-minimal structures. There is a second integer valued invariant, which we will call the Euler characteristic. In o-minimal expansions of fields, these two invariants characterize definable sets up to definable bijection.
With this post we discuss the general theory of Euler characteristics of definable sets and will see that when $\mathfrak{R} = (R,<,+,\cdot,\ldots)$ is an o-minimal expansion of a field every Euler characteristic must take values in a quotient of $\mathbb{Z}$.
The Grothendieck group construction makes sense for any small category.
Definition 1: Let $\mathsf{C}$ be a small category. We define $SK_0(\mathsf{C})$ to be the commutative monoid generated by the isomorphism classes of the objects in $\mathsf{C}$ modulo the congruence generated by the relations that $[X \coprod Y] = [X] + [Y]$ whenever $X$ and $Y$ are objects admitting a coproduct $X \coprod Y$.
In practice, we may prefer to work with a group rather than a mere monoid. Just as with the localization construction for commutative rings, there is a universal map from a commutative monoid $M$ to a group.
Proposition 2: The forgetful functor $F:\text{CGrp} \to \text{CMon}$ from commutative groups to commutative monoids has a left adjoint, $G:\text{CMon} \to \text{CGrp}$. More concretely, for any commutative monoid $M$ there is a commutative group $G(M)$ and a map of monoids $\gamma:M \to G(M)$ which is universal for such maps meaning that if $H$ is a commutative groups and $\delta:M \to H$ is a map of monoids, then there is a unique map of groups $f:G(M) \to H$ so that $\delta = f \circ \gamma$.
Proof: On the set $M \times M$ we define an equivalence relation $\langle a, b \rangle \sim \langle c, d \rangle :\Longleftrightarrow (\exists e \in M) (a + d) + e = (c+b) + e$. We define $G(M) := (M \times M) / \sim$ and $M \to G(M)$ by $m \mapsto [\langle m, 0 \rangle]_\sim$. We leave the verification that this construction works to the reader. $\Box$
Remark 3: Note that just as a localization map need not be injective, it may happend that $M \to G(M)$ is not an embedding. For example, if $M = \{ 0, 1 \}$ with $1 + 1 = 0 + 1 = 1 + 0 = 1$ and $0 + 0 = 0$, then $G(M)$ is the trivial group.
Definition 4: For any small category $\mathsf{C}$ the Grothendieck group $K_0(\mathsf{C})$ of $\mathsf{C}$ is the groupification of $SK_0(\mathsf{C})$, i.e. $G(SK_0(\mathsf{C})$.
Proposition 5: If $\mathsf{C}$ is a small category with binary coproducts, then every nonzero element of $SK_0(\mathsf{C})$ is represented by an object of $\mathsf{C}$, and every element of $K_0(\mathsf{C})$ is represented as the difference of two objects of $\mathsf{C}$. If moreover, $\mathsf{C}$ is closed under binary products, then $SK_0(\mathsf{C})$ has the structure of a commutative semiring and $K_0(\mathsf{C})$ is a commutative ring. If $\mathsf{C}$ has an initial object $\varnothing$, then the image of $\varnothing$ in $K_0(\mathsf{C})$ is the additive identity. If $\mathsf{C}$ has a terminal object $\{ \ast \}$, then the image of $\{ \ast \}$ in $K_0(\mathsf{C})$ is the multiplicative identity.
Proof: Let us start by showing that nonzero every element of $SK_0(\mathsf{C})$ is represented by an object of $\mathsf{C}$. For this we only need that $\mathsf{C}$ is closed under finite coproducts. A general element of $SK_0(\mathsf{C})$ is represented by a formal sum $\sum n_X [X]$ where $n_X \in \mathbb{N}$ for $[X]$ an isomorphism class of objects of $\mathsf{C}$ with $n_X = 0$ for all but finitely many $X$. Let us argue by induction on $\sum n_X$ that such a sum $\sum n_X [X]$ is represented by a single object of $\mathsf{C}$. One might guess that when $\sum n_X = 0$ the sum is represented by the initial object $\varnothing$ of $\mathsf{C}$, but this is not the case. It is true that $\varnothing$ acts as an additive identity, but in the congruence defining $SK_0(\mathsf{C})$ every part of a pair of equivalent sums is a nonzero sum. So we start with $\sum n_X = 1$, in which case $n_X = 1$ for exactly on $X$ and the sum is represented by $[X]$. For the inductive case where $\sum n_X = n + 1$, let $X \in \mathsf{C}$ with $n_X > 0$. Let us define $n’_Y := n_Y$ if $[Y] \neq [X]$ and $n’_X := n_X – 1$. By induction, there is some object $Z$ with $\sum n’_Y [Y] = [Z]$ and $\sum n_Y [Y] = \sum n’_Y [Y] + [X] = [Z] + [X] = [Z \coprod X]$.
From the groupification construction, we see that every element of $K_0(\mathsf{C})$ takes the form of $x – y$ where $x$ and $y$ are (images of) elements of $SK_0(\mathsf{C})$. Thus, under the hypothesis that $\mathsf{C}$ is closed under coproducts, every element of $K_0(\mathsf{C})$ is represented as a difference of two objects of $\mathsf{C}$.
On general grounds, for any pair of objects $X$ and $Y$ we have $X \coprod Y \approx Y \coprod X$ and $X \times Y \approx Y \times X$, giving the claimed commutativity. Likewise, for any triple of objects $X$, $Y$, and $Z$ we have $X \times (Y \coprod Z) \approx (X \times Y) \coprod (X \times Z)$. The assertions about the identities reflect the facts that for every object $X$ we have $\varnothing \coprod X \approx X$ and $\{ \ast \} \times X \approx X$. $\Box$
Definition 5: For any first-order language $\mathcal{L}$ and $\mathcal{L}$-structure $\mathfrak{M}$ we let $\text{Def}(\mathfrak{M})$ be the category whose objects are the $\mathcal{L}_M$-definable sets in $\mathfrak{M}$ (in any number of variables) and for which the set $\text{Mor}_{ \text{Def}(\mathfrak{M})}(X,Y)$ of morphisms betwen the definable sets $X$ and $Y$ is the set of definable functions $f:X \to Y$. We define $SK_0(\mathfrak{M}) := SK_0(\text{Def}(\mathfrak{M})$ and $K_0(\mathfrak{M}) := K_0(\text{Def}(\mathfrak{M}))$.
Remark 6: There are various refinements of the Grothendieck group/ring construction for first-order structures. For example, we might prefer to work only with definable sets in a first sort in which case the corresponding Grothendieck group does not have a natural ring structure. We can also work relative to a not necessarily complete theory. Here we would take $T$ an $\mathcal{L}$-theory, the category $\text{Def}(T)$ has as its objects the definable sets relative to $T$, that is, $\mathcal{L}$-formulae $\phi(x_1,\ldots,x_n) \in \mathcal{L}(x_1,\ldots,x_n)$ with a choice of variable context $(x_1,\ldots, x_n)$ up to equivalence, i.e. $\phi(x_1,\ldots,x_n) \sim \psi(x_1,\ldots,x_n) :\Longleftrightarrow T \vdash (\forall x_1) \ldots (\forall x_n) (\psi \leftrightarrow \phi)$ and the morphisms are the definable functions, i.e. $\text{Mor}_{\text{Def}(T)} ( [\phi(x_1,\ldots,x_n)]_\sim, [\psi(x_1,\ldots,x_m)]_\sim)$ is the set $$\{ [\theta(x_1,\ldots,x_{n+m})]_\sim : T \vdash [\theta \to (\phi \land \psi(x_{n+1},\ldots,x_{n+m)} )] \land (\forall (x_1, \ldots, x_n) )[\phi \to (\exists ! (x_{n+1}, \ldots, x_{n+m})) \theta] \}$$
Corollary 7: For any first-order structure $\mathfrak{M}$ with at least two elements the Grothendieck group $K_0(\mathfrak{M})$ is a commutative ring in which every element is of the form $[X] – [Y]$ for some definable sets $X$ and $Y$.
Proof: Let $a \neq b$ be two distinct elements of $M$. Then for $X$ and $Y$ definable sets with $X \subseteq M^n$ and $Y \subseteq M^m$ with $n \leq m$, then $X \coprod Y$ is represented by $X \times \{ (\overbrace{a, \ldots, a}^{(m-n)+1 \text{ times } \} \cup (Y \times \{ b \})$ and the product is represented by the usual set theoretic Cartesian product. $\Box$.
Definition 8: An Euler characteristic on a structure $\mathfrak{M}$ is a function $\chi:\text{Def}(\mathfrak{M}) \to A$ from the definable sets in $\mathfrak{M}$ to a ring $A$ satisfying
- $\chi(\varnothing) = 0$,
- $\chi(\{ \ast \}) = 1$ for any singleton $\{ \ast \} \in \text{Def}(\mathfrak{M})$,
- $\chi(X \dot{\cup} Y) = \chi(X) + \chi(Y)$ for any two definable sets $A$ and $B$,
- $\chi(X \times Y) = \chi(X) \cdot \chi(Y)$ for any two definable sets $X$ and $Y$, and
- if there is a definable bijection $f:X \to Y$, then $\chi(X) = \chi(Y)$.
Proposition 9: For any first-order structure $\mathfrak{M}$, the association from $\widetilde{\chi}:\text{Def}f(\mathfrak{M}) \to K_0(\mathfrak{M})$ sending a definable set $X$ to $\gamma([X]_\sim) \in K_0(\mathfrak{M})$, that is the image of the isomorphism class of $X$ under the groupification map, is the universal Euler characteristic on $\mathfrak{M}$: for any Euler characteristic $\chi:\text{Def}(\mathfrak{M}) \to A$ on $\mathfrak{M}$ there is a unique map of rings $\overline{\chi}:K_0(\mathfrak{M}) \to A$ with $\chi = \overline{\chi} \circ \widetilde{\chi}$.
Proof: This is an immediate consequence of the construction of $K_0(\mathfrak{M})$.
Proposition 10: If $\mathfrak{M}$ is a finite structure, then $K_0(\mathfrak{M}) = \mathbb{Z}$.
Proof: Define $\chi:\text{Def}(\mathfrak{M}) \to \mathbb{Z}$ by $X \mapsto |X(\mathfrak{M})$, the (finite) cardinality of the definable set $X$. By the usual properties of counting, $\chi$ is an Euler characteristic. By the universal property of $\widetilde{\chi}:\text{Def}(\mathfrak{M}) \to K_0(\mathfrak{M})$, there is a unique map of rings $\overline{\chi}:K_0(\mathfrak{M})$ so that for any pair of definable sets $X$ and $Y$ we have $\overline{\chi}([X] – [Y]) = |X| – |Y|$.
Let $\ast \in M$ be any element. We have a map of rings $\xi:\mathbb{Z} \to K_0(\mathfrak{M})$ defined by $n \mapsto n \cdot [\{ \ast \}] = n \cdot 1_{K_0(\mathfrak{M})}$. By construction, $\xi$ is a section of $\overline{\chi}$.
Since we allow parameters from $\mathfrak{M}$, we have for any definable set $X$, $X = \dot{\bigcup}_{x \in X(\mathfrak{M})} \{ x \}$ so that in $SK_0(\mathfrak{M})$, as long as $X$ is non-empty, we have $[X] = \sum_{x \in X(\mathfrak{M})} [\{ x \}] = \sum_{x \in X(\mathfrak{M})} [\{ \ast \}] = \sum_{x \in X(\mathfrak{M})} 1 = |X| = \chi(X)$. Representing a general element of $K_0(\mathfrak{M})$ as $[X] – [Y]$ for definable sets $X$ and $Y$, we then have $\xi \circ \overline{\chi} ( [X] – [Y] ) = \xi ( |X| – |Y| ) = |X| \{ \ast \} – |Y| \{ \ast \} = [X] – [Y]$. That is, $\xi$ is also a left inverse to $\overline{\chi}$. Therefore, $K_0(\mathfrak{M}) \cong \mathbb{Z}$. $\Box$
Proposition 11: For a first-order structure $\mathfrak{M}$ we have that $K_0(\mathfrak{M}) = 0$ if and only if there is a definable set $X$ and a definable injection $f:X \to X$ for which $|X \smallsetminus \text{ran}(f)| = 1$.
Proof: Let us prove the right-to-left implication first. Let $X$ be a definable set and $f:X \to X$ a definable injection which misses exactly one element, $\ast \in X$. Then in $SK_(\mathfrak{M})$ we have $[f(X)] + 0 = [f(X) \dot{\cup} \varnothing] = [f(X)] = [X] = [f(X) \dot{\cup} \{ \ast \}] = [f(X)] + [\{ \ast \}] = [f(X)] + 1$. Hence, in $K_0(\mathfrak{M})$ we have $0 = 1$ so that $K_0(\mathfrak{M})$ is the zero ring.
For the other implication, we suppose that $K_0(\mathfrak{M}) = 0$. Since $K_0(\mathfrak{M}) = 0$, we have $0 = 1$ in $K_0(\mathfrak{M})$. By Proposition 10, we may assume that $\mathfrak{M}$ is infinite. In particular, it has at least two elements so that every element of $K_0(\mathfrak{M})$ is represented by the difference of two definable sets. In $K_0(\mathfrak{M})$, $0 = [\varnothing]$ and $1 = [\{ \ast \}]$ for some $\ast \in M$. Thus, there is some definable set $Z$ disjoint from $\{ \ast \}$ with $Z = Z \cup \varnothing \approx Z \cup \{ \ast \} =: X$. Let $f:X \to Z \subseteq Z$ be a definable bijection between $X$ and $Z$ witnessing this equivalence. Then $f$ is a definable self-injection from $X$ to itself missing exactly one point. $\Box$