Monoid

From AoPSWiki

A monoid is a set $S$ closed under an operation $\times$ which is defined everywhere on $S$ , is associative, and has an identity in $S$ . That is, $M = (S, \times)$ is a monoid if and only if

There is a well-defined element $a \times b$ of $S$ , for all $a,b \in S$ ;
$a \times (b \times c) = (a \times b)\times c$ for all $a, b, c \in S$ ;
There is an element $e \in S$ such that $e\times a = a \times e = a$ for all $a \in S$ .

Alternatively, a monoid can be thought of as a group without inverses, or as an associative magma with an identity.

By abuse of notation, we often identity a monoid with its underlying set. That is, we often refer to a monoid $(S,\times)$ simply as the monoid $S$ , when there is no risk of confusion.

Because the conditions on monoids are so weak, there are very few theorems of "monoid theory." However, monoids do arise from time to time in the study of abstract algebra, and many objects (such as all groups, as well as any ring with respect to either of its operations) are in fact monoids.

Monoid Operating on a Set

Let $M$ be a monoid whose law of composition is written multiplicatively and whose identity is $e$ , and let $S$ be a set. Let $S^S$ be the set of functions on $S$ . We call a mapping $a \mapsto f_a$ from $M$ to $S^S$ a left operation of $M$ on $S$ if $f_e$ is the identity map on $S$ and for all $a,b$ in $M$ , $f_{ab} = f_a \circ f_b .$ (A right operation is defined similarly, except that $f_{ab} = f_b \circ f_a$ .) In other words, a left operation of $M$ on $S$ is a homomorphism from the monoid $M$ to the monoid $S^S$ ; a right operation is a homomorphism into the opposite monoid of $S^S$ .

We may also say that $M$ acts on $S$ . A set $S$ with an action of a monoid $M$ on $S$ is called an $M$ -set.

We say that a monoid's action on $S$ is faithful if the mapping $a\mapsto f_a$ is injective, i.e., for any distinct $a,b\in M$ , there exists some $x\in S$ for which $f_a(x) \neq f_b(x)$ .

Every monoid acts on the set of its elements.

Often one speaks of groups acting on sets. Since elements groups must have unique inverses, for every $a$ in a group $G$ acting on a set $S$ , the function $f_a$ must be a bijection.

If $x$ is an element of $S$ , and $a$ is an element of a monoid $M$ with a left operation on $S$ , we often write $f_a(x)$ simply as $ax$ , when there is no risk of confusion. Then we may rewrite our criteria thus, for $a,b$ in $M$ and $x$ in $S$ .