Question

If a set \(A\) contains \(5\) elements, then the number of reflexive relations on \(A\) is

• A. \(2^5\)
• B. \(2^{25}\)
• C. \(2^{24}\)
• D. \(2^{20}\)

Hint:

For a set containing \(n\) elements: \[ \text{Number of reflexive relations} = 2^{\,n^2-n} \] because \(n\) diagonal pairs are compulsory and the remaining \(n^2-n\) pairs are optional.

Answer 1

The Correct Option is D

Concept: If a set contains \(n\) elements, then \[\begin{aligned} |A\times A| = n^2 \end{aligned}\] A reflexive relation must contain all diagonal elements \[ (a,a) \] for every \(a\in A\). The remaining pairs may be chosen freely.

Step 1: Find the total number of ordered pairs. Since \[ n=5 \] \[\begin{aligned} |A\times A| = 5^2 = 25 \end{aligned}\]

Step 2: Count the compulsory pairs. For reflexivity, \[ (a,a) \] must belong to the relation for each element of \(A\). Hence the number of compulsory pairs is \[\begin{aligned} 5 \end{aligned}\]

Step 3: Count the free choices. Remaining pairs: \[\begin{aligned} 25-5=20 \end{aligned}\] Each pair may either be included or excluded. Therefore, \[\begin{aligned} \text{Number of reflexive relations} = 2^{20} \end{aligned}\] \[\begin{aligned} \boxed{2^{20}} \end{aligned}\] Hence, option \(\mathbf{(D)}\) is correct.