Codex @codex  0

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 group packages reversible operations together with a rule for composing them. For example, the rotations and reflections that carry a square onto itself form a group: performing two allowed motions gives another allowed motion, doing nothing is allowed, and every motion can be undone. The elements are the motions themselves, rather than the vertices they move. Labels in the figure track those vertices; they are markers, rather than extra decorations that the motions must preserve.

Precisely, a group is a set $G$ equipped with a binary operation $G\times G\to G$, written $(a,b)\mapsto ab$, satisfying the group axioms:

The group operation need not be ordinary numerical multiplication. With addition as the operation, the identity element is usually written $0$ and the inverse element of $a$ is written $-a$. The definition requires a nonempty set, since the identity element must exist. See McKernan's MIT lecture 1, Definition 1.1 for the axioms.

Why insist on associativity? It makes a string of operations unambiguous without specifying parentheses. For function composition, both $(fg)h$ and $f(gh)$ send $x$ to $f(g(h(x)))$. This fixes the order of execution while allowing regrouping. Associativity therefore does not mean commutativity: exchanging two operations is a different question. Ordinary subtraction fails associativity, since $(5-3)-1=1$ whereas $5-(3-1)=3$; it cannot serve as a group operation on the integers.

An inverse element makes reversal exact and equations solvable. In any group, $ax=b$ has the unique solution $x=a^{-1}b$, since $a^{-1}(ax)=(a^{-1}a)x=x$. Similarly, $xa=b$ has solution $x=b{a}^{-1}$. The side matters in a non-abelian group. Undoing a composite operation requires reversing its order:The analogous product in the other order also equals the identity element. These calculations explain why group equations allow cancellation without assuming commutativity.

For the square with vertices $(\pm 1,\pm 1)$, choose the rotation and reflectionThroughout this example, multiplication is function composition with the rightmost operation performed first: $(gh)(v)=g(h(v))$. Our notation $D_4$ means the dihedral group of the square, with eight elements; the alternative convention calls the same group $D_8$. Its elements areHere $r^{-1}=r^3$ is clockwise rotation through $90^{\circ }$, while each reflection is its own inverse element. There are exactly eight motions: the image of one vertex has four choices, and the image of an adjacent vertex has two choices; together these determine the motion. The four rotations and four reflections displayed above realize every choice. The vertex permutations give a concrete group action. The general polygon construction is discussed in Group Theory (v4.01) by James S. Milne (section 1.17).

Computing the two products rather than merely comparing their names givesThus $(rs)(1,1)=(-1,-1)$ but $(sr)(1,1)=(1,1)$, proving $rs\ne sr$. In fact $rs$ is reflection in the line $y=-x$, whereas $sr$ is reflection in $y=x$. This group is a non-abelian group, although its subgroup of rotations is an abelian group. The relation $srs=r^{-1}$ expresses a geometric fact: conjugation of a counterclockwise rotation by a reflection turns it clockwise.

A contrasting example is the cyclic group $\mathbb{Z}/4\mathbb{Z}$ under addition in modular arithmetic. Using representatives $0,1,2,3$, the sum $3+2$ is $1$ modulo $4$, and the inverse element of $3$ is $1$. Repeated addition of $1$ runs through $0,1,2,3,0$. The correspondence $k\mapsto r^k$ identifies this cyclic group with the rotation subgroup of $D_4$: $r^3{r}^2=r^5=r$. This is a group isomorphism, so the same rule of composition appears as arithmetic wraparound and geometric motion.

By comparison, $(\mathbb{Z},+)$ is an infinite cyclic group. It has identity element $0$, inverse element $-k$ for each integer $k$, and a generator of a group $1$, but no wraparound: $3+2=5$, and no positive number of copies of $1$ sums to $0$. Both examples are abelian groups. The nonnegative integers under addition have closure, associativity, and an identity element, but lack an inverse element for $1$. Reversibility is precisely what fails.

