Beiträge zur Algebra und Geometrie Contributions to Algebra and Geometry Volume 34 (1993), No. 2, 201-208.

Generators and Relations for Δ as a Monoidal 2-Category

Anders Kock

Matematisk Institut, Aarhus Universitet Ny Munkegade. Bygning 530, DK - 8000 Aarhus C

Introduction

By Δ, we understand the category of finite ordinals \underline{0}, \underline{1}, \underline{2},…, and their order preserving maps. It is the category which defines the notion of simplicial set. As a category, it is well known to be generated by face- and degeneracy operators d_{i} : \underline{n} → \underline{n + 1}, s_{j} : \underline{n + 2} → \underline{n + 1} (for each n), and a certain list of equations (for each n) for its relations, cf e.g. [6]. This category carries structure of monoidal (=tensored) category with \underline{n} ⊗ \underline{m} = \underline{n + m} (ordinal sum formation). As a monoidal category, it has a much smaller presentation, namely generated by d_{0} : \underline{0} → \underline{1}, s_{0} : \underline{2} → \underline{1}, and three equations, namely the three equations which define the notion of monoid (unit- and associative law); this was proved by Lawvere [4].

However, as observed by Street [8], being a category of order preserving maps between ordered sets, the category is enriched over partially ordered sets, in the sense that its homsets carry a partial order (compatible with the composition, and also with the ⊗). In fact it is a 2-category, cf e.g. [1], [2] for these notions; in fact, it is a strict monoidal 2-category. We give generators and relations for its 2-dimensional structure. The result (Theorem 2.1 below) is:

• one generator λ, namely the inequality (”2-cell”) d_{1} ≤ d_{0} (as maps \underline{1} → \underline{2})

• two relations: both d_{0} ∗ λ : \underline{0} → \underline{2} and λ ∗ s_{0} : \underline{1} → \underline{1} are identity 2-cells. The conventions are that we compose from left to right, for the horizontal composition ∗ (and also for the vertical composition · occurring later on); and that d_{i} : \underline{n} → \underline{n + 1} omits i ∈ \underline{n + 1}, where \underline{n + 1} = \{0, 1,…, n\}. Note that the 2-cell d_{0} ∗ λ has the same map \underline{0} → \underline{2} for its vertical source and target, but we are presenting Δ as a category enriched over categories (a 2-category), rather than enriched over partially ordered sets; thus we do not apriori assume that a 2-cell with its source and target coinciding is an identity 2-cell.

I want to acknowledge correspondence with Ross Street; in fact a result about a universal property of Δ as a monoidal 2-category appears in his [8]. It is not exactly the same universal property as the one given here (cf. remark at the end of the paper); the one given here was proposed by Ross Street when he was refereeing [3]. Since the proof I was able to give for it turned out to be a little involved, I decided to publish it separately.

0138-4821/93 $ 2.50 \begin{matrix}c \\ ◯ \end{matrix}1993 Heldermann Verlag, Berlin

1. The comparison functors

Let Δ′ denote a (strictly) monoidal 2-category with a given object T, given 1-cells y : I → T and m : T ⊗T → T (I denoting the (strict) unit object), and a given 2-cell λ : y⊗T → T ⊗y,

such that y and m make T into a monoid object, and such that λ satisfies the axioms

(1)  y ∗ λ = y ⊗ y
(2)  λ ∗ m = T;

and which is universal with these data. (We have here used the convention that the identity 1-cell of a 0-cell (object) A is also denoted A; and that the identity 1-cell of a 1-cell (arrow) f is also denoted f.) The monoidal 2-category Δ carries such T, y, m, λ, satisfying the axioms, namely T = \underline{1}, y and m the unique maps \underline{0} → \underline{1} and \underline{2} → \underline{1}, respectively, and with λ the inequality d_{1} ≤ d_{0} (as maps \underline{1} → \underline{2}). By the universal property of Δ′, there is a monoidal 2-functor P : Δ′ → Δ taking T to \underline{1}, y and m to \underline{0} → \underline{1} and \underline{2} → \underline{1}, respectively, and λ to d_{1} ≤ d_{0}.

Since it is clear that the 2-dimensional structure on Δ′ does not impose any constraints on the 1-dimensional structure, it follows that the underlying monoidal 1-category of Δ′ is the free monoidal category with a monoid object T, y, m; and therefore, by [4], it is (isomorphic to) Δ, so on the underlying monoidal 1-categories, P : Δ′ → Δ is an isomorphism. Our theorem is that P is also an isomorphism of the 2-dimensional structure, Theorem 2.1 below.

Since P is an isomorphism on the 1-dimensional structure, we may identify Δ′ and Δ in so far as this structure goes. This gives us two sets of notations for 0- and 1-cells of these categories. For instance, the map (face operator) d_{1} : \underline{2} → \underline{3} which omits 1 ∈ \{0, 1, 2\} = \underline{3} may also be denoted T ⊗ y ⊗ T, or just T yT. As in [3], we let ⊗ bind more strongly than the horizontal composition ∗ or the vertical composition ·, and sometimes we omit ⊗ (but we never omit ∗ or ·). Also T ⊗ T = T T may be denoted T^{2}, and similarly for T^{3}, etc. To fit with the conventions of [3], we need to have yT : T → T^{2} match d_{1} : \underline{1} → \underline{2} (which omits the last element 1 ∈ \underline{2}), so it is most natural in the graphics to think of the elements 0 and 1 of \underline{2} as displayed graphically in the order: 1,0 , with the largest element leftmost; similarly for the higher \underline{n}’s.

The strategy is now as follows: we shall provide an inverse J : Δ → Δ′ for P. On 0and 1-cells, J will be the identity, of course. On 2-cells, it will be constructed as a splitting of P, P (J(α)) = α, and commuting with ⊗ and ·. The construction of this splitting will occupy the rest of the present section, whereas Section 2 will prove that J is an onto map, implying hat J is a two-sided inverse for P which is thus an isomorphism.

Let f and g be maps \underline{n} → \underline{m} in Δ. If f ≤ g (i.e. f(i) ≤ g(i) ∀ i ∈ \underline{n}), we say that dist(f, g) = p if ∑_{i∈\underline{n}} g(i) − f(i) = p. If f ≤ g and dist(f, g) = 1, we say that the pair (f, g) is an elementary move out of f with result g. The unique element i ∈ \underline{n} with f(i) ≠ g(i) (in fact with f(i) + 1 = g(i)) is called the element moved by the elementary move. Clearly, an elementary move out of f moving i is possible (and then unique) iff i is the largest element in the set (interval) f^{−1}(f(i)), and f(i) is not the largest element in \underline{m}.

It is clear that if dist(f, g) = p, then we can interpolate a chain consisting of p elementary moves between f and g. Such chain is not unique, but at least we have the following ”confluence lemma”:

Proposition 1.1 Let f : \underline{n} → \underline{m}. If g and h are results of two distinct elementary moves out of f, there is a k : \underline{n} → \underline{m} which is the result of an elementary move out of g and also the result of an elementary move out of h. (Such k is unique.)

Proof. Let i and j be the elements moved by the elementary moves (f, g) and (f, h), respectively. We have i ≠ j since g and h are distinct. We may assume i > j. Because of the elementary move (f, g), i is the largest element in f^{−1}(f(i)) = f^{−1}(h(i)). This set differs from h^{−1}(h(i)) at most by the presence or not of j, which is the only element where f and h differ. Since i > j, the status of i as largest in f^{−1}(f(i)) is not affected by the presence or not of j, so i is the largest element also in h^{−1}(h(i)). So an elementary move out of h moving i is possible, with result the map k given by

(3)  k(i) = f(i) + 1; k(j) = f(j) + 1; k(x) = f(x) for all other x.

Also g(i) = f(i) + 1 > f(i) ≥ f(j), so g(i) ≠ f(j) = g(j). Also f(i) ≠ f(j), for f(i) = f(j) and i > j would contradict j being largest in f^{−1}(f(j)) (as witnessed by the elementary move (f, h)). Since f and g differ only at i, f^{−1}(f(j)) = g^{−1}(g(j)) (i belongs to neither); since j is the largest in f^{−1}(f(j)), it is largest in g^{−1}(g(j)). So an elementary move out of g moving j is possible, and it is clear that the result of the move is again k.

It is clear that any elementary move (f, g) in Δ can be written uniquely

(4)  (f′ ⊗ f_{0} ⊗ f′′, f′ ⊗ g_{0} ⊗ f′′)

with (f_{0}, g_{0}) an elementary move of maps \underline{n}_{0} → \underline{2}, for suitable \underline{n}_{0}, f′, f′′: if i is the element moved by the elementary move (f, g), f′′ is the restriction of f to the set of j’s with f(i) > f(j), and f′ (essentially) the restriction to the set of j’s with f(j) > f(i) + 1. And it is clear that there is exactly one elementary move L_{n,i} between maps \underline{n} → \underline{2} which moves i, namely

