The n-Category Café

Allowing general arities

Recall that a Lawvere theory can be defined as a pair $(I,L)$, where $L$ is a small category with finite coproducts and $I: \aleph_0 \to L$ is an identity-on-objects finite-coproduct preserving functor. To this data we associate a nerve functor $\nu_{\aleph_0}: \mathbf{Set} \to PSh(\aleph_0)$, which takes a set $X$ to its $\aleph_0$-nerve $\nu_{\aleph_0}(X): \aleph_0^{op} \to \mathbf{Set}$, the presheaf $\mathbf{Set}(i_{\aleph_0}(-), X)$ — the $\aleph_0$-nerve of a set $X$ thus takes a finite cardinal $n$ to $X^n$, up to isomorphism. It is easy to check $\nu_{\aleph_0}$ is faithful, but it is also full, with $\alpha\cong \nu_{\aleph_0}(\alpha_1)$ for each natural transformation $\alpha: \nu_{\aleph_0}(X) \to \nu_{\aleph_0}(X')$, seeing $\alpha_1$ as a function $X \to X'$. This allows us to regard sets as presheaves over the small category $\aleph_0$, and as $\nu_{\aleph_0}(X)([n])=\mathbf{Set}([n],X)\cong X^n$, the $\aleph_0$-nerves can be used to encode all possible $n$-ary operations on sets. To capture this behaviour of $\aleph_0$, we are inclined to make the following definition:

Definition. Let $\mathcal{C}$ be a category and $\mathcal{A}$ be a full small subcategory of $\mathcal{C}$. We say $\mathcal{A}$ is a dense generator of $\mathcal{C}$ if its associated nerve functor $\nu_{\mathcal{A}}: \mathcal{C} \to PSh(\mathcal{A})$ is fully faithful, where $\nu_{\mathcal{A}}(X)= \mathcal{C}(\imath_{\mathcal{A}}(-), X)$ for each $X \in \mathcal{C}$.

The idea is that we can replace $\mathbf{Set}$ and $\aleph_0$ in the original definition of Lawvere theory by a category $\mathcal{C}$ with a dense generator $\mathcal{A}$. This allows us to have operations with arities more diverse than simply finite cardinals, while still retaining “good behaviour” — if we think about the dense generator as giving the “allowed arities”, we end up being able to extend all the previous concepts and make the following analogies:

$$\array {\arrayopts{ \colalign{left left} \rowlines{solid} } \\ \text{Lawvere theory}\, L &\text{Theory}\, \Theta \, \text{with arity} \, \mathcal{A}\\ \text{Model of}\, L^{op}& \Theta\text{-model}\\ \text{Finitary monad}&\text{Monad with arity}\, \mathcal{A}\\ \text{Globular (Batanin) operad}&\text{Homogenous globular theory}\\ \text{Symmetric operad}&\Gamma\text{-homogeneous theory}\\  &   }$$ We’ll now discuss each generalised concept and important/useful properties.

If $(I,L)$ is a Lawvere theory, the restriction functor $I^{\ast}: PSh(L) \to PSh(\aleph_0)$ induces a monad $I^{\ast} I_!$, where $I_!$ is left Kan extension along $I$. This monad preserves the essential image of the nerve functor $\nu_{\aleph_0}$, and in fact this condition reduces to preservation of coproducts by $I$ (refer to 3.5 in the paper for further details). If $M$ is a model of $L^{op}$ on $\mathbf{Set}$ in the usual sense (i.e $M: L^{op} \to \mathbf{Set}$ preserves finite products) we can see that its restriction along $I$ is isomorphic to the $\aleph_0$-nerve of $MI([1])$ by arguing that

$$(I^{\ast} M)[n] = MI[n] = M \underbrace{(\coprod_n I[1])}_{\text{in} \, L} = M\underbrace{(\prod_n I[1])}_{\text{in}\, L^{op}}\cong \prod_n MI[1] \cong MI[1]^n \cong \nu_{\aleph_0}(MI[1])[n],$$

and so we may want to define:

Definition. Let $\mathcal{C}$ be a category with a dense generator $\mathcal{A}$. A theory with arities $\mathcal{A}$ on $\mathcal{C}$ is a pair $(\Theta,j)$, where $j: \mathcal{A} \to \Theta$ is a bijective-on-objects functor such that the induced monad $j^{\ast}j_!$ on $PSh(\mathcal{A})$ preserves the essential image of the associated nerve functor $\nu_{\mathcal{A}}$. A $\Theta$-model is a presheaf on $\Theta$ whose restriction along $j$ is isomorphic to some $\mathcal{A}$-nerve.

Again, for $\mathcal{A}=\aleph_0$, this requirement on models says a $\Theta$-model $M$ restricts to powers of some object: $I^\ast M(-)=MI(-) \cong X^{|-|}$ for some set $X$, the outcome we wanted for models of Lawvere theories.

A morphism of models is still just a natural transformation between them as presheaves and a morphism of theories $(\Theta_1, j_1) \to (\Theta_2, j_2)$ is a functor $\theta: \Theta_1 \to \Theta_2$ that intertwines with the arity functors, i.e $j_2=\theta j_1$. We’ll write $Mod(\Theta)$ for the full subcategory of $PSh(\Theta)$ consisting of the models of $\Theta$ and $Th(\mathcal{C}, \mathcal{A})$ for the category of theories with arities $\mathcal{A}$ on $\mathcal{C}$. We aim to prove a result that establishes an equivalence between $Th(\mathcal{C},\mathcal{A})$ and some category of monads, to mirror the situation between Lawvere theories and finitary monads on $\mathbf{Set}$.

Dense generators and nerves

Having a dense generator is desirable because we can then mimic the following situation:

Recall that if $\mathcal{D}$ is small and $F:\mathcal{D} \to \mathbf{Set}$ is a functor, then we can form a diagram of shape $({\ast}\downarrow F)^{op}$ over $[\mathcal{D}, \mathbf{Set}]$ by composing the (opposite) of the natural projection functor $({\ast}\downarrow F) \to \mathcal{D}$ and the Yoneda embedding. We may then consider the cocone

$$\mu=(\mu_{(d,x)}=\mu_x: \mathcal{D}(d,-) \to F \mid (d,x) \in ({\ast} \downarrow F)^{op}),$$

where $\mu_x$ is the natural transformation corresponding to $x \in F(d)$ via the Yoneda lemma, and find out it is actually a colimit, canonically expressing $F$ as a colimit of representable functors — if you are so inclined, you might want to look at this as the coend identity

$$F(-)= \int^{d \in \mathcal{D}} F(d) \times \mathcal{D}(-,d)$$

when $F$ is a presheaf on $\mathcal{D}$. Likewise for $X$ an object of a category $\mathcal{C}$ with dense generator $\mathcal{A}$, there is an associated diagram $a_X: \mathcal{A}/X \to \mathcal{C}$, which comes equipped with an obvious natural transformation to the constant functor on $X$, whose $(A \xrightarrow{f} X)$-component is simply $f$ itself — this is called the $\mathcal{A}$-cocone over $X$, and it is just the cocone of vertex $X$ under the diagram $a_X$ of shape $\mathcal{A}/X$ in $\mathcal{C}$ whose legs consist of all morphisms $A \to X$ with $A \in \mathcal{A}$. Note that if $\mathcal{A}$ is small (as is the case), then this diagram is small and, if $\mathcal{C}=PSh(\mathcal{A})$, the slice category $\mathcal{A}/X$ reduces to the category of elements of the presheaf $X$ and this construction gives the Yoneda cocone under $X$. One can show that

Proposition. A small full subcategory $\mathcal{A}$ of $\mathcal{C}$ is a dense generator precisely when the $\mathcal{A}$-cocones are actually colimit-cocones in $\mathcal{C}$.

This canonically makes every object $X$ of $\mathcal{C}$ a colimit of objects in $\mathcal{A}$ , and in view of this result it makes sense to define:

Definition. Let $\mathcal{C}$ be a category with a dense generator $\mathcal{A}$. A monad $T$ on $\mathcal{C}$ is a monad with arities $\mathcal{A}$ when $\nu_{\mathcal{A}}T$ takes the $\mathcal{A}$-cocones of $\mathcal{C}$ to colimit-cocones in $PSh(\mathcal{A})$.

That is, the monad has arities $\mathcal{A}$ whenever scrambling the nerve functor by first applying $T$ does not undermine its capacity of turning $\mathcal{A}$-cocones into colimits, which in turns preserves the status of $\mathcal{A}$ as a dense generator, morally speaking — the Nerve Theorem makes this statement more precise:

The Nerve Theorem. Let $\mathcal{C}$ be a category with a dense generator $\mathcal{A}$. For any monad $T$ with arities $\mathcal{A}$, the full subcategory $\Theta_T$ spanned by the free $T$-algebras on objects of $\mathcal{A}$ is a dense generator of the Eilenberg-Moore category $\mathcal{C}^T$. The essential image of the associated nerve functor is spanned by those presheaves whose restriction along $j_T$ belongs to the essential image of the $\nu_{\mathcal{A}}$, where $j_T: \mathcal{A} \to \Theta_T$ is obtained by restricting the free $T$-algebra functor.

The proof given relies on an equivalent characterization for monads with arities, namely that a monad $T$ on a category $\mathcal{C}$ with arities $\mathcal{A}$ is a monad with arities $\mathcal{A}$ if and only if the “generalised lifting (pseudocommutative) diagram”

$$\begin{matrix} \mathcal{C}^T & \overset{\nu_T}{\longrightarrow} & PSh(\Theta_T) \\ {}_{U}\downarrow && \downarrow_{j_T^{\ast}} \\ \mathcal{C} & \underset{\nu_{\mathcal{A}}}{\longrightarrow} & PSh(\mathcal{A}) \\ \end{matrix}.$$

is an exact adjoint square, meaning the mate $(j_T)_!\nu_{\mathcal{A}} \Rightarrow \nu_T F$ of the invertible $2$-cell implicit in the above square is also invertible, where $F$ is the free $T$-algebra functor. Note $j_T^{\ast}$ is monadic, so this diagram indeed gives some sort of lifting of the nerve functor on $\mathcal{C}$ to the level of monad algebras.

We can build on this result a little bit. Let $\alpha$ be a regular cardinal (at this point you might want to check David’s discussion on finite presentability).

Definition. A category $\mathcal{C}$ is $\alpha$-accessible if it has $\alpha$-filtered colimits and a dense generator $\mathcal{A}$ comprised only of $\alpha$-presentable objects such that $\mathcal{A}/X$ is $\alpha$-filtered for each object $X$ of $\mathcal{C}$. If in addition the category is cocomplete, we say it is locally $\alpha$-presentable.

If $\mathcal{C}$ is $\alpha$-accessible, there is a god-given choice of dense generator — we take $\mathcal{A}$ to be a skeleton of the full subcategory $\mathcal{C}(\alpha)$ spanned by the $\alpha$-presentable objects of $\mathcal{C}$. As all objects in $\mathcal{A}$ are $\alpha$-presentable, the associated nerve functor preserves $\alpha$-filtered colimits and so any monad $T$ preserving $\alpha$-filtered colimits is a monad with arities $\mathcal{A}$. The essential image of $\nu_{\mathcal{A}}$ is spanned by the $\alpha$-flat presheaves on $\mathcal{A}$ (meaning presheaves whose categories of elements are $\alpha$-filtered). As a consequence, any given object in an $\alpha$-accessible category is canonically an $\alpha$-filtered colimit of $\alpha$-presentable objects and we can prove:

Theorem (Gabriel-Ulmer, Adámek-Rosický). If a monad $T$ on an $\alpha$-accessible category $\mathcal{C}$ preserves $\alpha$-filtered colimits, then its category of algebras $\mathcal{C}^T$ is $\alpha$-accessible, with a dense generator $\Theta_T$ spanned by the free $T$-algebras on (a skeleton $\mathcal{A}$ of) the $\alpha$-presentable objects $C(\alpha)$. Moreover, this category of algebras is equivalent to the full subcategory of $PSh(\Theta_T)$ spanned by those presheaves whose restriction along $j_T$ is $\alpha$-flat.

Proof. We know $T$ is a monad with arities $\mathcal{A}$. That $\Theta_T$ is a dense generator as stated follows from its definition and the Nerve Theorem. Now, $\mathcal{C}^T$ has $\alpha$-filtered colimits since $\mathcal{C}$ has and $T$ preserves them. As the forgetful functor $U: \mathcal{C}^T \to \mathcal{C}$ preserves $\alpha$-filtered colimits (a monadic functor creates all colimits $\mathcal{C}$ has and $T$ preserves), it follows that the free algebra functor preserves $\alpha$-presentability: $\mathcal{C}(FA,-) \cong \mathcal{C}(A, U(-))$ preserves $\alpha$-filtered colimits whenever $A$ is $\alpha$-presentable, and so objects of $\Theta_T$ are $\alpha$-presentable. One can then check each $\mathcal{A}/X$ is $\alpha$-filtered. $\square$

Note that this theorem says, for $\alpha=\aleph_0$, that if a monad on sets is finitary, then its category of algebras (i.e models for the associated classical Lawvere theory) is accessible, with a dense generator given by all the free $T$-algebras on finite sets: this is because a finitely-presentable (i.e $\aleph_0$-presentable) set is precisely the same as a finite set. As a consequence, the typical “algebraic gadgets” are canonically a colimit of free ones on finitely many generators.

Theories and monads (with arities) are equivalent

If $T$ is a monad with arities $\mathcal{A}$, then $(\Theta_T, j_T)$ is a theory with arities $\mathcal{A}$. The Nerve Theorem then guarantees that $\nu_T: \mathcal{C}^T \to PSh(\Theta_T)$ induces an equivalence of categories between $\Theta_T$-models and $T$-algebras, since its essential image is, by definition, the category of $\Theta_T$-models and the functor is fully faithful. This gives us hope that the situation with Lawvere theories and finitary monads can be extended, and this is indeed the case: the assignment $T \mapsto (\Theta_T, j_T)$ extends to a functor $\mathbf{Mnd}(\mathcal{C}, \mathcal{A}) \to \mathbf{Th}(\mathcal{C}, \mathcal{A})$, which forms an equivalence of categories together with the functor $\mathbf{Th}(\mathcal{C}, \mathcal{A}) \to \mathbf{Mnd}(\mathcal{C}, \mathcal{A})$ that takes a theory $(\Theta, j)$ to the monad $\rho_{\mathcal{A}}T\nu_{\mathcal{A}}$ with arities $\mathcal{A}$, where $\rho_{\mathcal{A}}$ is a choice of right adjoint to $\nu_{\mathcal{A}}: \mathcal{C} \to EssIm(\nu_{\mathcal{A}})$. When $\mathcal{C}=\mathbf{Set}$ and $\mathcal{A}=\aleph_0$, we recover the Lawvere theory/finitary monad equivalence.

Relation to operads and examples

Certain kinds of theories with arities are equivalent to operads. Namely, there is a notion of homogeneous globular theory that corresponds to globular (Batanin) operads. Similarly, there is a notion of $\Gamma$-homogeneous theory that corresponds to symmetric operads. The remainder of the paper brings other equivalent definitions for monad with arities and builds a couple of examples, such as the free groupoid monad, which is a monad with arities given by (finite, connected) acyclic graphs. A notable example is that dagger categories arise as models of a theory on involutive graphs with non-trivial arities.