Motivation
Many familiar calculations have the same structure. You can solve in the integers by adding to both sides. You can solve in the nonzero reals by multiplying by . You can undo a rotation of a square by rotating back. In each case there is a set, a way of combining two elements into a third, a "do nothing" element, and a way of undoing each element.
Group theory isolates exactly the properties that make such calculations legitimate. Once a few axioms are checked, every consequence proved in this chapter holds automatically: cancellation, unique solvability of equations, and the rule for inverting a product. These hold whether the elements are numbers, residues, or rearrangements of objects.
Two warnings shape the whole chapter. First, a group is a set together with an operation. The same set can be a group under one operation and fail under another. Second, the order in which elements are combined can matter. In several important groups , and careless reordering produces wrong answers.
The later chapter on cosets and quotients builds directly on the material here. In particular it relies on subgroups, cancellation, and calculation with inverses.
Definitions
Definition 1.3.1
(Binary operation)
A binary operation on a set is a function . We write the value at as , or simply .
The requirement that the codomain is is called closure: combining two elements of must again give an element of . Closure is part of the definition, not an extra hope. Subtraction is a binary operation on but not on , because .
Definition 1.3.2
(Group)
A group is a pair where is a set and is a binary operation on satisfying the following three axioms.
- Associativity. For all , we have .
- Two-sided identity. There is an element such that for every .
- Two-sided inverses. For every there is an element with .
The group is abelian if for all , and nonabelian otherwise. The order of the group, written , is the number of elements of . Nothing in the axioms requires to be finite, and many central examples are infinite.
Associativity lets us drop parentheses. By induction on the number of factors, every way of bracketing a product gives the same element. For we write for the product of copies of , and we set . Associativity then gives for .
Definition 1.3.3
(Order of an element)
Let be an element of a group . If some positive integer satisfies , the least such is the order of . If no such exists, has infinite order.
Notation. Groups are written in one of two styles.
- In multiplicative notation we write for the product, or for the identity, for the inverse, and for powers.
- In additive notation we write for the operation, for the identity, for the inverse, and for . The statement " has order " then means that is least with .
Additive notation is conventionally reserved for abelian groups. The two styles describe the same mathematics, so a theorem proved multiplicatively translates directly. For example, becomes .
Do not mix the two styles within a single group. In particular, never use additive notation for one structure and multiplicative notation for another on the same set while calling both "the group". The operation is part of the data.
Examples and non-examples
Integers under addition. is an infinite abelian group with identity and inverse . Every nonzero element has infinite order, because with forces .
Nonzero reals under multiplication. Write . A product of nonzero reals is nonzero, so multiplication is a binary operation on . Multiplication is associative, is the identity, and . So is an infinite abelian group. The same reasoning shows that the nonzero rationals and the nonzero complex numbers are groups under multiplication.
Residues under addition. For , the set is an abelian group under . The identity is and the inverse is . Associativity is inherited from .
Counterexample mode
Structures that fail to be groups
- Subtraction on is not associative. We have but . So is not a group, even though subtraction is closed on .
- The positive integers under addition have no identity. Suppose is a positive integer with . Then , which is not positive. Closure and associativity both hold here, but the identity axiom fails.
- The nonnegative integers under addition lack inverses. In the identity exists. However, has no solution with .
- under multiplication lacks inverses. The identity is , but has no integer solution.
Permutation groups
Let be a set and let be the set of all bijections , with composition as the operation. Each group axiom holds for a concrete reason.
- Closure. A composite of bijections is a bijection.
- Associativity. Both and send to .
- Identity. The identity map is the identity element.
- Inverses. The inverse function of a bijection is a bijection and serves as its group inverse.
We write . This group has order .
Convention. In this book means , so we apply first and then . Products are therefore read right to left.
A cycle sends and fixes every other point.
Compute by tracking each point, applying first:
- is fixed by , then sent to by .
- is sent to by , then fixed by .
- is sent to by , then sent to by .
So , , and .
Now compute , applying first:
- .
- .
- .
Hence
Since , the group is nonabelian.
Symmetries of the square
Label the vertices of a square counterclockwise. A symmetry is a distance-preserving map of the plane that carries the square onto itself.
Such a map sends vertices to vertices. To see this, note two facts:
- The vertices are exactly the points of the square that are not the midpoint of two other points of the square.
- Distance-preserving maps of the plane preserve midpoints.
A symmetry also preserves distances between vertices. Adjacent vertices are a side length apart and opposite vertices are a diagonal apart, so adjacent vertices go to adjacent vertices. Moreover, a distance-preserving map of the plane is determined by the images of three non-collinear points, such as vertices . We may therefore identify each symmetry with the permutation it induces on the vertices. Composition of symmetries corresponds to composition of these permutations.
Let be the counterclockwise rotation by . Let be the reflection in the diagonal through vertices and . Then and .
To compute , apply , then , then :
- .
- .
- .
- .
Hence
There are exactly eight symmetries.
At most eight. A symmetry is determined by where it sends vertices , , and . Vertex can go to any of vertices. Vertex must then go to one of the neighbors of the image of . Vertex must go to the remaining neighbor. This gives at most symmetries.
At least eight. Consider the elements and for .
- sends to vertex , reading labels modulo . It sends to the counterclockwise neighbor of that vertex.
- also sends to vertex , because fixes . However, sends to , so sends to , which is the clockwise neighbor.
These eight elements produce eight distinct pairs (image of , image of ). They are therefore distinct, and the symmetry group has order .
The unit groups
Fix . Multiplication on , given by , is associative with identity . However, is not a group under it, because has no inverse.
A class is a unit if for some . We write for the set of units.
is a group under multiplication:
- Closure. If and have inverses and , then . So is a unit.
- Associativity is inherited from .
- Identity. is a unit, with inverse .
- Inverses. The inverse of a unit is itself a unit, because serves as its inverse.
Multiplication of residues is commutative, so is abelian.
Note that , but is not a subgroup of . The two structures use different operations, and does not even contain the additive identity .
Theorem 1.3.4
(Units modulo )
Let and . Then is invertible in if and only if .
Proof
(From an inverse to a Bézout relation and back)
First, the condition does not depend on the chosen representative. If , then and have the same common divisors with , so .
() Suppose . By Bézout's identity there are integers with . Reducing modulo gives . Multiplication is commutative, so as well, and is the inverse of .
() Suppose . Then divides , so for some integer . Any common divisor of and divides the left side, so it divides . Hence .
Basic consequences of the axioms
Theorem 1.3.5
(Uniqueness of identity and inverses)
A group has exactly one identity element. Each element has exactly one inverse, which we denote .
Proof
(Comparing two candidates)
Identity. Suppose and are both identities. Then
The first equality uses that is an identity, and the second uses that is one.
Inverses. Suppose and are both inverses of . Then
The middle step uses associativity.
Theorem 1.3.6
(Cancellation and solving equations)
Let be a group and .
- Left cancellation. If , then .
- Right cancellation. If , then .
- Solving equations. The equation has the unique solution . The equation has the unique solution .
- Inverse of a product. .
Proof
(Multiplying by an inverse on the correct side)
(1) Left cancellation. Multiply on the left by and apply associativity:
(2) Right cancellation. Symmetrically, multiply on the right by .
(3) Solving equations.
- Existence. .
- Uniqueness. If , then .
The same argument on the right shows that holds exactly when .
(4) Inverse of a product. Compute both products:
So is an inverse of . By uniqueness of inverses it is the inverse.
When is nonabelian, and can differ. So "divide by " is ambiguous until you say which side.
Subgroups
Definition 1.3.7
(Subgroup)
A subset of a group is a subgroup, written , if it satisfies all three conditions:
- ;
- whenever ;
- whenever .
These conditions say exactly that is a group under the restricted operation. Suppose instead that were a group under the restricted operation with some identity . Then in , so by cancellation. Inverses in then agree with inverses in by uniqueness of inverses.
Theorem 1.3.8
(Subgroup criterion)
Let be a nonempty subset of a group . Then if and only if for all .
Proof
(Recovering the three subgroup conditions)
() Suppose and . Then because is closed under inverses. So because is closed under products.
() Suppose for all . Since is nonempty, choose some .
- Identity. .
- Inverses. For any , we have .
- Closure. For any , we now know . Therefore .
All three subgroup conditions hold.
Theorem 1.3.9
(Finite closed subsets are subgroups)
Let be any group, finite or infinite. Let be a finite, nonempty subset with for all . Then .
Proof
(Repeated powers produce the identity and the inverse)
Fix . By closure and induction, every power lies in .
Because is finite, these powers cannot all be distinct. So for some . Let . Then
Left cancellation gives . Since , the element is one of the powers of , so .
For the inverse, consider two cases.
- If , then , and .
- If , then . It is the inverse of , because .
Closure under products is given by hypothesis.
Proof X-ray
Where finiteness and cancellation enter
The proof uses three ingredients, in this order. Finiteness of is used once, through the pigeonhole principle: the infinitely many powers must repeat inside . Cancellation is then applied in , not in : the equation lives in the ambient group, where exists even though we do not yet know that it lies in . The case split or only makes sure that the candidate inverse is a positive power of , hence in by closure. The ambient group may be infinite; only must be finite. For example, is a nonempty subset of closed under addition, yet . The additive powers of never repeat, so the pigeonhole step has nothing to work with.
Worked examples
Worked example 1.3.10
(Left and right equations in )
Using the right-to-left convention, let and in .
Solve . By the cancellation theorem, , using . Apply first:
- .
- .
- .
So . As a check, , matching the computation earlier in the chapter.
Solve . By the cancellation theorem, . Apply first:
- .
- .
- .
So . As a check, compute :
- .
- .
- .
This is , as required.
The two solutions and differ, which is exactly the effect of noncommutativity.
Worked example 1.3.11
(The group )
The integers with and are the odd ones. By the units criterion,
Products. Reduce each product modulo :
- .
- .
- .
- .
- .
- .
Orders and inverses. The identity has order . Each of , , has order , and so each is its own inverse.
Nonunits. The nonzero nonunits are , , . For instance, has no inverse: is always even, so it is never congruent to modulo .
The set is not even closed under multiplication, because .
Worked example 1.3.12
(A finite closed subset of an infinite group)
Let . Every element of is a power of :
So every product of two elements of is a power of . Moreover, means every power of equals one of , which all lie in . Hence is closed under multiplication. By the finite-subgroup test, , even though is infinite.
The proof of the finite-subgroup test is visible here. Taking , the powers first repeat at , giving . The inverse it produces is . Indeed .
Worked example 1.3.13
(Computing with and )
In the symmetry group of the square, compare and .
Compute (apply first):
- .
- .
- .
- .
So .
Compute (apply first):
- .
- .
- .
- .
So .
Since , the group is nonabelian.
Consistency check. Multiply on the left by . Because , this gives . Then
Tracking each point, applying first:
- .
- .
- .
- .
This is , which agrees with .
Common mistakes
Common mistake
(Reversing products when inverting)
In general ; the correct rule is . In the symmetry group of the square, is its own inverse, while , a different element. The reversed product is the correct inverse.
Common mistake
(Ignoring the composition convention)
Reading left to right, applying first, gives instead of . The two conventions produce inverse answers for this product. State your convention and keep to it throughout a calculation.
Common mistake
(Confusing the set with the group)
sits inside , but it is a group under multiplication, not addition: in we have , and does not contain . Similarly, is a group under but not under .
Further points to check:
- Forgetting closure. Before checking any axiom, confirm that the operation lands back in the set. The odd integers fail under addition at this first step.
- Checking a one-sided identity or inverse. The axioms require both and . In a nonabelian setting, one side does not automatically imply the other unless a group structure is already known.
- Using the finite-subset shortcut on infinite sets. Closure alone does not make a subgroup of .
- Assuming groups are finite. and are groups, and elements can have infinite order.
Exercises
Quick check
(In , let and . Compute , , and . Which of the last two equals ?)
Solution
From the computation earlier in the chapter, . Its inverse reverses the cycle, so .
Each transposition is its own inverse: and . Therefore
So , as the cancellation theorem predicts. The other order, , gives a different element because and do not commute.
Quick check
(Decide which of the following are groups: (a) ; (b) ; (c) the odd integers under addition; (d) with .)
Solution
(a) Not a group. The identity would be , but for every , so has no inverse.
(b) A group. The product of nonzero rationals is a nonzero rational, so the operation is closed. Multiplication is associative, the identity is , and the inverse of is .
(c) Not a group. The set is not closed under addition: is even.
(d) A group. The operation is closed on .
- Associativity. Both and equal .
- Identity. An identity must satisfy , so . Since is commutative, works on both sides.
- Inverses. An inverse of must satisfy , so , which is an integer.
The group is abelian.
Quick check
(List , find the order and inverse of each element, and exhibit a nonzero nonunit modulo with a reason it is not invertible.)
Solution
The integers with and are , so .
Powers of . Reducing modulo :
So has order .
Powers of . Reducing modulo :
So has order .
Powers of . , so has order .
Inverses. Since , we have and . Since , . Finally, has order and is its own inverse.
A nonzero nonunit. Take . We have , so is not a unit by the units criterion. Directly, always ends in the digit or , so it is never congruent to modulo .
Quick check
(Show that is a subgroup of .)
Solution
is nonempty and finite. Check closure under addition modulo :
- Adding to any element leaves it unchanged.
- .
- .
- .
Every sum lies in , so the finite-subgroup test gives .
The inverses can also be read off directly: , , and .
Quick check
(Let be a binary operation on a set . Suppose is a left identity ( for all ) and is a right identity ( for all ). Prove that , and deduce that a two-sided identity is unique.)
Solution
Consider the single element .
- Because is a left identity, .
- Because is a right identity, .
Therefore . Associativity was not needed.
Now suppose and are both two-sided identities. Then is in particular a left identity and is a right identity. The argument above gives , so a two-sided identity is unique.
Quick check
(Let . Show that is nonempty and closed under multiplication but is not a subgroup. Identify the step of the proof of the finite-subgroup test that fails.)
Solution
Nonempty and closed. contains , so it is nonempty. It is closed under multiplication because with .
Not a subgroup. The element has inverse in . If for some , then , a contradiction. So , and is not closed under inverses.
Where the proof of the finite-subgroup test fails. Apply the proof to . The powers are pairwise distinct, so no repetition with ever occurs. The proof never obtains an with , and so it never produces the candidate inverse . The finiteness of was exactly what forced the repetition.