The Euler Characteristic of a Category

Tom Leinster^{1}

Received: May 11, 2007 Revised: February 20, 2008

Communicated by Stefan Schwede

Abstract. The Euler characteristic of a finite category is defined and shown to be compatible with Euler characteristics of other types of object, including orbifolds. A formula is proved for the cardinality of a colimit of sets, generalizing the classical inclusion-exclusion formula. Both rest on a generalization of Rota’s Möbius inversion from posets to categories.

2000 Mathematics Subject Classification: 18F99, 55U99, 05C50, 57N65. Keywords and Phrases: Euler characteristic, finite category, inclusionexclusion, Möbius inversion, cardinality of colimit.

Introduction

We first learn of Euler characteristic as ‘vertices minus edges plus faces’, and later as an alternating sum of ranks of homology groups. But Euler characteristic is much more fundamental than these definitions make apparent, as has been made increasingly explicit over the last fifty years; it is something akin to cardinality or measure. More precisely, it is the fundamental dimensionless quantity associated with an object.

The very simplest context for Euler characteristic is that of finite sets, and of course the fundamental way to assign a quantity to a finite set is to count its elements. Euler characteristic of topological spaces can usefully be thought of as a generalization of cardinality; for instance, it obeys the same laws with respect to unions and products.

1Partially supported by a Nuffield Foundation award NUF-NAL 04 and an EPSRC Advanced Research Fellowship

Documenta Mathematica 13 (2008) 21–49

In a more sophisticated context, integral geometry, Euler characteristic also emerges clearly as the fundamental dimensionless invariant. A subset of ℝ^{n} is polyconvex if it is a finite union of compact convex subsets. Let V_{n} be the vector space of finitely additive measures, invariant under Euclidean transformations, defined on the polyconvex subsets of ℝ^{n}. Hadwiger’s Theorem [KR] states that dim V_{n} = n + 1. (See also [Sc2], and [MS] for an important application to materials science.) A natural basis consists of one d-dimensional measure for each d ∈ {0, …, n}: for instance, {Euler characteristic, perimeter, area} when n = 2. Thus, up to scalar multiplication, Euler characteristic is the unique dimensionless measure on polyconvex sets.

Schanuel [Sc1] showed that for a certain category of polyhedra, Euler characteristic is determined by a simple universal property, making its fundamental nature transparent.

All of the above makes clear the importance of defining and understanding Euler characteristic in new contexts. Here we do this for finite categories.

Categories are often viewed as large structures whose main purpose is organizational. However, some different viewpoints will be useful here. A combinatorial point of view is that a category is a directed graph (objects and arrows) equipped with some extra structure (composition and identities). We will concentrate on finite categories (those with only finitely many objects and arrows), which also suits the combinatorial viewpoint, and the composition and identities will play a surprisingly minor role.

A topological point of view is that a category can be understood through its classifying space. This is formed by starting with one 0-cell for each object, then gluing in one 1-cell for each arrow, one 2-cell for each commutative triangle, and so on.

Both of these points of view will be helpful in what follows. The topological perspective is heavily used in the sequel [BL] to this paper.

With topology in mind, one might imagine simply transporting the definition of Euler characteristic from spaces to categories via the classifying space functor, as with other topological invariants: given a category 𝔸, define χ(𝔸) as the Euler characteristic of the classifying space B𝔸. The trouble with this is that the Euler characteristic of B𝔸 is not always defined. Below we give a definition of the Euler characteristic of a category that agrees with the topological Euler characteristic when the latter exists, but is also valid in a range of situations when it does not. It is a rational number, not necessarily an integer.

A version of the definition can be given very succinctly. Let 𝔸 be a finite category; totally order its objects as a_{1}, …, a_{n}. Let Z be the matrix whose (i, j)-entry is the number of arrows from a_{i} to a_{j}. Let M = Z^{−1}, assuming that Z is invertible. Then χ(𝔸) is the sum of the entries of M. Of course, the reader remains to be convinced that this definition is the right one.

The foundation on which this work rests is a generalization of Möbius–Rota inversion (§1). Rota developed Möbius inversion for posets [R]; we develop it for categories. (A poset is viewed throughout as a category in which each homset has at most one element: the objects are the elements of the poset, and there is an arrow a b if and only if a ≤ b.) This leads, among other things, to a ‘representation formula’: given any functor known to be a sum of representables, the formula tells us the representation explicitly. This in turn can be used to solve enumeration problems, in the spirit of Rota’s paper.

However, the main application of this generalized Möbius inversion is to the theory of the Euler characteristic of a category (§2). We actually use a different definition than the one just given, equivalent to it when Z is invertible, but valid for a wider class of categories. It depends on the idea of the ‘weight’ of an object of a category. The definition is justified in two ways: by showing that it enjoys the properties that the name would lead one to expect (behaviour with respect to products, fibrations, etc.), and by demonstrating its compatibility with Euler characteristics of other types of structure (groupoids, graphs, topological spaces, orbifolds). There is an accompanying theory of Lefschetz number.

The technology of Möbius inversion and weights also solves another problem: what is the cardinality of a colimit? For example, the union of a family of sets and the quotient of a set by a free action of a group are both examples of colimits of set-valued functors, and there are simple formulas for their cardinalities. (In the first case it is the inclusion-exclusion formula.) We generalize, giving a formula valid for any shape of colimit (§3).

Rota and his school proved a large number of results on Möbius inversion for posets. As we will see repeatedly, many are not truly order-theoretic: they are facts about categories in general. In particular, important theorems in Rota’s original work [R] generalize from posets to categories (§4).

(The body of work on Möbius inversion in finite lattices is not, however, so ripe for generalization: a poset is a lattice just when the corresponding category has products, but a finite category cannot have products unless it is, in fact, a lattice.)

Other authors have considered different notions of Möbius inversion for categories; notably, there is that developed by Content, Lemay and Leroux [CLL] and independently by Haigh [H]. This generalizes both Rota’s notion for posets and Cartier and Foata’s for monoids [CF]. (Here a monoid is viewed as a oneobject category.) The relation between their approach and ours is discussed in §4. Further approaches, not discussed here, were taken by Dür [D] and Lück [Lü].

In the case of groupoids, our Euler characteristic of categories agrees with Baez and Dolan’s groupoid cardinality [BD]. The cardinality of the groupoid of finite sets and bijections is e = 2.718 …, and there are connections to exponential generating functions and the species of Joyal [J, BLL]. Paré has a definition of the cardinality of an endofunctor of the category of finite sets [Pa]; I do not know whether this can be related to the definition here of the Lefschetz number of an endofunctor.

The view of Euler characteristic as generalized cardinality is promoted in [Sc1], [BD] and [Pr1]. The appearance of a non-integral Euler characteristic is nothing new: see for instance Wall [Wl], Bass [Ba] and Cohen [Co], and the discussion of orbifolds in §2.

Ultimately it would be desirable to have the Euler characteristic of categories described by a universal property, as Schanuel did for polyhedra [Sc1]. For this, it may be necessary to relax the constraints of the present work, where for simplicity our categories are required to be finite and the coefficients are required to lie in the ring of rational numbers. Rather than asking, as below, ‘does this category have Euler characteristic (in ℚ)?’, we should perhaps ask ‘in what rig (semiring) does the Euler characteristic of this category lie?’ However, this is not pursued here.

Acknowledgements I thank John Baez, Andy Baker, Nick Gurski, Ieke Moerdijk, Urs Schreiber, Ivan Smith and Stephen Watson for inspiration and useful discussions. I am grateful to the Centre de Recerca Matemàtica, Barcelona, for their hospitality. I also thank the very helpful referee.

1 Möbius inversion

We consider a finite category 𝔸, writing ob 𝔸 for its set of objects and, when a and b are objects, 𝔸(a, b) for the set of maps from a to b.

Definition 1.1 We denote by R(𝔸) the ℚ-algebra of functions ob 𝔸 × ob 𝔸 ℚ, with pointwise addition and scalar multiplication, multiplication defined by

(θϕ)(a, c) = ∑_{b∈𝔸} θ(a, b)ϕ(b, c)

(θ, ϕ ∈ R(𝔸), a, c ∈ 𝔸), and the Kronecker δ as unit.

The zeta function ζ_{𝔸} = ζ ∈ R(𝔸) is defined by ζ(a, b) = |𝔸(a, b)|. If ζ is invertible in R(𝔸) then 𝔸 is said to have Möbius inversion; its inverse μ_{𝔸} = μ = ζ^{−1} is the Möbius function of 𝔸.

If a total ordering is chosen on the n objects of 𝔸 then R(𝔸) can be regarded as the algebra of n × n matrices over ℚ. The defining equations of the Möbius function are

∑_{b} μ(a, b)ζ(b, c) = δ(a, c) = ∑_{b} ζ(a, b)μ(b, c)

for all a, c ∈ 𝔸. By finite-dimensionality, μζ = δ if and only if ζμ = δ.

