# Abstract Nonsense

## Category Theory: Monoids Part II: Monoid Homomorphisms and Submonoids

Point of post: The point of this post is to discuss the ideas of monoid homomorphisms, submonoids, and product monoids. These are the monoid analogue of group homomorphisms, subgroups, and direct product. I also prove that every monoid can be isomorphically embedded in a monoid of functions. I also attempt to point out the differences and similarities between the monoid theoretic definitions of these familiar concepts and their group theoretic kin.

Monoid Homomorphism:

Let $\left(M,*\right)$ and $\left(N,\star\right)$ be monoids with identity elements $e_M$ and $e_N$ respectively. Then we see say that $\theta:\left(M,*\right)\to \left(N,\star\right)$ is a monoid homomorphism if:

1) $\theta(m*n)=\theta(m)\star\theta(n)$ for all $m,n\in M$

2) $\theta(e_M)=e_N$

Condition 2) may seem strange to those of you familiar with group theory since the group theoretic analogue of a homomorphism always satisfies that property. Said differently, if $\theta$ is a map from a group $G$ to a group $G'$ with property 1), then property2) is a direct consequence (i.e. in groups 1) implies 2)). So, let us examine the normal proof given for such an implication.

” Let $\left(G,*\right)$ and $(G',\star)$ be groups with identities $e_1$ and $e_2$ respectively. Then if  $\theta:G\to G'$ is such that $\theta(g_1*g_2)=\theta(g_1)\star\theta(g_2)$, then $\theta(e_1)=e_2$. To see this we merely note that $\theta(e_1)=\theta(e_1*e_1)=\theta(e_2)\star\theta(e_2)$ and so by the cancellation property $\theta(e_1)=e_2$

The operative part of the above proof was the use of the cancellation property in groups, a property whose proof is merely an application of the possession of inverses in groups. That said, a hand-waving plausibility argument about monoids not having this property proves nothing. But, we can easily exhibit a mapping from one monoid to another that has property 1) but not property 2). Consider though

Example: Consider the monoids $\left(\mathbb{N}\cup\{0\},+\right)$ and $\left(\mathbb{Z},\cdot\right)$ and the mapping

$\theta:\left(\mathbb{N}\cup\{0\},+\right)\to\left(\mathbb{Z},\cdot\right):n\mapsto 0$

We clearly see that

$\theta(m+n)=0=0\cdot 0=\theta(m)\cdot\theta(n)$

so that $\theta$ has property 1). That said, we see that $\theta(0)=0\ne 0$ so $\theta$ does not possess property 2). Thus, we see that property 2) is, in fact, not a redundancy of property 1).

If $\theta:\left(M,*\right)\to\left(N,\star\right)$ is a monoid homomorphism and is bijective we call $\theta$ a monoid isomorphism and say that $M$ and $N$ are isomorphic, denoted $M\cong N$.

Remark: It is common practice, since we’re dealing expressly with monoids, to drop the monoid prefix and just call the above mappings homomorphisms and isomorphisms.

Submonoid:

If $\left(M,*\right)$ is a monoid with identity element $e$ we call $S\subseteq M$ a submonoid if $S$ is closed under $*$-multiplication and $e_M\in S$

Remark: This notation, the $\leqslant$, is the same notation used for subgroup. So, be careful.

Theorem: Let $\left(M,*\right)$ be a monoid with identity element $e$. Then, $S\leqslant M$  if and only if $\left(S,*\right)$ is a monoid containing $e$.

Proof: Suppose that $S$ is a submonoid.Then, by assumption $e\in S$ and so $S$ has an identity. Furthermore, since $S$ is closed under multiplication we know that $*:S\times S\to S$ and since $*$ is associative for all $a,b,c\in S$ it is clearly associative for all $x,y,z\in S$. It follows that $\left(S,*\right)$ is a monoid.

Conversely, if $\left(S,*\right)$ is a monoid containing $e$, then it suffices to prove that $S$ is closed under $*$. But, since $*:S\times S\to S$ the conclusion follows. $\blacksquare$

Note that once again there is a seemingly redundant restriction on submonoids, namely that the identity of the ambient monoid is contained in it.  Once again the confusion arises from knowledge of group theory, namely the definition of a subgroup. It can be proven that if $\left(G,*\right)$ is a group and $H\leqslant G$ then the identity for $H$ is the same as the identity for $G$. Let’s go through the proof of this

” Let $\left(G,*\right)$ be a group and $H\leqslant G$. Then, if $e_H$ and $e_G$ are the identities for $H$ and $G$ respectively $e_G=e_H$. To see this let $x\in H$ (we assumed it’s non-empty). Now, technically for $H$ we have the map $*_{\mid H}:H\times H\to H$ and with this we see that $e_H=x*_{\mid H}x^{-1}=x*x^{-1}=e_G$. The conclusion follows.”