L_{n,i} = (f_{0}, g_{0})

with

f_{0}(j) = 0 for j ≤ i, 1 otherwise,
g_{0}(j) = 0 for j < i, 1 otherwise.

We associate to this elementary move L_{n,i} the 2-cell in Δ′

(5)  λ_{n,i} := (T^{n−1−i} ⊗ λ ⊗ T^{i}) ∗ (m′ ⊗ m′′)

where m′ : \underline{n − i} → \underline{1} and m′′ : \underline{i + 1} → \underline{1} are the unique such maps. And to the elementary move (4), we associate f′ ⊗ λ_{n,i} ⊗ f′′. This defines our map J : Δ → Δ′ on all elementary moves f ≤ g in Δ. It is clear that J, so far as it is defined by now, respects the domain/codomain book-keeping, and (hence) splits P. In this and similar considerations, the reader may find the following kind of diagram (illustrating, in this case, λ_{n,i}) useful (vertical concatenation corresponds to ∗, horizontal concatenation to ⊗). Note that λ itself is λ_{1,0}.

To extend J to yield a 2-cell J(f, g) : f ⇒ g in Δ′ for any inequality f ≤ g in Δ, we decompose f ≤ g into a chain of elementary moves f = h_{0} ≤ h_{1} ≤ … ≤ h_{p} = g, and we would then like to put J(f, g) equal the · -composite of the J(h_{q}, h_{q+1})’s. Since the chain decomposition is not unique, there is a question about well-definedness. Because of the confluence Lemma (Proposition 1.1), it easily follows that it suffices to see that

(6)  J(f ≤ g) · J(g ≤ k) = J(f ≤ h) · J(h ≤ k)

where f, g, h, and k are as in the Proposition. Also, let i and j be as in its proof.

It is clear that if ϕ is a 2-cell in Δ which is an elementary move, then so is ϕ ⊗ f and f ⊗ ϕ for any 1-cell f in Δ; and it is clear from the description of J on elementary moves that

J(ϕ ⊗ f) = J(ϕ) ⊗ f, J(f ⊗ ϕ) = f ⊗ J(ϕ).

Using such reductions, the problem of proving (6) gets reduced to the case where f : \underline{n + 1} → \underline{3}, and the elements i and j moved are the last and first elements n and 0. Thus

\begin{aligned}(f, g) & = L_{n,n−1} ⊗ T ↦ (λ ⊗ T^{n−1} ∗ T ⊗ m^{(n)}) ⊗ T \\ (g, k) & = T ⊗ L_{n,0} ↦ T ⊗ (T^{n−1} ⊗ λ ∗ m^{(n)} ⊗ T) \\ (f, h) & = y ⊗ L_{n+1,0} ↦ y ⊗ (T^{n} ⊗ λ ∗ m^{(n+1)} ⊗ T) \\ (h, k) & = L_{n+1,n} ⊗ y ↦ (λ ⊗ T^{n} ∗ T ⊗ m^{(n+1)}) ⊗ y, \end{aligned}

where m^{(q)} : \underline{q} → \underline{1} is the unique such map (thus m^{(2)} = m, m^{(1)} = T, m^{(0)} = y).

We now calculate λT^{n} ∗T^{n+1}λ∗T m^{(n+1)}T by the 2-category rules for the ∗-composite of two 2-cells. On the one hand, we get, using bifunctorality of ⊗,

(λT^{n−1}T ∗ T m^{(n)}T) · (T^{n}λ ∗ T m^{(n)}T) = J(f, g) ∗ J(g, k);

calculating this the other way round, we get

\begin{matrix}(yT^{n+1} ∗ T^{n+1}λ ∗ T m^{(n+1)}T) · (λT^{n} ∗ T^{n+2}y ∗ T m^{(n+1)}T) = \\ (yT^{n+1} ∗ T^{n+1}λ ∗ T m^{(n+1)}T) · (T^{n+1}y ∗ λT^{n+1} ∗ T m^{(n+1)}T). \end{matrix}

But the two factors here are, by bifunctorality of ⊗ seen to be, respectively, y ⊗ (T^{n}λ ∗ m^{(n+1)}T) and (λT^{n} ∗ T m^{(n+1)}) ⊗ y, i.e. J(f, h) and J(h, k), respectively. This proves the commutativity (6) for the special case considered, but as argued, this case suffices.

