# Contents

## Cartesian operads and Lawvere theories

This section explores a circle of ideas involving clones in universal algebra, a cartesian version of operads, Lawvere theories, and algebras or models over such. There is no doubt that all of this material has been known to the cognoscenti for decades (and accurately regarded as folklore), but it seems to be hard to find a convenient place where it is written down.

A subsidiary purpose of this section is to provide an abstract niche in which to show that the forgetful functor from the category of algebras for a Lawvere theory $T$,

$\mathbf{Mod}(T, C) \to C,$

is monadic provided that $C$ is (say) cocomplete and cartesian closed (the only aspect of exponentiation needed is that finite products distribute over colimits); see theorem 3. This addresses a question raised on MathOverflow in reasonably satisfying generality. The development is “soft” and in fact rather tautological, the moves being little more than manipulations based on adjunctions and universal properties. For theorem 3 in particular, there is no need to invoke a technical monadicity theorem; in effect one just writes down the monad and verifies monadicity directly. (True, the development is high-level abstract nonsense, but readers whose taste tends more toward the concrete should encounter no difficulty in verifying the claims.)

### Abstract context for cartesian operads

In what follows, a category with finite products will be called an FP category. A category with finite products and small colimits over which finite products distribute will be called a cartesian monoidally cocomplete (or cmc) category.

###### Proposition

The functor $1 \to Fin^{op}$ that names the one-element set exhibits $FinSet^{op}$ as the free FP category generated by $1$.

In other words, if $C$ and $D$ are FP categories and $\mathbf{Prod}(C, D)$ denotes the category of functors that preserve finite products, then evaluation at the one-element set produces an equivalence

$\mathbf{Prod}(Fin^{op}, D) \stackrel{\sim}{\to} D.$
###### Lemma

For an FP category $C$, the monoidal product on $Set^{C^{op}}$ given by the Day convolution induced from the cartesian monoidal product in $C$ is cartesian monoidal.

###### Proof

We have an evident sequence of isomorphisms

$\array{ (F \otimes G)(c) & = & \int^{a, b} F(a) \times G(b) \times C(c, a \times b) \\ & \cong & \int^{a, b} F(a) \times G(b) \times C(c, a) \times C(b) \\ & \cong & (\int^a F(a) \times C(c, a)) \times (\int^b G(b) \times C(c, b)) \\ & \cong & F(c) \times G(c) }$

where the second line alone uses the cartesian monoidal structure on $C$ (using projection maps, etc.), and the rest uses the usual yoga of Day convolution for symmetric monoidal products and the Yoneda lemma.

###### Proposition

The cartesian monoidal structure on $Set^{Fin}$ is cmc, and the functor $1 \to Set^{Fin}$ that names $I = \hom(1, -): Fin \to Set$ ($I =$ the inclusion functor) exhibits $Set^{Fin}$ as the free cmc category generated by $1$.

Given two cmc categories $C$, $D$, let $[C, D]$ denote the category of finite-product-preserving cocontinuous functors from $C$ to $D$. By the previous proposition we have, for each cmc category $C$, an equivalence

$[Set^{Fin}, C] \stackrel{\sim}{\to} C$

given by evaluation at $I: Fin \to Set$. In particular, taking $C = Set^{Fin}$, we have an equivalence

$Set^{Fin} \simeq [Set^{Fin}, Set^{Fin}]$

so that the monoidal product on the right side given by endofunctor composition transfers across the equivalence to a monoidal product on $Set^{Fin}$. This monoidal product is denoted $\odot$. The monoidal unit is $I$.

###### Definition

A cartesian operad is a monoid in the monoidal category $(Set^{Fin}, \odot, I)$.

### Concrete description of cartesian operads

We give a more concrete description of cartesian operads, beginning with a more concrete description of the equivalences

$C \simeq \mathbf{Prod}(Fin^{op}, C) \simeq [Set^{Fin}, C]$

for a cmc category $C$. The first equivalence takes an object $c$ to the product-preserving functor $\tilde{c}: Fin^{op} \to C: n \mapsto c^n$. This in turn is mapped, by the second equivalence, to the functor $\hat{c}: Set^{Fin} \to C$ that takes a weight $F: Fin \to Set$ to the corresponding weighted colimit of $\tilde{c}$:

$\hat{c}(F) \coloneqq \int^{n \in Fin} F(n) \cdot \tilde{c}(n) = \int^{n \in Fin} F(n) \cdot c^n.$

Of course, the inverse equivalence $[Set^{Fin}, C] \to C$ just the evaluation at the object $I = \hom(1, -)$ of $Set^{Fin}$.

We thus have a formula for the monoidal product $\odot$ on $Set^{Fin}$:

$F \odot G = \int^{n \in Fin} F(n) \cdot G^n.$

• A functor $M: Fin \to Set$,

• A natural transformation $u: I \to M$,

• A natural transformation $m: M \odot M \to M$

satisfying monoid axioms. By the Yoneda lemma, the unit $u$ is given by an element $e \in M(1)$. The multiplication $m$ consists of a natural transformation

$\int^n M(n) \cdot M^n \to M$

which in turn consists of maps

$m_{n, k}: M(n) \times M(k)^n \to M(k)$

natural in the argument “$k$” (for $k$-element sets) and dinatural in $n$.

The maps $m_{n, k}$ take on a more operad-like appearance if we take advantage of cartesian structure: if $k = k_1 + \ldots + k_n$ is a coproduct decomposition in $Fin$ (dual to a product decomposition in $Fin^{op}$), with summand inclusion maps denoted $i_j: k_j \to k$ (dual to projection maps; cf. the proof of lemma 1), then we have composites

$M(n) \times M(k_1) \times \ldots \times M(k_n) \stackrel{1 \times M(i_1) \times \ldots \times M(i_n)}{\to} M(n) \times M(k) \times \ldots \times M(k) = M(n) \times M(k)^n \stackrel{m_{n, k}}{\to} M(k),$

that is to say, maps

$M(n) \times M(k_1) \times \ldots \times M(k_n) \to M(k_1 + \ldots + k_n);$

this makes the connection with operads clear.

In the literature on universal algebra, the usual term for a cartesian operad is “clone” (or rather, one usually speaks of the clone of an algebraic theory, which we are repackaging here as a cartesian operad). The following is taken from Gould, definition 1.2.1,

###### Definition

A clone consists of

• A sequence of sets $M(0), M(1), M(2), \ldots$;

• For every $n, k \in \mathbb{N}$, a function $\bullet = \bullet_{n, k} \colon M(n) \times M(k)^n \to M(k)$;

• For each $n \in \mathbb{N}$, elements $\pi_{1, n}, \ldots, \pi_{n, n} \in M(n)$

such that

• For $f \in M(i)$, $g_1, \ldots, g_i \in M(j)$, and $h_1, \ldots, h_j \in M(k)$,

$f \bullet (g_1 \bullet (h_1, \ldots, h_j), \ldots, g_i \bullet (h_1, \ldots, h_j)) = (f \bullet (g_1, \ldots, g_i)) \bullet (h_1, \ldots, h_j);$
• For $f_1, \ldots, f_n \in M(k)$,

$\pi_{i, n} \bullet (f_1, \ldots, f_n) = f_i;$
• For $f \in M(n)$,

$f \bullet (\pi_{1, n}, \ldots, \pi_{n, n}) = f.$

To extract a functor $M: Fin \to Set$ from such data, define $M(f): M(m) \to M(n)$, for a function $f: \{1, \ldots, m\} \to \{1, 2, \ldots, n\}$ between finite sets, by the formula

$M(f)(\phi) \coloneqq \phi \bullet (\pi_{f(1), n}, \ldots, \pi_{f(m), n}).$

The unit $e \in M(1)$ is given by $\pi_{1, 1}$. It is not hard to verify that under these definitions, $M$ is functorial and $m: M \odot M \to M$ (as assembled from the maps $m_{n, k} = \bullet_{n, k}$) is natural. The first equation in the definition of clone expresses the associativity of $m$.

Each cartesian operad $(M: Fin \to Set, u: I \to M, m: M \odot M \to M)$ induces a monad on any cmc category $C$, as follows. By definition of cartesian operad, we have an induced monad

$(-) \odot M: Set^{Fin} \to Set^{Fin}$

that is cocontinuous and preserves finite products. It follows that we have a an induced monad

$[Set^{Fin}, C] \stackrel{\; \; \; [(-) \odot M, 1_C]\; \; \; }{\to} [Set^{Fin}, C]$

which may be transferred across the equivalence $C \simeq [Set^{Fin}, C]$ to give a monad $M_C$ on $C$. Following the constructions above, $M_C$ sends an object $c$ to the object named by the composite

$1 \stackrel{I}{\to} Set^{Fin} \stackrel{\; (-) \odot M\; }{\to} Set^{Fin} \stackrel{\hat{c}}{\to} C$

which boils down to the weighted colimit

$\int^{n \in Fin} M(n) \cdot c^n.$
###### Definition

An $M$-algebra in $C$ is an algebra over the monad $M_C$.

If $C$ is an FP category and $c$ is an object of $C$, there is a tautological cartesian operad attached to $c$, familiarly known as an “endomorphism operad”. Concretely, this is the functor $Fin \to Set$ whose value at $n \in Ob(Fin)$ is

$Endo_c(n) \coloneqq \hom_C(c^n, c)$

and where the operadic multiplication maps

$Endo_c(n) \times Endo_c(m)^n \to Endo_c(m)$

are given intuitively by substituting or plugging in $n$ $m$-ary operations $f_1, \ldots, f_n: c^m \to c$ into an $n$-ary function $f: c^n \to c$, to produce an $m$-ary operation. More formally, one forms the composite

$c^m \stackrel{\; \; \langle f_1, \ldots, f_n \rangle \; \; }{\to} c^n \stackrel{f}{\to} c.$

It is not difficult to calculate that this does indeed give a cartesian operad. It’s even easier to just believe this without even bothering to calculate! (From a logical standpoint, one could argue that since this is just an assertion of equational or FP logic, it suffices to verify the claim just in the case $C = Set$, since we can invoke the Yoneda embedding [which preserves and reflects FP logic] and then just argue pointwise. And of course everyone and his uncle knows it’s true in the case $C = Set$.)

However, these facts can also be cleanly deduced on abstract grounds. Each object $c$ of a cmc category $C$ corresponds to a cocontinuous product-preserving map

$\hat{c}: Set^{Fin} \to C$

which is left adjoint to the functor $C \to Set^{Fin}$ obtained by “currying” the functor

$Fin \times C \stackrel{\; \; \hom(\tilde{c}(-), -)}{\to} Set.$

This observation is very old, going back to the 1958 paper Kan. It applies equally well if we replace $C$ by the cmc category $Set^{C^{op}}$ (where we now need only that $C$ is a finite-product category) and replace $c$ by the hom-functor $C(-, c)$. For in that case, it follows easily from the Yoneda lemma that the curryed (curried?) functor is nothing but

$Set^{\tilde{c}^{op}} \colon Set^{C^{op}} \to Set^{Fin}$

(note this is well-defined – and no need to worry over the fact that $Set^{C^{op}}$ is not locally small; we just need $C$ to be locally small to apply the Yoneda lemma).

In other words, we have an adjoint pair

$(\widehat{C(-, c)}: Set^{Fin} \to Set^{C^{op}}) \; \dashv \; (Set^{\tilde{c}^{op}}: Set^{C^{op}} \to Set^{Fin})$

where both the left and right adjoint are manifestly (small-)cocontinuous and finite-product-preserving. Their composite yields a monad, i.e., a monoid in the endofunctor category $[Set^{Fin}, Set^{Fin}]$ of cocontinuous, product-preserving functors. This in turn gives a cartesian operad

$Set^{\tilde{c}^{op}} \circ C(-, c) = C(\tilde{c}, c): Fin \to Set,$

and it is nothing but the endomorphism operad attached to $c$ (we could take it as the abstract definition of the endomorphism operad).

### Morphisms to the endomorphism operad

###### Theorem

Let $C$ be a cmc category, and let $M$ be a cartesian operad. Then algebra structures $\xi: M_C(c) \to c$ over the monad $M_C$ are in canonical bijection with morphisms of cartesian operads $M \to Endo_c$.

Once again, this result is entirely expected for anyone familiar with ordinary operad theory. Roughly speaking, an $M_C$-algebra structure $\xi: M_C(c) \to c$ is given by a collection of maps

$M(n) \cdot c^n \to c$

which corresponds to a collection of morphisms

$\phi_n: M(n) \to \hom(c^n, c) = Endo_c(n)$

and the claim is that the conditions that $\xi$ be an algebra structure correspond exactly to the conditions that the $\phi_n$ constitute a morphism of cartesian operads.

This follows from a routine but slightly tedious calculation, or from a more abstract argument which we now give. According to our abstract definition of the endomorphism operad, a morphism $M \to Endo_c$ of cartesian operads corresponds exactly to a morphism of monoids in $Set^{Fin}, Set^{Fin}]$,

$(-) \odot M \to Set^{\tilde{c}^{op}} \circ \widehat{C(-, c)},$

or in other words a morphism of monads $- \odot M \to U F$ (where $U$ here denotes the right adjoint $Set^{\tilde{c}^{op}}$ and $F$ the left adjoint $\widehat{\hom(-, c)}$).

Generally speaking, there are a couple of equivalent ways of viewing a morphism of monads $T \to U F$:

