Equivalence Relations, Equivalence Classes and Set Partitions: Worked Examples

Follow a finite modulo-3 relation from its ordered pairs to three classes and one partition, then reverse the process and practise fast exam checks.

KnowledgeGate Team

Exam prep & CS education

Updated 13 Nov 20265 min read
Equivalence Relations, Equivalence Classes and Set Partitions: Worked Examples

Checking whether a relation is reflexive, symmetric and transitive is only the first step. Exam questions often switch immediately to equivalence classes and partitions, where similar-looking objects can cause confusion. A finite relation can be traced from its ordered pairs to its classes and partition, then reconstructed from the partition.

Equivalence relation means all three tests must hold

A relation R on a set A is a subset of A x A. We write aRb when (a,b) in R. For R to be an equivalence relation, all three conditions must hold:

  1. Reflexive: aRa for every a in A.

  2. Symmetric: if aRb, then bRa.

  3. Transitive: if aRb and bRc, then aRc.

Use a fixed checking order on a finite relation. First confirm that every diagonal pair (a,a) is present. Next search for a pair whose reverse is missing. Finally, combine composable pairs (a,b) and (b,c) and check whether (a,c) follows. One counterexample disproves a property, but a proof must cover arbitrary elements.

Keep the objects separate: R is a set of ordered pairs, [a] is one equivalence class, and A/R is the set of distinct equivalence classes. Review Set Theory and Relations Explained if Cartesian products or relation notation need revision.

Worked example: prove congruence modulo 3 is an equivalence relation

Let A = {0,1,2,3,4,5,6,7}, and define a R b exactly when 3 divides (a - b). The complete relation, grouped by equivalence class, is:

  • Class {0,3,6}: (0,0), (0,3), (0,6), (3,0), (3,3), (3,6), (6,0), (6,3), (6,6).

  • Class {1,4,7}: (1,1), (1,4), (1,7), (4,1), (4,4), (4,7), (7,1), (7,4), (7,7).

  • Class {2,5}: (2,2), (2,5), (5,2), (5,5).

It contains 22 ordered pairs. Now prove the properties algebraically.

  • Reflexive: for every a in A, a-a=0, and 3 divides 0. Therefore aRa.

  • Symmetric: if 3 divides (a-b), then 3 also divides -(a-b)=b-a. Therefore aRb implies bRa.

  • Transitive: if 3 divides (a-b) and 3 divides (b-c), then 3 divides their sum, (a-b)+(b-c)=a-c. Therefore aRb and bRc imply aRc.

For a concrete trace, 7R4 because 7-4=3, and 4R1 because 4-1=3. Hence 7R1 because 7-1=6. This illustrates the general proof, but it does not replace it.

Compute every equivalence class and the quotient set

By definition, [a] = {x in A : x R a}. Applying it to every residue group gives:

  • [0] = [3] = [6] = {0,3,6}.

  • [1] = [4] = [7] = {1,4,7}.

  • [2] = [5] = {2,5}.

Why is [0]=[3], rather than two different classes? An element x lies in [0] exactly when x-0 is divisible by 3. It lies in [3] exactly when x-3 is divisible by 3. Subtracting 3 does not change divisibility by 3, so both definitions select {0,3,6}.

After repeated classes are removed, the quotient set is A/R = {{0,3,6}, {1,4,7}, {2,5}}.

Thus |A/R|=3, while |A|=8 and |R|=22. These numbers count different things.

Set diagram of A={0,1,2,3,4,5,6,7} partitioned into C0, C1, and C2, with 22 directed relation arrows and three equivalence classes.

Why equivalence classes and partitions are two views of the same structure

Equivalence classes always partition the base set. First, every x in A belongs to [x] by reflexivity, so the classes cover A. Suppose z belongs to both [a] and [b]. Then z R a and z R b. Symmetry gives a R z, and transitivity gives a R b. If x belongs to [a], then x R a, so x R b and x belongs to [b]. The reverse inclusion follows in the same way. Therefore [a] = [b], which proves that any two classes are equal or disjoint.

Now reverse the construction. Let S = {a,b,c,d,e}, and let the partition P = {{a,b}, {c}, {d,e}}.

Define x ~ y when x and y lie in the same block of P. The induced relation is {(a,a), (a,b), (b,a), (b,b), (c,c), (d,d), (d,e), (e,d), (e,e)}.

Every element is in the same block as itself, so the relation is reflexive. If x shares a block with y, then y shares it with x, so it is symmetric. If x and y share a block and y and z share a block, disjointness forces that block to be the same one, so x and z share it. That proves transitivity.

Partition diagram for {{a,b},{c},{d,e}} beside a 5 by 5 relation matrix, with nine marked cells and total pair contribution 9.

This partition-to-quotient idea appears again in algebraic structures, where a larger object is organised through equivalent elements.

Common traps and fast counterexamples

Confusing elements, classes and pairs. The modulo-3 example has 8 elements, 3 distinct classes and 22 relation pairs. In general, if a finite equivalence relation has classes C1, C2, ..., Ck, count the pairs class by class.

The pair-count formula is |R| = |C1|^2 + |C2|^2 + ... + |Ck|^2, because every ordered pair within each class belongs to the relation.

Ignoring the base set. The relation {(1,1),(2,2),(1,2),(2,1)} is an equivalence relation on {1,2}. It is not reflexive on {1,2,3}, because (3,3) is missing.

Accepting two properties. The relation <= on {1,2,3} is reflexive and transitive, but not symmetric: 1 <= 2, while 2 <= 1 is false.

Treating overlaps as partition blocks. The sets {1,2} and {2,3} overlap. Under the rule "in the same listed block", 1R2 and 2R3, but 1R3 is false, so transitivity fails. Merge them into {1,2,3}, or choose genuinely disjoint blocks.

How exams turn the concept into questions

First, a question may ask whether a relation is an equivalence relation. Search for the cheapest decisive counterexample before writing a full proof. If the relation survives, prove the properties using arbitrary a,b,c.

Second, it may ask for a class, the quotient set, or the number of relation pairs. If the class sizes are 4, 3 and 1, there are 3 distinct classes on 4 + 3 + 1 = 8 elements. The relation contains 4^2 + 3^2 + 1^2 = 16 + 9 + 1 = 26 ordered pairs.

Third, a question may give a partition and ask for the relation as an ordered-pair list, matrix or graph. After completing both examples above, use the Discrete Mathematics Set Theory and Relations MCQs for practice. Work through the same moves without assuming any fixed exam frequency or marks pattern.

Short version and the next step

  • All three properties are compulsory.

  • Equivalent elements have the same equivalence class.

  • Distinct equivalence classes never overlap.

  • All equivalence classes together cover the base set.

  • Every partition induces an equivalence relation by relating elements in the same block.

As a final self-check, why is [4]={1,4,7}, why does [4]=[7], and why do the three class sizes produce 22 pairs? All three statements follow because 4 and 7 have the same residue modulo 3, while the pair count is 3^2+3^2+2^2=22.

For structured mathematics study, continue with Engineering Mathematics. For the wider preparation path, use GATE Guidance by Sanchit Sir, and compare the live options in the GATE course catalogue.