If R is the smallest equivalence relation on the set {1,2,3,4} such that {(1,2),(1,3)} ⊂ R, then the number of elements in R is __________.

Solution

Maths sir · 4 steps

Think in groups: 1, 2 and 3 get glued into one class, and 4 sits alone.

1. Build the classes. An equivalence relation splits the set into classes. Since 1 is related to 2 and to 3, all three must fall in one class {1,2,3}. Nothing forces 4 to join, so the smallest choice keeps {4} as its own class.
2. Count pairs per class. Inside a class of size n, every element is related to every element, which gives n² ordered pairs. Pairs across different classes are not included.

   |R| = 3² + 1² = 9 + 1 = 10

3. Check by listing. Reflexive: (1,1),(2,2),(3,3),(4,4). Symmetric: (1,2),(2,1),(1,3),(3,1). Transitive: (2,1) and (1,3) force (2,3), and then (3,2). That is 4 + 4 + 2 = 10 pairs.
4. So. The smallest such equivalence relation has 10 elements, option (b).

The idea to keep. For the smallest equivalence relation, merge only the elements you are forced to merge, then add n² for each class of size n.

Answer from the NTA final answer key. Solution by PrepWiser.