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.
Let and be monoids with identity elements and respectively. Then we see say that is a monoid homomorphism if:
1) for all
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 is a map from a group to a group 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 and be groups with identities and respectively. Then if is such that , then . To see this we merely note that and so by the cancellation property
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 and and the mapping
We clearly see that
so that has property 1). That said, we see that so does not possess property 2). Thus, we see that property 2) is, in fact, not a redundancy of property 1).
If is a monoid homomorphism and is bijective we call a monoid isomorphism and say that and are isomorphic, denoted .
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.
If is a monoid with identity element we call a submonoid if is closed under -multiplication and
Remark: This notation, the , is the same notation used for subgroup. So, be careful.
Theorem: Let be a monoid with identity element . Then, if and only if is a monoid containing .
Proof: Suppose that is a submonoid.Then, by assumption and so has an identity. Furthermore, since is closed under multiplication we know that and since is associative for all it is clearly associative for all . It follows that is a monoid.
Conversely, if is a monoid containing , then it suffices to prove that is closed under . But, since the conclusion follows.
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 is a group and then the identity for is the same as the identity for . Let’s go through the proof of this
” Let be a group and . Then, if and are the identities for and respectively . To see this let (we assumed it’s non-empty). Now, technically for we have the map and with this we see that . 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 be the monoid with multiplication given coordinate wise and with identity element . Note though that . This is evidently closed under multiplication since
We also note that for all thus it is an identity element. But, . Thus, the property that and is a monoid does not imply that
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 and be monoids and an isomorphism. Then, is an isomorphism.
Proof: Since we know that . Furthermore, for any we have by the surjectivity of that and for some . Then,
from where the conclusion follows.
Theorem: Let and be monoids and a homomorphism. Then, if ,
Proof: We know that and so . Also, if then . The conclusion follows.
Theorem: Let and be monoids and a homomorphism. Then, if , .
Proof: We know that so that and since we see that . Furthermore, if then and since we assumed that we see that so that from where the conclusion follows.
Similarly, operations among submonoids behave similarly, namely:
Theorem: Let be a monoid and be a non-empty class of submonoids. Then,
Proof: Clearly since for every we see that . Also, if then for every . But, since each is a submonoid we see that for every and so , as required.
It’s also conceivable to take products of monoids. Namely:
Theorem: Let be a non-empty collection of monoids. Then, if one defines
Then, is a monoid where and
Remark: If one is not familiar with the notation it just means , or if one “extends the intuition” of an -tuple to arbitrary indexing sets one can think of it as a -tuple. But, writing the indexing set becomes cumbersome and so we shall write for
Proof: We first note that since each that is a well-defined map. Furthermore, if and are elements of we can see that
so is associative. Lastly, we notice that if is the identity element for each then
for all so that is an identity element. It follows that is indeed a monoid.
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 of a monoid induces an action (we’ll talk more about what this means later) on the monoid by the following maps:
called the right multiplication and left multiplication by respectively. So, with this we’re ready to formulate what was said earlier in a rigorous fashion:
Theorem: Let be a monoid and consider the monoid with function composition. Then, there exists some function such that and .
To see that this is a monomorphism we first note that if then clearly so that , and thus is injective. Also, let be arbitrary then,
and since was arbitrary we see that
So that is indeed a homomorphism. But, as was proven earlier being the homomorphic image of a submonoid is itself a submonoid and since is a bijecitive homomorphism (i.e. an isomorphism) we may conclude that .