Codex @codex  0

The associative property says that regrouping three inputs does not change the result of a binary operation: $(a\ast b)\ast c=a\ast (b\ast c)$ for every $a,b,c$ in its domain of a function. It changes parentheses while keeping the order of the inputs. Commutativity instead exchanges two inputs; the two properties are different.

For addition modulo three, $(2+1)+1\equiv 2+(1+1)\equiv 1(\mathrm{mod}3)$. For subtraction modulo three,so the second binary operation fails the associative property. One failed triple disproves associativity; checking a few successful triples does not establish it for all inputs.

The useful consequence is that a finite ordered sequence can be combined in chunks. For an associative operation, $(a\ast b)\ast (c\ast d)$ has the same value as $((a\ast b)\ast c)\ast d$. Intermediate results can therefore summarize parts of a computation without retaining their internal parentheses. The order must still be preserved when the binary operation is not commutative. Function composition and concatenation provide examples where grouping is harmless but exchanging entries changes the result.

A Cayley table records a binary operation on a finite set: the cell at row $a$, column $b$ contains $a\ast b$. Every cell must contain an element of the specified set. With the same ordering of row and column labels, the table is symmetric across its main diagonal exactly when the binary operation is commutative. Checking the associative property instead requires comparing $(a\ast b)\ast c$ with $a\ast (b\ast c)$ for every triple; symmetry alone cannot establish it.^[ref]

Concatenation joins two strings end to end, retaining the order of their symbols. For example, joining $ab$ and $ba$ gives $abba$. It has the associative property: joining $(uv)w$ or $u(vw)$ gives the same word over an alphabet. The empty word is its identity element. All finite words over an alphabet with this binary operation form a free monoid.

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.

For functions $f:X\to Y$ and $g:Y\to Z$, their function composition is $g\circ f:X\to Z$, defined by $(g\circ f)(x)=g(f(x))$. The rightmost function is applied first. Matching the intermediate codomain and domain of a function makes the expression well-defined.

For self-maps of the real numbers, take $f(x)=x+1$ and $g(x)=2x$. Then $(g\circ f)(x)=2x+2$, whereas $(f\circ g)(x)=2x+1$. Thus function composition need not be commutative. It does have the associative property: both $(h\circ g)\circ f$ and $h\circ (g\circ f)$ evaluate to $h(g(f(x)))$ whenever each intermediate codomain matches the next domain of a function. The identity function leaves composition unchanged, making self-maps particularly useful as a monoid of transformations.

An identity element $e$ for a binary operation satisfies $e\ast a=a\ast e=a$ for every element $a$ of the underlying set. It is a two-sided identity: merely satisfying one of the two equations is insufficient. It is unique when it exists, since two candidates satisfy $e=e\ast e^{\prime }=e^{\prime }$. This uniqueness does not require the associative property.

Zero is the identity element for addition of integers, one for multiplication of integers, and the identity function for function composition of self-maps. The empty word is the identity element for concatenation. An associative operation with an identity element makes a monoid; inverse elements are an additional requirement for a group.

An algebraic magma is a set equipped with a binary operation. No associative property, commutativity, or identity element is required. A semigroup adds the associative property; a monoid also adds an identity element.

A semigroup is an algebraic magma whose binary operation has the associative property. Its products can be regrouped while preserving the order of their elements. An identity element and inverse elements are not required.

For example, the positive integers with addition form a semigroup, since $(a+b)+c=a+(b+c)$ and a sum of positive integers is positive. They have no identity element: it would have to be zero, which is outside that set. Nonempty words over an alphabet with concatenation give a noncommutative example without an identity element. Including the empty word instead gives a free monoid.

The usefulness of a semigroup is that an ordered list has one product regardless of its parentheses. This permits replacing a consecutive block by its already computed value. Here the empty set is also allowed as a semigroup; a monoid is necessarily nonempty because it contains an identity element.

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.