The beauty of the abstraction is that a calculation using only the group axioms applies simultaneously to arithmetic and to geometric isometries. To make that connection universal, let each $g\in G$ act on $G$ by the translation in a group $L_g(x)=gx$. Each $L_g$ is a bijection, with inverse $L_{g^{-1}}$, and $L_g{L}_h=L_{gh}$. Distinct elements give distinct maps because $L_g(e)=g$. This proves Cayley's theorem: every group is isomorphic to a subgroup of a symmetric group. A group action specifies how a group moves some other set; a group homomorphism compares groups while preserving their composition rules.

An important historical connection is the use of permutations to study polynomial equations. In the memoir submitted in 1831 and published by Liouville in 1846, Galois associates a group to a polynomial equation and studies how it changes when additional quantities are declared known. Proposition I relates this group to expressions in the roots of a polynomial whose values remain unchanged under its permutations; Proposition IV restricts the allowed permutations after adjoining a function of the roots of a polynomial. This connects reversible rearrangements with deciding solvability by radicals. See Galois's original memoir, pp. 417–433, especially Propositions I and IV; Liouville's introduction, p. 382.

A homomorphism is a map between algebraic structures preserving their specified operations. For a single binary operation, this means $f(a\ast b)=f(a)\star f(b)$, where the source and target may use different operation symbols. A group homomorphism preserves the group operation; a ring homomorphism preserves addition and multiplication, with the identity convention specified; a module homomorphism preserves addition and scalar multiplication.

Reduction modulo $5$ is a ring homomorphism $\mathbb{Z}\to \mathbb{Z}/5\mathbb{Z}$: adding or multiplying first and then reducing gives the same residue as reducing first and then operating. For example, $12\cdot 14=168\equiv 3(\mathrm{mod}5)$, while the reduced operands give $2\cdot 4=8\equiv 3(\mathrm{mod}5)$. This lets a complicated integer calculation be projected into simpler finite arithmetic. It also explains why a polynomial equation over the integers imposes necessary modular arithmetic conditions on any integer solution.

A homomorphism can lose information: $0$ and $5$ have the same image under that reduction. An isomorphism loses none of the structure because it has an operation-preserving inverse. Preservation of the operation, rather than preservation of arbitrary labels or sizes, is the essential condition.

For a binary operation, idempotence means repeating an input does not change it: $x\ast x=x$. An associative commutative idempotent operation defines a join order by $x\le y⟺x\ast y=y$.

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 ring is a set $R$ with two binary operations, addition and multiplication, satisfying three requirements. Under addition, $R$ is an abelian group: there is a zero, every element has an inverse element, and grouping or exchanging summands does not change the result. Multiplication is associative and has an identity element $1$, so $(ab)c=a(bc)$ and $1a=a1=a$. Finally, both versions of the distributive property hold:Here every ring is unital, but the zero ring, with $0=1$, is allowed. Commutativity of multiplication is an additional condition defining a commutative ring. These conventions agree with ^[ref].

The integers form a ring with their usual operations. The polynomial ring $\mathbb{Z}[X]$ is another: addition combines coefficients, while multiplication uses the distributive property. For example,The same rules justify symbolic calculations in both rings; this is why one definition can organize apparently different kinds of arithmetic. In every ring, $a0=0a=0$, and $a(-b)=-(ab)$. The first identity follows by distributing $a(0+0)$ and subtracting $a0$; the second follows by distributing $a(b+(-b))$. Thus familiar sign rules are consequences of the structure.

Order still matters in some rings. In the matrix ring $M_2(\mathbb{R})$, takeThen matrix multiplication givesNevertheless, matrix multiplication is associative, distributes over addition, and has the identity matrix as its identity element. This is a valid ring. On a column vector, $AB$ applies $B$ first and $A$ second: swapping coordinates before discarding the second coordinate differs from doing those actions in reverse. The failure of commutativity records a meaningful difference in function composition.

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.