Theory and Applications of Categories, Vol. 24, No. 21, 2010, pp. 580–655.

A UNIFIED FRAMEWORK FOR GENERALIZED MULTICATEGORIES

G.S.H. CRUTTWELL AND MICHAEL A. SHULMAN

Abstract. Notions of generalized multicategory have been defined in numerous contexts throughout the literature, and include such diverse examples as symmetric multicategories, globular operads, Lawvere theories, and topological spaces. In each case, generalized multicategories are defined as the “lax algebras” or “Kleisli monoids” relative to a “monad” on a bicategory. However, the meanings of these words differ from author to author, as do the specific bicategories considered. We propose a unified framework: by working with monads on double categories and related structures (rather than bicategories), one can define generalized multicategories in a way that unifies all previous examples, while at the same time simplifying and clarifying much of the theory.

Contents

1 Introduction 580 2 Virtual double categories 588 3 Monads on a virtual double category 593 4 Generalized multicategories 599 5 Composites and units 606 6 2-categories of T -monoids 612 7 Virtual equipments 615 8 Normalization 622 9 Representability 628 A Composites in 𝕄od and ℍ-Kl 636 B Comparisons to previous theories 640

1. Introduction

A multicategory is a generalization of a category, in which the domain of a morphism, rather than being a single object, can be a finite list of objects. A prototypical example is the multicategory Vect of vector spaces, in which a morphism (V_{1}, …, V_{n}) [figure] W is a

The first author was supported by a PIMS Calgary postdoctoral fellowship, and the second author by a National Science Foundation postdoctoral fellowship during the writing of this paper.

Received by the editors 2010-04-05 and, in revised form, 2010-12-10. Transmitted by Tom Leinster. Published on 2010-12-14, this revision 2016-09-12. 2000 Mathematics Subject Classification: 18D05,18D20,18D50. Key words and phrases: Enriched categories, change of base, monoidal categories, double categories,

multicategories, operads, monads.

\begin{matrix}c \\ ◯ \end{matrix} G.S.H. Cruttwell and Michael A. Shulman, 2010. Permission to copy for private use granted.

multilinear map. In fact, any monoidal category gives a multicategory in a canonical way, where the morphisms (V_{1}, …, V_{n}) [figure] W are the ordinary morphisms V_{1} ⊗ … ⊗ V_{n} [figure] W. The multicategory Vect can be seen as arising in this way, but it is also natural to view its multicategory structure as more basic, with the tensor product then characterized as a representing object for “multimorphisms.” This is also the case for many other multicategories; in fact, monoidal categories can be identified with multicategories satisfying a certain representability property (see [Her00] and §9).

In addition to providing an abstract formalization of the passage from “multilinear map” to “tensor product,” multicategories provide a convenient way to present certain types of finitary algebraic theories (specifically, strongly regular finitary theories, whose axioms involve no duplication, omission, or permutation of variables). Namely, the objects of the multicategories are the sorts of the theory, and each morphism (X_{1}, …, X_{n}) [figure] Y represents an algebraic operation of the theory. When viewed in this light, multicategories (especially those with one object, which correspond to one-sorted theories) are often called non-symmetric operads (see [May72]). The original definition of multicategories in [Lam69] (see also [Lam89]) was also along these lines (a framework for sequent calculus). The two viewpoints are related by the observation that when A is a small multicategory representing an algebraic theory, and C is a large multicategory such as Vect, a model of the theory A in C is simply a functor of multicategories A [figure] C. This is a version of the functorial semantics of [Law63].

Our concern in this paper is with generalized multicategories, a well-known idea which generalizes the basic notion in two ways. Firstly, one allows a change of “base context,” thereby including both internal multicategories and enriched multicategories. Secondly, and more interestingly, one allows the finite lists of objects serving as the domains of morphisms to be replaced by “something else.” From the first point of view, this is desirable since there are many other contexts in which one would like to analyze the relationship between structures with coherence axioms (such as monoidal categories) and structures with universal or “representability” properties. From the second point of view, it is desirable since not all algebraic theories are strongly regular.

For example, generalized multicategories include symmetric multicategories, in which the finite lists can be arbitrarily permuted. “Representable” symmetric multicategories correspond to symmetric monoidal categories. Enriched symmetric multicategories with one object can be identified with the operads of [May72, Kel05, KM95]. These describe algebraic theories in whose axioms variables can be permuted (but not duplicated or omitted). In most applications of operads (see [EM06, BM03] for some recent ones), both symmetry and enrichment are essential.

An obvious variation of symmetric multicategories is braided multicategories. If we allow duplication and omission in addition to permutation of inputs, we obtain (multisorted) Lawvere theories [Law63]; a slight modification also produces the clubs of [Kel72b, Kel92]. There are also important generalizations to “algebraic theories” on more complicated objects; for instance, the globular operads of [Bat98, Lei04] describe a certain sort of algebraic theory on globular sets that includes many notions of weak n-category.

A very different route to generalized multicategories begins with the observation of [Bar70] that topological spaces can be viewed as a type of generalized multicategory, when finite lists of objects are replaced by ultrafilters, and morphisms are replaced by a convergence relation. Many other sorts of topological structures, such as metric spaces, closure spaces, uniform spaces, and approach spaces, can also be seen as generalized multicategories; see [Law02, CT03, CHT04].

With so many different faces, it is not surprising that generalized multicategories have been independently considered by many authors. They were first studied in generality by [Bur71], but have also been considered by many other authors, including [Lei04], [Lei02], [Her01], [CT03], [CHT04], [Bar70], [Web05], [BD98], [Che04], and [DS03]. While all these authors are clearly doing “the same thing” from an intuitive standpoint, they work in different frameworks at different levels of generality, making the formal definitions difficult to compare. Moreover, all of these approaches share a certain ad hoc quality, which, given the naturalness and importance of the notion, ought to be avoidable.

In each case, the authors observe that the “something else” serving as the domain of morphisms in a generalized multicategory should be specified by some sort of monad, invariably denoted T. For example, ordinary multicategories appear when T is the “free monoid” monad, globular operads appear when T is the “free strict ω-category” monad, and topological spaces appear when T is the ultrafilter monad. All the difficulties then center around what sort of thing T is a monad on.

Leinster [Lei02, Lei04] takes it to be a cartesian monad on an ordinary category C, i.e. C has pullbacks, T preserves them, and the naturality squares for its unit and multiplication are pullback squares. Burroni [Bur71], whose approach is basically the same, is able to deal with any monad on a category with pullbacks. Hermida [Her01] works with a cartesian 2-monad on a suitable 2-category. Barr and Clementino et. al. [Bar70, CT03, CHT04] work with a monad on Set equipped with a “lax extension” to the bicategory of matrices in some monoidal category. Weber [Web05] works with a “monoidal pseudo algebra” for a 2-monad on a suitable 2-category. Baez-Dolan [BD98] and Cheng [Che04] (see also [FGHW08]) use a monad on Cat extended to the bicategory of profunctors (although they consider only the “free symmetric strict monoidal category” monad).

Inspecting these various definitions and looking for commonalities, we observe that in all cases, the monads involved naturally live on a bicategory, be it a bicategory of spans (Burroni, Leinster), two-sided fibrations (Hermida), relations (Barr), matrices (Clementino et. al., Weber), or profunctors (Baez-Dolan, Cheng). What causes problems is that the monads of interest are frequently lax (preserving composition only up to a noninvertible transformation), but there is no obvious general notion of lax monad on a bicategory, since there is no good 2-category (or even tricategory) of bicategories that contains lax or oplax functors.

Furthermore, merely knowing the bicategorical monad (however one chooses to formalize this) is insufficient for the theory, and in particular for the definition of functors and transformations between generalized multicategories. Leinster, Burroni, Weber, and Hermida can avoid this problem because their bicategorical monads are induced by monads on some underlying category or 2-category. Others resolve it by working with an extension of a given monad on Set or Cat to the bicategory of matrices or profunctors, rather than merely the bicategorical monad itself. However, the various definitions of such extensions are tricky to compare and have an ad hoc flavor.

Our goal in this paper (and its sequels) is to give a common framework which includes all previous approaches to generalized multicategories, and therefore provides a natural context in which to compare them. To do this, instead of considering monads on bicategories, we instead consider monads on types of double categories. This essentially solves both problems mentioned above: on the one hand there is a perfectly good 2-category of double categories and lax functors (allowing us to define monads on a double category), and on the other hand the vertical arrows of the double categories (such as morphisms in the cartesian category C, functions in Set, or functors between categories) provide the missing data with which to define functors and transformations of generalized multicategories.

The types of double categories we use are neither strict or pseudo double categories, but instead an even weaker notion, for the following reason. An important intermediate step in the definition of generalized multicategories is the horizontal Kleisli construction of a monad T, whose (horizontal) arrows X [figure] Y are arrows X [figure] T Y. Without strong assumptions on T, such arrows cannot be composed associatively, and hence the horizontal Kleisli construction does not give a pseudo double category or bicategory. It does, however, give a weaker structure, which we call a virtual double category.

Intuitively, virtual double categories generalize pseudo double categories in the same way that multicategories generalize monoidal categories. There is no longer a horizontal composition operation, but we have cells of shapes such as the following:

[figure: Y_{0}; Y_{1}; q; X_{0}; Y_{0}; f; X_{0}; X_{n}; X_{n}; Y_{1}; g; X_{0}; X_{1}; p_{1}; X_{1}; X_{2}; p_{2}; X_{2}; ⋯; p_{3}; ⋯; X_{n}; p_{n}; α]

We will give an explicit definition in §2. Virtual double categories have been studied by [Bur71] under the name of multicatégories and by [Lei04] under the name of fcmulticategories, both of whom additionally described a special case of the horizontal Kleisli construction. They are, in fact, the generalized multicategories relative to the “free category” or “free double category” monad (depending on whether one works with spans or profunctors). In [DPP06] virtual double categories were called lax double categories, but we believe that name belongs properly to lax algebras for the 2-monad whose strict algebras are double categories. (We will see in Example 9.7 that oplax double categories in this “2-monadically correct” sense can be identified with a restricted class of virtual double categories.)

Next, in §§3–4 we will show that for any monad T on a virtual double category 𝕏, one can define a notion which we call a T -monoid. In fact, we will construct an entire new virtual double category 𝕂Mod(𝕏, T) whose objects are T -monoids, by composing the “horizontal Kleisli” construction mentioned above with the “monoids and bimodules” construction 𝕄od described in [Lei04, §5.3], which can be applied to any virtual double category. Then in §6 we will construct from 𝕂Mod(𝕏, T) a 2-category KMon(𝕏, T) of T - monoids, T -monoid functors, and transformations, generalizing the analogous definition in [Lei04, §5.3]. This requires a notion of when a virtual double category has units, which we define in §5 along with the parallel notion of when it has composites. (These definitions generalize those of [Her00] and can also be found in [DPP06]; they are also a particular case of the “representability” of [Her01] and our §9.)

For particular 𝕏 and T, the notion of T -monoid specializes to several previous definitions of generalized multicategories. For example, if 𝕏 consists of objects and spans in a cartesian category C and T is induced from a monad on C, we recover the definitions of Leinster, Kelly, and Burroni. And if 𝕏 consists of sets and matrices enriched over some monoidal category V and T is a “canonical extension” of a taut set-monad to 𝕏, then we recover the definitions of Clementino et. al.

However, the other definitions of generalized multicategory cannot quite be identified with T -monoids for any T, but rather with only a restricted class of them. For instance, if 𝕏 consists of categories and profunctors, and T extends the “free symmetric monoidal category” monad on Cat (this is the situation of Baez-Dolan and Cheng), then T -monoids are not quite the same as ordinary symmetric multicategories. Rather, a T -monoid for this T consists of a category A, a symmetric multicategory M, and a bijective-on-objects functor from A to the underlying ordinary category of M. There are two ways to restrict the class of such T -monoids to obtain a notion equivalent to ordinary symmetric multicategories: we can require A to be a discrete category (so that it is simply the set of objects of M), or we can require the functor to also be fully faithful (so that A is simply the underlying ordinary category of M). We call the first type of T -monoid object-discrete and the second type normalized.

In order to achieve a full unification, therefore, we must give general definitions of these classes of T -monoid and account for their relationship. It turns out that this requires additional structure on our virtual double categories: we need to assume that horizontal arrows can be “restricted” along vertical ones, in a sense made precise in §7. Pseudo double categories with this property were called framed bicategories in [Shu08], where they were also shown to be equivalent to the proarrow equipments of [Woo82] (see also [Ver92]). Accordingly, if a virtual double category 𝕏 has this property, as well as all units, we call it a virtual equipment.

Our first result in §8, then, is that if T is a well-behaved monad on a virtual equipment, object-discrete and normalized T -monoids are equivalent. However, normalized T -monoids are defined more generally than object-discrete ones, and moreover when T which are insufficiently well-behaved, it is the normalized T -monoids which are of more interest. Thus, we subsequently discard the notion of object-discreteness. (Hermida’s generalized multicategories also arise as normalized T -monoids, where 𝕏 consists of discrete fibrations in a suitable 2-category K and T is an extension of a suitable 2-monad on K. Weber’s definition is a special case, since as given it really only makes sense for generalized operads, for which normalization is automatic; see §B.16.) In Table 1 we summarize the meanings of T -monoids and normalized T -monoids for a number of monads T.

Now, what determines whether the “right” notion of generalized multicategory is a plain T -monoid or a normalized one? The obvious thing distinguishing the situations of Leinster, Burroni, and Clementino et. al. from those of Baez-Dolan, Cheng, and Hermida is that in the former case, the objects of 𝕏 are “set-like,” whereas in the latter, they are “category-like.” However, some types of generalized multicategory can be constructed starting from two different monads on two different virtual equipments, one of which belongs to the first group and the other to the second.

For example, observe that an ordinary (non-symmetric) multicategory has an underlying ordinary category, containing the same objects but only the morphisms (V_{1}) [figure] W with unary source. Thus, such a multicategory can be defined in two ways: either as extra structure on its set of objects, or as extra structure on its underlying category. In the second case, normalization is the requirement that in the extra added structure, the multimorphisms with unary source do no more than reproduce the originally given category. Thus, ordinary multicategories arise both as T -monoids the “free monoid” monad on sets and spans, and as normalized T -monoids for the “free monoidal category” monad on categories and profunctors.

Our second result in §8 is a generalization of this relationship. We observe that the virtual equipment of categories and profunctors results from applying the “monoids and modules” construction 𝕄od to the virtual equipment of sets and spans. Thus, we generalize this situation by showing that for any monad T on a virtual equipment, plain T -monoids can be identified with normalized 𝕄od(T)-monoids. That this is so in the examples can be seen by inspection of Table 1. Moreover, it is sensible because application of 𝕄od takes “set-like” things to “category-like” things.

It follows that the notion of “normalized T -monoid” is actually more general than the notion of T -monoid, since arbitrary T -monoids for some T can be identified with the normalized S-monoids for some S (namely S = 𝕄od(T)), whereas normalized S-monoids cannot always be identified with the arbitrary T -monoids for any T. (For instance, this is not the case when S is the “free symmetric monoidal category” monad on categories and profunctors.) This motivates us to claim that the “right” notion of generalized multicategory is a normalized T -monoid, for some monad T on a virtual equipment.

Having reached this conclusion, we also take the opportunity to propose a new naming system for generalized multicategories which we feel is more convenient and descriptive. Namely, if (pseudo) T -algebras are called widgets, then we propose to call normalized T -monoids virtual widgets. The term “virtual double category” is of course a special case of this: virtual double categories are the normalized T -monoids for the monad T on ℙrof(Grph) whose algebras are double categories.

Of course, “virtual” used in this way is a “red herring” adjective^{1} akin to “pseudo” and “lax”, since a virtual widget is not a widget. The converse, however, is true: every widget

1The mathematical red herring principle states that an object called a “red herring” need not, in general, be either red or a herring.

586  G.S.H. CRUTTWELL AND MICHAEL A. SHULMAN
Monad T  on  T -monoid  Normalized ; T -Monoid  Pseudo ; T -algebra

Id V-𝕄at V-enriched category Set

Set

Id 𝕊pan(C)

Internal category in C Object of C

Object of C

Id  ℝel  Ordered Set  Set  Set
Id  \overline{R_{+}}-𝕄at  Metric Space  Set  Set

Powerset ℝel Closure Space T_{1} Closure Space

Complete Semilattice

𝕄od(powerset)

2-ℙrof Modular Closure Space Closure Space Meet-Complete Preorder

Ultrafilter ℝel Topological Space T_{1} space Compact Hausdorff space

𝕄od(ultrafilter)

2-ℙrof Modular Top. Space Topological Space Ordered Compact Hausdorff space

Ultrafilter \overline{R_{+}}-𝕄at Approach space ?

Compact Hausdorff space

Free monoid 𝕊pan(Set) Multicategory ? Monoid

𝕄od(free monoid)

Set-ℙrof “Enhanced” multicategory Multicategory

Monoidal category

Free sym. strict mon. cat.

Set-ℙrof “Enhanced” sym. multicategory Symmetric multicategory Symmetric mon. cat.

Free category 𝕊pan(Grph)

Virtual double category ?

Category

𝕄od(free category)

ℙrof(Grph)

?

Virtual double category Pseudo double category

Free cat. w/ finite products Set-ℙrof ?

Multi-sorted Lawvere theory Cat. w/ finite products

Free cat. w/ small products Set-ℙrof_{ls} ?

Monad on Set Cat. w/ small products

Free presheaf S^{op} [figure] Set 𝕊pan(Set^{ob(S)}) Functor A [figure] S Functor A [figure] S

w/ discrete fibers

Functor S^{op} [figure] Set

𝕄od(free presheaf)

ℙrof(Set^{ob(S)})

?

Functor A [figure] S Pseudofunctor S^{op} [figure] Cat

Free strict ω-category 𝕊pan(Globset) Multi-sorted

globular operad ?

Strict ω-category

𝕄od(free ω-cat.)

ℙrof(Globset)

?

Multi-sorted globular operad Monoidal globular cat.

Free M-set (M a monoid)

𝕊pan(Set)

M-graded category ?

M-set

Table 1: Examples of generalized multicategories. The boxes marked “?” do not have any established name; in most cases they also do not seem very interesting. has an underlying virtual widget, so the terminology makes some sense. For example, the observation above that every monoidal category has an underlying multicategory is an instance of this fact. Moreover, it often happens that virtual widgets share many of the same properties as widgets, and many theorems about widgets can easily be extended to virtual widgets. Thus, it is advantageous to use a terminology which stresses the close connection between the two. Another significant advantage of “virtual widget” over “T - multicategory” is that frequently one encounters monads T for which T -algebras have a common name, such as “double category” or “symmetric monoidal category,” but T itself has no name less cumbersome than “the free double category monad” or “the free symmetric monoidal category monad.” Thus, it makes more sense to name generalized multicategories after the algebras for the monad than after the monad itself.

By the end of §8, therefore, we have unified all existing notions of generalized multicategory under the umbrella of virtual T -algebras, where T is a monad on some virtual equipment. Since getting to this point already takes us over 40 pages, we leave to future work most of the development of the theory and its applications, along with more specific comparisons between existing theories (see [CS10a, CS10b]).

However, we do spend some time in §9 on the topic of representability. This is a central idea in the theory of generalized multicategories, which states that any pseudo T -algebra (or, in fact, any oplax T -algebra) has an underlying virtual T -algebra. Additionally, one can characterize the virtual T -algebras which arise in this way by a “representability” property. This can then be interpreted as an alternate definition of pseudo T -algebra which replaces “coherent algebraic structure” by a “universal property,” as advertised in [Her01]. In addition to the identification of monoidal categories with “representable” multicategories, this also includes the fact that compact Hausdorff spaces are T_{1} spaces with additional properties, and that fibrations over a category S are equivalent to pseudofunctors S^{op} [figure] Cat. In [CS10b] we will extend more of the theory of representability in [Her01] to our general context.

Finally, the appendices are devoted to showing that all existing notions of generalized multicategory are included in our framework. In Appendix A we prepare the way by giving sufficient conditions for our constructions on virtual double categories to preserve composites, which is important since most existing approaches use bicategories. Then in Appendix B we summarize how each existing theory we are aware of fits into our context.

We have chosen to postpone these comparisons to the end, so that the main body of the paper can present a unified picture of the subject, in a way which is suitable also as an introduction for a reader unfamiliar with any of the existing approaches. It should be noted, though, that we claim no originality for any of the examples or applications, or the ideas of representability in §9. Our goal is to show that all of these examples fall into the same framework, and that this general framework allows for a cleaner development of the theory.

1.1. Acknowledgements. The first author would like to thank Bob Paré for his suggestion to consider “double triples”, as well as helpful discussions with Maria Manuel Clementino, Dirk Hofmann, and Walter Tholen. The second author would like to thank David Carchedi and the patrons of the n-Category Café blog for several helpful conversations. Both authors would like to thank the editor and the referee for helpful suggestions.

2. Virtual double categories

The definition of virtual double category may be somewhat imposing, so we begin with some motivation that will hopefully make it seem inevitable. We seek a framework which includes all sorts of generalized multicategories. Since categories themselves are a particular sort of generalized multicategory (relative to an identity monad), our framework should in particular include all sorts of generalized categories. In particular, it should include both categories enriched in a monoidal category V and categories internal to a category C with pullbacks, so let us begin by considering how to unify these two situations.

We start by recalling that both V-enriched categories and C-internal categories are particular cases of monoids in a monoidal category. On the one hand, if V is a cocomplete closed monoidal category and O is a fixed set, then V-enriched categories with object set O can be identified with monoids in the monoidal category of O-graphs in V—i.e. (O × O)-indexed families of objects of V, with monoidal structure given by “matrix multiplication.” On the other hand, if C is a category with pullbacks and O is an object of C, then C-internal categories with object-of-objects O can be identified with monoids in the monoidal category of O-spans in C—i.e. diagrams of the form O ← A → O, with monoidal structure given by span composition.

Now, both of these examples share the same defect: they require us to fix the objects (the set O or object O). In particular, the morphisms of monoids in these monoidal categories are functors which are the identity on objects. It is well-known that one can eliminate this fixing of objects by combining all the monoidal categories of graphs and spans, respectively, into a bicategory. (In essense, this observation dates all the way back to [Bén67].) In the first case the relevant bicategory V-Mat consists of V-matrices: its objects are sets, its arrows from X to Y are (X × Y)-matrices of objects in V, and its composition is by “matrix multiplication.” In the second case the relevant bicategory Span(C) consists of C-spans: its objects are objects of C, its arrows from X to Y are spans X ← A → Y in C, and its composition is by pullback. It is easy to define monoids in a bicategory to generalize monoids in a monoidal category^{2}.

However, we still have the problem of functors. There is no way to define morphisms between monoids in a bicategory so as to recapture the correct notions of enriched and internal functors in V-Mat and Span(C). But we can solve this problem if instead of bicategories we use (pseudo) double categories, which come with objects, two different kinds of arrow called “horizontal” and “vertical,” and 2-cells in the form of a square:

2Monoids in a bicategory are usually called monads. However, we avoid that term for these sorts of monoids for two reasons. Firstly, the morphisms of monoids we are interested in are not the same as the usual morphisms of monads (although they are related; see [LS02, §2.3–2.4]). Secondly, there is potential for confusion with the monads on bicategories and related structures which play an essential role in the theory we present.

[figure]

Both V-Mat and Span(V) naturally enlarge to pseudo double categories, interpreting their existing arrows and composition as horizontal and adding new vertical arrows. For V-Mat the new vertical arrows are functions between sets, while for Span(C) the new vertical arrows are morphisms in C. We can now define monoids in a double category (relative to the horizontal structure) and morphisms between such monoids (making use of the vertical arrows) so as to recapture the correct notion of functor in both cases (see Definition 2.8).

The final generalization from pseudo double categories to virtual double categories is more difficult to motivate at the moment, but as remarked in the introduction, we will find it essential in §4. Conceptually (and, in fact, formally), a virtual double category is related to a pseudo double category in the same way that a multicategory is related to a monoidal category. Thus, just as one can define monoids in any multicategory, one can likewise do so in any virtual double category.

2.1. Definition. A virtual double category 𝕏 consists of the following data.

• A category X (the objects and vertical arrows), with the arrows written vertically:

[figure: X; Y; f]

• For any two objects X, Y ∈ X, a class of horizontal arrows, written horizontally with a slash through the arrow:

[figure: X; Y; p]

• Cells, with vertical source and target, and horizontal multi-source and target, written as follows:

[figure: Y_{0}; Y_{1}; q; X_{0}; Y_{0}; f; X_{0}; X_{n}; X_{n}; Y_{1}; g; X_{0}; X_{1}; p_{1}; X_{1}; X_{2}; p_{2}; X_{2}; ⋯; p_{3}; ⋯; X_{n}; p_{n}; α]  (2.2)

Note that this includes cells with source of length 0, in which case we must have X_{0} = X_{n}; such cells are visually represented as follows:

[figure: X; Y_{0}; f; X; Y_{1}; g; Y_{0}; Y_{1}; q; α]

• For the following configuration of cells,

[figure: Z_{0}; Z_{1}; r; Y_{0}; Z_{0}; g_{0}; Y_{0}; Y_{m}; Y_{m}; Z_{1}; g_{1}; Y_{0}; Y_{1}; q_{1}; X_{0}; Y_{0}; f_{0}; X_{0}; X_{n_{1}}; p_{11}...p_{1n_{1}}; X_{n_{1}}; Y_{1}; f_{1}; Y_{1}; Y_{2}; q_{2}; X_{n_{1}}; Y_{1}; X_{n_{1}}; X_{n_{2}}; p_{21}...p_{2n_{1}}; X_{n_{2}}; Y_{2}; f_{2}; X_{n_{2}}; ⋯; ···; ⋯; X_{n_{m}}; ···; Y_{2}; Y_{m}; q_{3}···q_{m}; X_{n_{m}}; Y_{m}; f_{m}; α_{1}; α_{2}; ^{α_{3}···α_{m}}; β]

a composite cell

[figure: Z_{0}; Z_{1}; r; Y_{0}; Z_{0}; g_{0}; Y_{0}; Y_{m}; Y_{m}; Z_{1}; g_{1}; Y_{0}; X_{0}; Y_{0}; f_{0}; X_{0}; X_{n_{1}}; p_{11}...p_{1n_{1}}; X_{n_{1}}; X_{n_{1}}; X_{n_{1}}; X_{n_{2}}; p_{21}...p_{2n_{1}}; X_{n_{2}}; X_{n_{2}}; ⋯; ···; ⋯; X_{n_{m}}; ···; X_{n_{m}}; Y_{m}; f_{m}; β(α_{m}⊡···⊡α_{1})]

• For each horizontal arrow p, an identity cell

[figure: X; Y; X; Y; p; p; 1_{p}]

• Associativity and identity axioms for cell composition. The associativity axiom states that

(γ(β_{m}⊡⋯⊡β_{1}))(α_{mk_{m}}⊡⋯⊡α_{11}) = γ(β_{m}(α_{mk_{m}}⊡⋯⊡α_{m1})⊡⋯⊡β_{1}(α_{1k_{1}}⊡⋯⊡α_{11}))

while the identity axioms state that

α(1_{p_{1}} ⊡ ⋯ ⊡ 1_{p_{n}}) = α  and  1_{q}(α_{1}) = α_{1}

whenever these equations make sense.

2.3. Remark. As mentioned in the introduction, virtual double categories have also been called fc-multicategories by Leinster [Lei04] and multicatégories by Burroni [Bur71]. Our terminology is chosen to emphasize their close relationship with double categories, and to fit into the general naming scheme of §9.

2.4. Remark. In much of the double-category literature, it is common for the “slashed” arrows (spans, profunctors, etc.) to be the vertical arrows. We have chosen the opposite convention purely for economy of space: the cells in a virtual double category fit more conveniently on a page when their multi-source is drawn horizontally.

2.5. Examples. As suggested by the discussion at the beginning of this section, monoidal categories, bicategories, 2-categories, multicategories, and pseudo double categories can each be regarded as examples of virtual double categories, by trivializing the vertical or horizontal structure in various ways; see [Lei02, p. 4] or [Lei04, §5.1] for details.

We now present the two virtual double categories that will serve as initial inputs for most our examples: spans and matrices. (Both are also described in [Lei04, Ch. 5].) For consistency, we name all of our virtual double categories by their horizontal arrows, rather than their vertical arrows or objects.

2.6. Example. Let (V, ⊗, I) be a monoidal category. The virtual double category V-𝕄at is defined as follows: its objects are sets, its vertical arrows are functions, its horizontal arrows X [figure: p] Y are families {p(y, x)}_{x∈X,y∈Y} of objects of V (i.e. (X × Y)- matrices), and a cell of the form (2.2) consists of a family of V-arrows

p_{1}(x_{1}, x_{0}) ⊗ p_{2}(x_{2}, x_{1}) ⊗ ⋯ ⊗ p_{n}(x_{n}, x_{n−1}) [figure: α] q(fx_{n}, gx_{0}),

one for each tuple (x_{0}, …, x_{n}) ∈ X_{0} × ⋯ × X_{n}. When n = 0, of course, the n-ary tensor product on the left is to be interpreted as the unit object of V.

In particular, if V is the 2-element chain 0 ≤ 1, with ⊗ given by ∧, then the horizontal arrows of V-𝕄at are relations. In this case we denote V-𝕄at by ℝel.

It is well-known that V-matrices form a bicategory (and, in fact, a pseudo double category) as long as V has coproducts preserved by ⊗. However, if we merely want a virtual double category, we see that this requirement is unnecessary. (In fact, V could be merely a multicategory itself.)

2.7. Example. For a category C with pullbacks, the virtual double category 𝕊pan(C) is defined as follows: its objects and vertical arrows are those of C, its horizontal arrows X [figure: p] Y are spans X [figure] P [figure] Y, and a cell of the form (2.2) is a morphism of spans

P_{1} ×_{X_{1}} P_{2} ×_{X_{2}} ⋯ ×_{X_{n−1}} P_{n} [figure: α] Q

lying over f and g. When n = 0, the n-ary span composite in the domain is to be interpreted as the identity span X_{0} [figure] X_{0} [figure] X_{0}.

Note that in this case, we do need to require that C have pullbacks. If C does not have pullbacks, a more natural setting would be to consider 𝕊pan(C) as a “co-virtual double category”, in which the horizontal target of a cell is a string of horizontal arrows. However, co-virtual double categories do not provide the structure necessary to define generalized multicategories.

We now recall the construction of monoids and modules in a virtual double category from [Lei04, §5.3].

592  G.S.H. CRUTTWELL AND MICHAEL A. SHULMAN

2.8. Definition. Let 𝕏 be a virtual double category. The virtual double category 𝕄od(𝕏) has the following components:

• The objects (monoids) consist of four parts (X_{0}, X, x̄, x̂): an object X_{0} of 𝕏, a horizontal endo-arrow X_{0} [figure: X] X_{0} in 𝕏, and multiplication and unit cells

[figure: X_{0}; X_{0}; X_{0}; X_{0}; X_{0}; X; X; X; x̄; and; X_{0}; X_{0}; X_{0}; X_{0}; X_{0}; X_{0}; X; x̂]

satisfying associativity and identity axioms.

• The vertical arrows (monoid homomorphisms) consist of two parts (f_{0}, f): a vertical arrow X_{0} [figure: f_{0}] Y_{0} in 𝕏 and a cell in 𝕏:

[figure: X_{0}; X_{0}; Y_{0}; Y_{0}; X; Y; f_{0}; f_{0}; f]

which is compatible with the multiplication and units of X and Y.

• The horizontal arrows (modules) consist of three parts (p, p̄_{r}, p̄_{l}): a horizontal arrow X_{0} [figure: p] Y_{0} in 𝕏 and two cells in 𝕏:

[figure: X_{0}; X_{0}; Y_{0}; X_{0}; Y_{0}; X; p; p; p̄_{r}; and; X_{0}; Y_{0}; Y_{0}; X_{0}; Y_{0}; p; Y; p; p̄_{l}]

which are compatible with the multiplication and units of X and Y.

• The cells are cells in 𝕏:

[figure: (Y^{0})_{0}; (Y^{1})_{0}; (X^{0})_{0}; (Y^{0})_{0}; f_{0}; (X^{0})_{0}; (X^{n})_{0}; (X^{n})_{0}; (Y^{1})_{0}; g_{0}; (Y^{0})_{0}; (Y^{1})_{0}; q; (X^{0})_{0}; (X^{1})_{0}; p_{1}; (X^{1})_{0}; (X^{2})_{0}; p_{2}; (X^{2})_{0}; ⋯; p_{3}; ⋯; (X^{n})_{0}; p_{n}; α]

which are compatible with the left and right actions of the horizontal cells. Note that, as observed in [Lei04, §5.3], we can define 𝕄od(𝕏) without requiring any

hypotheses on the virtual double category 𝕏, in contrast to the situation for bicategories or pseudo double categories.

2.9. Example. We denote the virtual double category 𝕄od(V-𝕄at) by V-ℙrof; its objects are V-enriched categories, its vertical arrows are V-functors, its horizontal arrows are V-profunctors, and its cells are a generalization of the “forms” of [DS97] (including, as a special case, natural transformations between profunctors). When V is closed (hence enriched over itself) and symmetric, V-profunctors C [figure: H] D can be identified with Vfunctors D^{op} × C [figure] V.

Again, note that because we are working with virtual double categories, we do not require that V have any colimits (in fact, V could be merely a multicategory).

2.10. Example. Let C be a category with pullbacks. We denote the virtual double category 𝕄od(𝕊pan(C)) by ℙrof(C); it consists of internal categories, functors, profunctors, and transformations in C.

Note that Set-𝕄at ≅ 𝕊pan(Set) and thus Set-ℙrof ≅ ℙrof(Set).

3. Monads on a virtual double category

We claimed in §1 that the “inputs” of a generalized multicategory are parametrized by a monad. Why should this be so? Suppose that we have an operation T which, given a set (or object) of objects X, produces a set (or object) T X intended to parametrize such inputs. For “ordinary” multicategories, T X will be the set of finite lists of elements of X.

Now, from the perspective of the previous section, the data of a category includes an object A_{0} and a horizontal arrow A_{0} [figure: A] A_{0} in some virtual double category. For example, if we work in Set-𝕄at, then A is a matrix consisting of the hom-sets A(x, y) for every x, y ∈ A_{0}. Now, instead, we want to have hom-sets A(𝔵, y) whose domain 𝔵 is an element of T A_{0}. Thus, it makes sense to consider a horizontal arrow A_{0} [figure: A] T A_{0} as part of the data of a T -multicategory. (We use A_{0} [figure] T A_{0} rather than T A_{0} [figure] A_{0}, for consistency with Examples 2.9 and 2.10: the codomain of the horizontal arrow datum of a monoid specifies the domains of the arrows in that monoid.)

However, we now need to specify the units and composition of our generalized multicategory. The unit should be a cell into A with 0-length domain, but its source and target vertical arrows can no longer both be identities because A_{0} ≠ T A_{0}. In an ordinary multicategory, the identities are morphisms (x) [figure: 1_{x}] x whose domain is a singleton list; in terms of Set-𝕄at this can be described by a cell

[figure: A_{0}; T A_{0}; A; A_{0}; A_{0}; A_{0}; T A_{0}; η]

where A_{0} [figure: η] T A_{0} is the inclusion of singleton lists.

Regarding composition, in an ordinary multicategory we can compose a morphism (y_{1}, …, y_{n}) [figure: g] z not with a single morphism, but with a list of morphisms (f_{1}, …, f_{n})

where (x_{i1}, …, x_{ik_{i}}) [figure: f_{i}] y_{i}. In terms of Set-𝕄at this represents the fact that we cannot ask for a multiplication cell with domain [figure: A] [figure: A] , since the domain of A does not match its codomain, but instead we can consider a cell with domain [figure: A][figure: T A] , where we extend T to act on Set-matrices in the obvious way. Now, however, the codomain of T A is T^{2}A_{0}; in order to have a cell with codomain A we need to “remove parentheses” from the resulting domain ((x_{11}, …, x_{1k_{1}}), …, (x_{n1}, …, x_{nk_{n}})) to obtain a single list. Thus the composition should be a cell

[figure: A_{0}; T A_{0}; A; A_{0}; A_{0}; A_{0}; T^{2}A_{0}; T^{2}A_{0}; T A_{0}; μ; A_{0}; T A_{0}; A; T A_{0}; T^{2}A_{0}; T A]

where μ is the “remove parentheses” function. Of course, these functions η and μ are the structure maps of the “free monoid” monad on Set. Thus we see that in order to define ordinary multicategories, what we require is an “extension” of this monad to Set-𝕄at.

In order to have a good notion of a monad on a virtual double category, we need at least a 2-category of virtual double categories. Since virtual double categories are themselves a special case of generalized multicategories, it suffices to observe that generalized multicategories of any sort form a 2-category. However, since we have not yet defined generalized multicategories in our context, at this point in our exposition it is appropriate to give an explicit description of the 2-category vDbl.

Of course, the objects of vDbl are virtual double categories, and its 1-morphisms (called functors of virtual double categories) are the obvious structure-preserving maps: functions from the objects, vertical and horizontal arrows, and cells of the domain to those of the codomain, preserving all types of source, target, identities, and composition. However, the definition of 2-morphisms in vDbl is slightly less obvious.

3.1. Definition. Given functors 𝕏 [figure: F; G] 𝕐 of virtual double categories, a transforma-

tion F [figure: θ] G consists of the following data.

• For each object X in 𝕏, a vertical arrow F X [figure: θ_{X}] GX, which form the components of a natural transformation between the vertical parts of F and G.

• For each horizontal arrow X [figure: p] Y in 𝕏, a cell in 𝕐:

[figure: F X; F Y; GX; GY; F p; Gp; θ_{X}; θ_{Y}; θ_{p}]  (3.2)

• An axiom asserting that θ is “cell-natural,” meaning that

θ_{q}(F α) = (Gα)(θ_{p_{1}} ⊡ ⋯ ⊡ θ_{p_{n}})

whenever this makes sense.

Virtual double categories, functors, and transformations form a 2-category denoted vDbl.

3.3. Example. Any lax monoidal functor V [figure: N] W induces functors V-𝕄at [figure: N_{∗}] W-𝕄at and V-ℙrof [figure: N_{∗}] W-ℙrof in an evident way. Moreover, any monoidal natural transfor-

mation N [figure: ψ] M between lax monoidal functors induces transformations N_{∗} [figure: ψ_{∗}] M_{∗} in both cases. In this way (−)-𝕄at and (−)-ℙrof become 2-functors from the 2-category of monoidal categories to vDbl.

3.4. Example. Similarly, any pullback-preserving functor C [figure: N] D between categories with pullbacks induces functors 𝕊pan(C) [figure: N_{∗}] 𝕊pan(D) and ℙrof(C) [figure: N_{∗}] ℙrof(D), and

any natural transformation N [figure: ψ] M between such functors induces transformations

N_{∗} [figure: ψ_{∗}] M_{∗}, thereby making 𝕊pan(−) and ℙrof(−) into 2-functors as well.

3.5. Example. When restricted to bicategories or pseudo double categories, functors of virtual double categories are equivalent to the usual notions of lax functor.

This is a special case of a general fact; see Theorem 9.13. When transformations of virtual double categories are similarly restricted, they become icons in the sense of [Lac10] (for bicategories) and vertical transformations (for pseudo double categories).

By a monad on a virtual double category 𝕏, we will mean a monad in the 2-category vDbl. Thus, it consists of a functor T: 𝕏 [figure] 𝕏 and transformations η: Id [figure] T and μ: T T [figure] T satisfying the usual axioms. We now give the examples of such monads that we will be interested in.

3.6. Example. Since 2-functors preserve monads, any pullback-preserving monad on a category C with pullbacks induces monads on 𝕊pan(C) and ℙrof(C). Examples of such monads include the following.

• The “free monoid” monad on Set (or, more generally, on any countably lextensive category).

• The “free M-set” monad (M × −) on Set, for any monoid M (or more generally, for any monoid object in a category with finite limits).

• The monad (−) + 1 on any lextensive category.

• The “free category” monad on the category of directed graphs.

• The “free strict ω-category” monad on the category of globular sets.

Many more examples can be found in [Lei04, pp. 103–107]; see also §B.1. By the argument above, each of these monads extends to a monad on a virtual double category of spans.

The assignments V ↦ V-𝕄at and V ↦ V-ℙrof are also 2-functorial, but the monads we obtain in this way from monads on monoidal categories are not usually interesting for defining multicategories. However, there are some general ways to construct monads on virtual double categories of matrices, at least when V is a preorder. The following is due to [Sea05], which in turn expands on [CHT04].

3.7. Example. By a quantale we mean a closed symmetric monoidal complete lattice. A quantale is completely distributive if for any b ∈ V we have b = ⋁{a | a ≺ b}, where a ≺ b means that whenever b ≤ ⋁ S then there is an s ∈ S with a ≤ s. (If in this definition S is required to be directed, we obtain the weaker notion of a continuous lattice.) For us, the two most important completely distributive quantales are the following.

• The two-element chain 2 = (0 ≤ 1).

• The extended nonnegative reals \overline{R_{+}} = [0, ∞] with the reverse of the usual ordering and ⊗ = +.

A functor said to be taut if it preserves pullbacks of monomorphisms (and therefore also preserves monomorphisms). A monad is taut if its functor part is taut, and moreover the naturality squares of η and μ for any monomorphism are pullbacks. Some important taut monads on Set are the identity monad, the powerset monad (whose algebras are complete lattices), the filter monad, and the ultrafilter monad (whose algebras are compact Hausdorff spaces).

Now let V be a completely distributive quantale and T a taut monad on Set. For a V-matrix X [figure: p] Y and elements F ∈ T X and G ∈ T Y, define

T p(G, F) = ⋁{v ∈ V | ∀B ⊆ Y : (G ∈ T B ⇒ F ∈ T (p_{v}[B]))},

where

p_{v}[B] = {x ∈ X | ∃y ∈ B : v ≤ p(y, x)}.

It is proven in [Sea05] that this action on horizontal arrows extends T to a monad on V-𝕄at. (Actually, Seal shows that it is a “lax extension of T to V-Mat with op-lax unit and counit”; we will show in §B.6 that this is the same as a monad on V-𝕄at.)

In [Sea05] this monad on V-𝕄at is called the “canonical extension” of T (note, however, that it is written backwards from his definition, as our Kleisli arrows will be X [figure] T Y, whereas his are T X [figure] Y). Since V-𝕄at is isomorphic to its “horizontal opposite,” there is also an “op-canonical extension”, which is in general distinct (although in some cases, such as for the ultrafilter monad, the two are identical). There are also many other extensions: for more detail, see [SS08].

Another general way of constructing monads on virtual double categories is to apply the construction 𝕄od from the previous section, which turns out to be a 2-functor. Its 1functoriality is fairly obvious and was described in [Lei04, §5.3]; its action on 2-morphisms is given as follows.

3.8. Definition. Let 𝕏 [figure: F; G] 𝕐 be functors between virtual double categories, and F [figure: θ] G

a transformation. One can define a transformation

𝕄od(F) [figure: 𝕄od(θ)] 𝕄od(G)

whose vertical-arrow component at an object (X_{0}, X, x̄, x̂) is the monoid homomorphism

[figure: F X_{0}; F X_{0}; GX_{0}; GX_{0}; F (X); G(X); θ_{X_{0}}; θ_{X_{0}}; θ_{X}]

and whose cell component at a horizontal arrow (p, p̄_{r}, p̄_{l}) is given by

[figure: F X_{0}; F Y_{0}; GX_{0}; GY_{0}; F p; Gp; θ_{X_{0}}; θ_{Y_{0}}; θ_{p}]

3.9. Proposition. With action on objects, 1-cells, and 2-cells described above, 𝕄od is an endo-2-functor of vDbl.

Note that the 2-functors (−)-ℙrof and ℙrof(−) can now be seen as the composites of 𝕄od with (−)-𝕄at and 𝕊pan(−), respectively.

3.10. Corollary. A monad T on a virtual double category 𝕏 induces a monad 𝕄od(T) on 𝕄od(𝕏).

3.11. Example. Any monad T on V-𝕄at induces a monad on V-ℙrof. For instance, this applies to the monads constructed in Example 3.7.

3.12. Example. Let V be a symmetric monoidal category with an initial object ∅ preserved by ⊗. Then the “free monoid” monad T on Set extends to a monad on V-𝕄at

as follows: a V-matrix X [figure: p] Y is sent to the matrix T X [figure: T p] T Y defined by

T p((y_{1}, …, y_{m}), (x_{1}, …, x_{n})) = \begin{cases}p(y_{1}, x_{1}) ⊗ … ⊗ p(y_{n}, x_{n}) & if n = m \\ ∅ & if n ≠ m \end{cases}

Applying 𝕄od, we obtain an extension of the “free strict monoidal V-category” monad from V-Cat to V-ℙrof.

3.13. Example. Likewise, any monad T on 𝕊pan(C) extends to a monad on ℙrof(C). But most interesting monads on 𝕊pan(C) are induced from C, so this gains us little beyond the observation that ℙrof(−) is a 2-functor.

Not every monad on V-ℙrof or ℙrof(C) is induced by one on V-𝕄at or 𝕊pan(C), however. The following examples are also important.

3.14. Example. Let V be a symmetric monoidal category with finite colimits preserved by ⊗ on both sides. Then there is a “free symmetric strict monoidal V-category” monad T on V-Cat, defined by letting the objects of T X be finite lists of objects of X, with

T X((x_{1}, …, x_{n}), (y_{1}, …, y_{m})) = \begin{cases}∑_{σ∈S_{n}} ⨂_{1≤i≤n} X(x_{σ(i)}, y_{i}) & if n = m \\ ∅ & if n ≠ m. \end{cases}

A nearly identical-looking definition for profunctors extends this T to a monad on V-ℙrof. A similar definition applies for braided monoidal V-categories.

