Binary operations and the group axioms
Adding integers, multiplying nonzero fractions and composing bijections look like three different activities. Which few rules do they share that let you solve an equation like a \ast x = b, and what can be proved from those rules alone, once for all three?
Where you are 6 in Groups
Why this exists
To solve 5 + x = 2 in \mathbb{Z}, add -5 on the left and regroup: x = (-5 + 5) + x = -5 + (5 + x) = -5 + 2 = -3. To solve 3x = 7 in the nonzero rationals, multiply on the left by \tfrac{1}{3} and regroup the same way. To find a bijection g with f \circ g = h, compose on the left with f^{-1} (Composing functions between sets, and when an inverse exists). Each solution used three facts: the operation can be regrouped, some element changes nothing, and the given element can be undone. A group is any set with an operation obeying those three facts, and a theorem proved from them holds for every such set at once.
Definition
Binary operation. A binary operation on a set S is a function \ast : S \times S \to S (Cartesian product), whose value at (a, b) is written a \ast b. Being a function into S packs in three requirements: a \ast b is defined for every ordered pair; it is one element, not depending on how a or b is written (it is well defined); and it lies in S (S is closed under \ast).
Let \ast be a binary operation on S.
- \ast is associative if (a \ast b) \ast c = a \ast (b \ast c) for all a, b, c \in S, and commutative if a \ast b = b \ast a for all a, b \in S.
- e \in S is an identity element if e \ast a = a \ast e = a for every a \in S. If only e \ast a = a holds for every a, it is a left identity; if only a \ast e = a, a right identity.
- Given an identity e, b is an inverse of a if a \ast b = b \ast a = e; if only b \ast a = e, a left inverse; if only a \ast b = e, a right inverse.
Group. A group (G, \ast) is a set G with a binary operation \ast on G satisfying the group axioms:
- \ast is associative;
- G has an identity element e;
- every a \in G has an inverse in G.
A group is abelian if \ast is also commutative. It is finite if G is a finite set, and then its order is |G|; otherwise it is infinite. By Theorems 1 and 2 below the identity is unique and so is the inverse of each a, written a^{-1}. When the operation is addition, as in (\mathbb{Z}, +), the identity is 0 and the inverse of a is -a.
Operation table. For a finite set, the operation table (or Cayley table) has a row and a column for each element, with a \ast b in row a, column b.
Intuition
A table shows some axioms at a glance. An identity is an element whose row copies the column headings and whose column copies the row headings; b is an inverse of a when e sits at row a, column b and at row b, column a; commutativity is symmetry about the main diagonal. Associativity is the axiom a table hides: for n elements it is n^3 equations, so it is usually inherited from addition, multiplication or composition.
In a group, a \ast x = b has exactly one solution, so each row lists every element once (Corollary 6). Most tables fail that test.
Results
Throughout, \ast is a binary operation on a set S, and G is a group.
Theorem 1 (one identity). If e is a left identity and e' is a right identity, then e = e'. In particular S has at most one identity.
Theorem 2 (one inverse). Suppose \ast is associative with identity e. If b \ast a = e and a \ast c = e, then b = c. In particular each a has at most one inverse.
Theorem 3 (inverses of products). For all a, b \in G, (a \ast b)^{-1} = b^{-1} \ast a^{-1} and (a^{-1})^{-1} = a.
Theorem 4 (solving equations). For all a, b \in G, the equation a \ast x = b has exactly one solution, x = a^{-1} \ast b, and y \ast a = b has exactly one, y = b \ast a^{-1}.
Corollary 5 (cancellation). In G, a \ast b = a \ast c implies b = c, and b \ast a = c \ast a implies b = c.
Corollary 6 (rows and columns). For each a \in G, the maps \lambda_a(x) = a \ast x and \rho_a(x) = x \ast a are bijections G \to G. So in the table of a finite group every element appears exactly once in each row and once in each column.
Theorem 7 (general associativity). If \ast is associative, then for all n \ge 1 and a_1, \dots, a_n \in S, every bracketing of a_1 \ast a_2 \ast \cdots \ast a_n (factors kept in order) gives the same element.
So brackets may be dropped. In a group, powers are a^n = a \ast \cdots \ast a (n factors) for n \ge 1, a^0 = e and a^{-n} = (a^{-1})^n. Theorem 7 gives a^m \ast a^n = a^{m + n} for m, n \ge 1 (both sides are m + n copies of a); the laws of exponents for all integers are proved in Cyclic groups.
Why it is true
Proof of Theorem 1. As e' is a right identity, e \ast e' = e; as e is a left identity, e \ast e' = e'. So e = e'. \square
Proof of Theorem 2. Using the identity, the hypotheses and associativity,
Proof of Theorem 3. Regrouping (Theorem 7), (a \ast b) \ast (b^{-1} \ast a^{-1}) = a \ast e \ast a^{-1} = e, and likewise (b^{-1} \ast a^{-1}) \ast (a \ast b) = b^{-1} \ast e \ast b = e. So b^{-1} \ast a^{-1} is an inverse of a \ast b, hence the inverse by Theorem 2. The equations a^{-1} \ast a = a \ast a^{-1} = e say that a is an inverse of a^{-1}, so (a^{-1})^{-1} = a. \square
Proof of Theorem 4. x = a^{-1} \ast b works: a \ast (a^{-1} \ast b) = (a \ast a^{-1}) \ast b = e \ast b = b. It is the only solution: if a \ast x = b, then
The equation y \ast a = b is the mirror image. \square
Proof of Corollary 5. b and c both solve a \ast x = a \ast b, which has one solution by Theorem 4; the right-hand law is the same with y \ast a. \square
Proof of Corollary 6. By Theorem 4 each b \in G equals \lambda_a(x) for exactly one x, so \lambda_a is injective and surjective (One-to-one, onto and bijective functions); its inverse is \lambda_{a^{-1}}. The row of a lists \lambda_a(x) as x runs through the headings, so it lists each element once. Columns use \rho_a. \square
Proof of Theorem 7. For i \le j let L_{i, j} be the left-normed product of a_i, \dots, a_j: L_{i, i} = a_i and L_{i, j} = L_{i, j - 1} \ast a_j. We show by Strong induction and well-ordering on n that every bracketing of a_1, \dots, a_n equals L_{1, n}; for n \le 2 there is one bracketing. For n \ge 3 the last operation splits a bracketing as P \ast Q, with P a bracketing of a_1, \dots, a_k and Q of a_{k + 1}, \dots, a_n, 1 \le k < n. By hypothesis P = L_{1, k} and Q = L_{k + 1, n}, so it remains to show
by induction on n - k. If n - k = 1, this is the definition. Otherwise L_{k + 1, n} = L_{k + 1, n - 1} \ast a_n, and associativity and the case n - k - 1 give
Worked examples
Binary operation or not
Decide whether each rule is a binary operation on the given set. (a) Subtraction on \mathbb{Z}. (b) Subtraction on the positive integers. (c) Multiplication on A = \{n \in \mathbb{Z} : 4 \mid n - 1\}. (d) The mediant on \mathbb{Q}: \displaystyle \frac{a}{b} \ast \frac{c}{d} = \frac{a + c}{b + d} for integers a, c and positive integers b, d.
Solution(a) Yes. The difference of two integers is a unique integer.
(b) No. Closure fails: 2 - 5 = -3 is not a positive integer.
(c) Yes. Unpack the definition as in Proving statements about divisibility: if m, n \in A, then m = 4j + 1 and n = 4k + 1 for integers j, k, and mn - 1 = 16jk + 4j + 4k = 4(4jk + j + k), so mn \in A.
(d) No: it is not well defined, since the answer depends on which fraction names the number. With \displaystyle \frac{1}{2} and \displaystyle \frac{1}{3} the rule gives \displaystyle \frac{2}{5}, but \displaystyle \frac{1}{2} = \frac{2}{4}, and \displaystyle \frac{2}{4} with \displaystyle \frac{1}{3} gives \displaystyle \frac{3}{7}, and 2 \cdot 7 \ne 3 \cdot 5.
A shifted product
On G = \mathbb{R} \setminus \{3\} let a \ast b = ab - 3a - 3b + 12. Prove that (G, \ast) is an abelian group, and find its identity and the inverse of 5.
SolutionThe key is the factorization a \ast b = (a - 3)(b - 3) + 3.
Closure. If a, b \ne 3, then (a - 3)(b - 3) is a product of nonzero reals, so it is nonzero and a \ast b \ne 3.
Associativity. Since (a \ast b) - 3 = (a - 3)(b - 3), both (a \ast b) \ast c and a \ast (b \ast c) equal (a - 3)(b - 3)(c - 3) + 3, by associativity of real multiplication; its commutativity gives a \ast b = b \ast a.
Identity. We need (a - 3)(e - 3) = a - 3 for all a, and e = 4 does it.
Inverses. We need (a - 3)(b - 3) + 3 = 4, that is, \displaystyle b = 3 + \frac{1}{a - 3}, a real number other than 3. So \displaystyle 5^{-1} = 3 + \frac{1}{2} = \frac{7}{2}. Check: \displaystyle 5 \ast \frac{7}{2} = 2 \cdot \frac{1}{2} + 3 = 4.
The point 3 had to go: 3 \ast b = 3 for every real b, so 3 has no inverse.
Blending at a perfumery
At a perfumery, Yuna blends two perfume bases by mixing equal volumes. If the bases contain x\% and y\% fragrance oil, the blend contains \displaystyle x \ast y = \frac{x + y}{2} percent, an operation on S = [0, 100]. Kofi wants one blend of bases with 8\%, 12\% and 20\% oil, made by two equal-volume mixings. Does the order matter? Which group axioms hold?
SolutionAn average of two numbers in [0, 100] lies between them, so S is closed, and x \ast y = y \ast x. Mixing the first two bases first,
while mixing the last two first gives 8 \ast (12 \ast 20) = 8 \ast 16 = 12. So \ast is commutative but not associative, and the order matters: the base added last supplies half the oil.
There is no identity: e \ast x = x means \displaystyle \frac{e + x}{2} = x, so e = x for every x, and x = 0 and x = 100 would force e = 0 and e = 100. Without an identity, inverses are not defined.
Completing a table
Let G = \{e, a, b, c\} be a group of order 4 with identity e, in which a \ast a = e and b \ast b = e. Find its operation table.
SolutionThe row and column of e copy the headings, and by Corollary 6 each row and column holds each element once. Row a has a \ast e = a and a \ast a = e, so a \ast b is b or c. If a \ast b = b = e \ast b, right cancellation (Corollary 5) gives a = e, which is false. So a \ast b = c and a \ast c = b.
Row b has b and e, and column a already holds a, so b \ast a = c and b \ast c = a. Each entry of row c is the one element its column still lacks.
| \ast | e | a | b | c |
|---|---|---|---|---|
| e | e | a | b | c |
| a | a | e | c | b |
| b | b | c | e | a |
| c | c | b | a | e |
The table is symmetric, so G is abelian, and c \ast c = e: every element is its own inverse. So there is at most one such group, and there is one: reading e, a, b, c as (0, 0), (1, 0), (0, 1), (1, 1), the table is addition mod 2 in each coordinate, which is associative. This is the Klein four-group V_4.
Abelian exactly when inverses distribute
Prove that a group (G, \ast) is abelian if and only if (a \ast b)^{-1} = a^{-1} \ast b^{-1} for all a, b \in G.
SolutionProof. If G is abelian, Theorem 3 gives (a \ast b)^{-1} = b^{-1} \ast a^{-1} = a^{-1} \ast b^{-1}.
Conversely, if the identity holds for all a, b, then with Theorem 3 it gives a^{-1} \ast b^{-1} = b^{-1} \ast a^{-1} for all a, b. Apply this to a^{-1} and b^{-1}; since (a^{-1})^{-1} = a and (b^{-1})^{-1} = b, it reads a \ast b = b \ast a. \square
Bijections of a set
Let \operatorname{Sym}(X) be the set of all bijections X \to X. Prove that (\operatorname{Sym}(X), \circ) is a group, not abelian when X = \{1, 2, 3\}.
SolutionProof. A composite of bijections is a bijection (Composing functions between sets, and when an inverse exists), so \circ is a binary operation on \operatorname{Sym}(X). It is associative, since (h \circ g) \circ f and h \circ (g \circ f) both send x to h(g(f(x))). The identity is \mathrm{id}_X, and the inverse of f is the inverse map f^{-1}, itself a bijection. \square
On \{1, 2, 3\} let f swap 1 and 2, and g swap 2 and 3. Then (f \circ g)(3) = f(2) = 1 but (g \circ f)(3) = g(3) = 2. Non-bijections must be left out: on \{1, 2\} the constant map k with value 1 has k \circ g constant for every g, never \mathrm{id}.
One-sided axioms are enough
Suppose \ast is associative on G, some e \in G has e \ast a = a for all a, and every a has some b with b \ast a = e. Prove that (G, \ast) is a group.
SolutionProof. It remains to show that each left inverse is a right inverse and that e is a right identity. Let b \ast a = e, and choose c with c \ast b = e. Using e as a left identity and Theorem 7,
Then a \ast e = a \ast (b \ast a) = (a \ast b) \ast a = e \ast a = a, so e is a right identity too, and b is an inverse of a. \square
The two one-sided conditions must be on the same side (exercise 15).
Boundaries
- Unique inverses need associativity. On \{e, a, b\} let e be an identity and let every product of two elements of \{a, b\} be e. Then a has the two inverses a and b; the operation is not associative, as (a \ast b) \ast b = b but a \ast (b \ast b) = a.
- Rows and columns that list every element do not make a group. On \mathbb{Z}_3 (writing k for [k], as in Relations, equivalence classes and partitions) let a \ast b = a - b. Each row and column lists 0, 1, 2 once, but 0 \ast 1 = 2, so 0 is only a right identity, and (0 \ast 0) \ast 1 = 2 while 0 \ast (0 \ast 1) = 1. The converse of Corollary 6 fails.
- The set is part of the data. \mathbb{Z} is a group under addition but not under multiplication (2 has no inverse); \mathbb{R} under multiplication fails because of 0, and \mathbb{R}^\times = \mathbb{R} \setminus \{0\} is a group.
Where this goes next
The first families of groups are in Integers mod n, symmetries and matrices as groups: the integers mod n, the units \mathbb{Z}_n^\times, symmetries of a shape and invertible matrices; from there on the operation is written ab. Groups inside groups are Subgroups; the powers of one element form a cyclic group; \operatorname{Sym}(X) for finite X is the subject of Permutation groups and cycle notation, and polygon symmetries of Dihedral groups. Traveling one loop and then another gives the The fundamental group of a space, and two operations tied by a distributive law make a ring (Rings and integral domains).
Exercises
Binary operations
- Decide whether each rule is a binary operation on the given set; if not, give a pair where it fails. (a) a \ast b = a^b on the positive integers. (b) a \ast b = a - b on the even integers. (c) a \ast b = a - b on the odd integers. (d) \displaystyle a \ast b = \frac{a + b}{2} on \mathbb{Z}. (e) a \ast b = \gcd(a, b) on the positive integers.
- Show that \displaystyle \frac{a}{b} \ast \frac{c}{d} = \frac{a + c}{bd}, for integers a, c and nonzero integers b, d, does not define a binary operation on \mathbb{Q}.
- How many binary operations are there on a set with 3 elements? How many are commutative? How many have a given element as identity?
Checking the axioms
- On \mathbb{Z} let a \ast b = a + b + 6. Prove that (\mathbb{Z}, \ast) is a group, and find its identity and the inverse of 10.
- On \mathbb{Q}^\times let a \ast b = 3ab. Prove that this is an abelian group, and find its identity and the inverse of 2.
- On \mathbb{R} \setminus \{-2\} let a \ast b = ab + 2a + 2b + 2. Prove that this is an abelian group, and find its identity and the inverse of 3.
- On \mathbb{Z} let a \ast b = a + b - ab. Show that \ast is associative and commutative with an identity, and find every element that has an inverse.
Tables and blends
- Let G = \{e, a, b, c\} be a group with identity e in which a \ast a = b. Find its table.
- Is \{p, q, r\} with this table a group? If so, name the identity and each inverse.
| \ast | p | q | r |
|---|---|---|---|
| p | r | p | q |
| q | p | q | r |
| r | q | r | p |
- At the perfumery of Example 3, Kofi now mixes two parts of the first base with one part of the second: \displaystyle x \ast y = \frac{2x + y}{3}. Compute 6 \ast 9, 9 \ast 6, (6 \ast 9) \ast 12 and 6 \ast (9 \ast 12). Which group axioms fail?
- In the group of exercise 6, solve 3 \ast x = 7 using Theorem 4.
Proofs
- Prove that if x \ast x = x in a group, then x = e.
- Prove that if a \ast a = e for every a in a group G, then G is abelian.
- Let \ast be associative on S with identity e, and let U be the set of elements of S that have an inverse. Prove that (U, \ast) is a group. What is U for \mathbb{Z} under multiplication?
- On a set S with at least two elements let a \ast b = b. Prove that \ast is associative, that any e \in S is a left identity, and that every element has a right inverse relative to e, but that (S, \ast) is not a group.
- Let G be a finite nonempty set with an associative operation for which both cancellation laws hold. Prove that G is a group. Show that finiteness is needed.
- Prove that a group of even order has an element a \ne e with a \ast a = e.
Answers
- (a) Yes: a^b is a positive integer. (b) Yes: 2j - 2k = 2(j - k). (c) No: 3 - 1 = 2 is even. (d) No: \displaystyle 1 \ast 2 = \frac{3}{2} \notin \mathbb{Z}. (e) Yes: \gcd(a, b) is a positive integer.
- \displaystyle \frac{1}{1} \ast \frac{1}{1} = \frac{2}{1} = 2, but \displaystyle \frac{1}{1} = \frac{2}{2} and \displaystyle \frac{2}{2} \ast \frac{1}{1} = \frac{3}{2}. Equal inputs give different outputs.
- Each of the 9 table cells holds one of 3 elements: 3^9 = 19{,}683. Commutative: the 3 diagonal cells and the 3 above it are free, 3^6 = 729. With e as identity, the 5 cells in its row and column are fixed: 3^4 = 81.
- Both bracketings give a + b + c + 12; identity -6, as a + (-6) + 6 = a and \ast is commutative. The inverse of a solves a + b + 6 = -6: b = -a - 12, so 10^{-1} = -22.
- A product of nonzero rationals is a nonzero rational, and both bracketings give 9abc. Identity \displaystyle \frac{1}{3}, since \displaystyle 3a \cdot \frac{1}{3} = a. The inverse of a solves \displaystyle 3ab = \frac{1}{3}: \displaystyle b = \frac{1}{9a}, so \displaystyle 2^{-1} = \frac{1}{18}.
- a \ast b = (a + 2)(b + 2) - 2. As in Example 2: closed since (a + 2)(b + 2) \ne 0; both bracketings give (a + 2)(b + 2)(c + 2) - 2; identity -1; the inverse of a is \displaystyle -2 + \frac{1}{a + 2}, so \displaystyle 3^{-1} = -2 + \frac{1}{5} = -\frac{9}{5}.
- a \ast b = 1 - (1 - a)(1 - b), so both bracketings give 1 - (1 - a)(1 - b)(1 - c); identity 0. An inverse of a needs (1 - a)(1 - b) = 1 with b \in \mathbb{Z}, so 1 - a = \pm 1: only 0 and 2 have inverses (2 \ast 2 = 4 - 4 = 0).
- Rows e, a, b, c read e\ a\ b\ c; a\ b\ c\ e; b\ c\ e\ a; c\ e\ a\ b. If a \ast b = e, then a \ast c = c = e \ast c and a = e; so a \ast b = c, a \ast c = e. By associativity b \ast a = (a \ast a) \ast a = a \ast b = c and b \ast b = a \ast (a \ast b) = a \ast c = e, so b \ast c = a; row c is forced by the columns.
- Yes. Rename q, p, r as 0, 1, 2: the table becomes addition in \mathbb{Z}_3 (p \ast p = r is 1 + 1 = 2, r \ast r = p is 2 + 2 = 1), which is associative (Relations, equivalence classes and partitions, exercise 20). Identity q; p^{-1} = r, r^{-1} = p, q^{-1} = q.
- 6 \ast 9 = 7, 9 \ast 6 = 8, \displaystyle (6 \ast 9) \ast 12 = 7 \ast 12 = \frac{26}{3}, \displaystyle 6 \ast (9 \ast 12) = 6 \ast 10 = \frac{22}{3}. Not associative, not commutative, no identity (\displaystyle \frac{2e + x}{3} = x forces e = x for every x). Only closure holds.
- \displaystyle x = 3^{-1} \ast 7 = -\frac{9}{5} \ast 7 = \frac{1}{5} \cdot 9 - 2 = -\frac{1}{5}. Check: \displaystyle 3 \ast (-\frac{1}{5}) = 5 \cdot \frac{9}{5} - 2 = 7.
- Proof. x \ast x = x = x \ast e; canceling x on the left (Corollary 5) gives x = e. \square
- Proof. a \ast a = e gives a^{-1} = a. So by Theorem 3, a \ast b = (a \ast b)^{-1} = b^{-1} \ast a^{-1} = b \ast a. \square
- Proof. e \in U. If a, b \in U have inverses a', b', the computation of Theorem 3 shows b' \ast a' is an inverse of a \ast b, so U is closed. Associativity is inherited from S, e is an identity, and a' lies in U with inverse a. \square For \mathbb{Z}, U = \{1, -1\}, since ab = 1 in integers forces a = \pm 1.
- Proof. (a \ast b) \ast c = c and a \ast (b \ast c) = a \ast c = c. For any e, e \ast a = a (left identity) and a \ast e = e (right inverse). An identity u would give a = a \ast u = u for every a, impossible with two elements. \square
- Proof. Fix a. By left cancellation x \mapsto a \ast x is injective, hence a bijection since G is finite (One-to-one, onto and bijective functions). Choose e with a \ast e = a. For any b, a \ast (e \ast b) = a \ast b, so e \ast b = b. Then (b \ast e) \ast y = b \ast y for every y, and right cancellation gives b \ast e = b. For each b, x \mapsto b \ast x and x \mapsto x \ast b are bijections, giving c with b \ast c = e and d with d \ast b = e, and c = d by Theorem 2. \square The nonzero integers under multiplication are associative and cancellative, but 2 has no inverse.
- Proof. The sets \{a, a^{-1}\} partition G: if a \in \{b, b^{-1}\} then \{a, a^{-1}\} = \{b, b^{-1}\}, as (b^{-1})^{-1} = b. Such a set has one element when a \ast a = e and two otherwise. So |G| is the number t of elements with a \ast a = e plus an even number. With |G| even, t is even, and t \ge 1 since e \ast e = e, so t \ge 2. \square