# Coproduct of free monoids.

Consider the following diagram, where $$A,B$$ are sets, $$A+B$$ is their disjoint union, and $$M(X)$$ is the free monoid on $$X$$ for $$X=A, B, A+B$$. I want to prove that $$M(A+B)$$ is the coproduct of $$M(A)$$ and $$M(B)$$, just using universal properties. How does the universal properties of $$A+B, M(A), M(B)$$ and $$M(A+B)$$ induce the existence (and uniquiness) of the dotted vertical arrow to $$N$$? In other words, how can I prove that $$M(A+B)$$ has the universal property of the coproduct $$M(A)+M(B)$$ of $$M(A)$$ and $$M(B)$$, without invoking any concrete presentation of the objects involved, such as the free monoid of words,...?

• – Arnaud D. Apr 24 '20 at 15:39
• Does this line of reasoning work for you? Let $a:M(A)\to N$ and $b:M(B)\to N$ be the two slanted arrows at the top. We have $a\circ\eta_A: A\to N$ and $b\circ\eta_B:B\to N$. By universality of coproduct in the set category, $a$ and $b$ uniquely induce $\gamma:A\sqcup B\to N$. Hence, by universality of free objects in the monoid category, we have a unique morphism $c:M(A\sqcup B)\to N$ through which $\gamma$ factors. It remains to show that $c$ makes the diagram commutative. – Batominovski Apr 24 '20 at 16:01
• @Batominovski yes, but following that reasoning I come up with an equality of composites I would like to cancel on the right to get the wanted commutativity of diagrams, but I can't cancel on the right because the morphisms on the right are monic, don't know what I am missing – Maryam Apr 24 '20 at 16:02
• Now that you mentioned this, I start to think that knowing the properties of free monoids may play a role. If I figure something out, I'll let you know. – Batominovski Apr 24 '20 at 16:10

The ingredients required for this proof are

• the functions $$\eta_A:A\to M(A)$$, $$\eta_B:B\to M(B)$$, and $$\eta_{A\sqcup B}:A\sqcup B\to M(A\sqcup B)$$;

• the functions $$i_A:A\to A\sqcup B$$ and $$i_B:B\to A\sqcup B$$;

• the monoid morphisms $$a:M(A)\to N$$ and $$b:M(B)\to N$$.

Other maps will be constructed through the universal properties in the relevant categories. (I am not comfortable using the notation $$A+B$$ for the coproduct of two sets $$A$$ and $$B$$. In my notation, $$A\sqcup B$$ is the coproduct.) The same proof works if $$\mathbf{Monoids}$$ is replaced by any concrete category that admits all free objects and coproducts (or at least, that the sets $$A$$, $$B$$, and $$A\sqcup B$$ are bases of some free objects $$M(A)$$, $$M(B)$$, and $$M(A\sqcup B)$$ in the target category).

We have two functions $$a\circ\eta_A: A\to N$$ and $$b\circ\eta_B:B\to N$$. By the universality of coproduct in $$\mathbf{Sets}$$, $$a$$ and $$b$$ uniquely induce $$\gamma:A\sqcup B\to N$$. That is, $$a\circ\eta_A = \gamma\circ i_A\text{ and }b\circ\eta_B=\gamma\circ i_B\,.$$

By the universality of free objects in $$\mathbf{Monoids}$$, we have a unique monoid morphism $$c:M(A\sqcup B)\to N$$ through which $$\gamma$$ factors. In other words, $$\gamma=c\circ\eta_{A\sqcup B}\,.$$ It remains to show that $$c$$ makes the diagram commutative.

We have a function $$\eta_{A\sqcup B}\circ i_A:A\to M(A\sqcup B)$$, which induces a unique monoid morphism $$\iota_A:M(A)\to M(A\sqcup B)$$ by the universality of free objects in $$\mathbf{Monoids}$$. That is, $$\iota_A\circ \eta_A=\eta_{A\sqcup B}\circ i_A\,.$$ Similarly, we have a unique monoid morphism $$\iota_B:M(B)\to M(A\sqcup B)$$. Likewise, $$\iota_B\circ \eta_B=\eta_{A\sqcup B}\circ i_B\,.$$

Consequently, $$(c\circ \eta_{A\sqcup B})\circ i_A=c\circ\left(\eta_{A\sqcup B}\circ i_A\right)=c\circ (\iota_A\circ\eta_A)=(c\circ \iota_A)\circ \eta_A\,.$$ However, $$(c\circ \eta_{A\sqcup B})\circ i_A=\gamma\circ i_A=a\circ \eta_A\,.$$ Thus, $$\eta_A$$ is an equilizer of the diagram $$A\underset{\eta_A}{\to} M(A)\underset{a}{\overset{c\circ \iota_A}{\rightrightarrows}}N\,.$$ Using the universality of free objects in $$\mathbf{Monoids}$$, we conclude that $$c\circ\iota_A=a\,.$$ Similarly, $$c\circ\iota_B=b\,.$$ Therefore, $$M(A\sqcup B)$$ together with $$\iota_A:M(A)\to M(A\sqcup B)$$ and $$\iota_B:M(B)\to M(A\sqcup B)$$ is the coproduct of $$M(A)$$ and $$M(B)$$.

From an “abstract nonsense” point of view, this follows from the fact that the underlying set functor $$\mathbf{U}$$, from monoids to sets, and the free monoid functor $$\mathbf{M}$$ from sets to monoids, are adjoints of each other. That is, for any set $$A$$ and any monoid $$M$$, we have a natural bijection $$\mathscr{S}\!\mathit{et}(A,\mathbf{U}(M)) \longleftrightarrow \mathscr{M}\!\mathit{onoid}(\mathbf{M}(A),M).$$ We say $$\mathbf{U}$$ is the right adjoint and $$\mathbf{M}$$ is the left adjoint of the pair. It is a theorem of Category Theory that left adjoints respect all colimits and right adjoins respect all limits.

Explicitly, for the case at hand, the disjoint union is the coproduct of sets, so for any sets $$A,B,C$$, we know that $$\mathscr{S}\!\mathit{et}(A+B,C) \cong \mathscr{S}\!\mathit{et}(A,C)\times \mathscr{S}\!\mathit{et}(B,C)$$ because the universal property of the disjoint union is that maps from the disjoint union correspond to pairs of maps from the constituents.

Likewise, for any monoids $$M$$, $$N$$, $$P$$, if $$M\amalg N$$ is their coproduct as monoids, $$\mathscr{M}\!\mathit{onoid}(M\amalg N,P) \cong \mathscr{M}\!\mathit{onoid}(M,P)\times\mathscr{M}\!\mathit{onoid}(N,P).$$

So we have that \begin{align*} \mathscr{M}\!\mathit{onoid}(\mathbf{M}(A+B),N) &\cong \mathscr{S}\!\mathit{et}(A+B,\mathbf{U}(N))\\ &\cong \mathscr{S}\!\mathit{et}(A,\mathbf{U}(N))\times \mathscr{S}\!\mathit{et}(B,\mathbf{U}(N))\\ &\cong \mathscr{M}\!\mathit{onoid}(\mathbf{M}(A),N)\times \mathscr{M}\!\mathit{onoid}(\mathbf{M}(B),N)\\ &\cong \mathscr{M}\!\mathit{onoid}(\mathbf{M}(A)\amalg\mathbf{M}(B),N). \end{align*}

More generally, as I mentioned, this follows because the coproduct is a colimit, and left adjoints respect colimits, and right adjoints respect limits. Symmetrically, the underlying set of the product is the product of the underlying sets; the underlying set of an inverse limit is the inverse limit of underlying sets, while the free monoid of a direct limit is the direct limit of the free monoids. Etc.

This answer, while it adds nothing essentially new to the existing answers to this question or the similar question mentioned in a comment, avoids using the existence of a functor that creates free monoids. By treating a more general case than was asked for, it also shows everything in one easily readable diagram.

Let $$(A_i)_{i \in I}$$ be a family of sets with a coproduct $$C.$$ Let $$(\kappa_i \colon A_i \to C)_{i \in I}$$ be the family of functions with the appropriate universal property. For all $$i \in I,$$ let there be given a monoid $$L_i$$ that is free over $$A_i.$$ Let $$(\eta_i \colon A_i \to L_i)_{i \in I}$$ be the family of functions with the appropriate universal property. Let $$M$$ be a monoid that is free over $$C.$$ Let $$\zeta \colon C \to M$$ be the function with the appropriate universal property. For all $$i \in I,$$ define $$\xi_i = \zeta \circ \kappa_i \colon A_i \to M.$$

We wish to show that $$M$$ is a coproduct of the family of monoids $$(L_i)_{i \in I}.$$ That is, there exists a family of homomorphisms $$(\lambda_i \colon L_i \to M)_{i \in I}$$ with the universal property that for every monoid $$N$$ and every family of homomorphisms $$(\varphi_i \colon L_i \to N)_{i \in I}$$ there exists a unique homomorphism $$\theta \colon M \to N$$ making the upper triangle in this diagram commute:

For all $$i \in I,$$ because $$L_i$$ is free over $$A_i,$$ there exists a unique homomorphism $$\lambda_i \colon L_i \to M$$ that makes the left hand triangle in the diagram commute. This defines the family $$(\lambda_i \colon L_i \to M)_{i \in I}$$ that is needed for the coproduct.

Because $$C$$ is a coproduct of the $$A_i,$$ there exists a unique function $$\psi \colon C \to N$$ that makes the square in the diagram commute, for all $$i \in I.$$ Because $$M$$ is free over $$C,$$ there exists a unique homomorphism $$\theta \colon M \to N$$ that makes the right hand triangle in the diagram commute. Then, for all $$i \in I$$: $$(\theta \circ \lambda_i) \circ \eta_i = \theta \circ (\lambda_i \circ \eta_i) = \theta \circ \xi_i = \theta \circ (\zeta \circ \kappa_i) = (\theta \circ \zeta) \circ \kappa_i = \psi \circ \kappa_i = \varphi_i \circ \eta_i.$$ By the uniqueness clause of the universal property of $$L_i$$ as a free monoid over $$A_i,$$ it follows that $$\theta \circ \lambda_i = \varphi_i.$$ It only remains to show that $$\theta$$ with this property is unique. If $$\theta \circ \lambda_i = \varphi_i,$$ then: $$(\theta \circ \zeta) \circ \kappa_i = \theta \circ (\zeta \circ \kappa_i) = \theta \circ \xi_i = \theta \circ (\lambda_i \circ \eta_i) = (\theta \circ \lambda_i) \circ \eta_i = \varphi_i \circ \eta_i = \psi \circ \kappa_i.$$ If this holds for all $$i \in I,$$ then $$\theta \circ \zeta = \psi,$$ by the uniqueness clause of the universal property of $$C$$ as a coproduct of the $$A_i.$$ The required result now follows from the uniqueness clause of the universal property of $$M$$ as a free monoid over $$C.$$