## May 12, 2017

### Unboxing Algebraic Theories of Generalised Arities

#### Posted by Emily Riehl

Guest post by José Siqueira

We began our journey in the second Kan Extension Seminar with a discussion of the classical concept of Lawvere theory , facilitated by Evangelia. Together with the concept of a model, this technology allows one to encapsulate the behaviour of algebraic structures defined by collections of $n$-ary operations subject to axioms (such as the ever-popular groups and rings) in a functorial setting, with the added flexibility of easily transferring such structures to arbitrary underlying categories $\mathcal{C}$ with finite products (rather than sticking with $\mathbf{Set}$), naturally leading to important notions such as that of a Lie group.

Throughout the seminar, many features of Lawvere theories and connections to other concepts were unearthed and natural questions were addressed — notably for today’s post, we have established a correspondence between Lawvere theories and finitary monads in $\mathbf{Set}$ and discussed the notion of operad, how things go in the enriched context and what changes if you tweak the definitions to allow for more general kinds of limit. We now conclude this iteration of the seminar by bringing to the table “Monads with arities and their associated theories”, by Clemens Berger, Paul-André Melliès and Mark Weber, which answers the (perhaps last) definitional “what-if”: what goes on if you allow for operations of more general arities.

At this point I would like to thank Alexander Campbell, Brendan Fong and Emily Riehl for the amazing organization and support of this seminar, as well as my fellow colleagues, whose posts, presentations and comments drafted a more user-friendly map to traverse this subject.

#### 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.

Posted at May 12, 2017 4:38 AM UTC

TrackBack URL for this Entry:   https://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/2964

### Re: Unboxing Algebraic Theories of Generalised Arities

Bravo! I don’t think I’d realized, even in the classical case of a finitary monad $T$ on the category of sets, that the (co)Lawvere theory $\Theta_T$ sitting inside the category of algebras (the full subcategory spanned by the free algebras on finite sets) was a dense generator. In retrospect, it’s not surprising, but still I’m grateful to have this clean slogan to recall.

Posted by: Emily Riehl on May 12, 2017 4:39 PM | Permalink | Reply to this

### Re: Unboxing Algebraic Theories of Generalised Arities

Me neither! It seems people always mention that the free algebra on a single generator is generally not dense, even in the case of abelian groups, where instead the free abelian group of rank two is dense. I vaguely feel that it’s supposed to be true that the free algebra on $n$ generators is dense in the algebras for a theory generated by operations of arity at most $n$. If that’s true, then it would give a reason why the result about all finitely generated free algebras is a bit esoteric-there would always be a much smaller dense generator, except for theories requiring operations of unbounded finite arities. How common are such theories, anyway?

Posted by: Kevin Carlson on May 13, 2017 5:44 AM | Permalink | Reply to this

Post a New Comment