Theory and Applications of Categories, Vol. 24, No. 10, 2010, pp. 221–265.

THE HOPF ALGEBRA OF MÖBIUS INTERVALS

F. W. LAWVERE AND M. MENNI

Abstract. An unpublished result by the first author states that there exists a Hopf algebra H such that for any Möbius category C (in the sense of Leroux) there exists a canonical algebra morphism from the dual H^{∗} of H to the incidence algebra of C. Moreover, the Möbius inversion principle in incidence algebras follows from a ‘master’ inversion result in H^{∗}. The underlying module of H was originally defined as the free module on the set of iso classes of Möbius intervals, i.e. Möbius categories with initial and terminal objects. Here we consider a category of Möbius intervals and construct the Hopf algebra via the objective approach applied to a monoidal extensive category of combinatorial objects, with the values in appropriate rings being abstracted from combinatorial functors on the objects. The explicit consideration of a category of Möbius intervals leads also to two new characterizations of Möbius categories.

Contents

1 Introduction 221 2 Möbius categories 223 3 Intervals of Möbius categories 226 4 Categories of Möbius categories and of intervals 229 5 Möbius inversion in the extensive ‘dual’ of sMöI 232 6 Incidence categories 237 7 Extensive Procomonoids 239 8 The Hopf rig of Möbius intervals 242 9 Incidence algebras 249 10 Two alternative proofs 260 11 Summary of notation 262

1. Introduction

The Möbius theory for locally finite posets was developed and promoted by Gian-Carlo Rota and collaborators such as Crapo, Stanley and Schmitt, to name a few. However, the theory needed in particular to be applied to the classical formal Dirichlet algebra which is based on a locally-finite monoid, that of positive integers under multiplication.

M. Menni was funded by Conicet and ANPCyT. Received by the editors 2009-09-28 and, in revised form, 2010-05-06. Transmitted by R.J. Wood. Published on 2010-05-09. 2000 Mathematics Subject Classification: 18A05, 13J05. Key words and phrases: Möbius category, Incidence algebra. \begin{matrix}c \\ ◯ \end{matrix} F. W. Lawvere and M. Menni, 2010. Permission to copy for private use granted.

A more adequate theory is based on suitable small categories, because then the key link in the Dirichlet application, the functor to a cancellative monoid from its divisibility poset, becomes a formal ingredient of the theory.

Pierre Leroux began the development of Möbius categories by isolating the very strong finiteness properties needed so that the incidence algebras should not only exist but satisfy an elegant form of the Möbius Inversion Theorem (see [12] and also [2, 13]). In particular, incremental counting (μ) can be recovered from the result (ζ) of cumulative counting, provided the structure that parameterizes the counting is any Möbius category, in the sense of Leroux.

The objective approach to combinatorial quantities treats constructions directly on the category of combinatorial objects to be counted, then derives the relevant algebras of quantities by the specific abstraction process of Galileo, Cantor, Burnside, Grothendieck, Schanuel: passing to isomorphism types, carrying along the functorial operations that abstract to algebraic operations such as addition and multiplication [15]. As pointed out by Steve Schanuel the use of rigs other than rings facilitates this relationship; moreover, other ‘dimension-like’ invariants arise that naturally take their values in rigs in which 1 + 1 = 1. (See also Section 6.2 below.)

A strong restriction on functors between Möbius categories is required in order that the contravariantly induced linear operators on the incidence algebras preserve convolution. This ULF condition was found in connection with general notions of states, duration, and determinism in Walter Noll’s approach to continuum physics [9].

A quite different strong restriction is appropriate for functors between intervals; the only ULF functors preserving endpoints are isomorphisms. Between intervals it is rather the ‘strict’ functors that covariantly induce relevant operators on the objective ‘quantities’ to be studied.

The nonlinear theory studied here has implicit connections with Barry Mitchell’s study of combinatorial information, as embodied in suitable small categories, in terms of homological dimension of linear representations. Very amenable to his methods were the finite one-way categories that he discovered. A central result in the present work states that a category is Möbius in the sense of Leroux if and only if its intervals are all finite one-way. (For each morphism f in a category, the interval of ‘duration’ f is the category whose objects are factorizations of f.)

The paper grew out of the set of lecture notes [10] recently recovered by Ross Street. These notes establish the importance of ULF functors among Möbius categories, identify the key role of finite Möbius categories and outline a proof of the result stated in the abstract (Theorem 9.8 below). The paper has two main purposes:

1. To present the Hopf algebra H whose dual contains an invertible element ζ in a way universal with respect to all Möbius categories and coefficient rigs.

2. To construct H and prove its fundamental role using the objective approach.

In the process of achieving these two goals we obtain two new characterizations of Möbius categories in terms of Möbius intervals (Propositions 3.8 and 9.16). The paper is mostly self contained and illustrates the main definitions with some simple examples, but the reader is assumed to be more or less familiar with the applications of incidence algebras (Definition 9.3), at least, for the poset case due to Rota (see [4] and references there).

This paper is organized as follows: Möbius categories, their intervals, and different kinds of functors between them are treated directly in Sections 2 - 7. The relevant algebras of quantities are then derived and studied in Sections 8 - 10. Section 11 summarizes most of the notation that we introduce, in the hope that this will be helpful to the reader.

2. Möbius categories

Let C be a small category and let f : x → y be a map in C. A decomposition of f is a sequence (f_{1}, …, f_{n}) of non-identity maps such that f_{1} … f_{n} = f. Each identity admits the empty sequence () as a decomposition. The length of a decomposition (f_{1}, …, f_{n}) is n. In particular, the length of the empty sequence is 0. A map is called indecomposable if it has no decompositions of length ≥ 2.

2.1. Definition. A small category is called Möbius if the set of decompositions of each map is finite.

The definition of decomposition appears naturally in the construction of free categories. Let Δ_{1} be the three-element monoid of all order-preserving endos of the two-element linearly ordered set, and consider the presheaf topos Δ̂_{1} of ‘reflexive graphs’ [8]. There is an obvious ‘underlying graph’ functor U : Cat → Δ̂_{1} where Cat denotes the category of small categories and functors between them. Consider its left adjoint F : Δ̂_{1} → Cat. Each object G in Δ̂_{1} has ‘identity’ edges and non-identity edges. The category F G has, as objects, the nodes of G. For each pair (x, x′) of nodes, the morphisms from x to x′ correspond to sequences (f_{1}, …, f_{n}) of non-identity edges appearing as in the diagram

\xymatrix{x \ar[r]_{f_{n}} & · \ar[r]_{f_{n−1}} & · . . . · \ar[r]_{f_{2}} & · \ar[r]_{f_{1}} & x′}

in G. For each node x, the empty sequence () in (F G)(x, x) acts as the identity morphism of the object x.

For any small category C, the counit ε : F UC → C maps a sequence (f_{1}, …, f_{n}) of non-identity maps to the composition f_{1} … f_{n}. So, an element in the fiber of ε over f is a decomposition of f and a category C is Möbius if and only if the counit ε : F UC → C has finite fibers.

It is clear from Definition 2.1 that Möbius categories are closed under forming opposites, finite products, and arbitrary coproducts in Cat. Also, every subcategory of a Möbius category is Möbius. Finally, if C is Möbius and x is an object of C then x/C and C/x are Möbius. Typical concrete examples are:

1. Finite posets or, more generally, ‘locally finite’ posets such as ℕ with its usual order or the positive integers under divisibility. (We characterize Möbius posets in Corollary 2.9 below.)

2. Free monoids, free commutative monoids, the monoid ℕ^{∗} of positive integers under multiplication. (We show in Section 3 that the trivial monoid is the only finite Möbius monoid.)

3. Free categories on reflexive graphs, the category of finite ordinals and monotone injections.

We will prove several characterizations of Möbius categories. In particular, Proposition 2.6 below, which needs the following sequence of lemmas.

2.2. Lemma. If C is a Möbius category then the following hold:

1. gh = g implies h = id and

2. fg = g implies f = id.

In particular, every idempotent in C is an identity.

Proof. Consider the first statement. If g = id then h = id. So assume that g is not an identity. If h is not an identity then the set of decompositions of g is infinite. Absurd. The second item follows from the first and the fact that C^{op} is Möbius.

This lack of non-trivial idempotents implies that initial and terminal objects in Möbius categories are strict. But more is true.

2.3. Lemma. Every Möbius category with initial and terminal object is finite.

Proof. Let C be a category as in the statement. It must have a finite number of objects; otherwise the unique map 0 → 1 would have an infinite set of decompositions of length 2. We claim that for every pair (x, y) of objects in C, the set of C(x, y) is finite. If y is terminal then the claim is trivial. If y is initial the claim holds because initials are strict in Möbius categories. Similarly, C(x, y) is finite if x is initial or final. So let x and y be neither initial nor terminal. Then C(x, y) must be finite because if not, 0 → 1 has an infinite set of decompositions of length 3.

The lack of non-trivial idempotents has further implications in arbitrary Möbius categories.

2.4. Lemma. If C is a Möbius category then all sections, retractions and isomorphisms in C are identities. It follows that identities in C are indecomposable.

Proof. If rs = id then r(sr) = r. Lemma 2.2 implies that sr = id. Then s and r are inverse to each other. If one of them is not an identity then neither is the other. In this case, an identity has an infinite number of decompositions. Absurd.

(Incidentally, this result implies that Möbius categories are not closed under equivalence. For example, consider the category with two objects, both of them terminal. It is not Möbius, but it is equivalent to the Möbius category with one object and one map.)

Some of the elementary properties of Lemmas 2.2 and 2.4, together with a restricted version of the finiteness condition defining Möbius categories provide a characterization that we prove in Proposition 2.6. But first we show an auxiliary result.

2.5. Lemma. Let C be a category such that the set of decompositions of length 2 of every map is finite. Then for every k ≥ 0 and for every map f in C, the set of decompositions of f of length k is finite.

Proof. Identities have a unique decomposition of length 0 and no decompositions of length 1. Non-identity maps have no decompositions of length 0 and a unique decomposition of length 1. Now consider a positive integer k + 2. For every map f, a decomposition of length k + 2 can be built by first choosing a decomposition (f_{1}, f_{2}) of f and then choosing a decomposition of length k + 1 of f_{1}. There are finitely many decompositions (f_{1}, f_{2}) of f by hypothesis, and the inductive hypothesis implies that there are finitely many decompositions of f_{1} of length k + 1. So the set of decompositions of f of length k + 2 is finite.

2.6. Proposition. [Leroux] A small category C is Möbius if and only if the following hold:

1. for each f in C, the set of decompositions of f of length 2 is finite,

2. identities are indecomposable and

3. one/both of the conditions of Lemma 2.2 hold.

Proof. If every map in C has a finite number of decompositions then, in particular, the first condition holds. The two other conditions follow from Lemmas 2.2 and 2.4. Conversely, assume that the small category C satisfies the three stated conditions. By Lemma 2.5 it is enough to prove that for every f, there is a bound for the possible lengths of decompositions of f. Let k be the cardinality of the set of decompositions of f of length 2. If there is no bound for the possible lengths of decompositions of f, then there exists a decomposition of f as below

(f_{1}, f_{2}, …, f_{k+1}, f_{k+2})

of length k + 2. There are k + 1 places where this list can be divided into an initial part and a final part. Each of these divisions induces a decomposition of f of length 2. But there are k such decompositions, so there must be two divisions of the decomposition above which induce the same decomposition of length 2. It follows that there exists g and h (obtained by composing some of the f_{i}’s) such that gh = g. Then h = id by hypothesis. But this is a contradiction because none of the f_{i}’s is an identity and because identities are indecomposable by hypothesis. Hence, there is a bound for the lengths of decompositions of f.

The last part of the proof of Proposition 2.6 admits a nice reformulation via the notion of ‘length’ of a morphism. Let ω be the partially ordered set of natural numbers. Denote by ω_{+∞} the complete poset obtained by freely adding a terminal object ‘∞’ to ω.

2.7. Definition. [Length of a morphism] For a map f in a category C, we define the length of f to be the supremum in ω_{+∞} of the set of lengths of decompositions of f.

As a corollary of Lemma 2.5 we obtain the following result.

2.8. Corollary. [Leroux] Let C be a category such that the set of decompositions of length 2 of every map is finite. Then C is Möbius if and only if every morphism of C has finite length.

Let P be a poset and let x ≤ y in P. The interval [x, y] is the set {p | x ≤ p ≤ y} equipped with the partial order inherited from P. A poset is called locally finite if all its intervals are finite. The restriction of Proposition 2.6 to the case of posets gives the following characterization.

2.9. Corollary. A poset (as a category) is Möbius if and only if it is locally finite.

The characterization stated in Corollary 2.9 can be generalized to categories. To do so, we need the correct notion of ‘interval’.

3. Intervals of Möbius categories

In this section we recall the definition of interval introduced in [9] and characterize Möbius categories in terms their intervals.

3.1. Definition. Let f : x → y be a morphism in a category C. The interval If is the category constructed as follows. An object of If is a pair (f_{0}, f_{1}) of morphisms of C for which f = f_{1}f_{0} and a morphism a : (f_{0}, f_{1}) → (g_{0}, g_{1}) in If is any morphism of C such that g_{0} = af_{0} and g_{1}a = f_{1} as in the diagram below.

\xymatrix{ & · \ar[d]|{a} \ar[dr]^{f_{1}} \\ x \ar[ur]^{f_{0}} \ar[r]_{g_{0}} & · \ar[r]_{g_{1}} & y}

If b : (g_{0}, g_{1}) → (h_{0}, h_{1}) is another morphism in If, the composition ba in C is easily verified to be a morphism (f_{0}, f_{1}) → (h_{0}, h_{1}) in If thus defining the composition operation needed to make If into a category.

The category If has an initial object 0 = (id, f) and a terminal object 1 = (f, id). The objects in If that are neither initial nor terminal coincide with the decompositions of f of length 2. A morphism f is indecomposable if and only if If is equivalent to a totally ordered set with at most two elements. If If has exactly one element then f is an indecomposable identity. If If has two elements then f is an indecomposable non-identity. (Compare with first paragraph in Section 2.)

There is a canonical ‘forgetful’ functor If → C which to any object \xymatrix{x \ar[r]^{f_{0}} & z \ar[r]^{f_{1}} & y} in If assigns the object z in C.

3.2. Lemma. There are canonical isomorphisms (x/C)/f → If and f/(C/y) → If such that the following diagram

\xymatrix{(x/C)/f \ar[d] \ar[r]^{≅} & If \ar[d] & f/(C/y) \ar[l]_{≅} \ar[d] \\ x/C \ar[r] & C & C/y \ar[l]}

commutes.

Proof. Consider the left square. An object α in (x/C)/f is a morphism f_{1} in x/C with codomain f. Let f_{0} : x → z be the domain of f_{1} in x/C. Then α is determined by the pair (f_{0}, f_{1}) with f_{1} : z → y and such that f_{1}f_{0} = f. Assume that β = (g_{0}, g_{1}) is another object in (x/C)/f. A morphism a : α → β is a map a in x/C from f_{0} to g_{0} and such that g_{1}a = f_{1}. It is then clear that the assignment that maps a : α → β in (x/C)/f to a : (f_{0}, f_{1}) → (g_{0}, g_{1}) is a functor. It is also evident that this functor is an iso. The leftbottom composition maps α to f_{0} and then f_{0} to z. The argument for f/(C/y) → If is analogous.

The functor If → C maps the unique 0 → 1 in If to f in C. In particular, if C has initial and terminal objects and we denote the unique map between them by ! : 0 → 1 then the canonical functor I! → C is an iso. As a corollary of these observations we obtain a characterization of categories of the form If for some morphism f.

3.3. Lemma. A category is iso to an interval if and only if it has initial and terminal objects.

This result also raises a relevant issue. What is a good notion of morphism between intervals? We will come back to this in Section 4. Before that, we need to discuss intervals in Möbius categories.

3.4. Lemma. If C is a Möbius category then If is finite and Möbius for all maps f in C.

Proof. Recall that slices and coslices of Möbius categories are Möbius (see discussion before Lemma 2.2). So Lemma 3.2 implies that If ≅ (x/C)/f is Möbius. Since intervals always have initial and terminal objects, Lemma 2.3 implies that If is finite.

This suggests that we take a closer look at finite Möbius categories. Recall that a category C is called (strongly) one-way if for any diagram in C as below

\xymatrix{x \ar[r]^{f} & y \ar[l]^{g}}

the objects x and y are equal and f = id = g.

3.5. Proposition. If C is a finite category then the following are equivalent:

1. C is Möbius,

2. all idempotents and isos in C are identities,

3. C is one-way.

The first item implies the second by Lemma 2.4 (regardless of the finiteness hypothesis). To prove that the third item implies the first, use Proposition 2.6. As C is finite, the set of decompositions of length two of every map is finite. Identities are indecomposable in any one-way category. The last condition required in Proposition 2.6 is trivial (in this case) because all endos are identities in a one-way category. So, to finish the proof of Proposition 3.5 we need to show that the second item implies the third.

3.6. Lemma. In a finite category every endo f has a power f^{m}, m ≥ 1, which is idempotent.

Proof. By finiteness, it must be the case that f^{n} = f^{n+k} for some n, k ≥ 1. It follows that f^{n} = f^{n+ik} for any i ≥ 1. Choose i, j ∈ ℕ such that n + j = ik and let m = n + j = ik. If we let e = f^{m} then ee = f^{n+j}f^{ik} = f^{n+ik+j} = f^{n+j} = e.

An application of the following corollary finishes the proof of Proposition 3.5.

3.7. Corollary. Let C be a finite category. If C has no non-trivial idempotents then every endo is invertible. Hence, if all idempotents and isos in C are identities then C is one-way.

Proposition 3.5 implies that the trivial monoid is the unique finite Möbius monoid. On the other hand, we have already mentioned many interesting infinite Möbius monoids such as free monoids, (ℕ, +, 0) and (ℕ, ·, 1). We can now characterize Möbius categories in terms of their intervals.

3.8. Proposition. For any small category C the following are equivalent:

1. C is Möbius,

2. all intervals of C are Möbius,

3. all intervals of C are finite and one-way.

Proof. The first item implies the second by Lemma 3.4. The second item implies the third by Lemma 2.3 and Proposition 3.5. Finally, assume that C is a small category such that all its intervals are finite and one-way. We use Proposition 2.6 to prove that C is Möbius. If intervals are finite, then the set of decompositions of length 2 of every map is finite. If intervals of identities are finite and one-way then identities are indecomposable. Finally, assume that gh = g holds in C. Each pair (h^{n}, g) is an object in Ig. As the interval is finite, there are m, k ≥ 1 such that h^{m} = h^{m+k}. We then have an endo h^{k} : (h^{m}, g) → (h^{m}, g). As Ig is one-way, h^{k} = id. We claim that this implies that h = id. To prove the claim, observe that h^{k−1} determines a morphism 1 = (h, id) → (id, h) = 0 in Ih. As Ih is oneway, 0 = 1 and hence h = id.

Intervals determined by maps in Möbius categories will play an important role in the rest of the paper. We now summarize what we have established about them so far.

3.9. Lemma. For a category C the following are equivalent.

1. C is iso to an interval of a Möbius category.

2. C is Möbius and has initial and terminal objects.

3. C is finite, one-way and has initial and terminal objects.

Proof. Combine Proposition 3.8 with Lemma 3.3.

It will be useful to introduce the following terminology.

3.10. Definition. A category is called a Möbius interval if it satisfies the equivalent conditions of Lemma 3.9.

4. Categories of Möbius categories and of intervals

Let Mö → Cat be the full subcategory determined by Möbius categories. We have already observed before Lemma 2.2 that Mö → Cat is closed under arbitrary coproducts, finite products, slices and coslices. We stress that the subcategory Mö → Cat is not ‘2-replete’; in the sense that a category equivalent to a Möbius category need not be Möbius. (See remark below Lemma 2.4.) In relation to this, it should also be mentioned that, since there are no non-trivial isos in Möbius categories, any equivalence between Möbius categories is actually an isomorphism.

Let MöI → Mö be the full subcategory determined by Möbius intervals in the sense of Definition 3.10. The category MöI has finite products and the embedding MöI → Mö preserves them. For some purposes, Mö and MöI have too many morphisms. The following simple observation is related to this fact and will be relevant at several places later.

4.1. Lemma. Let F : C → D be a functor between categories whose identities are indecomposable. Then the following are equivalent:

1. F reflects isos,

2. for all maps h in C, F h = id implies h = id.

Proof. In C and D the only isos are identities.

Although it is somewhat awkward to state, the idea is that iso-reflecting functors are those that ‘preserve decompositions’. In the following sense: if (f_{1}, …, f_{n}) is a decomposition of a map f and F satisfies the second item of Lemma 4.1 then (F f_{1}, …, F f_{n}) is a decomposition of F f. On the other hand, if f is not an identity and F f = id then applying F to the members of any decomposition (…, f, …) will produce a non-decomposition (…, F f, …).

In Section 4.2 we introduce a (non-full bijective on objects) subcategory ulfMö of Mö determined by the functors that induce convolution-preserving maps at the level of incidence algebras. In Section 4.5 we introduce a convenient subcategory sMöI of MöI. Both the relation with incidence algebras and the convenience of sMöI will only be sketched in this section. Further details will be treated in later sections.

4.2. Unique lifting of factorizations. Consider a functor F : C → D between arbitrary categories. Any map f : x → y in C induces a functor F_{f} : If → I(F f) such that the following diagram

\xymatrix{If \ar[d] \ar[r]^{F_{f}} & I(F f) \ar[d] \\ C \ar[r]_{F} & D}

commutes.

4.3. Lemma. For any functor F : C → D, the following are equivalent:

1. F_{f} : If → I(F f) is an isomorphism for every f in C,

2. for every map f : x → y in C, if F f = wv as on the left below

\xymatrix{F x \ar[dd]_{F f} \ar[dr]^{v} &  & x \ar[dd]_{f} \ar@{.>}[dr]^{g} \\  & · \ar[dl]^{w} &  & · \ar@{.>}[dl]^{h} \\ F y &  & y}

then there exists a unique pair g, h of maps in C such that hg = f as on the right above and such that F g = v and F h = w.

Proof. Straightforward.

A functor F : C → D satisfying the equivalent conditions of Lemma 4.3 is said to satisfy the unique lifting of factorizations condition. For brevity we sometimes say that F satisfies the ULF condition or that F is a ULF-functor. The definition of ULF-functor should be compared with that of local homeomorphism.

It is easy to check that the functors If → C are ULF. The canonical functors x/C → C and C/y → C are ULF. Discrete fibrations and op-fibrations are faithful ULF-functors. Composites of ULF-functors are ULF.

As a concrete example consider the functor ω → ℕ from the total order of natural numbers to the additive monoid of natural numbers that maps m ≤ n to n − m. A similar example relates the poset of natural numbers under divisibility with the multiplicative monoid ℕ^{∗}. This was the example that showed definitively that the theory of incidence algebras should not be limited to Möbius posets, nor even to Möbius monoids, but to appropriate small categories, because this functorial connection between the two extreme cases plays a central role in the applications. The unification, via Möbius categories, of the monoid and poset cases is explicitly mentioned in [2]. Moreover, the third paragraph in p. 170 loc. cit. states that ‘Un des principaux avantages de l’unification est de rendre possible des liaisons entre catégories de Möbius de types différents, à l’aide de foncteurs’. The applications mentioned above refer mainly to incidence algebras and to morphisms between them induced by ULF functors. We will briefly mention some of these applications in Section 9.17, after introducing incidence algebras explicitly in 9.3.

4.4. Lemma. Let C and D be categories whose identities are indecomposable. Then every ULF-functor C → D reflects isos.

Proof. By Lemma 4.1 it is enough to prove that F w = id implies w = id. Consider the factorizations w id = w and id w = w. The functor F maps both factorizations to id id = id. The uniqueness of liftings implies that w = id.

Define ulfMö → Mö to be the subcategory determined by ULF-functors.

4.5. Strict functors and length. In this section we introduce a convenient category of Möbius intervals (Definition 3.10) and relate it with the notion of length of a morphism as used in [2].

4.6. Definition. Let C and D be categories with initial and terminal objects. A functor C → D is called strict if it reflects isos and preserves the initial and terminal objects.

Identities are strict and strict functors compose. So let sMöI → MöI be the (bijective on objects) subcategory determined by strict functors.

4.7. Lemma. If F reflects isos then F_{f} : If → I(F f) is strict for any f in C.

Lemma 4.7 partially justifies that we consider strict functors as a good notion of functor between intervals. The next result states an important closure property and a simple characterization of strict ULF-functors.

4.8. Lemma. Let C and D be categories with initial and terminal objects. For any functor F : C → D the following hold:

1. If F is strict then so are x/F : x/C → (F x)/D and F/x : C/x → D/(F x).

2. F is strict and ULF if and only if F is an isomorphism.

Proof. The first item is easy. To prove the second, consider the unique map ! : 0 → 1 in C. The canonical I! → C is an iso (remark below Lemma 3.2) and the ULF property implies that the top map in the diagram below

\xymatrix{I! \ar[d] \ar[r]^{F_{!}} & I(F!) \ar[d] \\ C \ar[r]_{F} & D}

is an iso. But F! is the unique 0 → 1 in D by hypothesis. So the vertical map on the right is also an iso. Hence, F is an isomorphism too.

The second item of Lemma 4.8 implies that the intersection of sMöI → MöI and ulfMö → MöI is the groupoid of Möbius intervals and isos between them.

The terminal category 1 in MöI is not terminal in sMöI since the only iso-reflecting functor C → 1 in MöI is the identity. Also, the identity is the unique 1 → C preserving initial and terminal object. The projections C_{0} × C_{1} → C_{i} do not reflect isos. But products in MöI induce a symmetric monoidal structure on sMöI which we still denote by (sMöI, ×, 1). This monoidal structure interacts well with the notion of length introduced in Definition 2.7.

4.9. Definition. The length of a Möbius interval C is the length (in the sense of Definition 2.7) of the unique map 0 → 1 in C.

The length of a Möbius interval is always finite and we will denote it by ℓC ∈ ω. The assignment of lengths to intervals can be made functorial. Let (ω, +, 0) be the symmetric monoidal category induced by usual addition of numbers.

4.10. Lemma. The assignment C ↦ ℓC for Möbius intervals C, extends to a symmetric monoidal functor ℓ : (sMöI, ×, 1) → (ω, +, 0).

Proof. Let F : C → D in sMöI and let (f_{1}, …, f_{n}) be a decomposition of 0 → 1 in C. As F is strict (F f_{1}, …, F f_{n}) is a decomposition of 0 → 1 in D (recall the paragraph after Lemma 4.1). It follows that ℓC ≤ ℓD. Moreover, ℓ1 = 0 and its easy to see that ℓ(C × D) = (ℓC) + (ℓD).

Further evidence that sMöI is a good category of intervals is given in the next section.

5. Möbius inversion in the extensive ‘dual’ of sMöI

If C is a Möbius category, the incidence algebra of C with integer coefficients is denoted by ℤC. The element ζ in ℤC is called the Riemann function and its inverse, denoted by μ, is called the Möbius function. One of the main results in [2] is a non-recursive definition of μ in terms of numbers of decompositions. The result is stated as μ = Φ_{+} − Φ_{−} in Proposition 3.2 in [2]. Since μ = \frac{δ}{ζ}, it follows that δ = ζ ∗ (Φ_{+} − Φ_{−}) and hence that δ + ζ ∗ Φ_{−} = ζ ∗ Φ_{+}. This equality, without subtractions, admits a direct combinatorial interpretation in the extensive category Cat(sMöI, Set_{f}) equipped with a monoidal structure used to interpret ∗. The precise formulation and proof of this fact is the main content of this section. In Section 9 we show that the results about incidence algebras appear as corollaries of this result, by using the process that collapses a monoidal category into an algebra of iso-classes of objects (see [15, 11]). In the end, we hope to convey the idea that the fundamental results about incidence algebras for Möbius categories depend ultimately on simple combinatorial functors on sMöI, the category of Möbius intervals with strict functors.

The correct categorical setting for some of the results in this section seems to be the 2-category Ext of extensive categories (and coproduct-preserving functors between them, and all natural transformations between the functors) equipped with the tensor product described in Section 3.5 of [5]. The intuition is that Ext is analogous to a category of modules (see also the Introduction of [1]) and therefore monoids and comonoids behave in more or less the same way that they do in the theory of Hopf algebras. The 2-categorical details involved in a precise formulation are not trivial and, at the same time, are far from the typical applications of incidence algebras. We have therefore decided to introduce the fundamental combinatorial operations in detail, but to leave out the precise 2-categorical formulation of the structures that these operations induce. The unspecified structures induce monoidal structures and functors that we do need to define with full precision. For this reason, at key points, we give a hint of how a 2-categorical proof should go, and also suggest a direct concrete proof.

We assume familiarity with extensive categories as defined, for example, in [15, 1]. We denote the category of finite sets and functions between them by Set_{f}. Recall that Set_{f} is free on 1 in the category Ext. (So it plays the role of R as a special R-module.) For any category C we denote its finite-coproduct completion by FamC. Coproduct completions are always extensive. For example, consider the category sMöI. Objects in the extensive category Fam(sMöI) can be identified with finite Möbius categories such that each component has initial and terminal objects. Morphisms in Fam(sMöI) can be identified with families of strict functors.

5.1. Distinguished Set_{f}-valued functors on sMöI. In this section we introduce functors δ, ζ, η, Φ_{+}, Φ_{−} : sMöI → Set_{f}. Readers familiar with [2] will recognize the notation. The objects ζ, δ, η, Φ_{+}, Φ_{−} in the category Cat(sMöI, Set_{f}) are combinatorial analogs of the éléments remarquables introduced in Section 3 loc. cit. in order to prove the general Möbius inversion principle in incidence algebras stating that ζ^{−1} exists and equals Φ_{+} − Φ_{−}. For the moment, the lack of a ‘−1’ in Set_{f} does not allow us to define an analog of μ = ζ^{−1}, but we will show that the key fact underlying Möbius inversion follows from the existence of an isomorphism in Cat(sMöI, Set_{f}). Incidentally, the fact that we can define functors δ, η, Φ_{+}, Φ_{−} on sMöI gives further evidence that the strict category sMöI is a good category of intervals.

The functor ζ : sMöI → Set_{f} is simply the terminal object of Cat(sMöI, Set_{f}). It assigns the terminal set 1 to each Möbius interval.

We let δ : sMöI → Set_{f} be the functor that maps the trivial interval 1 to the final set 1 and every other interval to the empty set 0. Notice that δ cannot be extended to a functor MöI → Set_{f} because there are many functors 1 → C in MöI with C non-terminal.

Let η : sMöI → Set_{f} be the functor that maps the trivial interval to the empty set 0 and every other interval to 1. Again, this functor cannot be lifted to MöI, simply because 1 is terminal in MöI.

5.2. Lemma. The unique maps δ → ζ and η → ζ induce an isomorphism δ + η → ζ in Cat(sMöI, Set_{f}).

(In contrast, notice that the terminal object in the category Cat(MöI, Set_{f}) of nonstrict presheaves is connected.)

The functor Φ_{+} : sMöI → Set_{f} assigns, to each C in sMöI, the set Φ_{+}C of evenlength decompositions of the unique map 0 → 1 in C. If F : C → D is a strict functor and (f_{1}, …, f_{n}) is in Φ_{+}C then (F f_{1}, …, F f_{n}) is in Φ_{+}D.

Similarly, let Φ_{−} : sMöI → Set_{f} be the functor that maps each Möbius interval C to the set Φ_{−}C of odd-length decompositions of 0 → 1 in C.

5.3. The ‘coalgebra’ sMöI and its ‘dual’. Fundamental to everything we will do in the rest of the paper is the functor

Δ : sMöI → Fam(sMöI × sMöI)

defined by

ΔC = ∑_{x∈C}(x/C, C/x)

where the sum ranges over the objects of C. (The proof that it is a functor uses the first item of Lemma 4.8.) This functor Δ determines a ‘comonoid’ structure (in a suitable bicategorical sense) on the extensive category Fam(sMöI). The functor δ : sMöI → Set_{f}, introduced in Section 5.1, determines the ‘counit’ of this comonoid.

For general reasons, the ‘comonoid’ (Fam(sMöI), Δ, δ) in Ext, induces a monoidal structure on the category Cat(sMöI, E) where E is any extensive category with products. In particular, take E = Set_{f}. Then for any pair of objects α, β in Cat(sMöI, Set_{f}), define their convolution α ∗ β ∈ Cat(sMöI, Set_{f}) as the composition

\xymatrix{sMöI \ar[d]^{Δ} \ar[rr]^{α∗β} &  & Set_{f} \\ Fam(sMöI × sMöI) \ar[r]^{Fam(α×β)} & Fam(Set_{f} × Set_{f}) \ar[r]^{Fam(×)} & Fam(Set_{f}) \ar[u]}

where Fam(Set_{f}) → Set_{f} is determined by coproducts in Set_{f} (and the universal property of Fam(Set_{f})). More concretely,

(α ∗ β)C = ∑_{x∈C} α(x/C) × β(C/x)

for C in sMöI.

5.4. Proposition. Convolution extends to a monoidal structure on Cat(sMöI, Set_{f}) which has δ as unit and which distributes over coproducts.

Proof. The functor ∗ extends to a monoidal structure because (Fam(sMöI), Δ, δ) is a ‘comonoid’ in a good bi-categorical sense. Alternatively, one can calculate with the explicit definition of convolution and show that (α_{1} ∗ … ∗ α_{n})C is coherently iso to

∑_{(f_{1},...,f_{n})} α_{1}(If_{1}) × … × α_{n}(If_{n})

where (f_{1}, …, f_{n}) is a composable sequence of maps such that f_{1} … f_{n} equals the unique map 0 → 1 in C.

The extensive monoidal category Cat(sMöI, Set_{f}) ≃ Ext(Fam(sMöI), Set_{f}) should be thought of as the dual of the comonoid (Fam(sMöI), Δ, δ) in Ext.

5.5. Combinatorial Möbius inversion. Let Φ be the object in Cat(sMöI, Set_{f}) such that ΦC is the set of decompositions of the unique map 0 → 1 in C. For each C in MöI we have that

(Φ ∗ Φ)C = ∑_{x∈C} Φ(x/C) × Φ(C/x)

which means that an element of (Φ ∗ Φ)C can be identified with a triple (x, d_{1}, d_{0}) where x is an object of C, d_{1} is a decomposition of the unique map x → 1 and d_{0} is a decomposition of the unique map 0 → x. Now, if d_{1} = (f_{1}, …, f_{n}) and d_{0} = (g_{1}, …, g_{m}) then the sequence d = (f_{1}, …, f_{n}, g_{1}, …, g_{m}) is a decomposition of the unique map 0 → 1 in C. This assignment (x, d_{1}, d_{0}) ↦ d extends to a morphism Φ ∗ Φ → Φ in Cat(sMöI, Set_{f}).

5.6. Lemma. The morphism Φ ∗ Φ → Φ above is associative and has the unique map δ → Φ as unit.

Without giving a name to the operations, we will consider the object Φ as a monoid in Cat(sMöI, Set_{f}) with the operations distinguished in Lemma 5.6. There are obvious morphisms Φ_{+} → Φ and Φ_{−} → Φ and the induced Φ_{+} + Φ_{−} → Φ is an iso. The monoid structure on Φ restricts to a monoid structure on Φ_{+}. On the other hand, the monoid structure on Φ does not restrict to a monoid structure on Φ_{−}.

In order to state the next result, recall the object η ∈ Cat(sMöI, Set_{f}) introduced in Section 5.1. The unique map η → ζ was characterized in Lemma 5.2 as the complement of the subobject δ → ζ. Consider now the morphism η → Φ_{−} such that, at each stage C ≠ 1, the function ηC → Φ_{−}C maps the unique element in ηC to the unique decomposition of length 1 of the map 0 → 1 in C. Tensoring the monic maps η → Φ and Φ_{+} → Φ we obtain a monic η ∗ Φ_{+} → Φ ∗ Φ.

5.7. Lemma. The composition η ∗ Φ_{+} → Φ ∗ Φ → Φ factors through Φ_{−} → Φ as in the diagram below

\xymatrix{η ∗ Φ_{+} \ar[d] \ar@{.>}[r] & Φ_{−} \ar[d] \\ Φ ∗ Φ \ar[r] & Φ}

and the factorization η ∗ Φ_{+} → Φ_{−} is an iso. Similarly, the monoid structure on Φ restricts to an iso Φ_{+} ∗ η → Φ_{−}.

Proof. Every odd-length decomposition can be divided into its first map and an evenlength decomposition.

We will freely write η ∗ Φ_{+} = Φ_{−} or Φ_{+} ∗ η = Φ_{−} to denote any of the relevant isos distinguished in Lemma 5.7.

The unique map δ → Φ_{+} has a complement that could be denoted by (Φ_{+} − δ) → Φ_{+}, but for brevity, we denote it by Υ → Φ_{+}. For C in sMöI, ΥC is the set of even-length and non-empty decompositions of 0 → 1 in C. So Υ1 = 0 and ΥC = Φ_{+}C for C ≠ 1. We can relate Υ and Φ_{−} as follows. Tensoring the monic maps η → Φ and Φ_{−} → Φ we obtain two monic maps η ∗ Φ_{−} → Φ ∗ Φ and Φ_{−} ∗ η → Φ ∗ Φ.

5.8. Lemma. The compositions η ∗ Φ_{−} → Φ ∗ Φ → Φ and Φ_{−} ∗ η → Φ ∗ Φ → Φ factor through Υ → Φ as in the diagram below

\xymatrix{η ∗ Φ_{−} \ar[d] \ar@{.>}[r] & Υ \ar[d] & Φ_{−} ∗ η \ar@{.>}[l] \ar[d] \\ Φ ∗ Φ \ar[r] & Φ & Φ ∗ Φ \ar[l]}

and the resulting factorizations η ∗ Φ_{−} → Υ and Φ_{−} ∗ η → Υ are isos.

Proof. Similar to Lemma 5.7. Intuitively, every non-empty decomposition of even length is uniquely determined by a non-identity map and a ‘compatible’ odd-length decomposition.

By definition, the diagram δ → Φ_{+} ← Υ is a coproduct diagram. Since we have isomorphisms η ∗ Φ_{−} ≅ Υ ≅ Φ_{−} ∗ η we may write

δ + η ∗ Φ_{−} = Φ_{+}

to denote the iso δ + η ∗ Φ_{−} ⟶ δ + Υ ≅ Φ_{+} that is determined by Lemma 5.8. Combining these results we can prove the following.

5.9. Proposition. There exist isos δ + ζ ∗ Φ_{−} ⟶ ζ ∗ Φ_{+} and δ + Φ_{−} ∗ ζ ⟶ Φ_{+} ∗ ζ in the monoidal extensive category Cat(sMöI, Set_{f}).

Proof. The following calculation

ζ ∗ Φ_{+} = (δ + η) ∗ Φ_{+} = Φ_{+} + η ∗ Φ_{+} = δ + η ∗ Φ_{−} + Φ_{−} = δ + (η + δ) ∗ Φ_{−} = δ + ζ ∗ Φ_{−}

provides an explicit definition of the morphism δ + ζ ∗ Φ_{−} ⟶ ζ ∗ Φ_{+} and a proof that it is an isomorphism.

The proof of Proposition 5.9 constructs an explicit iso ζ ∗ Φ_{+} → δ + ζ ∗ Φ_{−} (determined by an indexed set of bijections) that can be described in more concrete terms as follows. First, an element of (ζ ∗ Φ_{+})C is determined by an object x in C together with an even-length decomposition (f_{1}, …, f_{n}) of the unique map 0 → x in C. In particular, if C is the trivial interval, then (ζ ∗ Φ_{+})C = 1. Similarly, when C is the trivial interval, (δ + ζ ∗ Φ_{−})C = δC = 1. So in this extreme case, the iso (ζ ∗ Φ_{+})C → (δ + ζ ∗ Φ_{−})C = δC is simply the identity on the terminal set.

We now concentrate on the case when C is a non-trivial interval and then, an element of (δ + ζ ∗ Φ_{−})C = (ζ ∗ Φ_{−})C is determined by an object y of C together with an oddlength decomposition of the unique map 0 → y. (Notice that y must be non-initial.) In this case, the iso (ζ ∗ Φ_{+})C → (δ + ζ ∗ Φ_{−})C = (ζ ∗ Φ_{−})C takes an element determined by x in C and an even-length decomposition (f_{1}, …, f_{n}) of 0 → x and distinguishes the two following cases:

1. If x = 1 then n ≥ 2, because n is even and C is non-trivial. Let y ≠ 0 be the domain of f_{1}. The iso produces the element in (ζ ∗ Φ_{−})C determined by y and the odd-length decomposition (f_{2}, …, f_{n}) of 0 → y.

2. If x ≠ 1 then the iso produces the element in (ζ ∗ Φ_{−})C given by y = 1 together with the odd-length decomposition (!, f_{1}, …, f_{n}) of 0 → 1.

Let us stress that this description is just the translation into concrete terms of the instructions provided by the proof of Proposition 5.9.

6. Incidence categories

Intermediate between the extensive monoidal category (Cat(sMöI, Set_{f}), ∗, δ) and incidence algebras for Möbius categories are the incidence categories we introduce in this section. Fix a small category C and let C_{1} denote the discrete category whose objects are the morphisms of C. If for every f ∈ C_{1}, If has a finite set of objects (equivalently, the set of decompositions of length 2 of f is finite), then we can define a functor Δ : C_{1} → Fam(C_{1} × C_{1}) by

Δf = ∑_{(f_{0},f_{1})∈If}(f_{1}, f_{0})

for each f in C_{1}.

Exactly as in Proposition 5.4, the functor Δ : C_{1} → Fam(C_{1} × C_{1}) induces a convolution on Cat(C_{1}, Set_{f}). For any α, β ∈ Cat(C_{1}, Set_{f}) define α ∗ β by

(α ∗ β)f = ∑_{(f_{0},f_{1})∈If}(αf_{1}) × (βf_{0})

for any f in C_{1}. Notice that this is the same formula defining convolution in incidence algebras (p. 171 in [2]) except that here we are using finite sets as coefficients instead of elements in a ring.

There is a subtlety involving the unit of convolution in the category Cat(C_{1}, Set_{f}). Define δ : C_{1} → Set_{f} by δid = 1 and δf = 0 for each non-identity f.

6.1. Lemma. Let C be such that every morphism has a finite set of decompositions of length 2. Then the following are equivalent:

1. identities in C are indecomposable,

2. for every α ∈ Cat(C_{1}, Set_{f}), the canonical maps α → α ∗ δ and α → δ ∗ α are isos.

Proof. Straightforward.

It will be useful to introduce the following auxiliary concept.

6.2. Definition. A small category C is pre-Möbius if its identities are indecomposable and for each map f in C, the set of decompositions of f of length 2 is finite.

6.3. Proposition. For any pre-Möbius category C, convolution extends to a monoidal structure on Cat(C_{1}, Set_{f}) which has δ as unit and which distributes over coproducts.

Proof. The functor Δ : C_{1} → Fam(C_{1} × C_{1}) together with the composition δ : C_{1} → Set_{f} determine a ‘comonoid’ structure on the extensive category Fam(C_{1}). The monoidal structure is an instance of a general definition of convolution of ‘linear’ maps from a comonoid to a monoid (just as in Proposition 5.4). In this case, the ‘monoid’ is Set_{f}. Alternatively, one can give a direct proof.

For example, if C is the monoid of natural numbers under addition, then the monoidal category Cat(C_{1}, Set_{f}) is equivalent to the monoidal category of espèces linéares of [7].

6.4. Definition. For any pre-Möbius category C, the extensive monoidal category

Cat(C_{1}, Set_{f}) ≅ Ext(Fam(C_{1}), Set_{f})

will be called the incidence category associated to C.

The discussion above suggests the problem of characterizing Möbius categories among pre-Möbius ones. We will give two solutions: one in Proposition 9.16 and the other (due to Leroux) in Theorem 9.27.

It is natural to denote the terminal object of Cat(C_{1}, Set_{f}) by ζ. It is also natural to define Φ_{+}f as the set of even-length decompositions of f. But notice that for an arbitrary pre-Möbius category this set need not be finite. However, if C is Möbius then it makes sense to define Φ_{+} ∈ Cat(C_{1}, Set_{f}) as above and Φ_{−} in a similar way. It is proved in [14] that δ + ζ ∗ Φ_{−} ⟶ ζ ∗ Φ_{+} is an iso in the incidence category of C. In the next section we show that this result also follows from Proposition 5.9.

7. Extensive Procomonoids

We have been tacitly using the idea that there is a pseudo-functor

(CoMon(Ext, ⊗, Set_{f}))^{op} → Cat

which assigns to each ‘comonoid’ (E, Δ, δ) in (Ext, ⊗, Set_{f}), the extensive ‘convolution’ category (Ext(E, Set_{f}), ∗, δ). But there is no definitive account of (Ext, ⊗, Set_{f}) in the literature and moreover, the ‘comonoids’ we are discussing are rather extreme. So it seems not unreasonable to introduce a category, simpler than CoMon(Ext, ⊗, Set_{f}), but which allows to relate the structure (sMöI, Δ, δ) introduced in Section 5.3 with the structures (C_{1}, Δ, δ) defined in Section 6, for C a Möbius category. We assume that the reader is familiar with the notions of promonoidal categories and functors [3].

7.1. Definition. An (extensive) procomonoid is a small category A equipped with a functor δ : A → Set (the ‘unit’), a functor Δ : A → Fam(A × A) (the ‘comultiplication’) and natural transformations

𝔩_{A,B} : ∫ ^{X}(δX) × P (X, A, B) → A(A, B)

𝔯_{A,B} : ∫ ^{X}(δX) × P (A, X, B) → A(A, B)

𝔞_{A,B,C,D} : ∫ ^{X} P (A, B, X) × P (X, C, D) → ∫ ^{X} P (B, C, X) × P (A, X, D)

where P : A^{op} × A^{op} × A → Set_{f} is defined by

P (A, B, C) = ∑_{(U,V)∈ΔC} A(A, U) × A(B, V)

and such that (A, P, δ, 𝔩, 𝔯, 𝔞) is a promonoidal category.

Day’s work implies that every procomonoid (A, Δ, δ, 𝔩, 𝔯, 𝔞) induces a monoidal structure (Cat(A, Set_{f}), ∗, δ) such that

(α ∗ β)C = ∑_{(U,V)∈ΔC}(αU) × (βV)

for α, β in Cat(A, Set_{f}) and C in A. It also implies, together with Proposition 5.4, that the structure (sMöI, Δ, δ) can be extended to a procomonoid whose induced monoidal structure on Cat(sMöI, Set_{f}) coincides with the one given in Proposition 5.4.

Similarly, if C is pre-Möbius, the structure (C_{1}, Δ, δ) can be extended to a procomonoid whose induced monoidal structure on Cat(C_{1}, Set_{f}) is the incidence category associated to C (Definition 6.4).

Consider now two procomonoids (A, Δ, δ, 𝔩, 𝔯, 𝔞) and (A′, Δ′, δ′, 𝔩′, 𝔯′, 𝔞′) and a functor F : A → A′ equipped with natural isomorphisms

𝔲 : δ → δ′F  and  𝔣 : (Fam(F × F))Δ → Δ′F

as in the diagrams below

[figure: A; δ; ⇒^{𝔲}; F; A′; δ′; A; Δ; F; ⇒^{𝔣}; A′; Δ′; _{Set_{f}}; Fam(A × A); Fam(F ×F); Fam(A′ × A′)]

It is straightforward to verify that 𝔣 induces a natural (in A, B, C) transformation \overline{𝔣} : P (A, B, C) → P′(F A, F B, F C) where P and P′ are induced by A and A′ respectively as in Definition 7.1.

7.2. Definition. The triple (F, 𝔲, 𝔣) is a morphism of procomonoids if (F, 𝔲, \overline{𝔣}) is a promonoidal functor in the sense of Day.

The fact that 𝔲 and 𝔣 are isos implies that the weak monoidal functor

\xymatrix{(Cat(A′, Set_{f}), ∗′, δ′) \ar[r]^{( )∘F} & (Cat(A, Set_{f}), ∗, δ)}

induced by the promonoidal (F, 𝔲, \overline{𝔣}) is strict monoidal. (We have been using ‘monoidal functor’ in the strict sense and we will continue to do so.)

It is straightforward to check that morphisms of procomonoids compose so we define the category ProCom of procomonoids and morphisms between them. The assignment

(A, Δ, δ, 𝔩, 𝔯, 𝔞) ↦ (Cat(A, Set_{f}), ∗, δ)

extends to an ‘indexed category’ ProCom^{op} → Cat whose fibers are extensive, monoidal and such that tensoring preserves coproducts. The bi-categorical details are left for the interested reader.

7.3. Lemma. For every Möbius category C, the assignment f ↦ If induces a morphism I : (C_{1}, Δ, δ) → (sMöI, Δ, δ) of procomonoids.

Proof. We show that the diagram

\xymatrix{C_{1} \ar[d]_{Δ} \ar[r]^{I} & sMöI \ar[d]^{Δ} \\ Fam(C_{1} × C_{1}) \ar[r]_{Fam(I×I)} & Fam(sMöI × sMöI)}

commutes up to iso. Let f ∈ C_{1} be a morphism of C and observe that the top-right composition maps f to ∑(If_{1}, If_{0}) in the category Fam(sMöI × sMöI), where the sum ranges over the objects (f_{0}, f_{1}) in If. On the other hand, the left-bottom composition maps f to

∑_{(f_{0},f_{1})∈If}((f_{0}, f_{1})/(If), (If)/(f_{0}, f_{1}))

but it is easy to check that (If)/(f_{0}, f_{1}) ≅ If_{0} and (f_{0}, f_{1})/(If) ≅ If_{1}. The remaining details are left for the reader.

Readers who are not familiar with promonoidal categories and functors should not feel discouraged by the introduction of the category ProCom. This category provides a more or less natural context where Möbius categories can interact with sMöI. But the fundamental Proposition 7.4 below can be proved without mentioning ProCom.

7.4. Proposition. For every Möbius category C, precomposition with I : C_{1} → sMöI induces a monoidal functor Cat(sMöI, Set_{f}) → Cat(C_{1}, Set_{f}) preserving coproducts and the distinguished elements ζ, Φ_{+} and Φ_{−}.

Proof. Most of the work is done in Lemma 7.3. Alternatively, it is possible to give a direct proof using the explicit definitions of convolution given in Sections 5.3 and 6 and properties of intervals.

As a corollary, we obtain that ‘combinatorial Möbius inversion’ holds in incidence categories. (Compare with Section 11 in [14].)

7.5. Corollary. For every Möbius category C, there are isos δ + ζ ∗ Φ_{−} ⟶ ζ ∗ Φ_{+} and δ + Φ_{−} ∗ ζ ⟶ Φ_{+} ∗ ζ in the incidence category of C.

Proof. The monoidal extensive functor Cat(sMöI, Set_{f}) → Cat(C_{1}, Set_{f}) of Proposition 7.4 preserves the isomorphisms of Proposition 5.9.

The proof of Corollary 7.5 provides an explicit description of the isomorphisms: if f is a map in C, take the interval If and apply the ‘master’ isomorphism defined in Proposition 5.9. This idea of one ‘master’ result was suggested by an algebraic version outlined in [10]. We give a detailed exposition in Sections 8 and 9.

Now, let F : C → D be a functor between pre-Möbius categories. It determines a function F : C_{1} → D_{1} between the respective sets of morphisms.

7.6. Lemma. If F is ULF then it induces a morphism F : (C_{1}, Δ, δ) → (D_{1}, Δ, δ) of procomonoids.

Proof. First we must show that the diagrams below

\xymatrix{C_{1} \ar[dr]_{δ} \ar[r]^{F} & D_{1} \ar[d]^{δ} & C_{1} \ar[d]_{Δ} \ar[r]^{F} & D_{1} \ar[d]^{Δ} \\  & _{Set_{f}} & Fam(C_{1} × C_{1}) \ar[r]_{Fam(F ×F)} & Fam(D_{1} × D_{1})}

commute up to iso. As F is ULF, it reflects isos by Lemma 4.4. Then there is a canonical iso δ → δF. Consider now the diagram on the right above. Let f be a map in C. The topright composition applied to f produces ∑_{(v,w)∈I(F f)}(w, v). On the other hand, the leftbottom composition produces ∑_{(g,h)∈If}(F h, F g). All we need is the iso F_{f} : If → I(F f) given by the ULF condition. The remaining details are left for the reader.

Let us reformulate the above result as follows.

7.7. Proposition. The assignment C ↦ (C_{1}, Δ, δ) mapping a Möbius category C to its associated procomonoid extends to an inclusion ulfMö → ProCom.

Procomonoids are analogous to the Lois de décomposition combinatoire introduced in Section 7.4 of [7]. The main difference is that Joyal uses groupoids and symmetric monoidal completions instead of categories and Fam. The reader is invited to present the monoidal category of species introduced loc. cit. as the convolution category for an extensive procomonoid.

8. The Hopf rig of Möbius intervals

The rest of the paper deals with various algebraic structures related to Möbius categories. As much as possible we will try to derive the algebraic results from the combinatorial ones we presented in previous sections.

A rig A is a set equipped with two commutative monoid structures (A, +, 0) and (A, ·, 1) such that x · (y + z) = (x · y) + (x · z) and x · 0 = 0. (We will usually avoid writing · and simply use juxtaposition.) A morphism A → B of rigs is a function preserving the two monoid structures. Let Rig be the category of rigs and morphisms between them. We will freely use modules and tensors over rigs. We denote the category of R-modules by Mod_{R} and tensors by ⊗. We typically mean tensors of ℕ, so that in particular the coproduct in Rig is also denoted by a tensor sign. The word ring shall mean a commutative ring with unit. In case the ‘multiplication’ is not commutative we will use the word algebra or speak of a non-commutative ring or rig. We let Ring → Rig be the full subcategory of rings.

If (C, Δ, ϵ) is a coalgebra and (A, ∇, u) is an algebra in Mod_{R} then the R-module Hom(C, A) of linear maps (from the module C to the module A) can be equipped with an algebra structure. For any α, β ∈ Hom(C, A), their convolution α ∗ β ∈ Hom(C, A) is defined by

\xymatrix{C \ar[r]^{Δ} & C ⊗ C \ar[r]^{α⊗β} & A ⊗ A \ar[r]^{∇} & A}

and induces an algebra structure on Hom(C, A) with unit δ = uϵ : C → ℕ → A. Let us call it the convolution algebra associated to the comonoid C and the monoid A. For A = ℕ, the resulting algebra is called the dual of the coalgebra C and it is denoted by C^{∗}. The assignment C ↦ C^{∗} extends to a functor (CoMon(Mod_{ℕ}))^{op} → Algebras where Mod_{ℕ} is the category of ℕ-modules (i.e. commutative monoids) and Algebras denotes some convenient category of non-commutative rigs.

8.1. Iso Klassen. If C is an essentially small category we can quotient its underlying collection of objects by the equivalence relation ‘is isomorphic to’. We denote the resulting set by 𝔅C following the notation in [15]. The object in 𝔅C determined by an object C in C will typically be denoted by [C]. Any monoidal structure on C induces a monoid structure on the set 𝔅C. The resulting structure may be called the Burnside monoid of C and will be denoted by 𝔅C. Clearly, any monoidal functor F : C → D induces a monoid morphism and we will denote it by 𝔅F : 𝔅C → 𝔅D. This general ‘𝔅 construction’ has at least three applications:

1. In its original context, it is mainly applied to linear categories C with a tensor product, and further quotiented to obtain a group. (See for example the definition of the abelian group K_{0}(A) in p. 65 of [17], where A is a small abelian category.)

2. More recently it was applied to prextensive categories in [15, 11]. Indeed, if C is an extensive category with products, 𝔅C is naturally equipped with a rig structure which is called the Burnside rig of C in [15]. In particular, 𝔅(Set_{f}) = ℕ.

3. Here we will apply the general construction in the following third case. If C is an extensive category equipped with a monoidal structure that distributes over coproducts then 𝔅C is naturally equipped with a non-commutative rig structure. Following Schanuel’s terminology, the resulting structure 𝔅C will be called the Burnside algebra of C. Of course, if the monoidal structure is symmetric then the Burnside algebra is a rig.

A simple general result may serve to illustrate the construction. Let (A, ⊗, z) be an essentially small symmetric monoidal category. The monoidal structure extends to the coproduct completion FamA by declaring (∑_{i} a_{i}) ⊗ (∑_{j} b_{j}) = ∑_{(i,j)} a_{i} ⊗ b_{j}. It is not difficult to show that (FamA, ⊗, z) is a symmetric monoidal category such that ⊗ distributes over coproducts, and that the embedding y : A → FamA is monoidal.

8.2. Lemma. The monoid morphism 𝔅y : 𝔅(A, ⊗, z) → 𝔅(FamA, ⊗, z) is universal from 𝔅(A, ⊗, z) to a rig.

In other words, 𝔅(FamA, ⊗, z) is the monoid-rig ℕ[𝔅(A, ⊗, z)]. We will apply this result in the next section. Before that, we need to discuss another general fact.

It is not unusual to find arguments of the construction 𝔅 as fibers of an indexed category. So it is useful to settle a good notation to reflect this fact. Consider the context of K-theory, for example. If R is a ring, K_{0}(R) actually denotes the result of applying K_{0} to the category of finitely generated projective left R-modules (see p. 73 in [17]).

8.3. Definition. [𝔎-notation] Fix an indexed category and let X be an object in the base. We denote by 𝔎X the result of applying 𝔅 to the fiber determined by X.

The 𝔎-notation intends to extend the usage of ‘K’ initiated by Grothendieck as an abbreviation for Klassen, meaning ‘isomorphism classes’. (This origin of Grothendieck’s notation was pointed out by Pierre Cartier.)

As another example, let E be an extensive category and consider its canonical indexing. If X is an object in E then 𝔎X denotes the additive monoid 𝔅(E/X).

We will use this notation in the context of the indexed (extensive-monoidal-)category ProCom^{op} → Cat introduced in Section 7. In this context, 𝔎(A, Δ, δ) denotes the algebra 𝔅(Cat(A, Set_{f}), ∗, δ). Let us stress that while 𝔅(sMöI, ×, 1) is just a monoid, 𝔎(sMöI, Δ, δ) is a non-commutative rig. In view of Proposition 7.7 it is reasonable to slightly extend the 𝔎-notation further.

8.4. Definition. [𝔎-notation for Möbius categories] If C is a Möbius category, then 𝔎C denotes the algebra 𝔎(C_{1}, Δ, δ) = 𝔅(Cat(C_{1}, Set_{f}), ∗, δ). In other words, 𝔎C is the Burnside algebra of the incidence category associated to C.

It is possible to give at this point a vague picture of the categories involved in the context where we intend to apply the construction 𝔅.

\xymatrix{ &  & _{(Cat_{+,∗})_{op}} \ar[r]^{𝔅^{op}} & _{Algebras_{op}} \\ _{ulfMö} \ar[r] & ProCom \ar[urr]^{𝔎} \ar[d] \ar[ur]^{∗} \ar@{.>}[r] & CoMon(Ext) \ar@{.>}[u]^{∗} \ar@{.>}[d] \ar@{.>}[r]^{CoMon(𝔅)} & CoMon(Mod_{ℕ}) \ar[d] \ar[u]_{∗} \\  & Cat \ar[r]_{Fam} & Ext \ar[r]_{𝔅} & _{Mod_{ℕ}}}

The bottom row is clear. In the middle row appears CoMon(Ext) which we have not introduced in sufficient detail for the reasons explained in the introduction to Section 5. Hence, the ‘functors’ from it or to it are dotted and we only use the inner part of the diagram as a ‘manner of speaking’. The functors going down are the obvious forgetful functors. The functors marked with ∗ produce ‘dual’ categories or algebras. The category Cat_{+,∗} is a sufficiently large category of extensive monoidal categories. Algebras is the convenient category of algebras fixed in the introduction to the present section. The curved arrow reflects the notation introduced in Definition 8.3.

8.5. The bialgebra of Möbius intervals and its dual. Recall that a Möbius interval is a finite one-way category with initial and terminal object (Definition 3.10). The symmetric monoidal category (sMöI, ×, 1) of Möbius intervals and strict functors between them was introduced in Section 4.5 as a ‘convenient’ category of intervals. The monoidal structure is denoted by × because it is inherited from the cartesian product in the larger category MöI (of Möbius intervals and arbitrary functors between them), although it no longer has the universal property for the morphisms in sMöI.

