Equivalence Relation MCQs: 12 Solved Questions on Classes and Partitions

Equivalence-relation questions become difficult when the same definition appears as a class, partition, closure or counting problem. Switch representations without losing the reflexive, symmetric and transitive tests. Start by identifying each type: nine MCQs, one MSQ and two NAT questions. For practice beyond these 12, continue from CS Fundamentals for Exams & Placements because these questions do not have individual practice-page links.

Related reading: relations in discrete mathematics and relation properties.

Use one partition to see the whole equivalence-relation picture

Let A = {0,1,2,3,4,5}, and define xRy when x mod 3 = y mod 3. Equal remainders give three equivalence classes:

[0] = {0,3}, [1] = {1,4}, [2] = {2,5}.

The relation is

{(0,0),(0,3),(3,0),(3,3),(1,1),(1,4),(4,1),(4,4),(2,2),(2,5),(5,2),(5,5)}.

Every (x,x) appears, so the relation is reflexive. The pair (0,3) has its reverse (3,0), illustrating symmetry. Also, 0R3 and 3R0 lead to 0R0. In general, if x and y have equal remainders, and y and z have equal remainders, then x and z do too. That proves transitivity. The three classes are non-empty, disjoint and their union is A, so they form a partition.

Fast test: check diagonal pairs, reverse pairs and chain endpoints, then read off the classes quickly. One absent diagonal, reverse or required endpoint is already a decisive counterexample, so stop as soon as you find it.

Questions 1-2: recognise the definition and reject a broken relation

Question 1

Which of the following represents an equivalence relation?

• A. Reflexive, Symmetric, Transitive

• B. Reflexive, Anti-Symmetric, Transitive

• C. Reflexive, Symmetric, Irreflexive

• D. Symmetric, Anti-Symmetric, Transitive

Answer: A. Reflexive, Symmetric, Transitive.

These are the three required properties. Symmetric demands (b,a) with (a,b), while antisymmetric restricts two-way pairs to a = b, so B is different. C conflicts because reflexive requires every diagonal while irreflexive forbids them. D omits reflexivity.

Question 2

UGC NET 2018, Computer Science, Paper 2 July

Which of the relations on {0, 1, 2, 3} is an equivalence relation?

• A. {(0, 0), (0, 2), (2, 0), (2, 2), (2, 3), (3, 2), (3, 3)}

• B. {(0, 0), (1, 1), (2, 2), (3, 3)}

• C. {(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0)}

• D. {(0, 0), (0, 2), (2, 3), (1, 1), (2, 2)}

Answer: B.

B is the identity relation. All four diagonal pairs are present, and symmetry and transitivity follow immediately. A lacks (1,1), C lacks (2,2) and (3,3), and D lacks (3,3). One missing diagonal pair disproves reflexivity, so no further testing is needed.

Questions 3-4: move between equivalence classes and partitions

Question 3

If R is an equivalence relation on a set A and a ∈ A, what is the equivalence class of a, denoted [a]?

• A. [a] = { x ∈ A | (a, x) ∈ R }

• B. [a] = { x ∈ A | x = a }

• C. [a] = { x ∈ A | (a, x) ∉ R }

• D. [a] = { x ∈ A | (x, a) ∉ R }

Answer: A.

[a] contains the elements related to a. Here [1] = {1,4}, not {1}. Symmetry allows (x,a) ∈ R; C and D negate membership.

Question 4

Which of the following is true about equivalence relations?

• A. They partition a set into disjoint subsets

• B. They combine a set into a single subset

• C. They divide a set into overlapping subsets

• D. They scatter a set into unrelated subsets

Answer: A. They partition a set into disjoint subsets.

Equivalence classes are identical or disjoint. Reflexivity puts every element in a class, so the classes cover the set. {0,3}, {1,4} and {2,5} show this. A universal class is possible but not required, so B is false.

Questions 5-6: count relations by counting partitions

Question 5

UPLT 2018, Computer Science

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

• A. 4

• B. 24

• C. 25

• D. 15

Answer: D. 15.

Each equivalence relation corresponds to one partition. Count partitions by their number of non-empty blocks:

S(4,1) + S(4,2) + S(4,3) + S(4,4) = 1 + 7 + 6 + 1 = 15.

Here is where the middle values come from. With two blocks, the size patterns are 3+1, giving 4 choices for the singleton, and 2+2, giving 3 pairings. Thus S(4,2) = 4 + 3 = 7. With three blocks, choose the only two-element block in C(4,2) = 6 ways. The total 15 is the fourth Bell number. The tempting value 4! = 24 counts orderings, not partitions.

Question 6

UGC NET 2016, Computer Science, Paper 2 June

