MathematicsRelations and FunctionsJEE

Relations and Functions · Part 3 of 20

Equivalence Relations and Bell Numbers

A relation that is reflexive, symmetric and transitive sorts A into classes. Equivalence relations match partitions, so they are counted by Bell numbers. The part ends with the minimum pairs needed for a required property.

Builds on: Part 2 · Reflexive, Symmetric and Transitive Relations.

Video coming soon

Classes

Equivalence relation = blocks

|a − b| even on {1, …, 5} is an equivalence relation with classes [1] = {1, 3, 5} and [2] = {2, 4}. Listed in class order, its grid becomes solid squares along the diagonal.

Grid with two solid blocks. — Classes are identical or disjoint and cover A.

The five partitions of a three-element set. — From all apart (I_A) to all together (A × A).

Counting

Partitions of {1, 2, 3}

Every equivalence relation is a partition into classes, and every partition gives one. {1, 2, 3} has 5 partitions, so 5 equivalence relations. Those containing (1, 2) keep 1 and 2 together: 2 of them.

Bell numbers

$B_{n + 1} = \sum^{n} C_{k} B_{k}$

Choose the k elements outside the new element's block, in $^{n} C_{k}$ ways, and partition them in $B_{k}$ ways. $B_{1} = 1$ , $B_{2} = 2$ , $B_{3} = 5$ , $B_{4} = 15$ , $B_{5} = 52$ .

Bell number recurrence. — B₀ = 1 starts the recurrence.

Minimum pairs

Reflexive, symmetric, not transitive

A = {1, 2, 3}, R = {(1, 2), (2, 1)}. Reflexive but not symmetric: add the diagonal and one unpaired pair, 4. Reflexive and symmetric but not transitive: diagonal plus (1, 3), (3, 1), 5; now 2 → 1 → 3 needs (2, 3).

Summary

Key formulas

B_{n + 1} = \sum_{k = 0}^{n}^{n} C_{k} B_{k}, B_{0} = 1

Equivalence relation, classes and Bell numbers

B_{1} = 1, B_{2} = 2, B_{3} = 5, B_{4} = 15

Equivalence relation, classes and Bell numbers

Worked examples

From the video

1. Equivalence relations on {1, 2, 3}?

2. A = {1, 2, 3}. Equivalence relations containing (1, 2)?

3. On P(X), A R B iff A ⊂ B. Equivalence?

No (reading ⊂ as ⊆): reflexive and transitive, not symmetric.

4. On P(S), A R B iff A ∩ X = B ∩ X = φ and A ∪ X = B ∪ X for some X. Prove R is an equivalence.

The conditions force A = A ∩ B = B, so R is equality; X = φ gives A R A.

JEE-style question

Your turn

The number of equivalence relations on the set {1, 2, 3, 4} is:

(a)5

(b)14

(c)15

(d)16

Show the answer and the traps

It is the Bell number B₄ = 15. Option (c).

5 is B₃, for a 3-element set. 14 misses one partition, usually the all-apart one, which is I_A.

16 = 2⁴ counts subsets of A, not partitions.

Watch out

Common mistakes

Counting partitions and forgetting the all-apart oneI_A is an equivalence relation too: it is the partition into singletons.

Adding one pair for symmetry and ignoring the new chains it createsEvery added pair can break or force transitivity; recheck.

Reading ⊂ as proper subset in the P(X) questionThen R isn't even reflexive; the intended reading is ⊆.

Practice

Try these

1. Show R = {(a, b) : 3 divides a − b} on Z is an equivalence relation and give its classes.

Reflexive (0), symmetric, transitive (sums of multiples of 3); classes [0], [1], [2] by remainder.

2. How many equivalence relations are there on a 5-element set?

B₅ = 1 + 4 + 12 + 20 + 15 = 52.

3. A = {1, 2, 3}. Equivalence relations containing both (1, 2) and (2, 3)?

1: all three elements must be in one class.

4. R = {(1, 1), (2, 2), (3, 3), (1, 2), (2, 1)} on {1, 2, 3}. Equivalence classes?

{1, 2} and {3}.