The definitions above could be made for directed graphs rather than categories, since they do not refer to composition. However, this generality seems to be inappropriate. For example, the definition of Möbius inversion will lead to a definition of Euler characteristic, and if we use graphs rather than categories then we obtain something other than ‘vertices minus edges’. Proposition 2.10 clarifies this point.

A different notion of Möbius inversion for categories has been considered; see §4.

Examples 1.2 a. Any finite poset A has Möbius inversion; this special case was investigated by Rota [R] and others. We may compute μ(a, c) by induction on the number of elements between a and c:

μ(a, c) = δ(a, c) − ∑_{b:a≤b<c} μ(a, b).

In particular, μ(a, c) = 0 unless a ≤ c, and μ(a, a) = 1 for all a. See also Theorem 1.4 and Corollary 1.5.

b. Let M be a finite monoid, regarded as a category with unique object ⋆. (The arrows of the category are the elements of the monoid, and composition in the category is multiplication in the monoid.) Then ζ(⋆, ⋆) = |M|, so μ(⋆, ⋆) = 1/|M|.

c. Let N ≥ 0. Write 𝔻_{N}^{inj} for the category with objects 0, …, N whose maps a b are the order-preserving injections {1, …, a} {1, …, b}. Then ζ(a, b) = \binom{b}{a}, and it is easily checked that μ(a, b) = (−1)^{b−a}\binom{b}{a}. If we use surjections instead of injections then ζ(a, b) = \binom{a−1}{b−1} and μ(a, b) = (−1)^{a−b}\binom{a−1}{b−1}.

A category with Möbius inversion must be skeletal (isomorphic objects must be equal), for otherwise the matrix of ζ would have two identical rows. The property of having Möbius inversion is not, therefore, invariant under equivalence of categories.

In general we cannot hope to just spot the Möbius function of a category. In 1.3–1.7 we make tools for computing Möbius functions. These cover large classes of categories, although not every finite skeletal category has Möbius inversion (1.11(d), (e)).

Let n ≥ 0, let 𝔸 be a category or a directed graph, and let a, b ∈ 𝔸. An n-path from a to b is a diagram

a = a_{0} ^{f_{1}} a_{1} ^{f_{2}} ⋯ ^{f_{n}} a_{n} = b  (1)

in 𝔸. It is a circuit if a = b, and (when 𝔸 is a category) nondegenerate if no f_{i} is an identity.

Lemma 1.3 The following conditions on a finite category 𝔸 are equivalent:

a. every idempotent in 𝔸 is an identity

b. every endomorphism in 𝔸 is an automorphism

c. every circuit in 𝔸 consists entirely of isomorphisms.

Proof (a) ⇒ (b) follows from the fact that if f is an element of a finite monoid then some positive power of f is idempotent. The other implications are straightforward. □

Theorem 1.4 Let 𝔸 be a finite skeletal category in which the only idempotents are identities. Then 𝔸 has Möbius inversion given by

μ(a, b) = ∑(−1)^{n}/|Aut(a_{0})| ⋯ |Aut(a_{n})|

where Aut(a) is the automorphism group of a ∈ 𝔸 and the sum runs over all n ≥ 0 and paths (1) for which a_{0}, …, a_{n} are all distinct.

Proof First observe that for a path (1) in 𝔸, if a_{0} ≠ a_{1} ≠ ⋯ ≠ a_{n} then the a_{i}s are all distinct. Indeed, if 0 ≤ i < j ≤ n and a_{i} = a_{j} then the sub-path running from a_{i} to a_{j} is a circuit, so by Lemma 1.3, f_{i+1} is an isomorphism, and by skeletality, a_{i} = a_{i+1}.

Now let a, c ∈ 𝔸 and define μ by the formula above. We have

∑_{b∈𝔸} μ(a, b)ζ(b, c) = μ(a, c)ζ(c, c) + ∑_{b:b≠c} μ(a, b)ζ(b, c)

= |Aut(c)| {μ(a, c) + ∑_{b:b≠c, g∈𝔸(b,c)} μ(a, b)/|Aut(c)|}

= |Aut(c)| {μ(a, c) + ∑(−1)^{n}/|Aut(a_{0})| ⋯ |Aut(a_{n})||Aut(c)|} ,

where the last sum is over all n ≥ 0 and paths

a = a_{0} ^{f_{1}} ⋯ ^{f_{n}} a_{n} = b ^{g} c

such that a_{0} ≠ ⋯ ≠ a_{n} ≠ c. By definition of μ, the term in braces collapses to 0 if a ≠ c and to 1/|Aut(a)| if a = c. Hence ∑_{b} μ(a, b)ζ(b, c) = δ(a, c), as required. □

Corollary 1.5 Let 𝔸 be a finite skeletal category in which the only endomorphisms are identities. Then 𝔸 has Möbius inversion given by

μ(a, b) = ∑_{n≥0}(−1)^{n}|{nondegenerate n-paths from a to b}| ∈ ℤ.

□

When 𝔸 is a poset, this is Philip Hall’s theorem (Proposition 3.8.5 of [St] and Proposition 6 of [R]).

An epi-mono factorization system (E, M) on a category 𝔸 consists of a class E of epimorphisms in 𝔸 and a class M of monomorphisms in 𝔸, satisfying axioms [FK]. The axioms imply that every map f in 𝔸 can be expressed as me for some e ∈ E and m ∈ M, and that this factorization is essentially unique: the other pairs (e′, m′) ∈ E × M satisfying m′e′ = f are those of the form (ie, mi^{−1}) where i is an isomorphism. Typical examples are the categories of sets, groups and rings, with E as all surjections and M as all injections.

Theorem 1.6 Let 𝔸 be a finite skeletal category with an epi-mono factorization system (E, M). Then 𝔸 has Möbius inversion given by

μ(a, b) = ∑(−1)^{n}/|Aut(a_{0})| ⋯ |Aut(a_{n})|

where the sum is over all n ≥ r ≥ 0 and paths (1) such that a_{0}, …, a_{r} are distinct, a_{r}, …, a_{n} are distinct, f_{1}, …, f_{r} ∈ M, and f_{r+1}, …, f_{n} ∈ E.

Proof The objects of 𝔸 and the arrows in E determine a subcategory of 𝔸, also denoted E; it satisfies the hypotheses of Theorem 1.4 and therefore has Möbius inversion. The same is true of M.

Any element α ∈ ℚ^{ob 𝔸} = ∏_{a∈𝔸} ℚ gives rise to an element of R(𝔸), also denoted α and defined by α(a, b) = δ(a, b)α(b). This defines a multiplicationpreserving map from ℚ^{ob 𝔸} to R(𝔸), where the multiplication on ℚ^{ob 𝔸} is coordinatewise. We have elements |Aut| and 1/|Aut| of ℚ^{ob 𝔸}, where, for instance, |Aut|(a) = |Aut(a)|.

By the essentially unique factorization property, ζ_{𝔸} = ζ_{E} · \frac{1}{|Aut|} ·ζ_{M}. Hence 𝔸 has Möbius function μ_{𝔸} = μ_{M} · |Aut| · μ_{E}. Theorem 1.4 applied to μ_{M} and μ_{E} then gives the formula claimed. □

Example 1.7 Let N ≥ 0 and write 𝔽_{N} for the full subcategory of Set with objects 1, …, N, where n denotes a (chosen) n-element set. Let E be the set of surjections in 𝔽_{N} and M the set of injections; then (E, M) is an epi-mono factorization system. Theorem 1.6 gives a formula for the inverse of the matrix (i^{j})_{i,j}. For instance, take N = 3; then μ(1, 2) may be computed as follows:

Paths  Contribution to sum
1 ^{2} 2  −2/1!2! = −1
1 ^{3} 3 ^{6} [figure] 2  3 · 6/1!3!2! = 3/2
1 ^{2} 2 ^{6} 3 ^{6} [figure] 2 −2 · 6 · 6/1!2!3!2! = −3

Here ‘1 ^{2} 2’ means that there are 2 monomorphisms from 1 to 2, ‘3 ^{6} [figure] 2’ that there are 6 epimorphisms from 3 to 2, etc. Hence μ(1, 2) = −1+3/2−3 = −5/2.

One of the uses of the Möbius function is to calculate Euler characteristic (§2). Another is to calculate representations. Specifically, suppose that we have a Set-valued functor known to be familially representable, that is, a coproduct of representables. The Yoneda Lemma tells us that the family of representing objects is unique (up to isomorphism). But if we have Möbius inversion, there is actually a formula for it:

Proposition 1.8 Let 𝔸 be a finite category with Möbius inversion and let X : 𝔸 Set be a functor satisfying

X ≅ ∑_{a} r(a)𝔸(a, −)

for some natural numbers r(a) (a ∈ 𝔸). Then

r(a) = ∑_{b} |X(b)|μ(b, a)

for all a ∈ 𝔸.

In the first formula, ∑ denotes coproduct of Set-valued functors.

Proof Follows from the definition of Möbius function. □

In the spirit of Rota’s programme, this can be applied to solve counting problems, as illustrated by the following standard example.

