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

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:
Reflexive: aRa for every a in A.
Symmetric: if aRb, then bRa.
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.

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.

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.
Keep learning
Equivalence Relation MCQs: 12 Solved Questions on Classes and Partitions
Solve 12 published equivalence relation questions, then check each answer through definitions, partitions, closures and careful ordered-pair counting.
Reflexive and Irreflexive Relations: Counts, Properties and Worked Examples
Learn to classify a relation from its diagonal, count the possible relations on an n-element set, and avoid the common confusion between irreflexive and not reflexive.
Cartesian Product and Relations: Inverse, Complement and Worked Examples
Learn how a Cartesian product defines the universe of a relation, then compute inverse and complement operations through small, fully checked examples.
Ex-OR and Ex-NOR Gates Explained: Truth Tables, Relations and a Worked Circuit
Learn why Ex-OR detects difference and Ex-NOR detects equality, then trace a three-input circuit and avoid the binary-cascade trap.





