Let A={1,2,3,4} and R={(1,2),(2,3),(1,4)} be a relation on A. Let S be the equivalence relation on A such that R ⊂ S and the number of elements in S is n. Then, the minimum value of n is __________.

Solution

Maths sir · 4 steps

Think in equivalence classes: R links 1, 2, 3 and 4 into one chain, so S must relate everything to everything.

1. Classes, not pairs. An equivalence relation splits A into classes, and every element is related to every element of its own class. So find which elements R forces into the same class.
2. Follow the links. (1,2) puts 1 and 2 together, and (2,3) adds 3 to that class. (1,4) adds 4 as well. All four elements are forced into a single class {1,2,3,4}.
3. Count the pairs. One class of size 4 means every ordered pair (a,b) with a, b ∈ A is in S. There is no smaller choice, because transitivity forces each of these pairs in.

   S = A × A ⇒ n = 4 × 4 = 16

4. So. The smallest equivalence relation containing R is A × A, so the minimum value of n is 16.

The common slip: 10. Adding only the 4 reflexive pairs and the 3 reversed pairs to R gives 10, but transitivity still forces pairs like (1,3), (2,4) and (3,4) in.

The idea to keep. To build the smallest equivalence relation containing R, join the linked elements into classes. A class of size k contributes k² pairs, so add k² over all the classes.

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