Chapter 7 introduces the single most important construction in this entire course: a subgroup's cosets. Every fact this section reviews does the actual work when that chapter proves it. A coset partition of a group is nothing more than an equivalence relation's classes. It is just applied to a set that happens to be a group. Say reflexive, symmetric, and transitive are already second nature to you, along with "classes partition the set." Then chapter 7 is just one new definition layered on a fact you already have. If those ideas aren't second nature yet, chapter 7 will feel like two new ideas at once instead of one.
Imagine sorting everyone at a large event onto buses by which town they're headed to. Anyone riding your bus is related to you by "goes to the same town." That relation groups every attendee into non-overlapping buses. Nobody is left standing, and nobody rides two buses at once. That is exactly what "the classes partition the set" means. Now run it the other direction. Hand someone a finished seating chart with no relation defined yet. They can still recover "rides the same bus as" purely from which names sit in which section. The relation and the grouping carry the same information; each one rebuilds the other.
A relation \sim on a set A is an equivalence relation when it is reflexive (a \sim a for every a), symmetric (a \sim b \Rightarrow b \sim a), and transitive (a \sim b and b \sim c \Rightarrow a \sim c). Its equivalence class [a] = \{x \in A : x \sim a\} collects everything related to a. Two facts work in both directions, and each is the reverse of the other. First: any such relation's classes form a partition of A, with every element in exactly one class. Second: start from any partition instead, and declare x \sim y whenever x and y share a block. That recovers a relation whose classes are exactly those blocks, and that relation is itself an equivalence relation. Checking whether a candidate relation qualifies is a three-item checklist. Missing even one item, usually the transitive one, means the "classes" it would produce can overlap or leave elements out.
Theorem
Equivalence Classes Partition the Set
Recalled from Discrete Mathematics I — Logic, Proof, and Structure · Equivalence classes — first taught there.
Let \sim be an equivalence relation on a set A. The distinct equivalence classes of \sim form a partition of A: every element of A belongs to exactly one class, the classes are pairwise disjoint, and their union is all of A.
Every a\in A satisfies a\sim a by reflexivity, so a\in[a] and the classes cover A. Suppose two classes [a] and [b] share an element c, so c\sim a and c\sim b. By symmetry a\sim c, and by transitivity a\sim c and c\sim b give a\sim b. Then for any x\in[a], x\sim a and a\sim b give x\sim b, so x\in[b], and the same argument in reverse gives [b]\subseteq[a]. Hence [a]=[b]: two classes that share even one element are the same class, so distinct classes never overlap. Combined with the classes covering A, this makes the collection of distinct classes a partition of A.
Theorem
A Partition Induces an Equivalence Relation
Recalled from Discrete Mathematics I — Logic, Proof, and Structure · Partitions — first taught there.
Let \{A_1, A_2, \ldots, A_k\} be a partition of a set A. Defining x\sim y to mean "x and y lie in the same block A_i" makes \sim an equivalence relation on A, and its equivalence classes are exactly the original blocks.
Reflexivity: every x\in A lies in whichever block contains it, so x shares that block with itself, giving x\sim x. Symmetry: if x and y share a block, that same fact says y and x share a block, so x\sim y implies y\sim x. Transitivity: if x,y share block A_i and y,z share block A_j, then y lies in both A_i and A_j; since the blocks of a partition are pairwise disjoint, A_i=A_j, so x and z share that same block and x\sim z. Thus \sim is an equivalence relation. For any x\in A_i, an element y satisfies x\sim y exactly when y\in A_i too, so the equivalence class [x] is precisely the block A_i containing x.
Group 6 elements into equivalence classes
Regroup the chips by remainder when divided by 3, forming exactly 3 blocks: {0,3}, {1,4}, {2,5}.
Loading interactive…
Recipe Check a relation and find its classes Use when: you're handed a specific relation on a set and need to know whether it's an equivalence relation, and if so, what its classes are Goal: either a confirmed equivalence relation with its full list of classes, or the specific property that fails
Quick recipe
-
1
Confirm a \sim a holds for every element a in the set. Don't just try a few examples and stop there.
Example
Let A = \{0,1,\ldots,8\} and x \sim y mean x and y leave the same remainder mod 4. Every x obviously relates to itself, so x \sim x holds for every x \in A.
Why: an element missing from its own class right away breaks the whole idea of a class containing it.
-
2
Confirm a \sim b implies b \sim a for every related pair. Check both directions, not just one.
Example
If x \sim y, then y \sim x too: the relation doesn't care which one is named first.
Why: without this check, an element could count as related to a while a doesn't count as related back. That leaves "the class containing a" unclear.
-
3
Confirm a \sim b and b \sim c together force a \sim c. Check every such chain in the relation, not just the pairs that come to mind first.
- all three checks pass — continue to the next step and build the classes.
- any single check fails — stop here. The relation is not an equivalence relation, and no class list can be built from it.
Why: the transitive check is the one most often skipped. Skipping it is exactly what lets "classes" overlap or leave elements out.
-
4
For each element a, collect [a] = \{x \in A : x \sim a\}. Repeat until every element of A sits in some class.
Example
Continuing with A=\{0,\ldots,8\}: sort by remainder mod 4 to get [0]=\{0,4,8\},\quad [1]=\{1,5\},\quad [2]=\{2,6\},\quad [3]=\{3,7\}
Why: once all three checks pass, the recalled theorem guarantees these classes partition A automatically. No element is left out or counted twice.
Common mistakes
- Checking that a relation is reflexive and symmetric, then skipping the transitive check because it "looks obviously fine."
- Testing a property on one or two elements, then assuming it holds everywhere, instead of confirming the general case.
- Building classes before finishing all three checks, then finding a missing pair only after the grouping is already drawn.
- Forgetting that a relation failing even one property can still group most elements correctly. That makes the one bad case easy to miss.
Worked example
Find the classes of 'same remainder mod 3'
-
1
This repeats the recipe above (Steps 1-4), now on a new relation and a new modulus. On A = \{0,1,2,3,4,5,6,7\}, define x \sim y to mean x and y leave the same remainder when divided by 3. Find every class.
-
2
Sort each element by its remainder: 0,3,6 give 0; 1,4,7 give 1; 2,5 give 2.
-
3
Each group is one class. Every element of A falls into exactly one of them.
-
4\boxed{[0] = \{0,3,6\}, \quad [1] = \{1,4,7\}, \quad [2] = \{2,5\}}
Chapter 3 rebuilds this exact grouping as \mathbb{Z}_3's three elements — a residue class is an equivalence class of this relation.
Loading interactive…
Worked example
A relation that isn't transitive is not an equivalence relation
-
1
This is the recipe's Step 3 failure case. Steps 1 and 2 pass, but the transitive check catches a relation that isn't an equivalence relation. On A = \{1,2,3\}, let R = \{(1,1),(2,2),(3,3),(1,2),(2,1),(2,3),(3,2)\}. R is reflexive and symmetric just by looking. Is it transitive?
-
2
Check whether 1 \sim 2 and 2 \sim 3 force 1 \sim 3: both pairs are in R, but (1,3) \notin R.
-
3\boxed{R \text{ is not an equivalence relation} — \text{transitivity fails}}
Had R also passed the transitive check, 1, 2, and 3 would all have collapsed into one class. The missing pair (1,3) is exactly what keeps that from happening cleanly. That's why "classes partition the set" cannot be salvaged once the transitive property fails.
Loading interactive…
Where this goes next
Chapter 7: Cosets and Lagrange's theorem
Given a subgroup H of G, chapter 7 defines a \sim b to mean a^{-1}b \in H. It then proves this is an equivalence relation. Its classes turn out to be exactly the left cosets of H. Every element of G lands in exactly one coset. The cosets never overlap, and their union is all of G. Those are the same three guarantees "equivalence classes partition the set" already gives you, just renamed. Lagrange's theorem is one short counting step away, once that partition is in hand.
Quick review
Practice from earlier coursework, pulled in for this topic.
From Discrete Mathematics I — Logic, Proof, and Structure
Is same parity (both even or both odd) an equivalence relation on the integers?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
Every integer shares its own parity, the relation obviously runs both ways, and matching parity chains through any middle integer.
From Discrete Mathematics I — Logic, Proof, and Structure
Is has the same absolute value as an equivalence relation on the integers? Check it against all three properties.
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
Every integer has the same absolute value as itself, the condition is obviously symmetric, and if two absolute values match a third's, all three match.
Quick review
Practice from earlier coursework, pulled in for this topic.
From Discrete Mathematics I — Logic, Proof, and Structure
Why does it not matter which member of an equivalence class is used to name it?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
Since every member of a class is equivalent to every other member, [a] equals [b] whenever a and b share a class, regardless of which one is chosen.
From Discrete Mathematics I — Logic, Proof, and Structure
For an equivalence relation ~ on A, the equivalence class [a] is defined as which set?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
[a] collects every element of A that is equivalent to a, by definition.
Quick review
Practice from earlier coursework, pulled in for this topic.
From Discrete Mathematics I — Logic, Proof, and Structure
What is the relationship between equivalence relations and partitions of the same set?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
This is the correspondence proved in this chapter: equivalence classes form a partition, and a partition's same-block relation is an equivalence relation, each recovering the other.
From Discrete Mathematics I — Logic, Proof, and Structure
Given the partition {{1,2}, {3,4}} of {1,2,3,4}, which pair belongs to the equivalence relation it induces?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
1 and 3 are in different blocks, so they are not related by the induced relation.
2 and 4 are in different blocks.
1 and 4 are in different blocks.
Why
1 and 2 sit in the same block, so the induced relation relates them; the other choices pair elements from different blocks.