Let \(X\) be a nonempty set. A binary operation on \(X\) is a function
\[ * : X \times X \longrightarrow X \]For \((x,y) \in X \times X\), the value \(*(x,y)\) is usually denoted by \(x*y\). Because the codomain of \(*\) is \(X\), the definition includes the closure condition
\[ x,y \in X \Rightarrow x*y \in X. \]Thus “closure” is not an additional axiom once a binary operation has been defined as a map \(X \times X \rightarrow X\); it is part of the statement that the map is well defined.
- Associativity: Let \(*\) be a binary operation on a set \(X\). We say that \(*\) is associative if, for every \(x,y,z \in X\), \[ (x*y)*z = x*(y*z). \]
- Commutativity: Let \(*\) be a binary operation on a set \(X\). We say that \(*\) is commutative if, for every \(x, y \in X\), \[ x*y = y*x. \]
- Addition is a binary operation on \(\mathbb{Z}\) because \(a+b \in \mathbb{Z}\) whenever \(a, b \in \mathbb{Z}\). Multiplication is also a binary operation on \(\mathbb{Z}\).
- Nonexample: Let \(\mathbb{N}_{0} = \{0, 1, 2, \dots\}\). Subtraction is not a binary operation on \(\mathbb{N}_{0}\): although \(2, 5 \in \mathbb{N}_{0}\), we have \(2 - 5 = -3 \notin \mathbb{N}_{0}\). Hence the rule \((a,b) \mapsto a-b\) does not define a function \(\mathbb{N}_{0} \times \mathbb{N}_{0} \rightarrow \mathbb{N}_{0}\). On the other hand, subtraction is a binary operation on \(\mathbb{Z}\).
Composition of self-maps: Let \(X\) be a set and define \(\text{End}(X) = \{f : f: X \rightarrow X\}\). If \(f, g \in \text{End}(X)\) and \(x \in X\), then \(g(x) \in X\) so \(f(g(x))\) is defined and lies in \(X\). Therefore
\[ (f \circ g)(x) = f(g(x)) \]defines another element \(f \circ g \in \text{End}(X)\). Thus composition is a binary operation on \(\text{End}(X)\).
A magma is a pair \((M, *)\) consisting of a nonempty set \(M\) and a binary operation \(*: M \times M \rightarrow M\).
No associativity, identity, inverse, or commutativity condition is imposed in the definition of a magma.
1. Subtraction: The pair \((\mathbb{Z}, -)\) is a magma. It is not associative, because
\[ (5 - 3) - 1 = 1 \ne 3 = 5 - (3 - 1), \]and it is not commutative, because \(5 - 3 = 2 \ne -2 = 3 - 5\).
2. Rock-paper-scissors: Let \(M = \{R, P, S\}\), where \(R, P, S\) denote rock, paper, and scissors. Define \(x*y\) to be the winner when \(x\) and \(y\) are played against one another, with a tie returning the common choice. The operation table is
| \(*\) | \(R\) | \(P\) | \(S\) |
|---|---|---|---|
| \(R\) | \(R\) | \(P\) | \(R\) |
| \(P\) | \(P\) | \(P\) | \(S\) |
| \(S\) | \(R\) | \(S\) | \(S\) |
Every entry of the table belongs to \(M\), so this is a binary operation. The table is symmetric about the main diagonal, hence \(x*y = y*x\) for every \(x,y \in M\); the magma is commutative. However,
\[ (R*P)*S = P*S = S \]whereas \(R*(P*S) = R*S = R\). Thus \(*\) is not associative. This gives a concrete example showing that commutativity does not imply associativity.
Let \((M, *)\) and \((N, \circ)\) be magmas. A function \(\varphi : M \longrightarrow N\) is a magma homomorphism if, for every \(x,y \in M\),
\[ \varphi(x*y) = \varphi(x) \circ \varphi(y). \]A bijective magma homomorphism from \(M\) to itself is called a magma automorphism.
For the preceding magma, define
\[ \varphi(R) = P, \quad \varphi(P) = S, \quad \varphi(S) = R. \]The map \(\varphi\) is bijective. To verify the homomorphism condition, note that \(\varphi\) cyclically relabels the three choices while preserving the cyclic winning relation: \(P\) beats \(R\), \(S\) beats \(P\), \(R\) beats \(S\). It also preserves ties. Hence, for each of the nine pairs \((x,y) \in M^{2}\), the winner of \(\varphi(x)\) and \(\varphi(y)\) is the image under \(\varphi\) of the winner of \(x\) and \(y\). Therefore
\[ \varphi(x*y) = \varphi(x) * \varphi(y) \]for all \(x,y \in M\). Thus \(\varphi\) is a magma automorphism. Moreover, \(\varphi^{3} = \text{id}_{M}\).
A semigroup is a magma \((S, *)\) whose binary operation is associative; that is,
\[ (x*y)*z = x*(y*z) \]for all \(x, y, z \in S\).
Let \((S, *)\) be a semigroup and let \(x_{1}, \dots, x_{n} \in S\), where \(n \ge 2\). Then every parenthesized product formed from
\[ x_{1} * x_{2} * \dots * x_{n} \]without changing the order of the factors has the same value.
Proof: We use strong induction on \(n\). For \(n=2\) there is only one product. Suppose \(n \ge 3\) and assume that the statement is true for all products involving fewer than \(n\) factors. Any full parenthesization has a final multiplication of the form \(P*Q\), where \(P\) is a parenthesized product of \(x_{1}, \dots, x_{k}\) and \(Q\) is a parenthesized product of \(x_{k+1}, \dots, x_{n}\) for some \(1 \le k < n\). By the induction hypothesis, the values of \(P\) and \(Q\) do not depend on their internal parentheses. Associativity permits the final split to be moved successively to the right; for example,
\[ (x_{1} \dots x_{k})(x_{k+1} \dots x_{n}) = ((x_{1} \dots x_{k})x_{k+1})(x_{k+2} \dots x_{n}). \]Repeating this step gives the left-associated product
\[ (((x_{1} * x_{2}) * x_{3}) * \dots) * x_{n}. \]Therefore every parenthesization has the same value. ∎
Consequently, in a semigroup one may write a finite product such as \(x_{1}x_{2}\dots x_{n}\) without specifying parentheses.
- Let \(\mathbb{N}_{>0} = \{1, 2, 3, \dots\}\). Then \((\mathbb{N}_{>0}, +)\) is a commutative semigroup. Closure follows because the sum of two positive integers is positive, and associativity and commutativity are inherited from integer addition. It is not a monoid: if \(e \in \mathbb{N}_{>0}\) were an additive identity, then \(e+1=1\), so \(e=0\), contradicting \(0 \notin \mathbb{N}_{>0}\).
- Words: Let \(A\) be an alphabet and let \(A^{+}\) be the set of all nonempty finite words whose letters lie in \(A\). For words \(u, v\), let \(uv\) denote concatenation. Concatenating two nonempty finite words again gives a nonempty finite word, so the operation is closed. Moreover, \((uv)w = u(vw)\) because both sides are the word obtained by writing the letters of \(u\), then \(v\), then \(w\). Thus \(A^{+}\) is a semigroup. It has no identity because the only possible identity for concatenation is the empty word, which is not in \(A^{+}\).
- Left-zero semigroup: Let \(S\) be a nonempty set and define \(x*y = x\) for all \(x, y \in S\). For all \(x, y, z \in S\), \[ (x*y)*z = x*z = x \quad \text{and} \quad x*(y*z) = x*y = x. \] Hence the operation is associative, so \((S, *)\) is a semigroup.
Let \((S, *)\) be a semigroup. An element \(a \in S\) is idempotent if
\[ a*a = a. \]In multiplicative notation this is written \(a^{2} = a\).
Example: Let \(X\) be a set. If \(f : X \rightarrow X\) satisfies \(f \circ f = f\), then \(f\) is an idempotent element of the semigroup \(\text{End}(X)\) under composition.
A semigroup \((S, *)\) is called commutative if \(x*y = y*x\) for all \(x, y \in S\).
- Power set: For a set \(X\), the power set of \(X\) is \(\mathcal{P}(X) = \{A : A \subseteq X\}\). \((\mathcal{P}(X), \cup)\) is a commutative semigroup. Closure holds because \(A \cup B \subseteq X\) whenever \(A, B \subseteq X\). For \(A, B, C \subseteq X\), \[ (A \cup B) \cup C = A \cup (B \cup C) \] because an element belongs to either side exactly when it lies in at least one of \(A, B, C\). Also \(A \cup B = B \cup A\). The same elementwise argument shows that \((\mathcal{P}(X), \cap)\) is a commutative semigroup.
- On \(\mathbb{R}\), define \(x*y = \max\{x, y\}\). Then \[ \max\{\max\{x,y\}, z\} = \max\{x, y, z\} = \max\{x, \max\{y,z\}\}, \] so \(*\) is associative. It is also commutative. Hence \((\mathbb{R}, \max)\) is a commutative semigroup. The same proof applies to \((\mathbb{R}, \min)\).
- A noncommutative semigroup: Composition is associative on \(\text{End}(\mathbb{R})\). It need not be commutative: if \(f(x) = x+1\) and \(g(x) = 2x\), then \((f \circ g)(x) = 2x+1\) and \((g \circ f)(x) = 2x+2\). Therefore \(f \circ g \ne g \circ f\).
A monoid is a semigroup \((M, *)\) for which there exists an element \(e \in M\) such that
\[ e*x = x*e = x \]for every \(x \in M\). Such an element is called an identity element.
A monoid has a unique identity element.
Proof: Existence is part of the definition. For uniqueness, suppose that \(e, e^{\prime} \in M\) are both identity elements. Because \(e\) is a left identity, \(e*e^{\prime} = e^{\prime}\). Because \(e^{\prime}\) is a right identity, \(e*e^{\prime} = e\). Thus \(e = e^{\prime}\). ∎
Let \((M, *)\) be a monoid with identity \(e\). An element \(x \in M\) is called a unit, or invertible, if there exists \(y \in M\) such that
\[ x*y = e \quad \text{and} \quad y*x = e. \]Such an element \(y\) is called an inverse of \(x\).
If an element of a monoid is invertible, then its inverse is unique.
Proof: Let \(x \in M\) and suppose \(y, z \in M\) are both inverses of \(x\). Then \(y*x = e\) and \(x*z = e\). Using the identity law and associativity,
\[ y = y*e = y*(x*z) = (y*x)*z = e*z = z. \]Hence \(y=z\). ∎
The unique inverse of a unit \(x\) is denoted by \(x^{-1}\).
- The set \((\mathbb{N}_{0}, +)\) is a commutative monoid with identity \(0\). If \(m>0\), there is no \(n \in \mathbb{N}_{0}\) such that \(m+n=0\). Thus the only invertible element is \(0\).
- The set \((\mathbb{N}_{0}, \cdot)\) is a commutative monoid with identity \(1\). Its only unit is \(1\): if \(mn=1\) with \(m, n \in \mathbb{N}_{0}\), then necessarily \(m=n=1\).
- Free monoid: Let \(A^{*}\) be the set of all finite words over an alphabet \(A\), now including the empty word \(\epsilon\). Concatenation is associative, and \(\epsilon w = w = w \epsilon\) for every word \(w\). Hence \(A^{*}\) is a monoid with identity \(\epsilon\).
- Matrices under multiplication: Let \(F\) be a field. The set \(M_{n}(F)\) is a monoid under matrix multiplication. Closure and associativity are standard properties of matrix multiplication, and the identity matrix \(I_{n}\) satisfies \(I_{n}A = A = AI_{n}\) for every \(A \in M_{n}(F)\). Not every element is invertible: for example, the zero matrix has no multiplicative inverse.
- Traffic-light monoid: Let \(L = \{G, Y, R\}\) and define \(G < Y < R\) and \(x*y = \max\{x, y\}\). As in the real-number maximum example, \(*\) is associative and commutative. Moreover, \(G*x = \max\{G, x\} = x = x*G\), so \(G\) is the identity. If \(x\) is invertible, there must exist \(y \in L\) with \(\max\{x, y\} = G\). Since \(G\) is the least element of \(L\), this forces \(x=y=G\). Hence \(G\) is the only unit of this monoid.
- A one-sided inverse need not be two-sided: Define \(S, P : \mathbb{N}_{0} \rightarrow \mathbb{N}_{0}\) by \[ S(n) = n+1, \quad P(n) = \begin{cases} 0, & n=0, \\ n-1, & n \ge 1. \end{cases} \] For every \(n \in \mathbb{N}_{0}\), \((P \circ S)(n) = P(n+1) = n\), so \(P \circ S = \text{id}_{\mathbb{N}_{0}}\). However, \((S \circ P)(0) = S(0) = 1 \ne 0\), so \(S \circ P \ne \text{id}_{\mathbb{N}_{0}}\). Thus, in the monoid \(\text{End}(\mathbb{N}_{0})\), a left inverse need not also be a right inverse.
A group is a monoid \((G, *)\) in which every element is a unit. Equivalently, a group is a pair \((G, *)\) consisting of a nonempty set \(G\) and a binary operation \(*: G \times G \rightarrow G\) satisfying the following axioms:
- Associativity: for all \(x, y, z \in G\), \[ (x*y)*z = x*(y*z). \]
- Identity: there exists \(e \in G\) such that, for all \(x \in G\), \[ e*x = x*e = x. \]
- Inverses: for every \(x \in G\) there exists \(y \in G\) such that \[ x*y = y*x = e. \]
By the preceding lemmas, the identity of a group is unique, and each element has a unique inverse.
- The additive group \((\mathbb{Z}, +)\) is a group. Closure and associativity follow from integer addition; \(0\) is the identity; and the inverse of \(n \in \mathbb{Z}\) is \(-n\). Since \(m+n = n+m\), the group is abelian.
- The nonzero real numbers \(\mathbb{R}^{\times} = \mathbb{R} \setminus \{0\}\) form an abelian group under multiplication. The product of nonzero real numbers is nonzero, multiplication is associative, the identity is \(1\), and the inverse of \(x \ne 0\) is \(x^{-1} = 1/x\). Real multiplication is commutative.
- Symmetric group: Let \(X\) be a set. The set \(\text{Sym}(X)\) of all bijections \(X \rightarrow X\) is a group under composition. The composite of two bijections is a bijection; composition is associative; the identity map \(\text{id}_{X}\) is the identity element; and every bijection \(f\) has a bijective inverse function \(f^{-1}\). If \(X = \{1, \dots, n\}\), this group is denoted by \(S_{n}\).
- Matrices under addition: The set \(M_{n}(\mathbb{R})\) is an abelian group under matrix addition. If \(A = (a_{ij})\) and \(B = (b_{ij})\) then \(A+B = (a_{ij} + b_{ij}) \in M_{n}(\mathbb{R})\), so the operation is closed. Associativity and commutativity hold entrywise. The zero matrix is the identity, and the inverse of \(A\) is \(-A = (-a_{ij})\).
- General linear group: Let \(F\) be a field. The invertible matrices \[ GL_{n}(F) = \{A \in M_{n}(F) : A \text{ is invertible}\} \] form a group under matrix multiplication. If \(A, B\) are invertible, then \(AB\) is invertible with \((AB)^{-1} = B^{-1}A^{-1}\), so the operation is closed on \(GL_{n}(F)\). Associativity is inherited from matrix multiplication, \(I_{n}\) is the identity, and each element has an inverse by definition.
A group \((G, *)\) is abelian if for all \(x, y \in G\),
\[ x*y = y*x. \]Thus \((\mathbb{Z}, +)\), \((\mathbb{R}^{\times}, \cdot)\), \(\mathbb{Z}/n\mathbb{Z}\), and \((M_{n}(\mathbb{R}), +)\) are abelian. The groups \(S_{n}\) for \(n \ge 3\) and \(GL_{n}(F)\) for \(n \ge 2\) need not be abelian.
The implications
\[ \text{group} \Rightarrow \text{monoid} \Rightarrow \text{semigroup} \Rightarrow \text{magma} \]follow directly from the definitions. None of the reverse implications is valid in general:
- \((\mathbb{Z}, -)\) is a magma but not a semigroup;
- \((\mathbb{N}, +)\) is a semigroup but not a monoid;
- \((\mathbb{N}_{0}, +)\) is a monoid but not a group.
| Structure | Binary op | Associative | Identity | Invertible |
|---|---|---|---|---|
| Magma | ✓ | - | - | - |
| Semigroup | ✓ | ✓ | - | - |
| Monoid | ✓ | ✓ | ✓ | - |
| Group | ✓ | ✓ | ✓ | ✓ |
Commutativity is an additional condition independent of the four columns.