We have seen how to assign a natural number valued dimension to definable sets in o-minimal structures.\u00a0 There is a second integer valued invariant, which we will call the Euler characteristic.\u00a0 \u00a0In o-minimal expansions of fields, these two invariants characterize definable sets up to definable bijection.<\/p>\n
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}$.<\/p>\n
<\/p>\n
The Grothendieck group construction makes sense for any small category.<\/p>\n
Definition 1:<\/strong> Let $\\mathsf{C}$ be a small category.\u00a0 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]$\u00a0 whenever $X$ and $Y$ are objects admitting a coproduct $X \\coprod Y$.<\/p>\n In practice, we may prefer to work with a group rather than a mere monoid.\u00a0 Just as with the localization construction for commutative rings, there is a universal map from a commutative monoid $M$ to a group.<\/p>\n Proposition 2:<\/strong> 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}$.\u00a0 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$.<\/p>\n Proof:<\/strong> 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$.\u00a0 We define $G(M) := (M \\times M) \/ \\sim$ and $M \\to G(M)$ by $m \\mapsto [\\langle m, 0 \\rangle]_\\sim$.\u00a0 We leave the verification that this construction works to the reader. $\\Box$<\/p>\n Remark 3:<\/strong> 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.<\/p>\n Definition 4:<\/strong> For any small category $\\mathsf{C}$ the Grothendieck group<\/em> $K_0(\\mathsf{C})$ of $\\mathsf{C}$ is the groupification of $SK_0(\\mathsf{C})$, i.e. $G(SK_0(\\mathsf{C})$.<\/p>\n Proposition 5:<\/strong> 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}$.\u00a0 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.\u00a0 If $\\mathsf{C}$ has an initial object $\\varnothing$, then the image of $\\varnothing$ in $K_0(\\mathsf{C})$ is the additive identity.\u00a0 If $\\mathsf{C}$ has a terminal object $\\{ \\ast \\}$, then the image of $\\{ \\ast \\}$ in $K_0(\\mathsf{C})$ is the multiplicative identity.<\/p>\n Proof: Let us start by showing that nonzero every element of $SK_0(\\mathsf{C})$ is represented by an object of $\\mathsf{C}$.\u00a0 \u00a0For this we only need that $\\mathsf{C}$ is closed under finite coproducts.\u00a0 \u00a0A 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$.\u00a0 \u00a0 \u00a0Let 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}$.\u00a0 \u00a0One 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.\u00a0 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.\u00a0 \u00a0So we start with $\\sum n_X = 1$, in which case $n_X = 1$ for exactly on $X$ and the sum is represented by\u00a0 $[X]$.\u00a0 For the inductive case where $\\sum n_X = n + 1$, let $X \\in \\mathsf{C}$ with $n_X > 0$.\u00a0 Let us define $n’_Y := n_Y$ if $[Y] \\neq [X]$ and $n’_X := n_X – 1$.\u00a0 By induction, there is some object $Z$ with $\\sum n’_Y [Y] = [Z]$ and $\\sum n_Y [Y] = \\sum n’_Y [Y] +\u00a0 [X] = [Z] + [X] = [Z \\coprod X]$.<\/p>\n <\/p>\n 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})$.\u00a0 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}$.<\/p>\n 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.\u00a0 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)$.\u00a0\u00a0The 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$.\u00a0 $\\Box$<\/p>\n Definition 5:<\/strong>\u00a0 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$.\u00a0 \u00a0We define $SK_0(\\mathfrak{M}) := SK_0(\\text{Def}(\\mathfrak{M})$ and $K_0(\\mathfrak{M}) := K_0(\\text{Def}(\\mathfrak{M}))$.<\/p>\n Remark 6<\/strong>: There are various refinements of the Grothendieck group\/ring construction for first-order structures.\u00a0 \u00a0For 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.\u00a0 We can also work relative to a not necessarily complete theory.\u00a0 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.\u00a0 $\\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] \\}$$<\/p>\n Corollary 7:<\/strong>\u00a0 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$.<\/p>\n Proof:\u00a0 Let $a \\neq b$ be two distinct elements of $M$.\u00a0 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.\u00a0 \u00a0$\\Box$.<\/p>\n Definition 8:\u00a0<\/strong> 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<\/p>\n Proposition 9:<\/strong>\u00a0 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}$.<\/p>\n Proof:<\/strong>\u00a0 This is an immediate consequence of the construction of $K_0(\\mathfrak{M})$.<\/p>\n Proposition 10:<\/strong>\u00a0 If $\\mathfrak{M}$ is a finite structure, then $K_0(\\mathfrak{M}) = \\mathbb{Z}$.<\/p>\n Proof:\u00a0 Define $\\chi:\\text{Def}(\\mathfrak{M}) \\to \\mathbb{Z}$ by $X \\mapsto |X(\\mathfrak{M})$, the (finite) cardinality of the definable set $X$.\u00a0 \u00a0By the usual properties of counting, $\\chi$ is an Euler characteristic.\u00a0 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|$.<\/p>\n 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})}$.\u00a0 By construction, $\\xi$ is a section of $\\overline{\\chi}$.<\/p>\n 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)$.\u00a0 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]$.\u00a0 That is, $\\xi$ is also a left inverse to $\\overline{\\chi}$.\u00a0 Therefore, $K_0(\\mathfrak{M}) \\cong \\mathbb{Z}$. $\\Box$<\/p>\n Proposition 11:<\/strong>\u00a0 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$.<\/p>\n Proof:\u00a0<\/strong> \u00a0Let us prove the right-to-left implication first.\u00a0 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$.\u00a0 Hence, in $K_0(\\mathfrak{M})$ we have $0 = 1$ so that $K_0(\\mathfrak{M})$ is the zero ring.<\/p>\n For the other implication, we suppose that $K_0(\\mathfrak{M}) = 0$.\u00a0 Since $K_0(\\mathfrak{M}) = 0$, we have $0 = 1$ in $K_0(\\mathfrak{M})$.\u00a0 \u00a0\u00a0\u00a0By Proposition 10, we may assume that $\\mathfrak{M}$ is infinite.\u00a0 \u00a0In 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.\u00a0 In $K_0(\\mathfrak{M})$, $0 = [\\varnothing]$ and $1 = [\\{ \\ast \\}]$ for some $\\ast \\in M$.\u00a0 \u00a0 Thus, there is some definable set $Z$ disjoint from $\\{ \\ast \\}$ with $Z = Z \\cup \\varnothing \\approx Z \\cup \\{ \\ast \\} =: X$.\u00a0 Let $f:X \\to Z \\subseteq Z$ be a definable bijection between $X$ and $Z$ witnessing this equivalence.\u00a0 Then $f$ is a definable self-injection from $X$ to itself missing exactly one point.\u00a0 $\\Box$<\/p>\n <\/p>\n <\/p>\n <\/p>\n <\/p>\n","protected":false},"excerpt":{"rendered":" We have seen how to assign a natural number valued dimension to definable sets in o-minimal structures.\u00a0 There is a second integer valued invariant, which we will call the Euler characteristic.\u00a0 \u00a0In o-minimal expansions of fields, these two invariants characterize … Continue reading \n