• Foundation
  • About 18 min
  • 5 practice questions

Equivalence relations and equivalence classes

Prove that a relation is an equivalence relation, find its equivalence classes, and see how an equivalence relation splits a set into disjoint pieces (a partition).

If something looks wrong, please tell us.

By the end of this lesson you can

  • Prove all three properties needed for an equivalence relation.
  • Write down the equivalence class [a] of an element.
  • Explain why equivalence classes form a partition, and build a relation from a given partition.

Sorting is everywhere: books by number of pages, students by house, integers by remainder. Each time we sort, we use a relation that behaves like 'is the same as' in some respect. Mathematics calls such a relation an equivalence relation, and the groups it produces are its equivalence classes.

Definition

A relation R in a set A is an equivalence relation if it is reflexive, symmetric and transitive.

— Definition

Any rule of the form 'a and b have the same ___' (same remainder, same length, same first letter) gives an equivalence relation, because 'same as' is automatically reflexive, symmetric and transitive.

Worked example 1: congruence modulo 5

In the set Z of integers, let R = {(a, b) : 5 divides a − b}. Prove that R is an equivalence relation.

  1. Reflexive: a − a = 0 = 5 × 0, so 5 divides a − a and (a, a) ∈ R for every integer a.
  2. Symmetric: if 5 divides a − b, then a − b = 5k for some integer k. So b − a = 5(−k), and 5 divides b − a; hence (b, a) ∈ R.
  3. Transitive: if a − b = 5k and b − c = 5m for integers k and m, then a − c = (a − b) + (b − c) = 5(k + m). So 5 divides a − c and (a, c) ∈ R.
  4. All three hold, so R is an equivalence relation.

Equivalence classes

For an equivalence relation R in A, the equivalence class of an element a is [a] = {x ∈ A : x R a}, the set of everything related to a. In Worked example 1, two integers are related exactly when they leave the same remainder on division by 5. So there are five classes: [0] = {…, −10, −5, 0, 5, 10, …}, [1] = {…, −9, −4, 1, 6, 11, …}, [2], [3] and [4]. Note that [5] = [0] and [7] = [2]: a class can have many names.

These classes have three properties, and they hold for every equivalence relation:

  • all elements inside one class are related to one another;
  • no element of one class is related to an element of a different class;
  • the classes are pairwise disjoint and their union is the whole set.

A collection of non-empty, pairwise disjoint subsets whose union is A is called a partition of A. So every equivalence relation partitions its set. The converse is also true: given a partition, define a R b when a and b lie in the same piece; this R is an equivalence relation whose classes are exactly the pieces.

Worked example 2: a finite set

Let A = {1, 2, 3, …, 10} and R = {(a, b) : a and b leave the same remainder on division by 4}. Working: it is a 'same as' relation, so it is an equivalence relation (the proof is the same as Worked example 1 with 4 in place of 5). Sorting by remainder: remainder 0 gives {4, 8}; remainder 1 gives {1, 5, 9}; remainder 2 gives {2, 6, 10}; remainder 3 gives {3, 7}. These four classes are disjoint and together contain all ten numbers. The set of elements related to 6 is [6] = {2, 6, 10}.

A = {1, 2, …, 10} sorted by remainder on division by 4

  • [0] (remainder 0)
    • 4
    • 8
  • [1] (remainder 1)
    • 1
    • 5
    • 9
  • [2] (remainder 2)
    • 2
    • 6
    • 10
  • [3] (remainder 3)
    • 3
    • 7
Four disjoint classes whose union is A: a partition.

Worked example 3: pairs of positive integers

On the set of ordered pairs of positive integers, define (p, q) R (r, s) when p + s = q + r. Working: p + q = q + p, so (p, q) R (p, q) (reflexive). If p + s = q + r then r + q = s + p, so (r, s) R (p, q) (symmetric). If p + s = q + r and r + v = s + u, add the two: p + s + r + v = q + r + s + u, and cancelling r + s gives p + v = q + u, so (p, q) R (u, v) (transitive). Hence R is an equivalence relation. (Each class collects the pairs with the same difference p − q.)

Intersection and union

If R₁ and R₂ are equivalence relations in A, then R₁ ∩ R₂ is also an equivalence relation: each property holds in both, so it holds in their common part. The union need not be. In A = {1, 2, 3}, take R₁ = {(1, 1), (2, 2), (3, 3), (1, 2), (2, 1)} and R₂ = {(1, 1), (2, 2), (3, 3), (2, 3), (3, 2)}. The union contains (1, 2) and (2, 3) but not (1, 3), so it is not transitive.

Counting equivalence relations

Because equivalence relations match partitions one-to-one, counting one counts the other. The set {1, 2, 3} has exactly 5 partitions: {1}{2}{3}; {1, 2}{3}; {1, 3}{2}; {2, 3}{1}; {1, 2, 3}. So it has 5 equivalence relations. The ones containing (1, 2) are the partitions where 1 and 2 share a piece: {1, 2}{3} and {1, 2, 3}, so there are 2.

Key takeaways: an equivalence relation is reflexive, symmetric and transitive. Its classes [a] are disjoint, cover the set, and form a partition; a partition, in turn, defines an equivalence relation. Intersections of equivalence relations are equivalence relations; unions may not be.

Check your understanding

  1. 1. In Z, R = {(a, b) : 3 divides a − b}. Which set is the equivalence class [2]?

    1. {…, −4, −1, 2, 5, 8, …}
    2. {…, −3, 0, 3, 6, …}
    3. {2, 5, 8} only
    4. {…, −2, 1, 4, 7, …}
    Show answer

    Answer: A. [2] contains every integer x with 3 dividing x − 2, i.e. x leaves remainder 2 on division by 3: …, −4, −1, 2, 5, 8, … (−4 − 2 = −6 and −1 − 2 = −3 are multiples of 3). {…, −3, 0, 3, …} is [0], {…, −2, 1, 4, …} is [1], and the class is infinite, not just three numbers.

  2. 2. How many equivalence relations are there on the set {a, b, c}?

    1. 3
    2. 4
    3. 5
    4. 8
    Show answer

    Answer: C. Equivalence relations correspond to partitions. The partitions of a three-element set are: all separate; {a, b}{c}; {a, c}{b}; {b, c}{a}; all together. That is 5.

  3. 3. A = {1, 2, 3, 4, 5, 6} and R = {(a, b) : a − b is divisible by 3}. How many equivalence classes are there and what is [4]?

    1. 2 classes; [4] = {2, 4, 6}
    2. 3 classes; [4] = {1, 4}
    3. 6 classes; [4] = {4}
    4. 3 classes; [4] = {4, 5, 6}
    Show answer

    Answer: B. Remainders on division by 3 split A into {3, 6}, {1, 4} and {2, 5}: three classes. 4 leaves remainder 1, so [4] = {1, 4} (4 − 1 = 3 is divisible by 3).

  4. 4. Assertion (A): The union of two equivalence relations in a set is always an equivalence relation.
    Reason (R): The intersection of two equivalence relations in a set is always an equivalence relation.

    1. Both A and R are true, and R is the correct explanation of A
    2. Both A and R are true, but R is not the correct explanation of A
    3. A is true but R is false
    4. A is false but R is true
    Show answer

    Answer: D. A is false: with R₁ pairing 1 and 2 and R₂ pairing 2 and 3 in {1, 2, 3}, the union contains (1, 2) and (2, 3) but not (1, 3), so it is not transitive. R is true: each property holding in both relations also holds in their common part.

  5. 5. Which of these relations in the set of all students of a school is NOT an equivalence relation?

    1. a R b if a and b are in the same class
    2. a R b if a and b were born in the same month
    3. a R b if a and b have the same height in cm
    4. a R b if a is taller than b
    Show answer

    Answer: D. 'Is taller than' is not reflexive (no one is taller than themselves) and not symmetric. The other three are 'same as' relations, so each is reflexive, symmetric and transitive.

Sign in to keep track of the lessons you finish.

Next lesson → One-one, onto and bijective functions

Privacy · Terms · Refunds · Delivery