How many different equivalence relations with exactly three different equivalence classes are there on a set with five elements ?

• A. 10

• B. 15

• C. 25

• D. 30

Answer: C. 25.

We need S(5,3), not the full Bell number. For block sizes 3+1+1, choose the triple in C(5,3) = 10 ways. For 2+2+1, choose the singleton in 5 ways, then pair the other four in 3 ways, giving 5 × 3 = 15. Therefore 10 + 15 = 25.

Questions 7-8: complete a relation and intersect two equivalence relations

Question 7

UPPSC Polytechnic Lecturer 2018, Computer Science

In the relation

R={(1,2),(2,3)},

the minimum number of ordered pairs that must be added to this set so that the enlarged relation is reflexive, symmetric, and transitive is:

• A. 4

• B. 5

• C. 6

• D. 7

Answer: D. 7.

On {1,2,3}, the chain 1R2 and 2R3 forces all three elements into one equivalence class. The completed relation is {1,2,3} × {1,2,3}, containing 3² = 9 ordered pairs. Two already exist, so 9 - 2 = 7 must be added: (1,1),(1,3),(2,1),(2,2),(3,1),(3,2),(3,3). No smaller closure can work.

Question 8

Suppose R₁ and R₂ are equivalence relations. The relation R₁ ∩ R₂ is:

• A. a reflexive closure of the relation

• B. a partial equivalence relation

• C. an equivalence relation

• D. not an equivalence relation

Answer: C. an equivalence relation.

Every diagonal pair belongs to both relations, so it belongs to their intersection. A pair's reverse belongs to both. If (a,b) and (b,c) are in the intersection, each relation contains the chain and therefore contains (a,c). Thus the intersection is reflexive, symmetric and transitive. A union need not be transitive, so the same conclusion does not automatically hold for unions.

Questions 9-10: recognise congruence and gcd as class-generating rules

Question 9

Let n be a fixed positive integer. Let R be a relation defined on the set of integers as (a,b)∈R iff a-b is divisible by n. The relation R is

• A. Reflexive only

• B. Symmetric only

• C. Transitive only

• D. An equivalence relation

Answer: D. An equivalence relation.

a-a = 0 is divisible by n, proving reflexivity. If n divides a-b, it divides b-a = -(a-b), proving symmetry. If it divides a-b and b-c, it divides their sum a-c, proving transitivity. For n = 3, these are exactly the three remainder classes from the opening example.

Question 10

Let N be the set of non-zero natural numbers. Define a binary relation R on N × N by (m, n) R (s, t) such that gcd(m, n) = gcd(s, t). The relation R is:

• A. Reflexive

• B. Symmetric

• C. Transitive

• D. Not equivalence

Answer: A, B and C.

This is an MSQ. Equality of gcd values is reflexive, symmetric and transitive because equality has all three properties. The pairs (6,9) and (21,24) have gcd 3, so they share a class. (10,15) has gcd 5, while (8,12) has gcd 4, placing them in different classes. A, B and C together reject D.

Questions 11-12: count classes and complement pairs from a partition

Question 11

Consider an equivalence relation R on the positive integers {2, 3, ..., 20}, defined by mRn iff m and n have the same largest prime divisor. How many equivalence classes does R have?

Answer: 8.

Group numbers by their largest prime divisor. The classes are:

• 2: {2,4,8,16}

• 3: {3,6,9,12,18}

• 5: {5,10,15,20}

• 7: {7,14}

• 11, 13, 17, 19: one singleton class each

The eight possible labels are 2,3,5,7,11,13,17,19, so there are 8 classes.

The class sizes total 19, matching the integers from 2 through 20. Every integer is accounted for.

Question 12

A relation R on A is induced by the partition π = {{1, 2, 7, 9, 11}, {5, 6, 8}, {3, 4, 10}, {12, 13}}. How many ordered pairs are in R', the complement of R in A × A?

Answer: 122.

The block sizes are 5,3,3,2, so |A| = 13 and |A × A| = 13² = 169. The induced equivalence relation contains every ordered pair within each block:

|R| = 5² + 3² + 3² + 2² = 25 + 9 + 9 + 4 = 47.

Therefore |R'| = 169 - 47 = 122. Do not use combinations here. A relation counts ordered pairs and includes diagonal pairs.

Equivalence-relation traps and the next practice step

Classify the task in ten seconds. Search for one counterexample before attempting a proof, and draw the partition whenever classes appear. For NAT questions, write the universe size before counting relation pairs.

Use Set Theory and Relations Explained for GATE if the theory needs rebuilding, then try the broader Set Theory and Relations MCQs. Retry only the missed questions after one day. If you want the full subject sequence and structured practice, continue with GATE Guidance by Sanchit Sir.