2.4Equivalence relations and partitions
The idea
An equivalence relation groups elements into classes of "the same kind". It is reflexive, symmetric and transitive, and the classes split the set into non-overlapping pieces: a partition.
Think of it like this: Sorting socks by colour: "same colour" is an equivalence relation, and each pile is a class.
Why it exists
Questions ask for the number of classes or the number of ordered pairs in the relation, or for the count of equivalence relations (Bell numbers).
How it works
- Class of a: [a] = all elements related to a.
- Distinct classes are disjoint and together cover the set (a partition).
- x ≡ y (mod k) gives exactly k classes.
- If the classes have sizes s₁, …, s_m, the relation has Σ sᵢ² pairs.
- The number of equivalence relations on an n-set is the Bell number: 1, 2, 5, 15, 52.
Worked example: A relation on {1..6} with classes {1,2,3}, {4,5}, {6}
Pairs = 3² + 2² + 1² = 9 + 4 + 1 = 14.
Now play with it
- →Change k and see the classes of {0..12}.
- →Compare the list of Bell numbers at the bottom.
The 3 classes are non-empty, pairwise disjoint and cover {0..12}: a partition. Every equivalence relation is exactly a partition, and conversely. Number of equivalence relations on an n-set = Bell(n): B(1..7) = 1, 2, 5, 15, 52, 203, 877.
Check yourself
How many equivalence relations exist on a 4-element set?
Exam notes (the dense version)
Equivalence = reflexive + symmetric + transitive. It splits the set into disjoint equivalence classes that cover it (a partition); every partition gives an equivalence relation. Number of classes of x ≡ y (mod k) is k. If a relation has k classes of sizes s₁..s_k it has Σ sᵢ² pairs. The number of equivalence relations on an n-set is the Bell number.
Previous year questions: Sets, Relations & Functions (20)
PYQs are grouped by topic, so this is the full set for Sets, Relations & Functions; try the ones that match this subtopic. Open all 20 on the topic page.