Example 1.9 A derangement is a permutation without fixed points. We calculate d_{n}, the number of derangements of n letters.

Fix N ≥ 0. Take the category 𝔻_{N}^{inj} of Example 1.2(c) and the functor S : 𝔻_{N}^{inj} Set defined as follows: S(n) is S_{n}, the underlying set of the nth symmetric group, and if f ∈ 𝔻_{N}^{inj}(m, n) and τ ∈ S_{m}, the induced permutation S_{f}(τ) ∈ S_{n} acts as τ on the image of f and fixes all other points. Any permutation consists of a derangement together with some fixed points, so there is an isomorphism of sets

S_{n} ≅ ∑_{m} d_{m}𝔻_{N}^{inj}(m, n)

where ∑ denotes disjoint union. Then by Proposition 1.8 and Example 1.2(c),

d_{n} = ∑_{m} |S_{m}|μ(m, n) = ∑_{m} m!(−1)^{n−m}\binom{n}{m} = n! (\frac{1}{0!} − \frac{1}{1!} + ⋯ + \frac{(−1)^{n}}{n!} ) .

To set up the theory of Euler characteristic we will not need the full strength of Möbius invertibility; the following suffices.

Definition 1.10 Let 𝔸 be a finite category. A weighting on 𝔸 is a function k^{•} : ob 𝔸 ℚ such that for all a ∈ 𝔸,

∑_{b} ζ(a, b)k^{b} = 1.

A coweighting k_{•} on 𝔸 is a weighting on 𝔸^{op}.

Note that 𝔸 has Möbius inversion if and only if it has a unique weighting, if and only if it has a unique coweighting; they are given by

k^{a} = ∑_{b} μ(a, b), k_{b} = ∑_{a} μ(a, b).

Examples 1.11 a. Let 𝕃 be the category

[figure: b_{1}; a; b_{2}.]

Then the unique weighting k^{•} on 𝕃 is (k^{a}, k^{b_{1}}, k^{b_{2}}) = (−1, 1, 1).

b. Let M be a finite monoid, regarded as a category with unique object ⋆. Again there is a unique weighting k^{•}, with k^{⋆} = 1/|M|.

c. If 𝔸 has a terminal object 1 then δ(−, 1) is a weighting on 𝔸.

d. A finite category may admit no weighting at all. (This can happen even when the category is Cauchy-complete, in the sense defined in the Appendix.) An example is the category 𝔸 with objects and arrows

[figure: a_{1}; a_{2}; a_{3}; a_{4}; f_{12},g_{12}; f_{21},g_{21}; f_{13}; f_{31}; f_{23}; f_{32}; f_{34}; f_{14}; f_{24}; g_{24}; 1; f_{11}; 1; f_{22}; f_{44}=1; f_{33}=1]
where if a_{i}  ^{p} a_{j}  ^{q} a_{k} and neither p nor q is an identity then

q^{∘} p = f_{ik}.

e. A category may certainly have more than one weighting: for instance, if 𝔸 is the category consisting of two objects and a single isomorphism between them, a weighting on 𝔸 is any pair of rational numbers whose sum is 1. But even a skeletal category may admit more than one weighting. Indeed, the full subcategories 𝔹 = {a_{1}, a_{2}} and ℂ = {a_{1}, a_{2}, a_{3}} of the category 𝔸 of the previous example both have a 1-dimensional space of weightings.

In contrast to Möbius invertibility, the property of admitting at least one weighting is invariant under equivalence:

Lemma 1.12 Let 𝔸 and 𝔹 be equivalent finite categories. Then 𝔸 admits a weighting if and only if 𝔹 does.

Proof Let F : 𝔸 𝔹 be an equivalence. Given a ∈ 𝔸, write C_{a} for the number of objects in the isomorphism class of a. Take a weighting l^{•} on 𝔹 and put k^{a} = (∑_{b:b≅F (a)} l^{b})/C_{a}. I claim that k^{•} is a weighting on 𝔸.

To prove this, choose representatives a_{1}, …, a_{m} of the isomorphism classes of objects of 𝔸; then F (a_{1}), …, F (a_{m}) are representatives of the isomorphism classes of objects of 𝔹. Let a′ ∈ 𝔸. For any a ∈ 𝔸, the numbers ζ(a′, a) and k^{a} depend only on the isomorphism class of a. Hence

∑_{a∈𝔸} ζ(a′, a)k^{a} = ∑_{i=1}^{m} ∑_{a:a≅a_{i}} ζ(a′, a)k^{a}

= ∑_{i=1}^{m} C_{a_{i}}ζ(a′, a_{i})k^{a_{i}}

= ∑_{i=1}^{m} ∑_{b:b≅F (a_{i})} ζ(a′, a_{i})l^{b}
= ∑_{b∈𝔹} ζ(F (a′), b)l^{b}
= 1,

as required. □

Weightings and Möbius functions are compatible with sums and products of categories. We write ∑_{i∈I} 𝔸_{i} for the sum of a family (𝔸_{i})_{i∈I} of categories, also called the coproduct or disjoint union and written ∐_{i∈I} 𝔸_{i}. The following lemma is easily verified.

Lemma 1.13 Let n ≥ 0 and let 𝔸_{1}, …, 𝔸_{n} be finite categories.

a. If each 𝔸_{i} has a weighting ki^{•} then ∑_{i} 𝔸_{i} has a weighting l^{•} given by l^{a} = k_{i}^{a} whenever a ∈ 𝔸_{i}. If each 𝔸_{i} has Möbius inversion then so does ∑_{i} 𝔸_{i}, where for a ∈ 𝔸_{i} and b ∈ 𝔸_{j},