• As a left action $T U \to U$, or

• As a right action $F T \to F$

where “action” has the usual meaning (involving a unit axiom and an associativity axiom). This is another very old observation, going back in this case to the 1965 paper of Eilenberg and Moore. If we choose the right action, then in the case at hand we are led to a natural transformation of the form

$\array{ Set^{Fin} & \stackrel{\; \; (-) \odot M \; \; }{\to} & Set^{Fin} \\ & _\mathllap{\widehat{C(-, c)}} \searrow ^\mathrlap{\swArrow} & \downarrow _\mathrlap{\widehat{C(-, c)}} \\ & & Set^{C^{op}} }$

i.e., a transformation

$\int^n M(n) \cdot C(-, c)^n \to C(-, c)$

satisfying action axioms.

### Cartesian operads are equivalent to Lawvere theories

###### Definition

Let $M$ be a cartesian operad. The prop of $M$ is the category $\mathbf{Prop}(M)$ whose objects are natural numbers $0, 1, 2, \ldots$ and whose hom-sets are defined by the formula

$\mathbf{Prop}(M)(n, m) = M(n)^m$

The unit $1_n: 1 \to M(n)^n$ is given by the $n$-tuple

$\langle M(i_1)(e), \ldots, M(i_n)(e) \rangle$

where $i_j: 1 \to n$ in $Fin$ names the element $j \in \{1, \ldots, n\}$. The composition

$M(m)^k \times M(n)^m \to M(n)^k$

takes a pair $(f_1, \ldots, f_k) \in M(m)^k$, $(g_1, \ldots, g_m) \in M(n)^m$ to the element $(h_j)_{1 \leq j \leq k} \in M(n)^k$ given by

$h_j = f_j \bullet (g_1, \ldots, g_m).$
###### Proposition

$\mathbf{Prop}(M)$ has finite products, where the product of two objects $m, n$ is $m+n$, where the product projections $\pi_m: m+n \to m$, $\pi_n: m+n \to n$ are defined by

$\pi_m = (M(i_1)(e), \ldots, M(i_m)(e)) \in M(m+n)^m, \qquad \pi_n = (M(i_{m+1})(e), \ldots, M(i_{m+n})(e)) \in M(m+n)^n.$

With this structure, $\mathbf{Prop}(M)$ is a Lawvere theory.

###### Example

For the endomorphism operad $Endo_c$ of a finite-product category, the homs of $\mathbf{Prop}(Endo_c)$ are given by $\hom(n, m) = C(c^n, c^m)$, with compositions given by composition in $C$.

###### Theorem

There is an equivalence between the category of cartesian operads and the category of Lawvere theories,

$CartOp \to LawTh,$

taking a cartesian operad $M$ to $\mathbf{Prop}(M)$.

For the inverse equivalence $LawTh \to CartOp$: if $T$ is a Lawvere theory (with product-preserving map $i: Fin^{op} \to T$ on the category of finite cardinals and functions giving an isomorphism between object sets), we get a functor $\hom_T(i(-), 1): Fin \to Set$ which carries a structure of cartesian operad, which we will denote as $\mathbf{Op}(T)$.

Under the identification of cartesian operads with clones, this theorem is well-known and goes back to Lawvere’s thesis. See for instance theorem 1.5.5 of Gould.

### Categories of algebras over a cmc category

Let $C$ be a cmc category, and let $T$ be a Lawvere theory. The cartesian operad $\mathbf{Op}(T)$ induces a monad $M$ on $C$, as in definition 3. The category of models of $T$ is by definition the category of product-preserving functors

$Mod(T, C) = \mathbf{Prod}(T, C).$
###### Theorem

The forgetful functor $Mod(T, C) = \mathbf{Prod}(T, C) \to C$ obtained by evaluating at $1 \in Ob(T)$ is monadic, via an equivalence $Mod(T, C) \simeq M$-$Alg$.

###### Proof overview

Using the development above, we have equivalences between

• Product-preserving functors $T \to C$ with underlying object $c$;

• Morphisms of Lawvere theories $T \to \mathbf{Prop}(Endo_c)$;

• Morphisms of cartesian operads $\mathbf{Op}(T) \to Endo_c$ (theorem 2);

• Algebra structures $M(c) \to c$ of the monad $M: C \to C$ induced from $\mathbf{Op}(T)$ (theorem 1).

It is straightforward to check that transformations $\phi$ between product preserving functors $T \to C$, uniquely induced from the component at $1 \in Ob(T)$ given by a map $f = \phi_1: c \to d$ in $C$, correspond precisely to such $f: c \to d$ that are $M$-algebra maps.