8.6. Definition. We call 𝔅(sMöI, ×, 1) the Burnside monoid of intervals and we will denote it by I.

By Lemma 8.2, the monoidal structure (sMöI, ×, 1) extends to Fam(sMöI) and the rig 𝔅(Fam(sMöI), ×, 1) can be identified with the monoid-rig ℕ[I]. In this section we show that ℕ[I] is a bialgebra. The monoid-rig structure on ℕ[I] determines an algebra structure (ℕ[I], ∇, u) where u is the unique ℕ → ℕ[I] and ∇ : ℕ[I] ⊗ ℕ[I] → ℕ[I] is such that ∇([C] ⊗ [D]) = [C] × [D] = [C × D]. The module ℕ[I] can also be equipped with a coalgebra structure that we denote by (ℕ[I], Δ, δ). This is essentially the ‘Burnside coalgebra’ associated to the structure (Fam(sMöI), Δ, δ) discussed in Section 5.3. But let us briefly give here some of the explicit details.

Recall that ℕ[I], as a module, is free on I. So linear morphisms from ℕ[I] are determined by functions from I. Define δ : ℕ[I] → ℕ to be the map determined by the function I → ℕ that assigns 1 to the trivial interval and 0 to everything else. The comultiplication Δ : ℕ[I] → ℕ[I] ⊗ ℕ[I] is determined by the function I → ℕ[I] ⊗ ℕ[I] defined by

[C] ↦ ∑_{x∈C}[x/C] ⊗ [C/x]

where the sum ranges over the objects of C. It is straightforward to verify that this is well-defined and that (ℕ[I], Δ, δ) is indeed a coalgebra. The details are essentially the combinatorial properties of intervals suggested in the explicit proof of Proposition 5.4.

8.7. Lemma. The structure (ℕ[I], ∇, u, Δ, δ) is a bialgebra.

Proof. It is enough to show that Δ and δ are algebra maps. That is, that the following diagrams

\xymatrix{ℕ[I] ⊗ ℕ[I] \ar[r]^{∇} \ar[d]_{δ⊗δ} & ℕ[I] \ar[d]^{δ} \\ ℕ ⊗ ℕ \ar[r]_{·} & ℕ}

\xymatrix{ℕ[I] ⊗ ℕ[I] \ar[d]_{Δ⊗Δ} \ar[rr]^{∇} &  & ℕ[I] \ar[d]^{Δ} \\ ℕ[I] ⊗ ℕ[I] ⊗ ℕ[I] ⊗ ℕ[I] \ar[r]_{id⊗τ⊗id} & ℕ[I] ⊗ ℕ[I] ⊗ ℕ[I] ⊗ ℕ[I] \ar[r]_{∇⊗∇} & ℕ[I] ⊗ ℕ[I]}

commute, where τ : ℕ[I] ⊗ ℕ[I] → ℕ[I] ⊗ ℕ[I] is the twist map. The first diagram commutes because [C × D] = [1] if and only if [C] = [D] = [1]. To prove that the second diagram commutes, consider a basic element [C] ⊗ [D] in ℕ[I] ⊗ ℕ[I] with [C], [D] ∈ I. It is straightforward to check that both compositions ℕ[I] ⊗ ℕ[I] → ℕ[I] ⊗ ℕ[I] applied to [C] ⊗ [D] result in

∑_{(c,d)}[(c, d)/(C × D)] ⊗ [(C × D)/(c, d)]

where the sum ranges over the objects (c, d) ∈ C × D.

(Notice that the main part of the proof of Lemma 8.7 is done at the level of sMöI. But the relevant diagrams commute on the nose because we have collapsed isos to equalities.)

Consider now the dual ℕ[I]^{∗} of ℕ[I]. Since the rig ℕ[I] is free on the monoid I, the inclusion I → ℕ[I] induces an isomorphism Set(I, ℕ) ≅ Hom(ℕ[I], ℕ) = ℕ[I]^{∗}. For functions α, β ∈ Set(I, ℕ) ≅ ℕ[I]^{∗}, their convolution α ∗ β ∈ ℕ[I]^{∗} is defined by the formula (α ∗ β)[C] = ∑_{x∈C} α[x/C] · β[C/x].

Among the arbitrary elements I → ℕ in ℕ[I]^{∗}, we can distinguish certain ‘special’ ones. The element ζ ∈ ℕ[I]^{∗} is defined by ζ[C] = 1 ∈ ℕ for every [C] in I = 𝔅(sMöI, ×, 1). The element Φ_{+} ∈ ℕ[I]^{∗} assigns, to each [C] in I, the number Φ_{+}[C] ∈ ℕ of even-length decompositions of the unique map 0 → 1 in C. Similarly for Φ_{−} ∈ ℕ[I]^{∗}. These elements of ℕ[I]^{∗} are, of course, related to the homonymous objects in Cat(sMöI, Set_{f}) introduced in Section 5.1. A precise relation is established in Proposition 8.8 below. But it seems better to approach this relation from a slightly more general perspective.

Let (A, Δ, δ) be procomonoid and 𝔎(A, Δ, δ) = 𝔅(Cat(A, Set_{f}), ∗, δ) be its Burnside algebra. The construction 𝔅, applied to functors, induces a function

\xymatrix{Cat(A, Set_{f}) \ar[r]^{≃} & Ext(FamA, Set_{f}) \ar[r]^{𝔅} & Hom(𝔅(FamA), ℕ)}

A general result should explain under what conditions the procomonoid (A, Δ, δ) induces a comonoid structure on 𝔅(FamA) such that the function above induces an algebra map

𝔎(A, Δ, δ) → (𝔅(FamA))^{∗}

from the Burnside algebra of (Cat(A, Set_{f}), ∗, δ) to the dual of the comonoid 𝔅(FamA). (Intuitively, this ‘result’ should be a corollary of the precise definition of the dotted arrow ProCom → CoMon(Mod_{ℕ}) in the diagram at the end of Section 8.1.)

For our purposes it is enough to prove the (A = sMöI)-version of this ‘result’. We have already explained before Lemma 8.7 how the procomonoid (sMöI, Δ, δ) induces a comonoid (ℕ[I], Δ, δ) on the ℕ-module 𝔅(Fam(sMöI)) = ℕ[𝔅(sMöI)] = ℕ[I].

8.8. Proposition. The function

\xymatrix{Cat(sMöI, Set_{f}) \ar[r]^{≃} & Ext(Fam(sMöI), Set_{f}) \ar[r]^{𝔅} & Hom(ℕ[I], ℕ)}

underlies an algebra map 𝔎(sMöI, Δ, δ) → ℕ[I]^{∗} preserving ζ, Φ_{+} and Φ_{−}.

Proof. Let us denote the function Cat(sMöI, Set_{f}) → Hom(ℕ[I], ℕ) by 𝔟. It clearly preserves 0, + and δ. To prove that 𝔟 preserves ∗, compare the explicit definitions of convolution in ℕ[I]^{∗} (given after Lemma 8.7) and in Cat(sMöI, Set_{f}), given just before Proposition 5.4. It is also easy to check that 𝔟 maps the special objects in 𝔎(sMöI, Δ, δ), determined by those defined in Section 5.1, to the special elements in ℕ[I]^{∗} defined after Lemma 8.7. For example, (𝔟Φ_{+})[C] = (𝔅Φ_{+})[C] = [Φ_{+}C] which is the number of evenlength decompositions of 0 → 1 in the Möbius interval C.

The algebra 𝔎(sMöI, Δ, δ) has, as elements, iso-classes of functorial operations on sMöI. So it is closer to the combinatorial objects that are our main object of study. On the other hand, the algebra ℕ[I]^{∗} is easier to manipulate because its elements can be identified with (arbitrary) functions I → ℕ. The algebra morphism 𝔟 is a ‘counting instrument’ that allows to transfer equalities in 𝔎(sMöI, Δ, δ), that record the existence of isomorphisms, to numerical equalities in ℕ[I]^{∗}. For example:

8.9. Corollary. The equalities

δ + ζ ∗ Φ_{−} = ζ ∗ Φ_{+} and δ + Φ_{−} ∗ ζ = Φ_{+} ∗ ζ

hold in ℕ[I]^{∗}.

Proof. The equalities hold in 𝔎(sMöI, Δ, δ) by Proposition 5.9. Apply the counting instrument given in Proposition 8.8 to conclude that the equalities hold in ℕ[I]^{∗}.

Allowing integer coefficients we obtain a more familiar formulation.

8.10. Corollary. [Master Möbius inversion] The element ζ in Hom(ℕ[I], ℤ) is invertible and its inverse is μ = Φ_{+} − Φ_{−}.

Proof. The unique morphism ℕ → ℤ induces an algebra map ℕ[I]^{∗} → Hom(ℕ[I], ℤ) and as such, preserves the identities of Corollary 8.9. It follows that δ = ζ ∗ (Φ_{+} − Φ_{−}) and δ = (Φ_{+} − Φ_{−}) ∗ ζ, which means that μ, as defined in the statement, is the inverse of ζ.

In particular, μ[• → •] = −1. This is the concentrated expression of the fact that for every indecomposable non-identity map f, in any Möbius category C, μ_{f} = −1. Indeed, such maps correspond to ULF functors (• → •) → C and they are the basic piece of information required to calculate the value of μ at each non-identity map. We will see in Corollary 9.9 how the ‘master’ μ ∈ Hom(ℕ[I], ℤ) determines the value of the individual μ’s in each incidence algebra.

8.11. The algebraic group determined by sMöI. For each rig A, evaluation at the trivial interval induces a map r : Hom(ℕ[I], A) → A. Denote by GA → Hom(ℕ[I], A) the inverse image of 1 ∈ A along r : Hom(ℕ[I], A) → A. Clearly, GA contains δ and is closed under convolution, so we consider GA as a submonoid of Hom(ℕ[I], A). For any rig morphism A → B, the induced Hom(ℕ[I], A) → Hom(ℕ[I], B) restricts to a monoid morphism GA → GB. So the assignment A ↦ GA extends to a functor from Rig to the category of monoids.

We will show that GA is a group when A is a ring. This is actually a corollary of a more general ‘inversion’ result implied by Proposition 5.9. Fix a rig A and denote the induced algebra by (A, ∇, u). If G is an element in the convolution algebra Hom(ℕ[I], A) then define G_{+} in Hom(ℕ[I], A) by

G_{+}[C] = ∑_{n≥0} ∑_{(f_{1},...,f_{n})} G[If_{1}] · . . . · G[If_{n}]

where (f_{1}, …, f_{n}) ∈ Φ_{+}[C]. Similarly, define G_{−} in Hom(ℕ[I], A) by the same formula except that (f_{1}, …, f_{n}) ranges over Φ_{−}[C].

8.12. Lemma. For every G in GA, the equations

δ + G ∗ G_{−} = G ∗ G_{+}  and  δ + G_{−} ∗ G = G_{+} ∗ G

hold in Hom(ℕ[I], A).

Proof. If G1 = 1 then there is a unique G_{η} in Hom(ℕ[I], A) such that δ + G_{η} = G, where δ denotes here the unit of Hom(ℕ[I], A). We claim that G_{η} ∗ G_{+} = G_{−}. To prove the claim notice that

(G_{η} ∗ G_{+})C = ∑_{x∈C} G_{η}(x/C) · G_{+}(C/x) = ∑_{x≠1} G[x/C] · ∑_{n≥0} ∑_{(g_{1},...,g_{n})} G[Ig_{1}] · . . . · G[Ig_{n}]

where (g_{1}, …, g_{n}) ranges over the finite set Φ_{+}(C/x). On the other hand,

G_{−}[C] = ∑_{m≥0} ∑_{(f_{1},...,f_{m})} G[If_{1}] · . . . · G[If_{m}]

where (f_{1}, …, f_{m}) ranges over the set Φ_{−}C. The equality G_{η} ∗ G_{+} = G_{−} follows by applying the reindexing η ∗ Φ_{+} → Φ_{−} in Cat(sMöI, Set_{f}) presented in Lemma 5.7. Lemma 5.8 also has an analog in the present context: δ + G_{η} ∗ G_{−} = G_{+}. The following variation of Proposition 5.9

G∗G_{+} = (δ+G_{η})∗G_{+} = G_{+}+G_{η} ∗G_{+} = δ+G_{η} ∗G_{−}+G_{−} = δ+(G_{η} +δ)∗G_{−} = δ+G∗G_{−}

can be applied to finish the proof.

Let A be a ring and let X and Y be A-algebras. An A-algebra map f : X → Y is called local if for every x in X, fx invertible implies x invertible. Having a local map is like having a determinant, especially if the codomain is commutative, as below; in one way it’s better because determinants do not preserve addition.

8.13. Lemma. If X and Y are A-algebras and r : X → Y has a section then the following are equivalent:

1. r is local,

2. for every x in X, rx = 1 implies x is invertible.

Proof. Straightforward.

This justifies restricting to the “special” (det = 1) algebraic group below.

8.14. Proposition. For any ring A, the morphism r : Hom(ℕ[I], A) → A is local.

Proof. For each a in A, we let sa be the linear map ℕ[I] → A determined by the function I → A that maps 1 ∈ I to a and every other interval to 0. It is easy to prove that the assignment a ↦ sa is an algebra map s : A → Hom(ℕ[I], A) and a section of r. Now let G ∈ Hom(ℕ[I], A) be such that rG = 1. Lemma 8.12 implies that G_{+} − G_{−} is inverse to G. So r is local by Lemma 8.13.

Altogether, we obtain a functor G : Ring → Grp which assigns, to each ring A, a subgroup of the group of invertible elements of Hom(ℕ[I], A).

It should be noticed that in the particular case of A = ℤ, if G ∈ Hom(ℕ[I], ℤ) is invertible then (G1) · (G^{−1}1) = (G ∗ G^{−1})1 = δ1 = 1 ∈ ℤ, so G1 = 1 or G1 = −1. In other words, for every invertible G in Hom(ℕ[I], ℤ), either G ∈ Gℤ or −G ∈ Gℤ.

8.15. The Hopf algebra of Möbius intervals. The rig ℕ[I] is not a ring. So we cannot apply Proposition 8.14 to conclude that the identity id ∈ G(ℕ[I]) → Hom(ℕ[I], ℕ[I]) is invertible. Instead, the identity id : ℕ[I] → ℕ[I] determines two maps id_{+} and id_{−} in Hom(ℕ[I], ℕ[I]) that we denote here by S_{+} and S_{−}. Applying Lemma 8.12 we obtain the following.

8.16. Corollary. In Hom(ℕ[I], ℕ[I]), δ + id ∗ S_{−} = id ∗ S_{+} and δ + S_{−} ∗ id = S_{+} ∗ id hold.

The linear maps S_{+} and S_{−} should be thought of as a ‘positive’ and a ‘negative’ part of an antipode. To make this idea precise, let H be the monoid ring ℤ[I]. Extension along the rig morphism ℕ → ℤ equips H with a bialgebra structure extending that of Lemma 8.7.

8.17. Proposition. The bialgebra H is a Hopf algebra.

Proof. Consider the extensions S_{+}, S_{−} : H → H of the maps considered in Corollary 8.16. Then δ = id ∗ (S_{+} − S_{−}) and δ = (S_{+} − S_{−}) ∗ id in Hom(H, H). So S = S_{+} − S_{−} is an antipode for the bialgebra H.