This now means that we have a map J : Δ → Δ′ which is the identity on 0- and 1-cells, and preserves the book-keeping and the compositions · and ⊗ on 2-cells; and J followed by P is the identity. So to see that J is a two-sided inverse for P, it suffices to see that every 2-cell in Δ′ is in the image of J. We turn to this task:

2. 2-cells in the image of J

To see that J is surjective on 2-cells, we use ’structural induction’: any 2-cell in Δ′ is given by an expression built by means of ⊗, ∗, and · , starting with λ (and identity 2-cells). If we assume that every 2-cell which can be built by an expression of length < n is in the image of J, and ϕ is an expression of length n, there are four cases to consider:

1) n = 1, in which case ϕ = λ or is an identity 2-cell. In both cases, ϕ is in the image of J.

2) ϕ = ϕ′ ⊗ϕ′′, with ϕ′ and ϕ′′ expressions of length < n. Then the 2-cells given by these expressions are in the image of J, and since J commutes with ⊗, the 2-cell given by the expression ϕ is in the image of J.

3) ϕ = ϕ′ · ϕ′′ - the argument is similar.

4) We finally consider the case ϕ = ϕ′ ∗ ϕ′′. Using the rules of 2-categories, this may be written as a · -composite of expressions of form f ∗ ϕ′′ and ϕ′ ∗ g with f and g 1-cells, and each of these expressions is strictly shorter than ϕ = ϕ′ ∗ ϕ′′ unless one of the ϕ’s is of length 1, that is, unless ϕ′ = λ or ϕ′′ = λ. So this leaves us with proving

Proposition 2.1 1) For any 1-cell f, f ∗ λ is in the image of J. 2) For any 1-cell g, λ ∗ g is in the image of J.

Proof. 1) f is of form m^{(k)} : \underline{k} → \underline{1} for some k; the cases k = 0 and k = 1 yield y ∗λ = y ⊗y (by (1)) and λ, respectively, and both of these are in the image of J. For k = n > 1, we shall prove the equation

m^{(n)} ∗ λ = (7)

(λT^{n−1} ∗ m^{(1)} ⊗ m^{(n)}) · (T λT^{n−2} ∗ m^{(2)} ⊗ m^{(n−1)}) ·. . . · (T^{n−1}λ ∗ m^{(n)} ⊗ m^{(1)}).

Each of the factors on the right hand side are values of J on elementary moves, cf. formula (5). To prove (7), we observe that the two terms to be compared have domain-1-cell of form

f ∗ yT

(in fact f = m^{(n)}). We prove

Lemma 1 Assume that there are given 2-cells α, β : f ∗yT ⇒ g : T^{n} → T^{2}. If α∗m = β∗m, then α = β.

Proof. It suffices to prove that α can be reconstructed from α ∗ m. Let us calculate α ∗ λT ∗ T m in two ways by the 2-category rules for the ∗-composite of two 2-cells. Since the domain 1-cell of λT ∗ T m is yT^{2} ∗ T m = m ∗ yT, one way of rewriting α ∗ λT ∗ T m gives

(8)  (α ∗ m ∗ yT) · (g ∗ λT ∗ T m);

since the codomain 1-cell of λT ∗ T m is T yT ∗ T m = id, the other way of rewriting gives

(9)  (f ∗ yT ∗ λT ∗ T m).α,

which is α, by (1). Since (8)=(9), α can be reconstructed from α ∗ m, using the expression (8).

Using the lemma, we may prove (7) by proving that we get the same 2-cell by ∗- composing either side of (7) on the right by m. We have m^{(n)} ∗ λ ∗ m the identity 2-cell of m^{(n)}, by (2). But applying − ∗ m to each of the factors on the right of (7) yields an identity 2-cell, since (m^{(j)} ⊗ m^{(n−j+1)}) ∗ m = m^{(n+1)}, which when applied on the right of T^{j−1}λT^{n−j} yields an identity 2-cell, essentially by (2).

Proof of 2). We may assume that g : \underline{2} → \underline{n} is monic, for, if g identifies the two elements in the domain, it is of form m∗g′, and hence λ∗g = λ∗m∗g′ which is an identity 2-cell by (2). Also, by bifunctorality of ⊗, it is easy to see that we only need to consider the case where g preserves first and last element, so is of form g = T y^{k}T = T ⊗ y ⊗… ⊗ y ⊗ T (k y’s). We may rewrite this as

