Grades 6–8FoundationsPlanned
Relations, equivalence relations and partitions
Relations as sets of ordered pairs, and the special relations (reflexive, symmetric and transitive) that sort a set into non-overlapping classes. 'Same remainder', 'same colour' and 'same shape' are first examples.
math.found.equivalence-relations
The lesson for this topic has not been written yet. The outline below is part of the curriculum map and has not been reviewed.
Builds on
Required prerequisites, all the way down: 2
You will learn to
- Represent a relation on a finite set as a set of ordered pairs, a table and an arrow diagram.
- Test a relation for reflexivity, symmetry and transitivity, giving a counterexample whenever a property fails.
- Pass between an equivalence relation and the partition formed by its equivalence classes.
Definition
- A relation R on a set A is a subset of A × A; we write a R b when (a, b) ∈ R.
- R is an equivalence relation if it is reflexive (a R a), symmetric (a R b implies b R a) and transitive (a R b and b R c imply a R c).
- The equivalence class of a is [a] = {x ∈ A : x R a}.
- A partition of A is a set of non-empty, pairwise disjoint subsets of A whose union is A.
Theorem
- The equivalence classes of an equivalence relation on A form a partition of A, and every partition of A comes from exactly one equivalence relation.
- Any two equivalence classes are either equal or disjoint.
- For n ≥ 1, 'has the same remainder on division by n' is an equivalence relation on ℤ with exactly n classes.
Common misconceptions
- Thinking symmetry and transitivity together imply reflexivity; the argument fails for an element related to nothing.
- Treating an equivalence class as a single element instead of a set of elements.
- Assuming every relation is symmetric, as 'is less than' shows it need not be.
Leads to
Optional discoveries
- Quotient groups and quotient rings Collapsing each class to a single point gives a quotient set; when the relation respects an operation, the quotient inherits it, giving quotient groups and rings such as ℤ/nℤ.Wonder Trail →
- Universal properties The quotient map A → A/~ is universal: every function out of A that is constant on equivalence classes factors through it in exactly one way.Wonder Trail →
- Metric spaces and point-set topology Gluing points by an equivalence relation produces quotient spaces, such as a circle from an interval with its endpoints identified.
- ← Collections
- ← Integers
Learning pathways
Further reading
- Daniel J. Velleman, How to Prove It: A Structured Approach (1994)