The explicit definition of S : H → H may be stated as follows

S[C] = ∑_{n≥0} ∑_{(f_{1},...,f_{n})}(−1)^{n}([If_{1}] × … × [If_{n}])

where (f_{1}, …, f_{n}) ∈ Φ[C].

Perhaps it is fair to refine the term ‘an antipode’ for bialgebras B over a rig A to mean a pair of linear maps S_{+}, S_{−} : B → B such that the equalities δ + id ∗ S_{−} = id ∗ S_{+} and δ + S_{−} ∗ id = S_{+} ∗ id hold in the convolution algebra Hom(B, B)?

9. Incidence algebras

We defined a category C to be pre-Möbius if its identities are indecomposable and for every map f, the set of decompositions of f of length 2 is finite (Definition 6.2). For such a category we defined a monoidal structure on Cat(C_{1}, Set_{f}) where C_{1} is the discrete category whose objects are the morphisms of C. The resulting extensive monoidal category was called the incidence category of C (Definition 6.4). In this section we introduce incidence algebras with coefficients in a rig and we characterize Möbius categories in terms of their incidence algebras.

9.1. Incidence algebras with coefficients in a rig. Let C be a small category and denote by ℕ[C_{1}] the free ℕ-module on the set C_{1} of morphisms of C. If for every map f in C, the set of decompositions of length 2 is finite then we can define the function C_{1} → ℕ[C_{1}] ⊗ ℕ[C_{1}] that maps f in C_{1} to ∑_{(f_{0},f_{1})∈If} f_{1} ⊗ f_{0}. (See Section X in [6].) Denote its linear extension by Δ : ℕ[C_{1}] → ℕ[C_{1}] ⊗ ℕ[C_{1}]. Also, define δ : ℕ[C_{1}] → ℕ to be the linear map determined by δid = 1 and δf = 0 for every non-identity f in C_{1}.

9.2. Lemma. For C as above, the structure (ℕ[C_{1}], Δ, δ) is a comonoid if and only if C is pre-Möbius.

Proof. The comultiplication is coassociative. The issue is with the unit (Lemma 6.1). The diagrams below

\xymatrix{ℕ[C_{1}] \ar[dr]_{≅} \ar[r]^{Δ} & ℕ[C_{1}] ⊗ ℕ[C_{1}] \ar[d]^{δ⊗id} & ℕ[C_{1}] \ar[dr]_{≅} \ar[r]^{Δ} & ℕ[C_{1}] ⊗ ℕ[C_{1}] \ar[d]^{id⊗δ} \\  & ℕ ⊗ ℕ[C_{1}] &  & ℕ[C_{1}] ⊗ ℕ}

commute if and only if identities are indecomposable.

So, from now on, we let C be a pre-Möbius category. We define the incidence algebras determined by C as certain convolution algebras (in the sense explained in the paragraph before 8.1).

9.3. Definition. The incidence algebra of C (with coefficients in the rig A) is the convolution algebra Hom(ℕ[C_{1}], A). We denote it by AC.

Elements of AC can be identified with functions C_{1} → A. If α, β ∈ AC then

(α ∗ β)f = ∑_{(f_{0},f_{1})∈If}(αf_{1})(βf_{0})

where we use juxtaposition to denote multiplication in A. For α in AC and f a map in C we will write α_{f} instead of αf. When A is a ring then AC coincides with the incidence algebra as defined in [2]. We briefly recall some of the usual examples (mainly taken from [4] and [2]).

9.4. Example. Let ℕ be the standard additive monoid of natural numbers. Then Aℕ is isomorphic to the algebra of formal power series A[[X]] with coefficients in A. In this guise, an element α of Aℕ may be written as

α = ∑_{n≥0} α_{n}X^{n}

with α_{n} ∈ A for every n ∈ ℕ.

Algebras of formal power series in more than one variable appear as incidence algebras on free monoids or free commutative monoids on more than one generator.

9.5. Example. Let ω be natural numbers equipped with its usual order. Then Aω is the algebra of upper triangular matrices with entries in A.

9.6. Example. Let ℕ^{∗} be the monoid of positive integers under multiplication. Then Aℕ^{∗} coincides with the algebra of formal Dirichlet series

α = ∑_{n≥1} \frac{α_{n}}{n^{s}}

with α_{n} ∈ A. Convolution of Dirichlet series is given by (α ∗ β)_{n} = ∑_{ij=n} α_{i}β_{j}.

In all incidence algebras there is an element ζ such that ζ_{f} = 1 for each f in C_{1}. If C is Möbius, there are also elements Φ_{+}, Φ_{−} which count even and odd length decompositions modulo the characteristic of the coefficient rig. Notice that for each morphism t : A → B of rigs, the induced algebra map AC → BC preserves ζ, Φ_{+} and Φ_{−}.

For the rest of the subsection let C be a Möbius category. Then, the function C_{1} → I given by the assignment f ↦ If induces a linear map I : ℕ[C_{1}] → ℕ[I], where ℕ[I] still denotes the bialgebra of Lemma 8.7.

9.7. Lemma. The linear map I : ℕ[C_{1}] → ℕ[I] is a morphism of coalgebras.

Proof. Essentially by Lemma 7.3.

The coalgebra morphism I : ℕ[C_{1}] → ℕ[I] of Lemma 9.7 induces an algebra map Hom(ℕ[I], ℕ) → Hom(ℕ[C_{1}], ℕ) between the dual convolution algebras, that is, an algebra map ℕ[I]^{∗} → ℕC, for any Möbius category C. So we can conclude the following result suggested in [10].

9.8. Theorem. For every Möbius category C and any rig A there exists a canonical algebra map ℕ[I]^{∗} → AC. Moreover, this morphism preserves ζ, Φ_{+} and Φ_{−}. So the equalities δ + ζ ∗ Φ_{−} = ζ ∗ Φ_{+} and δ + Φ_{−} ∗ ζ = Φ_{+} ∗ ζ hold in all incidence algebras.

Proof. That ℕ[I]^{∗} → ℕC preserves ζ, Φ_{+}, Φ_{−} follows from the fact that, in incidence algebras, all these elements are really calculated via intervals. The generalization to arbitrary rigs is obtained by postcomposing with the canonical ℕC → AC induced by the unique ℕ → A. The resulting algebra map ℕ[I]^{∗} → AC preserves the equalities stated in Corollary 8.9.

Restricting to rings we obtain an actual inverse for ζ and a closed formula for it. (The following result is stated as the first part of Proposition 3.2 in [2]. We outline the proof loc. cit. in Section 10.1. The proofs we present below are based on the idea of a ‘master’ inversion result as discussed above.)

9.9. Corollary. Let C be a Möbius category. If A is a ring then ζ is invertible in AC and its inverse μ equals Φ_{+} − Φ_{−}.

Proof. The coalgebra morphism ℕ[C_{1}] → ℕ[I] and the unique ℤ → A induce algebra maps

Hom(ℕ[I], ℤ) → Hom(ℕ[C_{1}], ℤ) → Hom(ℕ[C_{1}], A) = AC

and the resulting composition can be applied to push-forward the Master Möbius Inversion result given in Corollary 8.10. Alternatively, one can apply Theorem 9.8 and calculate as in Corollary 8.10.

Lemma 9.7 is the main tool to transfer (in Theorem 9.8) the relevant equalities in ℕ[I]^{∗} to the incidence algebra ℕC. But notice that we had already performed an analogous step in Proposition 7.4. So let us sketch an alternative proof of the fact that the equalities δ + ζ ∗ Φ_{−} = ζ ∗ Φ_{+} and δ + Φ_{−} ∗ ζ = Φ_{+} ∗ ζ hold in ℕC. Corollary 7.5 implies that these equalities hold in the Burnside algebra 𝔎C = 𝔎(C_{1}, Δ, δ) of the incidence category of C. So the following analog of Proposition 8.8 completes the alternative proof.

9.10. Lemma. The function

\xymatrix{Cat(C_{1}, Set_{f}) \ar[r]^{≃} & Ext(Fam(C_{1}), Set_{f}) \ar[r]^{𝔅} & Hom(ℕ[C_{1}], ℕ)}

underlies an isomorphism 𝔎C → ℕC of algebras preserving ζ, Φ_{+} and Φ_{−}.

Proof. As C_{1} is discrete, 𝔅(Cat(C_{1}, Set_{f})) ≅ Set(C_{1}, ℕ) ≅ ℕC.

9.11. The rig of lengths. The purpose of this section is to prove a converse to Lemma 9.7. We will not need the result in the rest of the paper, but it is relevant to discuss it at this point because the proof involves understanding length (in the sense of Definition 4.9) as an element in a convolution algebra.

Let ω be the totally ordered set of natural numbers. Denote by ω_{-∞} the result of adding a new initial object that we denote by −∞. The resulting join semi-lattice (ω_{-∞}, ∨, −∞) can be equipped with a symmetric monoidal structure (ω_{-∞}, +, 0) where + : ω_{-∞} × ω_{-∞} → ω_{-∞} is the usual addition extended with the case m + n = −∞ if either m or n are −∞. It is straightforward to check that + distributes over ∨, so the Burnside algebra 𝔅(ω_{-∞}) is a rig that we denote by ℕ_{-∞}. Notice that in this case, the construction ω_{-∞} ↦ 𝔅(ω_{-∞}) = ℕ_{-∞} simply ‘forgets the order’, so the underlying set of ℕ_{-∞} is {−∞} ∪ ℕ.

Recall the functor ℓ : (sMöI, ×, 1) → (ω, +, 0) introduced in Lemma 4.10. The obvious injection ω → ω_{-∞} extends to a monoidal (ω, +, 0) → (ω_{-∞}, +, 0) and so, there is a monoidal (sMöI, ×, 1) → (ω_{-∞}, +, 0) which we denote by ℓ again. Applying 𝔅 we obtain a monoid morphism

\xymatrix{I = 𝔅(sMöI, ×, 1) \ar[r]^{𝔅ℓ} & 𝔅(ω_{-∞}) = ℕ_{-∞}}

and the universal property of I → ℕ[I] implies the existence of a unique rig morphism as below

\xymatrix{I \ar[dr]_{𝔅ℓ} \ar[r] & ℕ[I] \ar@{.>}[d] \\  & ℕ_{-∞}}

that we denote by ℓ : ℕ[I] → ℕ_{-∞} and that may be seen as an element in the convolution algebra Hom(ℕ[I], ℕ_{-∞}). Notice that linearity of ℓ means that ℓ0 = −∞ and ℓ([C] + [D]) = ℓ[C] ∨ ℓ[D].

9.12. Lemma. The equality ℓ ∗ ℓ = ℓ holds in Hom(ℕ[I], ℕ_{-∞}).

Proof. Observe that

(ℓ ∗ ℓ)[C] = ⋁_{x∈C} ℓ[x/C] + ℓ[C/x]

which equals ℓ[C] by Definition 4.9.

The idempotent nature of ℓ ∈ Hom(ℕ[I], ℕ_{-∞}) plays an important role. Before using ℓ we need to discuss a related concept in incidence algebras.

9.13. Lemma. Let C be a pre-Möbius category and let L ∈ Hom(ℕ[C_{1}], ℕ_{-∞}) be such that Lid = 0 and L ∗ L = L. If f = gh in C then (Lh) + (Lg) ≤ Lf.

Proof. Calculate:

(Lh) + (Lg) ≤ ⋁_{(f_{0},f_{1})∈If}(Lf_{1}) + (Lf_{0}) = (L ∗ L)f = Lf

using convolution in Hom(ℕ[C_{1}], ℕ_{-∞}) and the hypothesis.

We will find it useful to extend this result to decompositions.

9.14. Lemma. Let C be a pre-Möbius category and let L ∈ Hom(ℕ[C_{1}], ℕ_{-∞}) be such that Lid = 0 and L ∗ L = L. Then, for every morphism f in C, and every decomposition (f_{1}, …, f_{n}) of f, (Lf_{1}) + … + (Lf_{n}) ≤ Lf.

Proof. By induction on the length of decompositions. If n = 0 we have that 0 = Lid by hypothesis. If n = 1 then Lf ≤ Lf trivially. So consider n ≥ 1 and let (f_{1}, …, f_{n+1}) be a decomposition of f. If we let g = f_{1}f_{2} … f_{n} then (Lf_{1}) + … + (Lf_{n}) ≤ Lg by inductive hypothesis. We also have that f_{n+1}g = f. So, using Lemma 9.13, we can calculate:

(Lf_{1}) + … + (Lf_{n}) + (Lf_{n+1}) ≤ (Lg) + (Lf_{n+1}) ≤ Lf

to complete the proof.

If we require further conditions on L then we can make a connection with length.

9.15. Lemma. Let C be a pre-Möbius category. If there is an L ∈ Hom(ℕ[C_{1}], ℕ_{-∞}) such that the following hold:

1. For every f in C, Lf ≥ 0,

2. Lf = 0 if and only if f = id and

3. L ∗ L = L,

then C is Möbius.

Proof. By Corollary 2.8, it is enough to show that the length l_{f} of f is finite for every map f in C. Since Lf ≥ 0 by hypothesis, it is enough to show that l_{f} ≤ Lf. We do this by induction. More precisely, we show that for every k ∈ ℕ, if Lf = k then l_{f} ≤ Lf. If Lf = 0 then f = id and so l_{f} = 0 ≤ Lf. Now let Lf = k + 1 and consider a decomposition (f_{1}, …, f_{n}) of f. Lemma 9.14 implies that (Lf_{1}) + … + (Lf_{n}) ≤ Lf. The first two items imply that Lf_{i} ≥ 1 so n ≤ Lf. But this is for every decomposition of f. So l_{f} ≤ Lf, as we needed to show.

We can now prove a converse to Lemma 9.7, which we state as another characterization of Möbius categories.

9.16. Proposition. Let C be a pre-Möbius category. Then C is Möbius if and only if there exists a morphism ℕ[C_{1}] → ℕ[I] of coalgebras.

Proof. If C is Möbius then the coalgebra morphism is that of Lemma 9.7. To prove the converse, let J : ℕ[C_{1}] → ℕ[I] be a morphism of coalgebras and consider the induced algebra map Hom(ℕ[I], ℕ_{-∞}) → Hom(ℕ[C_{1}], ℕ_{-∞}). Lemma 9.12 implies that the element ℓ is mapped to an element L ∈ Hom(ℕ[C_{1}], ℕ_{-∞}) such that L ∗ L = L. Also, for every f in C, Lf = ℓ(Jf) ≥ 0. Moreover, as J is a coalgebra map, δJ = δ. This implies that Lf = 0 if and only if f = id. Hence, L satisfies all the conditions needed to apply Lemma 9.15.

Notice that the result above does not prove that J : ℕ[C_{1}] → ℕ[I] equals the comonoid map used in Lemma 9.7. Perhaps there is some freedom to choose what intervals J assigns to indecomposable maps in C?

9.17. Unique lifting of factorizations. Fix a rig of coefficients A and let C, D be pre-Möbius categories so that we have incidence algebras AC and AD. Any functor F : C → D induces a function F_{A} : AD → AC via the formula (F_{A}α)_{f} = α_{F f} for every α in AD and f in C. This function is easily seen to preserve 0 and +. In this section we show that F_{A} is an algebra map if and only if F is ULF. The proof will proceed in several steps. First, we will find it convenient to consider the assignment f ↦ \overline{f} that maps every morphism f in C to the element \overline{f} in AC defined by \overline{f}g = 1 if f = g and \overline{f}g = 0 otherwise.

9.18. Lemma. If the composition fg makes sense then \overline{f} ∗ \overline{g} = \overline{fg} in AC.

To state the next step notice that F : C → D also induces a function F : C_{1} → D_{1} and hence, a linear F : ℕ[C_{1}] → ℕ[D_{1}].

9.19. Lemma. For the data above the following are equivalent:

1. F reflects isos,

2. the following diagram

\xymatrix{ℕ[C_{1}] \ar[dr]_{δ} \ar[rr]^{F} &  & ℕ[D_{1}] \ar[dl]^{δ} \\  & ℕ}

commutes,

3. for any rig A, F_{A}δ = δ.

Proof. By Lemma 4.1, the first item is equivalent to the condition: F h = id implies h = id. This condition implies the third item. The third item applied to ℕ implies the second item. Finally, to prove that the second item implies the first, let F h = id. Then 1 = δ(F h) = δh, which means that h = id.

Since F_{A} preserves 0 and +, F reflects isos if and only if F_{A} : AD → AC is A-linear for every rig A.

9.20. Lemma. If F : C → D is ULF then F : ℕ[C_{1}] → ℕ[D_{1}] is a comonoid morphism.

Proof. If F is ULF then it reflects isos by Lemma 4.4 and so the linear F : ℕ[C_{1}] → ℕ[D_{1}] is such that δF = δ : ℕ[C_{1}] → ℕ by Lemma 9.19. To prove that the following diagram

\xymatrix{ℕ[C_{1}] \ar[d]_{Δ} \ar[r]^{F} & ℕ[D_{1}] \ar[d]^{Δ} \\ ℕ[C_{1}] ⊗ ℕ[C_{1}] \ar[r]_{F ⊗F} & ℕ[D_{1}] ⊗ ℕ[D_{1}]}

commutes, consider a map f in C. The top-right composition applied to f produces the linear combination ∑_{(v,w)∈I(F f)} w ⊗ v. On the other hand, the left-bottom composition produces ∑_{(g,h)∈If}(F h) ⊗ (F g). To prove that both results are the same use the iso F_{f} : If → I(F f).

(It should be possible to prove the above result as a corollary of Lemma 7.6 together with a full understanding of the composition

ulfMö → ProCom → CoMon(Ext) → CoMon(Mod_{ℕ})

in the middle row of the diagram at the end of Section 8.1.) We can now prove the main result of the section.

9.21. Theorem. For every functor F : C → D between pre-Möbius categories the following are equivalent:

1. F satisfies the ULF condition,

2. F : ℕ[C_{1}] → ℕ[D_{1}] is a comonoid morphism,

3. for every rig A, F_{A} : AD → AC is an algebra map.

Proof. The first item implies the second by Lemma 9.20. The second item implies the third because comonoid morphisms induce algebra maps between convolution algebras. To prove that the third item implies the first, it suffices to consider A = ℕ. We show that the second condition of Lemma 4.3 holds. So let w be a map in C and assume that fg = F w in D. Consider the characteristic elements \overline{f}, \overline{g}, \overline{F w} ∈ ℕD. (See Lemma 9.18 for the notation.) Then \overline{F w} = \overline{fg} = \overline{f} ∗ \overline{g}. By hypothesis, we obtain that F_{ℕ}\overline{F w} = (F_{ℕ}\overline{f}) ∗ (F_{ℕ}\overline{g}). Applying to w we obtain ((F_{ℕ}\overline{f}) ∗ (F_{ℕ}\overline{g}))_{w} = 1 which means that there exists a unique pair of maps u and v in C such that uv = w, F u = f and F v = g.

(Théorème 4.1 in [2] proves an essentially equivalent result, but without the notion of ULF-functor; so the resulting condition on F is mixed with the arithmetic of a base ring A. The formulation above makes a clearer distinction between the purely combinatorial properties of the functor C → D and the algebraic properties of the induced functions AD → AC.)

Theorem 9.21 implies that, for each ring A, the assignment C ↦ AC induces a functor (ulfMö)^{op} → Alg_{A} where ulfMö is the category of Möbius categories and ULF-functors introduced in Section 4.2 and Alg_{A} is the category of A-algebras.

9.22. Example. The ULF functor ω → ℕ from the total order of natural numbers to the additive monoid of natural numbers (mapping m ≤ n to n − m) induces, for each A, a subalgebra inclusion Aℕ → Aω of the algebra of formal power series into the algebra of upper triangular matrices. (See Examples 9.4 and 9.5.)

9.23. Example. The ULF functor (ℕ^{∗}, |) → ℕ^{∗} which maps m | n to \frac{n}{m} induces subalgebra inclusions Aℕ^{∗} → A(ℕ^{∗}, |) of algebras of Dirichlet series (Example 9.6) into incidence algebras of posets.

It is interesting to compare the two examples above with the approach presented in [4]. Let us fix a base ring such as ℤ. Doubilet, Rota and Stanley introduce incidence algebras ℤC for a locally finite poset C. Then, in Section 4 loc. cit., they consider order compatible equivalence relations on the collection of segments of the poset C. We need not reproduce the definition. The point being that such an equivalence relation ∼, determines a subalgebra ℤ(C, ∼) → ℤC which they call the reduced incidence algebra.

For example, the algebra ℤ[[X]] of formal power series appears as the reduced incidence algebra ℤ(ω, ∼) determined by the relation ∼ defined by (m ≤ n) ∼ (m′ ≤ n′) if and only if n − m = n′ − m′. (See Example 4.5 in [4].) Of course, the subalgebra inclusion ℤ(ω, ∼) → ℤω is nothing but the inclusion determined by the ULF functor considered in Example 9.22 above.

An analogous discussion relates Example 9.23 above with Example 4.8 in [4]. It seems fair to say that the restriction to posets hides the fact that relevant subalgebra inclusions are determined by (ULF) functors. Clearly, restricting the general theory to Möbius monoids would suffer from a similar drawback.

The next example of a ULF inclusion will play a key role in Theorem 9.27.

9.24. Example. Let C be a small category and let |C| denote its set of objects. If C has indecomposable identities then the inclusion |C| → C is ULF. Hence, if C is pre-Möbius then so is |C| and the ULF-inclusion |C| → C induces a ‘restriction’ algebra map r : AC → A|C|.

If S is a set then it is Möbius as a discrete category and its incidence algebra AS is simply the commutative algebra of A-valued functions with pointwise operations.

9.25. Lemma. If C is a pre-Möbius category then the morphism r : AC → A|C| has a section s : A|C| → AC defined by (sψ)_{id} = ψ_{id} and (sψ)_{f} = 0 for each non-identity map f in C.

For example, let C = ℕ_{+} be the Möbius monoid of natural numbers under addition. Then ℝC is the algebra of power series with coefficients in ℝ and the restriction r : ℝC → ℝ assigns, to each power series p, its constant term p0. The morphism s in the opposite direction embeds numbers as constant power series. One of the motivations to introduce Möbius categories was to explain results such as the one saying that a power series is invertible if and only if its constant term is.

9.26. Characterization of Möbius categories in terms of localness. In this section we prove the characterization of Möbius categories in terms of incidence algebras. (The reader should compare this result with Proposition 8.14.)

9.27. Theorem. [Leroux] If C is a pre-Möbius category then the following are equivalent:

1. C is Möbius

2. for every ring A, r : AC → A|C| is local.

This formulation in terms of localness of an algebra map is taken from [10]. Lemmas 8.13 and 9.25, together with the next result provide a proof of one of the implications of Theorem 9.27.

9.28. Lemma. Let C be a Möbius category, A be a ring and α ∈ AC. If rα = δ ∈ A|C| then α is invertible.

Proof. The hypothesis rα = δ means that for every C in C, α_{id_{C}} = 1. To show that α is invertible it is enough to find σ, τ in AC such that σ ∗ α = δ = α ∗ τ. So, in particular, we must have that

1. 1 = δ_{id_{C}} = (α ∗ τ)_{id_{C}} = α_{id_{C}}τ_{id_{C}} = τ_{id_{C}} for each object C in C, and

2. for each non-identity f in C,

0 = δ_{f} = (α ∗ τ)_{f} = ∑_{f′f′′=f} α_{f′}τ_{f′′} = α_{id}τ_{f} + ∑_{f′′≠f^{f′f′′=f}} α_{f′}τ_{f′′} = τ_{f} + ∑_{f′′≠f^{f′f′′=f}} α_{f′}τ_{f′′}

As C is Möbius, f has a finite number of decompositions. Hence, the condition above induces the following recursive definition:

τ_{f} = − ∑_{f′′≠f^{f′f′′=f}} α_{f′}τ_{f′′}

for each non-identity f in C; with base case τ_{id_{C}} = 1 for each object C in C. Similarly, we can derive a left inverse σ and it follows that α is invertible in AC.

The proof of Lemma 9.28 is a simplified (by localness) version of the corresponding part of Théorème 1.1 in [2]. But it is worth mentioning that the result admits a slightly more general formulation, and a proof avoiding recursion, using the same ideas used in Lemma 8.12.

The next result completes the proof of Theorem 9.27.

9.29. Lemma. Let C be a pre-Möbius category. If r : ℤC → ℤ|C| is local then C is Möbius.

Proof. By Proposition 2.6, together with C pre-Möbius, we need only prove that gh = g implies h = id. Assume that h is not an identity. Then r(δ − \overline{h}) = δ ∈ ℤ|C| is invertible, so δ − \overline{h} is invertible in ℤC by hypothesis. The calculation below

(δ + \overline{g}) ∗ (δ − \overline{h}) = δ − \overline{h} + \overline{g} − \overline{g} ∗ \overline{h} = δ − \overline{h} + \overline{g} − \overline{gh} = δ − \overline{h}

implies that (δ + \overline{g}) = δ. This implies that g = id and hence that h = id, which is absurd.

9.30. The algebraic group of a Möbius category. For any rig A, denote by G_{C}A → AC the inverse image of δ ∈ A|C| along r : AC → A|C|. Clearly, G_{C}A contains δ and is closed under convolution, so we consider G_{C}A as a submonoid of AC.

9.31. Example. Let C be the ordinal number 3 and let A be a ring. Then AC is the algebra of 3 × 3 upper triangular matrices and G_{C}A → AC is the subgroup of matrices of the form

( \begin{matrix}1 & a & c \\ 0 & 1 & b \\ 0 & 0 & 1 \end{matrix} )

with a, b, c ∈ A.

For any rig morphism A → B, the induced AC → BC restricts to a monoid morphism G_{C}A → G_{C}B. So the assignment A ↦ G_{C}A extends to a functor from Rig to the category of monoids. Essentially by Theorem 9.27 we obtain the following.

9.32. Corollary. If C is a Möbius category then the assignment A ↦ G_{C}A restricts to a functor G_{C} : Ring → Grp.

Moreover, the natural map Hom(ℕ[I], ) → Hom(ℕ[C_{1}], ) induced by I : ℕ[C_{1}] → ℕ[I] (recall Lemma 9.7) restricts to a natural G → G_{C} as in the diagram below

\xymatrix{G \ar[d] \ar[r] & G_{C} \ar[d] \\ Hom(ℕ[I], ) \ar[r] & Hom(ℕ[C_{1}], )}

where the domain G is the functor Ring → Grp defined in Section 8.11.

Define Lie_{C}A → AC to be the kernel of r : AC → A|C|. It is an additive submonoid and is closed under convolution. But notice that δ is not in Lie_{C}A. The assignment A ↦ Lie_{C}A is functorial in A and, if A is a ring, then Lie_{C}A is naturally an associative (non-unitary, non-commutative) A-algebra and so a Lie algebra (with commutator as bracket).

Define an indexed family {β_{i}}_{i∈I} of elements in AC to be summable if for every f in C, the set {i ∈ I | β_{i}f ≠ 0} is finite. For such a family we define, ∑_{i∈I} β_{i} ∈ AC by the formula below

(∑_{i∈I} β_{i})_{f} = ∑_{{i∈I|(β_{i})_{f} ≠0}}(β_{i})_{f}

for every f in C. The notation has all the expected algebraic properties (see Propositions 2.2, 2.3 and 2.4 in [2]). All of this makes sense for an arbitrary pre-Möbius category C and rig A. But if C is Möbius, then {η^{n}}_{n∈ℕ} is summable and ∑_{n} η^{n} = Φ = Φ_{+} + Φ_{−}. This is a particular case of a more interesting fact we now explain.

9.33. Lemma. Let C be a Möbius category. For every α ∈ Lie_{C}A, the family {α^{n}}_{n∈ℕ} is summable.

Proof. Notice that (α^{n})_{f} is, by definition a sum indexed by sequences (f_{1}, …, f_{n}) such that f_{1}f_{2} … f_{n} = f. As α_{id} = 0, the sum can be considered as indexed by the decompositions of f. But if C is Möbius the set of decompositions of f is finite. So there is a bound for the cardinality of {n ∈ ℕ | (α^{n})_{f} ≠ 0}.

The assignment α ↦ ∑_{n} α^{n} induces a natural transformation Lie_{C} → G_{C}. Notice that if α is in Lie_{C}A then the sequence {α^{n+1}}_{n∈ℕ} is summable and it is easy to check that ∑_{n} α^{n} = δ + ∑_{n} α^{n+1} = δ + α ∗ ∑_{n} α^{n}. It is then natural to denote the above transformation by

(δ − ( ))^{−1} : Lie_{C}A → G_{C}A

The simple calculation above also implies that when A is a ring one has ∑_{n} α^{n} = (δ − α)^{−1} on the nose.

To end this section we note that, exactly as in the ring case (stated in Proposition 2.5 in [2]), Lemma 9.33 can be restricted to a characterization.

9.34. Lemma. Let C be a Möbius category. If A is a rig with no non-trivial nilpotent elements then α ∈ Lie_{C}A if and only if {α^{n}}_{n∈ℕ} is summable.

Proof. One direction is implied by Lemma 9.33. So assume that {α^{n}}_{n∈ℕ} is summable. Let C be an object of C and let α_{id_{C}} = a. For every n, (α^{n})_{id_{C}} = a^{n}. As {α^{n}}_{n∈ℕ} is summable, there is a k such that a^{k} = 0. Since A has no nilpotents, a = 0. Hence α ∈ Lie_{C}A.

10. Two alternative proofs

Corollary 9.9, stating that ζ^{−1} = Φ_{+} − Φ_{−} in incidence algebras (with coefficients in a ring) is one of the main motivating results for much of the work reported here. It seems a good idea to compare the proof we presented with some alternatives. Our proof is essentially a corollary of Proposition 5.9. The isomorphisms defined in that result are transformed into equalities in ℕ[I]^{∗} via ‘Burnside counting’ (Corollary 8.9). These equalities are transformed into a Master Inversion result in Hom(ℕ[I], ℤ) via the algebra map induced by ℕ → ℤ (Corollary 8.10) and finally transferred to incidence algebras essentially by the comonoid morphism I : ℕ[C_{1}] → ℕ[I] of Lemma 9.7. The reader is invited to compare the following proofs with that of Corollary 9.9; and also to relate them to the isomorphism described after Proposition 5.9.