(10)  g = T yT ∗ T yT^{2} ∗… ∗ T yT^{k}.

Consider the horizontal composite

Since each 1-cell in the top row composes with its 2-cell neighbour to the right to give an identity 2-cell (by (1)), the one way of rewriting this as a vertical composite of 2-cells yields only one 2-cell factor, namely

λ ∗ T yT ∗ T yT^{2} ∗… ∗ T yT^{k},

i.e. λ ∗ g. The other way of rewriting it yields a ·-composite of k + 1 factors; for instance, the one involving the 2-cell λT^{p} (p = 0, 1,…, k) from the above horizontal composite is

(11)  T y ∗ T yT ∗… ∗ T yT^{p−1} ∗ λT^{p} ∗ yT^{p+2} ∗… yT^{k+1}.

Using the rules of monoidal 2-categories, this is analyzed as

(12)  y^{k−p} ⊗ λ ⊗ y^{p},

which is in the image of J since λ is. This proves part 2) of the Proposition.

From this follows that J is a two-sided inverse for P (on the level of 2-cells; on the level of 0- and 1-cells, J and P are already known to be mutually inverse). Thus P is an isomorphism.

From this follows that the monoidal category Δ has the same universal property as Δ′; thus

Theorem 2.1 The (strict) monoidal 2-category Δ is freely generated by the 0-cell \underline{1} (=T), the 1-cells y : \underline{0} → \underline{1} (or y : I → T), m : \underline{2} → \underline{1} (or m : T ⊗ T → T), and the 2-cell

λ : y ⊗ T ⇒ T ⊗ y : T → T ⊗ T,

modulo the relations: y and m make T into a monoid; and λ satisfies (1) and (2), i.e. y ∗ λ = y ⊗ y and λ ∗ m = T.

Remark The cocompletion constructions of [3], T, y, m, on the 2-category Cat of categories, or on the 2-category Pos of partially ordered sets, say, are, (modulo coherent isomorphism, in the former case) monads, thus monoids in the monoidal 2-category C of endo-2-functors on Cat (resp. Pos), where the (strictly associative) ⊗ on C is composition of functors. But, as pointed out in [3], a special feature of cocompletion constructions is the presence of a natural transformation λ : yT ⇒ T y (in standard right-to-left notation:

λ_{C} : T (y_{C}) ⇒ y_{T C}

for each category (respectively poset) C), satisfying (1) and (2), at least in the Pos-case; in the Cat-case, the coherent isomorphisms must be taken into account. Thus by the universal property of Theorem 2.1, there is a monoidal 2-functor Δ → C with 1 ↦ T, extending the monoidal 1-functor Δ → C arising from the 1-dimensional aspect of the monad T, y, m, (according to [4]). In [8], a similar extension is also carried out, but only for the sub-2-category of Δ, consisting of the non-empty ordinals, and the last-element preserving maps.

The endofunctor − ⊗ T on Δ is itself (the restriction to Δ ⊆ Pos of) a cocompletion monad, namely ”freely adding a smallest element ⊥”.

References

[1] G.M. Kelly: Basic concepts of enriched category theory. London Math. Soc. Lecture Notes Series 64, Cambridge University Press 1982

[2] G.M. Kelly and Ross Street: Review of the elements of 2-categories. Sydney Category Seminar 1972/73, Springer Lecture Notes in Math. 420 (1974), 75-103

[3] A. Kock: Monads for which structures are adjoint to units. Submitted to Journ. Pure Appl. Alg. 1993; (revised form of Aarhus Preprint Series 1992 No. 3 and Aarhus Preprint Series 1972/73 No. 35).

[4] F.W. Lawvere: Ordinal sums and equational doctrines. Seminar on Triples and Categorical Homology Theory, Springer Lecture Notes in Math. 80 (1969), 141-155

[5] F.W. Lawvere: Tools for the advancement of objective logic: closed categories and toposes. The Logical Foundations of Cognition (ed. J. Macnamara and G.E. Reyes); Oxford University Press 1993

[6] S. Mac Lane: Homology. Grundlehren der Math. Wissenschaften 114, Springer Verlag 1963

[7] Ross Street: Fibrations and Yoneda’s Lemma in a 2-category. Sydney Category Seminar 1972/73, Springer Lecture Notes in Math. 420 (1974), 104-133

[8] Ross Street: Fibrations in bicategories. Cahiers de Topologie et Geometrie Differentielle 21 (1980), 111-160