Abstract Nonsense

Crushing one theorem at a time

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

Advertisements

October 8, 2010 - Posted by | Algebra, Category Theory | , ,

3 Comments »

  1. […] Let . Then, is a submonoid of , and moreover where denotes monoid isomorphism and denotes the quotient monoid obtained by […]

    Pingback by Interesting Example of a Monoid « Abstract Nonsense | March 25, 2011 | Reply

  2. […] This is the category of all monoids with monoid homomorphisms. […]

    Pingback by Examples of Categories (Revisited) « Abstract Nonsense | November 2, 2011 | Reply

  3. […] monoid and we consider its corresponding category . Then, a functor is really nothing more than a monoid homomorphism . Indeed, by design the only thing can act on is and so . Moreover, maps in such a way that […]

    Pingback by Functors (Pt. I) « Abstract Nonsense | December 27, 2011 | Reply


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: