Abstract Nonsense

Category Theory: Monoids (Part I)

Point of Post: To give a perfunctory background into monoid theory, in preparation for their appearance as both an object of study, and method to study categories.

What is a monoid?

In essence a monoid is a group without inverses. Said differently, a monoid is just a set with an associative binary operation and an identity element. In fact, as we’ll see in the examples monoids come up quite often.

If you remember back to your days of group theory, you were often consternated by sets which just barely didn’t qualify as groups. More often than not, it was because they lacked inverses. $\mathbb{N}$ with addition, $\mathbb{Z}$ with multiplication, $\mathbb{R}$ with multiplication,  etc. In all these cases (and much more) the structure is actually a monoid (a commutative monoid). Also, categories can be seen as somewhat of a generalization of monoids, in some sense. In fact, not only is every monoid a category (as was commented on in the last post) but there is a natural (not in the categorical sense) to turn a category into a monoid. We’ll discuss this later. So, let us give the definition

Definition

A monoid $\left(M,\mu\right)$ is a set $M$, and a binary operation

$\mu:M\times M\to M$

such that:

a) $\mu$ is associative, in the sense that

$\mu\left(x,\mu(y,z)\right)=\mu\left(\mu(x,y),z\right)$

for all $x,y,z\in M$.

b) There exists some element $e\in M$ such that

$\mu_{\mid{\{e\}\times M}}=\mu_{\mid{M\times\{e\}}}=\text{id}_M$

Remark: It is common practice to drop the function notation $\mu$ in lieu of concatenation. Meaning, instead of having to write $\mu(x,y)$ all the time, we simply let $xy$ to mean $\mu(x,y)$. With this in mind the, admittedly menacing, axioms above become the friendly lookin

a) For all $x,y,z\in M$ it’s true that $x(yz)=(xy)z$

b) There exists some $e\in M$ such that $ex=xe=x$ for all $x\in M$

So, we now state some examples so that the reader can see the diversity in which monoids appear

Examples

Along with the previous mentioned examples, and all groups, the following are monoids:

Example: Let $X$ be a set and let $M=\left\{f:X\to X\mid f\text{ is right invertible}\right\}$. We claim that $\left(M,\circ\right)$ where $\circ$ is normal function composition forms a monoid.

To see this we first must show that $\circ$ is really a well-defined map $M\times M\to M$, but this is equivalent to showing that if $f,g:X\to X$ are right invertible, then so is $g\circ f$. But, this is clear since there exists some $\tilde{f}$ and some $\tilde{g}$ which map $X\to X$ such that $f\tilde{f}=g\tilde{g}=\text{id}_X$. So then, $\tilde{f}\circ\tilde{g}:X\to X$ and

$\left(g\circ f\right)\circ\left(\tilde{f}\circ\tilde{g}\right)=g\circ\left(f\circ\tilde{f}\right)\circ\tilde{g}=g\circ\text{id}_X\circ\tilde{g}=g\circ\tilde{g}=\text{id}_X$

so that $g\circ f$ is indeed right invertible

Next, we need to check that $\circ$ is associative, but this is true since it’s just plain function composition. Thus, all that remains is to find an identity element, but since the identity map $\text{id}:X\to X$ is right invertible we have that $\text{id}_X\in M$ and evidently $f\circ\text{id}_X=\text{id}_X\circ f=f$ for all $f\in M$ from where the conclusion follows.

Example: Let $\mathfrak{M}_2=\left\{\begin{bmatrix}a & b \\ c & d\end{bmatrix}:a,b,c,d\in F\right\}$ for any field $F$. Then, $\left(\mathfrak{M}_2,\cdot\right)$ where $\cdot$ is the normal matrix multiplication is a monoid with identity element $I$ (the identity matrix)

Example: Let $M$ be a monoid, then $\mathcal{P}\left(M\right)$ with $XY=\left\{xy:x\in X\text{ and }y\in Y\right\}$ is a monoid.

Remark: This maybe isn’t so obvious since it’s clearly not true for groups. So, we’ll prove it.

We first note that clearly if $X,Y\subseteq M$ then $XY=\left\{xy:x\in X\text{ and }y\in Y\right\}\subseteq M$ since we assumed that $M$ was closed under multiplication. So $(X,Y)\mapsto XY$ is indeed a binary operation.

Let $X,Y,Z\in\mathcal{P}\left(M\right)$ and let $\alpha\in X(YZ)$ then $\alpha=x(yz)$ for some $x\in X, y\in Y$ and $z\in Z$. But, since we assumed that $M$ was a monoid it follows that $\alpha=x(yz)=(xy)z$ and so $\alpha\in (XY)Z$. The reverse is done similarly: let $\alpha\in (XY)Z$, then $\alpha=(xy)z$ for some $x\in X,y\in Y$ and $z\in Z$. But, since monoid multiplication is always associative we see that $\alpha=(xy)z=x(yz)$ so that $\alpha\in X(YZ)$. It follows that $X(YZ)=(XY)Z$ so that the prescribed multiplication on $\mathcal{P}\left(M\right)$ is associative.

Furthermore, let $e$ be the identity element of $M$, then $\{e\}\subseteq \mathcal{P}\left(M\right)$ and

$\{e\}X=\left\{ex:x\in X\right\}=\left\{x:x\in X\right\}=X=\left\{xe:x\in X\right\}=X\{e\}$

The following theorem for monoids will prove useful, namely

Theorem: Let $M$  be a monoid, then the identity element $e$ of $M$ is unique

Proof: Let $e'\in M$ be another such element with the property that $xe'=e'x=x$ for all $x\in X$. Then, combining this with the same property for $e$ we get

$e=ee'=e'$

from where the conclusion follows. $\blacksquare$

October 8, 2010 -

1. […] often because of their generality one can create very exotic types of monoids. In this post we derive a very interesting one involving the ‘extended’ natural numbers […]

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

2. […] 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 […]

Pingback by Category Theory: Monoids Part II: Monoid Homomorphisms and Submonoids « Abstract Nonsense | March 29, 2011 | Reply

3. […] An ordered triple is called a ring if is an abelian group and is an associative binary operation such that and for all (this is known as distributivity). If is a commutative binary operation we call a commutative ring. If there exists such that for all we say that is unital or that has . This , if it exists, is called the multiplicative identity for and it’s clear that it is unique (this follows since is a monoid). […]

Pingback by Basic Definitions of Rings « Abstract Nonsense | June 15, 2011 | Reply

4. […] Let be a monoid where every element has a left inverse . Then, every element of has a two-sided inverse and […]

Pingback by Definition and Basics of Ideals « Abstract Nonsense | June 21, 2011 | Reply

5. […] with the sum and product of ideals takes on a name. Namely, a set is called a semiring if is a commutative monoid with identity , is a semiring, left and right distributes over , and finally . What we now claim […]

Pingback by Semiring of Ideals « Abstract Nonsense | June 23, 2011 | Reply

6. […] evidently and form an abelian group (one can check this is where you need that is abelian) and monoid (with unit equal to the identity map ) respectively and thus it suffices to show distributivity. […]

Pingback by Endomorphism Ring of an Abelian Group « Abstract Nonsense | July 10, 2011 | Reply

7. […] is the category of all monoids with monoid […]

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

8. […] we have a monoid . We have then discussed how can be viewed as a category with , , and the composition of elements […]

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

9. […] The category of abelian groups is a subcategory of the category of groups which in turn is a subcategory of the category of monoids. […]

Pingback by Subcategories and Skeleta « Abstract Nonsense | December 27, 2011 | Reply

10. […] of an abelian category should look pretty familiar, because just as a category with one object is a monoid an -category with one object is just a ring. To go from a -category to a preadditive category we […]

Pingback by Ab-categories and Preadditive Categories (Pt. I) « Abstract Nonsense | January 2, 2012 | Reply

11. […] be a monoid and a field. A character is a monoid homomorphism . Of course we have a -vector space of all […]

Pingback by Maps of Extensions and the Galois Group (Pt. II) « Abstract Nonsense | April 24, 2012 | Reply