3
$\begingroup$

I'm learning about monads in Riehl's Category Theory in Context, and after reading Example 5.1.4.ii, about the free monoid monad (also known as the list monad to computer scientists) on the monoidal category $(\mathsf{Set}, \times, *)$, I've reached Exercise 5.1.i, meant to demonstrate that this monad can in fact be defined on any monoidal category with "coproducts that distribute over the monoidal product." To summarize the example, the list monad is the functor with action $T(A) = \coprod_{n \geq 0} A^n$ induced by the free $\dashv$ forgetful adjunction between sets and monoids, where the unit components are the coproduct inclusions and the multiplication components are concatenations. (e.g. $((a,b),(c)) \mapsto (a, b, c)$.)

In the exercise, the reader is given a generic monoidal category $(V, \otimes, *)$ with finite coproducts which $\otimes$ "preserves in each variable." (A footnote clarifies this with the equality $(v \sqcup v') \otimes (w \sqcup w') = v \otimes w \sqcup v' \otimes w \sqcup v \otimes w' \sqcup v' \otimes w'$. Isn't this "the monoidal product distributing over the coproduct," the reverse of the author's claim?) Then the reader is asked to define the unit and multiplication ($\eta : 1_V \Rightarrow T$ and $\mu : T^2 \Rightarrow T$) so that $T(X) = \coprod_{n \geq 0} X^{\otimes n}$ is a monad. (Tangent: shouldn't $V$ be required to have countable rather than just finite coproducts for this to make sense?) In analogy with the example, it's clear to me that the the unit components should again be the coproduct inclusions, but I'm having a really hard time defining the multiplication.

If I understand correctly, in the example the singleton $*$ is both the unit object and the terminal object. That would allow me to take the morphism $T(A)^{k-1} \to *$ and apply $T(A) \times (-)$ to get $T(A)^k \to T(A) \times * \cong T(A)$ for any $k$, defining a cone from the diagram $\emptyset, T(A), T(A)^2, \dots$ to $T(A)$ and thus inducing a unique morphism $T^2(A) \to T(A)$ by the universal property which I can take to be $\mu_A$. But not only am I unable to verify that this coincides with the example's concatenation, this also doesn't seem to be a useful analogy for the exercise since, as far as I can tell, there's no guarantee that $V$ has a terminal object at all!

EDIT: To clarify my response to Kevin Arlin's comment, the coproduct inclusions $A^k \xrightarrow{\iota} T(A)$ are split monomorphisms in $\mathsf{Set}$, (any injective function restricts to a bijection onto its image) giving us morphisms $T(A) \xrightarrow{r} A^k$ for any $k$ such that $r \circ \iota = \mathrm{id}_{A^k}$. This allows us to form diagrams as in the following example:

A commutative diagram showing how composition of retractions and projections defines a morphism from T(A)^2 to T(A)

Here, $r \circ (a) = a$ and $r \circ (b) = b$, so it should be that $\tilde{r} \circ ((a), (b)) = (a,b)$, which is exactly the desired concatenation for pairs of singlet lists. Similar constructions define concatenations of triples, quadruples, etc. of lists into $T(A)$, and hopefully induce a unique map $T^2(A) \to T(A)$. But now my concerns become:

  • This construction is specific to pairs of singlet lists. Each different combination of list lengths requires a unique such morphism. Can this collection of morphisms in $\mathsf{Set}(T(A)^2, T(A))$ define a single morphism?
  • Are coproduct inclusions in $V$ still split monic?
$\endgroup$
19
  • $\begingroup$ To the parentheticals: yes, I'd also phrase this as $\otimes$ distributing over $\sqcup.$ But the opposite never happens in natural examples so the risk of confusion shouldn't be major. And yes, you need countable coproducts, though I wonder if you haven't missed something in Riehl's setup that supposes this. $\endgroup$ Dec 28, 2022 at 19:13
  • 2
    $\begingroup$ As for the main question, you've defined a map of sets $T^2(A)\to T(A)$ that on, say, $T(A)^2,$ sends $(w_1,w_2)$ to $w_1.$ But that is not what the multiplication of the list monad is! I'd think this through more carefully for sets, and then it should become clear in the generalization. $\endgroup$ Dec 28, 2022 at 19:15
  • 1
    $\begingroup$ You're trying to reason quite abstractly, but the point of working in sets is to allow you to think concretely before generalizing. The maps $T(A)\to A^k$ you claim to define go in the other direction: they're the inclusion of $A^k$ into the coproduct. Then, you're trying to do something with $T(A)^2,$ but the algebra structure is supposed to be a map $T^2(A)=T(T(A))\to T(A),$ which is quite different. Anyway, $T(A)$ is the set of words from $A$ of finite length, and thus $T^2(A)$ is the set of words from the set of words from $A$ of finite length. If $A=\{0,1\},$ a characteristic... $\endgroup$ Jan 5, 2023 at 0:15
  • 1
    $\begingroup$ Literally, how would you turn $((0,1,1),(1,1,1,1,1),(),(0,1,0,1))$ into a single word? It wasn't obvious that either of those points were clear to you since it was non-obvious why you would do either of those thing, but I'm glad it makes sense. $\endgroup$ Jan 5, 2023 at 0:29
  • 1
    $\begingroup$ This looks again like an issue of not writing $T(A)^2$ down explicitly. It is $\sqcup_{i,j} A^i\otimes A^j.$ Thus you do indeed get to define different maps on the "disjoint" (not literally, in general) subobjects $A^3\otimes A$ and $A^2\otimes A^2,$ all part of a single map out of $T(A)^2.$ $\endgroup$ Jan 6, 2023 at 17:34

2 Answers 2

1
$\begingroup$

Here's an alternative take on the problem: one may use Theorem 2.1 from nLab's article on the free monoid (note: $\operatorname{Mon}(\mathsf{C})$ means the category of monoids in a monoidal category $\mathsf{C}$) and then apply Lemma 5.1.3 of Riehl's book (saying that any functor adjunction induces a monad on the domain of the left adjoint). A proof of the mentioned Theorem 2.1 of the nLab's article may be read in Mac Lane's Categories for the Working Mathematician, VII.3, Theorem 2. Anyway, here's a proof outline:

We define a left adjoint $F:\mathsf{C}\to\mathrm{Mon}(\mathsf{C})$ to the forgetful functor $\mathrm{Mon}(\mathsf{C})\to\mathsf{C}$. It sends $c$ to $Fc=\sum_{n\geq 0}c^{\otimes n}$. The unit $\eta=i_0:*\to Fc$ is just the inclusion in degree $0$. Distributivity of the tensor product with respect to countable coproducts means that the tensored inclusions $c^{\otimes n}\otimes c^{\otimes k}\to Fc\otimes Fc$ give rise to a canonical isomorphism $$ \label{iso}\tag{1} \sum_{n,k\geq 0}c^{\otimes n}\otimes c^{\otimes k}\cong Fc\otimes Fc. $$ We will now define the multiplication $\mu:Fc\otimes Fc\to Fc$. By \eqref{iso}, this amounts to define a map $\mu_{nk}:c^{\otimes n}\otimes c^{\otimes k}\to Fc$, for each $n,k\geq 0$. If $n,k\geq 1$, then $c^{\otimes n}\otimes c^{\otimes k}=c^{\otimes n+k}$ and $\mu_{nk}=i_{n+k}:c^{\otimes n+k}\to Fc$ is the inclusion in degree $n+k$. If one of $n$ or $k$ is zero (WLOG suppose $n=0$), then we define $\mu_{0k}$ to be $*\otimes c^{\otimes k}\xrightarrow{\lambda_k}c^{\otimes k}\xrightarrow{i_k} Fc$, where $\lambda_k$ is the component of the left unitor of (the monoidal structure on) $\mathsf{C}$ at $c^{\otimes k}$.

With this unit and multiplication, $Fc$ is a monoid in $\mathsf{C}$: it is associative [ref]. Unitality is expressed by the commutativity of the outer square in the following diagram:

enter image description here

(Here, $i_{nk}:c^{\otimes n}\otimes c^{\otimes k}\to\sum_{n,k\geq 0}c^{\otimes n}\otimes c^{\otimes k}$ denotes the inclusion in degree $n,k$.) Note that, in the diagram, the arrows $\nwarrow$ and $\uparrow$ are isos by distributivity of the tensor product with respect to countable coproducts. Hence, it suffices to see that the four internal triangles commute. The top, bottom and right triangles commute basically by definition. The left triangle commutes by naturality of $\lambda$. Hence, $Fc$ is left-unital. Showing that $Fc$ is right-unital is analogous.

This finishes the definition of the action of $F$ on objects. We now define the action on morphisms. A morphism $c\to d$ in $\mathsf{C}$ induces a canonical map $Fc\to Fd$, not difficult to verify to be a morphism in $\operatorname{Mon}(\mathsf{C})$.

Let $m$ be a monoid in $\mathsf{C}$. It is left to see that the natural map \begin{align*} \tag{2}\label{nat} \operatorname{Mon}(\mathsf{C})(Fc,m)&\rightarrow\mathsf{C}(c,m)\\ (Fc\to m)&\mapsto(c\to Fc\to m) \end{align*} is a bijection. We first see it is onto: a morphism $c\to m$ induces a morphism $c^{\otimes n}\to m^{\otimes n}$. Post-composing with the $n$-ary multiplication $m^{\otimes n}\to m$ (defined up to unique natural isomorphism, see Mac Lane's book, VII.3, Proposition 1) and summing everything up gives a map $Fc\to m$. One may verify that this constitutes a morphism of monoids.

To see injectivity, given a morphism of monoids $Fc\to m$, it suffices to see that for $n\geq 1$, the map $c^{\otimes n}\to Fc\to m$, is completely determined by $c\to Fc\to m$. The diagram $$ \require{AMScd} \begin{CD} (Fc)^{\otimes n}@>>> Fc\\ @VVV@VVV\\ m^{\otimes n}@>>> m \end{CD} $$ commutes by hypothesis. Precomposing the diagram with the canonical map $j:c^{\otimes n}\to (Fc)^{\otimes n}$ (equal to the composite $c^{\otimes n}\to\sum_{k_1,\dots,k_n\geq 0}c^{\otimes k_1+\cdots +k_n}\cong(Fc)^{\otimes n}$, where the latter is canonical and the former is the inclusion in degree $(k_1,\dots,k_n)=(1,\dots,1)$) gives the desired result.

$\endgroup$
5
  • $\begingroup$ Thank you so much for your answer, though I must admit I haven't been able to fully verify your proof. Trying to verify that $Fc$ is a monoid, I've shown that it satisfies the associative law, but I'm unable to show that it satisfies the left and right unit laws. Also, in showing that the natural map is bijective, I'm unable to show that the induced map $Fc \to m$ is a morphism of monoids in the onto step, and I don't understand how precomposing the multiplication square with $c^{\otimes n} \to (Fc)^{\otimes n}$ yields the result in the injective step. $\endgroup$
    – Itserpol
    Jan 13 at 1:27
  • $\begingroup$ Also, for anyone curious, I was able to work out associativity thanks to this: math.stackexchange.com/questions/1269975/… $\endgroup$
    – Itserpol
    Jan 13 at 1:30
  • $\begingroup$ Thanks for the critique. I have just added more details regarding the definition of the multiplication $\mu:Fc\otimes Fc\to Fc$ plus a full-detailed proof that $Fc$ satisfies the left unit law. When I say "one may verify that this constitutes a morphism of monoids" I'm just passing the buck. I would need more time to come up with the relevant commutative diagrams that give the full-detailed proof, but I don't have time right now... (I have already spent much more time than I expected thinking about the correct definition of $\mu$ and the proof of the left unit law). $\endgroup$ Jan 15 at 19:57
  • $\begingroup$ Alternatively, you may try to understand the proof I referenced from Mac Lane's book. I haven't read the details, but his strategy is different: instead of constructing $F$'s action on morphisms and proving \eqref{nat} is bijective (as I do), he verifies $F$ satisfies the definition of a left adjoint via the universal arrow formulation (Def. 2.8 here). Regarding your last question: call $f$ to the composite $c\to Fc\to m$. Then the composite $c^{\otimes n}\xrightarrow{j}(Fc)^{\otimes n}\to m^{\otimes n}$ equals $f^{\otimes n}$. $\endgroup$ Jan 15 at 19:58
  • 1
    $\begingroup$ Wow! I was just hoping for a hint, but you actually worked out the whole left unital diagram, thank you so much! Between that and Mac Lane's universal arrow formulation of the adjunction, I was finally able to solve this problem. $\endgroup$
    – Itserpol
    Jan 18 at 17:26
0
$\begingroup$

Based on Kevin Arlin's final comment, I was quickly able to construct the components $\mu_X$ of the multiplication to my satisfaction. Unfortunately, in the weeks since then I've still been unable to show that $\mu$ is natural in $X$ or that $\mu$ and $\eta$ satisfy the monad commutation relations. (Aside from $\mu_X\eta_{T(X)} = \mathrm{id}_{T(X)}$, which follows easily from the construction of $\mu$.) I've grown tired and frustrated with this problem, however, and will be moving on. But for the sake of posterity, I'll post my construction.

As Kevin mentioned, distributivity of the monoidal product yields $T(X)^2 \cong \coprod_{i,j} X^i \otimes X^j$. (Here I'm abusing notation and writing $X^{\otimes i}$ as $X^i$ for clarity, though I understand that this is distinct from the categorical product.) More generally, we can say that $T(X)^N \cong \coprod_{a \in \mathbb{N}^N} \bigotimes_{i=1}^N X^{a_i}$. And since $\bigotimes_{i=1}^N X^{a_i} \cong X^{\sum_{i=1}^N a_i}$ by associativity, this defines a cocone under the discrete diagram of all such monoidal powers of $X$ with nadir $T(X)$, and hence induces a morphism $T(X)^N \xrightarrow{\alpha_N} T(X)$.

enter image description here

As $N$ varies, these morphisms $\alpha_N$ further define a cocone under the discrete diagram of all monoidal powers of $T(X)$ with nadir $T(X)$. The multiplication component $\mu_X$ is the unique morphism induced by the universal property.

enter image description here

Since $\alpha_1$ is clearly the identity morphism on $T(X)$, this proves the sole commutation relation that I have been able to show: $$ \mathrm{id}_{T(X)} = \alpha_1 = \mu_X\iota_{T(X)} = \mu_X\eta_{T(X)}. $$

I welcome anyone who is able to show naturality of $\mu$ in $X$ and the remaining monad commutation relations, but I no longer wish to spend my energy thinking about this problem.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .