Theory and Applications of Categories, Vol. 12, No. 3, 2004, pp. 73–194.

OPERADS IN HIGHER-DIMENSIONAL CATEGORY THEORY

TOM LEINSTER

ABSTRACT. The purpose of this paper is to set up a theory of generalized operads and multicategories and to use it as a language in which to propose a definition of weak n-category. Included is a full explanation of why the proposed definition of ncategory is a reasonable one, and of what happens when n ≤ 2. Generalized operads and multicategories play other parts in higher-dimensional algebra too, some of which are outlined here: for instance, they can be used to simplify the opetopic approach to n-categories expounded by Baez, Dolan and others, and are a natural language in which to discuss enrichment of categorical structures.

Contents

Introduction 73 1 Bicategories 77 2 Operads and multicategories 88 3 More on operads and multicategories 107 4 A definition of weak ω-category 138 A Biased vs. unbiased bicategories 166 B The free multicategory construction 177 C Strict ω-categories 180 D Existence of initial operad-with-contraction 189

References 192

Introduction

This paper concerns various aspects of higher-dimensional category theory, and in particular n-categories and generalized operads.

We start with a look at bicategories (Section 1). Having reviewed the basics of the classical definition, we define ‘unbiased bicategories’, in which n-fold composites of 1-cells are specified for all natural n (rather than the usual nullary and binary presentation). We go on to show that the theories of (classical) bicategories and of unbiased bicategories are equivalent, in a strong sense.

The heart of this work is the theory of generalized operads and multicategories. More exactly, given a monad T on a category E, satisfying simple conditions, there is a theory of T -operads and T -multicategories. (As explained in ‘Terminology’ below, a T -operad is a special kind of T -multicategory.) In Section 2 we set up the basic concepts of the theory, including the important definition of an algebra for a T -multicategory. In Section 3 we cover an assortment of further operadic topics, some of which are used in later parts of the paper, and some of which pertain to the applications mentioned in the first paragraph.

Received by the editors 2003-09-15 and, in revised form, 2004-02-16.

Transmitted by John Baez. Published on 2004-02-20.

2000 Mathematics Subject Classification: 18D05, 18D50, 18F99, 18A99.

Key words and phrases: n-category, operad, higher-dimensional category.

\begin{matrix}c \\ ◯ \end{matrix} Tom Leinster, 2004. Permission to copy for private use granted.

Section 4 is a definition of weak ω-category. (That is, it is a proposed definition; there are many such proposals out there, and no attempt at a comparison is made.) As discussed at more length under ‘Related Work’, it is a modification of Batanin’s definition [Bat]. Having given the definition formally, we take a long look at why it is a reasonable definition. We then explore weak n-categories (for finite n), and show that weak 2-categories are exactly unbiased bicategories.

The four appendices take care of various details which would have been distracting in the main text. Appendix A contains the proof that unbiased bicategories are essentially the same as classical bicategories. Appendix B describes how to form the free T -multicategory on a given T -graph. In Appendix C we discuss various facts about strict ω-categories, including a proof that the category they form is monadic over an appropriate category of graphs. Finally, Appendix D is a proof of the existence of an initial object in a certain category, as required in Section 4.

Terminology. The terminology for ‘strength’ in higher-dimensional category theory is rather in disarray. For example, when something works up to coherent isomorphism, it is variously described as ‘pseudo’, ‘weak’ and ‘strong’, or not given a qualifier at all. In the context of maps between bicategories another word altogether is often used (‘homomorphism’—see [Bén]). Not quite as severe a problem is the terminology for n-categories themselves: the version where things hold up to coherent isomorphism or equivalence is (almost) invariably called weak, and the version where everything holds up to equality is always called strict, but ‘n-category’ on its own is sometimes used to mean the weak one and sometimes the strict one. The tradition has been for ‘n-category’ to mean ‘strict n-category’. However, Baez has argued (convincingly) that the terminology should reflect the fact that the weak version is much more abundant in nature; so in his work ‘n-category’ means ‘weak n-category’.

I have tried to bring some unity to the situation. When an entity is characterized by things holding on the nose (i.e. up to equality), it will be called strict. When they hold up to coherent isomorphism or equivalence it will be called weak. When they hold up to a not-necessarily-invertible connecting map (which does not happen often here), it will be called lax. The term ‘n-category’ will not (I hope) be used in isolation, but will always be qualified by either ‘strict’ or ‘weak’, except in informal discussion where both possibilities are intended. However, in deference to tradition, ‘2-category’ will always mean ‘strict 2-category’, and ‘bicategory’ will be used for the notion of weak 2-category proposed by Bénabou in [Bén].

We will, of course, be talking about operads and multicategories. Again the terminology has been a bit messy: topologists, who by and large do not seem to be aware of Lambek’s (late 1960s) definition of multicategory, call multicategories ‘coloured operads’; whereas amongst category theorists, the notion of multicategory seems much more widely known than that of operad. Basically, an operad is a one-object multicategory. This is also the way the terminology will work when we are dealing with generalized operads and multicategories, from Section 2 onwards: a T -operad will be a one-object T -multicategory, in a sense made precise just after the definition (2.2.2) of T -multicategory. So a T -operad is a special kind of T -multicategory. This means that in the title of this work, the word ‘operads’ would more accurately be ‘multicategories’: but, of course, euphony is paramount.

I have not been very conscientious about the distinction between small and large (sets and classes), and hope that the reader will find the issue no more disturbing than usual.

0 is a member of the natural numbers, ℕ.

Related work. This paper was originally my PhD thesis. In the time between it being submitted for publication and it being accepted I wrote my book [Lei9], which expounds at greater length on many of the topics to be found here. (In particular, it should be understood that the comments following this paragraph were written before the book was.) If the reader wants a more detailed discussion then [Lei9] is the place to look; otherwise, I hope that this will serve as a useful medium-length account.

Much of what is here has appeared in preprints available electronically. The main references are [Lei1] and Sections I and II of [Lei3], and to a lesser extent [Lei5]. In many places I have added detail and rigour; indeed, much of the new writing is in the appendices.

The first section, Bicategories, is also largely new writing. However, the results it contains are unlikely to surprise anyone: they have certainly been in the air for a while, even if they have not been written up in full detail before. See [Her2, 9.1], [Lei3, p. 8], [Lei5, 4.4] and [Lei7, 4.3] for more or less explicit references to the idea. Closely related issues have been considered in the study of 2-monads made by the (largely) Australian school: see, for instance, [BKP], [Kel1] and [Pow]. The virtues of the main proof of this section (which is actually in Appendix A) are its directness, and that it uses an operad where a 2-monad might be used instead, which is more in the spirit of this work. Similar methods to those used here also provide a way of answering more general questions concerning possible ways of defining ‘bicategory’, as explained in [Lei8].

I first wrote up the material of Section 2 , Operads and multicategories, in [Lei1] (and another account appears in [Lei3]). At that time the ideas were new to me, but subsequently I discovered that the definition of T -multicategory had appeared in Burroni’s 1971 paper [Bur]. Very similar ideas were also being developed, again in ignorance of Burroni, by Hermida: [Her2]. However, one important part of Section 2 which does not seem to be anywhere else is 2.3, on algebras for a multicategory.

Burroni’s paper is in French, which I do not read well. This has had two effects: firstly, that I have not used it as a source at all, and secondly, that I cannot accurately tell what is in it and what is not. I have attempted to make correct attributions, but I may not entirely have succeeded here.

Section 3, More on operads and multicategories, is a selection of further topics concerning multicategories. Subsections 3.1–3.4 all appear, more or less, in both [Lei1] and [Lei3]. Other work related to 3.3 (Free Multicategories) is described in the paragraph on Appendix B below. A shorter version of 3.5 is in [Lei1]. Subsection 3.6 (on fcmulticategories) is covered in each of [Lei4], [Lei5] and [Lei6]. fc-multicategories are another of those ideas that seem to have been in the air; they also seem to be in [Bur] (p. 280), and appear in [Her1, 10.2]. Moreover, Burroni’s section IV.3 is entitled ‘T - profunctors and T -natural transformations’ (in French), and these entities presumably bear some resemblance to the profunctors and natural transformations discussed in 3.7.

Section 4 is A definition of weak ω-category, based on the definition given by Batanin in [Bat] (and summarized by Street in [Str3]). I first wrote a version of this section in [Lei3]. At the time I thought I was writing an account of Batanin’s definition, reshaped and very much simplified but with the same end result mathematically. In fact, in trying to understand the meaning of a difficult part of [Bat], I had made a guess which turned out to be inaccurate (as Batanin informed me), but still provided a reasonable definition of weak ω-category.

As far as originality and novelty go, the upshot for Section 4 is this. The section contains two main ideas: globular operads and contractions. Globular operads were proposed in [Bat], but in a rather complicated way; here, we are able to give a oneline definition (‘operads for the free strict ω-category monad’). Contractions were the concept in [Bat] of which I had made a creative and inaccurate interpretation, so our two definitions of contraction differ; the definition given here seems more economical than that in [Bat]. There is a comparison of the two strategies at the end of 4.5. Overall, the present definition of weak ω-category is very economical conceptually, and short too: given the basic language of general multicategories, it only takes a page or two (138–140).

Appendix A, Biased vs. unbiased bicategories, is commented on with Section 1 above.

Appendix B, The free multicategory construction, is almost exactly the same as the appendix of [Lei5]. It is very like the free monoid construction in Appendix B of [BJT], although I did not see this until after writing [Lei5]. This is a more subtle free monoid construction than most: it does not require the tensor (with respect to which we are taking monoids) either to be symmetric or to preserve sums on each side. In our context, the latter condition translates to saying that the functor T preserves sums, where we are trying to form free T -multicategories. This is often not the case: for instance, if T is the free monoid functor on Set. There is a version of the free multicategory construction in Burroni’s paper [Bur] (III.III), but he does insist that T preserves sums.

Most of Appendix C, Strict ω-categories, sets out results which are widely assumed (e.g. [Her1, §10.1] or [Lei3, Ch. II]). However, I do not know of another place where the main result, that strict ω-categories are monadic over globular sets and the induced monad is cartesian and finitary, is actually proved. The material in the last subsection (C.3) is not so widely known, but is a reworking of results in [Bat].

Appendix D proves the Existence of an initial operad-with-contraction. This is new material, and fills a gap left in [Lei3] (II.5). Experts in these matters will probably be able to wave their hands and say with conviction that the initial object exists, on the general principle of there being free models for finitary essentially algebraic theories.

Acknowledgements. This work was supported by a PhD grant from EPSRC, by a Research Scholarship at Trinity College, Cambridge, and subsequently by the Laurence Goddard Fellowship at St John’s College, Cambridge. The document was prepared in L^{A}TEX, using Paul Taylor’s diagrams package for some of the diagrams. I am very grateful to the many people who have helped me in this project, and would especially like to thank Martin Hyland.

1. Bicategories

The main purpose of this section is to provide an alternative definition of bicategory in which, instead of having a specified identity 1-cell on each object and a specified binary composite of any pair of adjacent 1-cells, one has a specified composite of any string of n 1-cells

[figure: •; •; ⋯; •]

for each n ∈ ℕ. We then prove that this definition is equivalent, in a strong sense, to the classical definition. The details of the proof are relegated to Appendix A.

This alternative definition of bicategory—which we call an unbiased bicategory—is very natural, and in many ways more natural than the classical definition. But this is not why it appears in this work: the reason is that we will need it in Section 4, where we show that for n = 2, our weak n-categories are just unbiased bicategories.

More information on the pedigree of these ideas is contained in the ‘Related Work’ part of the Introduction.

1.1. Review of classical material. Here we review the basic properties of bicategories and state our terminology. The original definition of bicategory was made in Bénabou’s paper [Bén], along with the definition of lax functor (called ‘morphism’ there). Other references for these definitions are [Lei2] and [Str2], which also include definitions of transformation and modification; but we will not need these further concepts here.

We will typically denote 0-cells (or ‘objects’) of a bicategory B by A, B, …, 1-cells by f, g, … and 2-cells by α, β, …, e.g.

A [figure: f; g; α] B.

The ‘vertical’ composite of 2-cells

· [figure: α; β]·

is written β^{∘}α or βα, and the ‘horizontal’ composite of 2-cells

·  [figure: α] ·  [figure: α′] ·

is written α′ ∗ α. We will not need names for the associativity and unit isomorphisms; when they are all identities, the bicategory is called a 2-category.

A lax functor (F, ϕ) : B \overline{}B′ (between bicategories B and B′) consists of a function F_{0} : B_{0} \overline{}B′_{0} on objects, a functor

F_{A,B} : B(A, B) \overline{}B′(F_{0}A, F_{0}B)

for each pair A, B of objects of B, and ‘coherence’ 2-cells

ϕ_{f,g} : F g^{∘}F f \overline{}F (g^{∘}f),  ϕ_{A} : 1_{F A}  \overline{}F 1_{A}

satisfying some axioms. If these 2-cells are all invertible then F is called a weak functor (Bénabou: ‘homomorphism’). If they are identities (so that F g^{∘}F f = F (g^{∘}f) and F 1 = 1) then F is called a strict functor.

Lax functors can be composed, and this composition obeys strict associativity and identity laws, so that we obtain a category Bicat_{lax}. Moreover, the class of weak functors is closed under composition, and the same goes for strict functors, and the identity functor on a bicategory is strict; thus we have categories

Bicat_{str} ⊆ Bicat_{wk} ⊆ Bicat_{lax},

all with the same objects. (A more categorical way of putting it is that there are faithful functors

[figure: Bicat_{str}; Bicat_{wk}; Bicat_{lax}]

which are the identity on objects, but I will continue to use the ⊆ notation for brevity.)

A monad in a bicategory B is a lax functor from the terminal bicategory 1 to B. Explicitly, this consists of a 0-cell A, a 1-cell A ^{^{t}} A, and 2-cells

A [figure: 1; t; t^{∘}t; η; μ]A,

such that the diagrams

[figure: t^{∘}1; tη; t^{∘}t; ηt; 1^{∘}t; ∼; ∼; t; μ; t^{∘}(t^{∘}t); tμ; t^{∘}t; ∼; (t^{∘}t)^{∘}t; t^{∘}t; μt; μ; t; μ]

commute.

There is a one-to-one correspondence between bicategories with precisely one 0-cell and monoidal categories. Given such a bicategory, B, there is a monoidal category whose objects are the 1-cells of B and whose morphisms are the 2-cells, and with p ⊗ q = p^{∘}q and α ⊗ β = α ∗ β, where p, q are 1-cells of B and α, β are 2-cells. Lax, weak and strict functors between the bicategories then correspond to lax monoidal functors, (weak) monoidal functors and strict monoidal functors.

We could equally well have chosen the opposite orientation, so that p ⊗ q = q^{∘}p and α ⊗ β = β ∗ α. However, we stick with our choice. The consequence is that ‘⊗ and ^{∘} go in the same direction’. (This accounts for the apparently odd reversal of R and R′ in Example 3.6.1(b).)

1.2. Unbiased bicategories. The traditional definition of a bicategory is ‘biased’ towards binary and nullary compositions, in that only these are given explicit mention. For instance, there is no specified ternary composite of 1-cells, (h, g, f) ⟼ hgf, only the derived ones like h(gf) and ((h1)g)(f1). It is necessary to be biased in order to achieve a finite axiomatization. However, it is useful in this work (and elsewhere) to have a notion of ‘unbiased bicategory’, in which all arities are treated even-handedly. In this subsection we define unbiased bicategory and unbiased weak functor, and in the next we compare this approach to the classical one.

1.2.1. Definition. An unbiased bicategory B consists of

• a class B_{0}, whose elements are called objects or 0-cells

• for each pair A, B of objects, a category B(A, B), whose objects are called 1-cells and whose morphisms are called 2-cells • for each sequence A_{0}, …, A_{n} of objects (n ≥ 0), a ‘composition’ functor

comp_{(A_{0}, ... ,A_{n})} : B(A_{n−1}, A_{n}) × ⋯ × B(A_{0}, A_{1})  \overline{}B(A_{0}, A_{n}),
(f_{n}, …, f_{1}) ⟼ (f_{n}^{∘} ⋯^{∘}f_{1}),
(α_{n}, …, α_{1}) ⟼ (α_{n} ∗ ⋯ ∗ α_{1}),

where the f_{i}’s are 1-cells and the α_{i}’s are 2-cells

• for each double sequence ((f_{1}^{1}, …, f_{1}^{k_{1}}), …, (f_{n}^{1}, …, f_{n}^{k_{n}})) of 1-cells such that the composite (f_{n}^{k_{n}}^{∘} ⋯^{∘}f_{n}^{1}^{∘} ⋯^{∘}f_{1}^{k_{1}}^{∘} ⋯^{∘}f_{1}^{1}) makes sense, an invertible 2-cell

γ_{((f_{1}^{1}, ... ,f_{1}^{k_{1}}), ... ,(f_{n}^{1}, ... ,f_{n}^{kn}))} :

((f_{n}^{k_{n}}^{∘} ⋯^{∘}f_{n}^{1})^{∘} ⋯^{∘}(f_{1}^{k_{1}}^{∘} ⋯^{∘}f_{1}^{1})) ^{∼} (f_{n}^{k_{n}}^{∘} ⋯^{∘}f_{n}^{1}^{∘} ⋯^{∘}f_{1}^{k_{1}}^{∘} ⋯^{∘}f_{1}^{1})

• for each 1-cell f, an invertible 2-cell

ι_{f} : f ^{∼} (f)

with the following properties:

• γ_{((f_{1}^{1}, ... ,f_{1}^{k_{1}}), ... ,(f_{n}^{1}, ... ,f_{n}^{kn}))} is natural in each of the f_{i}^{j}’s, and ι_{f} is natural in f

• associativity: for any triple sequence (((f_{p,q,r})_{r=1}^{k_{p}^{q}})_{q=1}^{m_{p}})_{p=1}^{n} of 1-cells such that the following composites make sense, the diagram

(((f_{n,mn,k{mn \atop n}} ∘···∘f_{n,mn,1})∘···∘(f_{n,1,k1 n}∘···∘f_{n,1,1}))∘···∘((f_{1,m1,k{m1 \atop 1}} ∘···∘f_{1,m1,1})∘···∘(f_{1,1,k1 1}∘···∘f_{1,1,1})))
[figure: (γ_{Dn}∗···∗γ_{D_{1}}); γ_{D′}]
((f_{n,mn,k{mn \atop n}} ∘···∘f_{n,1,1})∘···∘(f_{1,m1,k{m1 \atop 1}} ∘···∘f_{1,1,1}))  ((f_{n,mn,k{mn \atop n}} ∘···∘f_{n,mn,1})∘···∘(f_{1,1,k1 1}∘···∘f_{1,1,1}))
[figure: γ_{D}; γ_{D′′}]
(f_{n,mn,k{mn \atop n}} ∘···∘f_{1,1,1})

commutes, where the double sequences D_{p}, D, D′, D′′ are

D_{p} = ((f_{p,1,1}, …, f_{p,1,k_{p}^{1}}), …, (f_{p,m_{p},1}, …, f_{p,m_{p},k_{p}^{mp}})),
D = ((f_{1,1,1}, …, f_{1,m_{1},k_{1}^{m_{1}}}), …, (f_{n,1,1}, …, f_{n,m_{n},k_{n}^{mn}})),
D′ = (((f_{1,1,k_{1}^{1}}^{∘} ⋯^{∘}f_{1,1,1}), …, (f_{1,m_{1},k_{1}^{m_{1}}}^{∘} ⋯^{∘}f_{1,m_{1},1})), …,
((f_{n,1,k_{n}^{1}}^{∘} ⋯^{∘}f_{n,1,1}), …, (f_{n,m_{n},k_{n}^{mn}}^{∘} ⋯^{∘}f_{n,m_{n},1}))),
D′′ = ((f_{1,1,1}, …, f_{1,1,k_{1}^{1}}), …, (f_{n,m_{n},1}, …, f_{n,m_{n},k_{n}^{mn}}))

• identity: for any composable sequence (f_{1}, …, f_{n}) of 1-cells, the diagrams

[figure: (f_{n}^{∘} ⋯^{∘}f_{1}); (ι_{fn}∗···∗ι_{f_{1}}); ((f_{n})^{∘} ⋯^{∘}(f_{1})); 1; (f_{n}^{∘} ⋯^{∘}f_{1}); γ_{((f_{1}), ... ,(fn))}; ((f_{n}^{∘} ⋯^{∘}f_{1})); ι_{(fn∘···∘f_{1})}; (f_{n}^{∘} ⋯^{∘}f_{1}); 1; (f_{n}^{∘} ⋯^{∘}f_{1}); γ_{((f_{1}, ... ,fn))}]

commute.

1.2.2. Remarks.

a. The associativity axiom is less fearsome than it might appear. It says that any two ways of removing brackets are equivalent, just as the associativity axiom does for a monad such as ‘free group’ on Set. If we allow different styles of brackets then it says, for instance, that

{[(h^{∘}g)^{∘}(f^{∘}e)]^{∘}[(d^{∘}c)^{∘}(b^{∘}a)]}
[figure: (γ ∗ γ); γ]
{[h^{∘}g^{∘}f^{∘}e]^{∘}[d^{∘}c^{∘}b^{∘}a]}  {(h^{∘}g)^{∘}(f^{∘}e)^{∘}(d^{∘}c)^{∘}(b^{∘}a)}
[figure: γ; γ]
{h^{∘}g^{∘}f^{∘}e^{∘}d^{∘}c^{∘}b^{∘}a}

commutes.

b. The coherence axioms for an unbiased bicategory are rather obvious, in contrast to the situation for classical bicategories: they look just like the associativity and unit axioms for a monoid.

c. An unbiased monoidal category may be defined as an unbiased bicategory with precisely one object; we would then write ⊗ in place of both ^{∘} and ∗.

d. If we drop the condition that γ and ι are invertible, then we obtain what might be called a lax or relaxed bicategory. (Or perhaps ‘colax’ would be more appropriate.) A one-object lax bicategory is then a relaxed monoidal category in the sense of [Lei5, 4.4]. In the other direction, let us define an unbiased 2-category as an unbiased bicategory in which the components of γ and ι are all identities. (Clearly unbiased 2-categories are in one-to-one correspondence with ordinary 2-categories.) So we have three classes of structures:

{unbiased 2-categories} ⊆ {unbiased bicategories} ⊆ {lax bicategories}.

For the moment this is just a statement about classes (large sets), but soon we will define maps between these structures and thus be able to compare the categories they form.

e. We have given a very explicit definition of unbiased bicategory, but a more abstract version is possible. There is a 2-category Cat-Gph, an object of which is a set B_{0} together with an indexed family

(B(B, B′))_{B,B′∈B_{0}}

of categories (a ‘Cat-graph’). An arrow F : B \overline{}C consists of a function F_{0} : B_{0} \overline{}C_{0} and a functor

F_{B,B′} : B(B, B′) \overline{}C(F_{0}B, F_{0}B′)

for each B, B′ ∈ B_{0}. There is only a 2-cell

B [figure: F; G] C

if F_{0} = G_{0}, and in this case such a 2-cell α is a family of natural transformations α_{B,B′} : F_{B,B′} \overline{}G_{B,B′}. Now, there is a 2-monad ‘free 2-category’ on Cat-Gph, and a (small) unbiased bicategory is, in a suitable sense, a weak algebra for this 2-monad. The definition of relaxed monoidal category in [Lei5, 4.4] implicitly uses this approach, but with lax algebras rather than weak algebras. For more on this point of view, see [KS] and [Pow]. We also use this approach in Appendix A.

f. The notation (f_{n}^{∘} ⋯^{∘}f_{1}) for the composite of a diagram

A_{0} ^{f_{1}} A_{1} ^{f_{2}} ⋯ ^{f_{n}} A_{n}

is sometimes inadequate in the case n = 0. When n = 0 the data to be composed is just a single object A_{0}, and we might prefer to write 1_{A_{0}} rather than the standard notation, ().

1.2.3. Definition. Let B and B′ be unbiased bicategories. An unbiased lax functor (F, ϕ) : B \overline{}B′ consists of

• a function F_{0} : B_{0} \overline{}B′_{0} (usually just written F)

• for each A, B ∈ B_{0}, a functor F_{A,B} : B(A, B) \overline{}B′(F_{0}A, F_{0}B) (again, usually just written F)

• for each composable sequence (f_{1}, …, f_{n}) of 1-cells, a 2-cell

ϕ_{(f_{1}, ... ,f_{n})} : (F f_{n}^{∘} ⋯^{∘}F f_{1}) \overline{}F (f_{n}^{∘} ⋯^{∘}f_{1}),

with the properties that

• ϕ_{(f_{1}, ... ,f_{n})} is natural in each f_{i}

• for each double sequence ((f_{1}^{1}, …, f_{1}^{k_{1}}), …, (f_{n}^{1}, …, f_{n}^{k_{n}})) of 1-cells such that the following composites make sense, the diagram

((F f_{n}^{k_{n}}^{∘} ⋯^{∘}F f_{n}^{1})^{∘} ⋯^{∘}(F f_{1}^{k_{1}}^{∘} ⋯^{∘}F f_{1}^{1})) \overline{γ′_{((F f_{1}^{1}, ... ,F f_{1}^{k_{1}}), ... ,(F f_{n}^{1}, ... ,F f_{n}^{kn}))}_{}}(F f_{n}^{k_{n}}^{∘} ⋯^{∘}F f_{1}^{1})

(F (f_{n}^{k_{n}}^{∘} ⋯^{∘}f_{n}^{1})^{∘} ⋯^{∘}F (f_{1}^{k_{1}}^{∘} ⋯^{∘}f_{1}^{1})) (ϕ_{(f_{n}^{1}, ... ,f_{n}^{kn})} ∗ ⋯ ∗ ϕ_{(f_{1}^{1}, ... ,f_{1}^{k_{1}})})_{}

[figure: F ((f_{n}^{k_{n}}^{∘} ⋯^{∘}f_{n}^{1})^{∘} ⋯^{∘}(f_{1}^{k_{1}}^{∘} ⋯^{∘}f_{1}^{1})); ϕ_{((f_{1}^{k_{1}}∘···∘f_{1}^{1}), ... ,(f_{n}^{kn}∘···∘f_{n}^{1}))}; F γ_{((f_{1}^{1}, ... ,f_{1}^{k_{1}}), ... ,(f_{n}^{1}, ... ,f_{n}^{kn}))}; F (f_{n}^{k_{n}}^{∘} ⋯^{∘}f_{1}^{1}); ϕ_{(f_{1}^{1}, ... ,f_{n}^{kn})}]

commutes

• for each 1-cell f, the diagram

[figure: F f; ι′_{F f}; (F f); F f; ‖; F ι_{f}; F (f); ϕ_{(f)}]

commutes.

An unbiased weak functor is an unbiased lax functor (F, ϕ) for which each ϕ_{(f_{1}, ... ,f_{n})} is invertible. An unbiased strict functor is an unbiased lax functor (F, ϕ) for which each ϕ_{(f_{1}, ... ,f_{n})} is the identity (so that F preserves composites and identities strictly).

We noted in Remark (b) that the coherence axioms for an unbiased bicategory were rather obvious, having the shape of the axioms for a monoid or monad. Perhaps the coherence axioms for an unbiased lax functor are a little less obvious; however, they are the same shape as the axioms for a monad functor given in Street’s paper [Str1], and in any case seem to be quite canonical in some vague sense.

Naturally, we would like to be able to compose lax functors. Given unbiased lax functors

B ^{(F,ϕ)} B′ ^{(F′,ϕ′)} B′′,

define the composite (G, ψ) by G_{0} = F′_{0}^{∘}F_{0}, G_{A,B} = F′_{F A,F B}^{∘}F_{A,B}, and by taking ψ_{(f_{1}, ... ,f_{n})} to be the composite of

(GF f_{n}^{∘} ⋯^{∘}GF f_{1}) ^{ϕ′_{(F f_{1}, ... ,F fn)}} G(F f_{n}^{∘} ⋯^{∘}F f_{1}) ^{Gϕ_{(f_{1}, ... ,fn)}} GF (f_{n}^{∘} ⋯^{∘}f_{1}).

Also define the identity unbiased lax functor (G, ψ) on an unbiased bicategory B by G_{0} = id, G_{A,B} = id, and ψ_{(f_{1}, ... ,f_{n})} = id. It is straightforward to check that composition is associative and that the identity functors live up to their name. We therefore obtain a category UBicat_{lax} of unbiased bicategories and unbiased lax functors. Evidently there are subcategories

UBicat_{str} ⊆ UBicat_{wk} ⊆ UBicat_{lax},

with the same objects and with arrows which are, respectively, unbiased strict functors and unbiased weak functors.

In fact, the definitions of unbiased lax functor and of their composites and identities work just as well for lax bicategories (1.2.2(d)). So there are 3 × 3 = 9 possible categories we might consider: for both the objects and the arrows, we choose one of ‘strict’, ‘weak’ or ‘lax’. With what I hope is obvious notation, the inclusions are as follows:

LBicat_{str} ⊆ LBicat_{wk} ⊆ LBicat_{lax}
∪^{|} ∪^{|} ∪^{|}
UBicat_{str} ⊆ UBicat_{wk} ⊆ UBicat_{lax}
∪^{|} ∪^{|} ∪^{|}
U2-Cat_{str} ⊆ U2-Cat_{wk} ⊆ U2-Cat_{lax}.

Of these nine, we might consider the three on the diagonal (bottom-left to top-right) to be the most conceptually natural. We will not actually need to discuss anything except for the middle row in the rest of this work. However, these remarks demonstrate the cleanliness of the unbiased theory when compared to the biased (classical) theory. In the latter, the top row is obscured—that is, there is no very satisfactory way to weaken the classical definition of bicategory to get a lax version. Admittedly, one can drop the condition that the classical associativity and unit maps are isomorphisms (as in [Borx1], after Definition 7.7.1); but somehow this does not seem quite right.

Another advertisement for the unbiased theory follows. To give it we need some preliminary basic constructions. Firstly, for any bicategory B (biased or unbiased), there is an opposite bicategory B^{op}, obtained by reversing the 1-cells only: thus to each 2-cell

A [figure: f; g; α] B

in B there corresponds a 2-cell

A[figure: f; g; α] B

in B^{op}. Secondly, one may form the product A × B of any two (biased or unbiased) bicategories in the obvious way (and this is the categorical product in each of the lax, weak and strict contexts). Thirdly, there is a 2-category Cat of all (small) categories, functors and natural transformations, and there is a corresponding unbiased 2-category Cat.

Now, we would like to form a functor

Hom : B^{op} × B  \overline{}Cat,
(A, B) ⟼ B(A, B)

for each B (ignoring questions of size). In the biased case this is not possible without making an arbitrary choice. For if A′ ^{^{f}} A and B ^{^{g}} B′ in B then applying Hom should give us a function

B(A, B) \overline{}B(A′, B′),

and this might reasonably be either p ⟼ (g^{∘}p)^{∘}f or p ⟼ g^{∘}(p^{∘}f). Although we could, say, consistently choose the first option and thereby get a weak functor Hom, neither choice is ‘canonical’. However, in the unbiased case one has a ternary composite (g^{∘}p^{∘}f), giving a canonical weak functor

Hom : B^{op} × B \overline{}Cat.

1.3. Biased vs. unbiased. In this subsection we define a forgetful functor

V : UBicat_{lax} \overline{}Bicat_{lax},

which turns out to be full, faithful and surjective on objects. (Proofs are deferred to Appendix A.) Thus the categories of biased and unbiased bicategories, with lax functors as maps, are equivalent; and the same in fact goes for weak functors, although not strict ones. So we will more or less be able to ignore the biased-unbiased distinction.

The primary reason for setting out the theory of unbiased bicategories in this paper is that in Section 4 we give a definition of weak n-category, and a weak 2-category is exactly an unbiased bicategory. We therefore want to know that unbiased and classical bicategories are essentially the same, as a test of the reasonability of our proposed definition.

This somewhat practical motivation provides an answer to a question which the reader may have been asking: where are the unbiased transformations and modifications? Quite simply, we don’t mention them because we don’t need them: the unbiased and classical theories can be compared without going above the level of functors.

An equally important answer is that transformations and modifications between unbiased bicategories are not defined because there seems to be no properly ‘unbiased’ way to do it. Of course, we can ‘cheat’ by transporting the definitions from Bicat_{lax} along the functor

V : UBicat_{lax} \overline{}Bicat_{lax}.

This immediately gives a coherence theorem: every unbiased bicategory is biequivalent to an unbiased 2-category. More honest coherence results, of the form ‘every diagram commutes’, appear in Appendix A.

Note also that the equivalence UBicat_{lax} ≃ Bicat_{lax} is two levels better than we might have expected: if B and B′ are two unbiased bicategories with V (B) = V (B′) ∈ Bicat_{lax}, then B and B′ are not just biequivalent in UBicat_{lax}, or even just equivalent: they are actually isomorphic. Put another way, we have a comparison which takes place at the 1-dimensional level, without having to resort to 2- or 3-dimensional structures.

To business: let us define the forgetful functor V. Given an unbiased bicategory B, attempt to define a biased bicategory C = V (B) by:

• C_{0} = B_{0}

• C(A, B) = B(A, B)

• composition

C(B, C) × C(A, B) \overline{}C(A, C)

in C is

comp_{(A,B,C)} : B(B, C) × B(A, B) \overline{}B(A, C)

• the identity in C on an object A is (the image of)

comp_{(A)} : 1 \overline{}B(A, A)

• the associativity isomorphism (h^{∘}g)^{∘}f \overline{}h^{∘}(g^{∘}f) is the composite of the 2-cells

((h^{∘}g)^{∘}f) ^{(1∗ι_{f})} ((h^{∘}g)^{∘}(f)) ^{γ_{((f),(g,h))}} (h^{∘}g^{∘}f) ^{γ_{((f,g),(h))}^{−1}} ((h)^{∘}(g^{∘}f)) ^{(ι_{h}^{−1}∗1)} (h^{∘}(g^{∘}f))

• the left unit isomorphism 1^{∘}f \overline{}f is the composite of the 2-cells

(()^{∘}f) ^{(1∗ι_{f})} (()^{∘}(f)) ^{γ_{((f),())}} (f) ^{ι_{f}^{−1}} f,

and dually for the right unit.

Given an unbiased lax functor (F, ϕ) : B \overline{}B′, attempt to define a lax functor (G, ψ) = V (F, ϕ) : V (B) \overline{}V (B′) by

G_{0} = F_{0},  G_{A,B} = F_{A,B},  ψ_{f,g} = ϕ_{(f,g)},  ψ_{A} = ϕ_{()}.

Here the symbol ϕ_{()} denotes ϕ_{(f_{1}, ... ,f_{n})} in the case n = 0, where

A = A_{0} ^{f_{1}} A_{1} ^{f_{2}} ⋯ ^{f_{n}} A_{n}.

In Appendix A we prove:

1.3.1. Theorem. With these definitions,

a. V (B) is a bicategory and V (F, ϕ) is a lax functor

b. V preserves composition and identities, so forms a functor

UBicat_{lax}  \overline{}Bicat_{lax}

c. V is full, faithful and surjective on objects.

If (F, ϕ) is a weak (respectively, strict) functor then V (F, ϕ) is one too, so V restricts to give functors

V_{wk} : UBicat_{wk}  \overline{}Bicat_{wk},  V_{str} : UBicat_{str}  \overline{}Bicat_{str}.

In the appendix we prove:

1.3.2. Corollary. The restricted functor V_{wk} : UBicat_{wk} \overline{}Bicat_{wk} is also full, faithful and surjective on objects.

Thus UBicat_{lax} ≃ Bicat_{lax} and UBicat_{wk} ≃ Bicat_{wk}.

Finally, what about the strict case—is V_{str} an equivalence of categories? Certainly V_{str} is surjective on objects and faithful (since the same is true of V), so the only question is whether it is full. It is not. For let C be any bicategory, and construct from C an unbiased bicategory L with V (L) = C, defining composition in L by associating to the left: e.g. the composite (f_{4}^{∘}f_{3}^{∘}f_{2}^{∘}f_{1}) in L is the composite ((f_{4}^{∘}f_{3})^{∘}f_{2})^{∘}f_{1} in C. (Appendix A shows that this construction is possible.) Dually, define an unbiased bicategory R with V (R) = C by associating to the right. If F : L \overline{}R is an unbiased strict functor with V (F) = 1_{C} then F must be the identity (since the data for an unbiased strict functor is just a graph map), and so L = R. But we can choose a bicategory C in which (h^{∘}g)^{∘}f ≠ h^{∘}(g^{∘}f) for some 1-cells f, g, h, so that L ≠ R. Hence the identity on C does not lift to a strict functor L \overline{}R, and therefore V_{str} is not full.

2. Operads and multicategories

In this section we introduce the language of operads and multicategories to be used in the rest of the paper. The simplest kind of operad—a plain operad—consists of a sequence C(0), C(1), … of sets together with an ‘identity’ element of C(1) and ‘composition’ functions

C(n) × C(k_{1}) × ⋯ × C(k_{n}) \overline{}C(k_{1} + ⋯ + k_{n}),

obeying associativity and identity laws. (In the original definition, [May1], the C(n)’s were not just sets but spaces with symmetric group action. Our operads never have symmetric group actions.) The simplest kind of multicategory—a plain multicategory—consists of a collection C_{0} of objects, and arrows

a_{1}, …, a_{n} ^{^{θ}} a

(a_{1}, …, a_{n}, a ∈ C_{0}), together with composition functions and identity elements obeying associativity and unit laws. (See [Lam, p. 103] for the details.) A plain operad is therefore a one-object plain multicategory.

The general idea now is that there’s nothing special about sequences of objects: the domain of an arrow might form another shape instead, such as a tree of objects or just a single object (as in a normal category). Indeed, the objects do not even need to form a set. Maybe a graph or a category would do just as well. Together, what these generalizations amount to is the replacement of the free-monoid monad on Set with some other monad on some other category.

This generalization is put into practice as follows. The graph structure of a plain multicategory is a diagram

C_{1}
[figure: dom; cod]
T C_{0}  C_{0}

in Set, where T is the free-monoid monad. Now, just as a (small) category can be described as a diagram

D_{1}
[figure]
D_{0}  D_{0}

in Set together with identity and composition functions

D_{0}  \overline{}D_{1},  D_{1} ×_{D_{0}} D_{1}  \overline{}D_{1}

satisfying some axioms, so we may describe the multicategory structure on

T C_{0} \underline{}C_{1} \overline{}C_{0}

by manipulation of certain diagrams in Set. In general, we take a category E and a monad T on E satisfying some simple conditions, and define ‘(E, T)-multicategory’. Thus a category is a (Set, id)-multicategory.

Subsection 2.1 describes the simple conditions on E and T required in order that everything that follows will work. Many examples are given. Subsection 2.2 explains what (E, T)-multicategories are, and what (E, T)-operads are—namely, one-object (E, T)- multicategories. Subsection 2.3 defines and explains algebras for multicategories, which are a generalization of Set-valued functors on a category. If an operad is thought of as a kind of algebraic theory (in which the elements of C(n) are n-ary operations) then an algebra for an operad is a model of that theory.

2.1. Cartesian monads. In this subsection we introduce the conditions required of a monad (T, η, μ) on a category E in order that we may (in 2.2) define the notions of (E, T)-multicategory and (E, T)-operad. The conditions are that the category and the monad are both cartesian, as defined now.

2.1.1. Definition. A category is called cartesian if it has all finite limits.

2.1.2. Definition. A monad (T, η, μ) on a category E is called cartesian if

a. η and μ are cartesian natural transformations, i.e. for any X ^{^{f}} Y in E the naturality squares

[figure: X; η_{X}; T X; Y; f; η_{Y}; T Y; T f; T^{2}X; μ_{X}; T X; T^{2}Y; T^{2}f; μ_{Y}; T Y; T f]

are pullbacks, and

b. T preserves pullbacks.

We often write T to denote the whole monad (T, η, μ), as is customary.

It would perhaps be more consistent to call a category cartesian just if it has pullbacks, and indeed this is all that is necessary in order to make the theory of general multicategories work. However, all of our examples have a terminal object too (and therefore all finite limits), and it is convenient to assume that this is always the case. For instance, the definition of (E, T)-operad only makes sense when E has a terminal object.

2.1.3. Examples.

a. The identity monad on any category is clearly cartesian. b. Let E = Set and let T be the monoid monad, i.e. the monad arising from the

adjunction

Monoid [figure: ⊤] Set.

Certainly E is cartesian. It is easy to calculate that T, too, is cartesian ([Lei1, 1.4(ii)]), although the theory explained in Example (d) below renders this unnecessary.

c. A non-example. Let E = Set and let (T, η, μ) be the free commutative monoid monad. This is not cartesian: e.g. the naturality square for μ at 2 \overline{}1 is not a pullback. See also Example 2.2.6(c) for some related thoughts.

d. Let E = Set. Any finitary algebraic theory gives a monad on E; which are cartesian? Without answering this question completely, we indicate a certain class of theories which do give cartesian monads. An equation (made up of variables and finitary operations) is said to be strongly regular if the same variables appear in the same order, without repetition, on each side. Thus

(x.y).z = x.(y.z) and (x ↑ y) ↑ z = x ↑ (y.z),

but not

x + (y + (−y)) = x, x.y = y.x or (x.x).y = x.(x.y),

qualify. A theory is called strongly regular if it can be presented by operations and strongly regular equations. In Example (b), the only property of the theory of monoids that we actually needed was its strong regularity: for in general, the monad yielded by any strongly regular theory is cartesian. This last result, and the notion of strong regularity, are due to Carboni and Johnstone. They show in [CJ] (Proposition 3.2 via Theorem 2.6) that a theory is strongly regular if and only if η and μ are cartesian natural transformations and T preserves wide pullbacks. A wide pullback is by definition a limit of shape

·  ·  ·  ⋯  ·
[figure]
·  ,

where the top row is a set of any size (perhaps infinite). When the set is of size 2 this is an ordinary pullback, so the monad from a strongly regular theory is indeed cartesian. (Examples (e), (f) and (g) can also be found in [CJ].)

e. Let E = Set, let E be a fixed set, and let + denote binary coproduct: then the endofunctor — + E on E has a natural monad structure. This monad is cartesian, corresponding to the algebraic theory consisting only of one constant for each member of E. In particular, if E = 1 then this is the theory of pointed sets. f. Let E = Set and let M be a monoid: then the endofunctor M × — on E has a

natural monad structure. This monad is cartesian, corresponding to an algebraic theory consisting only of unary operations.

g. Let E = Set, and consider the finitary algebraic theory on E generated by one n-ary operation for each n ∈ ℕ and no equations. This theory is strongly regular, so the induced monad (T, η, μ) on E is cartesian.

If X is any set then T X can be described inductively by

• if x ∈ X then x ∈ T X

• if t_{1}, …, t_{n} ∈ T X then ⟨t_{1}, …, t_{n}⟩ ∈ T X.

We can draw any element of T X as a tree with leaves labelled by elements of X:

• x ∈ X is drawn as x •

• if t_{1}, …, t_{n} are drawn as T_{1}, …, T_{n} then ⟨t_{1}, …, t_{n}⟩ is drawn as

[figure: T^{1} T^{2} ⋯ T^{n}; •] ,

or if n = 0, as \begin{matrix}∘ \\ • \end{matrix}.

Thus the element ⟨⟨x_{1}, x_{2}, ⟨⟩⟩, x_{3}, ⟨x_{4}, x_{5}⟩⟩ of T X is drawn as

[figure: ∘; {x_{1} \atop •} {x_{2} \atop •} •  {x_{4} \atop •}  {x_{5} \atop •}; •  {x_{3} \atop •}  •; •] .

The unit X \overline{}T X is x ⟼ x •, and multiplication T^{2}X \overline{}T X takes a T Xlabelled tree (e.g.

[figure: ∘; {t_{1} \atop •}  •; •  {t_{2} \atop •}; •] ,

with

t_{1} = [figure: {x_{2} \atop •}; {x_{1} \atop •} •; •] and t_{2} = [figure: ∘; {x_{3} \atop •} • {x_{4} \atop •}; •; •] )

and gives an X-labelled tree by substituting at the leaves (here,

[figure: {x_{2} \atop •}  ∘; {x_{1} \atop •}  • ∘ {x_{3} \atop •} • {x_{4} \atop •}; •  •  •; •  •; •] ).

h. On the category Cat of small categories and functors, there is the free strict mo-

noidal category monad. Both Cat and the monad are cartesian. i. In Section 4 we will examine the free strict ω-category monad on the category of

globular sets. Both category and monad are cartesian. j. A double category may be defined as a category object in Cat. More descriptively,

the graph structure consists of collections of • 0-cells A

• horizontal 1-cells f

• vertical 1-cells p

• 2-cells α and various source and target functions, as illustrated by the picture

[figure: A_{1}; f_{1}; A_{2}; ⇓ α; A_{3}; p_{1}; f_{2}; A_{4}; p_{2}] .

The category structure consists of identities and composition functions for 2-cells and both kinds of 1-cell, obeying strict associativity, identity and interchange laws; see [KS] for more details.

More generally, let us define n-cubical set for any n ∈ ℕ; the intention is that a 2cubical set will be the underlying graph of a double category. Let ℍ be the category

(1 [figure: σ; τ] 0), so that a functor ℍ \overline{}Set is a directed graph, and define an ncubical set as a functor ℍ^{n} \overline{}Set. Then, for instance, a functor X : ℍ^{2} \overline{}Set becomes a two-dimensional graph of the type just described, via

• X(0, 0) = {0-cells}

• X(1, 0) = {horizontal 1-cells}

• X(0, 1) = {vertical 1-cells}

• X(1, 1) = {2-cells},

and the map

(σ, 1) : (1, 1) \overline{}(0, 1)

in ℍ^{2} induces the map

\{2-cells\} \overline{}\{vertical 1-cells\}

which sends α to p_{1} in the diagram above.

We may now define a (strict) n-tuple category to be an n-cubical set together with various compositions and identities, as for double categories, all obeying strict laws. The category of n-cubical sets has on it the free strict n-tuple category monad; both category and monad are cartesian. Since we will not need to use cubical sets or n-tuple categories, this construction is not made precise and no proof is offered that the monad is cartesian.

2.2. Multicategories. We now describe what an (E, T)-multicategory is, where T is a cartesian monad on a cartesian category E. As mentioned in the introduction to this section, this is a generalization of the well-known description of a small category as a monad object in the bicategory of spans.

We will use the phrase ‘(E, T) is cartesian’ to mean that E is a cartesian category and (T, η, μ) is a cartesian monad on E.

2.2.1. Construction.

Let (E, T) be cartesian. We construct a bicategory Span(E, T) from (E, T), which in the case T = id is the usual bicategory of spans in E. Hermida calls Span(E, T) the ‘Kleisli bicategory of spans’ in [Her2]; the formal similarity between the definition of Span(E, T) and the usual construction of a Kleisli category is evident.

94  TOM LEINSTER

0-cell: Object S of E. 1-cell R \overline{}S: Diagram

M
[figure]
T R  S
in E.

2-cell M \overline{}M′: Commutative diagram

M
[figure]
T R  S
[figure]
M′^{}
in E.

1-cell composition: To define this we need to choose particular pullbacks in E, and in everything that follows we assume this has been done. Take

\begin{aligned}& & M \\ & [figure: d] & & [figure: c] \\ T R & & & & S \end{aligned} and \begin{aligned}& & N \\ & [figure: q] & & [figure: p] \\ T S & & & & Q \end{aligned} ;

then their composite is given by the diagram

N^{∘}M [figure]

[figure]
T M  N
[figure: T d; T c; q; p]
T^{2}R  T S  Q
[figure: μ_{R}]
T R

where the right-angle mark in the top square indicates that the square is a pullback.

1-cell identities: The identity on S is

S
[figure: η_{S}; 1]
T S  S .

2-cell identities and compositions: Identities and vertical composition are as in E. Horizontal composition is defined in an obvious way.

Because the choice of pullbacks is arbitrary, 1-cell composition does not obey strict associative and identity laws. That it obeys them up to invertible 2-cells is a consequence of the fact that (T, η, μ) is cartesian.

2.2.2. Definition. Let (E, T) be cartesian. Then an (E, T)-multicategory is a monad in Span(E, T).

An (E, T)-multicategory therefore consists of a diagram

T C_{0} ^{d} C_{1} ^{^{c}} C_{0}

in E and maps

C_{0} ^{ids} C_{1}, C_{1}^{∘}C_{1} ^{comp} C_{1}

satisfying associative and identity laws. Think of C_{0} as ‘objects’, C_{1} as ‘arrows’, d as ‘domain’ and c as ‘codomain’. Such a multicategory will be called an (E, T)-multicategory on C_{0}, and a (E, T)-multicategory on the terminal object 1 will be called an (E, T)-operad.

(Plain multicategories are often called ‘coloured operads’ in the literature, where the ‘colours’ are the objects of the multicategory: thus an operad is a single-coloured operad. A two-object plain multicategory would be called an ‘operad of two colours’, typically black and white. Baez and Dolan, in [BD], use ‘operad’ or ‘typed operad’ for the same kind of purpose as we use ‘multicategory’, and ‘untyped operad’ where we use ‘operad’.)

It is inherent that everything is small: when E = Set, for instance, the objects and arrows form sets, not classes. For plain multicategories, at least, there seems to be no practical difficulty in using large versions too.

In order to say what maps between (E, T)-multicategories are, we first introduce the notion of an (E, T)-graph.

2.2.3. Definition. Let (E, T) be cartesian. An (E, T)-graph (on an object C_{0}) is a diagram T C_{0} \underline{}C_{1} \overline{}C_{0} in E. A map of (E, T)-graphs

[figure: C_{1}; T C_{0}  C_{0}; C̃_{1}; T C̃_{0}  C̃_{0}]

is a pair (C_{0} ^{f_{0}} C̃_{0}, C_{1} ^{f_{1}} C̃_{1}) of maps in E such that

C_{1}
[figure]
T C_{0}  C_{0}
C̃_{1} f_{1}_{}
[figure]
[figure: T C̃_{0}; T f_{0}; C̃_{0}; f_{0}]

commutes.

This definition uses two different notions of a map between objects of E: on the one hand, genuine maps in E, and on the other, spans (i.e. 1-cells of Span(E, T)). A possible approach to formalizing this situation is via the ‘equipments’ of [CKVW]. But this is not our approach: as explained in 3.6 and 3.7, fc-multicategories are the structures that capture exactly what we want.

Any (E, T)-multicategory has an underlying (E, T)-graph, enabling the following definition to be made.

2.2.4. Definition. A map of (E, T)-multicategories C \overline{}C̃ is a map f of their underlying graphs such that the diagrams

[figure: C_{0}; f_{0}; C̃_{0}; C_{1}; ids; f_{1}; C̃_{1}; ĩds] C_{1}^{∘}C_{1} \overline{f_{1} ∗ f_{1}_{}}C̃_{1}^{∘}C̃_{1}

[figure: C_{1}; comp; f_{1}; C̃_{1}; { \atop comp}]

commute. (Here f_{1} ∗ f_{1} is the evident map induced by two copies of C_{1} ^{f_{1}} C_{1}.)

With these definitions we obtain categories

(E, T)-Graph, (E, T)-Multicat,

and a forgetful functor from the second to the first. Wherever possible we drop the ‘E’ and refer simply to T -multicategories, T -operads, T -Graph, etc.

It is also possible to define modules (profunctors) and natural transformations for T -multicategories, which we eventually do in 3.7.1(c).

2.2.5. Remarks.

a. Fix S ∈ E. Then we may consider the category of T -graphs on S, whose morphisms f = (S ^{f_{0}} S, C_{1} ^{f_{1}} C̃_{1}) all have f_{0} = 1. This is just the slice category \frac{E}{T S×S}. It is also the full sub-bicategory of Span(E, T) whose only object is S, and is therefore a monoidal category. The category of T -multicategories on S is then the category Mon(\frac{E}{T S×S}) of monoids in \frac{E}{T S×S}. In particular, E/T 1 is a monoidal category, and a monoid therein is a T -operad; this is a style of definition of plain operad sometimes found in the literature.

b. A choice of pullbacks in E was made; changing that choice gives an isomorphic category of (E, T)-multicategories.

c. If (E′, T′) is also cartesian then a cartesian monad functor from (E, T) to (E′, T′) induces a functor

(E, T)-Multicat \overline{}(E′, T′)-Multicat,

and the same is true of monad opfunctors. See 3.2 for an explanation.

2.2.6. Examples.

a. Let (E, T) = (Set, id). Then Span(E, T) is the usual ‘bicategory of spans’, and a monad in Span(E, T) is just a (small) category. Thus categories are (Set, id)- multicategories. Functors are maps of such. More generally, if E is any cartesian category then (E, id)-multicategories are internal categories in E, and similarly, idoperads are monoids.

b. Let (E, T) = (Set, free monoid). Specifying a T -graph

T C_{0} ^{d} C_{1} ^{^{c}} C_{0}

is equivalent to specifying a set C_{0} (‘of objects’) together with a set C(a_{1}, …, a_{n}; a) for each n ≥ 0 and a_{1}, …, a_{n}, a ∈ C_{0}. An element θ ∈ C(a_{1}, …, a_{n}; a) is illustrated by

a_{1}, …, a_{n} ^{^{θ}} a

or

[figure: a; a_{1}; a_{2}; a_{n}; θ]

or

[figure: …; a_{2}; a_{1}; ⇓ θ; a_{n}; \overline{a}] .

When n = 0, the first version looks like

· ^{^{θ}} a,

the second has no legs on the left-hand (‘input’) side, and the third is drawn as

a ⇓θ .

In Span(E, T), the identity 1-cell T C_{0} ^{η_{C_{0}}} C_{0} ^{^{1}} C_{0} on C_{0} has

C_{0}(a_{1}, …, a_{n}; a) = \{ \begin{matrix}1 & if n = 1 and a_{1} = a \\ ∅ & otherwise. \end{matrix}

The composite 1-cell C_{1}^{∘}C_{1} in Span(E, T) is

{((θ_{1}, …, θ_{n}), θ) | dθ = (cθ_{1}, …, cθ_{n})},

i.e. is the set of diagrams

[figure: θ_{1}; θ_{2}; θ_{n}; θ] .  (1)

If C is a T -multicategory then we have a function ids assigning to each a ∈ C_{0} a member of C(a; a), and a function comp composing diagrams like (1). These are required to obey associative and identity laws. Thus a (Set, free monoid)-multicategory is just a plain multicategory and a (Set, free monoid)-operad is a plain operad.

c. Suppose we want to realise symmetric operads as T -operads for some T. By a symmetric operad I mean a plain operad C with an action of the nth symmetric group S_{n} on C(n) for each n, satisfying certain axioms: in other words, an operad in the usual sense of topologists (e.g. [May2]), except that the C(n)’s are sets rather than spaces or graded modules etc.

A first attempt might be to take the free commutative monoid monad T on Set. But this is both misguided and doomed to failure: misguided because the maps

— · σ : C(n) \overline{}C(n)

coming from permutations σ ∈ S_{n} are only isomorphisms, not identities; and doomed because T is not cartesian (2.1.3(c)).

A more promising approach is to take T to be the free symmetric strict monoidal category monad on Cat, and to try to identify the symmetric operads as certain special T -operads. I have not investigated how well this works, but this idea seems to be related to the structures called ‘symmetric operads’ at the beginning of [BD] and explored further in [Che1] and [Che2].

d. Let E = Set, and consider the monad — + 1 of 2.1.3(e). A (Set, — + 1)-graph is a diagram C_{0} + 1 ^{d} C_{1} ^{^{c}} C_{0} of sets; this is like an ordinary (Set, id)-graph, except that some arrows have domain 0—an extra element not in C_{0}. (Thus 1 = {0} here.) If we put

Y (a) = {y ∈ C_{1} | dy = 0 and cy = a}

for each a ∈ C_{0}, then a multicategory structure on the graph provides a function

[figure: Y (a); Y (a′); y ⟼ θ^{∘}y; •; •; •; •; •; 0; θ^{∘}y; y; a; a′; θ; C_{0}]

for each θ ∈ C_{1} with d(θ) = a ∈ C_{0} and c(θ) = a′. It also provides a category structure on D_{0} ^{d} D_{1} ^{^{c}} D_{0}, where D_{0} = C_{0} and D_{1} = {θ ∈ C_{1} | dθ ∈ C_{0}}. Thus a (Set, — + 1)-multicategory turns out to be a (small) category D together with a functor Y : D \overline{}Set. Similarly, a (Set, — + E)-multicategory is a category D together with an E-indexed family of functors D \overline{}Set.

To put it another way, an (E, T)-multicategory is a discrete opfibration. More exactly, the category of (E, T)-multicategories is equivalent to the category whose objects are discrete opfibrations between small categories and whose morphisms are commutative squares.

e. Let M be a monoid and (E, T) = (Set, M × —). Then a T -multicategory consists of a category C together with a functor C \overline{}M, and in fact T -Multicat ≅ Cat/M. f. Let (E, T) = (Set, tree monad), as in 2.1.3(g). A T -multicategory consists of a set

C_{0} of objects, and hom-sets like

C ([figure: ∘; {a_{1} \atop •}  •; •  {a_{2} \atop •}; • a])

(a_{1}, a_{2}, a ∈ C_{0}), together with a unit element of each C(a • ; a) and composition functions like

C ([figure: ∘; {a_{1} \atop •}  •; •  {a_{2} \atop •}; • a]) × \{C ([figure: {b_{2} \atop •}; {b_{1} \atop •}  •; {• \atop a_{1}}]) × C ([figure: ∘; {b_{3} \atop •} • {b_{4} \atop •}; •; {• \atop a_{2}}])\}

\overline{}C ([figure: {b_{2} \atop •}  ∘; {b_{1} \atop •}  • ∘ {b_{3} \atop •} • {b_{4} \atop •}; •  •  •; •  •; • a])

(b_{1}, b_{2}, b_{3}, b_{4} ∈ C_{0}). These are to satisfy associativity and identity laws.

When C_{0} = 1, so that we’re considering T -operads, the graph structure is comprised of sets like

C ([figure: ∘; •  •; •  •; •]) .

The T -multicategories are a simpler version of Soibelman’s pseudo-monoidal categories ([Soi]) or Borcherds’ relaxed multilinear categories ([Borh], [Sny1], [Sny2]); they omit the aspect of maps between trees. See the end of 3.8 for comments on the unsimplified version. g. When E = Cat and T is the free strict monoidal category monad, a T -operad is

what Soibelman calls a strict monoidal 2-operad ([Soi, 2.1]). Such a structure might also be thought of as a plain operad enriched in Cat, in a sense not made precise here but explained in detail in [Lei5] and outlined in 3.8 below.

h. Let (E, T) = (globular sets, free strict ω-category), as in Example 2.1.3(i). A T - operad is exactly a globular operad in the sense of Batanin: see Section 4.

i. Operads for (E, T) = (n-cubical sets, free strict n-tuple category) can be understood in much the same way as Batanin’s globular operads (again, see Section 4), with cubical rather than globular shapes. For instance, a cell in the free strict n-tuple category on the terminal n-cubical set can be represented as a cuboid whose edgelengths are natural numbers; a T -operad associates a set (‘of operations’) to each such cuboid, and has composition functions according to ways of combining cuboids. (I will not take this example any further.)

j. Let (E, T) be cartesian, let X ∈ E, and let T X ^{^{h}} X be a map. Then the T -graph (T X ^{1} T X ^{^{h}} X) can be given the structure of a T -multicategory in at most one way, and this is possible if and only if T X ^{^{h}} X is an algebra for the monad T. (If it is possible then ids = η and comp = μ.) Maps between T -multicategories of this form are, similarly, just T -algebra maps. So we have a full and faithful functor

M : E^{T} \overline{}T -Multicat

turning algebras into multicategories.

2.3. Algebras. The motivating idea in the definition of a (plain) operad is that it is some kind of algebraic theory, with the nth component C(n) of an operad C being the set of n-ary operations. One therefore defines an algebra for an operad C to be a set X together with a suitable family of functions

C(n) × X^{n} \overline{}X,

one for each n ∈ ℕ. More generally, a plain multicategory can be regarded as a manysorted theory, and in an algebra for a multicategory one has not just a single set X, but one set X(a) for each object a of C. Thus if Set denotes the (large, plain) multicategory whose objects are sets and in which a map

S_{1}, …, S_{n} \overline{}S

is a function

S_{1} × ⋯ × S_{n} \overline{}S,

then an algebra for a plain multicategory C can be defined as a map C \overline{}Set of multicategories.

In this subsection we generalize these ideas to arbitrary (E, T). That is, we define a category Alg(C) of algebras for any (E, T)-multicategory C.

102  TOM LEINSTER

2.3.1. Construction.

Let (E, T) be cartesian: then any (E, T)-multicategory C gives rise to a monad (T_{C}, unit, mult) on E/C_{0}. In what follows, I will write T_{C}(X ^{^{p}} C_{0}) as X′ ^{p′} C_{0}.

• Given (X ^{^{p}} C_{0}) ∈ E/C_{0}, we define (X′ ^{p′} C_{0}) to be the right-hand diagonal

of the diagram

· [figure]
[figure]
T X  C_{1}
[figure: T p; d; c]
T C_{0}  C_{0}

(recalling that the right-angle mark denotes a pullback square).

• If

[figure: X; f; Y; p; q; C_{0}]

is a map in E/C_{0} then there is a unique map f′ : X′ \overline{}Y′ making

X′ [figure]
[figure: ...............................................; f′]
[figure: T X; C_{1}; Y′]
[figure: T p; T f; d; 1]
T C_{0}  T Y  C_{1}
[figure: 1; T q; d]
T C_{0}

commute, and we define

T_{C}(f) = f′ : (\begin{matrix}X′ \\ C_{0} & p′_{} \end{matrix}) \overline{}(\begin{matrix}Y′ \\ C_{0} & q′_{} \end{matrix}) .

• The unit at (X ^{^{p}} C_{0}) is given by

X

[figure: η_{X}; p]
C_{0}
[figure: X′; unit_{p}; .; .; . . . . . . . . . .]
[figure]
T X  C_{1} ids_{}
[figure: T p; d]

T C_{0}.

• For multiplication, we have a commutative diagram

X′′
[figure]
T X′
[figure]
T^{2}X  T C_{1}  C_{1}
[figure: μ_{X}; T^{2}p; T d; T c; d]
T X  T^{2}C_{0}  T C_{0}

and a pullback square

C_{1}^{∘}C_{1} [figure]
[figure]
T C_{1}  C_{1}
[figure: T c; d]
T C_{0}.

From these we deduce that there are maps

X′′

[figure]
T X  C_{1}^{∘}C_{1},

and the multiplication at (X ^{^{p}} S) is then given by

X′′
[figure]
C_{1}^{∘}C_{1}
[figure: X′; mult_{p}; .; .; . . . . . . . . . .]
[figure]
T X  C_{1} comp_{}
[figure: T p; d]
T C_{0}.

It is now straightforward, though tedious, to check that (T_{C}, unit, mult) forms a monad on E/C_{0}.

2.3.2. Definition. Let (E, T) be cartesian and let C be a T -multicategory. Then the category Alg(C) of algebras for C is the category of algebras for the monad T_{C} on E/C_{0}.

We sometimes say C-algebra instead of ‘algebra for C’.

2.3.3. Examples.

a. When (E, T) = (Set, id), so that an (E, T)-multicategory is an ordinary (small) category C, we have Alg(C) ≃ [C, Set].

b. When (E, T) = (Set, free monoid), so that an (E, T)-multicategory is a plain multicategory, we already have an idea of what an algebra for C should be: a map C \overline{}Set of multicategories (p. 101). That is, an algebra for C should consist of:

• for each a ∈ C_{0}, a set X(a)

• for each a_{1}, …, a_{n} ^{^{θ}} a in C, a function X(a_{1}) × ⋯ × X(a_{n}) \overline{}X(a),

preserving identities and composition. This is the same as the definition of algebra just given. To see this, let (X ^{^{p}} C_{0}) be an object of E/C_{0}: then, writing X(a) = p^{−1}{a} for a ∈ C_{0}, and similarly X′(a) = (p′)^{−1}{a}, we have

X′(a) = {((x_{1}, …, x_{n}), θ) | x_{i} ∈ X, θ ∈ C_{1}, dθ = (px_{1}, …, px_{n}), cθ = a}
= {X(a_{1}) × ⋯ × X(a_{n}) × C(a_{1}, …, a_{n}; a) | a_{1}, …, a_{n} ∈ C_{0}}.

An algebra structure on (X ^{^{p}} C_{0}) therefore consists of a function

X(a_{1}) × ⋯ × X(a_{n}) ^{θ̄} X(a)

for each

a_{1}, …, a_{n} ^{^{θ}} a

in C, with the assignation θ ⟼ θ̄ subject to certain rules. These turn out to say exactly that we have a multicategory map C \overline{}Set.

c. When (E, T) = (Set, — + 1), a T -multicategory is an ordinary category D together with a functor D ^{^{Y}} Set. A (D, Y)-algebra is then a functor D ^{X} Set together with a natural transformation

D  [figure: Y; ⇓; X] Set .

In terms of fibrations, a T -multicategory is a discrete opfibration Y over a small category D, and an algebra for Y consists of another discrete opfibration X over D together with a map from Y to X (of opfibrations over D).

d. Let M be a monoid and let (E, T) = (Set, M × —), so that a T -multicategory is a category C together with a functor C ^{^{π}} M. Then the category of algebras for (C, π) is simply [C, Set], regardless of what π is.

e. Let (E, T) be the tree monad on Set. For simplicity, let us just consider algebras for T -operads C—thus the object-set C_{0} is 1. An algebra for C consists of a set X together with a function X′ \overline{}X satisfying some axioms. One can calculate that an element of X′ consists of an X-labelling of the leaves of a tree τ together with a member of C(τ). An X-labelling of an n-leafed tree τ is just a member of X^{n}, so one can view the algebra structure X′ \overline{}X on X as: for each number n, each n-leafed tree τ, and each element of C(τ), a function X^{n} \overline{}X. These functions are required to be compatible with composition and identities in C.

f. For (E, T) = (globular sets, free strict ω-category), we will consider in Section 4 a certain operad L, the initial ‘operad-with-contraction’. A weak ω-category is then defined to be an L-algebra.

g. The graph T 1 ^{1} T 1 ^{^{!}} 1 is terminal amongst all (E, T)-graphs. It carries a unique multicategory structure, since a terminal object in a monoidal category always carries a unique monoid structure. It then becomes the terminal (E, T)- multicategory. The induced monad on E/1 is just (T, η, μ), and so an algebra for the terminal multicategory is just a T -algebra.

This can aid recognition of when a theory of operads or multicategories fits into our scheme. For instance, if we were to read Batanin’s paper and learn that, in his terminology, an algebra for the terminal operad is a strict ω-category ([Bat, §7, example 3]), then we might suspect that his operads were (E, T)-operads for the free strict ω-category monad T on an appropriate category E—as indeed they are. h. If T is a monad on a category E, and h = (T X ^{^{h}} X) is a T -algebra, then there

is a monad T/h on E/X whose functor part acts on objects by

[figure: Y; X; p; ⟼; T Y; T X; T p; X.; h]

Writing Alg for the category of algebras of a monad, we then have

Alg(T/h) ≅ Alg(T)/h,

where the right-hand side is Alg(T) sliced over h.

Now recall from Example 2.2.6(j) that when (E, T) is cartesian, the algebra h defines a T -multicategory

T X ^{1} T X ^{^{h}} X.

Naturally enough, it turns out that the monad on E/X induced by this multicategory is T/h: so the category of algebras for this multicategory is Alg(T)/h. (Example (g) above is a special case.)

We have seen how to associate to each (E, T)-multicategory C a category Alg(C), and we would expect some kind of functoriality. When (E, T) = (Set, id), a functor C \overline{}C′ induces a functor

Alg(C) = [C, Set] \underline{}[C′, Set] = Alg(C′),

and it is obvious that the same phenomenon holds for (E, T) = (Set, free monoid) if we view C-algebras as multicategory maps C \overline{}Set (2.3.3(b)).

In general, given a map f : C \overline{}C′ of (E, T)-multicategories, we obtain a functor Alg(C) \underline{}Alg(C′) as follows. First of all, we have the functor

E/C_{0} ^{_{f_{0}^{∗}}} E/C′_{0}

defined by pullback along f_{0} : C_{0} \overline{}C′_{0}. Then, as it turns out, there is a naturallyarising natural transformation

E/C_{0} ^{_{}f ∗ 0} E/C′_{0}
[figure: ϕ]
[figure: E/C_{0}; T_{C}; f_{0}^{∗}; E/C′_{0},; T_{C′}]

and this satisfies the axioms for a monad functor from T_{C′} to T_{C}. (Monad functors are defined in 3.2, and details of this construction are left to the reader.) Hence there is an induced functor from the category of T_{C′}-algebras to the category of T_{C}-algebras—that is, from Alg(C′) to Alg(C).

Because these induced functors are defined by pullback, the map

Alg : ((E, T)-Multicat)^{op} \overline{}CAT

inevitably preserves composition and identities only up to canonical isomorphism; in other words, it is a weak functor or pseudo-functor. In fact, there is a notion of natural transformation for T -multicategories, so that (E, T)-Multicat is a 2-category; and Alg is then a weak functor between 2-categories. Transformations for T -multicategories are discussed in Example 3.7.1(c), where we see that the natural structure formed by T - multicategories is not a 2-category but something richer: an fc-multicategory.

3. More on operads and multicategories

This section is an assortment of further topics in the general theory of multicategories. Some will be used in the discussion of weak n-categories in the final section. Others are not used there, but answer naturally-arising questions or have applications outside this paper. One of the subsections (3.8, Enrichment) is an introduction to a topic too large to include in full.

The contents of the subsections are as follows.

3.1 Structured categories We look at T -structured categories, which are to T - multicategories as strict monoidal categories are to plain multicategories.

3.2 Change of base Here we ask whether the passage from (E, T) to (E, T)-Multicat is functorial. It turns out that it is, in not one but three different ways. (The ‘base’ is (E, T).)

3.3 Free multicategories This subsection concerns when and how the free T - multicategory on a T -graph can be formed. Details are deferred to Appendix B.

The next two subsections each give an alternative (but equivalent) definition of algebra for a T -multicategory.

3.4 Algebras via fibrations In ordinary category theory there is a correspondence between Set-valued functors and discrete fibrations. We extend this to T - multicategories, giving an alternative definition of an algebra.

3.5 Algebras via endomorphisms We give a second alternative definition of an algebra, generalizing the definition of algebra for an operad often used by topologists.

The final subsections are on fc-multicategories: what they are, and two familiar categorical ideas for which they provide generalized contexts.

3.6 fc-multicategories This really belongs as an example in the previous section, and would be there but for its length. We examine T -multicategories in the case when T is the free category monad on the category of directed graphs.

3.7 The bimodules construction We show how an fc-multicategory V gives rise to a new fc-multicategory Bim(V), by taking bimodules (= modules, = profunctors, = distributors) in V.

3.8 Enrichment There is an interesting theory of enrichment for T -multicategories. Applied to the most basic case, categories, it provides a theory of categories enriched in an fc-multicategory. All of this is explained properly in [Lei5]; here we sketch the ideas.

None of these subsections is necessary in order to read the bulk of Section 4. The last part of Section 4, on weak n-categories, does rely on the material of 3.2 (Change of base). It also contains inessential references to 3.5 and 3.6. Appendix D, which supports Section 4, uses free multicategories (3.3).

3.1. Structured categories. The observation from which this subsection takes off is that any strict monoidal category has an underlying multicategory. (For the time being, all monoidal categories and maps between them are strict, and ‘multicategory’ means plain multicategory.) Explicitly, if (D, ⊗) is a monoidal category, then the underlying multicategory C has the same objects as D and has hom-sets defined by

C(a_{1}, …, a_{n}; a) = D(a_{1} ⊗ ⋯ ⊗ a_{n}, a)

for objects a_{1}, …, a_{n}, a. Composition and identities in C are easily defined.

There is a converse process: given any multicategory C, there is a ‘free’ monoidal category D on it. An object (respectively, arrow) of D is a sequence of objects (respectively, arrows) of C. Thus the objects of D are of the form (a_{1}, …, a_{n}) (a_{i} ∈ C_{0}), and a typical arrow

(a_{1}, a_{2}, a_{3}, a_{4}, a_{5}) \overline{}(a′_{1}, a′_{2}, a′_{3})

is a sequence (θ_{1}, θ_{2}, θ_{3}) of maps in C with domains and codomains as illustrated:

[figure: a′_{3}; a_{4}; a_{5}; θ_{3}; a′_{2}; θ_{2}; a′_{1}; a_{1}; a_{2}; a_{3}; θ_{1}]  (2)

The tensor in D is juxtaposition.

For example, the terminal multicategory 1 has one object and, for each n ∈ ℕ, one arrow of the form

n {  [figure]  ;

diagram (2) suggests that the ‘free’ monoidal category on the multicategory 1 is Δ, the category of finite ordinals (including 0), with addition as ⊗.

The name ‘free’ is justified: that is, there is an adjunction

(monoidal categories)

(multicategories) ⊣ _{}^{}

where the two functors are those described above, and (monoidal categories) denotes the category of strict monoidal categories and strict monoidal functors. Moreover, this adjunction is monadic.

(Note that the forgetful functor does not provide a full embedding of (monoidal categories) into (multicategories). For example, there is a multicategory map 1 \overline{}Δ sending the unique object of 1 to the object 1 of Δ, and this map does not preserve the monoidal structure. If D and D′ are strict monoidal categories then a map UD \overline{}UD′ of their underlying multicategories is actually the same as a lax monoidal functor D \overline{}D′.)

Naturally, we would like to generalize from (E, T) = (Set, free monoid) to any cartesian (E, T). To do this, we need a notion of ‘(E, T)-structured category’ which in the case (Set, free monoid) means monoidal category. A monoidal category is a category object in Monoid, so it is reasonable to define a T -structured category to be an (E^{T} , id)- multicategory—that is, an internal category in the category E^{T} of algebras for the monad T on E. We write

T -Struc = (E^{T} , id)-Multicat.

The fact that E is cartesian guarantees that E^{T} is too.

(In this subsection, (D, S)-Multicat is treated as a mere (1-)category, for any cartesian D and S.)

It is now possible to describe a monadic adjunction

T -Struc

T -Multicat \begin{aligned}F &  \\ & ⊣ U_{} \end{aligned}

generalizing that above. The effect of the functors U and F on objects is as outlined now. Given a T -structured category D, with algebraic structure T D_{0} ^{h_{0}} D_{0} and T D_{1} ^{h_{1}} D_{1}, the graph (T D_{0} \underline{}C_{1} \overline{}D_{0}) of UD is given by

C_{1} [figure]
[figure]
T D_{0}  D_{1}
[figure: h_{0}]
D_{0}  D_{0}.

Given a T -multicategory C, the category F C has graph

T C_{1}
[figure]
T^{2}C_{0}
[figure: μ_{C_{0}}]
T C_{0}  T C_{0}

and the algebraic structures T^{2}C_{0} ^{h_{0}} T C_{0} and T^{2}C_{1} ^{h_{1}} T C_{1} are components of μ. For an example of U in action, take a T -algebra (T X ^{^{h}} X). The diagram

X ^{1} X ^{^{1}} X

determines a (discrete) internal category in E^{T}; that is, a T -structured category, D(X, h). Then U(D(X, h)) is a T -multicategory with graph isomorphic to

T X ^{1} T X ^{^{h}} X.

So U(D(X, h)) is isomorphic to the T -multicategory M(X, h) of Example 2.2.6(j), and we have a triangle of functors

E^{T}  \overline{D ^{}}T -Struc
[figure: M; U]

T -Multicat

which commutes up to natural isomorphism.

For an example of F, take E to be Set and T = ( )^{∗} to be the free monoid monad. Take the terminal plain multicategory 1, which has graph

ℕ ^{1} ℕ ^{^{!}} 1.

Then F (1) is a strict monoidal category with graph

ℕ ^{+} ℕ^{∗} ^{!^{∗}} ℕ.

In other words, the objects of F (1) are the natural numbers, and an arrow (m \overline{}n) in F (1) is a sequence (m_{1}, …, m_{n}) of natural numbers such that m_{1} + ⋯ + m_{n} = m. That is, the objects are the finite ordinals and the arrows are the order-preserving functions. So we find that F (1) ≅ Δ, as claimed above.

As the reader may have noticed, a monoidal category does not have to be strict in order to have an underlying plain multicategory: any monoidal category will do. If D is the monoidal category then we can define a plain multicategory C with the same objects as D and with

C(a_{1}, …, a_{n}; a) = D(a_{1} ⊗ ⋯ ⊗ a_{n}, a).

In order for this to make sense, D must have n-fold tensor products for all n, not just for n = 0 and n = 2. There are various attitudes we can take to this. One is to abandon the usual definition of monoidal category, and work instead with unbiased monoidal categories, as defined in Section 1. Another is to use the traditional definition, but to derive n-fold tensors by, for instance, ‘associating to the left’ (as in Appendix A); but this is really just a roundabout version of the first attitude.

A third is more sophisticated. Take an n-leafed tree τ in which all nodes have either 0 or 2 outgoing edges: in the language introduced on page 174, a ‘classical tree’. This gives a method of tensoring together n objects in a classical monoidal category, which will be written

(a_{1}, …, a_{n}) ⟼ \overline{τ}(a_{1}, …, a_{n}).

For instance, if n = 2 then τ might be the first tree illustrated in Example 2.2.6(f) (without its labels), in which case

\overline{τ}(a_{1}, a_{2}) = (a_{1} ⊗ I) ⊗ a_{2}.

If τ and τ′ are two n-leafed classical trees then there is a canonical isomorphism

ω_{τ,τ′} : \overline{τ}(a_{1}, …, a_{n}) ^{∼} \overline{τ′}(a_{1}, …, a_{n}).

Now, start with a monoidal category D, and define from it a plain multicategory C with the same objects as D and in which a map a_{1}, …, a_{n} \overline{}a is a family

(f_{τ} : \overline{τ}(a_{1}, …, a_{n}) \overline{}a)

of maps in C indexed by n-leafed classical trees τ, such that f_{τ′}^{∘}ω_{τ,τ′} = f_{τ} for all τ and τ′. Since all of the f_{τ}’s are determined by any single one of them, the multicategory C is isomorphic to the one obtained by associating to the left; however, our new construction does not have the element of arbitrary choice.

Choosing one version or another of this process, we can compose with the functor F above to obtain a functor from (non-strict) monoidal categories to strict monoidal categories. Let D be a monoidal category and E the resulting strict monoidal category. Then an object of E is a sequence of objects of D, and an arrow

(a_{1}, …, a_{m}) \overline{}(b_{1}, …, b_{n})

in E consists of a sequence of arrows

a_{1}^{1} ⊗ ⋯ ⊗ a_{1}^{k_{1}}  \overline{}b_{1},
…  …
a_{n}^{1} ⊗ ⋯ ⊗ a_{n}^{k_{n}}  \overline{}b_{n}

in D (with n-fold tensors interpreted in the chosen way), such that the sequence

a_{1}^{1}, …, a_{1}^{k_{1}}, …, a_{n}^{1}, …, a_{n}^{k_{n}}

is equal to a_{1}, …, a_{m}. Tensor of both objects and arrows in E is by juxtaposition, and composition comes from the composition in D. (This E is not to be confused with the strict monoidal category st(D) defined in [JS, §1], which is monoidally equivalent to D.)

It does not seem straightforward to generalize the notion of (non-strict) monoidal category to give a notion of weak T -structured category, so for now these observations must be confined to the context of monoidal categories.

3.2. Change of base. So far we have only discussed (E, T)-multicategories for a fixed (E, T). In this subsection we look at what happens when (E, T) varies: in other words, at how the Multicat construction is functorial. We also examine functoriality of the structured categories construction, Struc.

Throughout this subsection (E, T)-Multicat will be regarded as a (1-)category. Subsection 3.7 contains an outline of a more advanced treatment of this material, in which (E, T)-Multicat is treated as an fc-multicategory—a categorical structure containing much more information than a mere category.

First we need to ‘recall’ some definitions from Street’s paper [Str1].

Let T and T′ be monads on respective categories E and E′ (not necessarily cartesian). A monad functor (E, T) ^{(Q,ψ)} (E′, T′) consists of a functor E ^{Q} E′ together with a natural transformation

E  \overline{T ^{}}E
[figure: ψ]
[figure: E; Q; T′; E′; Q]

making the diagrams

[figure: T^{′2}Q; T′ψ; T′QT; ψT; QT^{2}; T′Q; μ′Q; ψ; QT; Qμ; Q = = = = = = = = = Q; T′Q; η′Q; ψ; QT; Qη]

commute. If (E, T) ^{(R,χ)} (E′, T′) is another monad functor then a monad functor transformation (Q, ψ) \overline{}(R, χ) is a natural transformation Q ^{^{α}} R such that (αT)^{∘}ψ = χ^{∘}(T′α). There is consequently a 2-category Mnd whose 0-cells are pairs (E, T), whose 1-cells are monad functors, and whose 2-cells are monad functor transformations.

(In fact, [Str1] concerns monads and monad functors etc. in an arbitrary 2-category V. We are only interested in the case V = Cat.)

A crucial property of monad functors is that they induce maps between (Eilenberg-Moore) categories of algebras: thus if (Q, ψ) is a monad functor as above then there is an induced functor \overline{Q} : E^{T} \overline{}E^{′T′}.

Dually, there is a notion of a monad opfunctor, which is just like a monad functor except that ψ travels in the opposite direction; similarly, monad opfunctor transformations. This gives another 2-category, Mnd′. A monad opfunctor (E, T) \overline{}(E′, T′) induces a functor E_{T} \overline{}E′_{T′} between Kleisli categories.

We will also need a third 2-category, Mnd^{⊣}. Again, an object is a category E equipped with a monad T. A 1-cell from (E, T) to (E′, T′) consists of a monad functor (Q, ψ) : (E, T) \overline{}(E′, T′), a monad opfunctor (P, ϕ) : (E′, T′) \overline{}(E, T), and an adjunction P ⊣ Q compatible with the two monads. (Explicitly, this compatibility means that if γ and δ are the unit and counit of the adjunction then the diagrams

[figure: T′; T′γ; T′QP; QP T′; γT′; Qϕ; QT P; ψP; P T′Q; ϕQ; T P Q; P QT; P ψ; δT; T; T δ]

commute.) A 2-cell in Mnd^{⊣} consists of a monad functor transformation and a monad opfunctor transformation obeying further compatibility laws. Composition and identities in Mnd^{⊣} are defined in the evident way.

(Incidentally, if we are given a monad opfunctor (P, ϕ) : (E′, T′) \overline{}(E, T) and a functor Q right adjoint to P, then Q naturally becomes a monad functor (Q, ψ) by taking ψ to be the mate of ϕ. The two compatibility squares then commute, so we get a 1-cell of Mnd^{⊣}. This fact is used in the proof of Proposition 4.7.3(a).)

A monad functor (Q, ψ) will be called cartesian if Q preserves pullbacks; then cartesian pairs (E, T), cartesian monad functors, and all monad functor transformations form a sub-2-category CartMnd of Mnd. A monad opfunctor (P, ϕ) will be called cartesian if P preserves pullbacks and ϕ is a cartesian natural transformation; then cartesian pairs (E, T), cartesian monad opfunctors, and all monad opfunctor transformations form a sub-2-category CartMnd′ of Mnd′. Finally, we get a sub-2-category CartMnd^{⊣} of Mnd^{⊣} by allowing only cartesian pairs (E, T) as objects, 1-cells (P, ϕ, Q, ψ, γ, δ) in which (P, ϕ) is a cartesian monad opfunctor and (Q, ψ) a cartesian monad functor, and all 2-cells.

These definitions are rather haphazard: natural transformations are apparently required to be cartesian (or not) at random. The only justification I can give is that they seem to be necessary in order to make the constructions in the rest of this subsection work. Pulling in the other direction, if we want the Struc example (diagram (3)) to work then we cannot modify the definition of cartesian monad functor to include the condition that the natural transformation part ψ is cartesian—for in that case, it isn’t.

We have now collected together the definitions we need, and are ready to see the three different ways in which the Multicat construction is functorial. Only an outline of each construction is presented; the details are easily filled in.

Firstly, let (E, T) and (E′, T′) be cartesian and let (Q, ψ) : (E, T) \overline{}(E′, T′) be a cartesian monad functor. Then there is an induced functor

\overline{Q} : (E, T)-Multicat \overline{}(E′, T′)-Multicat

defined by pullback. That is, if C is a T -multicategory then \overline{Q}(C) is a T′-multicategory on QC_{0} whose underlying graph is given by

(\overline{Q}C)_{1} [figure]
[figure]
T′QC_{0}  QC_{1}
[figure: ψ_{C_{0}}; Qd; Qc]
QT C_{0}  QC_{0}.

Dually, let (P, ϕ) : (E′, T′) \overline{}(E, T) be a cartesian monad opfunctor. Then there is an induced functor

\overline{P} : (E′, T′)-Multicat \overline{}(E, T)-Multicat

defined by composition. That is, if C′ is a T′-multicategory then \overline{P} (C′) is a T -multicategory on P C′_{0} whose underlying graph is given by

P C′_{1}
[figure: P d; P c]
P T′C′_{0}
[figure: ϕ_{C′_{0}}]
T P C′_{0}  P C′_{0}.

After filling in all the details we get two maps of 2-categories:

CartMnd \overline{}CAT,  CartMnd′  \overline{}CAT.

The first is defined using pullbacks, so is only a weak functor (pseudo-functor); the second is a strict functor. On 0-cells, both functors send (E, T) to the (large) category (E, T)-Multicat. At the ‘intersection’ of CartMnd and CartMnd′ is the 2-category whose 1-cells are what might be called cartesian weak maps of monads: that is, cartesian monad functors—or equivalently opfunctors—whose natural transformation part is an isomorphism. Our two functors agree, up to isomorphism, on these 1-cells.

For the third construction, take a 1-cell in CartMnd^{⊣} as shown:

\begin{matrix}(E, T) \\ (E′, T′) & [figure: (P, ϕ); ⊣; (Q, ψ)] \end{matrix}

Let \overline{P} and \overline{Q} be the induced functors just described. Then there naturally arises an adjunction

(E, T)-Multicat

(E′, T′)-Multicat. [figure: \overline{P}; ⊣; \overline{Q}]

This construction gives a weak functor from CartMnd^{⊣} to a suitable 2-category of categories and adjunctions.

As an application of this third construction, take any cartesian (E, T). Then there is a 1-cell

\begin{matrix}(E^{T} , id) \\ (E, T) & [figure: (F, ν); ⊣; (U, ε)] \end{matrix}  (3)

in CartMnd^{⊣}, in which F and U are the free and forgetful T -algebra functors, and ν and ε are certain canonical natural transformations which the reader may easily identify. Applying the construction gives exactly the adjunction

(E, T)-Struc

(E, T)-Multicat [figure: ⊣]

of 3.1.

Let us now look at change of base for structured categories. Let (E, T) and (E′, T′) be cartesian, and let

(Q, ψ) : (E, T) \overline{}(E′, T′)

be a cartesian monad functor. This induces a pullback-preserving functor \overline{Q} : E^{T} \overline{}E^{′T′}. In turn, this induces a functor from the internal categories in E^{T} to those in E^{′T′},

\overline{Q} : (E, T)-Struc \overline{}(E′, T′)-Struc.

(The same induced functor results if instead of thinking in terms of internal categories, we think of the monad functor or opfunctor

(\overline{Q}, 1) : (E^{T} , id) \overline{}(E^{′T′}, id)  (4)

and use change of base for multicategories. This point of view will be useful later on.)

Note that this is compatible with the construction of a T -structured category from a T -algebra (the functor D on page 110), in the sense that the square

E^{T}  \overline{\overline{Q}  ^{}}E^{′T′}

[figure: T -Struc; D; ∩; \overline{Q}; T′-Struc; D; ∩]

commutes. Moreover, change of base for multicategories extends change of base for structured categories, in the sense that the square

T -Struc  \overline{\overline{Q} ^{}}T′-Struc

[figure: T -Multicat; \overline{U}; \overline{Q}; T′-Multicat; \overline{U}]

commutes up to canonical isomorphism. Here both \overline{U}’s are the functors denoted U in 3.1, and (Q, ψ) is a cartesian monad functor (as above). To see that the square commutes, take the monad functor (\overline{Q}, 1) of (4) above, and consider the square of monad functors

[figure: (E^{T} , id); (\overline{Q}, 1); (E^{′T′}, id); (E, T); (U, ε); (Q, ψ); (E′, T′).; (U, ε)]

This square commutes, so by (weak) functoriality the previous square commutes up to isomorphism.

One might expect a dual to all this, involving monad opfunctors and Kleisli categories. I do not know what this might be.

3.3. Free multicategories. Just as one can form the free category on a directed graph, one can form the free (E, T)-multicategory on an (E, T)-graph, assuming that E and T are suitably pleasant. In Appendix B we define what it means for (E, T) to be suitable (which is stronger than being cartesian), and prove the following result:

3.3.1. Theorem. Let (E, T) be suitable. Then the forgetful functor

(E, T)-Multicat \overline{}E′ = (E, T)-Graph

has a left adjoint, the adjunction is monadic, and if T′ is the resulting monad on E′ then (E′, T′) is suitable.

When one takes the free category on an ordinary directed graph, the collection of objects (vertices) is unchanged, and the corresponding fact for multicategories is expressed in a variant of the theorem. If S is an object of E then we write (E, T)-Multicat_{S} for the subcategory of (E, T)-Multicat whose objects C have C_{0} = S, and whose morphisms f have f_{0} = 1_{S}; similarly, we write E′_{S} for the category of (E, T)-graphs on S (see 2.2.5(a)).

3.3.2. Theorem. Let (E, T) be suitable and let S ∈ E. Then the forgetful functor

(E, T)-Multicat_{S} \overline{}E′_{S}

has a left adjoint, the adjunction is monadic, and if T′_{S} is the resulting monad on E′_{S} then (E′_{S}, T′_{S}) is suitable. Moreover, if E has filtered colimits and T preserves them, then the same is true of E′_{S} and T′_{S}.

Most of the time we will only need the weaker conclusions that (E′, T′) and (E′_{S}, T′_{S}) are cartesian (rather than suitable); the full recursive power of the two theorems is only brought into play in a couple of passing comments (pages 123 and 136). A point not mentioned elsewhere is that repeated application of Theorem 3.3.2 gives an instant definition of a sequence of sets (S_{n})_{n∈ℕ} looking very much like the n-dimensional opetopes or multitopes. See [Lei3, Ch. IV] or [Lei1, 4.1] for this construction, and [BD], [HMP],

[Che1] and [Che2] for background.

Our two theorems so far are useless without some instances of suitable (E, T)’s:

3.3.3. Theorem. Let E be a category equivalent to a functor category [𝔼, Set], where 𝔼 is small, and let T be a finitary cartesian monad on E. Then (E, T) is suitable.

Almost all of the specific examples of E in this paper are of the form [𝔼, Set], and all of the monads T are finitary.

The proofs of all three theorems are confined to the appendix. To give the rough idea, here is a description of the free plain multicategory construction. Let ( )^{∗} denote the free monoid functor on Set, and let

X_{0}^{∗} \underline{}X_{1} \overline{}X_{0}

be a ( )^{∗}-graph. This, then, is a set X_{0} together with a set X(x_{1}, …, x_{n}; x) for each x_{1}, …, x_{n}, x ∈ X_{0}. The free plain multicategory F (X) on X has graph

X_{0}^{∗} \underline{}A \overline{}X_{0}

where A is defined recursively as follows:

• if x ∈ X_{0} then A(x; x) has an element I_{x}

• if θ ∈ X(x_{1}, …, x_{n}; x) and

α_{1} ∈ A(x_{1}^{1}, …, x_{1}^{k_{1}}; x_{1}), …, α_{n} ∈ A(x_{n}^{1}, …, x_{n}^{k_{n}}; x_{n})

then A(x_{1}^{1}, …, x_{n}^{k_{n}}; x) has an element θ⟨α_{1}, …, α_{n}⟩.

Here I_{x} and θ⟨α_{1}, …, α_{n}⟩ are ‘formal symbols’, and identities and composition in F (X) are defined in ways suggested by these symbols.

What this means is that an arrow in F (X) is a tree of arrows in X. So for instance, if θ_{1}, θ_{2}, θ_{3}, θ_{4} are arrows in X with appropriately-matching domains and codomains, then

θ_{1}⟨θ_{2}⟨I_{x}, θ_{3}⟩, I_{y}, θ_{4}⟩

is an arrow in F (X). Similarly, if θ : x_{1}, …, x_{n} \overline{}x is any arrow in X then A has an element

θ⟨I_{x_{1}}, …, I_{x_{n}}⟩.

This provides the map X_{1} \overline{}A that determines the unit of the adjunction at X. It also explains why we did not specify that any element of X was an element of A in the recursive definition—this comes about automatically.

As a special case, if X is the terminal ( )^{∗}-graph (that is, the terminal object of Set/ℕ) then F (X) is the operad tr of (unlabelled) trees, as described in A.1. For more on trees see Example 2.1.3(g), where labels get attached to leaves rather than internal nodes.

3.4. Algebras via fibrations. It is well-known that for a small category C, the functor category [C, Set] is equivalent to the category of discrete opfibrations over C. In this subsection we extend the notion of discrete opfibration from categories to general T -multicategories, and show that the category of discrete opfibrations over a given T - multicategory is equivalent to its category of algebras.

By definition, a functor g : D \overline{}C between ordinary categories is a discrete opfibration if and only if, for any object b of D and arrow g(b) ^{^{θ}} a in C, there is a unique arrow b ^{^{χ}} b′ in D such that g(χ) = θ. Another way of saying this is that in the diagram

D_{1}
[figure: d; c]
D_{0}  D_{0}
C_{1} g_{1}_{}
[figure: d; c]
[figure: C_{0}; g_{0}; C_{0}; g_{0}]

depicting g, the left-hand ‘square’ is a pullback.

Generalizing to all cartesian (E, T)’s, let us say that a map D ^{^{g}} C of T -multicategories is a discrete opfibration if the square

[figure: T D_{0}; d; D_{1}; T C_{0}; T g_{0}; d; C_{1}; g_{1}]

is a pullback. We obtain, for any T -multicategory C, the category DOpfib(C) of discrete opfibrations over C, in which an object is a discrete opfibration with codomain C and an arrow from (D ^{^{g}} C) to (D′ ^{g′} C) is a T -multicategory map D ^{^{f}} D′ such that g′^{∘}f = g. (This f is automatically a discrete opfibration too, by a standard lemma on pasting of pullback squares.)

Notice, incidentally, that being a discrete opfibration is really a property of maps between T -graphs rather than T -multicategories. In this sense, the notion of a discrete opfibration between categories exists at a more primitive level than the full notion of opfibration.

3.4.1. Theorem. Let (E, T) be cartesian and let C be a T -multicategory. Then there is an equivalence of categories

DOpfib(C) ≃ Alg(C).

A more precise statement is that the forgetful functor from DOpfib(C) to E/C_{0} (sending g to g_{0}) is monadic, and that the induced monad is isomorphic to T_{C}.

Proof. Recall from 2.3.1 that a C-algebra is an algebra for the monad T_{C} on E/C_{0}. The effect of T_{C} on an object (X ^{^{p}} C_{0}) of E/C_{0} is given by the pullback diagram

X′ [figure]
[figure: ϕ_{X}; π_{X}]
T X  C_{1}
[figure: T p; d; c]
T C_{0}  C_{0}

and the formula T_{C}(X ^{^{p}} C_{0}) = (X′ ^{cπ_{X}} C_{0}). So a C-algebra consists of (X ^{^{p}} C_{0}) together with a map h : X′ \overline{}X satisfying axioms.

Given a C-algebra (X ^{^{p}} C_{0}, h), then, we get a commutative diagram

X′
[figure: ϕ_{X}; h]
T X  X
C_{1} π_{X}_{}
[figure: d; c]
[figure: T C_{0}; T p; C_{0}.; p]

The top part of this diagram defines a T -graph D, and there is a map g : D \overline{}C defined by g_{0} = p and g_{1} = π_{X}. With some calculation we see that D is naturally a T -multicategory and g a map of T -multicategories. (Composition in D is defined using composition in C, and similarly identities. In the case (E, T) = (Set, id), we are dealing with the familiar Grothendieck opfibration.) Moreover, the left-hand half of the diagram is a pullback, so we have constructed from the C-algebra a discrete opfibration over C.

We thus arrive at a functor from Alg(C) to DOpfib(C), which is easily checked to be full, faithful and essentially surjective on objects.

Let us take a closer look at the T -multicategory D corresponding to a C-algebra h = (X ^{^{p}} C_{0}, h). We could call D the multicategory of elements or the Grothendieck opfibration of h; for reasons soon to be apparent, I will write D = C/h.

A natural question to ask is: given a multicategory C and an algebra h for C, what are the algebras for C/h? To answer it we recall the process of slicing a monad by an algebra, as in Example 2.3.3(h): for any monad S on a category D and any S-algebra k, there is a monad S/k on D with the property that

Alg(S/k) ≅ Alg(S)/k.

(Here and below, Alg means the category of algebras for either a monad or a multicategory. So for instance, Alg(C) = Alg(T_{C}).)

The following two results answer the question. Both proofs are easy.

3.4.2. Proposition. Let (E, T) be cartesian, let C be a T -multicategory, and let h be a C-algebra. Then there is an isomorphism of monads T_{C/h} ≅ T_{C}/h.

3.4.3. Corollary. In the situation of the proposition, there is an isomorphism of categories Alg(C/h) ≅ Alg(C)/h.

The corollary generalizes the familiar fact that when C is a category and C/h is the category of elements of a functor h : C \overline{}Set,

[C/h, Set] ≅ [C, Set]/h.

In addition to the corollary, we have:

3.4.4. Proposition. Let (E, T) be cartesian, let C be a T -multicategory, and let h be a C-algebra. Then there is an isomorphism of categories

DOpfib(C/h) ≅ DOpfib(C)/h.

Proof. This follows from standard results on the pasting of pullback squares.

It is very nearly possible to deduce either one of 3.4.3 or 3.4.4 from the other. The only obstacle is that both results assert the isomorphism of a pair of categories, whereas Alg(D) and DOpfib(D) are only equivalent, for T -multicategories D.

As an example, let C be the terminal T -multicategory 1. We have T_{1} ≅ T and so Alg(1) ≅ Alg(T) (Example 2.3.3(g)). Given a T -algebra h, we therefore obtain a T - multicategory 1/h; plausibly enough, this is the T -multicategory of Example 2.2.6(j), with graph

T X ^{1} T X ^{^{h}} X.

The results above tell us that T_{1/h} ≅ T/h and Alg(1/h) ≅ Alg(T)/h, as we also saw in Example 2.3.3(h).

As another application, let us construct the slice multicategory C^{+} of a T -multicategory C, which will have the property that

Alg(C^{+}) ≃ T -Multicat/C.

In detail, let (E, T) be suitable, let E′ = T -Graph, and let T′ be the free T -multicategory monad, as in 3.3. Then C is an algebra for the terminal T′-multicategory 1 (that is, a T′-algebra), so

Alg(1/C) ≅ Alg(T′)/C ≃ T -Multicat/C.

We therefore define C^{+} = 1/C, and this has the required property. Notice that we have moved up a level: whereas C was a T -multicategory, C^{+} is a T′-multicategory.

The slice multicategory construction was first proposed by Baez and Dolan for their definition [BD] of weak n-category, where it plays a central part. Their construction takes place in a different and more specialized context than ours, but there is an evident similarity between the two. See also [Che1] and [Che2] for an elucidation of Baez-Dolan slicing, and [Lei3, IV.4] for further thoughts on our version.

3.5. Algebras via endomorphisms. The prototypical example of a plain operad arises from substitution. That is, if X is a set then there is a plain operad End(X) with

(End(X))(n) = Set(X^{n}, X),

with the identity element of (End(X))(1) provided by the identity function on X, and with composition in the operad defined by

θ^{∘}(θ_{1}, …, θ_{n}) = θ^{∘}(θ_{1} × ⋯ × θ_{n}).

For any plain operad C and set X, there is a one-to-one correspondence between Calgebra structures on X and operad maps C \overline{}End(X). Indeed, this is often used to define what an algebra for an operad is: for instance, in many accounts of the classical theory of operads, and in Batanin’s account [Bat] of his globular operads. (In the classical case a symmetric group action is usually involved too, but we ignore this elaboration.) In this short subsection we show that for a large class of cartesian (E, T), this alternative definition of algebra is also possible.

As motivation, let’s consider what the appropriate definition of End is for plain multicategories. An algebra for a plain multicategory C consists of a family (X(a))_{a∈C_{0}} of sets together with a function

C(a_{1}, …, a_{n}; a) × X(a_{1}) × ⋯ × X(a_{n}) \overline{}X(a)

for each a_{1}, …, a_{n}, a ∈ C_{0}, satisfying certain axioms. In other words, a C-algebra consists of an object X \overline{}C_{0} of Set/C_{0} together with a function

C(a_{1}, …, a_{n}; a) \overline{}Set(X(a_{1}) × ⋯ × X(a_{n}), X(a))

for each a_{1}, …, a_{n}, a, again satisfying axioms. With some work we see that given any object X ^{^{p}} C_{0} of Set/C_{0}, there is a plain multicategory End(X) with object-set C_{0}, with hom-sets

(End(X))(a_{1}, …, a_{n}; a) = Set(X(a_{1}) × ⋯ × X(a_{n}), X(a)),  (5)

and with composition and identities given by substitution and identities of functions; we also see that a C-algebra structure on X is exactly a multicategory map C \overline{}End(X) which is the identity on objects.

Analysing this further, let T be the free monoid functor and, given X ^{^{p}} C_{0}, consider the following two T -graphs on C_{0}:

[figure: T X × C_{0}; pr_{1}; pr_{2}; T X; T p; T C_{0}  C_{0}; T C_{0} × X; pr_{1}; pr_{2}; X; p; T C_{0}  C_{0}.]

Call these graphs G_{1}(X) and G_{2}(X) respectively. In G_{1}(X), the set of arrows (that is, elements of T X × C_{0}) with domain (a_{1}, …, a_{n}) and codomain a is X(a_{1}) × ⋯ × X(a_{n}); in G_{2}(X), the set of arrows with this domain and codomain is X(a). Let [ , ] denote exponential in the category Set/(T C_{0} × C_{0}) of T -graphs on C_{0}. Then in the T - graph [G_{1}(X), G_{2}(X)], the set of arrows with the aforementioned domain and codomain is the right-hand side of (5). Hence [G_{1}(X), G_{2}(X)] is the underlying T -graph of the endomorphism multicategory End(X) described above.

It is now easy to move to the general case. Let (E, T) be cartesian, and suppose that each slice E/Z of E is cartesian closed. (This happens if E ≃ [𝔼, Set] for some small category 𝔼, as in almost all of our examples.) Let S ∈ E and let X ^{^{p}} S be an object of E/S. Define T -graphs G_{1}(X) and G_{2}(X) on S by the same diagrams as above, replacing C_{0} by S throughout, and define a T -graph

End(X) = [G_{1}(X), G_{2}(X)],

where [ , ] is exponential in the category E/(T S × S) of T -graphs on S. Then End(X) carries a natural T -multicategory structure, as may be verified. Moreover, if C is any T -multicategory with C_{0} = S then T -algebra structures on X correspond one-to-one with those T -multicategory maps C ^{^{h}} End(X) which are the identity on objects (that is, h_{0} = 1, in the terminology of 2.2.4). Put another way, an algebra for C is an object X over C_{0} together with a map C \overline{}End(X) of multicategories on C_{0}.

To discuss maps between C-algebras (for a fixed T -multicategory C) we define

Hom(X, Y) = [G_{1}(X), G_{2}(Y)]

for T -graphs X and Y on S = C_{0}. Since both G_{1} and G_{2} are functors, so too is Hom. If (X, h) and (Y, k) are C-algebras, then an algebra map (X, h) \overline{}(Y, k) is exactly a map X ^{^{f}} Y in E/C_{0} such that the diagram

C  \overline{h ^{}}Hom(X, X)

[figure: Hom(Y, Y); k; Hom(f, 1); Hom(X, Y); Hom(1, f)]

commutes. Put formally, we have just given an alternative definition of the category of algebras for a T -multicategory C, and this alternative category is isomorphic to the official category Alg(C).

3.6. fc-multicategories. In this subsection we take a close look at T -multicategories in the case where T is the free category monad, fc, on the category of directed graphs, (Set, id)-Graph. This case is interesting for a variety of reasons. First of all, it arises naturally as soon as one thinks about categories and the fact that Cat is monadic over (Set, id)-Graph. It is therefore the first step in an infinite hierarchy: that is, if we define

(E^{(0)}, T^{(0)}) = (Set, id),
E^{(n+1)} = T^{(n)}-Graph,
T^{(n+1)} = free T^{(n)}-multicategory

then a T^{(1)}-multicategory is an fc-multicategory. (The validity of these definitions is guaranteed by Theorems 3.3.1 and 3.3.3; in particular, they say that the monad fc is cartesian.) We will only consider this first step here; more can be found in [Lei5, 3.4].

Secondly, fc-multicategories encompass many familiar ‘two-dimensional’ categorical structures, including bicategories, double categories, monoidal categories and plain multicategories. They also include structures we will call weak double categories, in which composition of horizontal 1-cells only obeys associativity and unit laws up to coherent isomorphism, and include structures resembling the 2-opetopic sets of Baez and Dolan.

Thirdly, there are a couple of well-known categorical ideas for which fc-multicategories provide a more general context than is traditional: the bimodules construction (usually performed on bicategories), and the enrichment of categories (usually done in monoidal categories, or occasionally bicategories). These subjects are treated in, respectively, 3.7 and 3.8.

Let us begin by finding out what an fc-multicategory is in explicit terms. An fc-graph V is a diagram

[figure: V_{1} = (V_{11}; V_{10})]
[figure]
[figure: fc(V_{0}) = (V_{01}^{∗}; V_{00}); V_{0} = (V_{01}; V_{00}),]

where V_{1} and V_{0} are directed graphs, the V_{ij} are sets, V_{01}^{∗} is the set of paths in V_{0}, the horizontal arrows are set maps, and the diagonal arrows are maps of directed graphs. Think of elements of V_{00} as objects or 0-cells, elements of V_{01} as horizontal 1-cells, elements of V_{10} as vertical 1-cells, and elements of V_{11} as 2-cells, as in the picture

[figure: x_{0}; m_{1}; x_{1}; m_{2}; ⋯; m_{n}; x_{n}; ⇓ θ; x; f; m; x′; f′]  (6)

(n ≥ 0, x_{i}, x, x′ ∈ V_{00}, m_{i}, m ∈ V_{01}, f, f′ ∈ V_{10}, θ ∈ V_{11}). An fc-multicategory structure on the fc-graph V firstly makes

(V_{00} \underline{}V_{10} \overline{}V_{00}),

the objects and vertical 1-cells, into a category. It also gives a composition function for 2-cells,

[figure: •; m_{1}^{1}; ⋯; m_{1}^{k_{1}}; •; m_{2}^{1}; ⋯; m_{2}^{k_{2}}; •; ⋯; •; m_{n}^{1}; ⋯; m_{n}^{k_{n}}; •; ⇓ θ_{1}  ⇓ θ_{2}  ⋯  ⇓ θ_{n}; •; f_{0}; m_{1}; •; m_{2}; •; ⋯; •; m_{n}; •; f_{n}; ⇓ θ; •; f; m; •; f′]  (7)

⟼

[figure: •; m_{1}^{1}; ⋯; m_{n}^{k_{n}}; •]
⇓ θ^{∘}(θ_{1}, θ_{2}, … θ_{n})
[figure: •; f^{∘}f_{0}; m; •; f′^{∘}f_{n}]

(n ≥ 0, k_{i} ≥ 0, with •’s representing objects), and an identity function

[figure: x; m; x′; ⟼; x; m; x′; ⇓ 1_{m}; x; 1_{x}; m; x′.; 1_{x′}]

The composition and identities obey associativity and identity laws, which ensure that any 2-cell diagram with a rectangular boundary has a well-defined composite.

The pictures in the nullary case are worth a short comment. When n = 0, the 2-cell of diagram (6) is drawn as

x_{0} = = = = = = = = = x_{0}
⇓ θ
[figure: x; f; m; x′,; f′]

and the diagram of pasted-together 2-cells in the domain of (7) is drawn as

w_{0} = = = w_{0}

=

[figure: x_{0}; f_{0}; = = =; x_{0}; f_{0}]

⇓ θ

[figure: x; f; m; x′.; f′]

The composite of this last diagram will be written as θ^{∘}f_{0}.

As such, fc-multicategories are not familiar, but various degenerate cases are. These are explained in the following examples, and summarized in Figure 3a.

Not ‘representable’ ‘Representable’  ‘Uniformly

representable’

No degeneracy fc-multicategory Weak double Double category

category

All vertical 1-cells Vertically discrete Bicategory  2-category
are identities fc-multicategory
Only one object and Plain multicategory Monoidal category Strict monoidal
one vertical 1-cell  category

Figure 3a: Some of the possible degeneracies of an fc-multicategory. The left-hand column refers to degeneracies in the category formed by the objects and vertical 1-cells. The top row refers to whether the fc-multicategory structure arises from a composition rule for horizontal 1-cells. See Examples 3.6.1.

3.6.1. Examples.

a. Any double category gives an fc-multicategory, in which a 2-cell as in (6) is a 2-cell

x_{0} m_{n}^{∘} ⋯^{∘}m_{1}_{}x_{n}
⇓
[figure: x; f; m; x′; f′]

in the double category.

b. In fact, (a) works even when the double category is ‘horizontally weak’. A typical example of such a structure—a weak double category—has rings (not necessarily commutative) as its 0-cells, bimodules as its horizontal 1-cells, ring homomorphisms as its vertical 1-cells, and ‘homomorphisms of bimodules with respect to the vertical changes of base’ as 2-cells. In other words, a 2-cell looks like

R  \overline{M ^{}}R′
⇓ θ
[figure: S; f; N; S′,; f′]

where R, R′, S, S′ are rings, M is an (R′, R)-bimodule (i.e. simultaneously a left R′- module and a right R-module) and N similarly, f and f′ are ring homomorphisms, and θ : M \overline{}N is an abelian group homomorphism such that

θ(r′ · m · r) = f′(r′) · θ(m) · f(r).

Composition of horizontal 1-cells is tensor, composition of vertical 1-cells is the usual composition of ring homomorphisms, and composition of 2-cells is defined in an evident way. The essential point is that although the 0-cells and vertical 1-cells form a category, the same cannot be said of the horizontal structure: tensor only obeys the associative and unit laws up to coherent isomorphism.

I will not write down the full definition of weak double category, since it is just an easy extension of the definition of a bicategory. It is most convenient to extend the definition of unbiased bicategory, since in order to have a 1-cell ‘m_{n}^{∘} ⋯^{∘}m_{1}’, as in the diagram of (a), we need n-fold composition.

Another example has small categories as 0-cells, profunctors (bimodules) as horizontal 1-cells, functors as vertical 1-cells, and ‘morphisms of profunctors with respect to the vertical functors’ as 2-cells. We will explore both of these examples further in 3.7.

c. Suppose that all vertical 1-cells are identities, that is, V_{10} = V_{00} and

(V_{00} \underline{}V_{10} \overline{}V_{00}) = (V_{00} ^{1} V_{00} ^{^{1}} V_{00}).

The category formed by the objects and vertical 1-cells is discrete, so we may call the fc-multicategory V vertically discrete. In this case, an alternative way of drawing the underlying fc-graph of V is as

V_{11}

[figure]
V_{01}^{∗}  V_{01}

[figure] [figure]

[figure: V_{00}; V_{00}.]

Thus a vertically discrete fc-multicategory consists of some objects x, x′, …, some 1-cells m, m′, …, and some 2-cells looking like

x_{2} …
x_{1} [figure: m_{2}]  x_{n−1}
[figure: m_{1}; ⇓ θ; m_{n}]
x_{0}  \overline{m  ^{}}x_{n},

together with a composition function

[figure: x_{0}; x_{1}; x_{n−1}; x_{n}; m; m_{1}; m_{n}; m_{1}^{1}; m_{1}^{k_{1}}; m_{n}^{1}; m_{n}^{k_{n}}; ⇓ θ; ⇒; θ_{1}; ⇐; θ_{n}; ⟼; x_{0}; x_{n}; m; m_{1}^{1}; m_{n}^{k_{n}}; ⇓ θ^{∘}(θ_{1}, …, θ_{n})]

and an identity function

[figure: x; x′; m; ⟼; x; x′; m; m; ⇓ 1_{m}]

obeying the inevitable associativity and identity laws. A vertically discrete fc-graph bears a strong resemblance to a 2-opetopic set in the sense of [BD], or a 2-truncated multitopic set in the sense of [HMP]; see also [Che1], [Che2] and [Lei3, Ch. IV].

d. Any bicategory gives rise to a vertically discrete fc-multicategory, in which a 2-cell as at (6) is a 2-cell

x_{0}[figure: m_{n}^{∘} ⋯^{∘}m_{1}; m]x_{n}

in the bicategory (with x_{0} = x and x_{n} = x′). This is a special case of (b).

e. Any monoidal category M gives an fc-multicategory in which there is one object and one vertical 1-cell, and a 2-cell

\begin{aligned}• & \overline{m_{1}} & • & \overline{m_{2}} & • & ⋯ & • & \overline{m_{n}} & • \\ & & & & ⇓ \\ • & 1 & \overline{m} & • & 1 \end{aligned}  (8)

is a morphism m_{n} ⊗ ⋯ ⊗ m_{1} \overline{}m in M. This, in turn, is a special case of (d).

f. Similarly, any plain multicategory M gives an fc-multicategory: there is one object, one vertical 1-cell, and a 2-cell (8) is a map

m_{1}, …, m_{n} \overline{}m

in M. In fact, a plain multicategory is exactly an fc-multicategory in which the category formed by the objects and vertical 1-cells is 1, the terminal category.

g. Let (E, T) be cartesian, and define an fc-multicategory V as follows. The objects are the objects of E, and the horizontal 1-cells are the same as the 1-cells of the bicategory Span(E, T) defined in 2.2.1. A vertical 1-cell is a morphism in E, and a 2-cell

[figure: X_{0}; M_{1}; X_{1}; M_{2}; ⋯; M_{n}; X_{n}]
⇓
[figure: X; f; M; X′; f′]

is a function θ making

M_{n}^{∘} ⋯^{∘}M_{1}
[figure]
T X_{0}  X_{n}
Mθ_{}
[figure]
[figure: T X; T f; X′; f′]

commute, where M_{n}^{∘} ⋯^{∘}M_{1} is the composite in Span(E, T). Composition and identities in V are defined in the obvious way. (This is actually not just an fcmulticategory, but a weak double category. Strictly speaking, E should be small; but having given an elementary description of what an fc-multicategory is, I will feel free to ignore this restriction.)

Given any fc-multicategory, we obtain a vertically discrete fc-multicategory simply by discarding all non-identity vertical 1-cells. Applying this process to V gives the same vertically discrete fc-multicategory as arises from the bicategory Span(E, T) by the method of (d). For this reason we also write Span(E, T) for the fc-multicategory V. In the next subsection we will see that it is useful—and perhaps more natural—to regard Span(E, T) as an fc-multicategory rather than a bicategory.

So far all of our examples of fc-multicategories have been degenerate in some way: either weak double categories or vertically discrete. The next subsection provides some non-degenerate examples.

3.7. The bimodules construction. Bimodules have traditionally been discussed in the context of bicategories. Thus given a bicategory B, one constructs a new bicategory Bim(B) whose 1-cells are bimodules in B (see [CKW] or [Kos]). The drawback is that this is only possible when B has certain properties concerning the existence and behaviour of local reflexive coequalizers.

Here we extend the Bim construction from bicategories to fc-multicategories, which allows us to drop the technical assumptions. In other words, we will construct an honest functor

Bim : fc-Multicat \overline{}fc-Multicat.

This provides lots of new examples of fc-multicategories.

I would like to be able to, but at present cannot, place the Bim construction in a more abstract setting: as it stands it is somewhat ad hoc. Possibly there is some connection with the contractions of Section 4.

Let V be an fc-multicategory. The fc-multicategory Bim(V) is defined as follows.

0-cells A 0-cell of Bim(V) is a multicategory map 1 \overline{}V. That is, it is a 0-cell x of V together with a horizontal 1-cell x ^{^{t}} x and 2-cells

[figure: x; t; x; t; x; ⇓ μ; x; 1; t; x; 1; x = = = = = = = = = x; ⇓ η; x; 1; t; x; 1]

satisfying the usual axioms for a monad, μ^{∘}(μ, 1_{t}) = μ^{∘}(1_{t}, μ) and μ^{∘}(η, 1_{t}) = 1_{t} = μ^{∘}(1_{t}, η).

Horizontal 1-cells A horizontal 1-cell (x, t, η, μ) ^{}(x′, t′, η′, μ′) consists of a horizontal 1-cell x ^{m} x′ in V together with 2-cells

[figure: x; t; x; m; x′; ⇓ θ; x; 1; m; x′; 1; x; m; x′; t′; x′; ⇓ θ′; x; 1; m; x′; 1]

satisfying the usual module axioms θ^{∘}(η, 1_{m}) = 1_{m}, θ^{∘}(μ, 1_{m}) = θ^{∘}(1_{t}, θ), and dually for θ′, and the ‘commuting actions’ axiom θ′^{∘}(θ, 1_{t′}) = θ^{∘}(1_{t}, θ′).

Vertical 1-cells A vertical 1-cell

\begin{matrix}(x, t, η, μ) \\ (x̂, t̂, η̂, μ̂) & \end{matrix}

in Bim(V) is a vertical 1-cell

\begin{matrix}x \\ x̂ & f_{} \end{matrix}

in V together with a 2-cell

x  \overline{t ^{}}x
⇓ ω
[figure: x̂; f; t̂; x̂; f]

such that ω^{∘}μ = μ̂^{∘}(ω, ω) and ω^{∘}η = η̂^{∘}f. (The notation on the right-hand side of the second equation is explained on page 125.)

2-cells A 2-cell

[figure: t_{0}; m_{1}; t_{1}; m_{2}; ⋯; m_{n}; t_{n}]
⇓
[figure: t; f; m; t′; f′]

in Bim(V), where t stands for (x, t, η, μ), m for (m, θ, θ′), f for (f, ω), and so on, consists of a 2-cell

[figure: x_{0}; m_{1}; x_{1}; m_{2}; ⋯; m_{n}; x_{n}]
⇓ α
[figure: x; f; m; x′; f′]

in V, satisfying the ‘external equivariance’ axioms

α^{∘}(θ_{1}, 1_{m_{2}}, …, 1_{m_{n}}) = θ^{∘}(ω, α)
α^{∘}(1_{m_{1}}, …, 1_{m_{n−1}}, θ′_{n}) = θ′^{∘}(α, ω′)

and the ‘internal equivariance’ axioms

α^{∘}(1_{m_{1}}, …, 1_{m_{i−2}}, θ′_{i−1}, 1_{m_{i}}, 1_{m_{i+1}}, …, 1_{m_{n}}) =
α^{∘}(1_{m_{1}}, …, 1_{m_{i−2}}, 1_{m_{i−1}}, θ_{i}, 1_{m_{i+1}}, …, 1_{m_{n}})

for 2 ≤ i ≤ n.

Composition and identities For both 2-cells and vertical 1-cells in Bim(V), composition is defined directly from the composition in V, and similarly identities.

We have now defined an fc-multicategory Bim(V) for each fc-multicategory V, and it is clear how to do the same thing for maps of fc-multicategories, so that we have a functor

Bim : fc-Multicat \overline{}fc-Multicat.

We could go further and treat fc-Multicat as a 2-category (cf. the remarks at the end of Section 2). Further still, it is really more natural to regard fc-Multicat as a (large) fc-multicategory itself, as we shall see very shortly. Such extensions are left to the consideration of the reader.

3.7.1. Examples.

a. Let B be a bicategory satisfying the conditions on local reflexive coequalizers mentioned in the first paragraph of this subsection, so that it is possible to construct a bicategory Bim(B) in the traditional way. Let V be the fc-multicategory coming from B. Then a 0-cell of Bim(V) is a monad in B, a horizontal 1-cell t \overline{}t′ is a (t′, t)-bimodule, and a 2-cell of the form

[figure: t_{0}; m_{1}; t_{1}; m_{2}; ⋯; m_{n}; t_{n}]
⇓
[figure: t_{0}; 1; m; t_{n}; 1]

is a map

m_{n} ⊗_{t_{n−1}} ⋯ ⊗_{t_{1}} m_{1} \overline{}m

of (t_{n}, t_{0})-bimodules, i.e. a 2-cell in Bim(B). So if we discard the non-identity 1-cells of Bim(V) to get a vertically discrete fc-multicategory, then this is precisely the fc-multicategory associated with the bicategory Bim(B).

b. Let V be the fc-multicategory Span(Set, id), as defined in 3.6.1(g). Then Bim(V) has

objects: small categories

vertical 1-cells: functors

horizontal 1-cells: profunctors (that is, a horizontal 1-cell C \overline{}C′ is a functor C^{op} × C′ \overline{}Set)

2-cells: a 2-cell

[figure: C_{0}; M_{1}; C_{1}; M_{2}; ⋯; M_{n}; C_{n}; ⇓; C; F; M; C′; F′]  (9)

is a family of functions

M_{n}(a_{n−1}, a_{n}) × ⋯ × M_{1}(a_{0}, a_{1}) \overline{}M(F a_{0}, F′a_{n}),

one for each a_{0} ∈ C_{0}, …, a_{n} ∈ C_{n}, natural in the a_{i}’s.

The 2-cells can be described another way. Firstly, there is a profunctor M′ : C_{0} \overline{}C_{n} defined by M′(a_{0}, a_{n}) = M(F a_{0}, F′a_{n}). Secondly, we can tensor together (compose) the profunctors M_{i} to obtain the profunctor M_{n} ⊗ ⋯ ⊗ M_{1} : C_{0} \overline{}C_{n}. A 2-cell as shown above is then a morphism M_{n} ⊗ ⋯ ⊗ M_{1} \overline{}M′ of profunctors, in the usual sense.

In particular, our fc-multicategory (which could reasonably be called Cat) incorporates natural transformations. For let D and C be categories and F, F′ : D \overline{}C functors; write I_{D} and I_{C} for the identity profunctors on D and C, i.e. I_{D} = Hom_{D} and I_{C} = Hom_{C}. Then by a simple Yoneda argument, a 2-cell

[figure: D; I_{D}; D; ⇓; C; F; I_{C}; C; F′]  (10)

in Bim(Span(Set, id)) is just a natural transformation F \overline{}F′.

c. More generally, consider Bim(Span(E, T)) for any cartesian (E, T). As we would expect, an object is a T -multicategory and a vertical 1-cell is a map of T -multicategories. A horizontal 1-cell C \overline{}C′ is a profunctor or (bi)module between T -multicategories: that is, a span

T C_{0} \underline{}M \overline{}C′_{0}

together with maps (‘actions’) M^{∘}C_{1} \overline{}M and C′_{1}^{∘}M \overline{}M obeying the usual rules for a bimodule. Here and in what follows, ‘^{∘}’ indicates composition of 1-cells in the bicategory Span(E, T). A 2-cell as pictured in (9) is a map θ in E making the diagram

M_{n}^{∘} ⋯^{∘}M_{1}
[figure]
T C_{0}  C_{n}
Mθ_{}
[figure]
[figure: T C; T F; C′; F′]

commute and satisfying compatibility axioms for the actions by the C_{i}’s, C and C′.

This provides a family of examples of fc-multicategories which are not degenerate in any of the ways described in 3.6.1. In other words, Bim(Span(E, T)) does not usually form a weak double category. For recall that in order to form the tensor of ordinary profunctors (as in the previous example), one needs to use a certain coend, which is effectively a reflexive coequalizer in the category of sets. Similarly, in order to form a tensor of profunctors in the (E, T) setting we need E to possess certain reflexive coequalizers, and in order for tensor to obey (weak) associative and unit laws we need T to preserve such coequalizers. In general E and T will not have these properties. (A rather self-referential example is provided by T = fc, which does not preserve all reflexive coequalizers. This is all at a pragmatic level; I have not actually got a proven counterexample to the claim that for all cartesian (E, T), the fc-multicategory Bim(Span(E, T)) comes from a weak double category.) So, for a fixed (E, T), the natural structure formed by T -multicategories is an fcmulticategory. As for ordinary categories, this incorporates a sensible notion of natural transformation. Formally, if C is a T -multicategory then let I_{C} denote the profunctor C \overline{}C consisting of the span

T C_{0} ^{d} C_{1} ^{^{c}} C_{0}

with left and right C-actions defined by composition in C. Let D and C be T - multicategories and F, F′ : D \overline{}C maps of T -multicategories: then a transformation F \overline{}F′ is a 2-cell in Bim(Span(E, T)) as shown in diagram (10). An elementary definition of transformation is given in [Lei5, 1.1.1]. For plain multicategories, a transformation α : F \overline{}F′ consists of an arrow α_{d} : F d \overline{}F′d for each d ∈ D_{0}, such that

α_{d}^{∘}(F g) = F′g^{∘}(α_{d_{1}}, …, α_{d_{n}})

for all arrows g : d_{1}, …, d_{n} \overline{}d in D.

d. For a less taxing example, let V be the fc-multicategory coming from the monoidal category (Ab, ⊗, ℤ) (as in 3.6.1(e)). Then Bim(V) has

objects: rings

vertical 1-cells: ring homomorphisms

horizontal 1-cells R \overline{}R′: (R′, R)-bimodules

2-cells: A 2-cell

[figure: R_{0}; M_{1}; R_{1}; M_{2}; ⋯; M_{n}; R_{n}]
⇓ θ
[figure: R; f; M; R′; f′]

is a function M_{n}×⋯×M_{1} ^{^{θ}} M which preserves addition in each coordinate (is ‘multi-additive’), and satisfies

θ(r_{n} · m_{n}, m_{n−1}, …) = f′(r_{n}) · θ(m_{n}, m_{n−1}, …)
θ(m_{n} · r_{n−1}, m_{n−1}, …) = θ(m_{n}, r_{n−1} · m_{n−1}, …)

etc.

This, then, is the fc-multicategory arising from the weak double category of 3.6.1(b). As in the last example, it is only a weak double category because certain reflexive coequalizers exist and behave well in the monoidal category (Ab, ⊗, ℤ).

e. The previous example can be repeated with the monoidal category (Set, ×, 1), with obviously analogous results.

f. Let W be a 2-category. We construct from W an fc-multicategory V, different from the vertically discrete fc-multicategory of 3.6.1(d). The objects of V are the objects of W, the vertical and horizontal 1-cells of V are both just the 1-cells of W, and a 2-cell

[figure: x_{0}; g_{1}; x_{1}; g_{2}; ⋯; g_{n}; x_{n}]
⇓
[figure: x; f; g; x′; f′]

in V is a 2-cell

x_{0} [figure: g^{∘}f; f′^{∘}g_{n}^{∘} ⋯^{∘}g_{1}]x_{n}

in W. Composition and identities are defined by pasting of 2-cells in W. (Effectively we are associating a (strict) double category to W, and obtaining from that an fcmulticategory as in 3.6.1(a).)

Now consider the fc-multicategory Bim(V). The category formed by the objects and vertical 1-cells is the category of monads and monad functors in W, in the sense of 3.2 and [Str1]. A horizontal 1-cell is what might be called a (bi)module between monads. (For an application of such modules to ‘hard-nosed mathematics’— homotopy theory, in fact—see [May1, 9.4].) The description of a general 2-cell is omitted.

Dually, we can reverse direction of the 2-cells in V to obtain another fc-multicategory V′ from W, and then the objects and vertical 1-cells of Bim(V′) form the category of monads and monad opfunctors in W.

Example (c) points the way towards a truly uncompromising, but logically superior, approach to writing up the general theory of multicategories. This approach would start with an elementary definition of (possibly large) fc-multicategory, which would look like the description at the beginning of 3.6. It would continue with the definition of the fcmulticategory Span(E, T), for any cartesian (E, T), and a definition of the bimodules construction. By applying the latter to the former it would arrive at the fc-multicategory (E, T)-Multicat. A (E, T)-multicategory would be, by definition, an object of this fcmulticategory, and similarly maps, modules, etc. So in this approach, it would not be necessary to treat Span(E, T) as a bicategory at all.

The ‘change of base’ discussed in 3.2 can also be explained using the bimodules construction. Given cartesian (E, T) and (E′, T′), a cartesian monad functor from (E, T) to (E′, T′) gives rise to a map

Span(E, T) \overline{}Span(E′, T′)

of fc-multicategories. (This is a direct and explicit construction, of which no further explanation is offered.) The same is true for a cartesian monad opfunctor, using a different construction. Applying Bim then gives an fc-multicategory map

(E, T)-Multicat \overline{}(E′, T′)-Multicat.

So a cartesian monad (op)functor tells us not just how to turn a T -multicategory into a T′-multicategory, and a functor between T -multicategories into a functor between T′- multicategories (as in 3.2), but also works on profunctors, transformations, and the general 2-cells described in Example (c).

3.8. Enrichment. There is a quite surprising theory of enrichment for general multicategories. In this subsection I will give a short outline of the shape of the theory, referring the reader to [Lei5] for a more full account.

The main surprise is what one enriches in. Given a category E and a monad T on E, which are ‘suitable’ in the sense of 3.3, define

E′ = (E, T)-Graph,
T′ = free (E, T)-multicategory.

Fix a T′-multicategory V (which makes sense as (E, T) is suitable). Then we will talk about ‘T -multicategories enriched in V ’. In other words, we enrich T -multicategories in T′-multicategories. This means that we can take, for instance, the hierarchy (E^{(n)}, T^{(n)}) of monads defined at the beginning of 3.6, and consider T^{(n)}-multicategories enriched in T^{(n+1)}-multicategories; thus a structure of one type gets enriched in a structure of a more complicated type.

(In general there appears to be no such thing as the ‘underlying’ T -multicategory of a V -enriched T -multicategory, in contrast with the familiar situation for categories enriched in a monoidal category.)

The definition itself is very simple. Given an object C_{0} of E, we can form I(C_{0}) (with I for indiscrete), the unique T -multicategory with graph

T C_{0} ^{pr_{1}} T C_{0} × C_{0} ^{pr_{2}} C_{0}.

Then I(C_{0}) is a T′-algebra, say h : T′(I(C_{0})) \overline{}I(C_{0}). By Example 2.2.6(j), we get from this MI(C_{0}), the unique T′-multicategory with graph

T′(I(C_{0})) ^{1} T′(I(C_{0})) ^{^{h}} I(C_{0}).

For a T′-multicategory V, a V -enriched T -multicategory is an object C_{0} of E together with a map MI(C_{0}) \overline{}V of T′-multicategories. Maps between V -enriched T -multicategories are also defined in a simple way (see [Lei5]), thus giving a category.

The simplest case is (E, T) = (Set, id). Then E′ is the category of directed graphs, T′ = fc, and we have a theory of categories enriched in an fc-multicategory. This extends the usual theory of categories enriched in a monoidal category, as well as the less popular theory of categories enriched in a bicategory ([BCSW], [CKW], [Wal]) and the evident but hardly-written-up theory of categories enriched in a plain multicategory. Categories enriched in an fc-multicategory are examined in each of [Lei4], [Lei5] and [Lei6].

The theory of bimodules interacts with the theory of enrichment in an fc-multicategory in the following way. Write V -Cat for the category of categories enriched in an fcmulticategory V. We then have some facts:

a. given a map V_{1} \overline{}V_{2} of fc-multicategories, there is an induced functor V_{1}-Cat \overline{}V_{2}-Cat

b. there is a forgetful map Bim(V) \overline{}V, for any V

c. the forgetful map Bim(MI(C_{0})) \overline{}MI(C_{0}) is an isomorphism for any set C_{0} (which takes a little thought)

d. by (c), a V -enriched category (MI(C_{0}) ^{^{γ}} V) gives rise to a Bim(V)-enriched

category

MI(C_{0}) ^{∼} Bim(MI(C_{0})) ^{Bim(γ)} Bim(V)

e. the same goes for maps, so there is a functor

V -Cat \overline{}Bim(V)-Cat.

(As it happens, this functor is right adjoint to the functor induced by the forgetful map of (b).)

For instance, a category C enriched in the monoidal category Ab gives rise to a category enriched in the fc-multicategory Bim(Ab) of 3.7.1(d). In concrete terms, this works because the abelian group C(a, a) is naturally a ring, and the abelian group C(a, b) is naturally a left C(b, b)-module and a right C(a, a)-module, for any a, b ∈ C_{0}. Further explanation is in [Lei5] and [Lei4].

This piece of theory again illustrates the advantages of working with fc-multicategories instead of bicategories. Let B be a bicategory satisfying the usual conditions on local reflexive coequalizers, so that there is a bicategory Bim(B). Then, just as above, any Benriched category gives rise to a Bim(B)-enriched category. However, this construction is not functorial: a map between B-enriched categories does not give rise to a map between the associated Bim(B)-enriched categories. Essentially, the problem is that the definition of a map between C-enriched categories (for a bicategory C, which in this case is Bim(B)) is too restrictive; and in turn, this restrictive definition is forced because bicategories do not have any vertical 1-cells. Once again, the reader is referred elsewhere for elucidation of cryptic remarks: see [Lei5] or [Lei6].

The second-most simple case of enrichment for general multicategories is when E = Set and T is the free monoid monad. This has an interesting application, concerning the structures called ‘pseudo-monoidal categories’ by Soibelman and ‘relaxed multicategories’ by Borcherds. (See [Soi] and [Borh], and [Sny1] and [Sny2] for further explanation. Borcherds actually used relaxed multilinear categories, where the hom-sets are not just sets but vector spaces.) In [Lei5, Ch. 4] it is shown that, for a certain naturally-arising T′-multicategory V, relaxed multicategories are exactly plain multicategories enriched in V.

4. A definition of weak ω-category

In this section we present a definition of weak ω-category, a variation on that given by Batanin in [Bat]. We start (4.1) by giving the definition in purely formal terms, which can be done very quickly. However, it is the explanation of why it is a reasonable definition that occupies most of the section (4.2–4.6).

It turns out that there are (at least) two natural ways to use our definition of weak ω-category to give a definition of weak n-category. We show that these two definitions are equivalent in a strong sense (4.7). Moreover, we show (4.8) that weak 2-categories are the same as unbiased bicategories.

In order to make the definition of weak ω-category we need to rely on certain technical results, which are confined to Appendices C and D.

Our definition of weak ω-category is very close to Batanin’s, although not the same. Both definitions involve two main ideas: operads and contractions. The operads he uses are the same as the (E, T)-operads here (for the particular choice of (E, T) that we will make), and part of the purpose of this section is to explain in elementary language and pictures what these (E, T)-operads are, so that the knowledgeable reader may understand that the two kinds of operad are the same. (More precisely, our (E, T)-operads are what Batanin calls ‘ω-operads in Span’.) However, Batanin’s notion of contraction is different from the one here. The difference between the two definitions is explained further at the end of 4.5.

4.1. Formal account. Let 𝔾 be the category whose objects are the natural numbers 0, 1, …, and whose arrows are generated by

σ_{n}, τ_{n} : n \overline{}n − 1

for each n ≥ 1, subject to equations

σ_{n−1}^{∘}σ_{n} = σ_{n−1}^{∘}τ_{n}, τ_{n−1}^{∘}σ_{n} = τ_{n−1}^{∘}τ_{n}

(n ≥ 2). A functor X : 𝔾 \overline{}Set is called a globular set; I will write s instead of X(σ_{n}), and t instead of X(τ_{n}).

Any (small) strict ω-category has an underlying globular set X, in which X(n) is the set of n-cells and s and t are the source and target maps. Moreover, a strict ω-functor induces a map of underlying globular sets, so there is a forgetful functor from the category ω-Cat (of strict ω-categories and strict ω-functors) to the category [𝔾, Set] of globular sets. In Appendix C we put this into exact terms and establish:

4.1.1. Proposition. The forgetful functor ω-Cat \overline{}[𝔾, Set] has a left adjoint, and the induced monad (T, η, μ) on [𝔾, Set] is cartesian.

This proposition means that it makes sense to talk about T -operads. Let C be a T - operad. The underlying T -graph of C is a diagram (C ^{^{d}} T 1) in [𝔾, Set]; if ν ∈ (T 1)(n), write

C(ν) = {θ ∈ C(n) | d(θ) = ν}.

For n ≥ 2 and π ∈ (T 1)(n), define

P_{π}(C) = {(θ_{0}, θ_{1}) ∈ C(s(π)) × C(t(π)) | s(θ_{0}) = s(θ_{1}) and t(θ_{0}) = t(θ_{1})},

and for π ∈ (T 1)(1), define

P_{π}(C) = C(s(π)) × C(t(π)).

A contraction κ on C is a family of functions

(κ_{π} : P_{π}(C) \overline{}C(π))_{n≥1,π∈(T 1)(n)},

satisfying

s(κ_{π}(θ_{0}, θ_{1})) = θ_{0}, t(κ_{π}(θ_{0}, θ_{1})) = θ_{1}

for every n ≥ 1, π ∈ (T 1)(n) and (θ_{0}, θ_{1}) ∈ P_{π}(C).

An operad-with-contraction is a pair (C, κ) in which C is a T -operad and κ is a contraction on C. Let OWC be the category whose objects are operads-with-contraction, and in which a map (C, κ) \overline{}(C′, κ′) is a map F : C \overline{}C′ of T -operads such that for all n ≥ 1, π ∈ (T 1)(n) and (θ_{0}, θ_{1}) ∈ P_{π}(C),

F (κ_{π}(θ_{0}, θ_{1})) = κ′_{π}(F (θ_{0}), F (θ_{1})).

(It is easy to verify that the right-hand side makes sense, i.e. that (F (θ_{0}), F (θ_{1})) ∈ P_{π}(C′).) In Appendix D we prove the following:

4.1.2. Proposition. OWC has an initial object.

Write (L, λ) for the initial object. This determines the T -operad L up to isomorphism; and since the algebras construction is functorial, the category Alg(L) is determined up to isomorphism.

4.1.3. Definition. A weak ω-category is an L-algebra.

It is not meant to be obvious why this is a reasonable definition of weak ω-category, and the next few subsections are devoted to an explanation.

4.2. Pasting diagrams. Before understanding weak ω-categories, we must first understand strict ones, and in particular we need to know about the free strict ω-category monad on the category of globular sets. In Appendix C we prove the existence and relevant properties of this monad, and that the category of strict ω-categories is monadic over the category of globular sets. Here we give pictorial descriptions.

First let us contemplate the globular set T (1), where

1 = (⋯ [figure] 1 [figure] ⋯ [figure] 1)

is the terminal globular set. The free strict ω-category functor takes a globular set X and creates formally all possible composites in it, to make T X. Thus a typical element of (T 1)(2) looks like

•  [figure]^{•}  \overline{}^{•}  [figure] ^{•} ,  (11)

where each k-cell drawn represents the unique member of 1(k). Note that because of identities (which we think of throughout as nullary composites), this diagram might be thought of as representing an element of (T 1)(n) for any given n ≥ 2. Let us call an element of (T 1)(n) (or the picture representing it) an n-pasting diagram, and define pd = T 1. (The sets pd(m) and pd(n) are considered disjoint, when m ≠ n.) This 2pasting diagram (11) has a source and a target, both of which are the 1-pasting diagram

•  \overline{}^{•}  \overline{}^{•}  \overline{}^{•} .

Since all cells in 1 have the same source and target—are ‘endomorphisms’—it is inevitable that the same should be true in T 1 = pd.

It is not hard to give a concrete description of the globular set pd. Write ( )^{∗} for the free monoid functor on Set: then pd(0) = 1 and pd(n + 1) = pd(n)^{∗}. In other words, an (n + 1)-pasting diagram is a sequence of n-pasting diagrams. For example, the 2-pasting diagram depicted in (11) is the sequence

( ^{•}  \overline{}^{•}  \overline{}^{•}  \overline{}^{•} , ^{•} , ^{•}  \overline{}^{•} )

of 1-pasting diagrams, so if pd(0) = {•} then (11) is the double sequence

((•, •, •), (), (•)) ∈ pd(2).

The source and target maps s, t : pd(n + 1) \overline{}pd(n) are equal, and we will write both as ∂ (‘boundary’); ∂ is defined inductively by

(pd(n + 1) ^{^{∂}} pd(n)) = (pd(n) ^{^{∂}} pd(n − 1))^{∗}.

The correctness of this description of T 1 follows from the results of Appendix C.

Having described pd as a globular set, we next turn to its strict ω-category structure: in other words, how pasting diagrams may be composed.

Typical binary compositions are illustrated by

[figure: •; •; •; •; ⊗_{1}; •; •; •; •] = ^{•}  [figure]^{•}  \overline{}^{•}  [figure]

and

• [figure] ^{•} ⊗_{0} ^{•}  [figure]^{•} = ^{•} [figure] ^{•}  [figure]^{•} .

These compositions are possible because the sources/targets match appropriately: e.g. in the first calculation, where we are gluing along 1-cells (indicated by ⊗_{1}), the 1-dimensional parts of the two arguments are the same. A typical nullary composition—identity—is

\begin{matrix}[figure: •; •; •; •] & ⟼ & [figure: •; •; •; •] \\ ∈ pd(1) & & ∈ pd(2). \end{matrix}

It is helpful to ponder not just binary and nullary composition in pd, but composition indexed by arbitrary shapes, in the sense now explained. We may think of the first binary composition above as indexed by

• [figure]^{•} ∈ pd(2),

because we were composing one 2-cell with another by joining along their bounding 1-cells. The composition can be represented as

[figure: •; •; •; •; •; •; •; •; •; •; •; •; ▽; △; ▽]  (12)

In general, the ways of composing pasting diagrams are indexed by pasting diagrams themselves. For instance,

[figure: •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; ▽; △; ▽; ▽; ▽]  (13)

represents the composition

( [figure: •; •; •; ⊗_{1}; •; •; •] ) ⊗_{0}_{•}  ^{}_{•} [figure]_{•}⊗_{0}_{•}  ^{}_{•}  ^{}_{•}  ^{}_{•}

=  [figure: •; •; •; •; •; •; •; •]

We have now described the strict ω-category pd = T 1. More generally, what does T X look like for an arbitrary globular set X? A globular set is a diagram

⋯ [figure: s; t] X(n + 1) [figure: s; t] X(n) [figure: s; t] ⋯ [figure: s; t] X(0)

of sets, in which s and t obey the ‘globularity’ relations given in 4.1; elements of X(k) are called k-cells of X. An element of (T X)(n) is an n-pasting diagram labelled by elements of X: for example, a typical element of (T X)(2) is a diagram

A^{•} [figure: f; f′; f′′; f′′′; α; α′; α′′]B^{•}  ^{g \overline{}}C^{•}  [figure: h; h′; β] D^{•} .

where A, …, D ∈ X(0), f, …, h′ ∈ X(1), α, …, β ∈ X(2), and s(α) = f, t(α) = f′, etc.

To state this more precisely, we first associate to each pasting diagram π a globular set π̂—the globular set ‘looking like π’. For instance, if π is the 2-pasting diagram (11) then

|π̂(k)| = \{ \begin{matrix}4 & if k = 0 \\ 7 & if k = 1 \\ 4 & if k = 2 \\ 0 & if k ≥ 3 \end{matrix}

since (the picture of) π has 4 0-cells, 7 1-cells, and so on. We construct π̂, for π ∈ pd(n), recursively on n. If π is the unique element of pd(0) then define

π̂ = (⋯ [figure] ∅ [figure] ∅ [figure] 1).

If n ≥ 0 and π ∈ pd(n + 1) then π = (π_{1}, …, π_{r}) for some π_{1}, …, π_{r} ∈ pd(n), and define

π̂ = (⋯ [figure] ∐_{i=1}^{r} π̂_{i}(1) [figure] ∐_{i=1}^{r} π̂_{i}(0) [figure] {0, 1, …, r}).  (14)

The source and target maps in all but the bottom dimension are the evident disjoint unions; in the bottom dimension, they are defined by

s(x) = i − 1,  t(x) = i,  for x ∈ π̂_{i}(0).

Having defined for each pasting diagram π its ‘representation’ π̂, we can formalize our guess as to what an element of (T X)(n) is. A ‘labelling of π by elements of X’ is a map π̂ \overline{}X, so we are guessing that

(T X)(n) ≅ ∐_{π∈pd(n)} [𝔾, Set](π̂, X).

This is indeed the case, as is shown in C.3. (Note that by taking X = 1 we recover the fact that (T 1)(n) ≅ pd(n).)

With a little more effort we could define the source and target inclusions s, t : ˆ∂π \overline{}π̂, to give a concrete description of the source and target maps in T X, and hence of the functor T. With an appreciable amount of effort, we could do the same thing for the monad structure on T; but we do not, as the constructions involved for multiplication are rather complex and not especially illuminating.

There is an alternative way to represent elements of (T 1)(n), used by Batanin in his paper [Bat]: as trees. (These trees differ slightly from those which occur elsewhere in this paper, and serve a different conceptual purpose.) For example, we translate the pasting diagram

[figure: •; •; •; •]

into the tree

[figure: • • • •; •; •; •; •].

The thinking here is that the pasting diagram is 3 1-cells long, so we start the tree as

[figure: • • •; •]; then the first column is 3 2-cells high, the second 0, and the third 1, so the tree

becomes

[figure: • • • •; •; •; •; •];

finally, there are no 3-cells so the tree stops there.

Formally, let us define an n-stage tree (n ∈ ℕ) to be a diagram

τ(n) \overline{}τ(n − 1) \overline{}⋯ \overline{}τ(1) \overline{}τ(0) = 1

in the category Δ of all finite ordinals, and write Bt(n) for the set of all n-stage trees (with Bt for ‘Batanin trees’). The element of Bt(2) just drawn corresponds to a certain diagram 4 \overline{}3 \overline{}1 in Δ, for example; note that if τ is an n-stage tree with τ(n) = 0 then the height of the picture of τ will be less than n. The source/target ∂τ of an n-stage tree τ is the (n−1)-stage tree obtained by removing all the nodes at height n, or formally, truncating

τ(n) \overline{}τ(n − 1) \overline{}⋯ \overline{}τ(1) \overline{}τ(0)

to

τ(n − 1) \overline{}⋯ \overline{}τ(1) \overline{}τ(0).

We thus have a diagram

⋯ \overline{}Bt(n + 1) ^{^{∂}} Bt(n) \overline{}⋯ ^{^{∂}} Bt(0)  (15)

in Set, and so a globular set Bt whose source and target maps are equal. This is isomorphic to T 1, by the following result.

4.2.1. Proposition. The diagram (15) in Set is isomorphic to

⋯ \overline{}pd(n + 1) ^{^{∂}} pd(n) \overline{}⋯ ^{^{∂}} pd(0).

Proof. pd(0) and Bt(0) are both 1-element sets, hence isomorphic in a unique way. Suppose inductively that n ≥ 0 and that we have constructed a commuting diagram

[figure: pd(n); ∂; pd(n − 1); ∂; ⋯; ∂; pd(0)]

[figure: Bt(n); α; ∂; Bt(n − 1); α; ∂; ⋯; ∂; Bt(0).; α]

If π ∈ pd(n + 1) then π = (π_{1}, …, π_{r}) for some r ∈ ℕ and π_{i} ∈ pd(n); then define α(π) to be

∑_{i=1}^{r}(α(π_{i}))(n) \overline{}⋯ \overline{}∑_{i=1}^{r}(α(π_{i}))(0) \overline{}1.

It is easy to check that the map α : pd(n + 1) \overline{}Bt(n + 1) thus defined is a bijection and commutes with the ∂’s.

Composition and identities in the strict ω-category Bt ( ≅ T 1) can also be expressed in the pictorial language of trees, in a simple and compelling way; for that the reader is referred to [Bat] or [Lei3, Ch. II].

4.3. Globular operads and algebras. Let T be the free strict ω-category monad on the category [𝔾, Set] of globular sets. This subsection is an attempt at an elementary explanation of T -operads and their algebras.

A collection is a T -graph on 1: that is, it is a globular set C together with a map C \overline{}pd. Put another way, a collection consists of a set C(π) for each n-pasting diagram

π, together with a pair of functions C(π) [figure: s; t] C(∂π) (when n ≥ 1), satisfying the usual

globularity equations ss = st and ts = tt.

A T -operad is a collection C ^{^{d}} pd together with identities and compositions satisfying suitable axioms. The elements of C(π) are to be thought of as the operations of shape or arity π: in other words, as the functions

[𝔾, Set](π̂, X) \overline{}X(n)  (16)

which exist as part of the structure of a C-algebra X. (Recall that [𝔾, Set](π̂, X) is the set of ‘labellings of π by elements of X’.)

The identities consist of an element of C(ι_{n}) for each n, where ι_{n} ∈ pd(n) is the n-pasting diagram looking like a single n-cell: formally, ι_{0} is the unique element of pd(0) and

ι_{n+1} = (ι_{n}) ∈ (pd(n))^{∗} = pd(n + 1).

Composition is a map C^{∘}C \overline{}C over pd, where the collection C^{∘}C d̃ ; pd is the left-hand diagonal of the diagram

[figure: C^{∘}C; T (C)  C; T (d); T (!); d; T (pd)  pd; μ_{1}; pd] .

A typical element of (C^{∘}C)(2) is depicted in the following diagram:

[figure: •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; ▽; △; △; ▽; π_{1} =; π_{2} =; π_{3} =; π =; θ_{1}; θ_{2}; θ_{3}; θ]  (17)

This diagram is meant to indicate that θ_{1} ∈ C(π_{1}), θ_{2} ∈ C(π_{2}), θ_{3} ∈ C(π_{3}), θ ∈ C(π), and that θ_{1}, θ_{2}, θ_{3} match suitably on their sources and targets (e.g. t(θ_{1}) = s(θ_{2})). The left-hand half of the diagram is an element of the fibre over π in the map T (C) ^{T (!)} pd; the right-hand half is an element of C(π) (which is the fibre over π in the map C ^{^{d}} pd);

hence the whole diagram is an element of (C^{∘}C)(2). The map C^{∘}C d̃ ; pd sends this element to the 2-pasting diagram

π^{∘}(π_{1}, π_{2}, π_{3}) = _{•} [figure]_{•} ^{}_{•} [figure]_{•} [figure] _{•} [figure] _{•}

(which is the composite of π with π_{1}, π_{2}, π_{3} in the ω-category pd; cf. diagram (13)). So, composition sends the data assembled in (17) to an element of C(π^{∘}(π_{1}, π_{2}, π_{3})), which may be drawn as

[figure: •; •; •; •; •; •; •; •; ▽; π^{∘}(π_{1}, π_{2}, π_{3}) =; θ^{∘}(θ_{1}, θ_{2}, θ_{3})] .

(The ‘linear’ notation π^{∘}(π_{1}, π_{2}, π_{3}) and θ^{∘}(θ_{1}, θ_{2}, θ_{3}) should not be taken too seriously. There is evidently no natural order in which to put the π_{i}’s and θ_{i}’s; the notation is just being used temporarily for convenience.)

The composition and identities in a T -operad C are required to commute with the source and target maps and, of course, to obey associativity and identity laws. For example, if we have a diagram

·

[figure: θ_{11}] ·  \overline{θ_{12} ^{}}·

[figure: θ_{13}; θ_{1}]

·

·  \overline{θ ^{}}·
[figure: θ_{2}]
·

of the same kind as (17), then

θ^{∘}(θ_{1}^{∘}(θ_{11}, θ_{12}, θ_{13}), θ_{2}) = (θ^{∘}(θ_{1}, θ_{2}))^{∘}(θ_{11}, θ_{12}, θ_{13}, 1).

We have now seen that an operad consists of a set C(π) for each pasting diagram π, with source and target functions, and compositions between the C(π)’s according to the pasting-together of pasting diagrams. We have already argued (equation (16)) that an algebra for C ‘ought’ to consist of a globular set X together with a function

\overline{θ} : [𝔾, Set](π̂, X) \overline{}X(n)

for each θ ∈ C(π) (π ∈ pd(n), n ∈ ℕ), obeying suitable axioms. So for instance, suppose that

π = ^{•}  [figure]^{•}  \overline{}^{•} ,

that θ ∈ C(π), and that

[figure: A^{•}; p; p′; p′′; p′′′; α; α′; α′′; B^{•}; q; C^{•}]

is a diagram of cells in X; then \overline{θ} assigns to this picture a 2-cell in X.

This is indeed what the general theory says a C-algebra is. For an algebra structure on X is a map T_{C}X ^{^{h}} X obeying suitable laws, where T_{C}(X) is the pullback

[figure: T_{C}X; T X C; T (!); d; pd] ,

and this means that

(T_{C}X)(n) = ∐_{π∈pd(n)} C(π) × [𝔾, Set](π̂, X).

Hence h consists of a function

C(π) × [𝔾, Set](π̂, X) \overline{}X(n)

for each number n and n-pasting diagram π. Writing h(θ, —) as \overline{θ}, we see that this is just the description above.

We have now discussed what operads and their algebras look like, and it is time to come to the main point of the section.

4.4. Contractions. We start with an informal description of what a weak ω-category ‘should’ be, centred around the idea of contraction, and then see how this is expressed by the formal definition of contraction.

The graph structure of an ω-category consists of 0-cells A^{•} , 1-cells A^{•} ^{f \overline{}}B^{•} ,

2-cells A^{•} [figure: f; g; α] B^{•} , …. There are then various ways of composing these cells; just

how many ways and how they interact depends on whether we are dealing with strict or weak ω-categories, or something in between. In a strict ω-category, there will be precisely one way of composing a diagram like

[figure: A^{•}; f; f′; f′′; α; α′; B^{•}; g; C^{•}; h; h′; γ; D^{•}]  (18)

to obtain a 2-cell: that is, any two different ways of doing it (such as ‘compose α′ with α, and γ with g, then the two of these together’) give exactly the same resulting 2-cell. In a weak ω-category there will be many ways, but the resulting 2-cells will all be equivalent in a suitably weak sense.

Our method of describing what ways of composing are available in a weak ω-category depends on one simple principle, the contraction principle. Take, for example, the diagram (18) above. Suppose we have already constructed two ways of composing a generic diagram

[figure: •; p; •; q; •; r; •]

of 1-cells, namely (rq)p and r(qp). Then the contraction principle says that there is a

way of composing diagram (18) to get a 2-cell of the form A^{•} [figure: (hg)f; h′(gf′′)] D^{•} . As another

example of the principle, this time in one higher dimension, take a diagram

A^{•}  [figure: f; f′; f′′; α; α′; α′′; β; x; y]B^{•}  ^{g  \overline{}}C^{•}  [figure: h; h′; γ; γ′; z] D^{•} .  (19)

Suppose we have constructed two ways of composing a generic diagram of the shape of (18) to a 2-cell, each of which invokes the same way of composing the 1-cells

[figure: •; •; •; •]

along the top and bottom. Say, for instance, that the first way of composing (18) results

in a 2-cell A^{•} [figure: (hg)f; h′(gf′′); δ] D^{•} and the second way in a 2-cell A^{•} [figure: (hg)f; h′(gf′′); δ′] D^{•} . Then the

contraction principle says that there is a way of composing (19) to get a 3-cell of the form

A^{•} [figure: (hg)f; h′(gf′′); δ; δ′] D^{•} .

In general, the contraction principle can be stated as follows. Suppose we are given an n-dimensional diagram and two ways of composing the (n − 1)-dimensional diagram at its source/target, such that these two ways match on the (n − 2)-dimensional source and target. Then there’s a way of composing the n-dimensional diagram, inducing the first way on its source and the second way on its target. (In our first example, we implicitly used the fact that the two ways of composing

•  ^{p \overline{}}^{•}  ^{q \overline{}}^{•}  ^{r \overline{}}^{•} ,

(rq)p and r(qp), do the same thing to the bounding 0-cells: nothing at all.) The ways of composing in a weak ω-category are to be generated by this principle, and this principle alone.

How does this idea of contraction compare to the definition given in 4.1? The structure encoding ‘ways of composing’ is, of course, a T -operad C. For π ∈ pd(n) (n ≥ 2), we defined

P_{π}(C) = {(θ_{0}, θ_{1}) ∈ C(∂π)^{2} | s(θ_{0}) = s(θ_{1}) and t(θ_{0}) = t(θ_{1})},

and for π ∈ pd(1),

P_{π}(C) = C(∂π)^{2}.

Thus an element of P_{π}(C) can be thought of as a way θ_{0} of composing the (n − 1)- dimensional source of an n-dimensional diagram of shape π, together with a way θ_{1} of composing its target, such that these two ways match on the (n − 2)-dimensional part. A contraction κ on C was defined as a function

κ_{π} : P_{π}(C) \overline{}C(π)

for each π, such that

s(κ_{π}(θ_{0}, θ_{1})) = θ_{0}, t(κ_{π}(θ_{0}, θ_{1})) = θ_{1}.

In other words, it extends θ_{0} and θ_{1} to a way κ_{π}(θ_{0}, θ_{1}) of composing a whole π-shaped diagram. This is exactly the effect of the informal contraction principle.

Notice, incidentally, that if κ is a contraction on a T -operad C then the functions κ_{π} are not required to be compatible with the operad structure on C in any way. So the natural entity on which to define a contraction is not in fact a T -operad but a collection (i.e. a T -graph on 1).

An important feature of the contraction idea is what happens with degenerate pasting diagrams. There is not only a 2-pasting diagram σ shaped like diagram (18), but also a (degenerate) 3-pasting diagram π shaped like it too: thus ∂π = σ. Now, suppose that θ_{0}, θ_{1} ∈ C(σ) with s(θ_{0}) = s(θ_{1}) and t(θ_{0}) = t(θ_{1}). Then there is an element θ = κ_{π}(θ_{0}, θ_{1}) of C(π) with s(θ) = θ_{0} and t(θ) = θ_{1}. This means that θ assigns to the data in (18) a 3-cell

A^{•} [figure: δ_{0}; δ_{1}] D^{•} ,

in which δ_{0} and δ_{1} are respectively the results of applying θ_{0} and θ_{1} to (18). This is the kind of argument we would use to prove that any two composites of a given diagram are, in a suitable sense, equivalent.

4.5. The definition. A weak ω-category is defined to be an L-algebra, where (L, λ) is the initial operad-with-contraction. We have seen what an operad-with-contraction is, and what an algebra for one is; now we have just to see why the initial one gives us what we want.

Another way of saying that (L, λ) is initial in OWC is that (L, λ) is the operad-with-contraction freely generated by the empty collection (∅ \overline{}pd). That is, we start with the empty collection and freely add in just enough to make it into a T -operad L with a contraction λ on it.

So, for a start there is an identity element 1 ∈ L(•), where • ∈ pd(0). Next, take the 1-pasting diagram

π_{n} = ( ^{•}  \overline{}^{•}  \overline{}⋯  \overline{}^{•} )

of length n. The contraction gives us an element ψ_{n} = λ_{π_{n}}(1, 1) of L(π_{n}). Thus in an L-algebra, ψ_{n} provides a way of composing a diagram

[figure: A_{0}^{•}; f_{1}; A_{1}^{•}; f_{2}; ⋯; f_{n}; A_{n}^{•}]

to give a 1-cell A_{0}^{•} ψ_{n}(f_{1}, …, f_{n})_{\overline{}}A_{n}^{•} ; let us write

(f_{n}^{∘} ⋯^{∘}f_{1}) = ψ_{n}(f_{1}, …, f_{n})

(n ≥ 1), and 1 = ψ_{0}(). Next, the operad structure on L gives us 1-dimensional elements of L such as

ψ_{3}^{∘}(ψ_{3}, ψ_{0}, ψ_{2}) ∈ L(π_{5}),

which is interpreted in an L-algebra as the function

[figure: •; f_{1}; •; f_{2}; •; f_{3}; •; f_{4}; •; f_{5}; •]
⟼  ^{•} ((f_{5}^{∘}f_{4})^{∘}1^{∘}(f_{3}^{∘}f_{2}^{∘}f_{1}))_{\overline{}}^{•} .

This analysis might lead us to suspect that L(π_{n}) is the set tr(n) of n-leafed trees (described in 3.3 and A.1), which in fact it is.

Moving now to the 2-dimensional level, if π is the 2-pasting diagram shaped like diagram (18) then any pair (θ_{0}, θ_{1}) of elements of L(π_{3}) gives rise to an element θ = λ_{π}(θ_{0}, θ_{1}) of L(π). (Since L(•) has only one element, there is no need to worry about θ_{0} and θ_{1} matching at the 0-dimensional level.) Generally, the 2-dimensional part of L contains elements obtained by contraction from the 1-dimensional parts, together with all the elements obtained by pasting them together (using the operad structure of L). To take a reasonably manageable example, let

\begin{matrix}π = ^{•}  [figure]^{•} ,  π′ = ^{•}  [figure] ^{•}  [figure] ^{•} , \\ π′′ = ^{•}  [figure]^{•}  [figure]^{•} . \end{matrix}

Then:

• L(π) has an element ψ = λ_{π}(1, 1) (where 1 ∈ L(π_{1}))

• L(π′) has an element ψ′ = λ_{π′}(ψ_{2}, ψ_{2})

• L(π′′) has an element λ_{π′′}(ψ_{2}, ψ_{2}) (‘compose all four cells at once’)

• L(π′′) also has an element which might reasonably be denoted ψ^{∘}(ψ′, ψ′) (‘first compose horizontally, then compose vertically’)

• L(π′′) has a third element ψ′^{∘}(ψ, ψ) (‘first compose vertically, then compose horizontally’).

These elements ψ^{∘}(ψ′, ψ′) and ψ′^{∘}(ψ, ψ) of L(π) are familiar from the interchange law in the definition of 2-category. Of course, the three elements of L(π) we have mentioned are not its only elements; there are infinitely many, since tr(2) is an infinite set.

This concludes our explanation of why weak ω-categories can reasonably be defined as objects of Alg(L).

Notice, however, that weak ω-functors are not defined as morphisms in Alg(L). On the contrary, a morphism in Alg(L) preserves the L-algebra structure strictly, so should be thought of as a strict map of weak ω-categories.

Here is a sketch of how ‘weak ω-functor’ might be defined. This is only speculation, and no proper definition is attempted here. As in the definition of weak ω-category, the idea is to take a theory of strict things and a notion of contraction to create a theory of weak things.

So, there is a T -multicategory Map such that a Map-algebra is a pair (X, Y) of strict ω-categories together with a strict ω-functor X ^{}Y. (The objects-object Map_{0} of Map is the coproduct 1 + 1 of two copies of the terminal globular set.) There is also a notion of what a contraction on a map of T -multicategories is. Hence there is a category of T -multicategories with contraction over Map, in which an object consists of a T -multicategory D, a map d : D \overline{}Map of T -multicategories, and a contraction δ on d. This category has an initial object (M ^{m} Map, ν), and a weak ω-functor is defined as an M-algebra.

The notion of a contraction on a map of T -multicategories has the property that for T -operads C, a contraction on the unique map from C to the terminal T -operad is precisely a contraction on C in the sense of the rest of this section. This means that the two inclusions 1 [figure] Map induce another pair of maps L [figure] M, and hence a pair of functors Alg(M) [figure] Alg(L). These are the functors assigning to a weak ω-functor its domain and codomain.

Batanin’s paper [Bat] contains a definition (§8) of weak ω-functor, which unfortunately I have not been able to understand. However, I think I can explain how Batanin’s definition of weak ω-category differs from the present one, as follows.

Let C be a T -operad. Firstly, a system of compositions on C consists of a chosen element θ_{π} of C(π) for each pasting diagram π that represents a binary composition: for instance, π might be one of

•  \overline{}_{•}  \overline{}_{•}, _{•} [figure] _{•} [figure] _{•}, _{•} [figure]_{•}.

These chosen elements are required to be consistent with one another: e.g. if π_{1} and π_{2} are the first and second of these three diagrams, then

s(θ_{π_{2}}) = θ_{π_{1}} = t(θ_{π_{2}}).

Secondly, a contraction κ on C is a family (κ_{π}) of functions of a certain kind, exactly as in our definition, except that now π only ranges over those n-pasting diagrams satisfying π̂(n) = ∅. The latter condition means that π is ‘degenerate’, as discussed earlier in the section.

Now consider the full subcategory Q of T -Operad whose objects are those T -operads on which there exists both a system of compositions and a contraction. Batanin constructs a certain weakly initial object K of Q, and defines a weak ω-category to be a K-algebra.

‘Weakly initial’ means that there is at least one map from K to any other object of Q. So K is not determined by its weak initiality, and this means that if we want to know what a Batanin weak ω-category is then we actually need the details of the construction of K in [Bat]. It might be the case that if we take the category Q′ of T -operads equipped with a system of compositions and a contraction, then K (together with its system of compositions and contraction) is initial in Q′, and of course this would determine K. A remark in [Bat] (just before Definition 8.6) suggests that this is true.

The idea behind the Batanin definition appears to be that the theory of weak ωcategories—that is, the operad K for which they are algebras—is generated by two things: operations and equations. The operations are binary compositions of various dimensions, and these are provided by the system of compositions. The ‘equations’ should really be called ‘equivalences’, and are provided by the contraction: compare the use of degenerate pasting diagrams at the end of 4.4 above. In our approach these two ingredients are merged into one: the more comprehensive notion of contraction.

I do not know if the present definition of weak ω-category is in any sense equivalent to Batanin’s. I would certainly imagine so, but there is little chance of providing a comparison before weak ω-functors are understood.

4.6. Examples. At this point it would be nice to give a fully worked-out non-trivial example of a weak ω-category. Unfortunately I do not yet have one for which all the details have been settled. However, the following remarks may provide partial satisfaction.

Recall from 2.3 that a map between T -operads induces a map in the opposite direction between their categories of algebras, and that an algebra for the terminal T -operad is just a T -algebra. Hence the unique T -operad map L \overline{}1 induces a functor

(strict ω-categories) = Alg(1) \overline{}Alg(L) = (weak ω-categories).

That is, ‘every strict ω-category is a weak ω-category’. Incidentally, the terminal T - operad 1 carries a unique contraction, and is then the terminal operad-with-contraction: so algebras for the terminal operad-with-contraction are strict ω-categories, and algebras for the initial operad-with-contraction are weak ω-categories.

More generally, for any operad-with-contraction (C, κ) there is a unique contractionpreserving operad map L \overline{}C, and this induces a functor

Alg(C) \overline{}Alg(L).

This provides a means of finding examples of weak ω-categories. For instance, suppose we wanted to define a weak ω-category Π_{ω}(S) for every topological space S, its ‘fundamental ω-groupoid’. It is clear what the globular set Π_{ω}(S) should be, and our strategy might then be to find a T -operad C such that

• Π_{ω}(S) is naturally a C-algebra for every space S, and

• there is a contraction on C.

Any way of doing this will give the globular set Π_{ω}(S) the structure of a weak ω-category. (The rough idea is that C(π) is the set of continuous maps from the closed n-ball to the contractible space which looks like the usual picture of π (for π ∈ pd(n)), subject to conditions on boundary-preservation. Something like this is done in [Bat, §9].)

In the next subsection, weak n-categories will be defined as weak ω-categories of a special kind. We will subsequently show that weak 2-categories are essentially the same as bicategories. Thus any bicategory provides a (degenerate) example of a weak ω-category.

4.7. Weak n-categories. Our definition of weak ω-category suggests not just one, but two plausible definitions of weak n-category. In this subsection we present both of these definitions and show that the two different categories of weak n-categories (with strict n-functors as morphisms) are equivalent.

Let us say that a globular set X is n-dimensional (for n ∈ ℕ) if for all m ≥ n,

s = t : X(m + 1) \overline{}X(m)

and this map is an isomorphism.

4.7.1. Definition. A weak n-category is a weak ω-category whose underlying globular set is n-dimensional.

This formalizes the idea that an n-category is an ω-category in which the only cells of dimension greater than n are identities. Let us write Wk-n-Cat for the full subcategory of Alg(L) whose objects are weak n-categories.

The alternative approach does not use the definition of weak ω-category directly, but instead imitates it. Write G = [𝔾, Set] for the category of globular sets. Let 𝔾_{n} be the full subcategory of 𝔾 with objects 0, …, n, let G_{n} = [𝔾_{n}, Set], call objects of G_{n} n-globular sets, and let T_{n} be the free strict n-category monad on G_{n}. Theorem C.1.1 tells us that T_{n} is a cartesian monad on G_{n}, so we can discuss T_{n}-operads.

Let C be a T_{n}-operad. If 1 ≤ k ≤ n and π ∈ pd(k), we may define the set P_{π}(C) just as in 4.1. A precontraction on C is a family of functions

(κ_{π} : P_{π}(C) \overline{}C(π))_{1≤k≤n,π∈pd(k)}

satisfying the same equations as in 4.1. If C has the property that for all π ∈ pd(n) and θ_{0}, θ_{1} ∈ pd(π),

s(θ_{0}) = s(θ_{1}) and t(θ_{0}) = t(θ_{1})  ⟹  θ_{0} = θ_{1}

then any precontraction on C is called a contraction. (There is then no choice about what the contraction does in the top dimension.) We therefore obtain a category OWC_{n}, in which an object is a T_{n}-operad equipped with a contraction and a map is a map of operads preserving contractions, defined analogously to OWC in 4.1.

Later we will show that OWC_{n} has an initial object (L_{n}, λ_{n}). The alternative definition of weak n-category is as an L_{n}-algebra. As in the case of ω-categories, the morphisms in Alg(L_{n}) should be interpreted as strict maps.

The aim of the rest of this subsection is to show that these two definitions are equivalent, in the following strong sense. (‘Strong’, because we do not have to resort to weak n-functors in order to be able to compare the objects of the two categories.)

4.7.2. Theorem. There is an equivalence of categories

Wk-n-Cat ≃ Alg(L_{n}).

The proof is in two parts: first we express the initial object (L_{n}, λ_{n}) of OWC_{n} in terms of (L, λ), and then we are in a position to compare algebras for L_{n} and for L.

So, the inclusions 𝔾_{n−1} ^{⊂} ^{}𝔾_{n} and 𝔾_{k} ^{⊂} ^{}𝔾 induce ‘restriction’ functors

R_{n−1}^{n} : G_{n}  \overline{}G_{n−1},  R_{k}^{ω} : G \overline{}G_{k},

for any n ≥ 1 and k ≥ 0. We then have:

4.7.3. Proposition.

a. For any n ≥ 1, the functor R_{n−1}^{n} has a right adjoint S_{n−1}^{n}, and there is an induced adjunction

\begin{matrix}OWP & n \\ OWP_{n−1} & [figure: R_{n−1}^{n}; ⊣; S_{n−1}^{n}] \end{matrix}

(abusing notation by reusing the symbols R_{n−1}^{n} and S_{n−1}^{n})

b. This adjunction restricts to an equivalence of categories

\begin{matrix}OWC & n \\ OWP_{n−1} & [figure: R_{n−1}^{n}; ≃; S_{n−1}^{n}] \end{matrix}

c. For any k ≥ 0, the functor R_{k}^{ω} has a right adjoint S_{k}^{ω}, and there is an induced adjunction

\begin{matrix}OWC \\ OWP_{k}. & [figure: R_{k}^{ω}; ⊣; S_{k}^{ω}] \end{matrix}

Proof.

a. That R_{n−1}^{n} : G_{n} \overline{}G_{n−1} has a right adjoint is immediate: it is the right Kan extension of the inclusion 𝔾_{n−1} ^{⊂} ^{}𝔾_{n}. However, it will be useful to have the following explicit description of S_{n−1}^{n}: if X ∈ G_{n−1} then

\begin{matrix}(S_{n−1}^{n}X)(k) = X(k) for 0 ≤ k ≤ n − 1, \\ (S_{n−1}^{n}X)(n) = \{(x_{0}, x_{1}) ∈ (X(n − 1))^{2} | s(x_{0}) = s(x_{1}), t(x_{0}) = t(x_{1})\}. \end{matrix}

(When n = 1 the second line does not make sense, and we instead define (S_{0}^{1}X)(1) as X(0) × X(0); essentially we are ‘taking X(−1) = 1’.) The source and target maps are the obvious ones.

As is shown in Appendix C, R_{n−1}^{n} is naturally a monad opfunctor (G_{n}, T_{n}) \overline{} (G_{n−1}, T_{n−1}), whose natural transformation part

R_{n−1}^{n}^{∘}T_{n} \overline{}T_{n−1}^{∘}R_{n−1}^{n}

is an isomorphism. Under the adjunction R_{n−1}^{n} ⊣ S_{n−1}^{n}, the mate of this isomorphism is a natural transformation

T_{n}^{∘}S_{n−1}^{n} \overline{}S_{n−1}^{n}^{∘}T_{n−1},

and this gives S_{n−1}^{n} the structure of a monad functor (G_{n−1}, T_{n−1}) \overline{}(G_{n}, T_{n}). Further checks reveal that the conditions of 3.2 are satisfied, so that there is an induced adjunction between categories of multicategories; moreover, R_{n−1}^{n} and S_{n−1}^{n} each preserve terminal objects, so this restricts to an adjunction

T_{n}-Operad

T_{n−1}-Operad. [figure: R_{n−1}^{n}; ⊣; S_{n−1}^{n}]

(20)

R_{n−1}^{n} has the obvious restriction effect on T_{n}-operads; in the other direction, if D is a T_{n−1}-operad, 0 ≤ k ≤ n and π ∈ pd(k), then

(S_{n−1}^{n}D)(π) = \{ \begin{matrix}D(π) & for 0 ≤ k ≤ n − 1 \\ P_{π}(D) & for k = n. \end{matrix}

Next we bring in precontractions. Any precontraction on a T_{n}-operad C evidently gives rise to a precontraction on R_{n−1}^{n}C; conversely, any precontraction on a T_{n−1}- operad D extends uniquely to a precontraction on S_{n−1}^{n}D. The precontractions produced by these two constructions are preserved by the unit and counit maps of the adjunction (20), so we obtain an adjunction

\begin{matrix}OWP & n \\ OWP_{n−1} & [figure: R_{n−1}^{n}; ⊣; S_{n−1}^{n}] \end{matrix}

as required.

b. Any adjunction F ⊣ G : D \overline{}C restricts to an equivalence between C′ and D′, where C′ is the full subcategory of C whose objects are those at which the unit of the adjunction is an isomorphism, and similarly D′ with the counit. In the present case we have R_{n−1}^{n}^{∘}S_{n−1}^{n} = 1, and the counit of the adjunction is the identity transformation. On the other hand, let (C, κ) be a T_{n}-operad with precontraction and consider the unit map

(C, κ) \overline{}S_{n−1}^{n}R_{n−1}^{n}(C, κ).

This is the identity in dimensions less than n, and in dimension n it consists of the maps

(s, t) : C(π) \overline{}P_{π}(C)

[figure: G; G_{n}; R_{n}^{ω}; ⊣; S_{n}^{ω}; G_{n−1}; R_{n−1}^{n}; ⊣; S_{n−1}^{n}] OWC

[figure: OWP_{n}; ⊣; ⊃; OWC_{n}]
[figure: ≃]
OWP_{n−1} [figure: ⊣]

[figure: L; R_{n}^{ω}L ↓ L_{n} = S_{n−1}^{n}R_{n−1}^{ω}L; R_{n−1}^{ω}L ↓]

Figure 4b: Relating L and L_{n}

(π ∈ pd(n)). This is always surjective as C carries a precontraction, and is injective precisely when C satisfies the condition for precontractions on it to be called contractions. So the unit at (C, κ) is an isomorphism if and only if (C, κ) is an object of OWC_{n}.

c. The proof is just like that of part (a). Again it will be useful to have an explicit description of the right adjoint S_{k}^{ω} of R_{k}^{ω}: it is given by

\begin{matrix}(S_{k}^{ω}X)(m) = \\ \{ & \begin{matrix}X(m) & for 0 ≤ m ≤ k \\ \{(x_{0}, x_{1}) ∈ (X(k))^{2} | s(x_{0}) = s(x_{1}), t(x_{0}) = t(x_{1})\} & for m ≥ k + 1. \end{matrix} \end{matrix}

The source and target maps in dimensions ≤ k are as in X; from dimension k + 1 to dimension k they are first and second projection; and in dimensions above k + 1, they are identities.

From this we deduce the following corollary, which shows incidentally that OWC_{n} does have an initial object. The overall strategy is depicted in Figure 4b.

4.7.4. Corollary. S_{n−1}^{n}R_{n−1}^{ω}(L, λ) is an initial object of OWC_{n}.

Proof. The functor R_{n−1}^{ω} : OWC \overline{}OWP_{n−1} constructed in part (c) of the proposition has a right adjoint, so R_{n−1}^{ω}(L, λ) is initial in OWP_{n−1}. The functor S_{n−1}^{n} : OWP_{n−1} \overline{}OWC_{n} constructed in part (b) is an equivalence, so S_{n−1}^{n}(R_{n−1}^{ω}(L, λ)) is initial in OWC_{n}.

We write (L_{n}, λ_{n}) for the initial object of OWC_{n}: that is,

(L_{n}, λ_{n}) = S_{n−1}^{n}R_{n−1}^{ω}(L, λ).

Before moving to the second half of the proof of Theorem 4.7.2, let us recall some notation. Fix n ∈ ℕ. To any m-pasting diagram π there is associated the globular set π̂, and we may turn π̂ into an n-globular set by restriction (truncation). If m ≤ n then this only amounts to ignoring some ∅’s, since π̂(k) = ∅ for k > m. In Appendix C we show that if X is a globular set and m ≤ n then

(T_{n}X)(m) = ∐_{π∈pd(m)} G_{n}(π̂, X).

Given a T_{n}-operad C, a C-algebra structure on X consists of a map

h_{π} : C(π) × G_{n}(π̂, X) \overline{}X(m)

for each m ≤ n and π ∈ pd(m), subject to various axioms. For θ ∈ C(π), we write

\overline{θ} = h_{π}(θ, —) : G_{n}(π̂, X) \overline{}X(m).

Now, any weak n-category is isomorphic to a ‘strictly’ n-dimensional weak ω-category: that is, to one whose underlying globular set is of the form

⋯ [figure: 1; 1] X(n) [figure: 1; 1] X(n) [figure: s; t] ⋯ [figure: s; t] X(0).  (21)

So to prove Theorem 4.7.2 it is enough to prove that the category of strictly n-dimensional weak ω-categories is equivalent to Alg(L_{n}); indeed, we will prove that these two categories are isomorphic.

Let X be an n-globular set. An L-algebra structure on the globular set (21) consists precisely of an (R_{n}^{ω}L)-algebra structure on X together with a dotted arrow

[figure: L(σ) × G_{n}(ˆ∂σ, X); .; .; .; .; .; .; .; .; .; .; .; .; .; .; X(n); L(∂σ) × G_{n}(ˆ∂σ, X); s × 1; t × 1; h_{∂σ}; X(n); 1; 1]

making the diagram commute serially, for each σ ∈ pd(n + 1). To see this, note first that a map ˆ∂σ \overline{}X is the same as a map from σ̂ to the globular set (21), so an algebra structure on (21) yields such a dotted arrow for each σ. Conversely, given such arrows, all the L-algebra structure in higher dimensions is uniquely determined, and the algebra axioms are automatically satisfied. There is at most one way of choosing the dotted arrows, and such a way exists if and only if

for all σ ∈ pd(n + 1) and θ ∈ L(σ),
\overline{sθ} = \overline{tθ} : G_{n}(ˆ∂σ, X) \overline{}X(n).

Since L admits a contraction, and for each π ∈ pd(n) there exists σ ∈ pd(n + 1) with ∂σ = π, this condition is equivalent to:

for all π ∈ pd(n) and (θ_{0}, θ_{1}) ∈ P_{π}(L),
\overline{θ_{0}} = \overline{θ_{1}} : G_{n}(π̂, X) \overline{}X(n).  (22)

So a strictly n-dimensional weak ω-category consists precisely of an (R_{n}^{ω}L)-algebra X satisfying condition (22).

Working from the other end, let

C = R_{n}^{ω}L ∈ T_{n}-Operad,

and let u be the unit map C \overline{}S_{n−1}^{n}R_{n−1}^{n}C coming from the adjunction R_{n−1}^{n} ⊣ S_{n−1}^{n}. By the description of this adjunction in the proofs of Proposition 4.7.3(a) and (b), u_{π}(θ_{0}) = u_{π}(θ_{1}) whenever π ∈ pd(n) and (θ_{0}, θ_{1}) ∈ P_{π}(L); since C admits a precontraction, u is (surjective and therefore) the universal map out of C with this property. It follows that an algebra for S_{n−1}^{n}R_{n−1}^{n}C is exactly an algebra X for C satisfying the condition (22). (The details of this step are omitted; the idea is perhaps most naturally expressed in terms of endomorphism operads (3.5).) So we have

(strictly n-dimensional weak ω-categories)

≅ ((R_{n}^{ω}L)-algebras X satisfying (22))
≅ Alg(S_{n−1}^{n}R_{n−1}^{n}C)
= Alg(S_{n−1}^{n}R_{n−1}^{ω}L)
≅ Alg(L_{n}).

We have only discussed the objects of these categories, and not their morphisms; but everything works as it should since in each case the morphisms are the maps strictly preserving all the structure. This proves Theorem 4.7.2.

4.8. Weak 2-categories. A polite person proposing a definition of weak n-category should explain what happens when n = 2. With our definition, the category Wk-2-Cat of weak 2-categories turns out to be equivalent to UBicat_{str}, the category of small unbiased bicategories and unbiased strict functors. This is the main result of this subsection.

Note that because the morphisms in Wk-2-Cat are strict maps (as noted on page 153), we obtain an equivalence with UBicat_{str}, not UBicat_{wk} or UBicat_{lax}; and unlike the weak and lax versions, UBicat_{str} is not equivalent to the corresponding category of classical bicategories (at least, the obvious functor is not an equivalence). So we cannot conclude that Wk-2-Cat is equivalent to Bicat_{str}. Nevertheless, the results of Section 1 mean that it is fair to regard classical bicategories as ‘essentially the same as’ unbiased bicategories, and therefore, by the results below, ‘essentially the same as’ weak 2-categories. If the definition of weak functor between n-categories were in place, we would expect there to be a genuine equivalence between Bicat_{wk} and the category of weak 2-categories and weak 2-functors.

Before embarking on the analysis of n = 2, let us check that things are as they should be for n = 0 and n = 1. In all cases, we will analyse Alg(L_{n}) rather than the equivalent category Wk-n-Cat, where (L_{n}, λ_{n}) is the initial T_{n}-operad with contraction.

4.8.1. Theorem. Wk-0-Cat ≃ Set.

Proof. T_{0} is the identity monad on the category G_{0} of sets, so a T_{0}-operad is a monoid. Any T_{0}-operad carries a unique contraction (vacuously), so OWC_{0} is the category of monoids; the initial object of OWC_{0} is the monoid 1. An algebra for the terminal T_{0}- operad is just a T_{0}-algebra (see 2.3.3(g)), so

Alg(L_{0}) ≅ G_{0}^{T_{0}} ≅ Set.

4.8.2. Theorem. Wk-1-Cat ≃ Cat.

Proof. T_{1} is the free category monad fc on the category G_{1} of directed graphs, so a T_{1}-operad is an fc-operad (see 3.6). A T_{1}-operad C admits at most one contraction, and does admit one if and only if the function

(s, t) : C(π) \overline{}C(•) × C(•)

is a bijection for each 1-pasting diagram π (where • ∈ pd(0)). It follows that the terminal T_{1}-operad is the initial object, L_{1}, of OWC_{1}. Hence Alg(L_{1}) ≅ G_{1}^{T_{1}} ≅ Cat.

The full proof that Wk-2-Cat ≃ UBicat_{str} involves rather more detailed manipulation than the reader would probably like to see. To keep the presentation light, I will use the coherence results of Appendix A for unbiased bicategories in the inexact form ‘all diagrams commute’. In the same spirit, I will use the following formulations of the notions of functor and natural transformation:

• A functor F : A_{1} × ⋯ × A_{n} \overline{}A consists of

– a function F_{0} : ob A_{1} × ⋯ × ob A_{n} \overline{}ob A

– a function assigning to each array of maps

\begin{matrix}a_{1}^{0} ^{α_{1}^{1}} ⋯ ^{α_{1}^{k_{1}}} a_{1}^{k_{1}} & in A_{1}, \\ … & … \\ a_{n}^{0} ^{α_{n}^{1}} ⋯ ^{α_{n}^{kn}} a_{n}^{k_{n}} & in A_{n} \end{matrix}  (23)

a map

F_{0}(a_{1}^{0}, …, a_{n}^{0}) \overline{}F_{0}(a_{1}^{k_{1}}, …, a_{n}^{k_{n}})

in A,

obeying ‘all reasonable coherence axioms’.

• A natural transformation

A_{1} × ⋯ × A_{n} [figure: F; F′; ϕ] A

consists of a function assigning to each array of maps (23) a map

F_{0}(a_{1}^{0}, …, a_{n}^{0}) \overline{}F′_{0}(a_{1}^{k_{1}}, …, a_{n}^{k_{n}}),

in such a way that ‘all reasonable coherence axioms’ hold.

In all parts of the proof where such sweeping language is used, the diligent reader should not find it difficult to fill in the details.

It will also be useful to have some notation for m-pasting diagrams when m ≤ 2. The unique 0-pasting diagram will be denoted •. We have pd(1) ≅ (pd(0))^{∗} ≅ ℕ, and the element of pd(1) corresponding to n ∈ ℕ will be denoted π_{n}; so π_{n} is usually drawn as

[figure: •; ⋯; •]

(n arrows). Similarly, pd(2) ≅ (pd(1))^{∗} ≅ ℕ^{∗}, and we write π_{k_{1},...,k_{n}} for the 2-pasting diagram corresponding to (k_{1}, …, k_{n}) ∈ ℕ^{∗}, which is usually drawn as a diagram

[figure: •; ⋮; •; ⋯; ⋯; •; ⋮; •]

with n columns and k_{i} 2-cells in the ith column.

4.8.3. Theorem. Wk-2-Cat ≃ UBicat_{str}.

Proof. First we identify the initial object (L_{2}, λ_{2}) of OWC_{2}; and since OWC_{2} ≃ OWP_{1}, this means examining OWP_{1}. A precontraction on a T_{1}-operad C consists of a function

κ_{π_{n}} : C(•) × C(•) \overline{}C(π_{n})

for each n ∈ ℕ, such that

s(κ_{π_{n}}(θ_{0}, θ_{1})) = θ_{0}, t(κ_{π_{n}}(θ_{0}, θ_{1})) = θ_{1}

for all θ_{0}, θ_{1}. A T_{1}-operad C with C(•) = 1 is merely a plain operad—call it C̃—and a precontraction on C consists of a distinguished element of C̃(n) for each n ∈ ℕ. The operad tr described in 3.3 and A.1, together with the element ν_{n} = (•, …, •) of tr(n) for each n, therefore defines a T_{1}-operad with precontraction. Using the fact that tr is the free plain operad on the terminal (free monoid)-graph, it is easy to see that this is the initial object of OWP_{1}. By Proposition 4.7.3, (L_{2}, λ_{2}) is S_{1}^{2} applied to this initial object: that is,

L_{2}(•) = 1,
L_{2}(π_{n}) = tr(n),
L_{2}(π_{k_{1},...,k_{n}}) = tr(n) × tr(n)

(n, k_{i} ∈ ℕ). In dimension 1, the T_{2}-operad structure is as in the plain operad tr. Given that the source and target functions

L_{2}(π_{k_{1},...,k_{n}}) [figure] L_{2}(π_{n})

are first and second projection, the T_{2}-operad structure in dimension 2 is uniquely determined.

This fully describes L_{2}. An algebra for L_{2} is, therefore:

• a 2-globular set X(2) [figure] X(1) [figure] X(0)

• for each n ∈ ℕ and τ ∈ tr(n), a function

\overline{τ} : G_{2}(π̂_{n}, X) \overline{}X(1)

• for each n, k_{1}, …, k_{n} ∈ ℕ and τ, τ′ ∈ tr(n), a function

\overline{(τ, τ′)} : G_{2}({ \atop π_{k_{1},...,k_{n}}}, X) \overline{}X(2)

satisfying axioms concerning the source and target of \overline{(τ, τ′)} in terms of \overline{τ} and \overline{τ′}, together with the axioms for an algebra (which we regard as ‘all reasonable coherence axioms’).

Rephrasing this a little, an algebra for L_{2} consists of • a set 𝔹_{0} (which is the X(0) of the previous paragraph)

• for each A, B ∈ 𝔹_{0}, a directed graph

𝔹(A, B) = (𝔹(A, B)_{1} [figure] 𝔹(A, B)_{0})

• for each τ ∈ tr(n) and A_{0}, …, A_{n} ∈ 𝔹_{0}, a function

𝔹(A_{0}, A_{1})_{0} × ⋯ × 𝔹(A_{n−1}, A_{n})_{0} ^{^{\overline{τ}}} 𝔹(A_{0}, A_{n})_{0}

• for each τ, τ′ ∈ tr(n), each A_{0}, …, A_{n} ∈ 𝔹_{0}, and each array of arrows

\begin{matrix}f_{1}^{0} ^{α_{1}^{1}} ⋯ ^{α_{1}^{k_{1}}} f_{1}^{k_{1}} & in 𝔹(A_{0}, A_{1}), \\ … & … \\ f_{n}^{0} ^{α_{n}^{1}} ⋯ ^{α_{n}^{kn}} f_{n}^{k_{n}} & in 𝔹(A_{n−1}, A_{n}), \end{matrix}

an arrow

\overline{τ}(f_{1}^{0}, …, f_{n}^{0}) \overline{}\overline{τ′}(f_{1}^{k_{1}}, …, f_{n}^{k_{n}})

in 𝔹(A_{0}, A_{n}),

satisfying ‘all reasonable coherence axioms’. These axioms imply that if τ = • ∈ tr(1) then the function

\overline{τ} : 𝔹(A_{0}, A_{1})_{0} \overline{}𝔹(A_{0}, A_{1})_{0}

is the identity. Now taking n = 1 and τ = τ′ = • in the fourth item, we have a function which assigns to each string of arrows

f^{0} ^{α^{1}} ⋯ ^{α^{k}} f^{k}

in 𝔹(A, B) an arrow \overline{•}(f^{0}) \overline{}\overline{•}(f^{k}), that is, f^{0} \overline{}f^{k}. This gives the directed graph 𝔹(A, B) the structure of a category. By the preliminary comments on functors and natural transformations (page 162), an L_{2}-algebra therefore consists of

• a set 𝔹_{0}

• for each A, B ∈ 𝔹_{0}, a category 𝔹(A, B)

• for each τ ∈ tr(n) and A_{0}, …, A_{n} ∈ 𝔹_{0}, a functor

\overline{τ} : 𝔹(A_{0}, A_{1}) × ⋯ × 𝔹(A_{n−1}, A_{n}) \overline{}𝔹(A_{0}, A_{n})

• for each τ, τ′ ∈ tr(n) and A_{0}, …, A_{n} ∈ 𝔹_{0}, a natural transformation

\overline{(τ, τ′)} : \overline{τ} \overline{}\overline{τ′}

satisfying ‘all reasonable coherence axioms’. Writing \overline{τ} as comp_{τ} and \overline{(τ, τ′)} as ω_{τ,τ′}, we see that this is just the description of a (small) unbiased bicategory given by Theorem A.1.3 and the comments thereafter.

We have proved that in the cases n = 0, 1, 2, the category Wk-n-Cat is equivalent to, respectively, Set, Cat and UBicat_{str}. In fact, we have proved that Alg(L_{0}) is isomorphic to Set, and similarly Alg(L_{1}) to Cat. The analogous property for n = 2 does not quite hold, because an unbiased bicategory is defined to be a structure on a ‘graph of directed graphs’ (that is, a set 𝔹_{0} together with a directed graph 𝔹(A, B) for each A, B ∈ 𝔹_{0}) whereas an L_{2}-algebra is a structure on a 2-globular set, and the category G_{2} of 2-globular sets is merely equivalent to the category of graphs of directed graphs. However, the proof reveals that this difference is the only obstacle to the equivalence Alg(L_{2}) ≃ UBicat_{str} becoming an isomorphism.

This concludes the material on weak ω- and n-categories, and indeed the main body of this paper. From the explanation of the formal definition of weak ω-category, and the analysis of the case n = 2, I hope that the reader is persuaded that the proposed definition is a reasonable one. Nonetheless, we have clearly only touched the beginning of a theory of weak higher-dimensional categories.

A. Biased vs. unbiased bicategories

In this appendix we prove the following results from Section 1, concerning the forgetful functor V : UBicat_{lax} \overline{}Bicat_{lax}:

Theorem 1.3.1 With the definitions given in 1.3,

a. V (B) is a bicategory and V (F, ϕ) is a lax functor

b. V preserves composition and identities, so forms a functor

UBicat_{lax}  \overline{}Bicat_{lax}

c. V is full, faithful and surjective on objects.

Corollary 1.3.2 The restricted functor V_{wk} : UBicat_{wk} \overline{}Bicat_{wk} is also full, faithful and surjective on objects.

It is possible to do the proofs in a thoroughly explicit way, as a very long sequence of calculations. At the other extreme, it is possible to state and prove a very general result, as follows. In the classical definition of bicategory, there is one nullary and one (horizontal) binary composition operation. In the unbiased definition, there is one n-ary operation for each n ∈ ℕ. Given a sequence (Ω_{n})_{n∈ℕ} of sets, there is a notion of ‘bicategory’ in which there is one n-ary operation for each member of Ω_{n}, and corresponding notions of lax and weak functors. So the classical case has Ω_{n} = 1 for n = 0, 2 and Ω_{n} = ∅ otherwise, and the unbiased case has Ω_{n} = 1 for all n. As long as Ω_{0} ≠ ∅ and Ω_{n} ≠ ∅ for some n ≥ 2, this gives a category of ‘bicategories’ and lax functors which is equivalent to Bicat_{lax}. This is the method employed for monoidal categories in [Lei8].

To keep things short, we shun both extremes and follow a third way. The strategy is to start by proving some coherence results for unbiased bicategories and functors, of the form ‘every diagram commutes’, and to recall similar coherence results for classical bicategories and functors. (All of this so far would be necessary even in the abstract approach outlined above.) We can then use these results as an aid to calculation when proving that V is well-defined and an equivalence; indeed, they are so powerful that detailed calculations can almost entirely be avoided.

Incidentally, the proofs of the coherence results for the unbiased theory are all absolutely straightforward. Just a little care is needed to keep track of the subscripts, but the proofs call for none of the ingenuity required in proving coherence for classical bicategories (see e.g. [JS, 1.1]).

The issue of large vs. small structures is not addressed here; it is left as a matter of conscience to the reader.

A.1. Coherence.

Preliminaries. To state our results we need some new language.

First recall the 2-category Cat-Gph from page 82 (Remark (e)). There is some extra structure on Cat-Gph: if B, B′ are Cat-graphs with B_{0} = B′_{0} = S, say, then there is a Cat-graph B ⊗ B′ defined by

(B ⊗ B′)_{0} = S, (B ⊗ B′)(s_{1}, s_{2}) = ∐_{s∈S} B(s_{1}, s) × B′(s, s_{2}).

There is also an object I_{S} of Cat-Gph defined by

(I_{S})_{0} = S,
(I_{S})(s_{1}, s_{2}) = \{ \begin{matrix}1 & if s_{1} = s_{2} \\ ∅ & otherwise. \end{matrix}

This defines a monoidal category structure on Cat^{S×S} for each set S.

Furthermore, if B ^{^{F}} C and B′ ^{F′} C′ are maps in Cat-Gph with B = B′ = S, say, C_{0} = C′_{0}, and F_{0} = F′_{0}, then there is a map F ⊗ F′ : B ⊗ B′ \overline{}C ⊗ C′ in Cat-Gph defined by

\begin{matrix}(F ⊗ F′)_{0} = F_{0} = F′_{0}, \\ (F ⊗ F′)_{s_{1},s_{2}}(p, p′) = (F_{s_{1},s}(p), F′_{s,s_{2}}(p′)) \end{matrix}

for s_{1}, s_{2}, s ∈ S, p ∈ B(s_{1}, s) and p′ ∈ B′(s, s_{2}). In particular, if B is a Cat-graph then there is a Cat-graph B^{⊗n} for each n ∈ ℕ, and if F : B \overline{}C is a map of Cat-graphs then there is a map F^{⊗n} : B^{⊗n} \overline{}C^{⊗n}. (So, for instance, the free 2-category functor on Cat-Gph is given by B ⟼ ∐_{n∈ℕ} B^{⊗n}.)

I will not attempt to describe exactly what structure is formed by Cat-Gph together with these tensor operations, although we will implicitly use some of its fairly obvious properties (such as functoriality of tensor). If we were discussing monoidal categories rather than bicategories, then the place of Cat-Gph would be taken by the monoidal category (Cat, ×, 1).

The definitions of unbiased bicategory and unbiased lax/weak functor can now be recast as follows. An unbiased bicategory consists of a Cat-graph B together with a functor comp_{n} : B^{⊗n} \overline{}B for each n ∈ ℕ and natural isomorphisms

[figure: B^{⊗(k_{1}+···+k_{n})}; B^{⊗n}; comp_{k_{1}+···+k_{n}}; ↙ γ_{k_{1},...,k_{n}}; B; comp_{n}] B^{⊗1} [figure: ∼; comp_{1}; ι] B

(where the horizontal arrow in the first diagram is comp_{k_{1}} ⊗ ⋯ ⊗ comp_{k_{n}}) satisfying associativity and identity axioms. An unbiased lax functor (F, ϕ) : B \overline{}B′ consists of a map F : B \overline{}B′ of Cat-graphs together with a natural transformation

B^{⊗n}  \overline{F^{⊗n} ^{}}B′^{⊗n}
[figure: ϕ_{n}]
[figure: B; comp_{n}; F; B′; comp_{n}]

for each n, satisfying axioms. (So unbiased bicategories are weak algebras, and unbiased lax functors are lax maps of weak algebras, for the free 2-category 2-monad on Cat-Gph.)

We will also need the language of trees. By definition, tr is the free (non-symmetric) operad (of sets) on the terminal object of Set^{ℕ}, as explained more fully in 3.3. Explicitly, we can define for each n ∈ ℕ a set tr(n) of n-leafed trees by the following recursive clauses:

• tr(1) has an element • (a formal symbol)

• if n ∈ ℕ and τ_{1} ∈ tr(k_{1}), …, τ_{n} ∈ tr(k_{n}), then tr(k_{1} + ⋯ + k_{n}) has an element (τ_{1}, …, τ_{n}).

(See Example 2.1.3(g) for why the word ‘tree’ is used.) We call • the unit tree, and define for each τ ∈ tr(n) and τ_{1} ∈ tr(k_{1}), …, τ_{n} ∈ tr(k_{n}) a composite tree τ^{∘}(τ_{1}, …, τ_{n}) as follows.

• If τ = • then τ^{∘}(τ_{1}) = τ_{1}

• Suppose τ = (σ_{1}, …, σ_{r}) with σ_{i} ∈ tr(n_{i}) and n_{1} +⋯+n_{r} = n: then we may write the sequence τ_{1}, …, τ_{n} as τ_{1}^{1}, …, τ_{1}^{n_{1}}, …, τ_{r}^{1}, …, τ_{r}^{n_{r}} and define

τ^{∘}(τ_{1}, …, τ_{n}) = (σ_{1}^{∘}(τ_{1}^{1}, …, τ_{1}^{n_{1}}), …, σ_{r}^{∘}(τ_{r}^{1}, …, τ_{r}^{n_{r}})).

Composition and unit obey associativity and unit laws: in other words, tr forms a nonsymmetric operad. Note also that if ν_{n} is the n-leafed tree (•, …, •) then (τ_{1}, …, τ_{n}) = ν_{n}^{∘}(τ_{1}, …, τ_{n}).

OPERADS IN HIGHER-DIMENSIONAL CATEGORY THEORY  169

Coherence for unbiased bicategories. Fix an unbiased bicategory B. Define for each n ∈ ℕ and τ ∈ tr(n) a functor comp_{τ} : B^{⊗n} \overline{}B, as follows:

• comp_{•} is the identity on B

• if τ_{1} ∈ tr(k_{1}), …, τ_{n} ∈ tr(k_{n}) then comp_{(τ_{1}, ... ,τ_{n})} is the composite

B^{⊗(k_{1}+···+k_{n})} comp_{τ_{1}} ⊗ ⋯ ⊗ comp_{τ_{n}} B^{⊗n} comp_{n}^{} B.

(More accurately, comp_{•} is not the identity but the canonical isomorphism B^{⊗1} \overline{}B. I will ignore such distinctions.) A.1.1. Proposition.

a. If τ ∈ tr(n), τ_{1} ∈ tr(k_{1}), …, τ_{n} ∈ tr(k_{n}) then

comp_{τ∘(τ_{1}, ... ,τ_{n})} = comp_{τ}^{∘}(comp_{τ_{1}} ⊗ ⋯ ⊗ comp_{τ_{n}})

b. comp_{•} = id

c. comp_{ν_{n}} = comp_{n}. Proof. Part (a) is a straightforward induction on the structure of τ. Part (b) is just the definition of comp_{•}. Part (c) is also straightforward.

Next define for each tree τ ∈ tr(n) a natural isomorphism ω_{τ} : comp_{τ} \overline{}comp_{n}, by • ω_{•} = ι : id \overline{}comp_{1}

• if τ_{1} ∈ tr(k_{1}), …, τ_{n} ∈ tr(k_{n}) then ω_{(τ_{1}, ... ,τ_{n})} is the composite

comp_{(τ_{1}, ... ,τ_{n})} = comp_{n}^{∘}(comp_{τ_{1}} ⊗ ⋯ ⊗ comp_{τ_{n}})
^{1∗(ω_{τ_{1}}⊗···⊗ω_{τn})} comp_{n}^{∘}(comp_{k_{1}} ⊗ ⋯ ⊗ comp_{k_{n}})
^{γ_{k_{1},...,kn}}  comp_{k_{1}+···+k_{n}}.

The ω_{τ}’s fit together coherently, as expressed by the following result.

170  TOM LEINSTER

A.1.2. Proposition.

a. If τ ∈ tr(n), τ_{1} ∈ tr(k_{1}), …, τ_{n} ∈ tr(k_{n}) then

comp_{τ∘(τ_{1}, ... ,τ_{n})} {= \atop =} comp_{τ}^{∘}(comp_{τ_{1}} ⊗ ⋯ ⊗ comp_{τ_{n}})

comp_{n}^{∘}(comp_{k_{1}} ⊗ ⋯ ⊗ comp_{k_{n}}) ω_{τ} ∗ (ω_{τ_{1}} ⊗ ⋯ ⊗ ω_{τ_{n}})_{}

[figure: comp_{k_{1}+···+k_{n}}; ω_{τ∘(τ_{1}, ... ,τ_{n})}; = = = = = = = = = = = =; comp_{k_{1}+···+k_{n}}; γ_{k_{1},...,k_{n}}]

commutes b. The diagram

comp_{•} = = = = = = = id

[figure: comp_{1}; ω_{•}; = = = = =; comp_{1}; ι]

commutes c. ω_{ν_{n}} = 1, ω_{ν_{n}∘(ν_{k_{1}}, ... ,ν_{kn})} = γ_{k_{1},...,k_{n}}, and ω_{•} = ι.

Proof. As in the previous proof, (a) is by induction on τ, (b) is immediate, and (c) is straightforward.

Everything so far works for lax bicategories, but the next part does not. For each τ, τ′ ∈ tr(n), define a natural isomorphism

ω_{τ,τ′} = (comp_{τ} ^{ω_{τ}} comp_{n} ^{ω_{τ′}^{−1}} comp_{τ′}).

The ω_{τ,τ′}’s also fit together coherently: A.1.3. Theorem.

a. If τ, τ′ ∈ tr(n), τ_{1}, τ′_{1} ∈ tr(k_{1}), …, τ_{n}, τ′_{n} ∈ tr(k_{n}) then

comp_{τ∘(τ_{1}, ... ,τ_{n})} = = = = = comp_{τ}^{∘}(comp_{τ_{1}} ⊗ ⋯ ⊗ comp_{τ_{n}})

[figure: comp_{τ′∘(τ′_{1}, ... ,τ′_{n})}; ω_{τ∘(τ_{1}, ... ,τn),τ′∘(τ′_{1}, ... ,τ′_{n})}; = = = = =; comp_{τ′}^{∘}(comp_{τ′_{1}} ⊗ ⋯ ⊗ comp_{τ′_{n}}); ω_{τ,τ′}∗(ω_{τ_{1},τ′_{1}}⊗···⊗ω_{τn,τ′_{n}})]

commutes

b. ω_{τ′,τ′′}^{∘}ω_{τ,τ′} = ω_{τ,τ′′} and ω_{τ,τ} = 1

c. ω_{ν_{n}∘(ν_{k_{1}}, ... ,ν_{kn}),ν_{k_{1}+···+kn}} = γ_{k_{1},...,k_{n}} and ω_{•,ν_{1}} = ι

Proof. (b) is immediate, and (a) and (c) follow from Proposition A.1.2.

The theorem says that for any pair of n-leafed trees τ and τ′, there is precisely one map comp_{τ} \overline{}comp_{τ′} which can be built up from γ and ι. In short, there is a single canonical isomorphism between comp_{τ} and comp_{τ′}: ‘coherence for an unbiased bicategory’.

This is a little different from the usual formulation of bicategorical coherence, in that we have not directly discussed graph maps B^{⊗n} \overline{}B^{⊗m} (or transformations between them) built up from the bicategory operations, except in the case m = 1. This is a feature of the tree-based (operadic) approach; it seems cleaner and, in any case, what we have done is enough for our present purpose.

Coherence for unbiased lax functors. Fix an unbiased lax functor (F, ϕ) : B \overline{}B′. I will use the same notation γ, ι, comp and ω in both B and B′; confusion should not arise.

Define for each n ∈ ℕ and τ ∈ tr(n) a natural transformation

ϕ_{τ} : comp_{τ}^{∘}F^{⊗n} \overline{}F^{∘}comp_{τ}

by

• ϕ_{•} is the identity (or again, more precisely, the canonical isomorphism)

• if τ_{1} ∈ tr(k_{1}), …, τ_{n} ∈ tr(k_{n}) then ϕ_{(τ_{1}, ... ,τ_{n})} is the composite

comp_{(τ_{1}, ... ,τ_{n})}^{∘}F^{⊗(k_{1}+···+k_{n})}
=  comp_{n}^{∘}((comp_{τ_{1}}^{∘}F^{⊗k_{1}}) ⊗ ⋯ ⊗ (comp_{τ_{n}}^{∘}F^{⊗k_{n}}))
^{1∗(ϕ_{τ_{1}}⊗···⊗ϕ_{τn})} comp_{n}^{∘}((F^{∘}comp_{τ_{1}}) ⊗ ⋯ ⊗ (F^{∘}comp_{τ_{n}}))
=  comp_{n}^{∘}F^{⊗n}^{∘}(comp_{τ_{1}} ⊗ ⋯ ⊗ comp_{τ_{n}})
^{ϕ_{n}∗1}  F^{∘}comp_{n}^{∘}(comp_{τ_{1}} ⊗ ⋯ ⊗ comp_{τ_{n}})
=  F^{∘}comp_{(τ_{1}, ... ,τ_{n})}.

Once again we have a coherence result.

A.1.4. Proposition.

172  TOM LEINSTER

a. If τ ∈ tr(n), τ_{1} ∈ tr(k_{1}), …, τ_{n} ∈ tr(k_{n}) then

comp_{τ∘(τ_{1}, ... ,τ_{n})}^{∘}F^{⊗(k_{1}+···+k_{n})} {= \atop =} comp_{τ}^{∘}((comp_{τ_{1}}^{∘}F^{⊗k_{1}}) ⊗ ⋯ ⊗ (comp_{τ_{n}}^{∘}F^{⊗k_{n}}))

comp_{τ}^{∘}F^{⊗n}^{∘}(comp_{τ_{1}} ⊗ ⋯ ⊗ comp_{τ_{n}}) 1 ∗ (ϕ_{τ_{1}} ⊗ ⋯ ⊗ ϕ_{τ_{n}})_{}

[figure: F^{∘}comp_{τ∘(τ_{1}, ... ,τ_{n})}; ϕ_{τ∘(τ_{1}, ... ,τ_{n})}; = = = = = = = = = = = = =; F^{∘}comp_{τ}^{∘}(comp_{τ_{1}} ⊗ ⋯ ⊗ comp_{τ_{n}}); ϕ_{τ} ∗ 1]

commutes b. The diagram

comp_{•}^{∘}F^{⊗1} = = = = = = F

[figure: F^{∘}comp_{•}; ϕ_{•}; = = = = = = =; F; 1]

commutes c. ϕ_{ν_{n}} = ϕ_{n}.

Proof. (a) is by induction on τ; (b) and (c) are immediate.

At this point, we have for each τ ∈ tr(n) a canonical map

ϕ_{τ} : comp_{τ}^{∘}F^{⊗n} \overline{}F^{∘}comp_{τ}

built up from ϕ_{n}’s only. Next we bring in the coherence isomorphisms ω of B and B′. A.1.5. Proposition. If τ, τ′ ∈ tr(n) then

comp_{τ}^{∘}F^{⊗n} \overline{ϕ_{τ}_{}}F^{∘}comp_{τ}

[figure: comp_{τ′}^{∘}F^{⊗n}; ω_{τ,τ′} ∗ 1; ϕ_{τ′}; F^{∘}comp_{τ′}; 1 ∗ ω_{τ,τ′}]

(24)

commutes. Proof. It is enough to prove this when τ′ = ν_{n}, in which case ω_{τ,τ′} = ω_{τ}. The proof is then another easy induction on τ.

OPERADS IN HIGHER-DIMENSIONAL CATEGORY THEORY  173

For τ, τ′ ∈ tr(n), define

ϕ_{τ,τ′} : comp_{τ}^{∘}F^{⊗n} \overline{}F^{∘}comp_{τ′}

as the diagonal of (24). We then have: A.1.6. Theorem.

a. If τ, τ′, σ, σ′ ∈ tr(n) then the diagrams

comp_{τ}^{∘}F^{⊗n} \overline{ϕ_{τ,τ′}_{}}F^{∘}comp_{τ′}
[figure: ϕ_{τ,σ′}]
F^{∘}comp_{σ′} 1 ∗ ω_{τ′,σ′}_{}

comp_{τ}^{∘}F^{⊗n} \overline{ω_{τ,σ} ∗ 1_{}}comp_{σ}^{∘}F^{⊗n}
[figure: ϕ_{τ,σ′}]
F^{∘}comp_{σ′} ϕ_{σ,σ′}_{}

commute b. If τ, τ′ ∈ tr(n), τ_{1}, τ′_{1} ∈ tr(k_{1}), …, τ_{n}, τ′_{n} ∈ tr(k_{n}), then

comp_{τ∘(τ_{1}, ... ,τ_{n})}^{∘}F^{⊗(k_{1}+···+k_{n})} {= \atop =} comp_{τ}^{∘}((comp_{τ_{1}}^{∘}F^{⊗k_{1}}) ⊗ ⋯ ⊗ (comp_{τ_{n}}^{∘}F^{⊗k_{n}}))
comp_{τ}^{∘}F^{⊗n}^{∘}(comp_{τ′_{1}} ⊗ ⋯ ⊗ comp_{τ′_{n}})^{^{1∗(ϕ_{τ_{1},τ′_{1}}⊗···⊗ϕ_{τn,τ′_{n}})}}
[figure: F^{∘}comp_{τ′∘(τ′_{1}, ... ,τ′_{n})}; ϕ_{τ∘(τ_{1}, ... ,τn),τ′∘(τ′_{1}, ... ,τ′_{n})}; = = = = = = = = = = = =; F^{∘}comp_{τ′}^{∘}(comp_{τ′_{1}} ⊗ ⋯ ⊗ comp_{τ′_{n}}); ϕ_{τ,τ′}∗1]

commutes c. ϕ_{•,•} : comp_{•}^{∘}F^{⊗1} \overline{}F^{∘}comp_{•} is the identity d. ϕ_{ν_{n},ν_{n}} = ϕ_{n}.

Proof. These all follow from the last two propositions.

This theorem is ‘coherence for an unbiased lax functor’ (F, ϕ): there is precisely one map

comp_{τ}^{∘}F^{⊗n} \overline{}F^{∘}comp_{τ′}

built up from ϕ and the coherence cells γ and ι of B and B′.

A warning is due here. We have shown that, for instance, any two maps

((F f_{4}^{∘}F f_{3})^{∘}1^{∘}(F f_{2}^{∘}F f_{1})) [figure] F (f_{4}^{∘}(f_{3}^{∘}f_{2}^{∘}f_{1}))

built up from coherence cells are equal. The form of the codomain is important, being F applied to a composite of 1-cells in B. In contrast, a counterexample in the introduction to [Lew] shows that there can be two distinct maps

F 1 [figure] F 1^{∘}F 1

built up from coherence cells. (The counterexample is stated in the context of classical bicategories—in fact, monoidal categories—but translates easily to the unbiased context.)

Summary. We have articulated the following coherence principles for the unbiased theory:

(UB) In an unbiased bicategory B, there is a unique natural isomorphism

comp_{τ}  \overline{}comp_{τ′}

built up from γ and ι, for any pair τ, τ′ of trees with the same number of leaves

(UF) For an unbiased lax functor (F, ϕ) : B \overline{}B′, there is a unique natural transfor-

mation

comp_{τ}^{∘}F^{⊗n} \overline{}F^{∘}comp_{τ′}

built up from ϕ, γ and ι, for any pair τ, τ′ of n-leafed trees.

We will also need to use similar coherence principles for classical bicategories. To state them, we define the set ctr(k) of k-leafed classical trees for each k ∈ ℕ by exactly the same recursive clauses as we used in the definition of tr (page 168), but only allowing n ∈ {0, 2} instead of n ∈ ℕ in the second clause. As in the unbiased case, we can define for each classical bicategory C, each n ∈ ℕ and each τ ∈ ctr(n), a functor comp_{τ} : C^{⊗n} \overline{}C. We then have the following coherence principles for the classical theory:

(CB) In a classical bicategory C, there is a unique natural isomorphism

comp_{τ}  \overline{}comp_{τ′}

built up from the associativity and unit isomorphisms, for any pair τ, τ′ of classical trees with the same number of leaves (CF) For a classical lax functor (G, ψ) : C \overline{}C′, there is a unique natural transforma-

tion

comp_{τ}^{∘}G^{⊗n} \overline{}G^{∘}comp_{τ′}

built up from ψ and the associativity and unit isomorphisms, for any pair τ, τ′ of n-leafed classical trees.

Principle (CB) follows from the classical coherence theorem for bicategories, in the form ‘every diagram commutes’. (CF) comes from Lewis’s paper [Lew].

A.2. The proof. We can now prove that UBicat_{lax} ≃ Bicat_{lax} and UBicat_{wk} ≃ Bicat_{wk} with almost no real work.

Recall from 1.3 that we attempted to construct a functor

V : UBicat_{lax} \overline{}Bicat_{lax};

that is, we specified all the necessary data for V but did not check any of the axioms. Here we must check these axioms, and must prove that V is full, faithful and surjective on objects. The easiest way to deduce the latter from our results so far is to construct a pseudo-inverse L to V, with V^{∘}L = 1.

Explicitly, take a (classical) bicategory C, and write its composition and identity as Cat-graph maps

I_{C_{0}} ^{ids} C ^{comp} C ⊗ C.

Attempt to define an unbiased bicategory B = L(C) by setting B equal to C as a Catgraph, putting

comp_{0} = ids, comp_{1} = 1_{B},

comp_{n+1} = (B^{⊗(n+1)} ≅ C^{⊗n} ⊗ C ^{comp_{n}⊗1_{C}} C ⊗ C ^{comp} C = B)

(n ≥ 1), and taking γ and ι to be the canonical isomorphisms (which exist by coherence principle (CB)). (So this choice of a pseudo-inverse is an arbitrary one; we have decided to ‘associate to the left’.) Given a classical lax functor (G, ψ) : C \overline{}C′, attempt to define an unbiased lax functor

(F, ϕ) = L(G, ψ) : L(C) \overline{}L(C′)

by setting F = G and taking ϕ_{f_{1},...,f_{n}} to be the canonical map

(F f_{n}^{∘} ⋯^{∘}F f_{1}) \overline{}F (f_{n}^{∘} ⋯^{∘}f_{1}),

which makes sense by coherence principle (CF).

So far we have attempted to construct functors

UBicat_{lax} [figure: V; L] Bicat_{lax},

and we will show that V L = 1 and LV ≅ 1. For the latter we attempt to construct unbiased weak functors

B [figure: (Θ_{B},θ_{B}); (Ξ_{B},ξ_{B})] LV (B)

for each unbiased bicategory B. This is done by taking Θ_{B} and Ξ_{B} each to be the identity on B (in Cat-Gph), and by taking θ_{B} and ξ_{B} to be the canonical isomorphisms (which exist by coherence principle (UB)).

Theorem 1.3.1 now follows from:

A.2.1. Proposition. With the definitions above, V and L are both functors, V L = 1,

and 1 [figure: (Θ,θ); (Ξ,ξ)] LV are mutually inverse natural transformations.

Proof. Essentially we have to check that our data satisfies a large collection of axioms, but our coherence results cover almost all of these checks automatically. Here is the list of the things to be checked and which coherence result each one can be inferred from.

• V is a functor UBicat_{lax} \overline{}Bicat_{lax}. This means:

– V (B) is a bicategory for any B: (UB)

– V (F, ϕ) is a lax morphism for any (F, ϕ): (UF)

– V preserves identities: (UB)

– V preserves composition: really we should deduce this from ‘coherence for a composable pair of unbiased lax morphisms’ (which we did not prove), but a direct check is easy.

• L is a functor Bicat_{lax} \overline{}UBicat_{lax}. This means:

– L(C) is an unbiased bicategory for any C: (CB)

– L(G, ψ) is an unbiased lax functor for any (G, ψ): (CF)

– L preserves identities: (CB)

– L preserves composition: as for V above.

• V L = 1. This means:

– V L(C) = C for any C: by construction, V L(C) and C are the same in all respects except perhaps their associativity and unit isomorphisms; and these too are equal by (CB)

– V L(G, ψ) = (G, ψ) for any (G, ψ): (CF).

• 1 [figure: (Θ,θ); (Ξ,ξ)] LV are natural transformations. This means:

– B [figure: (Θ_{B},θ_{B}); (Ξ_{B},ξ_{B})] LV (B) are unbiased lax functors for any B: (UB)

– (Θ_{B}, θ_{B}) and (Ξ_{B}, ξ_{B}) are natural in B: (UF).

• (Θ_{B}, θ_{B})^{∘}(Ξ_{B}, ξ_{B}) = 1 and (Ξ_{B}, ξ_{B})^{∘}(Θ_{B}, θ_{B}) = 1 for any B: (UB).

Evidently L sends weak functors to unbiased weak functors, and so restricts to a functor L_{wk} : Bicat_{wk} \overline{}UBicat_{wk}. Moreover, both (Θ_{B}, θ_{B}) and (Ξ_{B}, ξ_{B}) are unbiased weak functors, for any unbiased bicategory B. Hence:

A.2.2. Corollary. The functors

UBicat_{wk} [figure: V_{wk}; L_{wk}] Bicat_{wk}

satisfy V_{wk}L_{wk} = 1 and L_{wk}V_{wk} ≅ 1.

Corollary 1.3.2 follows immediately.

B. The free multicategory construction

In this appendix we define ‘suitability’ and sketch proofs of Theorems 3.3.1, 3.3.2 and 3.3.3. First we need some terminology.

Let E be a category with pullbacks, 𝕀 a small category, D : 𝕀 \overline{}E a functor for which a colimit exists, and (D(I) \overline{}Z)_{I∈𝕀} a colimit cone. We say that the colimit is stable under pullback if for any map Z′ \overline{}Z in E, the cone (D′(I) \overline{}Z′)_{I∈𝕀} is a colimit cone; here D′ and the new cone are obtained by pullback, so that

[figure: D′; D; Z′; Z]

is a pullback square in the functor category [𝕀, E].

The morphisms k_{I} in a colimit cone (D(I) ^{k_{I}} Z)_{I∈𝕀} will be called the coprojections of the colimit, and in particular we say that the colimit of D ‘has monic coprojections’ to mean that each k_{I} is monic.

A category will be said to have disjoint finite coproducts if it has finite coproducts, these coproducts have monic coprojections, and for any pair A, B of objects, the square

[figure: 0; B; A; A + B]

is a pullback.

Let ω be the natural numbers with their usual ordering. A nested sequence in a category E is a functor ω \overline{}E in which the image of every morphism of ω is monic. In other words, it is a diagram

A_{0} > > A_{1} > > ⋯

in E, where as usual > > indicates a monic. Note that a functor which preserves pullbacks also preserves monics, so it makes sense for such a functor to ‘preserve colimits of nested sequences’. Similarly, it makes sense to say that colimits of nested sequences commute with pullbacks, where ‘commute’ is used in the same sense as when we say that filtered colimits commute with finite limits in Set.

A category E is suitable if it satisfies

C1 E is cartesian

C2 E has disjoint finite coproducts which are stable under pullback

C3 E has colimits of nested sequences; these commute with pullbacks and have monic coprojections.

A monad (T, η, μ) is suitable if it satisfies

M1 (T, η, μ) is cartesian

M2 T preserves colimits of nested sequences.

We say that (E, T) is suitable when (T, η, μ) is a suitable monad on a suitable category E.

We now sketch a proof of the main theorem, 3.3.1, on the formation of free multicategories, which for convenience is re-stated here.

Theorem 3.3.1 Let (E, T) be suitable. Then the forgetful functor

(E, T)-Multicat ^{^{U}} E′ = (E, T)-Graph

has a left adjoint, the adjunction is monadic, and if T′ is the resulting monad on E′ then (E′, T′) is suitable.

Proof (sketch). We proceed in four steps:

a. construct a functor F : E′ \overline{}(E, T)-Multicat

b. construct an adjunction between F and U

c. check that (E′, T′) is suitable

d. check that the adjunction is monadic.

Each step goes roughly as follows. a. Construct a functor F : E′ \overline{}(E, T)-Multicat

Let X be a T -graph. Define for each n a graph T X_{0} ^{d_{n}} A_{n} ^{c_{n}} X_{0}, by

• A_{0} = X_{0}, d_{0} = η_{X_{0}} and c_{0} = 1

• A_{n+1} = X_{0}+X_{1}^{∘}A_{n}, where X_{1}^{∘}A_{n} is the 1-cell composite in (E, T)-Span, with the obvious choices of d_{n+1} and c_{n+1}.

Define for each n a map A_{n} ^{i_{n}} A_{n+1}, by

• i_{0} : X_{0} \overline{}X_{0} + X_{1}^{∘}X_{0} is first coprojection

• i_{n+1} = 1_{X_{0}} + (1_{X_{1}} ∗ i_{n}).

Then the i_{n}’s are monic, and by taking A to be the colimit of

A_{0} >^{i_{0}}> A_{1} >^{i_{1}}> ⋯

we obtain a graph T X_{0} \underline{}A \overline{}X_{0}. This graph naturally has the structure of a multicategory: the identities map X_{0} \overline{}A is just the colimit coprojection A_{0} > > A, and composition comes from maps A_{m}^{∘}A_{n} \overline{}A_{m+n} which piece together to give a map A^{∘}A \overline{}A. The composition construction needs many of the suitability axioms.

We have now described what effect F is to have on objects, and extension to morphisms is straightforward.

(The colimit of the nested sequence of A_{n}’s appears, in light disguise, as the recursive description of the free plain multicategory monad in 3.3: A_{n} is the set of formal expressions which can be obtained from the first clause and up to n applications of the second clause.)

b. Construct an adjunction between F and U We do this by constructing unit and counit transformations and verifying the triangle identities. Both transformations are the identity on the object of objects, so we only need to define them on the object of arrows. For the unit η′, if X ∈ E′ then η′_{X} : X_{1} \overline{}A is the composite

X_{1} ^{∼} X_{1}^{∘}X_{0} >^{copr_{2}} > X_{0} + X_{1}^{∘}X_{0} = A_{1} > > A.

For the counit ε′, let C ∈ (E, T)-Multicat. Write A and A_{n} for the objects used in the construction of the free multicategory on U(C), as if X = U(C) in part (a). Define for each n a map ε′_{C,n} : A_{n} \overline{}C_{1} by

• ε′_{C,0} = (A_{0} ^{=} C_{0} ^{ids} C_{1})

• ε′_{C,n+1} = (C_{0} + C_{1}^{∘}A_{n} ^{1+1∗ε′_{C,n}} C_{0} + C_{1}^{∘}C_{1} ^{^{q}} C_{1}), where q is ids on the first

summand and comp on the second,

and then there is a unique ε′_{C} : A \overline{}C_{1} such that

ε′_{C,n} = (A_{n} > > A ^{ε′_{C}} C_{1})

for all n.

c. Check that (E′, T′) is suitable This is quite routine.

d. Check that the adjunction is monadic We apply the Monadicity Theorem by checking that U creates coequalizers for Uabsolute coequalizer pairs. This can be done quite separately from the rest of the proof, and again is quite routine.

We can now easily prove the fixed-object version, Theorem 3.3.2. Recall that E′_{S} is the category of T -graphs on S (that is, E/(T S × S)) and (E, T)-Multicat_{S} is the category of T -multicategories on S.

Theorem 3.3.2 Let (E, T) be suitable and let S ∈ E. Then the forgetful functor

(E, T)-Multicat_{S} \overline{}E′_{S}

has a left adjoint, the adjunction is monadic, and if T′_{S} is the resulting monad on E′_{S} then (E′_{S}, T′_{S}) is suitable. Moreover, if E has filtered colimits and T preserves them, then the same is true of E′_{S} and T′_{S}.

Proof. It is evident from the proof of 3.3.1 that the adjunction (F, U, η′, μ′) constructed there restricts to the subcategories E′_{S} and (E, T)-Multicat_{S}, so we only have to check that (E′_{S}, T′_{S}) is suitable and the restricted adjunction is monadic. This is again quite routine, and involves many of the same calculations. (The most substantial difference between the two cases is that coproducts in E′ and E′_{S} are calculated differently, i.e. the inclusion E′_{S} ^{⊂} ^{}E′ does not preserve them.) ‘Moreover’ is straightforward.

Finally, we have to prove Theorem 3.3.3: that any functor category [𝔼, Set], and any finitary cartesian monad on it, is suitable. Since the category ω is filtered, the monad part is immediate. For the category part it is enough to see that Set is suitable, and this follows straight away from standard results.

C. Strict ω-categories

In this appendix we prove:

C.0.3. Theorem. The forgetful functor ω-Cat \overline{}G_{ω} has a left adjoint, the adjunction is monadic, and the induced monad on G_{ω} is cartesian and finitary.

Here ω-Cat is the category of strict ω-categories and G_{ω} is the category of globular sets. We need to know that the left adjoint exists and that the induced monad T is cartesian in order to be able to talk about T -operads (as we do in Section 4), we need monadicity in order to understand the definition of weak ω-category (Section 4 again), and we need to know that T is finitary in Appendix D.

In C.1 we recall the basics of strict ω-categories and strict n-categories, and outline the strategy for proving Theorem C.0.3. Subsection C.2 is devoted to the proof itself. In subsection C.3 we show that T acts on globular sets X by the formula

(T X)(n) ≅ ∐_{π∈pd(n)} [𝔾, Set](π̂, X),

as asserted in Section 4 (page 144).

C.1. Outline. Let V be a category with finite products. Then there is a category V-Cat of V-enriched categories and V-enriched functors, which also has finite products. Moreover, if F : V \overline{}W is a functor which preserves finite products then there is an induced functor F_{∗} : V-Cat \overline{}W-Cat, which also preserves finite products. Here, as everywhere in this appendix, the monoidal structure on the categories we are enriching in is always the cartesian product, and our enriched categories will always have just a set of objects—nothing larger.

These observations allow us to make the following definitions. For n ∈ ℕ, define the category n-Cat of strict n-categories and strict n-functors by

0-Cat = Set,
(n + 1)-Cat = (n-Cat)-Cat.

Also define functors S_{n} : (n + 1)-Cat \overline{}n-Cat, by taking S_{0} : Cat \overline{}Set to be the objects functor and S_{n+1} = (S_{n})_{∗}.

We thus have a diagram

⋯ \overline{}(n + 1)-Cat ^{S_{n}} n-Cat ^{S_{n−1}} ⋯ ^{S_{0}} 0-Cat = Set

in CAT, and the category ω-Cat of strict ω-categories and strict ω-functors is defined as the limit of this diagram. (CAT is the category of all categories, possibly large.)

Now let 𝔾_{ω} be the category denoted 𝔾 in 4.1, and let G_{ω} = [𝔾_{ω}, Set] (the category of globular sets). For n ∈ ℕ, let 𝔾_{n} be the full subcategory of 𝔾_{ω} with objects 0, …, n, let G_{n} = [𝔾_{n}, Set], and call objects of G_{n} n-globular sets. The inclusions 𝔾_{n} ^{⊂} ^{}𝔾_{n+1} give rise to a diagram

⋯ \overline{}G_{n+1} ^{R_{n}} G_{n} ^{R_{n−1}} ⋯ ^{R_{0}} G_{0} ≅ Set

in CAT, of which G_{ω} is the limit.

The next step is to see that there is a forgetful functor

U_{n} : n-Cat \overline{}G_{n}

for each n, expressing the idea that an n-globular set is the underlying graph structure of an n-category.

Formally, we first define for each category V the category V-Gph, in which an object is a set X_{0} together with an indexed family (X(x, x′))_{x,x′∈X_{0}} of objects of V, and a map f : X \overline{}Y consists of a function f_{0} : X_{0} \overline{}Y_{0} together with a map f_{x,x′} : X(x, x′) \overline{}Y (f_{0}x, f_{0}x′) in V for each x, x′ ∈ X_{0}. Objects of V-Gph will be called V-graphs (not to be confused with the T -graphs defined in 2.2). Observe that:

• if V has finite products then so does V-Gph, and the evident forgetful functor V-Cat \overline{}V-Gph preserves finite products

• if V and W have finite products and V \overline{}W is a functor preserving them, then the evident functor V-Gph \overline{}W-Gph also preserves them

• in the situation of the previous item, the diagram

V-Cat \overline{}W-Cat

[figure: V-Gph; W-Gph]

commutes, which means that there is an unambiguous functor V-Cat \overline{}W-Gph induced by the functor V \overline{}W.

To apply this to the current situation, note that G_{n+1} ≃ G_{n}-Gph; then take U_{0} : Set \overline{}Set to be the identity and define U_{n+1} : (n+1)-Cat \overline{}G_{n+1} to be the functor

(n-Cat)-Cat \overline{}G_{n}-Gph

induced by U_{n} : n-Cat \overline{}G_{n}. (All the conditions on finite products go through.) These U_{n}’s commute with the restriction functors R_{n} and S_{n}, so we obtain a forgetful functor U_{ω} : ω-Cat \overline{}G_{ω}:

[figure: ω-Cat; ⋯; (n + 1)-Cat; S_{n}; n-Cat; S_{n−1}; ⋯; S_{0}; 0-Cat]

[figure: G_{ω}; U_{ω}; ⋯; G_{n+1}; U_{n+1}; R_{n}; G_{n}; U_{n}; R_{n−1}; ⋯; R_{0}; G_{0}.; U_{0}]

Having constructed U_{ω}, we have given a precise meaning to Theorem C.0.3. (‘Finitary’ means ‘preserves filtered colimits’.) In order to prove the Theorem, it is enough to prove:

C.1.1. Theorem. Let n ∈ ℕ. Then

a. the forgetful functor U_{n} : n-Cat \overline{}G_{n} has a left adjoint F_{n}, the adjunction is monadic, and the induced monad T_{n} on G_{n} is cartesian and finitary

b. R_{n} is a weak map of monads (G_{n+1}, T_{n+1}) \overline{}(G_{n}, T_{n}), and S_{n} is the map G_{n+1}^{T_{n+1}} \overline{}G_{n}^{T_{n}} induced by R_{n}.

By a weak map of monads I mean a monad functor (or equivalently, opfunctor) whose natural transformation part is an isomorphism: thus there is an isomorphism between T_{n}^{∘}R_{n} and R_{n}^{∘}T_{n+1} which respects unit and multiplication. Because it is a monad functor, there is an induced functor G_{n+1}^{T_{n+1}} \overline{}G_{n}^{T_{n}}, and therefore (n + 1)-Cat \overline{}n-Cat.

Theorem C.0.3 follows almost immediately from Theorem C.1.1. The only sticking point is that the squares

[figure: (n + 1)-Cat; S_{n}; n-Cat; G_{n+1}; F_{n+1}; R_{n}; G_{n}; F_{n}]  (25)

do not a priori commute strictly, only up to (canonical) isomorphism. Since G_{ω} and ω-Cat are strict (not 2-categorical) limits, this means that the functors F_{n} do not necessarily induce a functor F_{ω} : G_{ω} \overline{}ω-Cat. But we can, in fact, choose the left adjoints F_{n} so that each canonical isomorphism inside (25) is the identity, and the situation is then rescued. The key is that the functors S_{n} have the following (easily proved) isomorphismlifting property: if C ∈ (n + 1)-Cat and j : S_{n}(C) ^{∼} D is an isomorphism in n-Cat, then there is an isomorphism i : C ^{∼} C′ in (n + 1)-Cat with S_{n}C′ = D and S_{n}i = j. This allows us to choose left adjoints F_{0}, F_{1}, … successively so that everything is strictly commutative, which is just what we need.

C.2. The proof. In this subsection we prove Theorem C.1.1. The core of the argument is contained in the following result:

C.2.1. Proposition. Let 𝔸 be a small category and A = [𝔸, Set]. Let (T, η, μ) be a monad on A such that T preserves all coproducts. Then

a. the forgetful functor A^{T} -Cat \overline{}A-Gph is monadic and preserves all coproducts

b. if (T, η, μ) is cartesian then so is the induced monad (T̃, η̃, μ̃) on A-Gph

c. if T is finitary then so is T̃.

C.2.2. Remarks. The ‘forgetful functor’ in the first part is induced by the forgetful functor A^{T} \overline{}A, where A^{T} is the category of T -algebras. Since A has all limits and a monadic functor creates limits, A^{T} has all limits—and in particular pullbacks, so that it makes sense to discuss A^{T} -Cat.

Parts (b) and (c) make sense even if A-Gph does not have all pullbacks or all filtered colimits. But in fact, A-Gph has all limits and colimits. This follows from the observation that A-Gph ≃ [𝔸̃, Set], where 𝔸̃ is the category obtained from 𝔸 by adjoining a new object

0 and a pair of morphisms A [figure: σ_{A}; τ_{A}] 0 for each A ∈ 𝔸, with σ_{A}^{∘}f = σ_{A′} and τ_{A}^{∘}f = τ_{A′} for any morphism f : A′ \overline{}A in 𝔸.

It is not necessary to insist that A is of the form [𝔸, Set] in order to make the proof work. We could get by on the assumption that A has finite limits and all (small) colimits, and that these interact in suitable ways: e.g. that × distributes over coproduct. But we do not need such a precise result, and by working in [𝔸, Set] we can manipulate limits and colimits as if we were in Set.

Before proving the Proposition, let us apply it to prove part (a) of Theorem C.1.1. The proof is by induction on n, adding in the hypothesis that the functor T_{n} preserves all (small) coproducts. When n = 0, the forgetful functor U_{0} is an isomorphism, and its inverse F_{0} is a left adjoint; thus the induced monad T_{0} on G_{0} is the identity. For the inductive step we just take 𝔸 = 𝔾_{n} and T = T_{n} in Proposition C.2.1, noting that under the equivalences A^{T} -Cat ≃ (n + 1)-Cat and A-Gph ≃ G_{n+1}, the forgetful functor A^{T} -Cat \overline{}A-Gph becomes U_{n+1} : (n + 1)-Cat \overline{}G_{n+1}.

Proof of Proposition C.2.1. The strategy is to construct two monads P and Q on A-Gph and a distributive law Q^{∘}P \overline{}P^{∘}Q (in the sense of [Str1, §6]). This gives the functor T̃ = Q^{∘}P the structure of a monad on A-Gph. We then show that (A-Gph)T̃ ≅ A^{T} -Cat, and that the diagram

(A-Gph)T̃ ≅ A^{T} -Cat
[figure]
A-Gph

(in which the two arrows are the forgetful functors) commutes. Part (a) follows, and by our construction of T̃, (b) and (c) are easy consequences. The idea behind this strategy is that to form the free A^{T} -category on an A-graph X, one first forms the free T -algebra on each ‘hom-object’ X(x, x′), then one forms the free A^{T} -category on the resulting A^{T} - graph.

So, the functor T : A \overline{}A induces a functor P : A-Gph \overline{}A-Gph: explicitly, (P X)_{0} = X_{0} and (P X)(x, x′) = T (X(x, x′)) for x, x′ ∈ X_{0}. Similarly, the unit and multiplication of T give P the structure of a monad on A-Gph.

A second monad Q on A-Gph is given by the forgetful functor

A-Cat \overline{}A-Gph

and its left adjoint. Explicitly, if X ∈ A-Gph then (QX)_{0} = X_{0} and

(QX)(x, x′) = ∐_{x=x_{0},...,x_{r}=x′} X(x_{0}, x_{1}) × ⋯ × X(x_{r−1}, x_{r}),

where the coproduct is over all r ∈ ℕ and x_{0}, …, x_{r} ∈ X_{0} such that x_{0} = x and x_{r} = x′. Everything works in the familiar way—that is, as for the free category monad on G_{1}— because A is a functor category [𝔸, Set].

A distributive law λ : P Q \overline{}QP is given as follows. If X ∈ A-Gph then

(P QX)_{0} = X_{0},
(P QX)(x, x′) = T ((QX)(x, x′))
≅ ∐_{x=x_{0},...,x_{r}=x′} T {X(x_{0}, x_{1}) × ⋯ × X(x_{r−1}, x_{r})}

(since T preserves coproducts), and

(QP X)_{0} = X_{0},
(QP X)(x, x′) = ∐_{x=x_{0},...,x_{r}=x′} T (X(x_{0}, x_{1})) × ⋯ × T (X(x_{r−1}, x_{r})),

for x, x′ ∈ X_{0}. So there is a map

(P QX)(x, x′) \overline{}(QP X)(x, x′)

defined by projections, giving a map

λ_{X} : P QX \overline{}QP X

of A-graphs which is the identity on objects. The axioms for a distributive law then hold.

P, Q and λ together define a monad (T̃, η̃, μ̃) on A-Gph, where T̃ = Q^{∘}P (again, see [Str1, §6]). A T̃-algebra is an A-graph X equipped with a P -algebra structure h and a Q-algebra structure k such that

P QX \overline{P k ^{}}P X

QP X λ_{X}_{}

[figure: QX; Qh; k; X; h]

commutes. In other words, it is an A-graph X together with a T -algebra structure h_{x,x′} on X(x, x′) for each x, x′ ∈ X_{0}, and an A-category structure

X(x_{0}, x_{1}) × ⋯ × X(x_{r−1}, x_{r}) \overline{k_{x_{0},...,x_{r}}_{}}X(x_{0}, x_{r})

(x_{i} ∈ X_{0}) on X, such that for all x_{0}, …, x_{r} ∈ X_{0},

T \{X(x_{0}, x_{1}) × ⋯ × X(x_{r−1}, x_{r})\} \overline{T (k_{x_{0},...,x_{r}})_{}}T (X(x_{0}, x_{r}))

T (X(x_{0}, x_{1})) × ⋯ × T (X(x_{r−1}, x_{r})) (T (pr_{1}), …, T (pr_{r}))_{}

[figure: X(x_{0}, x_{1}) × ⋯ × X(x_{r−1}, x_{r}); h_{x_{0},x_{1}} × ⋯ × h_{x_{r−1},x_{r}}; k_{x_{0},...,x_{r}}; X(x_{0}, x_{r}); h_{x_{0},x_{r}}]

commutes. But the left-hand column of this diagram is the product in A^{T} of the T - algebras X(x_{0}, x_{1}), …, X(x_{r−1}, x_{r}) (recalling the way in which a monadic functor creates limits): so a T̃-algebra is exactly a category enriched in A^{T}, and (A-Gph)T̃ ≅ A^{T} -Cat.

It is easy to see that the diagram of forgetful functors in the first paragraph of the proof commutes, so the forgetful functor A^{T} -Cat \overline{}A-Gph is monadic. Moreover, P preserves coproducts since T does, and Q evidently preserves coproducts, so the functor T̃ = Q^{∘}P does too. This completes the proof of (a).

For (b) and (c), note that P is cartesian (respectively, finitary) if T is, and that Q is cartesian and finitary in any case. It only remains to prove that if the monad T is cartesian then the natural transformation λ : P Q \overline{}QP is also cartesian, and this is straightforward.

The proof of Theorem C.1.1(a) is now done. For part (b) we use the following result:

C.2.3. Proposition. Let J : 𝔸′ \overline{}𝔸 be a functor between small categories, let (T′, η′, μ′) be a monad on A′ = [𝔸′, Set] such that T′ preserves all coproducts, and similarly (T, η, μ) on A = [𝔸, Set]. If J^{∗} is a weak map of monads

(A, T) \overline{}(A′, T′),  (26)

then the induced functor J^{∗}-Gph : A-Gph \overline{}A′-Gph also becomes a weak map of monads

(A-Gph, T̃) \overline{}(A′-Gph, T̃′),  (27)

where T̃ and T̃′ are as in Proposition C.2.1. Moreover, the diagram

A^{T} -Cat \overline{}A′^{T′}-Cat
[figure: (A-Gph)T̃; ≅; (A′-Gph)T̃′; ≅]

commutes, where the map along the top is induced by the monad map (26) and the map along the bottom by the monad map (27).

Proof. Consider the diagram

A-Gph \overline{J^{∗}-Gph_{}}A′-Gph

[figure: A-Gph; P; J^{∗}-Gph; A′-Gph; P′]

[figure: A-Gph; Q; J^{∗}-Gph; A′-Gph,; Q′]

where P and Q are as in the proof of Proposition C.2.1, and similarly P′ and Q′. Applying ( )-Gph to the isomorphism T′^{∘}J^{∗} ≅ J^{∗}^{∘}T gives an isomorphism ‘inside’ the upper square, making J^{∗}-Gph into a weak map of monads

(A-Gph, P) \overline{}(A′-Gph, P′).

There is also a natural isomorphism inside the lower square, expressing the fact that the free enriched category construction is natural in a suitable sense, and this gives a weak map of monads

(A-Gph, Q) \overline{}(A′-Gph, Q′).

(The checks involved here use the fact that J^{∗} : A′ \overline{}A is induced by J : 𝔸 \overline{}𝔸′; again, this is an unnecessarily strong hypothesis, but serves our purpose.) Gluing together these two weak maps of monads gives a third weak map of monads,

(A-Gph, T̃) \overline{}(A′-Gph, T̃′),

as required. One can easily check that the diagram in the last sentence of the Proposition commutes.

Theorem C.1.1(b) can now be proved by induction on n.

For the base step, take the monads T_{0} on G_{0} = [𝔾_{0}, Set] ≅ Set and T_{1} on G_{1} = [𝔾_{1}, Set], and the inclusion J : 𝔾_{0} \overline{}𝔾_{1}. Then T_{0} is the identity monad, T_{1} is the free category monad, and R_{0} = J^{∗} : G_{1} \overline{}G_{0} assigns to a directed graph its set of objects. Hence R_{0} is naturally a weak map of monads. (With the usual description of T_{1}, R_{0} is in fact a strict map of monads, i.e. the isomorphism T_{0}^{∘}R_{0} ^{∼} R_{0}^{∘}T_{1} is the identity.) Moreover, the map G_{1}^{T_{1}} \overline{}G_{0}^{T_{0}} induced by this monad map is the objects functor S_{0}, once one has identified G_{1}^{T_{1}} with 1-Cat and G_{0}^{T_{0}} with 0-Cat.

For the inductive step, let n ≥ 1 and apply Proposition C.2.3 with 𝔸 = 𝔾_{n}, 𝔸′ = 𝔾_{n−1}, the inclusion J : 𝔾_{n−1} \overline{}𝔾_{n}, the monad T = T_{n} on A = G_{n}, and the monad T′ = T_{n−1} on A′ = G_{n−1}. Then J^{∗} = R_{n−1}, which by inductive hypothesis is a weak map of monads. This makes J^{∗}-Gph into a weak map of monads

(A-Gph, T̃) \overline{}(A′-Gph, T̃′),

and using the equivalences G_{n}-Gph ≃ G_{n+1}, G_{n−1}-Gph ≃ G_{n}, this says that R_{n} is a weak map of monads

(G_{n+1}, T_{n+1}) \overline{}(G_{n}, T_{n}).

By the last part of Proposition C.2.3, the functor from G_{n+1}^{T_{n+1}} ( ≃ (n + 1)-Cat) to G_{n}^{T_{n}} ( ≃ n-Cat) induced by this map of monads is indeed S_{n}.

C.3. Representation by pasting diagrams. We finish this appendix by showing that if T = T_{ω} is the free strict ω-category monad on G_{ω}, and X a globular set, then

(T X)(n) ≅ ∐_{π∈pd(n)} G_{ω}(π̂, X)

for all n ∈ ℕ. Really this is just the beginning of a longer story which is not told here. Having given concrete descriptions of the globular set pd and the globular sets π̂, we could, as hinted on page 144, go on to specify further data which would determine the whole monad structure (T, η, μ). Such data would, for instance, encode the process of composition in the strict ω-category pd, i.e. the gluing together of pasting diagrams.

By analogy, the Carboni-Johnstone paper [CJ] discusses how a family (π̂)_{π∈P} of sets gives rise to a cartesian endofunctor T = ∐_{π∈P} Set(π̂, —) on Set, and contains the result that any cartesian endofunctor on Set arises in this way. (To be precise, the condition is that T preserves wide pullbacks, not just ordinary pullbacks.) The paper also goes some of the way towards saying what, in terms of the representing family (π̂)_{π∈P}, a cartesian monad structure on such an endofunctor would be.

What I envisage is that this theory extends from Set to functor categories [𝔸, Set]. This would mean that the free strict ω-category monad, purely on the grounds of being cartesian, is familially representable in a suitable sense, and the theory should tell us what the representing family is—namely, (π̂)_{π∈pd(n)} for each n, together with the extra data alluded to above. This extended theory seems to work perfectly well, but the details become so formidable that an ad hoc approach seems more sensible here.

Before proving our result we need some notation. If X is a globular set then denote by X^{[n]} the n-globular set obtained by truncating X: in other words, the image of X under the limit-projection G_{ω} \overline{}G_{n}. If Y is an (n + 1)-globular set and y, y′ ∈ Y (0) then there is an n-globular set Y (y, y′) given by

(Y (y, y′))(k) = {z ∈ Y (k + 1) | s^{k}(z) = y, t^{k}(z) = y′}.

The same definition can be made when Y is an (ω-)globular set, in which case Y (y, y′) is also an (ω-)globular set.

Next, let P_{n+1} : G_{n+1} \overline{}G_{n+1} be the functor given by

(P_{n+1}Y)(0) = Y (0), (P_{n+1}Y)(y, y′) = T_{n}(Y (y, y′))

(y, y′ ∈ Y (0)), and let Q_{n+1} : G_{n+1} \overline{}G_{n+1} be the functor given by

(Q_{n+1}Y)(0) = Y (0),
(Q_{n+1}Y)(y, y′) = ∐_{y=y_{0},...,y_{r}=y′} Y (y_{0}, y_{1}) × ⋯ × Y (y_{r−1}, y_{r}).

The arguments of the previous subsection established that T_{n+1} ≅ Q_{n+1}^{∘}P_{n+1}.

The proof of the present result is by induction on n. First of all, if X is a globular set then

(T_{ω}X)(0) = (T_{ω}X)^{[0]}(0) = (T_{0}X^{[0]})(0) = X(0) ≅ ∐_{π∈pd(0)} G_{ω}(π̂, X),

the second equality coming from the definition of T_{ω} as the limit of the T_{n}’s. Now suppose that the theorem holds for some n ≥ 0. We have

(T_{ω}X)(n + 1)
= (T_{ω}X)^{[n+1]}(n + 1)
= (T_{n+1}X^{[n+1]})(n + 1)
≅ (Q_{n+1}P_{n+1}X^{[n+1]})(n + 1)
≅ ∐_{x,x′∈X(0)}((Q_{n+1}P_{n+1}X^{[n+1]})(x, x′))(n)
≅ ∐_{x_{0},...,x_{r}∈X(0)}(T_{n}(X^{[n+1]}(x_{0}, x_{1})))(n) × ⋯ × (T_{n}(X^{[n+1]}(x_{r−1}, x_{r})))(n)
= ∐_{x_{0},...,x_{r}∈X(0)}(T_{ω}(X(x_{0}, x_{1})))(n) × ⋯ × (T_{ω}(X(x_{r−1}, x_{r})))(n)
≅ ∐_{\begin{matrix}x_{0},...,x_{r}∈X(0), \\ π_{1},...,π_{r}∈pd(n) \end{matrix}} G_{ω}(π̂_{1}, X(x_{0}, x_{1})) × ⋯ × G_{ω}(π̂_{r}, X(x_{r−1}, x_{r}))

≅ ∐_{π_{1},...,π_{r}∈pd(n)} G_{ω}({ \atop (π_{1}, …, π_{r})}, X)
≅ ∐_{π∈pd(n+1)} G_{ω}(π̂, X)

where in the penultimate isomorphism we use the construction of { \atop (π_{1}, …, π_{r})} from π̂_{1}, …, π̂_{r} (equation (14)). This completes the induction.

D. Existence of initial operad-with-contraction

Here we prove that the category OWC of operads-with-contraction has an initial object, as required in 4.1.

D.1. The strategy. The explanation in 4.5 suggests a way of constructing the initial operad-with-contraction explicitly: ascend through the dimensions, at each stage freely adding in elements got by contraction and then freely adding in elements got by operadic composition. However, we do not take this route here, instead relying on the following result from Kelly’s paper [Kel2]:

D.1.1. Theorem. Let

[figure: D; C; B; P; A; Q]

be a (strict) pullback diagram in CAT. If A is locally finitely presentable and each of P and Q is finitary and monadic, then the functor D \overline{}A is also monadic.

All we need to take from this is:

D.1.2. Corollary. In the situation of Theorem D.1.1, D has an initial object.

Proof. By definition, a locally finitely presentable category is cocomplete, so A has an initial object. The functor D \overline{}A has a left adjoint (being monadic), which applied to the initial object of A gives an initial object of D.

We apply this corollary as follows. Let T be the free strict ω-category monad on the category E = [𝔾, Set], as in Section 4. Write Coll for the category E/pd of collections (i.e. T -graphs on 1: see 4.3). Write Oper for the category of T -operads; then there is a forgetful functor Oper \overline{}Coll. As observed on page 151, the definition of a contraction on a T -operad is really a definition of a contraction on a collection, which means that we have a category CWC of collections-with-contraction and a (strict) pullback diagram

OWC  \overline{}Oper

[figure: CWC; Coll]

in CAT.

All we need to do now is check that the hypotheses of Theorem D.1.1 hold in this situation, and that is the content of the next subsection.

D.2. The proof.

Hypothesis on Coll. We have first to check that Coll is locally finitely presentable. Indeed, if Gr(pd) is the Grothendieck fibration (category of elements) of the functor pd : 𝔾 \overline{}Set, then

Coll ≅ [𝔾, Set]/pd ≃ [Gr(pd), Set],

and any category of the form [𝔸, Set] (with 𝔸 small) is locally finitely presentable: see [Borx2], Example 5.2.2(b).

Hypotheses on U : CWC ^{}Coll. We have to see that U is finitary and monadic. It is straightforward to calculate that U creates filtered colimits; and since Coll possesses all filtered colimits, U preserves them too. It is also easy to calculate that U creates coequalizers for U-split coequalizer pairs. Hence we have only to show that U has a left adjoint.

We construct a left adjoint F explicitly. Let C be a collection, and define a new collection F C and a map α_{C} : C \overline{}F C inductively as follows:

• if π ∈ pd(0) then (F C)(π) = C(π)

• if π ∈ pd(1) then (F C)(π) = C(π) + (C(∂π) × C(∂π))

• if n ≥ 2 and π ∈ pd(n) then

(F C)(π) =  (28)
C(π) + {(ψ_{0}, ψ_{1}) ∈ (F C)(∂π)^{2} | s(ψ_{0}) = s(ψ_{1}) and t(ψ_{0}) = t(ψ_{1})}

• α_{C,π} : C(π)^{⊂} ^{}(F C)(π) is inclusion as the first component, for all π

• if n ≥ 1 and π ∈ pd(n) then the source map s : (F C)(π) \overline{}(F C)(∂π) is given by

– the composite C(π) ^{^{s}} C(∂π) ^{α_{C,∂π}} (F C)(∂π), on the first summand

– first projection, on the second summand,

and the target map is defined similarly.

It is easy to check that the globularity relations in F C are satisfied, so that F C forms a collection, and that α_{C} : C \overline{}F C is a map of collections.

In the notation of 4.1, the set {…} in equation (28) is P_{π}(F C), so

(F C)(π) = C(π) + P_{π}(F C)

for any n ≥ 1 and π ∈ pd(n). Thus we can define a contraction κ^{C} on F C by taking κ_{π}^{C} to be second inclusion P_{π}(F C)^{⊂} ^{}(F C)(π).

We have now associated to each collection C a collection-with-contraction (F C, κ^{C}) and a map α_{C} : C \overline{}F C of collections. Another easy check shows that α_{C} has the appropriate universal property, so that U has a left adjoint.

Hypotheses on Oper ^{}Coll. Again, we have to see that this functor is finitary and monadic.

Monadicity will follow from Theorems 3.3.2 and 3.3.3 just as long as T is finitary, which is true by Theorem C.0.3.

Let T′_{1} be the monad on Coll induced by Oper \overline{}Coll and its left adjoint. The fact that T is finitary also implies that T′_{1} is finitary, by the ‘moreover’ part of Theorem 3.3.2. So our monadic adjunction is finitary, as required.

192  TOM LEINSTER

References

[BD] J. Baez, J. Dolan, Higher-dimensional algebra III: n-categories and the algebra of opetopes (1998). Advances in Mathematics 135, pp. 145–206. Also e-print q-alg/9702014.

[Bat] M. Batanin, Monoidal globular categories as a natural environment for the theory of weak n-categories (1997). Advances in Mathematics 136, pp. 39–103.

[BJT] Hans-Joachim Baues, Mamuka Jibladze, Andy Tonks, Cohomology of monoids in monoidal categories (1997). In: Operads: Proceedings of Renaissance Conferences, ed. Loday, Stasheff, Voronov, Contemporary Mathematics 202, AMS.

[Bén] Jean Bénabou, Introduction to bicategories (1967). In: Reports of the Midwest Category Seminar, ed.

Bénabou et al, Springer LNM 47.

[BCSW] Renato Betti, Aurelio Carboni, Ross Street, Robert Walters, Variation through enrichment (1983). Journal of Pure and Applied Algebra 29, pp. 109–127.

[BKP] R. Blackwell, G. M. Kelly, A. J. Power, Two-dimensional monad theory (1989). Journal of Pure and Applied Algebra 59, 1–41.

[Borx1] Francis Borceux, Handbook of Categorical Algebra 1: Basic Category Theory (1994). Cambridge University Press.

[Borx2] Francis Borceux, Handbook of Categorical Algebra 2: Categories and Structures (1994). Cambridge University Press.

[Borh] Richard Borcherds, Vertex algebras (1997). E-print q-alg/9706008. Also in Topological Field Theory, Primitive Forms and Related Topics (Kyoto, 1996), Progress in Mathematics 160, Birkhäuser Boston, 1998.

[Bur] A. Burroni, T -catégories (1971). Cahiers Top. Geom. Diff., Vol. XII, No. 3, pp. 215–321.

[CJ] A. Carboni, P. Johnstone, Connected limits, familial representability and Artin glueing (1995). Mathematical Structures in Computer Science, Vol. 5, pp. 441–459.

[CKW] Aurelio Carboni, Stefano Kasangian, Robert Walters, An axiomatics for bicategories of modules (1987). Journal of Pure and Applied Algebra 45, pp. 127–141.

[CKVW] A. Carboni, G. M. Kelly, D. Verity, R. J. Wood, A 2-categorical approach to change of base and geometric morphisms II (1998). Theory and Applications of Categories, Vol. 4, No. 5, pp. 82–136.

[Che1] Eugenia Cheng, Weak n-categories: opetopic and multitopic foundations (2003). E-print math.CT/ 0304277. Also Journal of Pure and Applied Algebra 186 (2004), no. 2, 109–137.

[Che2] Eugenia Cheng, Weak n-categories: comparing opetopic foundations (2003). E-print math.CT/0304279. Also Journal of Pure and Applied Algebra, to appear.

[Her1] Claudio Hermida, From coherent structures to universal properties (2000). E-print math.CT/0006161.

[Her2] Claudio Hermida, Representable multicategories (2000). Advances in Mathematics 151, pp. 164–225.

[HMP] C. Hermida, M. Makkai, J. Power, On weak higher dimensional categories I.1, I.2, I.3. Journal of Pure and Applied Algebra 154 (2000), no. 1–3, 221–246; 157 (2001), no. 2–3, 247–277; 166 (2002), no. 1–2, 83–104.

[JS] André Joyal, Ross Street, Braided tensor categories (1993). Advances in Mathematics 102, pp. 20–78.

[Kel1] G. M. Kelly, On clubs and doctrines (1974). In: Category Seminar, Springer LNM 420, pp. 181–256.

OPERADS IN HIGHER-DIMENSIONAL CATEGORY THEORY  193

[Kel2] G. M. Kelly, A unified treatment of transfinite constructions for free algebras, free monoids, colimits, associated sheaves, and so on (1980). Bulletin of the Australian Mathematical Society, Vol. 22, pp. 1–83.

[KS] G. M. Kelly, R. Street, Review of the elements of 2-categories (1974). In: Category Seminar, Springer LNM 420, pp. 75–103.

[Kos] Jürgen Koslowski, Monads and interpolads in bicategories (1997). Theory and Applications of Categories, Vol. 3, No. 8, pp. 182–212.

[Lam] Joachim Lambek, Deductive systems and categories II: standard constructions and closed categories (1969). In: Category Theory, Homology Theory and their Applications I, ed. P. Hilton, Springer LNM 86.

[Lei1] Tom Leinster, General operads and multicategories (1997). E-print math.CT/9810053.

[Lei2] Tom Leinster, Basic bicategories (1998). E-print math.CT/9810017.

[Lei3] Tom Leinster, Structures in higher-dimensional category theory (1998). E-print math.CT/0109021.

[Lei4] Tom Leinster, fc-multicategories (1999). E-print math.CT/9903004.

[Lei5] Tom Leinster, Generalized enrichment for categories and multicategories (1999). E-print math.CT/

          9901139.

[Lei6] Tom Leinster, Generalized enrichment of categories (1999). E-print math.CT/0204279. Also Journal of Pure and Applied Algebra 168 (2002), no. 2–3, 391–406.

[Lei7] Tom Leinster, Homotopy algebras for operads (2000). E-print math.QA/0002180.

[Lei8] Tom Leinster, What’s a monoidal category? (2000). Poster at CT2000, Como, Italy.

[Lei9] Tom Leinster, Higher Operads, Higher Categories (2003). E-print math.CT/0305049; also London Mathematical Society Lecture Note Series 298, Cambridge University Press, to appear.

[Lew] Geoffrey Lewis, Coherence for a closed functor (1972). In: Coherence in Categories, ed. Kelly, Laplaza, Lewis, Mac Lane, Springer LNM 281.

[May1] J. P. May, The Geometry of Iterated Loop Spaces (1972). Springer LNM 271.

[May2] J. P. May, Definitions: operads, algebras and modules (1997). In: Operads: Proceedings of Renaissance Conferences, ed. Loday, Stasheff, Voronov, Contemporary Mathematics 202, AMS.

[Pow] A. J. Power, A general coherence result (1989). Journal of Pure and Applied Algebra 57, no. 2, 165–173.

[Sny1] Craig T. Snydal, Equivalence of Borcherds G-vertex algebras and axiomatic vertex algebras (1999).

          E-print math.QA/9904104.

[Sny2] Craig T. Snydal, Relaxed multi category structure of a global category of rings and modules (1999).

          E-print math.QA/9912075.

[Soi] Y. Soibelman, Meromorphic tensor categories (1997). E-print q-alg/9709030.

[Str1] Ross Street, The formal theory of monads (1972). Journal of Pure and Applied Algebra 2, pp. 149–168.

[Str2] Ross Street, Categorical structures (1995). In: Handbook of Algebra, Vol. 1, ed. M. Hazewinkel, Elsevier North-Holland.

[Str3] Ross Street, The role of Michael Batanin’s monoidal globular categories (1997). In: Higher Category Theory (Evanston, IL, 1997), Contemporary Mathematics 230, AMS, 1998.

[Wal] R. F. C. Walters, Sheaves and Cauchy-complete categories (1981). Cahiers Top. Geom. Diff., Vol. XXII, No. 3.

Department of Mathematics, University of Glasgow, Glasgow G12 8QW, United Kingdom

Email: t.leinster@maths.gla.ac.uk

This article may be accessed via WWW at http://www.tac.mta.ca/tac/ or by anony-

mous ftp at ftp://ftp.tac.mta.ca/pub/tac/html/volumes/12/3/12-03.{dvi,ps}

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.

The method of distribution of the journal is via the Internet tools WWW/ftp. The journal is archived electronically and in printed paper format.

Subscription information. Individual subscribers receive (by e-mail) abstracts of articles as they are published. Full text of published articles is available in .dvi, Postscript and PDF. Details will be e-mailed to new subscribers. 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}TEX is the preferred flavour. TEX source of articles for publication should be submitted by e-mail directly to an appropriate Editor. They are listed below. Please obtain detailed information on submission format and style files from the journal’s WWW server at http://www.tac.mta.ca/tac/. You may also write to tac@mta.ca to receive details by e-mail.

Editorial board.

John Baez, University of California, Riverside: baez@math.ucr.edu Michael Barr, McGill University: barr@barrs.org, Associate Managing Editor Lawrence Breen, Université Paris 13: breen@math.univ-paris13.fr Ronald Brown, University of Wales Bangor: r.brown@bangor.ac.uk Jean-Luc Brylinski, Pennsylvania State University: jlb@math.psu.edu Aurelio Carboni, Università dell Insubria: aurelio.carboni@uninsubria.it Valeria de Paiva, Palo Alto Research Center: paiva@parc.xerox.com Martin Hyland, University of Cambridge: M.Hyland@dpmms.cam.ac.uk P. T. Johnstone, University of Cambridge: ptj@dpmms.cam.ac.uk G. Max Kelly, University of Sydney: maxk@maths.usyd.edu.au 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@buffalo.edu 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 Robert Rosebrugh, Mount Allison University: rrosebrugh@mta.ca, Managing Editor Jiri Rosicky, Masaryk University: rosicky@math.muni.cz 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