Whenever we say two things are "the same for our purposes", we are using an equivalence relation. Two integers are the same modulo 5 if they leave the same remainder. Two strings are the same length. Two fractions 1/2 and 2/4 are the same rational number. Two files land in the same hash bucket. In each case the relation chops the whole set into separate groups, and inside a group everything is interchangeable.
This chapter makes that idea precise. Building on Properties of Relations, we define equivalence relations and equivalence classes, prove the central theorem that equivalence relations and partitions are the same thing seen from two sides, and then count them using Bell and Stirling numbers.
An equivalence relation on a set A is a relation that is reflexive, symmetric and transitive. It splits A into disjoint equivalence classes, and every partition of A arises from exactly one equivalence relation in this way.
All counts in this chapter were checked by generating every set partition by program, and the class computations were done with the union-find code shown below.
Definition and First Examples
A relation R on A is an equivalence relation if it is
reflexive: a R a for every a ∈ A,
symmetric: a R b → b R a,
transitive: a R b ∧ b R c → a R c.
We often write a ~ b or a ≡ b instead of a R b.
Each property matches an intuition about "sameness": everything is the same as itself; if a is like b then b is like a; and "likeness" can be chained.
Relation | Equivalence? | Why |
|---|---|---|
a ≡ b (mod n) on ℤ | Yes | Proved below |
"has the same length as" on strings | Yes | It is "f(x) = f(y)" with f = length |
a2 = b2 on ℤ | Yes | Classes {0}, {1, −1}, {2, −2}, … |
= on any set | Yes | The smallest equivalence relation: every class is a single element |
A × A (everything related) | Yes | The largest: one single class |
≤ on ℤ | No | Not symmetric |
|a − b| ≤ 1 on ℤ | No | Not transitive: 1 ~ 2, 2 ~ 3, but 1 ≁ 3 |
"is a friend of" | No | Not reflexive (by convention), not transitive |
Proof: congruence mod n is an equivalence relation
Fix n ≥ 1. Define a ≡ b (mod n) ⇔ n | (a − b).
Reflexive: a − a = 0 = n · 0, so n | (a − a).
Symmetric: if a − b = nk, then b − a = n(−k).
Transitive: if a − b = nk and b − c = nl, then adding gives a − c = n(k + l). ∎
The kernel of a function
The two examples "same length" and "same square" follow one pattern. For any function f : A → B define
a ~ b ⟺ f(a) = f(b)This is always an equivalence relation, because = itself is reflexive, symmetric and transitive. It is called the kernel of f (some books say "the equivalence relation induced by f"). Congruence mod n is the kernel of f(a) = a mod n. Remarkably, every equivalence relation is the kernel of some function: just take f(a) = the class of a. So "equivalence relation" and "having the same label" are one and the same idea.
A less obvious example: fractions
On the set of pairs (a, b) with a, b ∈ ℤ and b ≠ 0, define (a, b) ~ (c, d) ⇔ ad = bc. The pair (a, b) stands for the fraction a/b, and the relation says "same value": (1, 2) ~ (2, 4) ~ (−3, −6).
Reflexive (ab = ba) and symmetric (ad = bc ⇔ cb = da) are immediate. Transitive: suppose ad = bc and cf = de. Multiply the first by f: adf = bcf = b(de) using the second. So d(af − be) = 0. Because d ≠ 0, af = be, which says (a, b) ~ (e, f). ∎
Note how the condition "second component ≠ 0" was essential. With a zero second component allowed, (0, 0) would be related to every pair (since a · 0 = 0 · c) and transitivity would fail: (1, 2) ~ (0, 0) and (0, 0) ~ (1, 3), but (1, 2) ≁ (1, 3) because 1 · 3 ≠ 2 · 1.
Equivalence Classes
The equivalence class of a is [a] = {x ∈ A : x ~ a}, the set of everything equivalent to a. Any element of a class is called a representative of that class. The set of all classes is the quotient set A/~.
For congruence mod 3 on ℤ:
[0] = { …, −6, −3, 0, 3, 6, … }
[1] = { …, −5, −2, 1, 4, 7, … }
[2] = { …, −4, −1, 2, 5, 8, … }
ℤ / ≡3 = { [0], [1], [2] } (usually written ℤ3)Notice [1] = [4] = [−2]: one class, many names. Choosing a representative is like choosing which member of a group to speak for it.
The key lemma
Lemma. Let ~ be an equivalence relation on A and a, b ∈ A. The following are equivalent:
a ~ b
[a] = [b]
[a] ∩ [b] ≠ ∅
Proof. (1 ⇒ 2) Assume a ~ b. Take any x ∈ [a], so x ~ a. By transitivity with a ~ b, x ~ b, so x ∈ [b]. Thus [a] ⊆ [b]. By symmetry b ~ a, and the same argument gives [b] ⊆ [a]. So [a] = [b].
(2 ⇒ 3) By reflexivity a ∈ [a] = [b], so the intersection contains a.
(3 ⇒ 1) Pick x ∈ [a] ∩ [b]. Then x ~ a and x ~ b. By symmetry a ~ x, and by transitivity with x ~ b, a ~ b. ∎
The lemma says two classes are either identical or completely disjoint. There is no partial overlap. That is exactly the structure of a partition.
Partitions
A partition of a set A is a collection of subsets A1, A2, … (called blocks) such that
every block is non-empty,
the blocks are pairwise disjoint (Ai ∩ Aj = ∅ for i ≠ j), and
their union is A.
So every element of A lies in exactly one block. For A = {1, 2, 3, 4}: {{1, 3}, {2}, {4}} is a partition. {{1, 3}, {3, 4}, {2}} is not (3 is in two blocks), and {{1}, {2, 3}} is not (4 is missing).
The fundamental theorem
Theorem. (a) If ~ is an equivalence relation on A, then its distinct equivalence classes form a partition of A. (b) Conversely, if P is a partition of A, then "a ~ b ⇔ a and b lie in the same block of P" is an equivalence relation whose classes are exactly the blocks of P.
Proof of (a). Each class [a] is non-empty because a ∈ [a]. Every a ∈ A lies in its own class, so the union of the classes is A. Two distinct classes are disjoint by the lemma (if they shared an element they would be equal). ∎
Proof of (b). Reflexive: every a lies in some block, since the blocks cover A. Symmetric: "a and b in the same block" is a symmetric statement. Transitive: say a, b ∈ B1 and b, c ∈ B2. Then b ∈ B1 ∩ B2, and since different blocks are disjoint, B1 = B2; so a and c are in the same block. The class of a is precisely the block containing a. ∎
Going from relation to partition and back returns what you started with, so equivalence relations on A and partitions of A are in one-to-one correspondence. This is why counting equivalence relations is the same as counting partitions.
Worked example: from a partition to ordered pairs
Partition {{1, 2}, {3, 4, 5}} of A = {1, 2, 3, 4, 5}. The corresponding relation contains every ordered pair inside each block:
block {1,2}: (1,1) (1,2) (2,1) (2,2) 4 pairs
block {3,4,5}: (3,3) (3,4) (3,5) (4,3) (4,4) (4,5) (5,3) (5,4) (5,5) 9 pairs
total 13 pairsIn general, if the blocks have sizes n1, …, nk, the equivalence relation has exactly n12 + n22 + … + nk2 ordered pairs. In matrix form, if you list the elements block by block, the matrix is made of all-ones squares along the diagonal.
So an equivalence relation on an n-element set has between n pairs (all blocks singletons: the relation =) and n2 pairs (one block: A × A).
Computing Classes: Union-Find
In practice we are often given a few "these two are the same" facts and must find the groups they generate, that is, the classes of the smallest equivalence relation containing the given pairs (the closure t(s(r(R))) from Properties of Relations). The union-find (disjoint-set) data structure does this in almost linear time when it uses both union by rank and path compression; the short version below uses only path halving, which is more than fast enough for exam-sized inputs. The same structure powers Kruskal's algorithm and connected-component labelling.
def equivalence_classes(A, pairs):
"""Classes of the smallest equivalence relation on A containing `pairs`
(union-find: each class is a tree, find() returns its root)."""
parent = {a: a for a in A}
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]] # path halving
x = parent[x]
return x
for a, b in pairs:
parent[find(a)] = find(b) # merge the two classes
classes = {}
for a in sorted(A):
classes.setdefault(find(a), []).append(a)
return list(classes.values())
def set_partitions(items):
"""Generate every partition of the list `items`."""
if not items:
yield []
return
first, rest = items[0], items[1:]
for p in set_partitions(rest):
for i in range(len(p)): # put `first` into an existing block
yield p[:i] + [[first] + p[i]] + p[i + 1:]
yield [[first]] + p # or give it a block of its own
A = range(1, 9)
pairs = [(1, 3), (2, 5), (5, 6), (7, 8), (3, 7)]
classes = equivalence_classes(A, pairs)
print("classes:", classes)
print("ordered pairs in the relation:", sum(len(c) ** 2 for c in classes))
for n in range(1, 7):
counts = {}
for p in set_partitions(list(range(n))):
counts[len(p)] = counts.get(len(p), 0) + 1
print(f"n={n}: total={sum(counts.values()):3} by number of classes: {counts}")Output:
classes: [[1, 3, 7, 8], [2, 5, 6], [4]]
ordered pairs in the relation: 26
n=1: total= 1 by number of classes: {1: 1}
n=2: total= 2 by number of classes: {1: 1, 2: 1}
n=3: total= 5 by number of classes: {1: 1, 2: 3, 3: 1}
n=4: total= 15 by number of classes: {1: 1, 2: 7, 3: 6, 4: 1}
n=5: total= 52 by number of classes: {1: 1, 2: 15, 3: 25, 4: 10, 5: 1}
n=6: total=203 by number of classes: {1: 1, 2: 31, 3: 90, 4: 65, 5: 15, 6: 1}Trace the first part by hand: 1 ~ 3 and 3 ~ 7 and 7 ~ 8 chain into {1, 3, 7, 8}; 2 ~ 5 ~ 6 gives {2, 5, 6}; 4 is mentioned in no pair, so by reflexivity alone it forms {4}. Pairs: 42 + 32 + 12 = 26. The second part of the output counts partitions, which we explain next.
Counting Equivalence Relations
Stirling numbers of the second kind
S(n, k) is the number of ways to partition an n-element set into exactly k non-empty blocks, which equals the number of equivalence relations on that set with exactly k classes.
Recurrence: look at element n. Either it is alone in a block (partition the other n − 1 elements into k − 1 blocks), or it joins one of the k blocks of a partition of the other n − 1 elements into k blocks:
S(n, k) = k · S(n−1, k) + S(n−1, k−1), S(0, 0) = 1, S(n, 0) = 0 for n ≥ 1n \ k | 1 | 2 | 3 | 4 | 5 | 6 | Row sum Bn |
|---|---|---|---|---|---|---|---|
1 | 1 | 1 | |||||
2 | 1 | 1 | 2 | ||||
3 | 1 | 3 | 1 | 5 | |||
4 | 1 | 7 | 6 | 1 | 15 | ||
5 | 1 | 15 | 25 | 10 | 1 | 52 | |
6 | 1 | 31 | 90 | 65 | 15 | 1 | 203 |
Check one entry with the recurrence: S(5, 3) = 3 · S(4, 3) + S(4, 2) = 3 · 6 + 7 = 25. ✓
Two closed forms worth knowing:
S(n, 2) = 2n−1 − 1. Put element 1 in the "first" block. Each of the other n − 1 elements either joins it or not: 2n−1 ways, minus the one way in which everybody joins and the second block is empty.
S(n, n − 1) = n(n − 1)/2. Exactly one block has two elements and the rest are singletons, so just choose that pair.
Bell numbers
The Bell number Bn is the total number of partitions of an n-element set, which is the number of equivalence relations on it: Bn = S(n, 1) + S(n, 2) + … + S(n, n).
n : 0 1 2 3 4 5 6 7 8
B_n : 1 1 2 5 15 52 203 877 4140Bell numbers also satisfy Bn+1 = Σk=0..n C(n, k) Bk: choose which k of the other n elements are not in the block of the new element, and partition those k elements in Bk ways. (Here C(n, k) = n! / (k!(n − k)!) is the number of ways to choose k items out of n; it is studied in detail later in the tutorial, but this is all we need now.) For example B4 = 1·1 + 3·1 + 3·2 + 1·5 = 15. ✓
Compare with the counts from Properties of Relations: on 4 elements there are 65536 relations, 64 reflexive-and-symmetric ones, but only 15 equivalence relations. Transitivity is a very strong condition.
Combining Equivalence Relations
Intersection is an equivalence relation. Reflexivity, symmetry and transitivity are all preserved by ∩. Its classes are the non-empty intersections of a class of R with a class of S. Example: (≡ mod 2) ∩ (≡ mod 3) is ≡ mod 6.
Union need not be. On ℤ, take ≡ mod 2 together with ≡ mod 3. Then 1 ~ 3 (mod 2) and 3 ~ 6 (mod 3), but 1 − 6 = −5 is divisible by neither 2 nor 3, so (1, 6) is missing: not transitive. The smallest equivalence relation containing R ∪ S is the transitive closure of R ∪ S (here it relates everything, because 1 is linked to every integer through such chains).
Refinement. Partition P1 refines P2 if every block of P1 lies inside some block of P2. In terms of relations: R1 ⊆ R2. Example: ≡ mod 4 refines ≡ mod 2, because [0]4 ∪ [2]4 = [0]2 and [1]4 ∪ [3]4 = [1]2. The k-equivalence partitions P0, P1, … used in DFA minimization form exactly such a chain of refinements.
Where Equivalence Relations Appear in CS
Modular arithmetic: ℤn is the quotient ℤ/≡n, the basis of hashing, checksums and RSA.
Connected components: in an undirected graph, "there is a path from u to v" is an equivalence relation; the classes are the components.
Strongly connected components: in a directed graph, "u reaches v and v reaches u" is an equivalence relation.
Automata: DFA minimization merges equivalent states, and the Myhill–Nerode relation on strings is an equivalence relation whose number of classes is the size of the minimal DFA.
Programming: a correct
equals()in Java (or__eq__in Python) must be reflexive, symmetric and transitive, andhashCode()must be constant on each class. Violating this silently breaks hash maps.
Common Mistakes
Checking only two of the three properties. "Reflexive and symmetric" is not enough: |a − b| ≤ 1 shows transitivity can fail.
Forgetting reflexive pairs when listing a relation. An element in a singleton block still contributes (a, a).
Counting pairs as Σ ni or Σ C(ni, 2). The correct count of ordered pairs is Σ ni2.
Confusing S(n, k) with C(n, k). S(4, 2) = 7 ways to split 4 items into 2 unlabeled groups; C(4, 2) = 6 ways to choose 2 items.
Assuming the union of equivalence relations is one. Only the intersection is guaranteed.
Calling a cover with overlapping or empty blocks a partition. Blocks must be non-empty, disjoint and must cover A.
Practice and GATE-Style Questions
Q1. How many equivalence relations are there on a set of 5 elements? How many of them have exactly 2 classes?
B5 = 52. With exactly 2 classes: S(5, 2) = 24 − 1 = 15.
Q2. How many equivalence relations on {1, 2, 3, 4} contain the pair (1, 2)?
1 and 2 must be in the same block, so glue them into a single "super-element". We are then partitioning 3 objects: B3 = 5.
Q3. An equivalence relation on a 7-element set has classes of sizes 3, 2, 2. How many ordered pairs does it contain?
32 + 22 + 22 = 9 + 4 + 4 = 17.
Q4. On ℤ, define a R b ⇔ 3a + 4b is divisible by 7. Is R an equivalence relation?
Note 3a + 4b = 7a − 4(a − b), so 7 | 3a + 4b ⇔ 7 | 4(a − b) ⇔ 7 | (a − b), because gcd(4, 7) = 1. So R is exactly congruence mod 7: yes, with 7 classes.
Q5. Can an equivalence relation on a 4-element set have exactly 6 ordered pairs?
We need block sizes summing to 4 with squares summing to 6. Options: 1+1+1+1 → 4; 2+1+1 → 6 ✓. So yes, for example the partition {{1, 2}, {3}, {4}}.
Q6. Interview: you implement equals() for 2-D points as "the distance between them is less than 0.001". What goes wrong?
The relation is reflexive and symmetric but not transitive: p ~ q and q ~ r can hold while p and r are 0.0018 apart. Hash-based collections and sorting/deduplication code assume transitivity, so results depend on insertion order. A fix is to snap points to a grid first and compare grid cells, which is a kernel and therefore a true equivalence relation.
Summary
An equivalence relation is reflexive, symmetric and transitive; it formalises "the same for our purposes".
The class [a] collects everything equivalent to a; two classes are either equal or disjoint.
Equivalence relations on A correspond one-to-one with partitions of A.
Every equivalence relation is the kernel of a function "a ~ b ⇔ f(a) = f(b)".
A relation with block sizes n1, …, nk has Σ ni2 ordered pairs.
Counting: S(n, k) relations with exactly k classes, Bn in total (1, 1, 2, 5, 15, 52, 203, …).
Intersections of equivalence relations are equivalence relations; unions in general are not.
An equivalence relation is a labelling in disguise: give each element a label, call two elements equivalent when their labels match, and the labels' groups are the classes.