μ_{∑ 𝔸_{k}}(a, b) = \{ \begin{matrix}μ_{𝔸_{i}}(a, b) & if i = j \\ 0 & otherwise. \end{matrix}

b. If each 𝔸_{i} has a weighting ki^{•} then ∏_{i} 𝔸_{i} has a weighting l^{•} given by l^{(a_{1},...,a_{n})} = k_{1}^{a_{1}} ⋯ k_{n}^{a_{n}}. If each 𝔸_{i} has Möbius inversion then so does ∏_{i} 𝔸_{i}, with

μ_{∏ 𝔸_{i}}((a_{1}, …, a_{n}), (b_{1}, …, b_{n})) = μ_{𝔸_{1}}(a_{1}, b_{1}) ⋯ μ_{𝔸_{n}}(a_{n}, b_{n}).

□

Thinking of R(𝔸) as a matrix algebra (as described after Definition 1.1), the part of (a) concerning Möbius inversion merely says that the inverse of a block sum of matrices is the block sum of the inverses.

To every Set-valued functor X there is assigned a ‘category of elements’ 𝔼 (X). (See the Appendix for a review of definitions.) This is also true of functors X taking values in Cat, the category of small categories and functors, even when X is only a weak or ‘pseudo’ functor. We say that a Set- or Catvalued functor X is finite if 𝔼 (X) is finite. When the domain category 𝔸 is finite, this just means that each set or category X(a) is finite.

Lemma 1.14 Let 𝔸 be a finite category and X : 𝔸 Cat a finite weak functor. Suppose that we have weightings on 𝔸 and on each X(a), all written k^{•}. Then there is a weighting on 𝔼 (X) defined by k^{(a,x)} = k^{a}k^{x} (a ∈ 𝔸, x ∈ X(a)).

Proof Let a ∈ 𝔸 and x ∈ X(a). Then

∑_{(b,y)∈𝔼(X)} ζ((a, x), (b, y))k^{b}k^{y} = ∑_{b} ∑_{f∈𝔸(a,b)} ( ∑_{y∈X(b)} ζ((X(f))x, y)k^{y}) k^{b}

= ∑_{b} ζ(a, b)k^{b} = 1.

□

This result will be used to show how Euler characteristic behaves with respect to fibrations.

2 Euler characteristic

In this section, the Euler characteristic of a category is defined and its basic properties are established. The definition is justified by a series of propositions showing its compatibility with the Euler characteristics of other types of object: graphs, topological spaces, and orbifolds. There follows a brief discussion of the Lefschetz number of an endofunctor.

Lemma 2.1 Let 𝔸 be a finite category, k^{•} a weighting on 𝔸, and k_{•} a coweighting on 𝔸. Then ∑_{a} k^{a} = ∑_{a} k_{a}.

Proof

∑_{b} k^{b} = ∑_{b} (∑_{a} k_{a}ζ(a, b)) k^{b} = ∑_{a} k_{a} (∑_{b} ζ(a, b)k^{b}) = ∑_{a} k_{a}.

□

If 𝔸 admits a weighting but no coweighting then ∑_{a} k^{a} may depend on the weighting k^{•} chosen: see Example 4.8 of [BL].

Definition 2.2 A finite category 𝔸 has Euler characteristic if it admits both a weighting and a coweighting. Its Euler characteristic is then

χ(𝔸) = ∑_{a} k^{a} = ∑_{a} k_{a} ∈ ℚ

for any weighting k^{•} and coweighting k_{•}.

With the Gauss–Bonnet Theorem in mind, one might think of weight as an analogue of curvature: summed over the whole structure, it yields the Euler characteristic.

Any category 𝔸 with Möbius inversion has Euler characteristic, χ(𝔸) = ∑_{a,b} μ(a, b), as in the Introduction.

Examples 2.3 a. If 𝔸 is a finite discrete category then χ(𝔸) = |ob 𝔸|.

b. If M is a finite monoid then χ(M) = 1/|M|. (We continue to view monoids as one-object categories.) When M is a group, this can be understood as follows: M acts freely on the contractible space EM, which has Euler characteristic 1; one would therefore expect the quotient space BM to have Euler characteristic 1/|M|. (Compare [Wl] and [Co].)

c. By Corollary 1.5, a finite poset A has Euler characteristic ∑_{n≥0}(−1)^{n}c_{n} ∈ ℤ, where c_{n} is the number of chains in A of length n. (See [Pu], [Fo], [R] and [Fa] for connections with poset homology, and §4 for further comparisons with the Rota theory.) More generally, the results of §1 lead to formulas for the Euler characteristic of any finite category that either has no non-trivial idempotents or admits an epi-mono factorization system.

For example, let 𝔸 be a category with no non-trivial idempotents. Let 𝔹 be a skeleton of 𝔸, that is, a full subcategory containing exactly one object from each isomorphism class of 𝔸. Theorem 1.4 tells us that 𝔹 has Möbius inversion and gives us a formula for its Möbius function, hence for its Euler characteristic. Proposition 2.4(b) below then implies that 𝔸 has Euler characteristic, equal to that of 𝔹.

d. By 1.11(c) and its dual, if 𝔸 has Euler characteristic and either an initial or a terminal object then χ(𝔸) = 1; moreover, if 𝔸 has both an initial and a terminal object then it does have Euler characteristic. This applies, for instance, to the category ℂ of 1.11(e). Hence having Möbius inversion is a strictly stronger property than having Euler characteristic, even for skeletal categories.

e. Euler characteristic is not invariant under Morita equivalence. Recall that categories 𝔸 and 𝔹 are Morita equivalent if their presheaf categories [𝔸^{op}, Set] and [𝔹^{op}, Set] are equivalent; see [Bo], for instance. Equivalent categories are Morita equivalent, but not conversely. For instance, take 𝔸 to be the two-element monoid consisting of the identity and an idempotent, and 𝔹 to be the category generated by objects and arrows

b_{1} [figure: i; s] b_{2}

subject to si = 1. Then 𝔸 and 𝔹 are Morita equivalent but not equivalent. Moreover, their Euler characteristics are different: χ(𝔸) = 1/2 by (b), but χ(𝔹) = 1 by (d).

Clearly χ(𝔸^{op}) = χ(𝔸), one side being defined when the other is. The next few propositions set out further basic properties of Euler characteristic.

Proposition 2.4 Let 𝔸 and 𝔹 be finite categories.

a. If there is an adjunction 𝔸 [figure] 𝔹 and both 𝔸 and 𝔹 have Euler characteristic then χ(𝔸) = χ(𝔹).

b. If 𝔸 ≃ 𝔹 then 𝔸 has Euler characteristic if and only if 𝔹 does, and in that case χ(𝔸) = χ(𝔹).

In (a), it may be that one category has Euler characteristic but the other does not: consider, for instance, the unique functor from the category 𝔸 of 1.11(d) to the terminal category.

Proof

a. Suppose that 𝔸 [figure: F; G] 𝔹 with F ⊣ G. Then ζ(F (a), b) = ζ(a, G(b)) for all

a ∈ 𝔸, b ∈ 𝔹; write ζ(a, b) for their common value. Take a coweighting k_{•} on 𝔸 and a weighting k^{•} on 𝔹. Then ∑_{a} k_{a} = ∑_{b} k^{b} by the same proof as that of Lemma 2.1.

b. The first statement follows from Lemma 1.12 and its dual, and the second from (a). □

Example 2.5 If 𝔹 is a category with an initial or a terminal object then χ(𝔸^{𝔹}) = χ(𝔸) for all 𝔸, provided that both Euler characteristics exist. Indeed, if 0 is initial in 𝔹 then evaluation at 0 is right adjoint to the diagonal functor 𝔸 𝔸^{𝔹}.

Proposition 2.6 Let n ≥ 0 and let 𝔸_{1}, …, 𝔸_{n} be finite categories that all have Euler characteristic. Then ∑_{i} 𝔸_{i} and ∏_{i} 𝔸_{i} have Euler characteristic, with

χ (∑_{i} 𝔸_{i}) = ∑_{i} χ(𝔸_{i}), χ (∏_{i} 𝔸_{i}) = ∏_{i} χ(𝔸_{i}).

Proof Follows from Lemma 1.13. □

Example 2.7 Let 𝔸 be a finite groupoid. Choose one object a_{i} from each connected-component of 𝔸, and write G_{i} for the automorphism group of a_{i}. Then 𝔸 ≃ ∑_{i} G_{i}, so by 2.3(b), 2.4(b) and 2.6, we have χ(𝔸) = ∑_{i} 1/|G_{i}|. This is what Baez and Dolan call the cardinality of the groupoid 𝔸 [BD].

One might also ask whether χ(𝔸^{𝔹}) = χ(𝔸)^{χ(𝔹)}. By 2.3(d), 2.5 and 2.6, the answer is yes if every connected-component of 𝔹 has an initial or a terminal object (and all the Euler characteristics exist). But in general the answer is no: for instance, take 𝔸 to be the 2-object discrete category and 𝔹 to be the category of 3.4(b). See also Propp [Pr2], Speed [Sp], and §5, 6 of Rota [R].

An important property of topological Euler characteristic is its behaviour with respect to fibre bundles (or more generally, fibrations). Take a space A with connected-components A_{1}, …, A_{n}, take a fibre bundle E over A, and write X_{i} for the fibre in the ith component. Then under suitable hypotheses, χ(E) = ∑_{i} χ(A_{i})χ(X_{i}).

There is an analogy between topological fibrations and categorical fibrations, which are functors satisfying a certain condition. (In this discussion I will use ‘fibration’ to mean what is usually called an opfibration; the difference is inessential.) The crucial property of fibrations of categories is that for any category 𝔸, the fibrations with codomain 𝔸 correspond naturally to the weak functors 𝔸 Cat. Given a fibration P : 𝔼 𝔸, define a functor X : 𝔸 Cat by taking X(a), for each a ∈ 𝔸, to be the fibre over a: the subcategory of 𝔼 whose objects e are those satisfying P (e) = a and whose arrows f are those satisfying P (f) = 1_{a}. Conversely, given a weak functor X : 𝔸 Cat, the corresponding fibration is the category of elements 𝔼 (X) together with the projection functor to 𝔸. For details, see [Bo], for instance.

The formula for the Euler characteristic of a fibre bundle has a categorical analogue. Since in general the fibres of a fibration over 𝔸 vary within each connected-component of 𝔸, the formula for categories is more complicated. We state the result in terms of Cat-valued functors rather than fibrations; the proof follows from Lemma 1.14.

Proposition 2.8 Let 𝔸 be a finite category and X : 𝔸 Cat a finite weak functor. Let k^{•} be a weighting on 𝔸 and suppose that 𝔼 (X) and each X(a) have Euler characteristic. Then

χ(𝔼 (X)) = ∑_{a} k^{a}χ(X(a)).

□

Examples 2.9 a. When X is a finite Set-valued functor, χ(𝔼 (X)) = ∑_{a} k^{a}|X(a)|. For example, let M be a finite monoid. A finite functor X : M Set is a finite set S with a left M-action. Following [BD], we write 𝔼 (X) as S//M, the lax quotient of S by M. (Its objects are the elements of S, and the arrows s s′ are the elements m ∈ M satisfying ms = s′.) Then χ(S//M) = |S|/|M|. b. Define a sequence (𝕊^{n})_{n≥−1} of categories inductively as follows. 𝕊^{−1} is

empty. Let 𝕃 be the category of 1.11(a); define X : 𝕃 Cat by X(a) = 𝕊^{n−1} and X(b_{1}) = X(b_{2}) = 1 (the terminal category); put 𝕊^{n} = 𝔼 (X). Then explicitly, 𝕊^{n} is the poset

[figure: c_{0}; c_{1}; ⋯; c_{n}; d_{0}; d_{1}; ⋯; d_{n}.]

(If we take the usual expression of the topological n-sphere S^{n} as a CWcomplex with two cells in each dimension ≤ n then 𝕊^{n} is the set of cells ordered by inclusion; S^{n} is the classifying space of 𝕊^{n}.)

Each 𝕊^{n} is a poset, so has Euler characteristic. By Proposition 2.8,

χ(𝕊^{n}) = −χ(𝕊^{n−1}) + 2χ(1) = 2 − χ(𝕊^{n−1})

for all n ≥ 0; also χ(𝕊^{−1}) = 0. Hence χ(𝕊^{n}) = 1 + (−1)^{n}.

The next three propositions show how the Euler characteristics of various types of structure are compatible with that of categories.

First, Euler characteristic of categories extends Euler characteristic of graphs. More precisely, let G = (G_{1} [figure] G_{0}) be a directed graph, where G_{1} is the set of edges and G_{0} the set of vertices. We will show that if F (G) is the free category on G then χ(F (G)) = |G_{0}| − |G_{1}|. This only makes sense if F (G) is finite, which is the case if and only if G is finite and circuit-free; then F (G) is also circuit-free. (A directed graph is circuit-free if it contains no circuits of non-zero length, and a category is circuit-free if every circuit consists entirely of identities.)

Proposition 2.10 Let G be a finite circuit-free directed graph. Then χ(F (G)) is defined and equal to |G_{0}| − |G_{1}|.

Proof Given a, b ∈ G_{0}, write ζ_{G}(a, b) for the number of edges from a to b in G. Then ζ_{F (G)} = ∑_{n≥0} ζ_{G}^{n} in R(F (G)), the sum being finite since G is circuit-free. Hence μ_{F (G)} = δ − ζ_{G}, and the result follows. □

This suggests that in the present context, it is more fruitful to view a graph as a special category (via F) than a category as a graph with structure. Compare the comments after Definition 1.1.

The second result compares the Euler characteristics of categories and topological spaces. We show that under suitable hypotheses, χ(B𝔸) = χ(𝔸), where B𝔸 is the classifying space of a category 𝔸 (that is, the geometric realization of its nerve N𝔸). To ensure that B𝔸 has Euler characteristic, we assume that N𝔸 contains only finitely many nondegenerate simplices; then

χ(B𝔸) = ∑_{n≥0}(−1)^{n}|{nondegenerate n-simplices in N𝔸}|.

An n-simplex in N𝔸 is just an n-path in 𝔸, and is nondegenerate in the sense of simplicial sets if and only if it is nondegenerate as a path, so 𝔸 must contain only finitely many nondegenerate paths. This is the case if and only if 𝔸 is circuit-free, if and only if 𝔸 is skeletal and contains no endomorphisms except identities. So by Corollary 1.5, we have:

Proposition 2.11 Let 𝔸 be a finite skeletal category containing no endomorphisms except identities. Then χ(B𝔸) is defined and equal to χ(𝔸). □

For the final compatibility result, consider the following schematic diagrams:

{triangulated manifolds}

[figure: {posets}; χ; ℤ; χ]

{triangulated orbifolds}

[figure: {categories}; χ; ℚ.; χ]

On the left, we start with a compact manifold M equipped with a finite triangulation. As shown in §3.8 of [St], the topological Euler characteristic of M is equal to the Euler characteristic of the poset of simplices in the triangulation, ordered by inclusion. We generalize this result from manifolds to orbifolds, which entails replacing posets by categories and ℤ by ℚ.

Let M be a compact orbifold equipped with a finite triangulation. (See [MP] for definitions.) The simplices in the triangulation form a poset P, and if p ∈ P is a d-dimensional simplex then ↓ p = {q ∈ P | q ≤ p} is isomorphic to the poset ℙ_{d+1} of nonempty subsets of {1, …, d+1}, with p ∈↓p corresponding to {1, …, d + 1} ∈ ℙ_{d+1}. Every p ∈ P has a stabilizer group G(p), and

χ(M) = ∑_{p∈P}(−1)^{dim p}/|G(p)|.

On the other hand, the groups G(p) fit together to form a complex of finite groups on P^{op}, that is, a weak functor G : P^{op} Cat taking values in finite groups (regarded as one-object categories) and injective homomorphisms; see §3 of [M]. This gives a finite category 𝔼 (G). For example, when M is a manifold, each group G(p) is trivial and 𝔼 (G) ≅ P.

The following result is joint with Ieke Moerdijk.

Proposition 2.12 Let M be a compact orbifold equipped with a finite triangulation. Let G be the resulting complex of groups. Then χ(𝔼 (G)) is defined and equal to χ(M).

Proof Every arrow in 𝔼 (G) is monic, so by Theorem 1.4, 𝔼 (G) has Euler characteristic. Moreover, P is a finite poset, so has a unique coweighting k_{•}, and χ(𝔼 (G)) = ∑_{p} k_{p}/|G(p)| by the dual of Proposition 2.8.

The coweight of p in P is equal to the coweight of p in ↓p ≅ ℙ_{d+1}, where d = dim p. The unique coweighting k_{•} on ℙ_{d+1} is given by k_{J} = (−1)^{|J|−1}, so k_{p} = (−1)^{(d+1)−1} = (−1)^{dim p}. The result follows. □

We now turn to the theory of Lefschetz number. Let F : 𝔸 𝔸 be an endofunctor of a category 𝔸. The category Fix F has as objects the (strict) fixed points of F, that is, the objects a ∈ 𝔸 such that F (a) = a; a map a b in Fix F is a map f : a b in 𝔸 such that F (f) = f.

Definition 2.13 Let F be an endofunctor of a finite category. Its Lefschetz number L(F) is χ(Fix F), when this exists.

The Lefschetz number is, then, the sum of the (co)weights of the fixed points. This is analogous to the standard Lefschetz fixed point formula, (co)weight playing the role of index. The following results further justify the definition.

Proposition 2.14 Let 𝔸 be a finite category.

a. L(1_{𝔸}) = χ(𝔸), one side being defined if and only if the other is.

b. If 𝔹 is another finite category and 𝔸 [figure: F; G] 𝔹 are functors then L(GF) =

L(F G), one side being defined if and only if the other is.

c. Let F : 𝔸  𝔸 and write BF : B𝔸  B𝔸 for the induced map on

the classifying space of 𝔸. If 𝔸 is skeletal and contains no endomorphisms except identities then L(F) = L(BF), with both sides defined.

In the special case that 𝔸 is a poset, part (c) is Theorem 1.1 of [BB].

Proof For (a) and (b), just note that Fix 1_{𝔸} ≅ 𝔸 and Fix GF ≅ Fix F G. For (c), recall from the proof of Proposition 2.11 that N𝔸 has only finitely many nondegenerate simplices; then

L(BF) = ∑_{n≥0}(−1)^{n}|{nondegenerate n-simplices in N𝔸 fixed by NF }|
= ∑_{n≥0}(−1)^{n}|{nondegenerate n-paths in Fix F }|
= L(F),

using Corollary 1.5 in the last step. □

An algebra for an endofunctor F of 𝔸 is an object a ∈ 𝔸 equipped with a map h : F (a) a. With the evident structure-preserving morphisms, algebras for F form a category Alg F. There is a dual notion of coalgebra (where now h : a F (a)), giving a category Coalg F.

Proposition 2.15 Let F be an endofunctor of a finite skeletal category 𝔸 containing no endomorphisms except identities. Then χ(Alg F) = L(F) = χ(Coalg F), with all three terms defined.

Proof First observe that 𝔸 is circuit-free. Now, the inclusion Fix F Alg F has a right adjoint R: given an algebra (a, h), circuit-freeness implies that F^{N}(a) is a fixed point for all sufficiently large N, and R(a, h) = F^{N}(a). The Euler characteristics of Alg F and Fix F exist, by Corollary 1.5, and are equal, by Proposition 2.4(a). The statement on coalgebras follows by duality.

□

For example, if f is an endomorphism of a finite poset A then the subposets

{a ∈ A | f(a) ≤ a},  {a ∈ A | f(a) = a},  {a ∈ A | f(a) ≥ a}

all have the same Euler characteristic.

The theory of Euler characteristic presented here can be extended in at least two directions.

First, we can relax the finiteness assumption. For instance, the category of finite sets and bijections should have Euler characteristic ∑_{n=0}^{∞} 1/|S_{n}| = e, as observed in [BD]. See the remarks after Corollary 4.3.

Second, the Euler characteristic of categories is defined in terms of the cardinality of finite sets, and the theory can be generalized to V-enriched categories whenever there is a suitable notion of cardinality or Euler characteristic of objects of V. For example, V might be the category of finite-dimensional vector spaces, with dimension playing the role of cardinality, and this leads to an Euler characteristic for finite linear categories. For another example, a 0category is a set and an n-category is a category enriched in (n − 1)-categories; iterating, we obtain an Euler characteristic for finite n-categories. In particular, if S^{n} is the n-category consisting of two parallel n-cells then χ(S^{n}) = 1+(−1)^{n}.

3 The cardinality of a colimit

The main theorem of this section generalizes the formulas

|X ∪ Y | = |X| + |Y | − |X ∩ Y |, |S/G| = |S|/|G|

where X and Y are finite subsets of some larger set and S is a finite set acted on freely by a finite group G.

Take a finite functor X : 𝔸 Set. The colimit (or direct limit, or inductive limit) lim_{⟶} X can be viewed as the gluing-together of the sets X(a). Its cardinality depends on the way in which these sets are glued together, which in turn is determined by the action of X on arrows, so in general there is no formula for |lim_{⟶} X| purely in terms of the cardinalities |X(a)| (a ∈ 𝔸).

Suppose, however, that we are in the extreme case that there are no unforced equations of the type (X(f))(x) = (X(f′))(x′), where f and f′ are arrows in 𝔸. For pushouts, this means that the two functions along which we are pushing out are injective; when 𝔸 is a group G, so that X is a set with a G-action, it means that the action is free. In this extreme case, |lim_{⟶} X| can be calculated as a weighted sum of the cardinalities |X(a)|.

We now make this precise. Recall from §1 that a Set-valued functor is said to be familially representable if it is a sum of representables.

Proposition 3.1 Let 𝔸 be a finite category and k^{•} a weighting on 𝔸. If X : 𝔸 Set is finite and familially representable then |lim_{⟶} X| = ∑_{a} k^{a}|X(a)|.

Proof The result holds if X is representable, since then |lim_{⟶} X| = 1. On the other hand, the class of functors X for which the conclusion holds is clearly closed under finite sums. □

To make use of this, we need a way of recognizing familially representable functors. Carboni and Johnstone [CJ1, CJ2] show that when A satisfies certain hypotheses, including having all limits, a functor A Set is familially representable if and only if it preserves connected limits. This does not help directly, because our categories 𝔸 are finite, and a finite category does not have even all finite limits unless it is a lattice.

However, a standard philosophy applies: when 𝔸 fails to have all limits of a certain type, it is rarely useful to consider the functors 𝔸 Set preserving limits of that type; the correct substitute is the class of functors that are suitably ‘flat’. The notion of flatness appropriate here will be called nondegeneracy. (This is unrelated to the usage of ‘nondegenerate’ in §1.)

Definition 3.2 Let 𝔸 be a small category. A functor X : 𝔸 Set is nondegenerate if 𝔼 (X) has the following diagram-completion properties:

[figure: ·; ·; .; .; .; .; .; .; .; .; .; ·; ·; .; .; .; .; .; .; .; .; .; ·; .; .; .; .; .; .; .; .; .; .; ·; ·]

Explicitly, this means that

a. given arrows a ^{f} b ^{f′} a′ in 𝔸 and x ∈ X(a), x′ ∈ X(a′) satisfying

(X(f))(x) = (X(f′))(x′), there exist arrows a ^{g} c ^{g′} a′ and z ∈ X(c) satisfying fg = f′g′, (X(g))(z) = x, and (X(g′))(z) = x′, and

b. given arrows a [figure: f; f′] b in 𝔸 and x ∈ X(a) satisfying (X(f))(x) =

(X(f′))(x), there exist c ^{g} a and z ∈ X(c) satisfying fg = f′g and (X(g))(z) = x.

This is the most concrete form of the definition. For further explanation, see the Appendix; for references, see [Ln]. In the Appendix (Lemma 5.2) it is shown that under suitable hypotheses, nondegeneracy is equivalent to familial representability, and from this we deduce a more applicable form of Proposition 3.1:

Theorem 3.3 Let 𝔸 be a finite Cauchy-complete category and k^{•} a weighting on 𝔸. If X : 𝔸 Set is finite and nondegenerate then |lim_{⟶} X| = ∑_{a} k^{a}|X(a)|. □

Using the fact that lim_{⟶} X is the set of connected-components of 𝔼 (X), this may be rephrased as |π_{0}(𝔼 (X))| = ∑ k^{a}|X(a)|. On the other hand, Proposition 2.8 implies that χ(𝔼 (X)) = ∑ k^{a}|X(a)|. Indeed, under the hypotheses of the Theorem, X is familially representable, so each connected-component of 𝔼 (X) has an initial object, so χ(𝔼 (X)) = |π_{0}(𝔼 (X))|.

Examples 3.4 a. Let 𝕃 be the category of 1.11(a). A functor X : 𝕃 Set is nondegenerate if and only if both functions X(a) X(b_{i}) are injective. In that case, Theorem 3.3 says that

|X(b_{1}) +_{X(a)} X(b_{2})| = |X(b_{1})| + |X(b_{2})| − |X(a)|

where the set on the left-hand side is a pushout.

b. Let 𝔹 be the category (a [figure: f; g] b). A functor X : 𝔹 Set is non-

degenerate if and only if the two functions X(f), X(g) are injective and have disjoint images. The unique weighting k^{•} on 𝔹 is (k^{a}, k^{b}) = (−1, 1), and

|(X(b))/ ∼ | = |X(b)| − |X(a)|

where ∼ is the equivalence relation generated by (X(f))(x) ∼ (X(g))(x) for all x ∈ X(a).

c. Let G be a group. A functor X : G Set is a set S equipped with a left G-action; the functor is nondegenerate if and only if the action is free. Theorem 3.3 then says that the number of orbits is |S|/|G|.

d. The Theorem can be viewed as a generalized inclusion-exclusion principle. (Compare [R].) Let n ≥ 0 and let ℙ_{n} be the poset of nonempty subsets of {1, …, n}, ordered by inclusion. (So ℙ_{2}^{op} is the category 𝕃 of (a).) Its unique coweighting k_{•} is defined by k_{J} = (−1)^{|J|−1}. Given subsets S_{1}, …, S_{n} of some set, there is a nondegenerate functor X : ℙ_{n}^{op} Set defined on objects by X(J) = ⋂_{j∈J} S_{j} and on maps by inclusion. Theorem 3.3 gives the inclusion-exclusion formula,

|S_{1} ∪ ⋯ ∪ S_{n}| = ∑_{∅≠J⊆{1,...,n}}(−1)^{|J|−1} | ⋂_{j∈J} S_{j}| .

Corollary 3.5 Let 𝔸 be a finite Cauchy-complete category admitting a weighting. Let X, Y : 𝔸 Set be finite nondegenerate functors satisfying |X(a)| = |Y (a)| for all a ∈ 𝔸. Then |lim_{⟶} X| = |lim_{⟶} Y |. □

The condition that 𝔸 admits a weighting cannot be dropped: consider the category 𝔸 of Example 1.11(d) and the functors X = 𝔸(a_{1}, −) + 𝔸(a_{4}, −), Y = 𝔸(a_{2}, −).

If 𝔸 not only has a weighting but admits Möbius inversion then a sharper statement can be made (Proposition 1.8).

4 Relations with Rota’s theory

In 1964, Gian-Carlo Rota published his seminal paper [R] on Möbius inversion in posets. The name is motivated as follows: in the poset of positive integers ordered by divisibility, μ(a, b) = μ(b/a) whenever a divides b, where the μ on the right-hand side is the classical Möbius function. He was not the first to define Möbius inversion in posets—Weisner, Hall, and Ward preceded him—but Rota’s contribution was the decisive one; in particular, he realized the power of the method in enumerative combinatorics. The history of Möbius inversion is well described in [R], [G] and [St].

In this section we discover that some of the principal results in Rota’s theory are the order-theoretic shadows of more general categorical facts. We also examine briefly a different generalization of Möbius–Rota inversion, proposed by other authors.

Given a poset A, Rota considered its incidence algebra I(A), which is the subring of R(A) consisting of the integer-valued θ ∈ R(A) such that θ(a, b) = 0 whenever a ≰ b. By Example 1.2(a) or Corollary 1.5, μ ∈ I(A).

In posets, then, ζ(a, b) = 0 ⇒ μ(a, b) = 0. More generally:

Theorem 4.1 If 𝔸 is a finite category with Möbius inversion then, for a, b ∈ 𝔸,

ζ(a, b) = 0 ⇒ μ(a, b) = 0.

The proof uses a combinatorial lemma.

Lemma 4.2 Let n ≥ 2 and σ ∈ S_{n−1}. Then there exist k ≥ 1 and p_{0}, …, p_{k} such that

p_{0} = 1, p_{1}, …, p_{k−1} ∈ {1, …, n − 1}, p_{k} = n,

and p_{r} = σ(p_{r−1}) + 1 for each r ∈ {1, …, k}.

Proof Suppose not; then there is an infinite sequence (p_{r})_{r≥0} of elements of {1, …, n − 1} satisfying p_{0} = 1 and p_{r} = σ(p_{r−1}) + 1 for all r ≥ 1. Let ε be the endomorphism of the finite set {p_{r} | r ≥ 0} defined by ε(p) = σ(p) + 1. Then ε is injective but not surjective (since 1 is not in its image), contradicting finiteness. □

Proof of Theorem 4.1 Write the objects of 𝔸 as a_{1}, …, a_{n}. There is an n × n matrix Z defined by Z_{ij} = ζ(a_{i}, a_{j}), and Z is invertible over ℚ with (Z^{−1})_{ij} = μ(a_{i}, a_{j}). Suppose that i, j ∈ {1, …, n} and Z_{ij} = 0. Certainly i ≠ j, so n ≥ 2 and we may assume that (i, j) = (1, n). By the standard formula for the inverse of a matrix, our task is to prove that the (n, 1)-minor of Z is 0.

The (n, 1)-minor of Z is

∑_{σ∈S_{n−1}} ±Z_{1,σ(1)+1} ⋯ Z_{n−1,σ(n−1)+1},

and in fact we will prove that each summand is 0. Indeed, let σ ∈ S_{n−1}. Take p_{0}, …, p_{k} as in the Lemma. By hypothesis, there is no map a_{1} a_{n} in 𝔸. Categories have composition, so there is no diagram

a_{1} = a_{p_{0}}  a_{p_{1}}  ⋯  a_{p_{k}} = a_{n}

in 𝔸. Hence ζ(a_{p_{r−1}}, a_{p_{r}}) = 0 for some r ∈ {1, …, k}, giving Z_{p_{r−1},σ(p_{r−1})+1} = 0, as required. □

Given objects a, c of a category 𝔸, let 𝔸_{a,c} be the full subcategory consisting of those b ∈ 𝔸 for which there exist arrows a b c. Theorem 4.1 easily implies:

Corollary 4.3 Let 𝔸 be a finite category. Then 𝔸 has Möbius inversion if and only if 𝔸_{a,c} has Möbius inversion for all a, c ∈ 𝔸, and in that case the Möbius function of 𝔸_{a,c} is the restriction of that of 𝔸. □

These results suggest a way of relaxing the finiteness assumption on our categories. It extends to categories the local finiteness condition on posets used in the Rota theory. Let 𝔸 be a category for which each subcategory 𝔸_{a,c} is finite. Then each hom-set 𝔸(a, b) has finite cardinality, ζ(a, b), and there is a ℚ-algebra

R̂(𝔸) = {θ : ob 𝔸 × ob 𝔸 ℚ | for a, b ∈ 𝔸, ζ(a, b) = 0 ⇒ θ(a, b) = 0}

with operations defined as for R(𝔸). Evidently ζ ∈ R̂(𝔸), and 𝔸 may be said to have Möbius inversion if ζ has an inverse μ in R̂(𝔸). By Theorem 4.1, this extends the definition for finite categories. For example, the skeletal category 𝔻^{inj} of finite totally ordered sets and order-preserving injections has Möbius inversion; compare Example 1.2(c).

The main theorem in Rota’s paper [R] relates the Möbius functions of two posets linked by a Galois connection. Viewing a poset as a special category, a Galois connection is nothing but a (contravariant) adjunction, and Rota’s theorem is a special case of the following result.

Proposition 4.4 Let 𝔸 and 𝔹 be finite categories with Möbius inversion. Let

𝔸 [figure: F; G] 𝔹 be an adjunction, F ⊣ G. Then for all a ∈ 𝔸, b ∈ 𝔹,

∑_{a′:F (a′)=b} μ(a, a′) = ∑_{b′:G(b′)=a} μ(b′, b).

Proof Write ζ(a, b) = ζ(F (a), b) = ζ(a, G(b)). Then for all a ∈ 𝔸, b ∈ 𝔹,

∑_{a′:F a′=b} μ(a, a′) = ∑_{a′∈𝔸} μ(a, a′)δ(F (a′), b) = ∑_{a′∈𝔸, b′∈𝔹} μ(a, a′)ζ(a′, b′)μ(b′, b).

The result follows by symmetry. □

For example, when l is an element of a finite lattice L, the inclusion of the sub-poset {x ∈ L | x ≤ l} into L has right adjoint (− ∧ l), giving Weisner’s Theorem (p.351 of [R]).

The Euler characteristic of posets has been studied extensively; see [St] for references. Given a finite poset A, the classifying space BA always has Euler characteristic, which by Proposition 2.11 is equal to the Euler characteristic of the category A. On the other hand, we may form a new poset Ã by adjoining to A a least element 0 and a greatest element 1, and then χ(A) = μ_{A}(0, 1) + 1: see [R] or §3.8 of [St]. This result can be extended from posets to categories:

Proposition 4.5 Let 𝔸 be a finite category. Write 𝔸̃ for the category obtained from 𝔸 by freely adjoining an initial object 0 and a terminal object 1. If 𝔸 has Möbius inversion then 𝔸̃ does too, and χ(𝔸) = μ_{𝔸}(0, 1) + 1.

Proof Suppose that 𝔸 has Möbius inversion. Let 𝔸_{0} be the category obtained from 𝔸 by freely adjoining an initial object 0. Extend μ ∈ R(𝔸) to a function μ ∈ R(𝔸_{0}) by defining

μ(0, b) = − ∑_{a∈𝔸} μ(a, b),  μ(a, 0) = 0,  μ(0, 0) = 1

(b, a ∈ 𝔸). It is easily checked that this is the Möbius function of 𝔸_{0}.

Dually, if 𝔹 is a finite category with Möbius inversion then the category 𝔹_{1} obtained from 𝔹 by freely adjoining a terminal object 1 also has Möbius inversion, with μ(c, 1) = − ∑_{b∈𝔹} μ(c, b) for all c ∈ 𝔹. Take 𝔹 = 𝔸_{0}: then 𝔸_{01} = 𝔸̃ has Möbius inversion, and

μ(0, 1) = − ∑_{b∈𝔸_{0}} μ(0, b) = − ∑_{b∈𝔸} μ(0, b) − μ(0, 0) = ∑_{a,b∈𝔸} μ(a, b) − 1 = χ(𝔸) − 1.

□

Remark Given categories 𝔹, 𝔸 and a functor M : 𝔹^{op} × 𝔸 Set, the collage of M is the category ℂ formed by taking the disjoint union of 𝔹 and 𝔸 and adjoining one arrow b a for each b ∈ 𝔹, a ∈ 𝔸 and m ∈ M(b, a), with composition defined using M [CKW]. Assuming finiteness, if 𝔹 and 𝔸 have Möbius inversion then so does ℂ:

\begin{matrix}μ_{ℂ}(b, b′) = μ_{𝔹}(b, b′),  μ_{ℂ}(a, a′) = μ_{𝔸}(a, a′),  μ_{ℂ}(a, b) = 0, \\ μ_{ℂ}(b, a) = − ∑_{b′,a′} μ_{𝔹}(b, b′) |M(b′, a′)| μ_{𝔸}(a′, a) \end{matrix}

(b, b′ ∈ 𝔹, a, a′ ∈ 𝔸). In the proof above, the calculation of the Möbius function of 𝔸_{0} is the special case where 𝔹 is the terminal category and M has constant value 1. The ordinal sum of posets is another special case. Moreover, one easily deduces a formula for the Euler characteristic of a collage, which in the special case of posets is essentially Theorem 3.1 of Walker [Wk].

Let us now look at the different generalization of Rota’s Möbius inversion proposed, independently, by Content, Lemay and Leroux [CLL] and by Haigh [H]. (See also [Lr] and §4 of [La]. Haigh briefly considered the same generalization as here, too; see 3.5 of [H].) Given a sufficiently finite category 𝔸, they take the algebra I(𝔸) of functions from {arrows of 𝔸} to ℚ (or more generally, to some base commutative ring), with a convolution product:

(θϕ)(f) = ∑_{hg=f} θ(g)ϕ(h).

Taking ζ ∈ I(𝔸) to have constant value 1, they call the Möbius function of 𝔸 the inverse μ = ζ^{−1} in I(𝔸), if it exists. When 𝔸 is a poset, this agrees with Rota; when 𝔸 is a monoid, it agrees with Cartier and Foata [CF].

They seek to solve a harder problem than we do: if a finite category 𝔸 has Möbius inversion in their sense then it does in ours (with μ(a, b) = ∑_{f∈𝔸(a,b)} μ(f)), but not conversely. For instance, a non-trivial finite group never has Möbius inversion in their sense, but always does in ours.

5 Appendix: category theory

Here follows a skeletal account of some standard notions: category of elements, flat functors, and Cauchy-completeness. Details can be found in texts such as [Bo]. Throughout, 𝔸 denotes a small category.

Let X : 𝔸 Set. The category of elements 𝔼 (X) of X has as objects all pairs (a, x) where a ∈ 𝔸 and x ∈ X(a), and as maps (a, x) (a′, x′) all maps f : a a′ in 𝔸 such that (X(f))(x) = x′.

Similarly, let X : 𝔸 Cat, where Cat is the category of small categories and functors. Then X has a category of elements 𝔼 (X); its objects are pairs (a, x) where a ∈ 𝔸 and x ∈ X(a), and its maps (a, x) (a′, x′) are

pairs (f, ξ) where f : a  a′ in 𝔸 and ξ : (X(f))(x)  x′ in X(a′). This

definition can be made even when X is a weak functor or pseudofunctor, that is, only preserves composition and identities up to coherent isomorphism. The weak functors 𝔸 Cat correspond to the fibrations over 𝔸^{op}; see [Bo].

A set can be viewed as a discrete category (one in which the only maps are the identities). From this point of view, Set-valued functors are special Catvalued functors, and the second definition of the category of elements extends the first.

Any two functors Y : 𝔸^{op} Set and X : 𝔸 Set have a tensor product Y ⊗ X, a set, defined by

Y ⊗ X = (∐_{a∈𝔸} Y (a) × X(a)) / ∼

where ∼ is the equivalence relation generated by (y, (X(f))(x)) ∼ ((Y (f))(y), x) whenever f : a b, x ∈ X(a) and y ∈ Y (b). (It may be helpful to think of X and Y as left and right 𝔸-modules.) A functor X : 𝔸 Set is flat if

− ⊗ X : [𝔸^{op}, Set] Set

preserves finite limits. An equivalent condition is that 𝔼 (X) is cofiltered, that is, every finite diagram in 𝔼 (X) admits at least one cone.

Proposition 5.1 The following conditions on a functor X : 𝔸 Set are equivalent:

a. X is nondegenerate (in the sense of 3.2)

b. every connected-component of 𝔼 (X) is cofiltered

c. X is a sum of flat functors.

d. − ⊗ X : [𝔸^{op}, Set] Set preserves finite connected limits

Proof See [Ln] or [ABLR]. □

An idempotent e : a a in 𝔸 splits if there exist a [figure: s; i] b such that

si = 1 and is = e. The category 𝔸 is Cauchy-complete if every idempotent in 𝔸 splits. (This is a very weak form of completeness. Let 𝕀 be the category consisting of one object, the identity on it, and an idempotent u. Then a splitting of e is precisely a limit of the functor 𝕀 𝔸 defined by u ⟼ e.) All of the examples of categories in this paper are Cauchy-complete, except that a finite monoid is Cauchy-complete if and only if it is a group.

Lemma 5.2 Let 𝔸 be a Cauchy-complete category and X : 𝔸 Set a finite functor. Then X is familially representable if and only if X is nondegenerate.

As in §1, ‘finite’ means that 𝔼 (X) is a finite category.

Proof By Proposition 5.1, it is enough to prove that a finite functor X is representable if and only if it is flat. ‘Only if’ is immediate.

For ‘if’, suppose that X is flat. Then 𝔼 (X) is cofiltered and finite, so the identity functor 1_{𝔼(X)} admits a cone. Also, 𝔼 (X) is Cauchy-complete since 𝔸

is. Now, if ℂ is a Cauchy-complete category and (j ^{p_{c}} c)_{c∈ℂ} is a cone on 1_{ℂ} then p_{j} is idempotent, and the object through which it splits is initial. Hence 𝔼 (X) has an initial object; equivalently, X is representable. □

References

[ABLR] Jiří Adámek, Francis Borceux, Stephen Lack, Jiří Rosický, A classification of accessible categories, Journal of Pure and Applied Algebra 175 (2002), 7–30.

[BB] Kenneth Baclawski, Anders Björner, Fixed points in partially ordered sets, Advances in Mathematics 31 (1979), 263–287.

[BD] John Baez, James Dolan, From finite sets to Feynman diagrams, in Mathematics Unlimited—2001 and Beyond, Springer, 2001.

[Ba] Hyman Bass, Euler characteristics and characters of discrete groups, Invent. Math. 35 (1976), 155–196.

[BL] Clemens Berger, Tom Leinster, The Euler characteristic of a category as the sum of a divergent series, Homology, Homotopy and Applications 10(1), 2008, 41–51.

[BLL] F. Bergeron, G. Labelle, P. Leroux, Combinatorial Species and Tree-Like Structures, Encyclopedia of Mathematics and its Applications 67, Cambridge University Press, 1998.

[Bo] Francis Borceux, Handbook of Categorical Algebra 1: Basic Category Theory, Encyclopedia of Mathematics and its Applications 50, Cambridge University Press, 1998.

[CJ1] Aurelio Carboni, Peter Johnstone, Connected limits, familial representability and Artin glueing, Math. Structures Comput. Sci. 5 (1995), 441–459.

[CJ2] Aurelio Carboni, Peter Johnstone, Corrigenda for: “Connected limits, familial representability and Artin glueing”, Math. Structures Comput. Sci. 14 (2004), 185–187.

[CKW] A. Carboni, G.M. Kelly, R.J. Wood, A 2-categorical approach to change of base and geometric morphisms I, Cahiers Top. Géom. Diff. 32 (1991), 47–95.

[CF] P. Cartier, D. Foata, Problèmes Combinatoires de Commutation et Réarrangements, Lecture Notes in Mathematics 85, Springer, 1969.

[Co] Joel M. Cohen, La caratteristica di Eulero a valori reali, Rend. Sem. Mat. Fis. Milano 47 (1977), 233–239.

[CLL] Mireille Content, François Lemay, Pierre Leroux, Catégories de Möbius et fonctorialités: un cadre général pour l’inversion de Möbius, J. Combin. Theory Ser. A 28 (1980), 169–190.

[D] Arne Dür, Möbius Functions, Incidence Algebras and Power Series Representations, Lecture Notes in Mathematics 1202, Springer, 1986.

[Fa] F.D. Farmer, Cellular homology for posets, Math. Japonica 23 (1979), 607–613.

[Fo] Jon Folkman, The homology groups of a lattice, J. Math. Mech. 15 (1966), 631–636.

[FK] P. Freyd, G.M. Kelly, Categories of continuous functors I, J. Pure Appl. Algebra 2 (1972), 169–191.

[G] Curtis Greene, The Möbius function of a partially ordered set, in I. Rival (ed.), Ordered Sets, NATO Advanced Study Institute Series C, 1982.

[H] John Haigh, On the Möbius algebra and the Grothendieck ring of a finite category, J. London Math. Soc. (2) 21 (1980), 81–92.

[J] André Joyal, Une théorie combinatoire des séries formelles, Adv. Math. 42 (1981), 1–82.

[KR] Daniel A. Klain, Gian-Carlo Rota, Introduction to Geometric Probability, Lezioni Lincee, Cambridge University Press, 1997.

[La] F. William Lawvere, Taking categories seriously, in Seminar and Workshop on Category Theory and Applications, Rev. Colombiana Mat. 20 (1986); reprinted as Repr. Theory Appl. Categ. No. 8 (2005), 1–24.

[Ln] Tom Leinster, A general theory of self-similarity I, arXiv:math.DS/ 0411344 (2004).

[Lr] Pierre Leroux, Les catégories de Möbius, in A. Bastiani, C. Ehresmann (eds.), Deuxième Colloque sur l’Algèbre des Catégories, Centre National de la Recherche Scientifique, 1975.

[Lü] Wolfgang Lück, Transformation Groups and Algebraic K-Theory, Lecture Notes in Mathematics 1408, Springer, 1989.

[MS] Robert D. MacPherson, David J. Srolovitz, The von Neumann relation generalized to coarsening of three-dimensional microstructures, Nature 446, No. 7139 (26 April 2007), 1053–1055.

[M] Ieke Moerdijk, Orbifolds as groupoids: an introduction, in Orbifolds in Mathematics and Physics, Contemp. Math. 310, Amer. Math. Soc., 2002.

[MP] I. Moerdijk, D.A. Pronk, Simplicial cohomology of orbifolds, Indag. Math. (N.S.) 10 (1999), 269–293.

[Pa] Robert Paré, Contravariant functors on finite sets and Stirling numbers, Theory and Applications of Categories 6 (1999), 65–76.

[Pr1] J. Propp, Euler measure as generalized cardinality, arXiv:math.CO/ 0203289 (2002).

[Pr2] J. Propp, Exponentiation and Euler measure, Algebra Universalis 49 (2003), 459–471.

[Pu] A. Pultr, On the homology theory of partially ordered sets (Russian), Soobšč. Akad. Nauk Gruzin. SSR 34 (1964), 25–30.

[R] Gian-Carlo Rota, On the foundations of combinatorial theory I: theory of Möbius functions, Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 2 (1964), 340–368.

[Sc1] Stephen H. Schanuel, Negative sets have Euler characteristic and dimension, Category Theory (Como, 1990), 379–385, Lecture Notes in Math. 1488, Springer, 1991.

[Sc2] Stephen H. Schanuel, What is the length of a potato? An introduction to geometric measure theory, in Categories in Continuum Physics, Lecture Notes in Math. 1174, Springer, 1986.

[Sp] T.P. Speed, On the Möbius function of Hom(P, Q), Bull. Austral. Math. Soc. 29 (1984), 39–46.

[St] Richard P. Stanley, Enumerative Combinatorics, Vol. I, Cambridge Studies in Advanced Mathematics 49, Cambridge University Press, corrected reprint 1997.

[Wk] James W. Walker, Homotopy type and Euler characteristic of partially ordered sets, Europ. J. Combinatorics 2 (1981), 373–384.

[Wl] C.T.C. Wall, Rational Euler characteristic, Proc. Cambridge Philos. Soc. 57 (1961), 182–184.

Tom Leinster Department of Mathematics University of Glasgow Glasgow G12 8QW UK 50

Documenta Mathematica 13 (2008)