Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

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 nn-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 Set\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 Set\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)(I,L), where LL is a small category with finite coproducts and I: 0LI: \aleph_0 \to L is an identity-on-objects finite-coproduct preserving functor. To this data we associate a nerve functor ν 0:SetPSh( 0)\nu_{\aleph_0}: \mathbf{Set} \to PSh(\aleph_0), which takes a set XX to its 0\aleph_0-nerve ν 0(X): 0 opSet\nu_{\aleph_0}(X): \aleph_0^{op} \to \mathbf{Set}, the presheaf Set(i 0(),X)\mathbf{Set}(i_{\aleph_0}(-), X) — the 0\aleph_0-nerve of a set XX thus takes a finite cardinal nn to X nX^n, up to isomorphism. It is easy to check ν 0\nu_{\aleph_0} is faithful, but it is also full, with αν 0(α 1)\alpha\cong \nu_{\aleph_0}(\alpha_1) for each natural transformation α:ν 0(X)ν 0(X)\alpha: \nu_{\aleph_0}(X) \to \nu_{\aleph_0}(X'), seeing α 1\alpha_1 as a function XXX \to X'. This allows us to regard sets as presheaves over the small category 0\aleph_0, and as ν 0(X)([n])=Set([n],X)X n\nu_{\aleph_0}(X)([n])=\mathbf{Set}([n],X)\cong X^n, the 0\aleph_0-nerves can be used to encode all possible nn-ary operations on sets. To capture this behaviour of 0\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 ν 𝒜:𝒞PSh(𝒜)\nu_{\mathcal{A}}: \mathcal{C} \to PSh(\mathcal{A}) is fully faithful, where ν 𝒜(X)=𝒞(ı 𝒜(),X)\nu_{\mathcal{A}}(X)= \mathcal{C}(\imath_{\mathcal{A}}(-), X) for each X𝒞X \in \mathcal{C}.

The idea is that we can replace Set\mathbf{Set} and 0\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:

Lawvere theoryL TheoryΘwith arity𝒜 Model ofL op Θ-model Finitary monad Monad with arity𝒜 Globular (Batanin) operad Homogenous globular theory Symmetric operad Γ-homogeneous theory     \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)(I,L) is a Lawvere theory, the restriction functor I *:PSh(L)PSh( 0)I^{\ast}: PSh(L) \to PSh(\aleph_0) induces a monad I *I !I^{\ast} I_!, where I !I_! is left Kan extension along II. This monad preserves the essential image of the nerve functor ν 0\nu_{\aleph_0}, and in fact this condition reduces to preservation of coproducts by II (refer to 3.5 in the paper for further details). If MM is a model of L opL^{op} on Set\mathbf{Set} in the usual sense (i.e M:L opSetM: L^{op} \to \mathbf{Set} preserves finite products) we can see that its restriction along II is isomorphic to the 0\aleph_0-nerve of MI([1])MI([1]) by arguing that

(I *M)[n]=MI[n]=M( nI[1]) inL=M( nI[1]) inL op nMI[1]MI[1] nν 0(MI[1])[n], (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 (Θ,j)(\Theta,j), where j:𝒜Θj: \mathcal{A} \to \Theta is a bijective-on-objects functor such that the induced monad j *j !j^{\ast}j_! on PSh(𝒜)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 jj is isomorphic to some 𝒜\mathcal{A}-nerve.

Again, for 𝒜= 0\mathcal{A}=\aleph_0, this requirement on models says a Θ\Theta-model MM restricts to powers of some object: I *M()=MI()X ||I^\ast M(-)=MI(-) \cong X^{|-|} for some set XX, 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 (Θ 1,j 1)(Θ 2,j 2)(\Theta_1, j_1) \to (\Theta_2, j_2) is a functor θ:Θ 1Θ 2\theta: \Theta_1 \to \Theta_2 that intertwines with the arity functors, i.e j 2=θj 1j_2=\theta j_1. We’ll write Mod(Θ)Mod(\Theta) for the full subcategory of PSh(Θ)PSh(\Theta) consisting of the models of Θ\Theta and Th(𝒞,𝒜)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(𝒞,𝒜)Th(\mathcal{C},\mathcal{A}) and some category of monads, to mirror the situation between Lawvere theories and finitary monads on Set\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:𝒟SetF:\mathcal{D} \to \mathbf{Set} is a functor, then we can form a diagram of shape (*F) op({\ast}\downarrow F)^{op} over [𝒟,Set][\mathcal{D}, \mathbf{Set}] by composing the (opposite) of the natural projection functor (*F)𝒟({\ast}\downarrow F) \to \mathcal{D} and the Yoneda embedding. We may then consider the cocone

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

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

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

when FF is a presheaf on 𝒟\mathcal{D}. Likewise for XX an object of a category 𝒞\mathcal{C} with dense generator 𝒜\mathcal{A}, there is an associated diagram a X:𝒜/X𝒞a_X: \mathcal{A}/X \to \mathcal{C}, which comes equipped with an obvious natural transformation to the constant functor on XX, whose (AfX)(A \xrightarrow{f} X)-component is simply ff itself — this is called the 𝒜\mathcal{A}-cocone over XX, and it is just the cocone of vertex XX under the diagram a Xa_X of shape 𝒜/X\mathcal{A}/X in 𝒞\mathcal{C} whose legs consist of all morphisms AXA \to X with A𝒜A \in \mathcal{A}. Note that if 𝒜\mathcal{A} is small (as is the case), then this diagram is small and, if 𝒞=PSh(𝒜)\mathcal{C}=PSh(\mathcal{A}), the slice category 𝒜/X\mathcal{A}/X reduces to the category of elements of the presheaf XX and this construction gives the Yoneda cocone under XX. 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 XX 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 TT on 𝒞\mathcal{C} is a monad with arities 𝒜\mathcal{A} when ν 𝒜T\nu_{\mathcal{A}}T takes the 𝒜\mathcal{A}-cocones of 𝒞\mathcal{C} to colimit-cocones in PSh(𝒜)PSh(\mathcal{A}).

That is, the monad has arities 𝒜\mathcal{A} whenever scrambling the nerve functor by first applying TT 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 TT with arities 𝒜\mathcal{A}, the full subcategory Θ T\Theta_T spanned by the free TT-algebras on objects of 𝒜\mathcal{A} is a dense generator of the Eilenberg-Moore category 𝒞 T\mathcal{C}^T. The essential image of the associated nerve functor is spanned by those presheaves whose restriction along j Tj_T belongs to the essential image of the ν 𝒜\nu_{\mathcal{A}}, where j T:𝒜Θ Tj_T: \mathcal{A} \to \Theta_T is obtained by restricting the free TT-algebra functor.

The proof given relies on an equivalent characterization for monads with arities, namely that a monad TT 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”

𝒞 T ν T PSh(Θ T) U j T * 𝒞 ν 𝒜 PSh(𝒜) . \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) !ν 𝒜ν TF(j_T)_!\nu_{\mathcal{A}} \Rightarrow \nu_T F of the invertible 22-cell implicit in the above square is also invertible, where FF is the free TT-algebra functor. Note j T *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 𝒜/X\mathcal{A}/X is α\alpha-filtered for each object XX 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 TT 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 TT on an α\alpha-accessible category 𝒞\mathcal{C} preserves α\alpha-filtered colimits, then its category of algebras 𝒞 T\mathcal{C}^T is α\alpha-accessible, with a dense generator Θ T\Theta_T spanned by the free TT-algebras on (a skeleton 𝒜\mathcal{A} of) the α\alpha-presentable objects C(α)C(\alpha). Moreover, this category of algebras is equivalent to the full subcategory of PSh(Θ T)PSh(\Theta_T) spanned by those presheaves whose restriction along j Tj_T is α\alpha-flat.

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

Note that this theorem says, for α= 0\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 TT-algebras on finite sets: this is because a finitely-presentable (i.e 0\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 TT is a monad with arities 𝒜\mathcal{A}, then (Θ T,j T)(\Theta_T, j_T) is a theory with arities 𝒜\mathcal{A}. The Nerve Theorem then guarantees that ν T:𝒞 TPSh(Θ T)\nu_T: \mathcal{C}^T \to PSh(\Theta_T) induces an equivalence of categories between Θ T\Theta_T-models and TT-algebras, since its essential image is, by definition, the category of Θ T\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(Θ T,j T)T \mapsto (\Theta_T, j_T) extends to a functor Mnd(𝒞,𝒜)Th(𝒞,𝒜)\mathbf{Mnd}(\mathcal{C}, \mathcal{A}) \to \mathbf{Th}(\mathcal{C}, \mathcal{A}), which forms an equivalence of categories together with the functor Th(𝒞,𝒜)Mnd(𝒞,𝒜)\mathbf{Th}(\mathcal{C}, \mathcal{A}) \to \mathbf{Mnd}(\mathcal{C}, \mathcal{A}) that takes a theory (Θ,j)(\Theta, j) to the monad ρ 𝒜Tν 𝒜\rho_{\mathcal{A}}T\nu_{\mathcal{A}} with arities 𝒜\mathcal{A}, where ρ 𝒜\rho_{\mathcal{A}} is a choice of right adjoint to ν 𝒜:𝒞EssIm(ν 𝒜)\nu_{\mathcal{A}}: \mathcal{C} \to EssIm(\nu_{\mathcal{A}}). When 𝒞=Set\mathcal{C}=\mathbf{Set} and 𝒜= 0\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:

2 Comments & 0 Trackbacks

Re: Unboxing Algebraic Theories of Generalised Arities

Bravo! I don’t think I’d realized, even in the classical case of a finitary monad TT on the category of sets, that the (co)Lawvere theory Θ T\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 nn generators is dense in the algebras for a theory generated by operations of arity at most nn. 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