## Sketch of a general theory of operads

The development given above for cartesian operads can be carried out analogously for other sorts of operads, perhaps along the following lines.

Let $D: Cat \to Cat$ be a 2-monad on the 2-category of locally small categories lying over the 2-monad $Mon$ whose pseudo-algebras are monoidal categories, so that there is a given 2-monad morphism $j: Mon \to D$. We probably want to assume $D$ is a strict 2-monad and $j$ is a strict 2-monad morphism, even though we will deal with pseudo-algebras over such. Possibly we also want to assume that $j$ is essentially surjective on objects and even an isomorphism on objects (although that could be considered “evil”), or better, that $j$ is eso and faithful. (Cf. ternary factorization systems on $Cat$.) Roughly speaking, this would mean that the only type constructor on $D$ is given by a binary symbol $\otimes$, representing a monoidal product, but the monoidal product can be enhanced by other structural data.

We will also suppose that $D$ comes equipped with a distributive law

$\theta: D P \to P D$

that is compatible with the usual distributive law $Mon P \to P Mon$ on which Day convolution is based. With the distributive law $\theta$, which we could view as an enhanced Day convolution, we get an accompanying 2-monad structure on $P D$.

Examples of such $D$ include

• The doctrine of symmetric monoidal categories,

• The doctrine of braided monoidal categories,

• The doctrine of cartesian monoidal categories,

• The doctrine of affine monoidal categories,

to name just a few.

### $D$-operads

Under our assumptions, the free $P D$-algebra on one generator is $P D(1) = Set^{D(1)^{op}}$, and for any $P D$-algebra $C$ there is an equivalence

$[Set^{D(1)^{op}}, C] \stackrel{\sim}{\to} C$

where $[C, E]$ denotes the category of $P D$-algebra maps. In particular, for $C = Set^{D(1)^{op}}$, we have an equivalence

$[Set^{D(1)^{op}}, Set^{D(1)^{op}}] \simeq Set^{D(1)^{op}}$

so that the monoidal structure on the left given by endofunctor composition may be transferred across the equivalence to give a monoidal category structure on $Set^{D(1)^{op}}$, playing the role of plethysm appropriate to the doctrine $D$. The monoidal product will be denoted $\odot_D$, and the monoidal unit $I_D$; here $I_D = \hom(-, i(1)): D(1)^{op} \to Set$ where $i: 1 \to D(1)$ is the generator.

###### Definition

A $D$-operad is a monoid in the monoidal category $(Set^{D(1)^{op}}, \odot_D, I_D)$.

### Towards an explicit description of $D$-operads

The objects of $D(1)$ may be considered as abstract arities. If $C$ is a $D$-algebra and $c$ is an object of $C$, then it may be suggestive to write $c^a$ for the value of an arity $a \in Ob(D(1))$ under the unique $D$-algebra map $D(1) \to C$ carrying the generator $1 \to D(1)$ to $c$. Then we have a coend formula for the $D$-plethysm product of two $D$-species $F, G: D(1)^{op} \to Set$:

$F \odot_D G = \int^{a \in D(1)} F(a) \cdot G^a$

and accordingly one can write out a relatively “concrete” description of the structure of a $D$-operad.

Of course $D(1)$ has an underlying monoidal category (by pulling back the $D$-algebra structure along $j: Mon \to D$), so that arities may be tensored; it is suggestive to write $a + b$ for the monoidal product of arities $a, b$.

If $M$ is a $D$-operad, then the $P D$-algebra map

$(-) \odot_D M: Set^{D(1)^{op}} \to Set^{D(1)^{op}}$

carries a monad structure, and it follows that for any $P D$-algebra $C$

## References

• Miles Gould, Coherence for categorified operadic theories, PhD thesis, University of Glasgow, 2008. (link)
• Daniel Kan, Functors involving c.s.s. complexes, Transactions of the American Mathematical Society, Vol. 87, No. 2 (March 1958), pp. 330–346.
• Samuel Eilenberg and John C. Moore, Adjoint functors and triples, Illinois J. Math. Volume 9, Issue 3 (1965), 381-398. (web)
• F. William Lawvere, Functorial semantics of algebraic theories, PhD thesis, Columbia University, 1963. (web)
• Martin Brandenburg (mathoverflow.net/users/2841), Free cocommutative commutative Hopf monoids, http://mathoverflow.net/questions/118998 (version: 2013-01-15). (link)
Revised on April 27, 2013 00:36:53 by Todd Trimble