Monoid ($(M,\ast ,e)$)

A monoid is a semigroup with a two-sided identity element $e$: $e\ast a=a\ast e=a$ for every element $a$. Associativity handles the grouping of a nonempty sequence; the identity element also supplies the result for an empty sequence. This makes the same rules apply to combining zero, one, or many contributions. ^[ref].

The nonnegative integers $\{0,1,2,\dots \}$ with addition form a commutative monoid, with identity element zero. They do not form a group: a positive integer has no additive inverse in that set. All words over an alphabet with concatenation form a free monoid, whose identity element is the empty word. The full transformation monoid consists of all self-maps of a set, with function composition and the identity function.

These examples explain why monoids are useful: accumulation needs an operation and a starting value, but it need not be reversible. Adding counts, joining strings, and composing transformations all share the same grouping and identity laws. Requiring every element to have an inverse element gives a group, a stronger structure suitable for reversible operations.

An inverse element of $a$ in a monoid is an element $b$ satisfying $a\ast b=b\ast a=e$, where $e$ is the identity element. Its notation is $a^{-1}$. Some elements of a monoid can lack an inverse element; a group requires one for every element. Associativity makes a two-sided inverse element unique: if $b,c$ both invert $a$, then $b=b\ast (a\ast c)=(b\ast a)\ast c=c$.

For the full transformation monoid, a self-map has an inverse element exactly when it is a bijection; that element is its inverse function. On $\{0,1\}$, the swap $s(0)=1,s(1)=0$ is its own inverse element, while a constant function has none because it merges the two inputs.

A transformation monoid is a collection of self-maps of a fixed set $X$ that contains the identity function and is closed under function composition. The associative property comes from function composition. A monoid action describes transformations of a set that obey a monoid's multiplication and identity laws.

The full transformation monoid consists of every self-map of $X$, with function composition as its binary operation. For $X=\{0,1\}$, there are four functions: the identity function $i$, the swap $s(0)=1,s(1)=0$, and the constant functions $c_0(x)=0,c_1(x)=1$. Their composition order matters: $c_0\circ s=c_0$, whereas $s\circ c_0=c_1$. Thus associativity does not imply commutativity.

Only $i$ and $s$ are bijections, and their inverse elements are themselves. They form a two-element group within this monoid. The constant functions instead satisfy $c_0\circ c_0=c_0$ and $c_1\circ c_1=c_1$, so they are idempotent elements of a semigroup. Such irreversible transformations explain why the monoid setting is useful even when a group would be too restrictive.

A left monoid action assigns each $m\in M$ a map $a\mapsto m\cdot a$ with $1\cdot a=a$ and $(mn)\cdot a=m\cdot (n\cdot a)$. It need not be invertible or injective. A left M-set is equivalently a covariant functor from the one-object category determined by $M$.

A right monoid action has $x1=x$ and $(xm)n=x(mn)$. It is a contravariant functor from the one-object category of the monoid to sets. The regular right action is multiplication on $M$ itself. Products of right actions use the diagonal action.

Give $M\times X$ the diagonal right monoid action. On its equivariant maps into $Y$, define $(ek)(g,x)=e(kg,x)$. The evaluation map of an exponential object is $e(1,x)$ and currying of $h:Z\times X\to Y$ is $\hat{h}(z)(g,x)=h(zg,x)$. Both maps are equivariant, and they are inverse under evaluation. The left multiplication $kg$ in this right action is essential in a noncommutative monoid.

For a group, evaluation at the identity identifies the monoid exponential with all set functions $X\to Y$. Its inverse is $e_f(g,x)=f(x{g}^{-1})g$, and the resulting function action is the displayed formula. Fixed functions are precisely equivariant maps. The inverse on the input is necessary for equivariance of evaluation and for the right-action law.

An equivariant map $h:A\to B$ between left M-sets obeys $h(m\cdot a)=m\cdot h(a)$. These are the natural transformations of the corresponding functors from the one-object monoid category.

An M-set is a set carrying a monoid action. This terminology here uses left actions. Morphisms are equivariant maps of monoid sets, and the resulting functor category $[M,\mathbf{Set}]$ is an elementary topos.

A monoid homomorphism $h:M\to N$ preserves multiplication and identity: $h(xy)=h(x)h(y)$ and $h(1_M)=1_N$. It therefore preserves every finite ordered product, including the empty product. The monoids with these maps form the category $\mathbf{Mon}$.

