Equivalence Relations and Partitions
A relation that is reflexive, symmetric and transitive cuts a set into classes with no overlap. Modular arithmetic, quotient constructions and much of later algebra are this one idea.
What a learner can do afterwards
- Verify the three properties for a proposed relation
- Describe the classes of congruence modulo n
- Show that equivalence classes either coincide or are disjoint
1 · Read
A relation on a set is a collection of ordered pairs saying which elements stand related. It is reflexive when every element relates to itself, symmetric when each pair appears both ways, and transitive when chains link through. An equivalence relation meets all three at once. Equality passes: a equals a, a equals b gives b equals a, and chains link up. But a less than b fails at once, since a is never less than itself.
Congruence modulo n groups integers by remainder. Two numbers share a class exactly when n divides their difference. Modulo 3 there are three classes: multiples of 3, numbers leaving remainder 1, and numbers leaving remainder 2. Modulo 5 the possible remainders are 0, 1, 2, 3 and 4, so there are five classes. Every integer lands in exactly one class.
Two equivalence classes either coincide or are disjoint, with no partial overlap. If the classes of a and b share an element c, symmetry and transitivity link every member of one class to the other, so each class sits inside the other. Lee is right about 2 and 5 modulo 3: 5 minus 2 equals 3, so 5 lies in the class of 2 and the classes coincide. A relation can be reflexive and symmetric yet fail transitivity, and that near miss is not an equivalence relation.
Check all three properties for the relation, sort integers into remainder classes, and remember that overlapping classes collapse into one.
2 · Watch
Take it off screen
Where it sits
Where this leads
Jobs that lean on this skill. Follow one to see everything it is built on.
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.