3.15. Example. For V as in Example 3.14, there is also a “free V-category with strictly associative finite products” monad on V-Cat. The objects of this T X are again finite lists of objects of X, but now we have

T X((x_{1}, …, x_{m}), (y_{1}, …, y_{n})) = ∏_{1≤i≤n} ∑_{1≤j≤m} X(x_{j}, y_{i}).

If V is cartesian monoidal, then this can equivalently be written as

T X((x_{1}, …, x_{m}), (y_{1}, …, y_{n})) = ∑_{α: n→m} ∏_{1≤i≤n} X(x_{α(i)}, y_{i}).

Again, a nearly identical definition for profunctors extends this to a monad on V-ℙrof.

3.16. Example. Monads that freely adjoin other types of limits and colimits also extend from V-Cat to V-ℙrof in a similar way. For instance, if V is a locally finitely presentable closed monoidal category as in [Kel82], there is a “free V-category with cotensors by finitely presentable objects” monad on V-Cat. An object of T X consists of a pair^{3} (v; x) where x ∈ X and v ∈ V is finitely presentable. On homs we have

T X((v; x), (w; y)) = [w, X(x, y) ⊗ v].

As before, a nearly identical definition extends this to V-ℙrof.

3To be precise, this definition only gives a pseudomonad on V-Cat. It is, however, easy to modify it to make a strict monad.

4. Generalized multicategories

We now lack only one final ingredient for the definition of generalized multicategories. Since multicategories are like categories, we expect them to also be monoids in some virtual double category. However, as we have seen in §3, their underlying data should include a horizontal arrow A_{0} [figure] T A_{0} rather than A_{0} [figure] A_{0}. Thus we need to construct, given T and 𝕏, a virtual double category in which the horizontal arrows are horizontal arrows of the form A_{0} [figure] T A_{0} in 𝕏. This is the purpose of the following definition.

4.1. Definition. Let T be a monad on a virtual double category 𝕏. Define the horizontal Kleisli virtual double category of T, ℍ-Kl(𝕏, T), as follows.

• Its vertical category is the same as that of 𝕏.

• A horizontal arrow X [figure: p] Y is a horizontal arrow X [figure: p] T Y in 𝕏.

• A cell with nullary source uses the unit of the monad, so that a cell

[figure: X; Y; f; X; Z; g; Y; Z; p; α]

in ℍ-Kl(𝕏, T) is a cell

[figure: X; Y; f; X; T X; η; T X; T Z; T g; Y; T Z; p; α]

in 𝕏 (note that T g ∘ η = η ∘ g by naturality).

• A cell with non-nullary source uses the multiplication of the monad, so that a cell

[figure: Y_{0}; Y_{1}; X_{0}; Y_{0}; f; X_{0}; X_{n}; X_{n}; Y_{1}; g; Y_{0}; Y_{1}; q; X_{0}; X_{1}; p_{1}; X_{1}; X_{2}; p_{2}; X_{2}; ⋯; p_{3}; ⋯; X_{n}; p_{n}; α]

in ℍ-Kl(𝕏, T) is a cell

[figure: X_{0}; Y_{0}; f; Y_{0}; T Y_{1}; q; X_{0}; T X_{1}; p_{1}; T X_{1}; T^{2}X_{2}; T p_{2}; T^{2}X_{2}; ⋯; T^{2}p_{3}; ⋯; T^{n}X_{n}; T^{n−1}p_{n}; T^{n}X_{n}; ⋮; μ; ⋮; T X_{n}; μ; T X_{n}; T Y_{1}; T g; α]

in 𝕏 (note that T g ∘ μ^{n−1} = μ^{n−1} ∘ T^{n}g, by naturality).

• The composite of

[figure: ⋯; α_{1}; ⋯; α_{2}; ⋯; α_{n}; ⋯; β]

is given by the composite of in 𝕏.

• Identity cells use those of 𝕏:

[figure: α_{1}; ⋯; μ; ⋯; μ; μ; μ; ⋯; ⋯; ⋯; μ; μ; T μ; T α_{2}; ⋯; T μ; μ; μ; μ; μ; T μ; T^{2}μ; T^{2}α_{3}; ⋯; ⋯; ⋯; ⋯; ⋯; μ; μ; T μ; T^{2}μ; T^{3}α_{4}; μ; μ; μ; μ; T μ; T μ; ⋯; ⋯; ⋯; ⋯; ⋯; ⋯; ⋯; ⋯; ⋯; T^{n−2}μ; T^{n−2}μ; ⋯; T^{n−1}α_{n}; β]

[figure: X; T Y; X; T Y; p; p; 1_{P}]

In general, the associativity for ℍ-Kl(𝕏, T) is shown by using the (cell) naturality of μ and η, as well as the monad axioms. The general associativity is too large a diagram to show here; instead, we will demonstrate a sample associativity calculation, which is representative of the general situation. Consider the following cells in ℍ-Kl(𝕏, T):

[figure: α_{1}; α_{2}; α_{3}; α_{4}; β_{1}; β_{2}; γ]

There are two possible ways to compose these cells: either composing the bottom first:

(γ(β_{1} ⊡ β_{2}))(α_{1} ⊡ α_{2} ⊡ α_{3} ⊡ α_{4})

or the top two first, followed by composition with the bottom:

γ((β_{1}(α_{1} ⊡ α_{2})) ⊡ (β_{2}(α_{3} ⊡ α_{4})))

The first composite is given by the following composite in 𝕏:

By using cell naturality of μ twice, the above becomes we then use the monad axiom T μ ∘ μ = μ ∘ μ to get

[figure: α_{1}; T α_{2}; T μ; T μ; T^{2}α_{3}; T^{3}α_{4}; β_{1}; μ; μ; T β_{2}; γ] [figure: α_{1}; T α_{2}; T μ; T μ; μ; μ; β_{1}; T α_{3}; T^{2}α_{4}; T β_{2}; γ]

[figure: α_{1}; T α_{2}; μ; μ; μ; μ; β_{1}; T α_{3}; T^{2}α_{4}; T β_{2}; γ]

which is the second composite γ((β_{1}(α_{1} ⊡ α_{2})) ⊡ (β_{2}(α_{3} ⊡ α_{4}))).

4.2. Remark. Unfortunately, we do not know of any universal property satisfied by this construction. In particular, ℍ-Kl(𝕏, T) is not a Kleisli object for T in vDbl in the sense of [Str72a]; the latter would instead contain vertical Kleisli arrows. In fact, for general 𝕏 there need not even be a canonical functor 𝕏 [figure] ℍ-Kl(𝕏, T).

We can now give our first preliminary definition of generalized multicategories relative to a monad T.

4.3. Definition. Let T be a monad on a virtual double category 𝕏. A T -monoid is defined to be a monoid in ℍ-Kl(𝕏, T), and likewise for a T -monoid homomorphism. We denote the virtual double category 𝕄od(ℍ-Kl(𝕏, T)), whose objects are T -monoids, by 𝕂Mod(𝕏, T).

As a reference, the data for a T -monoid consists of an object X_{0} ∈ 𝕏, a horizontal arrow X_{0} [figure: X] T X_{0} in 𝕏, and cells

[figure: X_{0}; T X_{0}; X_{0}; X_{0}; X_{0}; T^{2}X_{0}; T^{2}X_{0}; T X_{0}; μ; X_{0}; T X_{0}; X; X_{0}; T X_{0}; X; T X_{0}; T^{2}X_{0}; T X; x̄; and; X_{0}; X_{0}; X_{0}; T X_{0}; η; X_{0}; T X_{0}; X; x̂]

Note that these cells have precisely the forms we predicted at the beginning of §3.

4.4. Remark. We have seen in §2 that 𝕄od is a 2-functor. In fact, under suitable hypotheses (involving the notions of restriction and composites to be introduced in §5 and §7), ℍ-Kl is also a (pseudo) functor, and thus so is 𝕂Mod. In fact, ℍ-Kl is a pseudo functor in two different ways, corresponding to the two different kinds of morphisms of monads: lax and colax. This was observed by [Lei04] in his context; we will discuss the functoriality of ℍ-Kl and 𝕂Mod in our framework in the forthcoming [CS10a].

We now consider some examples.

4.5. Example. Of course, if T is the identity monad on any 𝕏, then a T -monoid is just a monoid, and 𝕂Mod(𝕏, T) = 𝕄od(𝕏).

Recall from Example 3.6 that any pullback-preserving monad C [figure: T] C extends to a monad on 𝕊pan(C).

4.6. Example. If T is the “free monoid” monad extended to 𝕊pan(Set) ≅ Set-𝕄at, then a T -monoid consists of a set A_{0}, a Set-matrix {A((x_{1}, …, x_{n}), y)}_{x_{i},y∈A_{0}}, and composition and identity functions. It is easy to see that this reproduces the notion of an ordinary multicategory. Likewise, T -monoid homomorphisms are functors between multicategories.

4.7. Example. If T is the “free category” monad on directed graphs, then a T -monoid is a virtual double category. (This is, of course, the origin of the name “fc-multicategory,” where fc is a name for this monad.) The vertices and edges of the directed graph A_{0} are the objects and horizontal arrows, respectively, while in the span A_{0} ← A → T A_{0} the vertices of A are the vertical arrows and its edges are the cells. Likewise, T -monoid homomorphisms are functors between virtual double categories.

4.8. Example. Let M be a monoid and T = (M × −) the “free M-set” monoid on 𝕊pan(Set). A T -monoid consists of a set A_{0} and a family of sets {A(m; x, y)}_{x,y∈A_{0},m∈M}. The composition and identity functions make it into an M-graded category, i.e. a category in which every arrow is labeled by an element of M in a way respecting composition and identities. The case M = ℤ may be most familiar.

4.9. Example. Let C be a lextensive category and T the monad (−) + 1 on 𝕊pan(C). A T -monoid consists of an object A_{0} and a span A_{0} ← A → A_{0} + 1; since S is extensive, A decomposes into two spans A_{0} ← A_{1} → A_{0} and A_{0} ← B → 1. The composition and identity functions then make the first span into an internal category in C and the second into an internal diagram over this category.

4.10. Example. Let S be a small category, and let T be the monad on Set^{ob(S)} whose algebras are functors S [figure] Set. Thus, for a family {A_{x}}_{x∈ob(S)} in Set^{ob(S)} we have

(T A)_{x} = ∐_{y∈ob(S)} A_{y} × S(x, y).

This T preserves pullbacks, so it induces a monad on 𝕊pan(Set^{ob(S)}). A T -monoid

A [figure: M] T A can be identified with a category over S, i.e a functor A [figure] S. Namely, the elements of the set A_{x} are the objects of the fiber of A over x ∈ ob(S), while M can be broken down into a collection of spans

A_{x} [figure] M_{x,y} [figure] A_{y} × S(x, y),

which together supply the arrows of A and their images in S. The morphisms of T - monoids are likewise the functors over S.

4.11. Example. If T is the “free strict ω-category” monad on 𝕊pan(Globset), then a T -monoid of the form 1 [figure] T 1 can be identified with a globular operad in the sense of [Bat98], as described in [Lei04]. General T -monoids are globular multicategories (or many-sorted globular operads) as considered in [Lei04, p.273–274].

Recall from Example 3.7 that any taut monad T on Set (such as the identity monad, the powerset monad, the filter monad, or the ultrafilter monad) extends to a monad on V-𝕄at for any completely distributive quantale V (such as 2 or \overline{R_{+}}). We will show in §B.6 that in such a case, our T -monoids are the same as the (T, V)-algebras studied by [CT03, CHT04, Sea05], and others; thus we have the following examples.

4.12. Example. If T is the identity monad, then 𝕂Mod(V-𝕄at, T) = V-ℙrof. Thus, for V = 2, T -monoids are preorders; and for V = \overline{R_{+}}, T -monoids are metric spaces (in the sense of [Law02]).

4.13. Example. If T is the ultrafilter monad, and V = 2, then a T -monoid consists of a set equipped with a binary relation between ultrafilters and points satisfying unit and composition axioms. If we call this relation “convergence,” then the axioms precisely characterize the convergence relation in a topological space; thus T -monoids are topological spaces, and T -monoid homomorphisms are continuous functions. This observation is originally due to [Bar70] (note that although his construction of an ultrafilter monad on ℝel looks quite different, it is in fact the same).

4.14. Example. If T is the powerset monad, and V = 2, then T -monoids are closure spaces. A closure space consists of a set A equipped with an operation c(−) on subsets which is:

• extensive: X ⊆ c(X),

• monotone: Y ⊆ X ⇒ c(Y) ⊆ c(X), and

• idempotent: c(c(X)) ⊆ c(X).

4.15. Example. If T is the ultrafilter monad and V = \overline{R_{+}}, then T -monoids are equivalent to approach spaces. An approach space is a set X equipped with a function d : X × P X [figure] [0, ∞] such that

• d(x, {x}) = 0,

• d(x, ∅) = ∞,

• d(x, A ∪ B) = min{d(x, A), d(x, B)}, and

• ∀ϵ ≥ 0, d(x, A) ≤ d(x, {x : d(x, A) ≤ ϵ}) + ϵ.

Approach spaces have found applications in approximation theory, products of metric spaces, and measures of non-compactness: for more detail, see [Low88].

Finally, we consider T -monoids relative to the additional examples of monads on V-ℙrof from the end of §3.

4.16. Example. Let T be the “free symmetric strict monoidal V-category” monad on V-ℙrof from Example 3.14. If A_{0} is a discrete V-category, then a T -monoid A_{0} [figure: A] T A_{0} is a symmetric V-enriched multicategory (known to some authors as simply a “multicategory”). Likewise, from the “free braided strict monoidal V-category” monad we obtain braided multicategories.

If A_{0} is not discrete, then a T -monoid (for V = Set) is a symmetric multicategory in the sense of [BD98] and [Che04]: in addition to the multi-arrows, there is also another type of arrow between the objects of the multicategory which forms a category, and which acts on the multi-arrows.

4.17. Example. Let T be the “free category with strictly associative finite products” monad on Set-ℙrof from Example 3.15. If A_{0} is a one-object discrete category, then a T -monoid A_{0} [figure: A] T A_{0} is a Lawvere theory, as in [Law63]. If A_{0} has more than one object, but is still discrete, then a T -monoid A_{0} [figure: A] T A_{0} is a “multi-sorted” Lawvere theory.

This is a little different from the more usual definition of Lawvere theory, but the equivalence between the two is easy to see. A Lawvere theory is commonly defined to be a category A with object set ℕ such that each object n is the n-fold product 1^{n}. This implies that A(m, n) ≅ A(m, 1)^{n}, so it is equivalent to give just the collection of sets A(m, 1) with suitable additional structure. Since T 1 has object set ℕ, a T -monoid 1 [figure] T 1 also consists of sets A(m, 1) for m ∈ ℕ, and it is then straightforward to verify that the additional structures in the two cases are in bijective correspondence. Note, however, that the morphisms between such T -monoids do not correspond to all of the morphisms between theories considered in [Law63], but only those of “degree one;” the others are only visible from the “category with object set ℕ” viewpoint.

The relationship between these two definitions of Lawvere theory is analogous to the way in which an operad can also be defined as a certain sort of monoidal category with object set ℕ. In fact, both arise from a very general adjunction between T -algebras and T -monoids; see Remark 9.16 and the forthcoming [CS10b].

4.18. Example. If T is the “free V-category with strictly associative finite products” monad on V-ℙrof from Example 3.15 and A_{0} is a one-object discrete V-category, then a T -monoid A_{0} [figure: A] T A_{0} is a “V-enriched finite product theory.” If A_{0} is unchanged but T is instead the “free V-category with finitely presentable cotensors” monad from Example 3.16, then a T -monoid A_{0} [figure: A] T A_{0} is a “Lawvere V-theory” as defined in [Pow99] (with the same caveat as in the previous example). To obtain a “multi-sorted Lawvere V-theory” we need T to adjoin both finite products and finite cotensors.

4.19. Example. If T is any of

• the “free symmetric strict monoidal category” monad,

• the “free category with strictly associative finite products” monad, or

• the “free category with strictly associative finite coproducts” monad, but now considered as a monad on 𝕊pan(Cat), then a T -monoid with a discrete category of objects is a club in the sense of [Kel72b] and [Kel72a] (relative to P, S, or S^{op}, in Kelly’s terminology). See also §B.4.

4.20. Remark. When T is the “free symmetric strict monoidal category” monad on Set-ℙrof, the horizontal arrows between discrete categories in ℍ-Kl(Set-ℙrof, T) are the generalized species of structure of [FGHW08] (called structure types in [BD01]). The espéces de structures of [Joy81, Joy86] are the particular case of horizontal arrows 1 [figure] 1 in ℍ-Kl(Set-ℙrof, T). Likewise, when T is the analogous monad on 𝕊pan(Gpd), the horizontal arrows in ℍ-Kl(𝕊pan(Gpd), T) are the (generalized) stuff types of [BD01, Mor06].

We can see from these examples that for virtual double categories whose objects are “category-like,” it is often the T -monoids whose objects are discrete which are of particular interest. We will make this notion precise in §8, and propose that often a better solution is to consider “normalized” T -monoids.

First, however, we must develop some additional machinery for virtual double categories. We will describe when horizontal arrows have units and composites, as well as when horizontal arrows can be “restricted” along vertical arrows. With this theory in hand, we can then return to study “object discrete” and “normalized” T -monoids, as well as when such T -monoids are “representable”.

4.21. Remark. If V is a complete and cocomplete closed symmetric monoidal category, then the virtual double category V-ℙrof is itself “almost” of the form ℍ-Kl(𝕏, T). We take 𝕏 to be the double category 𝕊q(V-Cat), whose objects are V-categories, whose vertical and horizontal arrows are both V-functors, and whose cells are V-natural transformations, and we define T A = V^{Aop} to be the enriched presheaf category of A. The observation is then that a V-profunctor A [figure] B can be identified with an ordinary V-functor A [figure] V^{Bop}, so that V-ℙrof is almost the same as ℍ-Kl(𝕊q(V-Cat), T). This is not quite right, since T is not really a monad due to size issues. But these problems can be dealt with, for instance by using “small presheaves” as in [DL07].

Assuming the functoriality of ℍ-Kl mentioned in Remark 4.4, this observation implies that if S is another monad on V-Cat related to T by a distributive law, or equivalently a monad in the 2-category of monads and monad morphisms (see [Bec69, Str72b]), then S induces a monad on V-ℙrof, which we can in turn use to define generalized multicategories as S-monoids in V-ℙrof. For example, since a symmetric monoidal structure on A extends to T A by Day convolution, the “free symmetric monoidal V-category” monad distributes over T, inducing its extension to V-ℙrof considered in Example 3.14. This is the argument used in [FGHW08] to construct the bicategory H(ℍ-Kl(V-ℙrof, T)). Similar arguments apply to the monad from Example 3.15.

5. Composites and units

In §2 we introduced (virtual) double categories as a framework in which one can define monoids and monoid homomorphisms so as to include both enriched and internal categories with the appropriate notions of functor. However, we would certainly like to be able to recover natural transformations as well, but this requires more structure than is present in a virtual double category.

It is not hard to see that the vertical category of any (pseudo) double category can be enriched to a vertical 2-category, whose 2-cells f ⇒ g are the squares of the form

[figure: A; g; A; f; B; B,]

and that in examples such as ℙrof(C) and V-ℙrof these 2-cells recover the appropriate notion of natural transformation. In a virtual double category this definition is impossible, since there may not be any horizontal identity arrows. However, it turns out that we can characterize those horizontal identities which do exist by means of a universal property. In fact, it is not much harder to characterize arbitrary horizontal composites (viewing identities as 0-ary composites). In this section we study such composites; in the next section we will use them to define vertical 2-categories.

5.1. Definition. In a virtual double category, a cell

[figure: p_{1}; _{⇓_{opcart}}; p_{2}; …; p_{n}; q]

is said to be opcartesian if any cell

[figure: r_{1}; f; r_{2}; …; r_{m}; p_{1}; ⇓; p_{2}; …; p_{n}; s_{1}; s_{2}; …; s_{k}; g; t]

factors through it uniquely as follows:

[figure: r_{1}; r_{2}; …; r_{m}; ···; p_{1}; _{⇓_{opcart}}; p_{2}; …; p_{n}; s_{1}; s_{2}; …; s_{k}; ···; r_{1}; f; r_{2}; …; r_{m}; q; ⇓; s_{1}; s_{2}; …; s_{k}; g; t; .]

If a string of composable horizontal arrows is the source of some opcartesian cell, we say that it has a composite. We refer to the target q of that cell as a composite of the given string and write it as p_{1} ⊙ ⋯ ⊙ p_{n}. Similarly, if n = 0 and there is an opcartesian cell of the form

[figure: X; ⇓; X; U_{X}; X.]

we say that X has a unit U_{X}.

These universal properties make it easy to show that composites and units, when they exist, behave like composites and units in a pseudo double category. For example, composites and units are unique up to isomorphism: given two opcartesian arrows with the same source, factoring each through the other gives an isomorphism between their targets. Likewise, the composite of opcartesian cells is opcartesian, so composition is associative up to coherent isomorphism whenever all relevant composites exist. More precisely, if p ⊙ q exists, then (p ⊙ q) ⊙ r exists if and only if p ⊙ q ⊙ r exists, and in that case they are isomorphic. It follows that if p ⊙ q and q ⊙ r exist, then

(p ⊙ q) ⊙ r ≅ p ⊙ (q ⊙ r),

each existing if the other does. Similarly, any string in which all but one arrow is a unit:

[figure: X; U_{X}; …; U_{X}; X; p; Y; U_{Y}; …; U_{Y}; Y]

has a composite, which is (isomorphic to) p.

The following theorem, which was also observed in [DPP06], is a straightforward generalization of the relationship between monoidal categories and ordinary multicategories described in [Her00]. It is also a special case of the general relationship between pseudo algebras and generalized multicategories, as in [Lei04, §6.6], [Her01], and §9 of the present paper.

5.2. Theorem. A virtual double category is a pseudo double category if and only if every string of composable horizontal arrows (including zero-length ones) has a composite.

Proof (sketch). “Only if” is clear, by definition of how a pseudo double category becomes a virtual one. For “if”, we use the isomorphisms constructed above; we invoke again the universal property of opcartesian cells to show coherence.

5.3. Example. If V has an initial object ∅ which is preserved by ⊗ on both sides, then V-𝕄at has units: the unit of a set X is the matrix

U_{X}(x, x′) = \begin{cases}I & x = x′ \\ ∅ & x ≠ x′. \end{cases}

If V has all small coproducts which are preserved by ⊗ on both sides, then V-𝕄at has composites given by “matrix multiplication.” For instance, the composite of matrices X [figure: p] Y and Y [figure: q] Z is

(p ⊙ q)(z, x) = ∐_{y∈Y} p(y, x) ⊗ q(z, y).

5.4. Example. Since 𝕊pan(C) is a pseudo double category, all composites and units always exist. Composites are given by pullback, and the unit of X is the unit span X ← X → X.

Regarding units in V-ℙrof and ℙrof(C), we have the following.