10.1. The proof by Content, Lemay and Leroux. The proof in [2] is based on the results about summable families in incidence algebras with coefficients in a ring. Specifically, the authors rely on the fact that if α ∈ Lie_{C}A then δ − α is invertible and (δ − α)^{−1} = ∑ α^{n}. In particular, take α = −η. As ζ = δ + η, the calculation

μ = ζ^{−1} = (δ + η)^{−1} = ∑_{i∈ℕ}(−1)^{i}η^{i} = (∑_{i∈ℕ}η^{2i}) − (∑_{i∈ℕ}η^{2i+1}) = Φ_{+} − Φ_{−}

proves (again) Corollary 9.9.

10.2. A Hopf algebraic proof. Let H be the Hopf algebra described in Section 8.15. The bialgebra map ℕ[I] → H induces an algebra morphism Hom(H, ℤ) → Hom(ℕ[I], ℤ). So, an argument analogous to that in Corollary 9.9, allows to transfer equalities in Hom(H, ℤ) to incidence algebras with coefficients in a ring. For this reason we concentrate on a ‘master result’ in Hom(H, ℤ) analogous to Corollary 8.10.

Denote the dual algebra Hom(H, ℤ) by H^{∗}. Since ℤ is commutative, we can rely on the general theory of Hopf algebras to conclude that the set of algebra maps Alg(H, ℤ) → H^{∗} is actually a convolution subgroup and that for each α ∈ Alg(H, ℤ), its inverse α^{−1} is the composition αS : H → ℤ, where S is the antipode of H. In particular, ζ ∈ Alg(H, ℤ) and so

μ[C] = ζ(S[C]) = ζ ∑_{n≥0} ∑_{(f_{1},...,f_{n})}(−1)^{n}([If_{1}]×…×[If_{n}]) = ∑_{n≥0} ∑_{(f_{1},...,f_{n})}(−1)^{n} = (Φ_{+} −Φ_{−})[C]

where the second sum ranges over the decompositions (of length n) of the unique 0 → 1 in C.

But this is a bit like cheating because the construction of the Hopf algebra H is based on Lemma 8.12, which depends essentially on the isos δ + ζ ∗ Φ_{−} ≅ ζ ∗ Φ_{+} described in Proposition 5.9.

A purely Hopf-algebraic proof should construct H in ring-theoretic terms. This may be done as follows. Given the bialgebra H as defined just before Proposition 8.17, we need to define an antipode. That is, a map S : H → H such that S ∗ id = δ = id ∗ S. Assume we have an S such that δ = S ∗ id. Then, for every [C] in I we can calculate

δ[C] = ∇ ((S ⊗ id) ∑_{x∈C}[x/C] ⊗ [C/x]) = ∑_{x∈C} ∇(S[x/C] ⊗ [C/x]) =

= ∇(S[C] ⊗ 1) + ∑_{0≠x∈C} ∇(S[x/C] ⊗ [C/x]) = S[C] + ∑_{0≠x∈C} ∇(S[x/C] ⊗ [C/x])

so, for [C] = 1 we have 1 = S1. On the other hand, for [C] ≠ 1, the above implies that

S[C] = − ∑_{0≠x∈C} ∇(S[x/C] ⊗ [C/x])

which can be seen as a recursive definition of S because C is finite. Similarly, we can derive a recursive definition for the right inverse (i.e. a linear S′ : H → H such that δ = id ∗ S′) using the terminal object of C instead of the initial one as above.

To give a non-recursive definition for S one should devise a closed formula and check that it satisfies the recursive equations derived above. This is the strategy used in [16] to prove a similar result. Define S ∈ Hom(H, H) as the extension of the function S : I → H given by

S[C] = ∑_{n≥0} ∑_{(f_{1},...,f_{n})}(−1)^{n}[(If_{1}) × … × (If_{n})]

where (f_{1}, … f_{n}) ranges over the decompositions of length n of the unique map 0 → 1 in C.

Clearly S1 = 1. Now, for [C] ≠ 1, we have that

S[C] = ∑_{0≠x∈C} ∑_{m≥0} ∑_{(g_{1},...,g_{m},!)}(−1)^{m+1}[(Ig_{1}) × … × (Ig_{n}) × I!]

where ! : 0 → x and (g_{1}, …, g_{m}) is a decomposition of length m of the unique map x → 1 in C. But I! = C/x, so

S[C] = (−1) ∑_{0≠x∈C} ∑_{m≥0} ∑_{(g_{1},...,g_{m})}(−1)^{m}∇([(Ig_{1}) × … × (Ig_{n})] ⊗ [C/x]) =

= − ∑_{0≠x∈C} ∇ ((∑_{m≥0} ∑_{(g_{1},...,g_{m})}(−1)^{m}[(Ig_{1}) × … × (Ig_{n})]) ⊗ [C/x]) =

− ∑_{0≠x∈C} ∇(S[x/C] ⊗ [C/x])

which shows that the explicit definition of S : H → H satisfies the recursive equations derived above.

(Concerning the relation with [16], Schmitt associates a Hopf algebra to each family of locally finite posets satisfying a number of conditions. He comments in page 266 that his closed formula for the antipode, in terms of an alternating sum over chains in a segment, ‘bears a striking resemblance to Phillip Hall’s formula for the Möbius function of a poset’. The formula for S given above is almost the same as that given in the statement of Theorem 6.1 in [16] except for the fact that we use elements of I instead of equivalence relations of segments coming from a family of locally finite posets.)

11. Summary of notation

In this section we summarize the notation introduced in the paper.

Categories of Möbius categories. In Section 4 we introduce the following subcate-

gories of Cat:

\xymatrix{MöI \ar[r] & Mö \ar[r] & Cat \\ sMöI \ar[u] & _{ulfMö} \ar[u]}

whose objects are Möbius categories. Mö → Cat is the full subcategory of Möbius categories. ulfMö → Mö is the non-full (bijective on objects) subcategory determined by ULF functors (Section 4.2). MöI → Mö is the full subcategory determined by Möbius intervals (Section 4.5). sMöI → MöI is the non-full (bijective on objects) subcategory determined by strict functors (Section 4.5 also).

Intervals. We denote by If the interval determined by a morphism f (Definition 3.1). The symbol I is also used in Section 7 to denote the functor I : C_{1} → sMöI, where C_{1} is the discrete category of morphisms of a Möbius category C. In turn, this functor induces a coalgebra map ℕ[C_{1}] → ℕ[I] in Lemma 9.7.

Incidence categories. These extensive monoidal categories are discussed in Section 6. See also Lemma 9.10.

Extensive procomonoids. The category ProCom is introduced in Section 7.

Burnside algebras. If C is a monoidal category, we denote the induced monoid of isoclasses of objects by 𝔅C. The same notation is used for extensive monoidal categories and the resulting structures are called Burnside algebras. The letter 𝔎 is used to simplify the notation in a context where 𝔅 is applied to the fibers of an indexed category. All this is introduced in Section 8.1.

In Definition 8.6 we introduce the symbol I for the monoid 𝔅(sMöI). Lemma 8.2 implies that the algebra 𝔅(Fam(sMöI)) coincides with the monoid-rig ℕ[I].

All the structure of ℕ[I] extends to the monoid-ring ℤ[I] that we also denote by H. The bialgebra H is shown to be a Hopf algebra in Proposition 8.17.

Incidence algebras. Let C be a pre-Möbius category (Definition 6.4). We denote by ℕ[C_{1}] the free ℕ-module (commutative monoid) on the set C_{1} of morphisms of C. The module ℕ[C_{1}] is shown to have a canonical coalgebra structure in Lemma 9.2. For a rig A, the convolution algebra Hom(ℕ[C_{1}], A) is called the incidence algebra of C (with coefficients in A) and it is denoted by AC (Definition 9.3).

One general algebraic group. The functor G : Ring → Grp is introduced in Section 8.11.

Many particular algebraic groups. In Section 9.30 we introduce, for each Möbius category C, the functor G_{C} : Ring → Grp. Its relation with the ‘general’ algebraic group G is discussed also in that section.

Éléments remarquables. The symbols δ, ζ, μ, Φ_{+}, Φ_{−} and η are used for different but related objects. The origin of the notation comes from [2] where they are used to state and prove the General Möbius Inversion Principle for incidence algebras. We use them in the same way in Section 9. But we use the same symbols for related objects in Cat(sMöI, Set_{f}) defined in Section 5.1 and in Cat(C_{1}, Set_{f}) as discussed in Section 6.

Acknowledgments

Thanks to Don Taylor, Ross Street and Steve Lack for helping to rescue [10]. Also to the referee who offered several suggestions to improve the paper.

References

[1] A. Carboni, S. Lack, and R. F. C. Walters. Introduction to extensive and distributive categories. Journal of Pure and Applied Algebra, 84:145–158, 1993.

[2] M. Content, F. Lemay, and P. Leroux. Categories de Möbius et fonctorialites: un cadre général pour l’inversion de Möbius. J. Comb. Theory, Ser. A, 28:169–190, 1980.

[3] B. Day. On closed categories of functors. Rep. Midwest Category Semin. 4, Lect. Notes Math. 137, 1-38 (1970)., 1970.

[4] P. Doubilet, G.-C. Rota, and R. Stanley. On the foundations of combinatorial theory (vi): The idea of generating function. Proc. 6th Berkeley Sympos. math. Statist. Probab., Univ. Calif. 1970, 2, 267-318, 1972.

[5] R. Gates. On extensive and distributive categories. PhD thesis, School of mathematics and statistics, University of Sydney, Sydney, New South Wales, Australia, 1997.

[6] S. A. Joni and G.-C. Rota. Coalgebras and bialgebras in combinatorics. Studies in Applied Mathemaics, 61(2):93–139, 1979.

[7] A. Joyal. Une théorie combinatoire des séries formelles. Advances in mathematics, 42:1–82, 1981.

[8] F. W. Lawvere. Categories of spaces may not be generalized spaces as exemplified by directed graphs. Revista colombiana de matemáticas, 20:179–186, 1986. Also in Reprints in Theory and Applications of Categories, No. 9 (2005) pp. 1-7.

[9] F. W. Lawvere. State categories and response functors. Dedicated to Walter Noll, May 1986.

[10] F. W. Lawvere. Möbius algebra of a category. Handwritten Notes by S. Schanuel at the Sydney Combinatorics Seminar organized by Don Taylor, May 1988.

[11] F. W. Lawvere. Some thoughts on the future of category theory. In Proceedings of Category Theory 1990, Como, Italy, volume 1488 of Lecture notes in mathematics, pages 1–13. Springer-Verlag, 1991.

[12] P. Leroux. Les categories de Möbius. Cahiers de Topologie et Géométrie Différentielle Catégoriques, 16(3):280–282, 1975. Deuxième colloque sur l’algèbre des catégories. Amiens-1975. Résumés des conférences.

[13] P. Leroux. The isomorphism problem for incidence algebras of Moebius categories. Ill. J. Math., 26:52–61, 1982.

[14] M. Menni. Algebraic categories whose projectives are explicitly free. Theory Appl. Categ., 22:509–541, 2009.

[15] S. H. Schanuel. Negative sets have Euler characteristic and dimension. Category theory, Proc. Int. Conf., Como/Italy 1990, Lect. Notes Math. 1488, 379-385 (1991).

[16] W. R. Schmitt. Antipodes and Incidence Coalgebras. Journal of Combinatorial Theory (Series A), 46:264–290, 1987.

[17] R. G. Swan. Algebraic K-theory. Lecture Notes in Mathematics 76, 1968.

SUNY at Buffalo 244 Mathematics Building Buffalo, N. Y. 14260

Lifia C. C. 11 (1900) La Plata Argentina

Email: wlawvere@buffalo.edu
      matias.menni@gmail.com

This article may be accessed at http://www.tac.mta.ca/tac/ or by anonymous ftp at

ftp://ftp.tac.mta.ca/pub/tac/html/volumes/24/10/24-10.{dvi,ps,pdf}

THEORY AND APPLICATIONS OF CATEGORIES (ISSN 1201-561X) will disseminate articles that significantly advance the study of categorical algebra or methods, or that make significant new contributions to mathematical science using categorical methods. The scope of the journal includes: all areas of pure category theory, including higher dimensional categories; applications of category theory to algebra, geometry and topology and other areas of mathematics; applications of category theory to computer science, physics and other mathematical sciences; contributions to scientific knowledge that make use of categorical methods. Articles appearing in the journal have been carefully and critically refereed under the responsibility of members of the Editorial Board. Only papers judged to be both significant and excellent are accepted for publication. Full text of the journal is freely available in .dvi, Postscript and PDF from the journal’s server at http://www.tac.mta.ca/tac/ and by ftp. It is archived electronically and in printed paper format.

Subscription information. Individual subscribers receive abstracts of articles by e-mail as they are published. To subscribe, send e-mail to tac@mta.ca including a full name and postal address. For institutional subscription, send enquiries to the Managing Editor, Robert Rosebrugh, rrosebrugh@mta.ca.

Information for authors. The typesetting language of the journal is TEX, and L^{A}TEX2e strongly encouraged. Articles should be submitted by e-mail directly to a Transmitting Editor. Please obtain detailed information on submission format and style files at http://www.tac.mta.ca/tac/.

Managing editor. Robert Rosebrugh, Mount Allison University: rrosebrugh@mta.ca

TEXnical editor. Michael Barr, McGill University: barr@math.mcgill.ca

Assistant TEX editor. Gavin Seal, Ecole Polytechnique Fédérale de Lausanne:

gavin seal@fastmail.fm

Transmitting editors.

Clemens Berger, Université de Nice-Sophia Antipolis, cberger@math.unice.fr Richard Blute, Université d’ Ottawa: rblute@uottawa.ca Lawrence Breen, Université de Paris 13: breen@math.univ-paris13.fr Ronald Brown, University of North Wales: ronnie.profbrown (at) btinternet.com Aurelio Carboni, Università dell Insubria: aurelio.carboni@uninsubria.it Valeria de Paiva, Cuill Inc.: valeria@cuill.com Ezra Getzler, Northwestern University: getzler(at)northwestern(dot)edu Martin Hyland, University of Cambridge: M.Hyland@dpmms.cam.ac.uk P. T. Johnstone, University of Cambridge: ptj@dpmms.cam.ac.uk Anders Kock, University of Aarhus: kock@imf.au.dk Stephen Lack, University of Western Sydney: s.lack@uws.edu.au F. William Lawvere, State University of New York at Buffalo: wlawvere@acsu.buffalo.edu Tom Leinster, University of Glasgow, T.Leinster@maths.gla.ac.uk Jean-Louis Loday, Université de Strasbourg: loday@math.u-strasbg.fr Ieke Moerdijk, University of Utrecht: moerdijk@math.uu.nl Susan Niefield, Union College: niefiels@union.edu Robert Paré, Dalhousie University: pare@mathstat.dal.ca Jiri Rosicky, Masaryk University: rosicky@math.muni.cz Brooke Shipley, University of Illinois at Chicago: bshipley@math.uic.edu James Stasheff, University of North Carolina: jds@math.unc.edu Ross Street, Macquarie University: street@math.mq.edu.au Walter Tholen, York University: tholen@mathstat.yorku.ca Myles Tierney, Rutgers University: tierney@math.rutgers.edu Robert F. C. Walters, University of Insubria: robert.walters@uninsubria.it R. J. Wood, Dalhousie University: rjwood@mathstat.dal.ca