nLab
multicategory

Contents

The idea

Recall that a category consists of a collection of arrows each having a single object as source or input, and a single object as target or output, together with laws for composition and identity obeying associativity and identity axioms. A multicategory is like a category, except that one allows multiple inputs and a single output.

Thus a multicategory C consists of

  • A collection of objects, C 0.

  • A collection of multimorphisms, C 1.

  • A source map s:C 1(C 0)* to the collection of finite, possibly empty lists of objects (thus (C 0)* is the free monoid generated by C 0), and a target map t:C 1C 0. We write f:c 1,,c nc to indicate the source and target of a multimorphism f.

  • Identity and composition laws. The identity law is a map 1 :C 0C 1 where 1 c:cc. The composition law assigns, to each f:c 1,,c nc together with an n-tuple f i:c ic i:i=1,,n, a composite

    f(f 1,,f n):c 1,,c ncf \circ (f_1, \ldots, f_n): \vec{c}_1, \ldots, \vec{c}_n \to c

    where the source is obtained by concatenating lists in the evident way.

These operations are subject to associativity and identity axioms which the reader can probably figure out, but see for example Tom Leinster’s book, page 35 ff., for details.

Many people (especially non-category theorists) use multicategory to mean what we would call a symmetric multicategory, in which there is also an action of the symmetric group S n on the multimorphisms c 1,,c nc and the composition is equivariant.

Further details and generalizations

An efficient abstract method for defining multicategories and related structures is through the formalism of cartesian monads. For ordinary categories, one uses the identity monad on Set; for ordinary multicategories, one uses the free monoid monad ()*:SetSet. There is a very general notion of T-multicategory, where T is a cartesian monad on a category with pullbacks, which we outline as follows.

  • First, a T-span from X to Y is a span p from TX to Y, that is, a diagram

    TXp 1Pp 2YT X \stackrel{p_1}{\leftarrow} P \stackrel{p_2}{\to} Y

    A T-span is often written as p:XY.

Dang… how do you make an arrow with a vertical slash in the middle? – Todd

I don’t think that has been implemented yet. Here is a list of all available arrows. – Eric

When T is the free monoid monad on Set, a T-span from X to itself is called a multigraph on X.

  • T-spans are the 1-cells of a bicategory. A 2-cell between T-spans e,f:XY is a 2-cell between ordinary spans from TX to Y. To horizontally compose T-spans e:XY and f:YZ, take the ordinary span composite of

    (TXmXT 2XTe 1TETe 2TY)(TYf 1Ff 2Z)(T X \stackrel{m X}{\leftarrow} T^2 X \stackrel{T e_1}{\leftarrow} T E \stackrel{T e_2}{\to} T Y) \circ (T Y \stackrel{f_1}{\leftarrow} F \stackrel{f_2}{\to} Z)

    where m:T 2T is the monad multiplication. The identity T-span from X to itself is the span

    TXuXX1 XXT X \stackrel{u X}{\leftarrow} X \stackrel{1_X}{\to} X

    where u:IT is the monad unit. The verification of the bicategory axioms uses the cartesianness of T in concert with the corresponding axioms on the bicategory of spans.

  • A T-_multicategory_ is defined to be a monad in the bicategory of T-spans.

The full details are carefully treated in Tom Leinster’s book, loc. cit., who gives many illuminating examples.

Connection with operads

A nonpermutative (or Stasheff) operad in Set may be defined as an ordinary multicategory with exactly one object. Likewise, an operad in any symmetric monoidal category V is equivalent to a V-enriched multicategory with one object. Furthermore, for each cartesian monad T, there is a corresponding notion of T-operad, namely a T-multicategory whose underlying T-span has the form 11.

For example, in Batanin’s approach to (weak) -categories, a globular operad? is a T-operad, where T is the free (strict) ω-category monad on the category of globular sets.

With a little care, ordinary (permutative/symmetric) operads may also be treated within this framework. See Tom Leinster’s book for details.

References