5.5. Proposition. For any virtual double category 𝕏, all units exist in 𝕄od(𝕏). For any monoid A, its unit cell

[figure: A_{0}; A_{0}; A; A_{0}; A_{0}; A_{0}; A_{0}; A_{0}; A_{0}; |; ⇓â]

is opcartesian in 𝕄od(𝕏). Therefore, U_{A} is A itself, regarded as an A-A-bimodule.

Proof. Firstly, the unit axioms of A show that â is, in fact, a cell in 𝕄od(𝕏). Now we must show that composing with â gives a bijection between cells

[figure: D; E; P; B; D; g; B; C; C; E; f; B; A; p_{1}...p_{m}; A; C; q_{1}...q_{n}; ⇓α; and; D; E; p; B; D; g; B; C; C; E; f; B; A; p_{1}...p_{m}; A; A; A; A; C; q_{1}...q_{n}; ⇓β]

in 𝕄od(𝕏). Clearly composing any cell β of the second form with â gives a cell α of the first form. Conversely, given α of the first form, there are two cells of the second form defined by letting A act first on p_{m} from the right and q_{1} from the left, respectively. These are equal by one of the axioms for α to be a cell in 𝕄od(𝕏); we let β be their common value. (In the case when m = 0 or n = 0, we use the action of f or g instead.) The other axioms for α then carry over to β to show that it is a cell in 𝕄od(𝕏).

The unit axioms for the action of A on bimodules show that α ↦ β ↦ α is the identity, while the equivariance axioms for β regarding the two actions of A show that β ↦ α ↦ β is the identity. Thus we have a bijection, as desired.

Therefore, since V-ℙrof = 𝕄od(V-𝕄at) and ℙrof(C) = 𝕄od(𝕊pan(C)), they both always have all units. By contrast, extra assumptions on 𝕏 are required for composites to exist in 𝕄od(𝕏); here are the two examples of greatest interest to us.

5.6. Example. If V has small colimits preserved by ⊗ on both sides, then V-ℙrof has all composites; the composite of enriched profunctors A [figure: p] B and B [figure: q] C is given by the coend

(p ⊙ q)(z, x) = ∫ ^{y∈B} p(y, x) ⊗ q(z, y).

5.7. Example. If C has coequalizers preserved by pullback, then ℙrof(C) has all composites; the composite of internal profunctors is an “internal coend.”

Together with Proposition 5.5, these examples will suffice for the moment. In appendix A we will give general sufficient conditions for composites to exist in 𝕄od(𝕏), and for composites and units to exist in ℍ-Kl(𝕏, T).

5.8. Remark. If Definition 5.1 is satisfied only for m = k = 0, we say that the cell is weakly opcartesian. We do not regard a weakly opcartesian cell as exhibiting its target as a composite of its source, since the weak condition is insufficient to prove associativity and unitality. However, a weakly opcartesian cell does suffice to detect its target as the composite of its source, if we already know that that composite exists. Furthermore, if any composable string in 𝕏 is the source of a weakly opcartesian cell and moreover weakly opcartesian cells are closed under composition, then one can show, as in [Her00], that in fact every weakly opcartesian cell is cartesian; see also §9.

Virtual double categories having only weakly opcartesian cells seem to be fairly rare; one example is V-𝕄at where V has colimits which are not preserved by its tensor product. Note that in this case, V-ℙrof need not even have weakly opcartesian cells, since we require ⊗ to preserve coequalizers simply to make the composite of two profunctors into a profunctor.

If 𝕏 and 𝕐 have units, we say that a functor (or monad) 𝕏 [figure: F] 𝕐 is normal if it preserves opcartesian cells with nullary source, which is to say it preserves units in a coherent way. Likewise, if 𝕏 and 𝕐 have all units and composites (i.e. are pseudo double categories), we say that 𝕏 [figure: F] 𝕐 is strong if it preserves all opcartesian cells.

5.9. Example. Any functor 𝕊pan(C) [figure] 𝕊pan(D) induced by a pullback-preserving functor C [figure] D is strong, and in particular normal.

5.10. Example. It is also easy to see that 𝕄od(F) is normal for any functor F, by the construction of units in Proposition 5.5.

5.11. Examples. If V is a cocomplete symmetric monoidal category in which ⊗ preserves colimits on both sides, then V-𝕄at has all composites, and the extension of the “free monoid” monad to V-𝕄at from Example 3.12 is easily seen to be strong. Since the “free strict monoidal V-category” monad on V-ℙrof is obtained by applying 𝕄od to this, it is normal by our above observation. In fact, it is also strong, essentially because the tensor product of reflexive coequalizers is again a reflexive coequalizer (see, for example, [Joh02, A1.2.12]).

5.12. Examples. The “free symmetric strict monoidal V-category” monad on V-ℙrof from Example 3.14 is also normal, essentially by definition, as are the “free V-category with strictly associative finite products” monad from Example 3.15 and its relatives from Example 3.16. A more involved computation with coequalizers shows that the first is actually strong, and the second is strong whenever V is cartesian monoidal. However, it seems that the others are not in general strong.

5.13. Examples. The monads on V-𝕄at constructed in Example 3.7 are not generally strong or even normal. Two notable exceptions are the ultrafilter monads on ℝel and \overline{R_{+}}-𝕄at, of which the first is strong and the second is normal.

We write vDbl_{n} for the locally full sub-2-category of vDbl determined by the virtual double categories with units and normal functors between them; thus 𝕄od is a 2-functor vDbl [figure] vDbl_{n}. In fact, we have the following.

5.14. Proposition. 𝕄od is right pseudo-adjoint to the forgetful 2-functor vDbl_{n} [figure] vDbl.

Proof. “Pseudo-adjoint” means that we have a pseudonatural η and ϵ that satisfy the triangle identities up to coherent isomorphism. We take ϵ_{𝕏} to be the forgetful functor 𝕄od(𝕏) [figure] 𝕏 which sends a monoid to its underlying object and a module to its underlying horizontal arrow; this is strictly 2-natural. If 𝕏 has units, we take η_{𝕏} to be the “unit assigning” functor 𝕏 [figure] 𝕄od(𝕏) which sends X to U_{X} (which has a unique monoid structure) and X [figure: p] Y to itself considered as a (U_{X}, U_{Y})-bimodule; this is only pseudonatural since normal functors preserve units only up to isomorphism. But if we choose the units in 𝕄od(𝕏) according to Proposition 5.5, then the triangle identities are satisfied on the nose.

In particular, if 1 denotes the terminal virtual double category, then the category of normal functors 1 [figure] 𝕏 is equivalent to the vertical category of 𝕏. It then follows from Proposition 5.14 that the category of arbitrary functors 1 [figure] 𝕏 is equivalent to the vertical category of 𝕄od(𝕏). Thus, Proposition 5.14 generalizes the well-known observation (which dates back to [Bén67]) that monoids in a bicategory B are equivalent to lax functors 1 [figure] B.

5.15. Remark. It follows that 𝕄od is a pseudomonad on the 2-category vDbl_{n}, and so in particular it has a multiplication

𝕄od(𝕄od(𝕏)) [figure] 𝕄od(𝕏).  (5.16)

Inspection reveals that an object of 𝕄od(𝕄od(𝕏)) consists of an object X of 𝕏, two monoids X [figure: A] X and X [figure: M] X, and a monoid homomorphism A [figure] M whose vertical arrow components are identities. The multiplication (5.16) simply forgets the monoid A. This idea will be further discussed in [CS10b].

5.17. Remark. If 𝕏 is a virtual double category in which all units and composites exist (equivalently, it is a pseudo double category), then it has a horizontal bicategory H(𝕏) consisting of its objects, horizontal arrows, and cells of the form

[figure: ⇓; .]

Clearly when C and V satisfy the required conditions for all composites to exist in our examples, we recover in this way the usual bicategories of matrices, spans, and enriched and internal profunctors. Any functor between pseudo double categories likewise induces a lax functor of horizontal bicategories, but this is not true of transformations without additional assumptions; see Remarks 7.26 and A.5.

6. 2-categories of T -monoids

As proposed in the previous section, we now use the notion of units introduced there to define 2-categories of generalized multicategories, generalizing the approach taken in [Lei04, §5.3].

6.1. Proposition. Let 𝕏 be a virtual double category in which all units exist. Then it has a vertical 2-category V𝕏 whose objects are those of 𝕏, whose morphisms are the

vertical arrows of 𝕏, and whose 2-cells [figure: A; f; g; α; B] are the cells

[figure: A; U_{A}; g; ⇓α; A; f; B; U_{B}; B]

in 𝕏.

Proof. This is straightforward; note that when composing 2-cells we must use the isomorphisms U_{A} ≅ U_{A} ⊙ U_{A}.

In particular, for any 𝕏, 𝕄od(𝕏) has a vertical 2-category, which we denote Mon(𝕏) and call the 2-category of monoids in 𝕏. (This 2-category is closely related to various 2-categories of monads in a bicategory; see [LS02, §2.3–2.4].) It turns out that in this case, the description of the 2-cells of Mon(𝕏) can be rephrased in a way that looks much more like a natural transformation.

6.2. Proposition. Giving a 2-cell [figure: A; f; g; α; B] in Mon(𝕏) is equivalent to giving a cell

[figure: B_{0}; B_{0}; B; A_{0}; B_{0}; g_{0}; A_{0}; B_{0}; f_{0}; B_{0}; B_{0}; |; ⇓α_{0}]

in 𝕏 such that

[figure: B_{0}; B_{0}; B; A_{0}; B_{0}; f_{0}; A_{0}; A_{0}; A; A_{0}; B_{0}; f_{0}; ⇓f; A_{0}; B_{0}; g_{0}; α_{0} ⇓; B_{0}; B_{0}; B; ⇓b̄; B_{0}; B_{0}; B; B_{0}; B_{0}; B_{0}; B_{0}; B_{0}; B_{0}] = [figure: B_{0}; B_{0}; B; A_{0}; B_{0}; g_{0}; A_{0}; A_{0}; A; A_{0}; B_{0}; g_{0}; g ⇓; A_{0}; B_{0}; f_{0}; ⇓α_{0}; B_{0}; B_{0}; B; ⇓b̄; B_{0}; B_{0}.; B; B_{0}; B_{0}; B_{0}; B_{0}; B_{0}; B_{0}.]  (6.3)

Proof. This is an instance of Proposition 5.5, where m = n = 0, f = g = 1_{A}, and P = U_{A}.

6.4. Example. Recall that in V-ℙrof = 𝕄od(V-𝕄at), the objects are V-enriched categories and the vertical morphisms are V-enriched functors; thus these are the objects and morphisms of Mon(V-𝕄at). Recalling from Example 2.6 the definition of cells in

V-𝕄at, Proposition 6.2 implies that a 2-cell [figure: A; f; g; α; B] in Mon(V-𝕄at) is given by a

family of morphisms I [figure: α_{x}] B(fx, gx) for x an object of A, such that for every x, y the following square commutes:

[figure: B(gx, gy) ⊗ B(fx, gx); B(fx, gy).; A(x, y); B(gx, gy) ⊗ B(fx, gx); g⊗α_{x}; A(x, y); B(fy, gy) ⊗ B(fx, fy); α_{y}⊗f; B(fy, gy) ⊗ B(fx, fy); B(fx, gy).]

This is precisely the usual definition of a V-enriched natural transformation; thus we have Mon(V-𝕄at) ≃ V-Cat.

6.5. Example. Likewise, Mon(𝕊pan(C)) ≃ Cat(C) is the 2-category of internal categories, functors, and natural transformations in C.

6.6. Examples. On the other hand, the vertical 2-category of 𝕊pan(S) is just S, regarded as a 2-category with only identity 2-cells. The vertical 2-category of V-𝕄at depends on what V is, but usually it is not very interesting. Thus, in general, vertical 2-categories are only interesting for virtual double categories whose objects are “categorylike” rather than “set-like.”

Now, if T is a monad on a virtual double category 𝕏, we write KMon(𝕏, T) for the 2-category V(𝕂Mod(𝕏, T)) and call it the 2-category of T -monoids in 𝕏. Its objects are T -monoids, its morphisms are T -monoid homomorphisms, and its 2-cells may be called T - monoid transformations. By Proposition 6.2 and the definition of ℍ-Kl(𝕏, T), a T -monoid transformation α: f [figure] g: A [figure] B is specified by a cell

[figure: B_{0}; T B_{0}; B; A_{0}; B_{0}; g_{0}; A_{0}; T B_{0}; T f_{0}∘η_{A_{0}}=η_{T B_{0}}∘f_{0}; B_{0}; T B_{0}; |; ⇓α_{0}]

such that

[figure: T A_{0}; T^{2}A_{0}; B; A_{0}; T A_{0}; η; A_{0}; T A_{0}; A; T A_{0}; T^{2}A_{0}; η; ⇓η_{A}; T B_{0}; T^{2}B_{0}; T B; T A_{0}; T B_{0}; T f_{0}; T A_{0}; T^{2}A_{0}; T^{2}A_{0}; T^{2}B_{0}; T^{2}f_{0}; ⇓T f; A_{0}; B_{0}; g_{0}; α_{0} ⇓; B_{0}; T B_{0}; B; ⇓b̄; B_{0}; T B_{0}; B; B_{0}; B_{0}; B_{0}; T^{2}B_{0}; T^{2}B_{0}; T B_{0}; μ_{B}] = [figure: B_{0}; T B_{0}; B; A_{0}; B_{0}; g_{0}; A_{0}; T A_{0}; A; T A_{0}; T B_{0}; T g_{0}; g ⇓; T A_{0}; T^{2}B_{0}; T (η_{B_{0}})∘T f_{0}; ⇓T α_{0}; T B_{0}; T^{2}B_{0}; T B; ⇓b̄; B_{0}; T B_{0}.; B; B_{0}; B_{0}; B_{0}; T^{2}B_{0}; T^{2}B_{0}; T B_{0}.; μ_{B}]

Many authors have defined this 2-category KMon(𝕏, T) in seemingly ad-hoc ways, whereas it falls quite naturally out of the framework of virtual double categories. This was also observed in [Lei04, §5.3]; see §B.1.

6.7. Example. Let T be the “free monoid” monad on Set-𝕄at, so that T -monoids

are ordinary multicategories. If A [figure: f; g] B are functors, then according to the above, a

transformation f [figure: α] g consists of, for each x ∈ A, a morphism α_{x} ∈ B(η(fx), gx) (that is to say, a morphism (fx) [figure: α_{x}] gx with source of length one) such that for any morphism ξ: (x_{1}, …, x_{n}) [figure] y in A, we have

α_{y} ∘ f(ξ) = g(ξ) ∘ (α_{x_{1}}, …, α_{x_{n}}).

This is the usual notion of transformation for functors between multicategories.

6.8. Example. When T is the “free category” monad on directed graphs, so that T - monoids are virtual double categories, T -monoid transformations are the same as the transformations we defined in 3.1.

6.9. Example. Let U be the ultrafilter monad on ℝel, so that U-monoids are topological

spaces. If A [figure: f; g] B are continuous maps (i.e. U-monoid homomorphisms), then there

exists a transformation f [figure] g (which is necessarily unique) just when for all x ∈ A, the principal ultrafilter η_{fx} converges to gx in B. This is equivalent to saying that f ≥ g in the pointwise ordering induced by the usual specialization order on B. The situation for other topological examples is similar.

Any normal functor clearly induces a strict 2-functor between vertical 2-categories. In fact, if 2-Cat denotes the 2-category of 2-categories, strict 2-functors, and strict 2-natural transformations, then we have:

6.10. Proposition. There is a strict 2-functor V: vDbl_{n} [figure] 2-Cat.

In particular, any normal monad T on 𝕏 induces a strict 2-monad on V(𝕏). As we saw in §3, most monads on virtual double categories are “extensions” of a known monad on their vertical categories (or vertical 2-categories), so this construction usually just recovers the familiar monad we started with. In §9, we will show that V(T)-algebras are closely related to T -monoids.

7. Virtual equipments

If we have succeeded in convincing the reader that virtual double categories are inevitable, she may be justified in wondering why they have not been more studied. Certainly, virtual double categories involve significant complexity above and beyond pseudo double categories, and the latter suffice to describe the important examples 𝕊pan(C), V-𝕄at, V-ℙrof, and ℙrof(C) as long as V and C are suitably cocomplete. However, even pseudo double categories have generally received less publicity than bicategories.

One possible reason for this is that in most of the (pseudo or virtual) double categories arising in practice, the vertical arrows are more tightly coupled to the horizontal arrows that we have heretofore accounted for; in fact they can almost be identified with certain

horizontal arrows. For example, a V-functor A [figure: f] B is determined, up to isomorphism,

by the V-profunctor A [figure: B(1,f)] B defined by B(1, f)(b, a) = B(b, fa). Furthermore, this coupling is very important for many applications, such as the formal definition of weighted limits and colimits (see [Str83, Woo82]), so a mere double category (pseudo or virtual) would be insufficient for these purposes. Because of this, many authors have been content to work with bicategories, or bicategories with a collection of horizontal arrows singled out (such as the “proarrow equipments” of [Woo82]).

However, while not all pseudo double categories exhibit this type of coupling, it is possible to characterize those that do (and they turn out to be equivalent to the “proarrow equipments” mentioned above). The basic idea of this dates back to [BS76], but it has recently been revived in various equivalent forms; see for instance [Ver92, GP99, GP04, DPP10, Shu08] and the Notes at the end of [Lei04, Ch. 5]. Since this type of coupling also plays an important role in the theory of generalized multicategories, in this section we give the basic definitions appropriate to the virtual case.

The basic idea is the following. The profunctor B(1, f) considered above can be constructed in two stages: first we consider the hom-profunctor B(−, −): B [figure] B, and then we precompose it with f on one side. We already know from §5 that hom-profunctors are the units in V-ℙrof, so it remains only to characterize precomposition with functors in terms of V-ℙrof. This is accomplished by the following definition.

7.1. Definition. A cell

[figure: p; f; _{⇓_{cart}}; g; q]  (7.2)

in a virtual double category is cartesian if any cell

[figure: r_{1}; fh; ⇓; r_{2}; …; r_{n}; gk; q]

factors through it uniquely as follows:

[figure: r_{1}; h; ⇓; r_{2}; …; r_{n}; k; p; f; _{⇓_{cart}}; g; q; .]

If there exists a cartesian cell (7.2), we say that the p is the restriction q(g, f). The notation is intended to suggest precomposition of a profunctor q(−, −) with f and g. When f or g is an identity, we write q(g, 1) or q(1, f), respectively. It is evident from the universal property that restrictions are unique up to isomorphism, and pseudofunctorial; that is, we have q(1, 1) ≅ q and q(1, g)(1, f) ≅ q(1, gf) coherently.

We say that 𝕏 has restrictions if q(g, f) exists for all q, f, and g, and that a functor preserves restrictions if it takes cartesian cells to cartesian cells. We write vDbl_{r} for the sub-2-category of vDbl determined by the virtual double categories with restrictions and the restriction-preserving functors.

7.3. Examples. The virtual double categories V-𝕄at, V-ℙrof, 𝕊pan(C), and ℙrof(C) have all restrictions. Restrictions in V-𝕄at are given by reindexing matrices, restrictions in 𝕊pan(C) are given by pullback, and restrictions in V-ℙrof and ℙrof(C) are given by precomposing with functors.

Note that the restrictions in V-ℙrof and ℙrof(C) are induced by those in V-𝕄at and 𝕊pan(C), in the following general way.

7.4. Proposition. If 𝕏 is a virtual double category with restrictions, then 𝕄od(𝕏) also has restrictions.

Proof. If B [figure: p] D is a bimodule in 𝕏 and

[figure: A_{0}; A; f_{0}; ⇓f; A_{0}; f_{0}; B_{0}; B; B_{0}; and; C_{0}; C; g_{0}; ⇓g; C_{0}; g_{0}; D_{0}; D; D_{0}]

are monoid homomorphisms, then the restriction p(g_{0}, f_{0}) in 𝕏 becomes an (A, C)-bimodule in an obvious way, making it into the restriction p(g, f) in 𝕄od(𝕏).

The other ingredient in the construction of generalized multicategories also preserves restrictions.

7.5. Proposition. If 𝕏 is a virtual double category with restrictions and T is a monad on 𝕏, then ℍ-Kl(𝕏, T) also has restrictions.

Proof. Let A [figure: p] T B be a horizontal arrow in 𝕏, regarded as a horizontal arrow A [figure] B

in ℍ-Kl(𝕏, T). It is easy to verify that the restriction of p along C [figure: f] A and D [figure: g] B in ℍ-Kl(𝕏, T) is given by the restriction p(T g, f) in 𝕏.

Therefore, if 𝕏 has restrictions, so does 𝕂Mod(𝕏, T) for any monad T on 𝕏. Moreover, by Proposition 5.5, 𝕂Mod(𝕏, T) always also has units. As suggested in the introduction to this section, units and restrictions together are an especially important combination, so we give a special name to this situation.

7.6. Definition. A virtual equipment is a virtual double category in which all units and all restrictions exist.

We write vEquip for the locally full sub-2-category of vDbl determined by the virtual equipments and the normal restriction-preserving functors between them (however, see Theorem 7.24). We can now observe that 𝕄od is a 2-functor from vDbl_{r} to vEquip.

7.7. Examples. 𝕊pan(C), V-ℙrof, and ℙrof(C) are always virtual equipments, and V-𝕄at is a virtual equipment whenever V has an initial object preserved by ⊗. More generally, 𝕄od(𝕏) and 𝕂Mod(𝕏, T) are virtual equipments whenever 𝕏 has restrictions.

If A [figure: f] B is a vertical arrow in a virtual equipment, we define its base change objects to be

B(1, f) = U_{B}(1, f) and B(f, 1) = U_{B}(f, 1).

These come with cartesian cells

[figure: B(1,f); f; U_{B}] and [figure: B(f,1); f; U_{B}] .  (7.8)

By factoring U_{f} through these cartesian cells, we obtain two further cells

[figure: U_{A}; f; B(f,1); and; U_{A}; f; B(1,f)]  (7.9)

such that the following equations hold:

[figure: U_{A}; f; B(1,f); f; U_{B}] = [figure: U_{A}; f; ⇓U_{f}; f; U_{B}]  [figure: U_{A}; f; B(f,1); f; U_{B}] = [figure: U_{A}; f; ⇓U_{f}; f; U_{B}]  (7.10)

Moreover, the following equations also hold:

[figure: U_{A}; B(1,f); f; B(1,f); U_{B}; B(1,f); _{⇓_{opcart}}] = [figure: U_{A}; _{⇓_{opcart}}; B(1,f); B(1,f)]  (7.11)

[figure: B(f,1); U_{A}; f; U_{B}; B(f,1); B(f,1); _{⇓_{opcart}}] = [figure: B(f,1); _{⇓_{opcart}}; U_{A}; B(f,1)]  (7.12)

We can verify these by postcomposing each side with the appropriate cartesian cell, using the equations (7.10), and invoking the uniqueness of factorizations through cartesian cells. In the terminology of [DPP10], equations (7.10)–(7.12) are said to make B(1, f) and B(f, 1) into a companion and a conjoint of f, respectively.

