The minimum number of elements that must be added to the relation R = {(a, b), (b, c), (b, d)} on the set {a, b, c, d} so that it is an equivalence relation, is __________.

Solution

Maths sir · 3 steps

Do not chase pairs one by one: find the equivalence classes first, then count every pair inside them.

1. Find the classes. An equivalence relation splits the set into classes, and every element of a class is related to every other. Here a is linked to b, and b is linked to both c and d. So a, b, c, d must all end up in one class.
2. Count the pairs. A single class of 4 elements means every ordered pair from {a, b, c, d} is in the relation. That is 4 × 4 = 16 pairs.

   Property needed	Pairs to add	Count
   Reflexive	(a,a), (b,b), (c,c), (d,d)	4
   Symmetric (reverse the given pairs)	(b,a), (c,b), (d,b)	3
   Transitive (through b)	(a,c), (c,a), (a,d), (d,a), (c,d), (d,c)	6

   16 - 3 = 4 + 3 + 6 = 13

3. So. The relation already has 3 of the 16 pairs, so the minimum number of pairs to add is 13.

The common slip: 7. Adding only the reflexive and symmetric pairs gives 4 + 3 = 7, not 13. The 6 pairs that transitivity forces through b are missing.

The idea to keep. For the smallest equivalence relation containing R, group the linked elements into classes. A class of k elements gives k² pairs. Subtract the pairs already in R.

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