12 min readConcept sheetOften a 5-mark proof, or a 2 or 3-mark question; 1-mark MCQ on counting; also a JEE favourite

Equivalence relations and equivalence classes

A relation that is reflexive, symmetric and transitive is an equivalence relation. It splits the set into disjoint equivalence classes.

Equivalence relationReflexive + symmetric + transitive. All three must be proved.

Equivalence class of a[a] = {x ∈ A: (x, a) ∈ R}, the set of all elements related to a

Classes form a partitionAny two classes are either equal or disjoint, and together they make up the whole set A.

'n divides a − b' on ZAn equivalence relation with exactly n classes: [0], [1], ..., [n − 1]

What an equivalence relation does

An equivalence relation treats related elements as 'the same' for one purpose. 'Has the same PIN code as' groups people by area. 'Leaves the same remainder on division by 3' groups integers. To call R an equivalence relation you must show it is reflexive, symmetric and transitive, each with a general proof. If even one property fails, R is not an equivalence relation.

Proof: R = {(a, b): 3 divides a − b} is an equivalence relation on Z

This pattern of proof works for any 'divisible by n' relation.

1
Reflexive: for any a ∈ Z, a − a = 0 = 3 × 0. So 3 divides a − a, and (a, a) ∈ R.
2
Symmetric: let (a, b) ∈ R. Then a − b = 3k for some integer k.
3
So b − a = 3(−k), and −k is an integer. Hence (b, a) ∈ R.
4
Transitive: let (a, b) ∈ R and (b, c) ∈ R. Then a − b = 3k and b − c = 3m for some integers k and m.
5★
Add the two equations: a − c = (a − b) + (b − c) = 3(k + m).
k + m is an integer
6
So 3 divides a − c, and (a, c) ∈ R. So, R is reflexive, symmetric and transitive: an equivalence relation.

★ key step

Equivalence classes

The equivalence class [a] is the set of all elements related to a.
For the relation above, [0] = {..., −6, −3, 0, 3, 6, ...}, the multiples of 3.
[1] = {..., −5, −2, 1, 4, 7, ...} and [2] = {..., −4, −1, 2, 5, 8, ...}.
[3] = [0], [4] = [1], and so on. There are only three different classes.
The classes do not overlap, and their union is Z. Such a split is called a partition.
Any element of a class can name it: [1] = [4] = [−2].

Example 1: classes on a finite set

Problem

On A = {1, 2, 3, ..., 10}, R = {(a, b): a − b is divisible by 3} is an equivalence relation. Write all its equivalence classes.

Working

Rule: [a] is the set of all x ∈ A with x − a divisible by 3.
[1]: the numbers that leave remainder 1 on division by 3: {1, 4, 7, 10}.
[2]: remainder 2: {2, 5, 8}.
[3]: remainder 0: {3, 6, 9}.
Check: 4 + 3 + 3 = 10 elements, none repeated, so the classes cover A with no overlap.

Answer

The equivalence classes are {1, 4, 7, 10}, {2, 5, 8} and {3, 6, 9}.

Example 2: a relation on pairs (5-mark style)

Problem

On N × N, define (a, b) R (c, d) if ad = bc. Show that R is an equivalence relation.

Working

Rule: prove reflexive, symmetric and transitive in turn.
Reflexive: ab = ba, so (a, b) R (a, b) for every (a, b).
Symmetric: let (a, b) R (c, d). Then ad = bc.
So cb = da, which says (c, d) R (a, b).
Transitive: let (a, b) R (c, d) and (c, d) R (e, f). Then ad = bc and cf = de.
Multiply the two equations: (ad)(cf) = (bc)(de), that is (af)(cd) = (be)(cd).
c and d are natural numbers, so cd ≠ 0. Divide by cd: af = be.
So (a, b) R (e, f).

Answer

R is reflexive, symmetric and transitive, so it is an equivalence relation. Each class is a set of equal fractions, e.g. [(1, 2)] = {(1, 2), (2, 4), (3, 6), ...}.

Quick facts for MCQs

The smallest equivalence relation on A is the identity relation {(a, a): a ∈ A}.
The largest is the universal relation A × A.
On A = {1, 2, 3} there are exactly 5 equivalence relations, one for each way of splitting A into classes.
'a ≤ b' on R is not an equivalence relation: it is reflexive and transitive but not symmetric.

In real life

When a school sorts its students into houses, or a courier sorts parcels by PIN code, it uses an equivalence relation. 'Same house' or 'same PIN code' splits everyone into classes that never overlap.

Exam angle

1 marks: “How many equivalence relations are there on the set A = {1, 2, 3}?” 5. They match the ways to split A into classes: {1}{2}{3}; {1, 2}{3}; {1, 3}{2}; {2, 3}{1}; {1, 2, 3}.

3 marks: “Show that R = {(a, b): a − b is divisible by 5} on Z is an equivalence relation, and write the class [2].” Reflexive: a − a = 0 = 5 × 0. Symmetric: a − b = 5k gives b − a = 5(−k). Transitive: a − b = 5k and b − c = 5m give a − c = 5(k + m). [2] = {..., −8, −3, 2, 7, 12, ...}.

5 marks: “On A = N × N, define (a, b) R (c, d) if a + d = b + c. Show that R is an equivalence relation.” Reflexive: a + b = b + a. Symmetric: a + d = b + c gives c + b = d + a. Transitive: add a + d = b + c and c + f = d + e, then cancel c + d to get a + f = b + e. So R is an equivalence relation.

Remember it

RST in order: Reflexive, Symmetric, Transitive. Miss one and it is not an equivalence relation.