A monoid automorphism is a bijective operation- and identity-preserving self-map of a monoid. Its inverse is also a monoid homomorphism. Permuting prime numbers and extending by prime factorization gives all automorphisms of the multiplicative monoid of positive natural numbers; extending by $0\mapsto 0$ gives automorphisms of the multiplicative monoid including zero.

The free monoid ${\Sigma }^{\ast }$ on an alphabet $\Sigma$ consists of all finite words over an alphabet, including the empty word $\epsilon$, with concatenation as its binary operation. Distinct strings represent distinct elements: there are no imposed equalities between different sequences of letters. The empty word is its identity element, and concatenation has the associative property.^[ref]

For $\Sigma =\{a,b\}$, the elements begin $\epsilon ,a,b,aa,ab,ba,bb,\dots$. Both $(ab)a$ and $a(ba)$ give the same word $aba$, but $ab\ne ba$, so this monoid is not commutative. The length of a word over an alphabet obeys $\ell (uv)=\ell (u)+\ell (v)$; it is a monoid homomorphism to the nonnegative integers with addition. A nonempty word has no inverse element, since joining it to any other word cannot decrease its length to zero.

The defining benefit of being free is that letters can stand for arbitrary elements of another monoid. Choose a value $h(a)$ for each letter $a\in \Sigma$; then $h(a_1\cdots a_n)=h(a_1)\ast \cdots \ast h(a_n)$, with $h(\epsilon )=e$, is the unique monoid homomorphism extending those choices. Associativity and the identity element make this evaluation consistent for every finite word. For example, interpreting the letters as self-maps evaluates a word as a composed transformation; interpreting them as nonnegative counts evaluates it by addition.

A commutative monoid is a monoid whose operation is commutative. The natural numbers with addition form a commutative monoid that is not an abelian group, because positive elements have no additive inverses.

The free commutative monoid on $d$ generators consists of the nonnegative integral sums of those generators, with unique coefficients. Its semigroup algebra over a commutative ring is the polynomial ring in $d$ variables. In a smooth toric chart, the dual-cone lattice points form such a monoid, yielding affine-space coordinates.

A commutative monoid is cancellative when $a+c=b+c$ implies $a=b$. Cancellation makes the natural map into its Grothendieck group injective.

For an integer $m\ge 2$, the positive integers congruent to one modulo $m$ form a cancellative commutative monoid under multiplication. The identity is one, and it is the only unit. Proper factors outside this congruence class do not witness reducibility inside the monoid. Hence irreducible elements of a commutative monoid need not coincide with ordinary prime numbers.

The congruence submonoid of the positive integers with modulus ten has four distinct irreducible elements of a commutative monoid $21,221,51,91$ with equal pairwise products. Their ordinary prime factors are respectively $(3,7),(13,17),(3,17),(7,13)$. None of these proper prime factors is congruent to one modulo ten. The Euclid lemma proves that a product of two distinct primes has no other proper positive divisors, so all four are irreducible in this monoid. This gives nonunique factorization without assuming the fundamental theorem of arithmetic.

A nonunit element of a commutative monoid is irreducible if each factorization has a unit factor. In a submonoid of the positive integers under multiplication, the only unit is one. Irreducibility is relative to the allowed factors: a composite integer can be irreducible in a smaller monoid even though it is not a prime number.

A cancellative commutative monoid is torsion-free in this sense when $na=nb$ implies $a=b$ for every positive integer $n$. Its Grothendieck group is then a torsion-free abelian group, because $n(a-b)=0$ forces $na=nb$. This is the condition inherited by a submonoid of a torsion-free abelian group.

This category has commutative monoids and their homomorphisms. Pointwise addition makes each hom-set a commutative monoid, and composition is additive in both variables. Finite cartesian products are also coproducts, using the coordinate injections with zero in the other coordinates and summing images. Therefore it is a semi-additive category, but it is not an additive category. The reflexive pair from the submonoid $\{(m,n):m\le n\le 2m\}$ of ${\mathbb{N}}^2$ to $\mathbb{N}$, using the two projections and section $m\mapsto (m,m)$, has an arrow from $1$ to $2$ and none from $2$ to $1$ in its represented graph. Thus a reflexive pair here need not yield a groupoid.