Equivalence Relations and Partitions
A reflexive, symmetric and transitive relation divides a set into classes with no overlap. Modular arithmetic, quotient constructions and much of later algebra use this same 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 S specifies ordered pairs of elements of S. Write a ~ b when the pair (a, b) belongs to it. Reflexive means a ~ a for every a. Symmetric means a ~ b implies b ~ a. Transitive means a ~ b and b ~ c imply a ~ c. An equivalence relation has all three properties. Equality satisfies them. The relation a < b on integers fails reflexivity because a < a never holds.
For a positive integer n, congruence modulo n means n divides a - b. It is reflexive because a - a = 0, symmetric because reversing a difference changes its sign, and transitive because a - c = (a - b) + (b - c). Integers are grouped by remainders 0 through n - 1. Use a = qn + r with 0 <= r < n, including for negative a. For example, -8 = (-3) times 3 + 1.
The class [a] is the set of x with x ~ a. Reflexivity puts a in [a]. If c belongs to both [a] and [b], then a ~ c ~ b, so a ~ b. For any x in [a], x ~ a ~ b puts x in [b]. Reversing this argument gives [b] inside [a]. Thus classes with a shared element are equal. For example, 1 and 4 have the same class modulo 3 because their difference is divisible by 3.
A partition is a collection of nonempty, disjoint blocks covering a set. Equivalence classes form a partition. Conversely, define a ~ b when a and b lie in the same block; this is an equivalence relation. To find classes from listed pairs, collect every element related to a representative. On the empty set, the empty relation satisfies all three properties: there is no element or pair that can violate them.
Check all three properties for the relation, sort integers into remainder classes, and remember that classes sharing an element are equal.
Lesson and questions written for this dataset.
Readings and extra questions written for this dataset. Flashcards retained from the imported fact collection; their source terms have not been verified.
2 · Watch
به انگلیسیTake it off screen
Where it sits
Learn first
Optional connections
Where this leads
Jobs that lean on this skill. Follow one to see everything it is built on.
14 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.