7.13. Example. In 𝕊pan(C), the base change objects B(1, f) and B(f, 1) are the spans

[figure: A; A; 1_{A}; A; B; f; and; A; B; f; A; A; 1_{A}]

respectively. These are often called the graph of f.

7.14. Example. In V-𝕄at, for a function f: X [figure] Y the base change object Y (1, f) is the matrix

Y (1, f)(x, y) = \begin{cases}I & if f(x) = y \\ ∅ & otherwise. \end{cases}

7.15. Example. In V-ℙrof, the base change objects B(1, f) and B(f, 1) are the representable distributors defined by B(1, f)(b, a) = B(b, fa) and B(f, 1)(a, b) = B(fa, b). Base change objects in ℙrof(C) are analogous.

At first glance, base change objects may seem only to be a particular special case of restrictions. However, it turns out that all restrictions can be recovered by composition with the base change objects (hence the name).

7.16. Theorem. Let B [figure: p] D be a horizontal arrow and f: A [figure] B and g: C [figure] D be vertical arrows in a virtual equipment. Then B(1, f)⊙p⊙D(g, 1) exists and is isomorphic to p(g, f).

Proof. Consider the composite

[figure: B(1,f); f; p; 1_{p}; D_{g}; g; U_{B}; p; U_{D}; _{⇓_{opcart}}; p]  (7.17)

By the universal property of restriction, this factors through the cartesian cell defining p(g, f) to give a canonical cell

[figure: B(1,f); p; D(g,1); p(g,f); .]  (7.18)

We claim that this cell is opcartesian. To show this, suppose given a cell

[figure: h; B(1,f); p; D(g,1); k; q; .]

We need to factor it uniquely through (7.18). A factorization is given by the composite

[figure: p(g,f); U_{A}; f; p(g,f); g; U_{C}; h; B(1,f); p; D(g,1); k; q; .]

To verify that this is a factorization, and that it is unique, we use the equations (7.10)– (7.12). The details are similar to the proof of [Shu08, Theorem 4.1].

7.19. Corollary. For vertical arrows f: A [figure]B and g: B [figure]C, the composite B(1, f) ⊙ C(1, g) always exists and is isomorphic to C(1, gf), and dually.

We also have the following dual result.

7.20. Theorem. For arrows f: A [figure] B and g: C [figure] D in a virtual equipment, we have a bijection between cells of the form

[figure: A; p; f; C; g; B; q; D; and; B; B(f,1); A; p; C; D(1,g); D; B; q; D]

Proof. The inverse bijections are given by composing with the cells (7.8) and (7.9). (Recall that all composites with units exist in any virtual double category.) The fact that they are inverses follows from (7.10)–(7.12).

It follows that in the situation of Theorem 7.20, if the composite B(f, 1) ⊙ p ⊙ D(1, g) exists, then it is a “corestriction” or “extension” of p along f and g—that is, it satisfies a universal property dual to that of a restriction.

Combining Theorems 7.16 and 7.20, we obtain the following.

7.21. Corollary. In a virtual equipment, there is a bijection between cells of the form

[figure: p; h; B(1,f); k; D(1,g); q; and; p; h; f; g; k; q]

Taking p and q to be units and h and k to be identities, we obtain:

7.22. Corollary. For vertical arrows f, g: A [figure] B in a virtual equipment 𝕏, there is a bijection between cells f [figure] g in V𝕏 and cells

[figure: B(1,f); ⇓; B(1,g); ,]

which respects composition. Similarly, we have a bijection between cells f [figure] g and cells B(g, 1) [figure] B(f, 1).

Now suppose that 𝕏 is a virtual equipment which moreover has all composites. Then it has a horizontal bicategory H𝕏, and Corollaries 7.19 and 7.22 imply that f ↦ B(1, f) defines a pseudofunctor V𝕏 [figure] H𝕏 which is locally full and faithful. Furthermore, it is easy to verify that B(f, 1) is right adjoint to B(1, f) in H𝕏.

This structure—a pseudofunctor which is bijective on objects, locally full and faithful, and which takes each 1-cell to one having a right adjoint—was defined in [Woo82] to constitute an equipment. This is the structure we referred to in the introduction to this section, which many authors have used where we would find double categories more natural. In fact, it is not hard to show (see [Shu08, Appendix C]) that an equipment in the sense of [Woo82] is equivalent to a virtual equipment which has all composites (this was called a framed bicategory in [Shu08]). Therefore, from now on we use equipment to mean a virtual equipment having all composites (thereby justifying the terminology “virtual equipment”).

7.23. Remark. It was shown in [Shu08] that an equipment can equally well be defined as a pseudo double category in which all restrictions exist, or in which all “extensions” exist (in the sense mentioned after Theorem 7.20), or in which there exist base change objects with cells (7.8) and (7.9) satisfying (7.10)–(7.12). In the virtual case, we have a Goldilocks trifurcation: merely having base change objects is too weak, and having all extensions is too strong, but having restrictions (together with units) is just right.

We now consider how functors and transformations interact with restrictions.

7.24. Theorem. Any functor F between virtual equipments preserves restriction.

Proof. The proof given for equipments in [Shu08, Theorem 6.4] applies basically verbatim to virtual equipments.

In particular, vEquip is in fact a full sub-2-category of vDbl_{n}. Note, though, that an arbitrary functor F between virtual equipments still may not preserve units, so that while we have F (B(1, f)) ≅ F U_{B}(1, F f), neither need be the same as F B(1, F f). Of course, they are the same if F is normal.

Now, recall that any transformation [figure: 𝕏; F; G; α; 𝕐] of functors between virtual equip-

ments induces a strictly 2-natural transformation V(α) of 2-functors between vertical 2categories. In particular, we have α_{B} ∘F (f) = G(f)∘α_{A} for any vertical arrow f: A [figure] B in 𝕏. However, we also have the cell component

[figure: F (B(1,f)); α_{A}; ⇓α_{B(1,f)}; α_{B}; G(B(1,f))]

of α. If F and G are normal, so that F (B(1, f)) ≅ F B(1, F f) and G(B(1, f)) ≅ GB(1, Gf), then by Corollary 7.21, α_{B(1,f)} induces a 2-cell α_{B} ∘ F (f) [figure] G(f) ∘ α_{A}, which seems to be trying to make V(α) into an oplax natural transformation. Fortunately, however, this is an illusion.

7.25. Proposition. In the above situation, the 2-cell α_{B} ∘ F (f) [figure] G(f) ∘ α_{A} induced by α_{B(1,f)} is an identity.

Proof. This follows by inspection of how this 2-cell is constructed, and use of the cell naturality of α.

7.26. Remark. Recall from Remark 5.17 that any functor 𝕏 [figure: F] 𝕐 between pseudo

double categories induces a lax functor H(𝕏) [figure: H(F)] H(𝕐) between horizontal bicategories, but not every transformation F [figure] G induces a transformation H(F) [figure] H(G). It is true, however, that if 𝕏 and 𝕐 are equipments, then any transformation F [figure: α] G

induces an oplax transformation H(F) [figure: H(α)] H(G) whose component at X is GX(1, α_{X}). Likewise, the components (GX)(α_{X}, 1) form a lax transformation H(G) [figure] H(F). See also Remark A.5.

8. Normalization

With the notion of virtual equipment under our belt, we now return to the general theory of generalized multicategories. We observed in §4 that for virtual double categories whose objects are “category-like,” such as V-ℙrof and ℙrof(C) (as opposed to those such as V-𝕄at and 𝕊pan(C), whose objects are “set-like”), general T -monoids often contain too much structure. For instance, if T is the “free strict monoidal category” monad on Set-ℙrof, then a T -monoid consists of a category A, a multicategory M and a bijectiveon-objects functor from A to the underlying category of M. Usually, the morphisms of A constitute superfluous data which we would like to eliminate. (This is not always true, though: in [Che04] these extra morphisms played an important role.)

The obvious way to eliminate this extra data, which we adopted in describing examples of this sort in §4, is to require A to be a discrete category; this way the extra morphisms simply do not exist. However, a different way to eliminate it is to require the given functor A [figure] M to induce an isomorphism between A and the underlying category of M; this way the extra morphisms exist, but are determined uniquely by the rest of the structure. In this section we define general analogues of both approaches, show their equivalence under general hypotheses, and argue that when they are not equivalent it is usually the second approach that is more useful. (This second approach was also the one taken in [Her01].)

8.1. Definition. Let 𝕏 be a virtual equipment and let T be a monad on 𝕄od(𝕏). A T -monoid A [figure: M] T A is called object-discrete if A is a monoid in 𝕏 of the form U_{X}.

We write d𝕂Mod(𝕄od(𝕏), T) for the full sub-virtual-equipment of 𝕂Mod(𝕄od(𝕏), T) determined by the object-discrete T -monoids, and dKMon(𝕏, T) for its vertical 2-category. Note that object-discreteness is only defined for a monad on a virtual equipment of the form 𝕄od(𝕏).

8.2. Definition. Let T be a monad on a virtual equipment 𝕏. A T -monoid A [figure: M] T A is normalized if its unit cell

[figure: A; U_{A}; A; η; A; M; T A]

is cartesian in 𝕏.

We write n𝕂Mod(𝕏, T) for the full sub-virtual-equipment of 𝕂Mod(𝕏, T) determined by the normalized T -monoids, and nKMon(𝕏, T) for its vertical 2-category. Unlike objectdiscreteness, normalization is defined for monads on any virtual equipment.

Now, to prove an equivalence between normalization and object-discreteness, we need to introduce the following definitions.

8.3. Definition. A monoid homomorphism

[figure: B_{0}; B_{0}; B; A_{0}; B_{0}; f_{0}; A_{0}; A_{0}; A; A_{0}; B_{0}; f_{0}; f]

in a virtual double category 𝕏 is called bijective on objects (or b.o.) if f_{0} is an isomorphism. It is called fully faithful (or f.f.) if the cell f is cartesian.

8.4. Lemma. If A_{0} [figure: A] A_{0} is a monoid in a virtual double category 𝕏 with restrictions

and X [figure: f] A_{0} is any vertical arrow, then X [figure: A(f,f)] X is also a monoid, and its defining cartesian cell is a monoid homomorphism with f as its vertical part.

Proof. To obtain a multiplication for A(f, f), we compose two copies of the defining cartesian cell with the multiplication of A, then factor the result through the defining cartesian cell. The unit is similar.

8.5. Lemma. If 𝕏 has restrictions, then (b.o., f.f.) is a factorization system on the category Mon(𝕏) of monoids and monoid homomorphisms in 𝕏.

Proof. Orthogonality is supplied by the universal property of cartesian cells, together with the fact that isomorphisms are orthogonal to anything. Factorizations are given by restriction along the vertical arrow component of a monoid homomorphism, using the previous lemma.

8.6. Theorem. Let 𝕏 be a virtual equipment, and let T be a monad on 𝕄od(𝕏) which preserves b.o. morphisms. Then

(i) d𝕂Mod(𝕄od(𝕏), T) is coreflective in 𝕂Mod(𝕄od(𝕏), T) (that is, its inclusion has a right adjoint in vEquip),

(ii) n𝕂Mod(𝕄od(𝕏), T) is reflective in 𝕂Mod(𝕄od(𝕏), T), and

(iii) the induced adjunction

d𝕂Mod(𝕄od(𝕏), T) [figure] n𝕂Mod(𝕄od(𝕏), T)

is an adjoint equivalence.

Proof. We first prove (i). Let A [figure: M] T A be a T -monoid in 𝕄od(𝕏), where A_{0} [figure: A] A_{0} is a monoid in 𝕏. The unit of A is a monoid homomorphism e: U_{A_{0}} [figure] A, so by Lemma 8.4, M(T e, e): U_{A_{0}} [figure] T (U_{A_{0}}) is an (object-discrete) T -monoid. Likewise, if B [figure: N] T B is another T -monoid and M [figure: p] T N is a horizontal arrow in 𝕂Mod(𝕄od(𝕏), T), then p(T e_{B}, e_{A}) is a horizontal arrow from M(T e_{A}, e_{A}) to N(T e_{B}, e_{B}). It is straightforward to extend these constructions to a functor 𝕂Mod(𝕄od(𝕏), T) [figure] d𝕂Mod(𝕄od(𝕏), T).

Note that M(T e, e) comes with a natural map to M, whose vertical arrow component is e, and likewise for p(T e_{B}, e_{A}). This supplies the counit of the desired coreflection. We obtain the unit by observing that if M were already object-discrete, then e would be the identity, so we would have M(T e, e) ≅ M. The triangle identities are easy to check.

Note that the horizontal arrow in 𝕏 underlying M(T e, e) is the restriction of A_{0} [figure: M] (T A)_{0} along the identity e_{0} : A_{0} = A_{0} and the map (T e)_{0} : T (U_{A_{0}})_{0} [figure] (T A)_{0}. Since e is b.o. and T preserves b.o. morphisms, (T e)_{0} is an isomorphism; thus the coreflection of M leaves its underlying horizontal arrow in 𝕏 essentially unmodified.

We now prove (ii); let A and M be as before. We first observe that the T -monoid M in 𝕄od(𝕏) has an underlying monoid in 𝕄od(𝕏), namely M(η, 1). (This is a special case of a general functoriality result we will prove in [CS10a].) As noted in Remark 5.15, a monoid in 𝕄od(𝕏) consists of two monoids in 𝕏 and a monoid homomorphism between them whose vertical arrow components are identities. In this case the first monoid is of course A. We denote the second by A′ and the monoid homomorphism by c: A [figure] A′. Note that the underlying horizontal arrow of A′ in 𝕏 is just M(η, 1).

Now since T preserves b.o. morphisms, T A [figure: T c] T A′ is b.o., hence (T A)_{0} [figure: (T c)_{0}] (T A′)_{0} is an isomorphism. By restricting along its inverse and using the identity (A′)_{0} = A_{0}, from A_{0} [figure: M] (T A)_{0} we obtain a horizontal arrow (A′)_{0} [figure] (T A′)_{0}. We abuse notation by continuing to denote this M (since restriction along isomorphisms leaves an arrow essentially unchanged). Now A′ is a restriction of M, so it acts on M from the left via the multiplication of M. And since T preserves restrictions, T A′ is a restriction of T M, so it also acts on M from the right via the multiplication of M. Thus, the horizontal arrow in 𝕏 underlying M also admits the structure of a horizontal arrow A′ [figure] T A′ in 𝕄od(𝕏), which we denote M′. Likewise, the multiplication and unit of the T -monoid M induce a multiplication and unit on M′, making it also into a T -monoid, and we have a canonical T -monoid homomorphism M [figure] M′ which is an isomorphism in 𝕏. By definition of A′, M′ is normalized. There is an analogous construction on horizontal arrows, and together they extend straightforwardly to a functor 𝕂Mod(𝕄od(𝕏), T) [figure] n𝕂Mod(𝕄od(𝕏), T).

Now recall that A′ came equipped with a b.o. monoid homomorphism A [figure] A′. It is straightforward to check that this homomorphism underlies a T -monoid homomorphism M [figure] M′; in this way we obtain the unit of the desired reflection. We obtain its counit by observing that if M is already normalized, then A ≅ A′ and hence M ≅ M′. The triangle identities are again easy to check.

Finally, to show (iii), we observe that the unit of the reflection and the counit of the coreflection are isomorphisms on the underlying horizontal arrow in 𝕏 (since they are restrictions along an isomorphism). Moreover, the reflection and coreflection functors both invert morphisms with this property. Statement (iii) then follows formally.

Recall that we began this section by observing that ordinary multicategories can be recovered as either object-discrete or normalized T -monoids, when T is the “free strict monoidal category” monad on Set-ℙrof. Since this T preserves b.o. morphisms, this statement is indeed an instance of Theorem 8.6. However, ordinary multicategories can also be obtained as arbitrary S-monoids, when S is the free monoid monad on Set-𝕄at = 𝕊pan(Set). Noting that in this case T = 𝕄od(S), we generalize this statement to the following.

8.7. Theorem. Let S be a monad on a virtual equipment 𝕏. Then the monad 𝕄od(S) on 𝕄od(𝕏) preserves b.o. morphisms, and we have a diagram

[figure: d𝕂Mod(𝕄od(𝕏), 𝕄od(S)); 𝕂Mod(𝕄od(𝕏), 𝕄od(S)); n𝕂Mod(𝕄od(𝕏), 𝕄od(S)); 𝕂Mod(𝕏, S)]

which serially commutes (up to isomorphism). Moreover, the two diagonal functors

d𝕂Mod(𝕄od(𝕏), 𝕄od(S)) [figure] 𝕂Mod(𝕏, S)  (8.8)
n𝕂Mod(𝕄od(𝕏), 𝕄od(S)) [figure] 𝕂Mod(𝕏, S)  (8.9)

are equivalences.

Proof. By definition, 𝕄od(S) takes a monoid A_{0} [figure: A] A_{0} to SA_{0} [figure: SA] SA_{0}, so it preserves b.o. morphisms since S preserves isomorphisms. We define the middle vertical arrow

𝕂Mod(𝕄od(𝕏), 𝕄od(S)) [figure] 𝕂Mod(𝕏, S)  (8.10)

by applying the 2-functor 𝕄od to the functor

ℍ-Kl(𝕄od(𝕏), 𝕄od(S)) [figure] ℍ-Kl(𝕏, S)

which takes a monoid A_{0} [figure: A] A_{0} to its underlying object A_{0}, and similarly for horizontal arrows. (This is again a special case of the general functorial result of [CS10a].) Thus, (8.10) takes a 𝕄od(S)-monoid A [figure: M] 𝕄od(S)(A) to the S-monoid A_{0} [figure: M] SA_{0}.

We define the diagonal functors by composition with this, so that the triangles [figure]

and [figure] commute by definition. The other triangles commute up to isomorphism because the reflection and coreflection were defined to fix A_{0}, replace A, and restrict M along an isomorphism, whereas (8.10) simply forgets about A.

Now, by the 2-out-of-3 property for equivalences, it suffices to show that (8.8) is an equivalence. We will construct an explicit inverse to it. By Proposition 5.14, to construct a normal functor

𝕂Mod(𝕏, S) [figure] 𝕂Mod(𝕄od(𝕏), 𝕄od(S))  (8.11)

it suffices to construct a not-necessarily-normal functor

𝕂Mod(𝕏, S) [figure] ℍ-Kl(𝕄od(𝕏), 𝕄od(S)).  (8.12)

We define (8.12) on objects by sending an S-monoid A_{0} [figure: A] SA_{0} to U_{A_{0}}, and likewise on vertical arrows. A horizontal arrow A [figure: p] B in 𝕂Mod(𝕏, S) has an underlying horizontal arrow A_{0} [figure: p] SB_{0} in 𝕏, which acquires a S(U_{B_{0}})-module structure from the following composite:

[figure: A_{0}; SB_{0}; p; A_{0}; A_{0}; A_{0}; S^{2}B_{0}; S^{2}B_{0}; SB_{0}; μ; SB_{0}; S^{2}B_{0}; SB; SB_{0}; SB_{0}; SB_{0}; SB_{0}; S(U_{B_{0}}); SB_{0}; S^{2}B_{0}; Sη; A_{0}; SB_{0}; p; A_{0}; A_{0}; A_{0}; SB_{0}; p; SB_{0}; SB_{0}; =; Sb̂; p̄_{r}]

This defines (8.12) on horizontal arrows; its action on cells is straightforward. The induced normal functor (8.11) takes an S-monoid A_{0} [figure: A] SA_{0} to itself, regarded as an (U_{A_{0}}, S(U_{A_{0}}))-bimodule. Clearly (8.11) followed by the forgetful functor is the identity, while the composite in the other direction is precisely the coreflection functor into d𝕂Mod(𝕄od(𝕏), 𝕄od(S)); this completes the proof.

8.13. Examples. As remarked above, when S is the “free monoid” monad on 𝕊pan(Set), this shows that ordinary multicategories (i.e. S-monoids) can also be identified with object-discrete or normalized 𝕄od(S)-monoids. Likewise, virtual double categories are S-monoids for the “free category” monad, and thus can also be identified with objectdiscrete or normalized 𝕄od(S)-monoids.

8.14. Example. Since topological spaces can be identified with U-monoids in ℝel, they can also be identified with object-discrete or normalized 𝕄od(U)-monoids in 2-ℙrof. In the terminology of [Tho09], a 𝕄od(U)-monoid is a modular topological space. It is normalized precisely when its order is the specialization order, so that it is equivalent to an ordinary topological space—i.e. a U-monoid, as required by Theorem 8.7.

By no means are all interesting monads on 𝕄od(𝕏) of the form 𝕄od(S). However, many of them do preserve b.o. morphisms, so that Theorem 8.6 at least applies.

8.15. Example. The “free symmetric strict monoidal category” monad on Set-ℙrof = 𝕄od(Set-𝕄at) preserves b.o. morphisms but is not of the form 𝕄od(S) for any monad S on Set-𝕄at. We have seen in Example 4.16 that object-discrete T -monoids are symmetric multicategories; hence so are normalized T -monoids.

8.16. Example. The “free category with strictly associative finite products” monad on Set-ℙrof also preserves b.o. morphisms but is not of the form 𝕄od(S). We have seen in Example 4.17 that object-discrete T -monoids are multi-sorted Lawvere theories; hence so are normalized T -monoids.

8.17. Non-Example. Recall from Example 4.19 that clubs are T -monoids in 𝕊pan(Cat) with a discrete category of objects, where T is a monad like the previous two. However, since 𝕊pan(Cat) is not of the form 𝕄od(𝕏), the theory of this section does not apply to clubs. In particular, their “object-discreteness” is not an instance of our definition, and is not the same as normalization.

When T does not preserve b.o. morphisms, however, normalized and discrete T - monoids can be quite different, even on a virtual equipment of the form 𝕄od(𝕏). Intuitively, saying that T preserves b.o. morphisms says that the possible domains of multimorphisms in a T -multicategory depend only on its objects. If this fails to be true, then how many morphisms are included in the underlying monoid can change what these possible domains are.

8.18. Example. Let T be the “free category with equalizers” monad on Set-ℙrof. Then T evidently does not preserve b.o. morphisms, but it is the identity on discrete categories. Therefore, an object-discrete T -monoid is just a category, whereas a normalized T -monoid can have morphisms whose domain is a “formal equalizer” of ordinary morphisms.

More interestingly, normalized T -monoids for the “free category with finite limits” monad (which also does not preserve b.o. morphisms) can be considered a generalization of Lawvere theories to finite-limit logics. We can also continue to generalize to more powerful logics (or “doctrines”).

These examples suggest that when T does not preserve b.o. morphisms, it is often the normalized, rather than the object-discrete, T -monoids that better capture the desired notion of T -multicategory. Note also that normalization makes sense for any monad on a virtual equipment, while object-discreteness only makes sense for monads on virtual equipments of the form 𝕄od(𝕏). Finally, we will see in the next section that normalized T - monoids are the most natural notion to compare with pseudo T -algebras. This inspires us to take normalized T -monoids as our preferred definition of “generalized multicategory,” and to make the following informal definition.

8.19. Definition. If T is a monad on a virtual equipment for which (possibly pseudo) T -algebras are called widgets, then normalized T -monoids are called virtual widgets.

The reasons for this definition were summarized in the introduction. In §9 we will prove that any widget has an underlying virtual widget, further justifying the terminology. Of course, we have seen that a number of types of virtual algebras already have their own names, such as “multicategory” and “Lawvere theory.” When such common names exist, we of course use them in preference to terms such as “virtual monoidal category” or “category with virtual finite products.”

Note that “virtual widget” is, strictly speaking, ambiguous: knowing the notion of widget determines at most the vertical 2-category V𝕏 and the 2-monad VT, rather than 𝕏 and T themselves. However, many 2-categories that arise in practice come with an obvious “natural” extension to a virtual equipment, so in practice there is little ambiguity. (In fact, there is a general construction of an equipment from a well-behaved 2-category; see [CJSV94].) One case of ambiguity is if “widget” is the name for T -algebras in Set or Cat, but we consider T -monoids in V-𝕄at or V-ℙrof; in this case we may speak of V-enriched virtual widgets.

8.20. Remark. The discussion above suggests that when the objects of 𝕏 are categorylike, it is the normalized T -monoids (i.e. virtual T -algebras) that are more important, while when the objects of 𝕏 are set-like, it is the non-normalized T -monoids (i.e. virtual 𝕄od(T)-algebras) that are more important. This does seem to usually be the case, but there are exceptions on both sides, such as the following.

• As we have already remarked, the multicategories of [BD98] and [Che04] are nonnormalized T -monoids, when T is the “free symmetric strict monoidal category” monad on Set-ℙrof (whose objects are obviously category-like).

• Let U be the ultrafilter monad on ℝel, whose objects are set-like. We have seen that a U-monoid is just a topological space, but it is easy to verify that a U-monoid is normalized just when it is a T_{1}-space—certainly also an important concept.

9. Representability

We now turn to a general version of the comparison between monoidal categories and multicategories. Of course, we first need to identify the analogue of a monoidal category in the general case. We saw in §8 that ordinary multicategories have two different faces in our setup: they are the S-monoids where S is the “free monoid” monad on 𝕊pan(Set), and also the normalized T -monoids, where T = 𝕄od(S) is the “free strict monoidal category” monad on Set-ℙrof. Monoidal categories, however, are more visible from the second point of view: they are the pseudo V(T)-algebras in V(Set-ℙrof) = Cat.

Accordingly, in this section we will assume that T is a monad on a virtual equipment 𝕏 whose objects are “category-like,” and seek to compare (pseudo) V(T)-algebras with (normalized) T -monoids. We will additionally have to assume that T is a normal monad as defined in §6, since otherwise it doesn’t even induce a 2-monad on V(𝕏). If we are given instead a monad S on a virtual double category whose objects are “set-like,” then in order to apply the theory of this section we simply consider 𝕄od(S) instead; some examples of this can be found later on. Generalizing the terminology of [Lei04, p. 165], we may call a (pseudo) V(𝕄od(S))-algebra an S-structured monoid.

Actually, the most natural approach to the comparison turns out to be via oplax T - algebras. Recall that for a 2-monad T on a 2-category, an oplax T -algebra is an object A with a map a: T A [figure] A and 2-cells

[figure: T^{2}A; μ; T a; \overline{a}; T A; a; T A; a; A; and; A; η; T A; a; â; A]  (9.1)

satisfying certain straightforward axioms. We call it normal if â is an isomorphism, and a pseudo T -algebra if both â and \overline{a} are isomorphisms. Finally, if T is a monad on a virtual equipment, we will always abuse terminology by saying “T -algebra” (with appropriate prefixes) to mean V(T)-algebra.

9.2. Theorem. Let T be a normal monad on a virtual equipment 𝕏. Then:

(i) Any oplax T -algebra T A [figure: a] A in V𝕏 gives rise to a T -monoid A [figure: A(a,1)] T A, which is normalized if and only if A is normal.

(ii) A T -monoid A [figure: M] T A arises from an oplax T -algebra if and only if M ≅ A(a, 1) for some vertical arrow T A [figure: a] A.

Proof. If a: T A [figure] A is an oplax T -algebra, then by definition of A(a, 1), the 2-cell â induces a unit cell

[figure: A; U_{A}; A; η; A; A(a,1); T A.]

Likewise, by the dual of Corollary 7.21, \overline{a} induces a multiplication

[figure: A; A(a,1); T A; (T A)(T a,1); T^{2}A; μ; A; A(a,1); T A]

and using the isomorphism (T A)(T a, 1) ≅ T (A(a, 1)) (since T is normal) we obtain a multiplication cell. The axioms to make A(a, 1) into a T -monoid follow directly from the axioms for an oplax T -algebra. To complete (i), we observe that â is an isomorphism if and only if the induced cell U_{A} [figure] A(aη, 1) ≅ A(a, 1)(η, 1) is an isomorphism, which says precisely that the unit defined above is cartesian. Conversely, if A [figure: M] T A is a T -monoid and M ≅ A(a, 1), then the same bijections supply 2-cells \overline{a} and â satisfying the same axioms making a: T A [figure] A into an oplax T -algebra; this shows (ii).

The following example may serve to clarify the connection between normality of oplax T -algebras and normalization of T -monoids.

9.3. Example. Let T be the “free strict monoidal category” monad on Set-ℙrof. Then an oplax T -algebra is an oplax monoidal category: a category A equipped with tensor product functors

A × ⋯ × A [figure] A
(x_{1}, …, x_{n}) ↦ ⟨x_{1} ⊗ … ⊗ x_{n}⟩

for n ≥ 0, and transformations

⟨x⟩ [figure] x
⟨x_{11} ⊗ … ⊗ x_{nk_{n}}⟩ [figure] ⟨⟨x_{11} ⊗ … ⊗ x_{1k_{1}}⟩ ⊗ … ⊗ ⟨x_{n1} ⊗ … ⊗ x_{nk_{n}}⟩⟩

satisfying certain evident axioms. Note that the 0-ary tensor product ⟨⟩ is a “lax unit” and the 1-ary tensor product ⟨x⟩ is not necessarily isomorphic to x, only related by the given unit transformation ⟨x⟩ [figure] x.

As mentioned previously, a T -monoid consists of a category A, a multicategory M with the same objects, and an identity-on-objects functor from A to the underlying ordinary category of M. Now Theorem 9.2 says that we can make an oplax monoidal category into a T -algebra by defining the multimorphisms in M from (x_{1}, …, x_{n}) to y to be the morphisms ⟨x_{1} ⊗ … ⊗ x_{n}⟩ [figure] y in A.

Note that the morphisms from x to y in the underlying ordinary category of M are the morphisms from ⟨x⟩ to y in A. The functor A [figure] M is defined by composing with the unit transformation ⟨x⟩ [figure] x. Clearly this is fully faithful (i.e. the T -monoid is normalized) just when ⟨x⟩ [figure] x is an isomorphism (i.e. the oplax T -algebra is normal).

The following characterization of pseudo T -algebras is now obvious.

9.4. Corollary. A normalized T -monoid A [figure: M] T A arises from a pseudo T -algebra if and only if

(i) M ≅ A(a, 1) for some T A [figure: a] A, and

(ii) the induced 2-cell \overline{a} is an isomorphism.

We say that a normalized T -monoid is weakly representable if it satisfies (i), and representable if it satisfies both (i) and (ii) (hence is equivalent to a pseudo T -algebra).

9.5. Example. When T is the “free strict monoidal category” monad on Set-ℙrof, Corollary 9.4 specializes to the characterization of monoidal categories as representable multicategories, as in [Her00] and [Lei04, §3.3]. We will see in §B.14 that it also includes the general representability notion of [Her01]. The analogue of Theorem 9.2 in the language of [Bur71] can be found in [Pen09], which uses “representable” for what we call “weakly representable” and “lax algebra” for what we call an “oplax algebra.”

9.6. Remark. Strictly speaking, the notion of monoidal category obtained in this way is the “unbiased” version, which is equipped with a specified n-ary tensor product for all n ≥ 0, instead of the usual “biased” version having only a binary and nullary product (see [Lei04, §3.1]). This is generally what happens for pseudoalgebras: if T is a monad whose strict algebras are some strict structure, then pseudo T -algebras are an “unbiased” sort of weak structure. Generally the unbiased version is equivalent to the biased one, but there is real mathematical content in this statement; for instance, the equivalence of biased and unbiased monoidal categories is essentially equivalent to Mac Lane’s coherence theorem.

9.7. Example. Recall that virtual double categories can be identified with S-monoids for the “free category” monad S on directed graphs, and hence also with normalized 𝕄od(S)-monoids. In this case it is easy to check that for a normalized 𝕄od(S)-monoid A [figure: M] T A, we have M ≅ A(a, 1) iff every composable string of horizontal arrows is the source of a weakly opcartesian arrow (see Remark 5.8). Thus, such virtual double categories can be identified with “normal oplax double categories,” which are equipped with n-ary composites for all n and comparison maps

⟨p_{11} ⊙ ⋯ ⊙ p_{nk_{n}}⟩ [figure] ⟨⟨p_{11} ⊙ ⋯ ⊙ p_{1k_{1}}⟩ ⊙ ⋯ ⊙ ⟨p_{n1} ⊙ ⋯ ⊙ p_{nk_{n}}⟩⟩

and invertible comparison maps

⟨p⟩ [figure: ≅] p

satisfying analogous axioms to an oplax monoidal category. Condition (ii) in Corollary 9.4 is then equivalent to requiring weakly opcartesian cells to be closed under composition. As observed in Remark 5.8, this suffices to ensure we have a pseudo double category, i.e. a pseudo 𝕄od(S)-algebra.

9.8. Example. Let U be the ultrafilter monad on ℝel. We have seen that a U-monoid is a topological space, and a normalized U-monoid is a T_{1}-space. A vertical U-algebra (which is automatically strict, since V(ℝel) is locally discrete) is a compact Hausdorff space, and in this case Theorem 9.2 tells us what we already knew: any compact Hausdorff space is, in particular, a T_{1} topological space.

Now consider the induced monad 𝕄od(U) on 𝕄od(ℝel). The objects of 𝕄od(ℝel) = 2-ℙrof are preorders. In the language of [Tho09], a strict 𝕄od(U)-algebra is an ordered compact Hausdorff space, whereas by Theorem 8.7 a normalized 𝕄od(U)-monoid is simply a topological space. Thus, Theorem 9.2 tells us that any ordered compact Hausdorff space X can be equipped with a topology in which an ultrafilter 𝔉 converges to a point y if and only if the (unique) limit of 𝔉 in X is ≤ y in the given preorder.

The next three examples can all be found in [Her01] (see B.14 for more on the comparison between our setting and Hermida’s).

9.9. Example. Let S be a small category and T the monad on C = Set^{ob(S)} whose algebras are functors S [figure] Set, as in Example 4.10, and consider the monad 𝕄od(T) on 𝕄od(𝕊pan(C)) = ℙrof(C). A strict 𝕄od(T)-algebra is a functor S [figure] Cat, while a pseudo 𝕄od(T)-algebra is a pseudofunctor S [figure] Cat. Now by Theorem 8.7, normalized 𝕄od(T)-monoids can be identified with T -monoids, which as we saw can be identified with functors A [figure] S. It is then easy to verify that a normalized 𝕄od(T)-monoid satisfies 9.4(i) iff the corresponding functor A [figure] S admits all weakly opcartesian liftings, and 9.4(ii) iff weakly opcartesian arrows are closed under composition. Thus, in this case Corollary 9.4 specializes to the classical equivalence between pseudofunctors S [figure] Cat and opfibrations over S.

9.10. Example. Let T be as in Example 9.9, but now consider T -monoids rather than 𝕄od(T)-monoids. A T -monoid is normalized just when for each x ∈ S, the induced span A(x, 1) [figure] M [figure] A(x, 1) is the identity span; i.e. when the fibers of A [figure] S are discrete categories. Such a normalized T -monoid satisfies 9.4(i) iff A [figure] S admits all weakly opcartesian liftings, which in this case are automatically opcartesian by discreteness. Thus, Corollary 9.4 also specializes to the equivalence of functors S [figure] Set and discrete opfibrations over S.

9.11. Example. Let T be the “free strict ω-category” monad on 𝕊pan(Globset), for which we saw in Example 4.11 that T -monoids on 1 are globular multicategories. Pseudo T -algebras are an “unbiased” version of the monoidal globular categories of [Bat98]. Thus any monoidal globular category has an underlying globular multicategory, and can be characterized among the latter by a representability property.

The requirement that T be normal in Theorem 9.2 cannot be dispensed with.

9.12. Example. Let P be the extension of the powerset monad to ℝel described in Example 3.7. Since V(ℝel) = Set is locally discrete, oplax P -algebras are just P - algebras in Set, which can be identified with complete meet-semilattices (the structure map P A [figure] A takes a subset X ⊆ A to its meet ⋀ X).

Now, we have observed in Example 4.14 that P -monoids can be identified with closure spaces. If we attempt to follow the prescription of Theorem 9.2, starting from a complete join-semilattice we would define the “closure operation” c(X) = {⋀ X}; but this is neither extensive nor monotone.

On the other hand, if we first apply 𝕄od, we obtain a monad 𝕄od(P) on 𝕄od(ℝel) = 2-ℙrof, which is normal. By Theorem 8.7, normalized 𝕄od(P)-monoids can be identified with P -monoids, i.e. closure spaces. With a little effort, pseudo 𝕄od(P)-algebras can be identified with meet-complete preorders (that is, preorders that are complete as categories). Theorem 9.2 then tells us that from a meet-complete preorder we can construct a closure space with c(X) = {x | ⋀ X ≤ x}, which is certainly true.

We can also make the correspondence of Theorem 9.2 functorial. Recall that for any T we have a 2-category KMon(𝕏, T) of T -monoids, defined to be the vertical 2category of 𝕂Mod(𝕏, T). It turns out that while T -monoids correspond to oplax T - algebras, morphisms of T -monoids correspond to lax T -algebra morphisms. Recall that a lax T -morphism between oplax T -algebras consists of a map f: A [figure] B and a 2-cell

[figure: T A; T f; a; \overline{f}; T B; b; A; f; B]

satisfying certain straightforward axioms. And if A [figure: f; g] B are two such, a T -transformation

is a 2-cell f [figure: α] g such that

[figure: T A; T f; a; \overline{f}; T B; b; A; f; g; α; B] = [figure: T A; a; T f; T g; T α; T B; b; \overline{f}; A; f; B.]

We write Oplax-T -Alg_{l} for the resulting 2-category.

9.13. Theorem. Let T be a normal monad on a virtual equipment 𝕏. Then there is a strict 2-functor Oplax-T -Alg_{l} [figure] KMon(𝕏, T), whose underlying 1-functor is fully faithful, and which becomes 2-fully-faithful (that is, an isomorphism on hom-categories) when restricted to normal oplax T -algebras.

Proof. For oplax T -algebras (A, a) and (B, b), regarded as T -monoids A [figure: A(a,1)] T A and

B [figure: B(b,1)] T B, a morphism of T -monoids consists of a vertical arrow f: A [figure] B and a 2-cell

[figure: A; A(a,1); f; T A; T f; B; B(b,1); T B]

satisfying certain axioms. But by definition of B(b, 1), and by Theorem 7.20 applied to A(a, 1), this 2-cell is equivalent to one

[figure: T A; U_{T A}; a; T A; T f; A; f; T B; b; U_{B}; .]

This defines a 2-cell b∘T f [figure] f ∘a in V(𝕏), which is precisely the additional data required to make f into a lax T -algebra morphism. It is easy to verify that the axioms of a T - monoid morphism are equivalent to the axioms of a lax T -algebra morphism under this translation, and that composition is preserved.

Now let f, g: A [figure] B be two such morphisms, and recall from §6 that a T -monoid transformation β: f [figure] g consists of a cell

[figure: B; T B; B(b,1); A; B; g; A; T B; η_{T B}∘f; B; T B; |; ⇓β]

satisfying a certain axiom. Equivalently, β is a 2-cell bηf [figure] g in V(𝕏). Thus, given a T -algebra transformation α: f [figure] g, it is natural to define β to be the composite

bηf [figure: b̂f] f [figure: α] g,

where b̂: bη [figure] 1 is the oplax unit map of B. With this definition, the axiom that must be satisfied for β to be a T -monoid transformation becomes the following equality of pasting diagrams in V𝕏.

[figure: B; T B; b; A; B; f; A; T A; a; T A; T B; T f; \overline{f}; T B; T^{2}B; T b; B; T B; η; B; T B; b; T B; T^{2}B; η; =; B; B; A; B; g; α; b̂; B; T B; b; \overline{b}; B; T B; b; B; B; B; T^{2}B; T^{2}B; T B; μ_{B}] = [figure: B; T B; b; A; B; g; A; T A; a; T A; T B; T g; \overline{g}; T A; T B; T f; T B; T^{2}B; T η_{B}; T B; T B; T α; T b̂; T B; T^{2}B; T b; \overline{b}; B; T B.; b; B; B; B; T^{2}B; T^{2}B; T B.; μ_{B}]  (9.14)

The cell marked “=” is an identity by Proposition 7.25 applied to a cell component of η. Now, two of the axioms for an oplax T -algebra say that

[figure: T B; T^{2}B; T b; B; T B; η; B; T B; b; T B; T^{2}B; η; =; B; B; b̂; B; T B; b; \overline{b}; B; T B; b; B; B; B; T^{2}B; T^{2}B; T B; μ_{B}] = [figure: B; T B; b; b; 1_{B}] = [figure: T B; T^{2}B; T η_{B}; T B; T B; T b̂; T B; T^{2}B; T b; B; T B; b; \overline{b}; B; T B.; b; B; B; B; T^{2}B; T^{2}B; T B.; μ_{B}]

After removing these composites from (9.14), what is left is simply the equation for α to be a T -algebra transformation; thus α is such precisely when β = α.b̂f is a T -monoid transformation. And, of course, if B is normal, then b̂f is an isomorphism, and so α can be recovered uniquely from β. We leave it to the reader to verify that this association preserves both types of 2-cell composition.

The restriction to normal oplax algebras in the final statement of Theorem 9.13 cannot be dispensed with either.

9.15. Example. Let A and B be oplax monoidal categories, regarded as T -monoids

for the “free strict monoidal category” monad T as in Example 9.3, and let A [figure: f; g] B be

lax monoidal functors. A T -algebra transformation f [figure] g is, in particular, a natural transformation f [figure] g, and therefore has components fx [figure: α_{x}] gx. However, if we unravel the definition of a T -monoid transformation, we see that its components are of the form

⟨fx⟩ [figure: β_{x}] gx. Thus, when B is not normal, there can be no bijection in general.

9.16. Remark. Recall from §1 that generalized multicategories can be regarded as “algebraic theories.” For instance, ordinary multicategories correspond to strongly regular finitary theories, while Lawvere theories correspond to arbitrary finitary theories. In language introduced by Jon Beck, one may say that the monad T provides the “doctrine” in which the theories are written. (Motivated by this, some authors use the word doctrine to mean simply a 2-monad.) If X is a T -monoid, regarded as a theory in the doctrine T, and A is a pseudo T -algebra, then it is natural to define a model of X in A to be a T -monoid homomorphism from X to (the underlying T -monoid of) A.

Now, frequently the functor of Theorem 9.13 has a left adjoint F_{T} when restricted to pseudo T -algebras and morphisms. In such a case, a model of X in A can equally be defined as a T -algebra morphism F_{T} X [figure] A. That is, F_{T} X is the “free T -algebra containing a model of X.” Following [Law63], this is sometimes called the “functorial semantics” of T.

For example, when X is a Lawvere theory, F_{T} X is the category with finite products that incarnates it. (In fact, as we remarked in Example 4.17, Lawvere theories are often defined to be certain categories with finite products.) Likewise, when X is a Lawvere Vtheory, then F_{T} X is the V-category with finite cotensors that incarnates it (see [Pow99]) and when X is an ordinary or non-symmetric operad, F_{T} X is the “PROP” or “PRO” associated to it (see [BV73]).

This adjunction can also be used to characterize representability. It turns out that the strict (resp. pseudo) algebras for the induced 2-monad T_{⊣} on KMon(𝕏, T) can be identified with strict (resp. pseudo) T -algebras. Moreover, T_{⊣} is a “lax-idempotent” 2-monad in the sense of [KL97], so that A is a pseudo T_{⊣}-algebra precisely when the unit A [figure] T_{⊣}A has a left adjoint. Thus the “structure” imposed by the 2-monad T has been transformed into “property-like structure” imposed by T_{⊣}. In particular cases, these observations can be found in [Her00, Her01, Pen09]; in [CS10b] we will study them in our general context.

A. Composites in 𝕄od and ℍ-Kl

In this appendix we consider the question of when 𝕄od(𝕏) and ℍ-Kl(𝕏, T) have composites and units, which will be needed for our comparisons with existing theories in the next appendix. The first case is easy; the following was also observed in [Shu08].

A.1. Theorem. If 𝕏 is an equipment in which each category H𝕏(A, B) has coequalizers, which are preserved on both sides by ⊙, then 𝕄od(𝕏) is also an equipment.

Proof (Sketch). We have seen already that 𝕄od(𝕏) always has units, and inherits restrictions from 𝕏, so it remains only to construct composites. We define the composite of bimodules A [figure: p] B [figure: q] C to be the coequalizer of the two actions of B:

p ⊙ B ⊙ q [figure] p ⊙ q [figure] p ⊙_{B} q

and similarly for longer composites. Given a cell

[figure: p; f; q; g; r]

in 𝕄od(𝕏), to factor it through p ⊙_{B} q, we first factor it through a cartesian cell to obtain a cell (p, q) [figure] r(g, f) in H𝕏(A, C), then factor this through the coequalizer in H𝕏(A, C), and finally compose again with the cartesian cell. Thus (p, q) [figure] p ⊙_{B} q is weakly opcartesian; to show that these cells compose we use the fact that ⊙ preserves coequalizers.

Note that we require 𝕏 to have restrictions, as well as composites, in order to show that 𝕄od(𝕏) has composites. We could instead assume explicitly that the coequalizers in H𝕏(A, B) satisfy a universal property relative to all cells, but in practice this generally tends to hold only because of the existence of restrictions.

A.2. Example. If V has small colimits preserved by ⊗, then V-𝕄at satisfies the hypotheses of Theorem A.1, so (as we have seen) V-ℙrof is an equipment.

A.3. Example. If C has pullbacks and coequalizers preserved by pullback, then 𝕊pan(C) satisfies the hypotheses of Theorem A.1, so (as we have also seen) ℙrof(C) is an equipment.

We have also already seen that ℍ-Kl(𝕏, T) always inherits restrictions from 𝕏. However, to show that it has composites, we require fairly strong conditions not just on 𝕏 but on T as well. Recall that a functor between pseudo double categories (and, therefore, also between equipments) is called strong if it preserves all composites. We then make the following definition:

A.4. Definition. A transformation F [figure: α] G of functors 𝕏 [figure: F; G] 𝕐 between equipments

is horizontally strong if for every horizontal arrow X [figure: p] Y in 𝕏, the cell induced by α_{p} under the bijection of Corollary 7.21:

[figure: F X; F p; F Y; GY (1,α_{Y} ); GY; F X; GX(1,α_{X}); GX; Gp; GY]

is an isomorphism. A monad T on an equipment 𝕏 is horizontally strong if T is a strong functor and μ and η are horizontally strong.

A.5. Remark. Recall from Remark 7.26 that any transformation α of functors between equipments induces an oplax transformation H(α) of functors between horizontal bicategories. Horizontal strength of α is equivalent to requiring H(α) to be a strong (aka pseudo) transformation (hence the name).

A.6. Example. Let [figure: C; F; G; α; D] be a transformation between pullback-preserving func-

tors between categories with pullbacks. It is not hard to verify that the induced transformation 𝕊pan(α) is horizontally strong if and only if α is a cartesian natural transformation, meaning that all its naturality squares are pullbacks. Therefore, if T is a pullback-preserving monad on C, the monad 𝕊pan(T) is horizontally strong if and only if μ and η are cartesian natural transformations. Such a T is often called a cartesian monad; see §B.1.

A.7. Example. We have remarked that most of the monads from Example 3.7 are not even strong functors in general, with the exception of the ultrafilter monad on ℝel. One can verify that for this monad, the multiplication transformation is horizontally strong, but the unit transformation is not; hence it is not a horizontally strong monad.

A.8. Theorem. If T is a horizontally strong monad on an equipment 𝕏, then ℍ-Kl(𝕏, T) is also an equipment.

Proof (Sketch). It suffices to show that ℍ-Kl(𝕏, T) has composites. A composable string of horizontal arrows

X_{0} [figure: p_{1}] X_{1} [figure: p_{2}]⋯ [figure: p_{n}] X_{n}

in ℍ-Kl(𝕏, T) consists of horizontal arrows X_{i} [figure: p_{i+1}] T X_{i+1} in 𝕏. Since 𝕏 is an equipment, we can form the composite

p_{1} ⊙ T (p_{2}) ⊙ ⋯ ⊙ T^{n−1}(p_{n}) ⊙ T X_{n}(1, μ^{n−1})

in 𝕏, which clearly supplies a weakly opcartesian cell in ℍ-Kl(𝕏, T). Likewise, T X(1, η) is a weak unit for X in ℍ-Kl(𝕏, T). The assumptions on T are required to show that these weakly opcartesian cells compose, or equivalently that this composition is associative; rather than write this out in detail we merely compute the 3-fold associativity isomorphism for X [figure: p] Y [figure: q] Z [figure: r] W.

(p ⊙ T q ⊙ T Z(1, μ)) ⊙ T r ⊙ T W (1, μ)
≅ p ⊙ T q ⊙ T^{2}r ⊙ T^{2}W (1, μT) ⊙ T W (1, μ) (strength of μ)
≅ p ⊙ T q ⊙ T^{2}r ⊙ T^{2}W (1, T μ) ⊙ T W (1, μ) (associativity of μ)
≅ p ⊙ T q ⊙ T^{2}r ⊙ T (T W (1, μ)) ⊙ T W (1, μ) (normality of T)
≅ p ⊙ T (q ⊙ T r ⊙ T W (1, μ)) ⊙ T W (1, μ)  (strength of T).

Of course, in the unit isomorphisms η is used instead of μ.

A.9. Corollary. If T is a horizontally strong monad on an equipment 𝕏, such that each category H𝕏(A, B) has coequalizers that are preserved by ⊙ on both sides and also preserved by T, then 𝕂Mod(𝕏, T) is also an equipment.

Proof. The hypotheses ensure that ℍ-Kl(𝕏, T) satisfies the conditions of Theorem A.1.

A.10. Example. If T is a cartesian monad on a category C with pullbacks, then we have seen that the induced monad on 𝕊pan(C) is horizontally strong; thus ℍ-Kl(𝕊pan(C) , T) is an equipment. If furthermore C has coequalizers that are preserved by pullback and by T, then Corollary A.9 implies that 𝕂Mod(𝕊pan(C) , T) is also an equipment.

For example, the “free M-set” monad (M × −) on Set preserves coequalizers, so we have an equipment of M-graded categories. However, the “free monoid” monad does not preserve coequalizers, and the virtual equipment of ordinary multicategories is not an equipment.

A.11. Example. Let V be a symmetric monoidal category with small coproducts preserved by ⊗ on both sides, and let T be the extension of the “free monoid” monad on Set to a monad on V-𝕄at defined in Example 3.12. We have already remarked in Examples 5.11 that T is strong, and an easy calculation shows that it is in fact horizontally strong. Thus, ℍ-Kl(V-𝕄at, T) is an equipment. However, even if V is cocomplete, and in particular has coequalizers preserved by ⊗ on both sides, these coequalizers will not in general be preserved by T. Thus, the virtual equipment 𝕂Mod(V-𝕄at, T) of V-enriched ordinary multicategories fails to be an equipment. (For V = Set we have seen this already in the previous example.)

A.12. Example. Let V be a cocomplete symmetric monoidal category with small colimits preserved by ⊗ on both sides, and let T be the “free symmetric strict monoidal Vcategory” monad on V-ℙrof from Examples 3.14 and 4.16. We remarked in Examples 5.12 that T is strong. In fact, it is easily seen to be horizontally strong, so that ℍ-Kl(V-ℙrof, T) is an equipment. As in the previous example, however, T fails to preserve coequalizers in H(V-ℙrof)(A, B), so that 𝕂Mod(V-ℙrof, T) is not an equipment even when V = Set.

When the horizontal arrows in ℍ-Kl(Set-ℙrof, T) are identified with the generalized structure types of [FGHW08] as in Remark 4.20, their horizontal composites are identified with the substitution operation on structure types. In [FGHW08] the bicategory H(ℍ-Kl(Set-ℙrof, T)) was constructed in this way from structure types and substitution.

A.13. Example. Let T be the “free category with strictly associative finite products” monad on V-ℙrof from Examples 3.15 and 4.17. We remarked in Examples 5.12 that T is strong if V is cartesian monoidal. In fact, in this case it can moreover be shown to be horizontally strong, so that ℍ-Kl(V-ℙrof, T) is an equipment.

Now we specialize to V = Set. If 1 denotes the terminal category, then T 1 is equivalent to Set_{f}^{op}, the opposite of the category of finite sets. Thus, a profunctor 1 [figure] T 1 is equivalent to a functor Set_{f} [figure] Set, which (since Set is locally finitely presentable) is equivalent to a finitary endofunctor of Set. It is then not hard to verify that the equivalence

H(ℍ-Kl(Set-ℙrof, T))(1, 1) ≃ [Set_{f}, Set]

is actually an equivalence of monoidal categories, and thus induces an equivalence between categories of monoids. But a monoid in H(ℍ-Kl(Set-ℙrof, T))(1, 1) is a T -monoid 1 [figure] T 1, i.e. a Lawvere theory; thus we recover the classical result of [Law63] that Lawvere theories can be identified with finitary monads on Set.

An analogous argument for the “free V-category with finite cotensors” monad on V-ℙrof from Examples 3.16 and 4.18 reproduces the result of [Pow99] that Lawvere Vtheories can be identified with finitary V-monads on V. In this case, ℍ-Kl(V-ℙrof, T) seemingly need not be an equipment, but at least the multicategory ℍ-Kl(V-ℙrof, T)(1, 1) is a monoidal category, precisely because it can be identified with the monoidal category of finitary endofunctors of V under composition.

A.14. Example. Let Set-ℙrof_{ls} denote the virtual double category whose objects are locally small categories (that is, large categories with small hom-sets), whose vertical arrows are functors, and whose horizontal arrows are profunctors taking values in small sets. Then there is a monad T on Set-ℙrof_{ls} whose algebras are categories with all small products, and we have T 1 ≃ Set^{op}. Thus, by analogous reasoning to Example A.13, we see that T -monoids 1 [figure] T 1 for this T can be identified with arbitrary monads on Set. We can likewise obtain monads on any suitable V by using the monad for arbitrary cotensors on V-ℙrof_{ls}. In [CS10a] we will see that by regarding monads as particular generalized multicategories in this way, we can recover the monad associated to an operad (as originally defined in [May72]) as a particular case of the functoriality of generalized multicategories.

B. Comparisons to previous theories

We now describe the existing approaches to generalized multicategories, and show how they compare to our theory. Most existing approaches turn out to be instances of our theory, applied to a particular sort of monad on a particular sort of virtual equipment. Unsurprisingly, however, often more can be said in such special cases that is not true in general. Thus, in each section below we briefly mention some of the additional results that different authors have obtained in their particular contexts.

B.1. Cartesian Monads. In order to study and define a type of n-category, Leinster developed a theory of cartesian monads and their associated multicategories. This theory was developed in a series of papers, eventually culminating in his book [Lei04]. Recall the following from Example A.6:

B.2. Definition. Let E be a category with pullbacks. A monad (T, η, μ) on E is cartesian if T preserves pullbacks, and all naturality squares of η and μ are pullbacks.

Given a cartesian monad, Leinster constructs a bicategory E_{(T)} of T -spans and defines a (E, T)-multicategory (or simply a T -multicategory) to be a monad in E_{(T)}. To compare this to our context, recall that whenever E has pullbacks, 𝕊pan(E) is an equipment, and any pullback-preserving monad T on such a E extends to a strong monad on 𝕊pan(E), which is horizontally strong just when T is cartesian. It is then easy to see:

B.3. Proposition. For a cartesian monad T on E, Leinster’s bicategory E_{(T)} is isomorphic to H(ℍ-Kl(𝕊pan(E), T)).

Therefore, Leinster’s category of (E, T)-multicategories is the vertical category of our 𝕂Mod(𝕊pan(E) , T). In particular, what he calls a T -operad is a T -monoid 1 [figure] T 1 in 𝕊pan(E).

Actually, Leinster constructs the whole virtual double category 𝕂Mod(𝕊pan(E) , T) (which he calls an fc-multicategory) in [Lei04, §5.3], and uses it to define transformations of his generalized multicategories just as we did in §6. (The notes at the end of his §5.3 also point in the direction of our §§5 and 7.)

Leinster also proves most of the results of our §9 in his context, as well as the functoriality of the construction mentioned in Remark 4.4. Furthermore, he shows that if T is a “suitable” cartesian monad on a “suitable” cartesian category E, then the category of (E, T)-multicategories is itself monadic over a cartesian category of “T -graphs,” and this monad is also cartesian. Thus the process can be iterated, leading to a definition of the “opetopes” used in the Baez-Dolan definition of weak n-categories. Finally, Leinster also studies algebras for generalized operads, which are closely related to the horizontal arrows in 𝕂Mod(𝕏, T).

B.4. Clubs. Essentially the same theory was developed in [Kel92] for the case of generalized operads (generalized multicategories on 1). Observe that when T is a cartesian monad on a category E with finite limits, so that ℍ-Kl(𝕊pan(E) , T) is an equipment, then in particular the category

E/T 1 ≃ H(ℍ-Kl(𝕊pan(E) , T))(1, 1)

inherits a monoidal structure. It is easy to verify that this monoidal structure on E/T 1 is the same as that constructed by Kelly (see the explicit description in [Kel92, p. 174–175]). Kelly defined a club over T to be a monoid for this monoidal structure; thus such clubs can be identified with T -monoids 1 [figure] T 1 in 𝕊pan(E). He also proved that such clubs are essentially equivalent to cartesian monads equipped with a “cartesian map” to T.

(Actually, in [Kel92] it was assumed that T preserves certain pullbacks rather than all pullbacks. This suffices to construct a monoidal structure on E/T 1, though not for T to define a monad on all of 𝕊pan(E).)

B.5. Pseudomonads on Prof. The existing theory which is probably closest to our approach involves the construction of a Kleisli bicategory from a pseudomonad on a bicategory such as V-ℙrof. A general theory of multicategories based on such pseudomonads does not appear to exist in the literature, but it is implicit in [BD98, Che04, FGHW08, Gar08, DS03] among other places.

The general framework is, however, quite simple to state: from a pseudomonad T on a bicategory B, one can construct the Kleisli bicategory B_{T} and consider monads in B_{T} as a notion of generalized multicategory. (Leinster’s approach is a special case of this for B = 𝕊pan(C), as is Hermida’s for a different bicategory—see §B.14, below.) The relationship with our theory is that if T is a horizontally strong monad on an equipment 𝕏, it gives rise to a pseudomonad H(T) on the bicategory H(𝕏), and H(𝕏)_{H(T)} ≃ H(ℍ-Kl(𝕏, T)) so that the resulting notions of multicategory agree.

In the converse direction, of course not every pseudomonad on H(𝕏) arises from a monad on 𝕏 itself, but we have seen that this is true for most monads relative to which one may want to define generalized multicategories. In a few cases, however, the extension to 𝕏 may not be vertically strict, necessitating the extension of vEquip to a tricategory.

Note that if T is also co-horizontally strong, in the sense that its horizontal dual is horizontally strong, then it also induces a pseudo-comonad Ĥ(T) on the bicategory H(𝕏). From this perspective, T -monoids can be identified with lax Ĥ(T)-coalgebras. Of course, if we work in the horizontal dual, then Ĥ(T) becomes a pseudomonad and T -monoids are its lax algebras. This is the terminology used by several authors, including Hermida. The authors of [DS03] consider the special case when the bicategory B is monoidal and T is its free monoid monad, so that T -monoids can be called lax monoids. Such lax monoids can also be described directly in terms of B, without the need for cocompleteness hypotheses to ensure that T exists.

B.6. (T, V)-algebras. Following Barr [Bar70], [CT03] started a series of papers which described the ideas of a “set-monad with lax extension to V-Mat”, as well as the (T, V)- algebras associated to these monads. Barr’s original idea showed that the “lax algebras” of the ultrafilter monad are topological spaces; Clementino and Tholen’s idea extended this further, developing a framework that eventually included not only topological spaces, but also metric spaces, approach spaces, and closure spaces.

In the work on (T, V)-algebras, two definitions of set-monad with lax extension to V-Mat have been proposed. The original version was applicable to all monoidal V. However, it failed to capture all relevant examples, and so a second, slightly different definition was proposed in [Sea05], which captured further examples. However, this definition was only applicable when V was a preorder. As we shall see, Seal’s definition turns out to be equivalent to asking for a monad on V-𝕄at (in the case when V is ordered), while the original definition is equivalent to asking for a monad on V-𝕄at which is normal.

The original definition, given in [CT03], was as follows:

B.7. Definition. A set monad with lax extension to V consists of a monad (T, η, μ) on Set, together with a lax functor T_{M} on V-Mat such that:

• T_{M} is the same as T on objects and functions (viewed as V-matrices),

• the comparisons (T_{M}s)(T_{M}r) [figure] T_{M}(sr) are isomorphisms when r is a function,

• when viewed as transformations on T_{M}, η and μ have op-lax structure.

In general, however, this definition was found to be too restrictive, as it didn’t allow for examples such as extensions of the powerset monad, whose algebras would be closure spaces. To include this type of example, the requirement that T_{M} was the same as T on functions needed to be removed. Seal’s definition, given in [Sea05], was the following:

B.8. Definition. Suppose that V is a monoidal preorder. A set monad with lax extension to V consists of a monad (T, η, μ) on Set, together with a lax functor T_{M} on V-Mat which is the same as T on objects, and satisfies

(i) T f ≤ T_{M}f,

(ii) (T f)^{∘} ≤ T_{M}f^{∘}.

Here, ()^{∘} denotes taking the opposite V-matrix. By [Sea05, p. 225] the conditions imply that if q is a V-matrix and f a function, then T_{M}(qf) = (T_{M}q)(T f) and T_{M}(f^{∘}q) = (T f)^{∘}(T_{M}q).

In [Sea05, p. 203], he also shows that when V is completely distributive, η and μ have op-lax structure. However, this is not a priori required in his definition. If, however, we include this axiom in his definition, then his notion of set monad with lax extension is equivalent to giving our notion of a monad on the virtual double category V-𝕄at.

B.9. Proposition. Suppose that V is a monoidal preorder. If T is a set monad with lax extension T_{M} (in the sense of Seal) for which η and μ are op-lax, then we can define a monad T on V-𝕄at which is T on vertical arrows, and T_{M} on horizontal arrows. Conversely, given a monad T on V-𝕄at, we can define a set monad with lax extension which is T on functions, and uses the horizontal action of T to define T_{M}.

Proof. Suppose that we have a set monad with lax extension to V, in the second sense given above. Define a functor T on the double category V-𝕄at, which is T on vertical arrows, and T_{M} on horizontal arrows. Using the η and μ, we get all of the necessary data for a monad on V-𝕄at, with the exception of checking that

[figure: W; Z; X; W; f; X; Y; Y; Z; g; X; Y; p; W; Z; q; implies; T W; T Z; T X; T W; T f; T X; T Y; T Y; T Z; T g; T X; T Y; T p; T W; T Z; T q]

This is equivalent to checking that p ≤ g^{∘}qf ⇒ T_{M}(p) ≤ (T g)^{∘}T_{M}q(T f). But this is easy to check by using the two results given after Seal’s definition.

T_{M}(p) ≤ T_{M}(g^{∘}qf) = (T g)^{∘}T_{M}(qf) = (T g)^{∘}(T_{M}q)(T f)

Conversely, suppose that we have a monad T on V-𝕄at. We would like to define a lax extension of T (considered as a Set-monad) to V-Mat. Define T_{M} on matrices as for T. The only conditions we need to check are T f ≤ T_{M}f and (T f)^{∘} ≤ T_{M}f^{∘}. To show the first is equivalent to showing that T B(1, T f) ≤ T (B(1, f)). To show this, recall that we have a cartesian cell

[figure: A; B; B; B; B(1,f); U_{B}; f]

Moreover, since T is a functor, it preserves cartesian cells (Theorem 7.24), and so

[figure: T A; T B; T B; T B; T (B(1,f)); T (U_{B}); T f]

is also cartesian. We can thus factor the cell

[figure: T A; T B; T B; T B; T B; T B; T B(1,T f); U_{T B}; T f; T (U_{B})]

through it to get a cell

[figure: T A; T B; T A; T B; T B(1,T f); T (B(1,f))]

as required. The second inequality follows similarly, using the cartesian cell

[figure: B; A; B; B; B(f,1); U_{B}; f]

Thus, a monad on V-𝕄at defines a set-monad with lax extension to V-Mat.

For general V, we can also use the above correspondence to recover the first notion of notion of set-monad with lax extension: they are the monads which are normal.

B.10. Proposition. Using the above correspondence, we get a set-monad with lax extension in the first sense if and only if the monad T on V-𝕄at is normal.

Proof. Suppose we have a set-monad T with lax extension T_{M} in the first sense. Then we have T_{M}f ≅ T f for all functions f, and we get a monad on V-𝕄at. Moreover, we also have T (B(1, f)) ≅ T B(1, T f). In particular, we have T (A(1, 1)) ≅ T A(1, 1). But A(1, 1) ≅ U_{A}, so we have T (U_{A}) ≅ U_{T A}. Thus T is normal.

Conversely, suppose that we have a monad T on V-𝕄at which is normal. We would like to show that T (B(1, f)) ≅ T B(1, T f). Using the factoring as for the above proposition, we get a cell in one direction. To get the other direction, we factor

[figure: T B; T B; T B; T B; T B; T B; T B; T B; T A; T B; T (B(1,f)); T B; T B; T (U_{B}); T B; T B; T A; T B; T f; T A; T B; T B; T B; T B; T B; U_{T B}; through; T B; T B; T A; T B; T f; T A; T B; T B; T B; T A; T B; T B(1,T f); T B; T B; U_{T B}]

(note that the bottom cell on the left exists by normality of T). The composites of the two cells are identities by the universal property of the cartesian cells, and so we have T (B(1, f)) ≅ T B(1, T f), as required. We also need to check the condition that the comparison cell be an isomorphism when r is a function. However, this is equivalent to asking that T (r(1, s)) ≅ T r(1, T s), and this follows from Theorem 7.24.

For a set-monad with lax extension T, the category of (T, V)-algebras that Tholen, Clementino and Seal define is exactly the vertical category of the virtual double category 𝕂Mod(V-𝕄at, T). They also describe (T, V)-modules, and these are the horizontal arrows of 𝕂Mod(V-𝕄at, T).

In addition to providing a more conceptual explanation of the notion of lax extension, and a way to compare (T, V)-algebras with other notions of generalized multicategory, our general framework improves the theory of (T, V)-algebras in two ways. Firstly, it gives a context in which the horizontal Kleisli construction makes sense; such a construction has been recognized as desirable (see, for example, [Tho07, p. 7]), but is impossible using only bicategories since the monads used in this case are not horizontally strong. Secondly, it provides a general reason for the observation of [Tho07, p. 15] that any set-monad with lax extension to V-Mat can also be extended to a monad on V-Cat with a lax extension to V-Prof (we simply apply the 2-functor 𝕄od).

There are, however, other special aspects of the theory of (T, V)-algebras which we have not discussed. One is that the category of (T, V)-algebras is generally topological over Set, and has many other similar formal properties. Another is the use of the “pro” construction found in [CHT04]. This is useful to describe additional topological structures; for example, monoids in pro-ℝel are quasi-uniform spaces. In general, given a virtual double category 𝕏, one can define a new virtual double category pro-𝕏, and go on to describe “pro-generalized multicategories”. Further discussion of this, however, awaits a future paper.

B.11. Non-cartesian monads. The earliest work on generalized multicategories was by Burroni in [Bur71]. His framework is very similar to Leinster’s (see §B.1) except that he requires nothing at all about the monad T, not even that it preserve pullbacks (although the category E must still have pullbacks). This level of generality does not fit into our existing framework, since if T does not preserve pullbacks then it does not induce a functor on 𝕊pan(E) of the sort we have defined. However, it does induce an oplax functor between pseudo double categories.

The simplest way for us to define an oplax functor is to say it is a functor between pseudo double categories regarded as co-virtual double categories. Pseudo double categories, oplax functors, and transformations form a 2-category, and we define an oplax monad on a pseudo double category to be a monad in this 2-category. Since any functor on a category E with pullbacks induces an oplax functor on 𝕊pan(E), any monad on such an E induces an oplax monad on 𝕊pan(E). Moreover, we can extend our framework to deal with oplax functors as follows.

B.12. Definition. If T is an oplax monad on a pseudo double category 𝕏, the horizontal Kleisli virtual double category ℍ-Kl(𝕏, T) of T is defined as follows.

• Its objects, vertical and horizontal arrows, and cells with nullary source are defined as when T is a lax functor.

• A cell

[figure: Y_{0}; Y_{1}; X_{0}; Y_{0}; f; X_{0}; X_{n}; X_{n}; Y_{1}; g; Y_{0}; Y_{1}; q; X_{0}; X_{1}; p_{1}; X_{1}; X_{2}; p_{2}; X_{2}; ⋯; p_{3}; ⋯; X_{n}; p_{n}; α]

in ℍ-Kl(𝕏, T) is a cell

[figure: X_{0}; p_{1}⊙T (p_{2}⊙T (···T (p_{n−1}⊙T p_{n})···)); f; T^{n}X_{n}; T g∘μ^{n}; Y_{0}; q; T Y_{1}]

in 𝕏.

• Composition is defined using the multiplication, unit, and oplax structure of T. For

example, the composite of

[figure: ⇓α; ⇓β; ⇓γ; ⇓δ]

is given by the composite

δ ∘ (α ⊙ T (β ⊙ T γ)) ∘ (1 ⊙ μ) ∘ (1 ⊙ T (1 ⊙ μ)) ∘ T_{⊙}

in 𝕏,where T_{⊙} is a composite of the oplax structure maps of T:

p_{1} ⊙ T (p_{2} ⊙ T (p_{3} ⊙ T (p_{4} ⊙ T (p_{5} ⊙ T p_{6})))) [figure] p_{1} ⊙ T p_{2} ⊙ T^{2}(p_{3} ⊙ T p_{4} ⊙ T^{2}(p_{5} ⊙ T p_{6}))

Note that when T is a strong functor, both definitions of ℍ-Kl(𝕏, T) make sense; however, in this case, they are equivalent.

B.13. Definition. If T is an oplax monad on a pseudo double category 𝕏, then a T -monoid is a monoid in ℍ-Kl(𝕏, T), and we write 𝕂Mod(𝕏, T) = 𝕄od(ℍ-Kl(𝕏, T)).

To compare this to Burroni’s definition, note that ℍ-Kl(𝕏, T) clearly has weak composites, and hence is an oplax double category (see Example 9.7). Burroni works instead with what he calls a pseudo-category, and what we would probably call a lax-biased bicategory: a bicategory-like structure with units and binary composites and noninvertible comparison maps

p [figure] p ⊙ U_{A}
p [figure] U_{B} ⊙ p
p ⊙ (q ⊙ r) [figure] (p ⊙ q) ⊙ r.

satisfying suitable axioms. In fact, of course, Burroni’s “pseudo-category of T -spans” extends to a lax-biased double category. Moreover, any lax-biased double category defines an oplax double category (and hence a virtual double category), if we take the n-ary composite to be

⟨p_{1} ⊙ ⋯ ⊙ p_{n}⟩ = p_{1} ⊙ (p_{2} ⊙ ⋯ (p_{n−1} ⊙ p_{n}) ⋯).

(Burroni points this out as well; see [Bur71, p. 66, example 3]. He refers to virtual double categories as simply “multicatégories”.) In this way, Burroni’s Sp(T) is identified with our H(ℍ-Kl(𝕊pan(E), T)), and thus his “T -categories” can be identified with our T -monoids. However, he must move outside the bicategory (or “pseudo-category”) framework to define functors of T -categories, whereas they emerge naturally from our setup.

Burroni also constructs the left adjoint F_{T} from Remark 9.16, and proves the functoriality of his construction under lax morphisms of monads. Working with his language, [Pen09] gives a version of the representability results from §9.

B.14. Cartesian 2-monads. We have described the horizontal arrows A [figure] B in Set-ℙrof as profunctors, i.e. functors B^{op} × A [figure] Set, but it is well-known that such functors can equivalently be described by two-sided discrete fibrations, and that this notion can be internalized to a sufficiently well-behaved 2-category. [Her01] develops a theory of generalized multicategories in such a context.

Let K be a finitely complete 2-category (see [Str76]). Since its underlying ordinary category K_{0} has pullbacks, we can form the virtual equipment ℙrof(K_{0}). Now, as observed in [Str74], for any object A ∈ K we have an internal category ΦA in K, defined by (ΦA)_{0} = A and (ΦA)_{1} = A^{2} (the cotensor with the arrow category 2). Similarly, every morphism f: A [figure] B defines an internal functor Φf: ΦA [figure] ΦB, and the same for 2-cells; thus we have a 2-functor K [figure] V(ℙrof(K_{0})). Moreover, this 2-functor is locally full and faithful, i.e. 2-cells f [figure] g are in bijection with internal natural transformations Φf [figure] Φg.

We define an internal profunctor ΦA [figure: H] ΦB to be a discrete fibration from A to B if the object H ∈ K/(A × B) is internally discrete, i.e. (K/(A × B))(C, H) is a discrete category for any C ∈ K/(A×B). We define 𝔻Fib(K) to be the sub-virtual double category of ℙrof(K_{0}) determined by

• The internal categories of the form ΦA,

• The internal functors of the form Φf, • The internal profunctors which are discrete fibrations, and

• All cells between these.

Since the pullback of a discrete fibration is a discrete fibration, and U_{ΦA} is a discrete fibration, 𝔻Fib(K) is a virtual equipment. Our remarks above show that K ≃ V(𝔻Fib(K)). Under suitable conditions on K, discrete fibrations can be composed, so that 𝔻Fib(K) becomes an equipment. (Several authors have tried to isolate these conditions, with varying degrees of success; in addition to [Her01] see [Str80] and [CJSV94]. Our approach sidesteps this issue completely.)

Now suppose that F: K [figure] L is a 2-functor that preserves pullbacks and comma objects. Then it preserves internal categories, profunctors, the Φ construction, and discrete fibrations, so it induces a normal functor 𝔻Fib(F): 𝔻Fib(K) [figure] 𝔻Fib(L). Likewise, any 2-natural transformation F [figure] G induces a transformation 𝔻Fib(F) [figure] 𝔻Fib(G), so we have a 2-functor 𝔻Fib from finitely complete 2-categories to vEquip. In particular, any 2-monad T on K whose functor part preserves pullbacks and comma objects induces a normal monad on 𝔻Fib(K), so we can talk about 𝔻Fib(T)-monoids.

This is basically the context of [Her01], except that, like most other authors, he works only with bicategories. Thus, he assumes that K has the structure required to compose discrete fibrations, and that moreover T preserves this structure and that μ and η are cartesian transformations. This ensures that 𝔻Fib(T) is horizontally strong, so that ℍ-Kl(𝔻Fib(K), 𝔻Fib(T)) is an equipment. Under these hypotheses, we have:

B.15. Theorem. The 2-category nKMon(𝔻Fib(K), 𝔻Fib(T)) of normalized 𝔻Fib(T)- monoids is isomorphic to the 2-category Lax-Bimod(T)-alg defined in [Her01, 4.3 and 4.4].

Our Theorem 9.2 is also a generalization of results of [Her01]. Hermida proves furthermore that under his hypotheses, the left adjoint F_{T} from Remark 9.16 exists, the adjunction is monadic when restricted to pseudo T -algebras, and the induced monad T_{⊣} on Lax-Bimod(T)-alg is lax-idempotent (see [KL97]). In [CS10b] we will show that an analogous result is true for any monad T on an equipment 𝕏 satisfying suitable cocompleteness conditions.

B.16. Monoidal pseudo algebras. In [Web05], Weber gives a definition of generalized operads enriched in monoidal pseudo algebras. More precisely, for any 2-monad T on a 2-category K with finite products, and any pseudo T -algebra A which is also a pseudomonoid in a compatible way, he defines a notion of T -operad in A. A general description of the relationship of this theory to ours would take us too far afield, so we will remark only briefly on how such a comparison should go.

For any pseudomonoid A in a 2-category K with finite products, there is a virtual equipment A-𝕄at defined as follows. Its objects and vertical arrows are the objects and arrows of K. A horizontal arrow from X [figure] Y is a morphism X × Y [figure: p] A in K, and a cell

[figure: X_{0}; p_{1}; f; X_{1}; X_{n−1}; p_{n}; X_{n}; g; Y_{0}; q; Y_{1}]

is a 2-cell

[figure: Y_{0} × Y_{1}; A.; q; (X_{0} × X_{1}) × (X_{1} × X_{2}) × ⋯ × (X_{n−1} × X_{n}); Y_{0} × Y_{1}; (f,g); (X_{0} × X_{1}) × (X_{1} × X_{2}) × ⋯ × (X_{n−1} × X_{n}); A.; (p_{1}⊗···⊗p_{n})]

in K, where ⊗: A × A [figure] A is the multiplication of the pseudomonoid A (if n = 0 we use its unit instead).

Now, if A is additionally a pseudo T -algebra in a compatible way, we might hope to be able to extend T to a monad on A-𝕄at. However, given a horizontal arrow X [figure: p] Y, from X × Y [figure: p] A we can form the composite

T (X × Y) [figure: T p] T A [figure: a] A,

but this is not yet a horizontal arrow T X [figure] T Y. If we assume that A admits well-

behaved left (Kan) extensions, then we can define T X [figure: T p] T Y to be the extension of the above composite along T (X×Y) [figure] T X×T Y. We can then construct ℍ-Kl(A-𝕄at, T) and 𝕂Mod(A-𝕄at, T) as usual. Moreover, we can give an equivalent characterization of ℍ-Kl(A-𝕄at, T) which is valid even in the absence of left extensions: a horizontal arrow X [figure] Y is a morphism X × T Y [figure: p] A in K, and a cell

[figure: X_{0}; p_{1}; f; X_{1}; X_{n−1}; p_{n}; X_{n}; g; Y_{0}; q; Y_{1}]

is a 2-cell [figure: X_{0} × T (X_{1} × … T (X_{n−1} × T X_{n}) …); π; p_{1}⊗...⊗p_{n}; X_{0} × T^{n}X_{n}; 1×μ^{n−1}; A; X_{0} × T X_{n}; f×T g; Y_{0} × T Y_{1}; q]

in K. Thus, we obtain a notion of T -monoid in A for any monoidal pseudo algebra A. Weber only considers the case of operads, rather than more general multicategories, but it is easy to verify that his T -operads in A coincide with those T -monoids in A whose underlying object in K is the terminal object 1.

Actually, there is a good reason that Weber considers only operads: T -monoids X_{0} [figure: X] T X_{0} in this context for which X_{0} is not discrete, or at least a groupoid, are not very familiar objects. In familiar cases such as K = Cat, we would obtain familiar types of A-enriched multicategory only by taking the horizontal arrows X [figure] Y in A-𝕄at to be morphisms X × Y^{op} [figure] A, rather than X × Y [figure] A. To put this in a general context, however, requires a 2-category K in which “opposites” make sense, such as the “2-toposes” of [Web07].

References

[Bar70] Michael Barr. Relational algebras. Lectures Notes in Mathematics 137: Reports of the Midwest Category Seminar IV, pages 39–55, 1970.

[Bat98] M. A. Batanin. Monoidal globular categories as a natural environment for the theory of weak n-categories. Adv. Math., 136(1):39–103, 1998.

[BD98] John C. Baez and James Dolan. Higher-dimensional algebra. III. n-categories and the algebra of opetopes. Adv. Math., 135(2):145–206, 1998.

[BD01] John C. Baez and James Dolan. From finite sets to Feynman diagrams. In Mathematics unlimited—2001 and beyond, pages 29–50. Springer, Berlin, 2001.

[Bec69] Jon Beck. Distributive laws. In Sem. on Triples and Categorical Homology Theory (ETH, Zürich, 1966/67), pages 119–140. Springer, Berlin, 1969.

[Bén67] Jean Bénabou. Introduction to bicategories. In Reports of the Midwest Category Seminar, pages 1–77. Springer, 1967.

[BM03] Clemens Berger and Ieke Moerdijk. Axiomatic homotopy theory for operads. Comment. Math. Helv., 78(4):805–831, 2003.

[BS76] Ronald Brown and Christopher B. Spencer. Double groupoids and crossed modules. Cahiers Topologie Géom. Différentielle, 17(4):343–362, 1976.

[Bur71] Albert Burroni. T -catégories (catégories dans un triple). Cahiers Topologie Géom. Différentielle, 12:215–321, 1971.

[BV73] J. M. Boardman and R. M. Vogt. Homotopy invariant algebraic structures on topological spaces. Lecture Notes in Mathematics, Vol. 347. Springer-Verlag, Berlin, 1973.

[Che04] Eugenia Cheng. Weak n-categories: opetopic and multitopic foundations. Journal of Pure and Applied Algebra, 186(2):109 – 137, 2004.

[CHT04] M. Clementino, D. Hofmann, and W. Tholen. One setting for all: metric, topology, uniformity, approach structure. Applied Categorical Structures, 12:127–154, 2004.

[CJSV94] Aurelio Carboni, Scott Johnson, Ross Street, and Dominic Verity. Modulated bicategories. J. Pure Appl. Algebra, 94(3):229–282, 1994.

[CS10a] G. S. H. Cruttwell and Michael A. Shulman. On the functoriality of generalized multicategories. In preparation, 2010.

[CS10b] G. S. H. Cruttwell and Michael A. Shulman. Representability of generalized multicategories. In preparation, 2010.

[CT03] M. Clementino and W. Tholen. Metric, topology, and multicategory - a common approach. J. Pure and Applied Algebra, 153:13–47, 2003.

[DL07] Brian J. Day and Stephen Lack. Limits of small functors. J. Pure Appl. Algebra, 210(3):651–663, 2007.

[DPP06] R. Dawson, R. Paré, and D. A. Pronk. Paths in double categories. Theory Appl. Categ., 16:No. 18, 460–521 (electronic), 2006.

[DPP10] R. Dawson, R. Pare, and D. A. Pronk. The span construction. Theory Appl. Categ., 24:302–377 (electronic), 2010.

[DS97] Brian Day and Ross Street. Monoidal bicategories and Hopf algebroids. Adv. Math., 129(1):99–157, 1997.

[DS03] Brian Day and Ross Street. Lax monoids, pseudo-operads, and convolution. In Diagrammatic morphisms and applications (San Francisco, CA, 2000), volume 318 of Contemp. Math., pages 75–96. Amer. Math. Soc., Providence, RI, 2003.

[EM06] A. D. Elmendorf and M. A. Mandell. Rings, modules, and algebras in infinite loop space theory. Adv. Math., 205(1):163–228, 2006.

[FGHW08] M. Fiore, N. Gambino, M. Hyland, and G. Winskel. The Cartesian closed bicategory of generalised species of structures. J. Lond. Math. Soc. (2), 77(1):203–220, 2008.

[Gar08] Richard Garner. Polycategories via pseudo-distributive laws. Adv. Math., 218(3):781–827, 2008.

[GP99] Marco Grandis and Robert Paré. Limits in double categories. Cahiers Topologie Géom. Différentielle Catég., XL(3):162–220, 1999.

[GP04] Marco Grandis and Robert Paré. Adjoints for double categories. Cah. Topol. Géom. Différ. Catég., 45(3):193–240, 2004.

[Her00] Claudio Hermida. Representable multicategories. Advances in Mathematics, 151:164–225, 2000.

[Her01] Claudio Hermida. From coherent structures to universal properties. J. Pure and Applied Algebra, 165:7–61, 2001.

[Joh02] Peter T. Johnstone. Sketches of an Elephant: A Topos Theory Compendium: Volume 1. Number 43 in Oxford Logic Guides. Oxford Science Publications, 2002.

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

[Joy86] André Joyal. Foncteurs analytiques et espèces de structures. In Combinatoire énumérative (Montreal, Que., 1985/Quebec, Que., 1985), volume 1234 of Lecture Notes in Math., pages 126–159. Springer, Berlin, 1986.

[Kel72a] G. M. Kelly. An abstract approach to coherence. In Coherence in categories, pages 106–147. Lecture Notes in Math., Vol. 281. Springer, Berlin, 1972.

[Kel72b] G. M. Kelly. Many-variable functorial calculus. I. In Coherence in categories, pages 66–105. Lecture Notes in Math., Vol. 281. Springer, Berlin, 1972.

[Kel82] G. M. Kelly. Structures defined by finite limits in the enriched context. I. Cahiers Topologie Géom. Différentielle, 23(1):3–42, 1982. Third Colloquium on Categories, Part VI (Amiens, 1980).

[Kel92] G. M. Kelly. On clubs and data-type constructors. In Applications of categories in computer science (Durham, 1991), volume 177 of London Math. Soc. Lecture Note Ser., pages 163–190. Cambridge Univ. Press, Cambridge, 1992.

[Kel05] G. M. Kelly. On the operads of J. P. May. Repr. Theory Appl. Categ., (13):1– 13 (electronic), 2005.

[KL97] G. M. Kelly and Stephen Lack. On property-like structures. Theory Appl. Categ., 3(9):213–250, 1997.

[KM95] Igor Kříž and J. P. May. Operads, algebras, modules and motives. Astérisque, (233):iv+145pp, 1995.

[Lac10] Stephen Lack. Icons. Appl. Categ. Structures, 18(3):289–307, 2010. arXiv:0711.4657.

[Lam69] Joachim Lambek. Deductive systems and categories. II. Standard constructions and closed categories. In Category Theory, Homology Theory and their Applications, I (Battelle Institute Conference, Seattle, Wash., 1968, Vol. One), pages 76–122. Springer, Berlin, 1969.

[Lam89] J. Lambek. Multicategories revisited. In Categories in computer science and logic (Boulder, CO, 1987), volume 92 of Contemp. Math., pages 217–239. Amer. Math. Soc., Providence, RI, 1989.

[Law63] F. William Lawvere. Functorial semantics of algebraic theories. Proc. Nat. Acad. Sci. U.S.A., 50:869–872, 1963.

[Law02] F. W. Lawvere. Metric spaces, generalized logic and closed categories. Reprints in Theory and Applications of Categories, 1:1–37, 2002.

[Lei02] Tom Leinster. Generalized enrichment of categories. J. Pure and Applied Algebra, 168:391–406, 2002.

[Lei04] Tom Leinster. Higher operads, higher categories, volume 298 of London Mathematical Society Lecture Note Series. Cambridge University Press, Cambridge, 2004.

[Low88] R. Lowen. Approach Spaces: The Missing Link in the Topology-Uniformity-Metric Triad. Oxford Science Publications, 1988.

[LS02] Stephen Lack and Ross Street. The formal theory of monads. II. J. Pure Appl. Algebra, 175(1-3):243–265, 2002. Special volume celebrating the 70th birthday of Professor Max Kelly.

[May72] J. Peter May. The geometry of iterated loop spaces. Springer-Verlag, Berlin, 1972. Lectures Notes in Mathematics, Vol. 271.

[Mor06] Jeffrey Morton. Categorified algebra and quantum mechanics. Theory Appl. Categ., 16:No. 29, 785–854 (electronic), 2006.

[Pen09] Jacques Penon. T-catégories représentables. Theory Appl. Categ., 22(15):376– 387, 2009.

[Pow99] John Power. Enriched Lawvere theories. Theory Appl. Categ., 6:83–93 (electronic), 1999. The Lambek Festschrift.

[Sea05] Gavin J. Seal. Canonical and op-canonical lax algebras. Theory and Applications of Categories, 14:221–243, 2005.

[Shu08] Michael Shulman. Framed bicategories and monoidal fibrations. Theory and Applications of Categories, 20:650–738, 2008.

[SS08] Christoph Schubert and Gavin J. Seal. Extensions in the theory of lax algebras. Theory Appl. Categ., 21:No. 7, 118–151, 2008.

[Str72a] Ross Street. The formal theory of monads. J. Pure Appl. Algebra, 2(2):149– 168, 1972.

[Str72b] Ross Street. The formal theory of monads. Journal of Pure and Applied Algebra, 2:149–168, 1972.

[Str74] Ross Street. Fibrations and Yoneda’s lemma in a 2-category. In Category Seminar (Proc. Sem., Sydney, 1972/1973), pages 104–133. Lecture Notes in Math., Vol. 420. Springer, Berlin, 1974.

[Str76] Ross Street. Limits indexed by category-valued 2-functors. J. Pure Appl. Algebra, 8(2):149–181, 1976.

[Str80] Ross Street. Fibrations in bicategories. Cahiers Topologie Géom. Différentielle, 21(2):111–160, 1980.

[Str83] Ross Street. Enriched categories and cohomology. In Proceedings of the Symposium on Categorical Algebra and Topology (Cape Town, 1981), volume 6, pages 265–283, 1983. Reprinted as Repr. Theory Appl. Categ. 14:1–18, 2005.

[Tho07] Walter Tholen. Lax-algebraic methods in general topology. Summer School on Contemporary Categorical Methods in Algebra and Topology (course notes), 2007.

[Tho09] Walter Tholen. Ordered topological structures. Topology Appl., 156(12):2148– 2157, 2009.

[Ver92] Dominic Verity. Enriched categories, internal categories, and change of base. Cambridge University (PhD Thesis), 1992.

[Web05] Mark Weber. Operads within monoidal pseudo algebras. Appl. Categ. Structures, 13(5-6):389–420, 2005.

[Web07] Mark Weber. Yoneda structures from 2-toposes. Appl. Categ. Structures, 15(3):259–323, 2007.

[Woo82] R. J. Wood. Abstract proarrows. I. Cahiers Topologie Géom. Différentielle, 23(3):279–290, 1982.

Department of Computer Science, University of Calgary 2500 University Dr. NW, Calgary, Alberta, T2N 1N4 Canada

Department of Mathematics, University of California, San Diego 9500 Gilman Dr #0112, La Jolla, CA, 92023-0112, USA

Email: gscruttw@ucalgary.ca
      mshulman@ucsd.edu

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

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

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

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

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

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

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

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

gavin seal@fastmail.fm

Transmitting editors.

Clemens Berger, Université de Nice-Sophia Antipolis, cberger@math.unice.fr Richard Blute, Université d’ Ottawa: rblute@uottawa.ca Lawrence Breen, Université de Paris 13: breen@math.univ-paris13.fr Ronald Brown, University of North Wales: ronnie.profbrown(at)btinternet.com Aurelio Carboni, Università dell Insubria: aurelio.carboni@uninsubria.it

Valeria de Paiva: valeria.depaiva@gmail.com

Ezra Getzler, Northwestern University: getzler(at)northwestern(dot)edu Martin Hyland, University of Cambridge: M.Hyland@dpmms.cam.ac.uk P. T. Johnstone, University of Cambridge: ptj@dpmms.cam.ac.uk Anders Kock, University of Aarhus: kock@imf.au.dk Stephen Lack, Macquarie University: steve.lack@mq.edu.au F. William Lawvere, State University of New York at Buffalo: wlawvere@buffalo.edu Tom Leinster, University of Glasgow, Tom.Leinster@glasgow.ac.uk Jean-Louis Loday, Université de Strasbourg: loday@math.u-strasbg.fr Ieke Moerdijk, University of Utrecht: moerdijk@math.uu.nl Susan Niefield, Union College: niefiels@union.edu Robert Paré, Dalhousie University: pare@mathstat.dal.ca Jiri Rosicky, Masaryk University: rosicky@math.muni.cz Brooke Shipley, University of Illinois at Chicago: bshipley@math.uic.edu James Stasheff, University of North Carolina: jds@math.unc.edu Ross Street, Macquarie University: street@math.mq.edu.au Walter Tholen, York University: tholen@mathstat.yorku.ca Myles Tierney, Rutgers University: tierney@math.rutgers.edu Robert F. C. Walters, University of Insubria: robert.walters@uninsubria.it R. J. Wood, Dalhousie University: rjwood@mathstat.dal.ca