Once again, the proof relies heavily on the existence of inverses in the group and subgroup. But, once again a half-hearted plausibility argument is no proof. So, consider:

Example: Let $\left(\mathbb{Z}\times\mathbb{Z},\cdot\right)$ be the monoid with multiplication given coordinate wise and with identity element $(1,1)$. Note though that $\mathbb{Z}\times\{0\}\subseteq\mathbb{Z}\times\mathbb{Z}$. This is evidently closed under multiplication since

$(z,0)\cdot(z',0)=(z\cdot z',0\cdot0)=(z\cdot z',0)\in\mathbb{Z}\times\{0\}$

We also note that $(1,0)\cdot(z,0)=(1\cdot z,0\cdot0)=(z,0)$ for all $(z,0)\in\mathbb{Z}\times\{0\}$ thus it is an identity element. But,  $(1,0)\ne(1,1)$. Thus, the property that $N\subseteq M$ and $\left(N,*\right)$ is a monoid does not imply that $e_M\in N$

Notice that there are similarities between group theoretic homomorphisms and monoid theoretic. For example the following theorems are common to both (or the analogues of them):

Theorem: Let $\left(M,*\right)$ and $\left(N,\star\right)$ be monoids and $\theta:M\to N$ an isomorphism. Then, $\theta^{-1}:N\to M$ is an isomorphism.

Proof: Since $\theta(e_M)=e_N$ we know that $\theta^{-1}(e_N)=e_M$. Furthermore, for any $n,n'\in N$ we have by the surjectivity of $\theta$ that $n=\theta(m)$ and $n'=\theta(n')$ for some $m,m'\in M$. Then,

\begin{aligned} \theta^{-1}\left(n\star n'\right) &=\theta^{-1}\left(\theta(m)\star\theta(m')\right)\\ &=\theta^{-1}\left(\theta(m*m')\right)\\ &=m*m'\\ &=\theta^{-1}(n)\star\theta^{-1}(n')\end{aligned}

from where the conclusion follows. $\blacksquare$

Theorem: Let $\left(M,*\right)$ and $\left(N,\star\right)$ be monoids and $\theta:M\to N$ a homomorphism. Then, if $S\leqslant M$, $\theta\left(S\right)\leqslant N$

Proof: We know that $e_M\in S$ and so $\theta(e_M)=e_N\in \theta\left(S\right)$. Also, if $\theta(m),\theta(m')\in S$ then $\theta(m)\star\theta(m')=\theta(m*m')\in \theta(S)$. The conclusion follows. $\blacksquare$

Theorem: Let $\left(M,*\right)$ and $\left(N,\star\right)$ be monoids and $\theta:M\to N$ a homomorphism. Then, if $S\leqslant N$, $\theta^{-1}\left(S\right)\leqslant M$.

Proof: We know that $S\leqslant N$ so that $e_N\in S$ and since $\theta(e_M)=e_N$ we see that $e_M\in\theta^{-1}\left(S\right)$. Furthermore, if $m,m'\in\theta^{-1}\left(S\right)$ then $\theta(m),\theta(m')\in S$ and since we assumed that $S\leqslant N$ we see that $\theta(m)\star\theta(m')=\theta(m*m')\in S$ so that $m*m'\in \theta^{-1}\left(S\right)$ from where the conclusion follows. $\blacksquare$

Similarly, operations among submonoids behave similarly, namely:

Theorem: Let $\left(M,*\right)$ be a monoid and $\left\{S_{\alpha}\right\}_{\alpha\in\mathcal{A}}$ be a non-empty class of submonoids. Then, $\displaystyle \bigcap_{\alpha\in\mathcal{A}}S_\alpha\leqslant M$

Proof: Clearly since $e_M\in S_\alpha$ for every $\alpha\in\mathcal{A}$ we see that $\displaystyle e_M\in\bigcap_{\alpha\in\mathcal{A}}S_\alpha$. Also, if $\displaystyle s,s'\in\bigcap_{\alpha\in\mathcal{A}}S_\alpha$ then $s,s'\in S_\alpha$ for every $\alpha\in\mathcal{A}$. But, since each $S_\alpha$ is a submonoid we see that $s*s'\in S_\alpha$ for every $\alpha\in\mathcal{A}$ and so $\displaystyle s*s'\in\bigcap_{\alpha\in\mathcal{A}}S_\alpha$, as required. $\blacksquare$

It’s also conceivable to take products of monoids. Namely:

Theorem: Let $\left\{\left(M_{\alpha},*_\alpha\right)\right\}_{\alpha\in\mathcal{A}}$ be a non-empty collection of monoids. Then, if one defines

$\displaystyle \prod_{\alpha\in\mathcal{A}}*_\alpha:\prod_{\alpha\in\mathcal{A}}M_\alpha\times\prod_{\alpha\in\mathcal{A}}M_\alpha\to\prod_{\alpha\in\mathcal{A}}M_\alpha:\left((m_\alpha)_{\alpha\in\mathcal{A}},(m'_\alpha)_{\alpha\in\mathcal{A}}\right)\mapsto\left(m_\alpha*_\alpha m'_\alpha\right)_{\alpha\in\mathcal{A}}$

Then, $\left(\mathscr{M},*\right)$ is a monoid where $\displaystyle \mathscr{M}=\prod_{\alpha\in\mathcal{A}}M_\alpha$  and $\displaystyle *=\prod_{\alpha\in\mathcal{A}}*_\alpha$

Remark: If one is not familiar with the notation $(m_\alpha)_{\alpha\in\mathcal{A}}$ it just means $\displaystyle \prod_{\alpha\in\mathcal{A}}\{m_\alpha\}$, or if one “extends the intuition” of an $n$-tuple to arbitrary indexing sets one can think of it as a $\text{card }\mathcal{A}$-tuple. But, writing the indexing set becomes cumbersome and so we shall write $(m_\alpha)$ for $(m_\alpha)_{\alpha\in\mathcal{A}}$

Proof: We first note that since each $*_\alpha:M_\alpha\times M_\alpha\to M_\alpha$ that $*$ is a well-defined map. Furthermore, if $(x_\alpha),(y_\alpha)$ and $(z_\alpha)$ are elements of $\mathscr{M}$ we can see that

\begin{aligned} (x_{\alpha})*\left((y_{\alpha})*(z_{\alpha})\right) &= x_\alpha *\left((y_\alpha *\alpha z_\alpha)\right)\\ & = \left((x_\alpha) *_\alpha ( y_\alpha *_\alpha z_\alpha)\right)\\ &=\left((x_\alpha *_\alpha y_\alpha) *_\alpha \right) \\ &= \left(x_\alpha *_\alpha y_\alpha\right)* (z_\alpha)\\ &=\left((x_\alpha)*(y_\alpha)\right)*(z_\alpha)\end{aligned}

so $*$ is associative. Lastly, we notice that if $e_\alpha$ is the identity element for each $M_\alpha$ then

$(x_\alpha)*(e_\alpha)=(x_\alpha *_\alpha e_\alpha)=(e_\alpha * x_\alpha)=(x_\alpha)$

for all $(x_\alpha)\in\mathscr{M}$ so that $(e_\alpha)=e\in\mathscr{M}$ is an identity element. It follows that $\left(\mathscr{M},*\right)$ is indeed a monoid. $\blacksquare$

I’d like to end this post by proving something that basically says every monoid is embeddable (isomorphic to a submonoid) into a monoid of functions. This idea comes from a simple one, namely that each element $m$ of a monoid $M$ induces an action (we’ll talk more about what this means later) on the monoid by the following maps:

$R_m:M\to M:x\mapsto x*m$

and

$L_m:M\to M:x\mapsto m*x$

called the right multiplication and left multiplication by $m$ respectively. So, with this we’re ready to formulate what was said earlier in a rigorous fashion:

Theorem: Let $\left(M,*\right)$ be a monoid and consider the monoid $M^M=\left\{f\mid f:M\to M\right\}$ with function composition. Then, there exists some function $\theta:M\hookrightarrow M^M$ such that $\theta\left(M\right)\leqslant M^M$ and $M\cong\theta\left(M\right)$.

Proof: Define

$\theta:M\hookrightarrow M^M:m\mapsto L_m$

To see that this is a monomorphism we first note that if $m\ne m'$ then clearly $m*e_M\ne m' *e_M$ so that $R_m\ne R_{m'}$, and thus $\theta$ is injective. Also, let $x\in M$ be arbitrary then,

$\theta(m*m')(x)=R_{m*m'}(x)=(m*m')*x=m*(m'*x)=m* R_{m'}(x)=R_{m}\left(R_{m'}(x)\right)$

and since $x$ was arbitrary we see that

$\theta(m*m')=R_m\circ R_{m'}=\theta(m)\circ\theta(m')$

So that $\theta$ is indeed a homomorphism. But, as was proven earlier $\theta(M)$ being the homomorphic image of a submonoid is itself a submonoid and since $\theta:M\to\theta\left(M\right)$ is a bijecitive homomorphism (i.e. an isomorphism) we may conclude that $M\cong\theta(M)\leqslant M^M$. $\blacksquare$

October 8, 2010 -