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.

February 18, 2017

Distributive Laws

Posted by Emily Riehl

Guest post by Liang Ze Wong

The Kan Extension Seminar II continues and this week, we discuss Jon Beck’s “Distributive Laws”, which was published in 1969 in the proceedings of the Seminar on Triples and Categorical Homology Theory, LNM vol 80. In the previous Kan seminar post, Evangelia described the relationship between Lawvere theories and finitary monads, along with two ways of combining them (the sum and tensor) that are very natural for Lawvere theories but less so for monads. Distributive laws give us a way of composing monads to get another monad, and are more natural from the monad point of view.

Beck’s paper starts by defining and characterizing distributive laws. He then describes the category of algebras of the composite monad. Just as monads can be factored into adjunctions, he next shows how distributive laws between monads can be “factored” into a “distributive square” of adjunctions. Finally, he ends off with a series of examples.

Before we dive into the paper, I would like to thank Emily Riehl, Alexander Campbell and Brendan Fong for allowing me to be a part of this seminar, and the other participants for their wonderful virtual company. I would also like to thank my advisor James Zhang and his group for their insightful and encouraging comments as I was preparing for this seminar.

First, some differences between this post and Beck’s paper:

  • I’ll use the standard, modern convention for composition: the composite XFYGZ\mathbf{X} \overset{F}{\to} \mathbf{Y} \overset{G}{\to} \mathbf{Z} will be denoted GFGF. This would be written FGFG in Beck’s paper.

  • I’ll use the terms “monad” and “monadic” instead of “triple” and “tripleable”.

  • I’ll rely quite a bit on string diagrams instead of commutative diagrams. These are to be read from right to left and top to bottom. You can learn about string diagrams through these videos or this paper (warning: they read string diagrams in different directions than this post!).

  • All constructions involving the category of SS-algebras, X S\mathbf{X}^S, will be done in an “object-free” manner involving only the universal property of X S\mathbf{X}^S.

The last two points have the advantage of making the resulting theory applicable to 22-categories or bicategories other than Cat\mathbf{Cat}, by replacing categories/ functors/ natural transformations with 0/1/2-cells.

Since string diagrams play a key role in this post, here’s a short example illustrating their use. Suppose we have functors F:XYF: \mathbf{X} \to \mathbf{Y} and U:YXU: \mathbf{Y} \to \mathbf{X} such that FUF \dashv U. Let η:1 XUF\eta: 1_{\mathbf{X}} \Rightarrow{UF} be the unit and ε:FU1 Y\varepsilon: FU \Rightarrow 1_{\mathbf{Y}} the counit of the adjunction. Then the composite FFηFUFεFFF \overset{F \eta}{\Rightarrow} FUF \overset{\varepsilon F}{\Rightarrow} F can be drawn thus:

Sample string diagram

Most diagrams in this post will not be as meticulously labelled as the above. Unlabelled white regions will always stand for a fixed category X\mathbf{X}. If FUF \dashv U, I’ll use the same colored string to denote them both, since they can be distinguished from their context: above, FF goes from a white to red region, whereas UU goes from red to white (remember to read from right to left!). The composite monad UFUF (not shown above) would also be a string of the same color, going from a white region to a white region.

Motivating examples

Example 1: Let SS be the free monoid monad and TT be the free abelian group monad over Set\mathbf{Set}. Then the elementary school fact that multiplication distributes over addition means we have a function STXTSXSTX \to TSX for XX a set, sending (a+b)(c+d)(a+b)(c+d), say, to ac+ad+bc+bdac+ad+bc+bd. Further, the composition of TT with SS is the free ring monad, TSTS.

Example 2: Let AA and BB be monoids in a braided monoidal category (𝒱,,1)(\mathcal{V}, \otimes, 1). Then ABA \otimes B is also a monoid, with multiplication:

ABABAtw BABAABBμ Aμ BAB, A \otimes B \otimes A \otimes B \xrightarrow{A \otimes tw_{BA} \otimes B} A \otimes A \otimes B \otimes B \xrightarrow{\mu_A \otimes \mu_B} A \otimes B,

where tw BA:BAABtw_{BA}: B \otimes A \to A \otimes B is provided by the braiding in 𝒱\mathcal{V}.

In example 1, there is also a monoidal category in the background: the category (End(Set),,Id)\left(\mathbf{End}(\mathbf{Set}), \circ, \text{Id}\right) of endofunctors on Set\mathbf{Set}. But this category is not braided – which is why we need distributive laws!

Distributive laws, composite and lifted monads

Let (S,η S,μ S)(S,\eta^S, \mu^S) and (T,η T,μ T)(T,\eta^T,\mu^T) be monads on a category X\mathbf{X}. I’ll use Scarlet and Teal strings to denote SS and TT, resp., and white regions will stand for X\mathbf{X}.

A distributive law of SS over TT is a natural transformation :STTS\ell:ST \Rightarrow TS, denoted

Definition of distributive law

satisfying the following equalities:

Axioms for a distributive law

A distributive law looks somewhat like a braiding in a braided monoidal category. In fact, it is a local pre-braiding: “local” in the sense of being defined only for SS over TT, and “pre” because it is not necessarily invertible.

As the above examples suggest, a distributive law allows us to define a multiplication m:TSTSTSm:TSTS \Rightarrow TS:

Multiplication for the composite monad

It is easy to check visually that this makes TSTS a monad, with unit η Tη S\eta^T \eta^S. For instance, the proof that mm is associative looks like this:

Associativity for the composite monad

Not only is TSTS a monad, we also have monad maps Tη S:TTST \eta^S: T \Rightarrow TS and η TS:STS\eta^T S: S \Rightarrow TS:

Monad maps to the composite monad

Asserting that Tη ST \eta^S is a monad morphism is the same as asserting these two equalities:

Check that we have a monad map

Similar diagrams hold for η TS\eta^T S. Finally, the multiplication mm also satisfies a middle unitary law:

Middle unitary law

To get back the distributive law, we can simply plug the appropriate units at both ends of mm:

Recovering the distributive law

This last procedure (plugging units at the ends) can be applied to any m:TSTSTSm':TSTS \Rightarrow TS. It turns out that if mm' happens to satisfy all the previous properties as well, then we also get a distributive law. Further, the (distributive law \to multiplication) and (multiplication \to distributive law) constructions are mutually inverse:

Theorem   The following are equivalent: (1) Distributive laws :STTS\ell:ST \Rightarrow TS; (2) multiplications m:TSTSTSm:TSTS \Rightarrow TS such that (TS,η Tη S,m)(TS, \eta^T \eta^S, m) is a monad, Tη ST\eta^S and η TS\eta^T S are monad maps, and the middle unitary law holds.

In addition to making TSTS a monad, distributive laws also let us lift TT to the category of SS-algebras, X S\mathbf{X}^S. Before defining what we mean by “lift”, let’s recall the universal property of X S\mathbf{X}^S: Let Y\mathbf{Y} be another category; then there is an isomorphism of categories between Funct(Y,X S)\mathbf{Funct}(\mathbf{Y}, \mathbf{X}^S) – the category of functors G˜:YX S\tilde{G}: \mathbf{Y} \to \mathbf{X}^S and natural transformations between them, and SS-Alg(Y)\mathbf{Alg}(\mathbf{Y}) – the category of functors G:YXG: \mathbf{Y} \to \mathbf{X} equipped with an SS-action σ:SGG\sigma: SG \Rightarrow G and natural transformations that commute with the SS-action.

Universal property of S-algebras

Given G˜:YX S\tilde{G}: \mathbf{Y} \to \mathbf{X}^S, we get a functor YX\mathbf{Y} \to \mathbf{X} by composing with U SU^S. This composite U SG˜U^S \tilde{G} has an SS-action given by the canonical action on U SU^S. The universal property says that every such functor G:YXG: \mathbf{Y} \to \mathbf{X} with an SS-action is of the form U SG˜U^S \tilde{G}. Similar statements hold for natural transformations. We will call G˜\tilde{G} and ϕ˜\tilde{\phi} lifts of GG and ϕ\phi, resp.

A monad lift of TT to X S\mathbf{X}^S is a monad (T˜,η˜ T,μ˜ T)(\tilde{T}, \tilde{\eta}^T,\tilde{\mu}^T) on X S\mathbf{X}^S such that

U ST˜=TU S,U Sη˜ T=η TU S,U Sμ˜ T=μ TU S. U^S \tilde{T} = T U^S, \qquad U^S \tilde{\eta}^T = \eta^T U^S, \qquad U^S \tilde{\mu}^T = \mu^T U^S.

We may express U ST˜=TU SU^S \tilde{T} = T U^S via the following equivalent commutative diagrams:

Commutative diagrams for lifts

The diagram on the right makes it clear that T˜\tilde{T} being a monad lift of TT is equivalent to T˜,η˜ T,μ˜ T\tilde{T}, \tilde{\eta}^T, \tilde{\mu}^T being lifts of TU S,η TU S,μ TU STU^S, \eta^T U^S,\mu^T U^S, resp. Thus, to get a monad lift of TT, it suffices to produce an SS-action on TU STU^S and check that it is compatible with η TU S\eta^T U^S and μ TU S\mu^T U^S. We may simply combine the distributive law with the canonical SS-action on U SU^S to obtain the desired action on TU STU^S:

S-action on TU^S

(Recall that the unlabelled white region is X\mathbf{X}. In subsequent diagrams, we will leave the red region unlabelled as well, and this will always be X S\mathbf{X}^S. Similarly, teal regions will denote X T\mathbf{X}^T.)

Conversely, suppose we have a monad lift T˜\tilde{T} of TT. Then the equality U ST˜=TU SU^S \tilde{T} = T U^S can be expressed by saying that we have an invertible natural transformation χ:U ST˜TU S\chi: U^S \tilde{T} \Rightarrow TU^S. Using χ\chi and the unit and counit of the adjunction F SU SF^S \dashv U^S that gives rise to SS, we obtain a distributive law of SS over TT:

Getting a distributive law from a lift

The key steps in the proof that these constructions are mutually inverse are contained in the following two equalities:

Constructions are mutually inverse

The first shows that the resulting distributive law in the (distributive law \to monad lift \to distributive law) construction is the same as the original distributive law we started with. The second shows that in the (monad lift T˜\tilde{T} \to distributive law \to another lift T˜\tilde{T}') construction, the SS-action on U ST˜U^S \tilde{T}' (LHS of the equation) is the same as the original SS-action on U ST˜U^S \tilde{T} (RHS), hence T˜=T˜\tilde{T} = \tilde{T}' (by virtue of being lifts, T˜\tilde{T} and T˜\tilde{T}' can only differ in their induced SS-actions on U ST˜=U ST˜=TU SU^S \tilde{T} = U^S \tilde{T}' = TU^S). We thus have another characterization of distributive laws:

Theorem   The following are equivalent: (1) Distributive laws :STTS\ell:ST \Rightarrow TS; (3) monad lifts of TT to X S\mathbf{X}^S.

In fact, the converse construction did not rely on the universal property of X S\mathbf{X}^S, and hence applies to any adjunction giving rise to SS (with a suitable definition of a monad lift of TT in this situation). In particular, it applies to the Kleisli adjunction F SU SF_S \dashv U_S. Since the Kleisli category X S\mathbf{X}_S is equivalent to the subcategory of free SS-algebras (in the classical sense) in X S\mathbf{X}^S, this means that to get a distributive law of SS over TT, it suffices to lift TT to a monad over just the free SS-algebras! (Thanks to Jonathan Beardsley for pointing this out!) The resulting distributive law may be used to get another lift of TT, but we should not expect this to be the same as the original lift unless the original lift was “monadic” to begin with, in the sense of being a lift to X S\mathbf{X}^S.

There are two further characterizations of distributive laws that are not mentioned in Beck’s paper, but whose equivalences follow easily. Eugenia Cheng in Distrbutive laws for Lawvere theories states that distributive laws of SS over TT are also equivalent to extensions of SS to a monad S˜\tilde{S} on the Kleisli category X T\mathbf{X}_T. This follows by duality from the above theorem, since X T=(X op) T\mathbf{X}_T = (\mathbf{X}^{op})^T. Finally, Ross Street’s The formal theory of monads (which was also covered in a previous Kan Extension Seminar post) says that distributive laws in a 22-category K\mathbf{K} are precisely monads in Mnd(K)\mathbf{Mnd}(\mathbf{K}). It is a fun and easy exercise to draw string diagrams for objects of Mnd(Mnd(K))\mathbf{Mnd}(\mathbf{Mnd}(\mathbf{K})); it becomes visually obvious that these are the same as distributive laws.

Algebras for the composite monad

After characterizing distributive laws, Beck characterizes the algebras for the composite monad TSTS.

Just as a morphism of rings RRR \to R' induces a “restriction of scalars” functor RR'-ModR\mathbf{Mod} \to R-Mod\mathbf{Mod}, the monad maps Tη S:TTST \eta^S: T \Rightarrow TS and η TS:STS\eta^T S: S \Rightarrow TS induce functors U^ TS:X TSX T\hat{U}^{TS}: \mathbf{X}^{TS} \to \mathbf{X}^T and U˜ TS:X TSX S\tilde{U}^{TS}: \mathbf{X}^{TS} \to \mathbf{X}^S.

Equivalently, we have SS- and TT-actions on U TSU^{TS}, which we call σ:SU TSU TS\sigma: SU^{TS} \Rightarrow U^{TS} and τ:TU TSU TS\tau: T U^{TS} \Rightarrow U^{TS}. Let ε:TSU TSU TS\varepsilon: TS\, U^{TS} \Rightarrow U^{TS} be the canonical TSTS-action on U TSU^{TS}. The middle unitary law then implies that ε=Tστ\varepsilon = T\sigma \cdot \tau:

Actions of T, S and TS

Further, σ\sigma is distributes over τ\tau in the following sense:

S-action distributes over T-action

The properties of these actions allow us to characterize TSTS-algebras:

Theorem   The category of algebras for TSTS coincides with that of T˜\tilde{T}:

X TS(X S) T˜ \mathbf{X}^{TS} \cong (\mathbf{X}^S)^{\tilde{T}}

To prove this, Beck constructs Φ:(X S) T˜X TS\Phi: (\mathbf{X}^{S})^{\tilde{T}} \to \mathbf{X}^{TS} and its inverse Φ 1:X TS(X S) T˜\Phi^{-1}: \mathbf{X}^{TS} \to (\mathbf{X}^S)^{\tilde{T}} . These constructions are best summarized in the following diagram of lifts:

Diagram of required lifts

On the left half of the diagram, we see that to get Φ 1\Phi^{-1}, we must first produce a functor U˜ TS:X TSX S\tilde{U}^{TS}: \mathbf{X}^{TS} \to \mathbf{X}^S with a T˜\tilde{T}-action. We already have U˜ TS\tilde{U}^{TS} as a lift of U TSU^{TS}, given by the SS-action σ\sigma. We also have the TT-action τ\tau on U TSU^{TS}, which σ\sigma distributes over. This is precisely what is required to get a lift of τ\tau to a T˜\tilde{T}-action τ˜\tilde{\tau} on U˜ TS\tilde{U}^{TS}, which gives us Φ 1\Phi^{-1}.

On the right half of the diagram, to get Φ\Phi we need to produce a functor (X S) T˜X(\mathbf{X}^{S})^{\tilde{T}} \to \mathbf{X} with a TSTS-action. The obvious functor is U SU T˜U^S U^{\tilde{T}}, and we get an action by using the canonical actions of SS on U SU^S and T˜\tilde{T} on U T˜U^{\tilde{T}}:

Lifts for Phi

All that’s left to prove the theorem is to check that Φ\Phi and Φ 1\Phi^{-1} are inverses. In a similar fashion, we can prove the dual statement (again found in Cheng’s paper but not Beck’s):

Theorem   The Kleisli category of TSTS coincides with that of S˜\tilde{S}:

X TS(X T) S˜ \mathbf{X}_{TS} \cong (\mathbf{X}_T)_{\tilde{S}}

Distributivity for adjoints

From now on, we identify X TS\mathbf{X}^{TS} with (X S) T˜(\mathbf{X}^S)^{\tilde{T}}. Under this identification, it turns out that U˜ TSU T˜\tilde{U}^{TS} \cong U^{\tilde{T}}, and we obtain what Beck calls a distributive adjoint situation comprising 3 pairs of adjunctions:

Distributive adjoint situation

For this to qualify as a distributive adjoint situation, we also require that both composites from X TS\mathbf{X}^{TS} to X\mathbf{X} are naturally isomorphic, and both composites from X S\mathbf{X}^S to X T\mathbf{X}^T are naturally isomorphic. This can be expressed in the following diagram by requiring both blue circles to be mutually inverse, and both red circles to be mutually inverse:

Distributive adjoints in string

(Recall that colored regions are categories of algebras for the corresponding monads, and the cap and cup are the unit and counit of F SU SF^S \dashv U^S.)

This diagram is very similar to the diagram for getting a distributive law out of a lift T˜\tilde{T}, and it is easy to believe that any such distributive adjoint situation (with 3 pairs of adjoints - not necessarily monadic - and the corresponding natural isomorphisms) leads to a distributive law.

Finally, suppose the “restriction of scalars” functor U^ TS\hat{U}^{TS} has an adjoint. This adjoint behaves like an “extension of scalars” functor, and Beck fittingly calls it () SF T(\,) \otimes_S F^T at the start of his paper. I’ll use F^ TS\hat{F}^{TS} instead, to highlight its relationship with U^ TS\hat{U}^{TS}.

In such a situation, we get an adjoint square consisting of 4 pairs of adjunctions. By drawing these 4 adjoints in the following manner, it becomes clear which natural transformations we require in order to get a distributive law:

Distributive adjoints again

(Recall that S=U SF SS = U^S F^S and T=U TF TT = U^T F^T, so this is a “thickened” version of what a distributive law looks like.)

It turns out that given the natural transformation uu between the composite right adjoints U SU T˜U^S U^{\tilde{T}} and U TU^ TSU^T \hat{U}^{TS}, we can get the natural transformation ff as the mate of uu between the corresponding composite left adjoints F^ TSF T\hat{F}^{TS} F^T and F T˜F SF^{\tilde{T}} F^S. Note that ff is invertible if and only if uu is. We may use uu or ff, along with the units and counits of the relevant adjunctions, to construct ee:

Getting e from u or f

But ee is in the wrong direction, so we have to further require that ee is invertible, to get e 1e^{-1}. We get ee' from u 1u^{-1} or f 1f^{-1} in a similar manner. Since ee' will turn out to already be in the right direction, we will not require it to be invertible. Finally, given any 4 pairs of adjoints that look like the above, along with natural transformations u,f,e,eu,f,e,e' satisfying the above properties, we will get a distributive law!

What next?

Beck ends his paper with some examples, two of which I’ve already mentioned at the start of this post. During our discussion, there were some remarks on these and other examples, which I hope will be posted in the comments below. Instead of repeating those examples, I’d like to end by pointing to some related works:

  • Since we’ve been talking about Lawvere theories, we can ask what distributive laws look like for Lawvere theories. Cheng’s Distributive laws for Lawvere theories, which I’ve already referred to a few times, does exactly that. But first, she comes up with 4 settings in which to define Lawvere theories! She also has a very readable introduction to the correspondence between Lawvere theories and finitary monads.

  • As Beck mentions in his paper, we can similarly define distributive laws between comonads, as well as mixed distributive laws between a monad and a comonad. Just as we can define bimonoids/bialgebras, and thus Hopf monoids/algebras, in a braided monoidal category, such distributive laws allow us to define bimonads and Hopf monads. There are in fact two distinct notions of Hopf monads: the first is described in this paper by Alain Bruguières and Alexis Virelizier (with a follow-up paper coauthored with Steve Lack, and a diagrammatic approach with amazing surface diagrams by Simon Willerton); the second is this paper by Bachuki Mesablishvili and Robert Wisbauer. The difference between these two approaches is described in the Mesablishvili-Wisbauer paper, but both involve mixed distributive laws. Gabriella Böhm also recently gave a talk entitled The Unifying Notion of Hopf Monad, in which she shows how the many generalizations of Hopf algebras are just instances of Hopf monads (in the first sense) in an appropriate monoidal bicategory!

  • We also saw that distributive laws are monads in a category of monads. Instead of thinking of distributive laws as merely a means of composing monads, we can study distributive laws as objects in their own right, just as monoids in a category of monoids (a.k.a. abelian monoids) are studied in their own right! The story for monoids terminates at this step: monoids in abelian monoids are just abelian monoids. But for distributive laws, we can keep going! See Cheng’s paper on Iterated Distributive Laws, where she shows the connection between iterated distributive laws and nn-categories. In addition to requiring distributive laws between each pair of monads involved, it is also necessary to have a Yang-Baxter equation between every three monads:

Yang-Baxter condition

  • Finally, there seems to be a strange connection between distributive laws and factorization systems (e.g. here, here and even in “Distributive Laws for Lawvere theories” mentioned above). I can’t say more because I don’t know much about factorization systems, but hopefully someone else can say something illuminating about this!
Posted at February 18, 2017 7:06 AM UTC

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

16 Comments & 0 Trackbacks

Re: Distributive Laws

Thanks Ze for a great post! I felt like I’ve gained something from seeing the commutative diagrams presented as string diagrams, in particular the intuition of distributive laws as local non-invertible braidings.

This makes me wonder if in the past I’ve paid too much heed to shapes of diagrams. For instance, if I were to describe the distributive law axioms to another category theorist but couldn’t be bothered to spell them out, I’d say that a distributive law between two monads TT and SS on the same object is given by a 2-cell :STTS\ell \colon ST \Rightarrow TS satisfying two triangles involving the units of the monads and two pentagons involving the multiplications of the monads.

My question: do the shapes of these commutative diagrams (the fact that two involve three morphisms and the other two involve five) have any significance?

Posted by: Emily Riehl on February 20, 2017 11:25 PM | Permalink | Reply to this

Re: Distributive Laws

In this case, I would tend to say that all four of the diagrams are actually rectangles; it’s just that one of their sides might consist of two or zero morphisms. From an unbiased perspective, a distributive law should satisfy 2ω2\omega axioms saying that it commutes with all the operations of a monad (= a monoid in an endofunctor category), of which there is exactly one nn-ary one for each nn, and each such axiom is naturally regarded as a commutativity rectangle (down-then-right = right-then-down) even if some of the sides have more than one morphism in them. It just so happens that, as usual, the cases n=0,2n=0,2 suffice.

Posted by: Mike Shulman on February 21, 2017 12:14 PM | Permalink | Reply to this

Re: Distributive Laws

There is a comment at the end of Beck’s paper that I’d like to understand better.

A monad on Set is called inconsistent if it is either of the two monads corresponding to hh-levels 2-2 or 1-1 in homotopy type theory, by which I mean:

  • it is the terminal monad T(X):=1T(X) := 1 for all XX, or

  • it is the monad with T(0):=0T(0) := 0 and T(X):=1T(X) := 1 otherwise.

Beck continues:

It is known that if TT is a consistent monad in sets, then the unit η X:XTX\eta_X \colon X \to TX is a monomorphism for every XX. And every monad in sets, as a functor, preservers monomorphisms.

I don’t see how to prove either of these statements. (Note that if XX admits a TT-algebra structure, then η X\eta_X must be a split monomorphism, but I can’t see how to get from this to the general argument.)

The reason these observations are interesting is that it follows in particular that the monad maps η S:STS\eta_S \colon S \Rightarrow TS and Tη:TTST\eta \colon T \Rightarrow TS are component wise monomorphisms, which means that

the operations of SS and of TT are mapped injectively into operations of STST, and no new equations hold among them in the composite.

Posted by: Emily Riehl on February 20, 2017 11:40 PM | Permalink | Reply to this

Re: Distributive Laws

For the first statement, if TT has at least one algebra with at least two elements, then the unit map η X:XTX\eta_X : X \to T X is injective for each set XX. For take distinct x,yXx, y \in X, and choose an algebra AA with at least two elements a,ba, b. We can then pick a function f:XAf: X \to A with f(x)=af(x) = a and f(y)=bf(y) = b. By adjointness, ff factors as η X\eta_X followed by some map TXAT X \to A. Since f(x)f(y)f(x) \neq f(y), it follows that η X(x)η X(y)\eta_X(x) \neq \eta_X(y).

So for the first statement, all that remains to prove is that if every TT-algebra has 1\leq 1 element then TT is one of Beck’s two “inconsistent” monads. To see this, take a set XX. The set T(X)T(X) can be given the structure of a TT-algebra, so it has either no elements or one element. But if XX is nonempty then T(X)T(X) must be nonempty too, since we have the unit map XT(X)X \to T(X). So T(X)=1T(X) = 1 for all nonempty XX. This leaves only the two options listed.

The second statement is that the underlying endofunctor TT of every monad on SetSet preserves monomorphisms. Well, every mono in SetSet is split unless its domain is empty, so we only need to show that T(0X)T(0 \to X) is mono for all sets XX. And it’s enough to show that T(01)T(0 \to 1) is mono, since it factors through T(0X)T(0 \to X). But now I’m stuck.

Posted by: Tom Leinster on February 21, 2017 12:13 AM | Permalink | Reply to this

Re: Distributive Laws

OK, here’s a proof that for every monad (T,η,μ)(T, \eta, \mu) on SetSet, the endofunctor TT preserves monics. It’s not the most elegant proof in the world — maybe someone can improve on it.

  • In SetSet, every monic with nonempty domain is split. So it suffices to show that T(0X)T(0 \to X) is monic for all sets XX.

  • If T(0)T(0) is empty, this is immediate. So assume that T(0)T(0) is nonempty.

  • Let XX be any set. By the assumption just made, we can pick a map XT(0)X \to T(0). Then the unique map 0T(0)0 \to T(0) factorizes as 0XT(0)0 \to X \to T(0). Applying TT to this factorization gives (T(0)T(!)T 2(0))=(T(0)T(!)T(X)T 2(0)). \Bigl( T(0) \stackrel{T(!)}{\to} T^2(0) \Bigr) = \Bigl( T(0) \stackrel{T(!)}{\to} T(X) \to T^2(0) \Bigr). If the composite of two maps is monic then so is the first of those maps. So it is enough to prove that T(!):T(0)T 2(0)T(!): T(0) \to T^2(0) is monic.

  • The map !! just mentioned is the unique map 0T(0)0 \to T(0). But this is η 0\eta_0. So it is enough to ptove that T(η 0)T(\eta_0) is monic. And this is true, since by definition of monad, T(η 0)T(\eta_0) is split by μ 0\mu_0.

Posted by: Tom Leinster on February 21, 2017 1:10 AM | Permalink | Reply to this

Re: Distributive Laws

In this last case where T0T 0 is nonempty you can directly construct a splitting for T! X:T0TXT!_X \colon T 0 \to T X, as follows. Let f:XT0f \colon X \to T 0 be your map such that η 0=f! X\eta_0 = f \circ !_X. Then since μ 0TfT! X=μ 0Tη 0=1 T0\mu_0 \circ T f \circ T!_X = \mu_0 \circ T \eta_0 = 1_{T 0} we see that the composite μ 0Tf\mu_0 \circ T f splits T! XT!_X, which is therefore monic.

Posted by: Alexander Campbell on February 21, 2017 1:48 AM | Permalink | Reply to this

Re: Distributive Laws

Here’s a challenge: can anyone give a constructive proof of (a version of) either of these statements, or an argument that they fail constructively?

Constructively, there are other monads on Set that one probably ought to exclude along with the “inconsistent” ones (although I don’t see what is “inconsistent” about the propositional truncation). For instance, any Lawvere-Tierney topology on the set of truth values gives rise to a subtopos of Set, which is in particular a reflective subcategory and thus an idempotent monad, and its units will not always be monic (but it will preserve monos, since it is left exact). Classically, the only proper subtopos of Set is the trivial one, but constructively there can be others. However, these clearly aren’t the sort of monads the statements are meant to apply to; is there a natural way to exclude them?

Posted by: Mike Shulman on February 21, 2017 11:43 AM | Permalink | Reply to this

Re: Distributive Laws

I know, right? I learned how to do this kind of argument from Peter Johnstone’s Cambridge Part III Category Theory problem sheets, which I tutored for a year or two. It took me a while to get the hang of them.

Eventually, I realized the huge gap between the style of argument you use for a general category and the style of argument you use for a particular category (such as the category of sets). When you’re told that you’re working with a particular category, it’s no holds barred: you use whatever you can. Learning to really take advantage of that assumption was difficult for me (and doubtless I haven’t mastered it yet). It’s the opposite of doing everything in a scrupulously constructive manner.

Of course, it’s a bonus if you can show that the argument works for an arbitrary topos, or regular category, or adhesive quasi-topos, or whatever — and Peter himself is very good at that kind of thing. But that comes second.

Posted by: Tom Leinster on February 21, 2017 11:27 PM | Permalink | Reply to this

Re: Distributive Laws

While I agree that there’s a difference between arguing in a general category and a particular one, I wouldn’t identify it with constructivity versus classicality. A philosophical constructivist would dispute that your argument works even for the particular category Set\mathbf{Set}.

Posted by: Mike Shulman on February 22, 2017 3:27 AM | Permalink | Reply to this

Re: Distributive Laws

While I agree that there’s a difference between arguing in a general category and a particular one, I wouldn’t identify it with constructivity versus classicality.

Nor would I.

Posted by: Tom Leinster on February 22, 2017 10:05 PM | Permalink | Reply to this

Re: Distributive Laws

Those string diagrams look beautiful. Which software did you use?

Posted by: Anonymous Coward on February 21, 2017 9:11 AM | Permalink | Reply to this

Re: Distributive Laws

Ze can probably give you more information about it but in case he does not see your question, here is what he told us live: the diagram are done with TikZ, with the help of a software called TikzEdt.

Posted by: Pierre Cagne on February 21, 2017 11:42 AM | Permalink | Reply to this

Re: Distributive Laws

Thanks! As Pierre says, they were done in TikZ (I took screenshots of the resulting PDF). The use of TikzEdt made it a lot easier, because I could select multiple nodes and drag them around. This meant that I could pretty much treat the strings as real strings, and just drag one across another to form the necessary braidings.

To get the effect of a line crossing over another line, I used Tikz’s “double” property for lines.

Posted by: Ze on February 22, 2017 12:05 AM | Permalink | Reply to this

Re: Distributive Laws

Nice post, nice pictures! In the believe that beautiful theory is enhanced by a wide variety of examples, and bearing in mind (a) that people tend to mention the ring monad as the key example of a distributive law and (b) that I should look at the Hopf monad example, can I ask what other interesting examples there are?

Posted by: Simon Willerton on February 21, 2017 11:15 AM | Permalink | Reply to this

Re: Distributive Laws

In our discussion, David Myers pointed out that Zappa-Szep products of groups H,KH,K are precisely distributive laws between the monads T=H×T = H \times - and S=K×S = K \times -. These include semi-direct and direct products as special cases.

The characterization of distributive laws as multiplications making TST S into a monad translates into the following: a group GG is a Zappa-Szep product of subgroups HH and KK iff G=HKG = H K and HK={e G}H \cap K = \{e_G\}, where e Ge_G is the identity of GG.

Saying that G=HKG = H K is the same as saying we have group structure on the set H×KH \times K. That HH and KK are subgroups of GG corresponds to the monad maps Tη ST \eta^S and η TS\eta^T S being monomorphisms. The unit of TST S is η Tη S\eta^T \eta^S, which makes e H×e Ke_H \times e_K the unit of GG. In this case, the diagram that defines the unit of TST S is a pullback diagram (of η TS\eta^T S and Tη ST \eta^S), and thus HK={e G}H \cap K = \{e_G\}.

I’m not sure if the diagram that defines the unit of TST S is always a pullback for more general TT and SS, but if TT and SS are consistent, we at least have monomorphisms η TS\eta^T S and Tη ST \eta^S, so TT and SS can be thought of as ‘submonads’ of TSTS. To get direct and semi-direct products, we would need something like ‘normal submonads’, but I don’t know what that would look like.

We can also work with monads of the form MM \otimes - for monoids MM in other monoidal categories, and I think bicrossed products and bismash products of Hopf algebras are examples of this.

David also pointed out that expressing GG as HKH K gives a ‘factorization’ of GG. This is in fact related to strict factorization systems on categories (see section 4 of this). Small categories are monads in textbfSpan\textbf{Span}, and distributive laws between them yield ‘composite’ categories with strict factorization systems given by the original categories. If we think of a group as a 1 object category containing only isomorphisms, then a strict factorization system on that category gives the decomposition that we saw above.

Distributive laws between a monad and comonad also turn up in algebraic weak factorization systems, but I’m not sure if they arise from distributive laws in the same manner that strict factorization systems do.

Posted by: Ze on February 22, 2017 2:10 AM | Permalink | Reply to this

Re: Distributive Laws

Thanks Ze for writing this up! I’ll just mention a few other examples and special cases.

I never learned about Zappa-Szep products in my algebra classes, but I did learn about two special cases: the semi-direct product, and the direct product. An internal Zappa-Szep product happens when the group GG factors as the product of two disjoint subgroups HKHK. This product is semi-direct when HH is normal, and is direct when both HH and KK are normal. This tells us, for example, that if an abelian group factors as a semi-direct product of two other abelian groups (or even as a Zappa-Szep product), then it is actually their direct product.

It’s pretty straightforward to see how the direct product gives a distributive law between two groups HH and KK. We define the law H×KK×HH \times K \to K \times H to be the twist map (h,k)(k,h)(h, k) \mapsto (k, h), and the multiplication induced is the composite (h,k,h,k)(h,h,k,k)(hh,kk)(h, k, h', k') \mapsto (h, h', k, k') \mapsto (hh', kk') which is exactly the multiplication you want for the direct product.

I found the semi-direct product case revealing as well. When I was learning about semi-direct products, I wondered why we only acted on one of the factors. Seeing it as a distributive law makes it clear: we only need to twist the middle two instances of the groups like this H×K×H×KH×H×K×KH \times K \times H \times K \to H \times H \times K \times K, so we only need to act on that copy of HH that moved. So, explicitly, let ϕ:KAut(H)\phi : K \to \text{Aut}(H) be a homomorphism. Define the distributive law by (h,k)(k,ϕ(k)(h))(h, k) \mapsto (k, \phi(k)(h)). The multiplication on the composite group then becomes (h,k,h,k)(h,ϕ(k)(h),k,k)(hϕ(k)(h),kk)(h, k, h', k') \mapsto (h, \phi(k)(h'), k, k') \mapsto (h \cdot \phi(k)(h'), kk') which is the definition of the multiplication in the semi-direct product.

More fun than distributive laws between groups are distributive laws between algebraic structures of different kinds. The functor sending a group GG to the monad G×G \times - of its actions is fully faithful, as is the functor sending a ring to the monad of its modules. We can recover the group GG from G×G \times - with its monad structure as G×1G \times 1, and the ring as the free module on 11 generator. So we are justified in equating a group with its monad of actions, and a ring with its monad of modules. If GG is a group and RR a ring, then we can distribute GG over RR by the law GRXRGXGRX \to RGX sending (g,r ix i)r i(g,x i)(g, \sum r_i x_i) \mapsto \sum r_i (g, x_i). This gives us another ring, the group ring R[G]R[G], which we can see by checking the action on 11: the elements of RG1RG1 are formal RR-linear combinations r ig i\sum r_i g_i of group elements. The modules of R[G]R[G] are representations of GG on RR-modules.

On a related note, I’d be really interested in seeing a characterization of all the categories of algebras (by which I mean categories of modules for a monad) which embed into the category of monads. I’m particularly interested when the base is the category of sets, but it would be great to know over a general category as well.

One last example, less algebraic this time. Let PP be the powerset monad (whose unit is the inclusion of singletons, and whose multiplication is union), and MM the monoid monad. We can define a distributive law MPPMMP \to PM by sending a formal product H 1H nH_1 \cdots H_n of subsets to the set {h 1h nh iH i}\{h_1 \cdots h_n \mid h_i \in H_i\} of formal products of their elements. This is the usual set product, the one we were using to talk about Zappa-Szep products. Since the modules of the powerset monad are sup-lattices, I’d expect the modules of PMPM to be quantales, but I haven’t checked this.

Posted by: David Jaz Myers on February 24, 2017 9:52 PM | Permalink | Reply to this

Post a New Comment