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

Step 1: Recall what a relation is.
A relation on a set $A$ is any collection of ordered pairs from $A \times A$. So first we count how many ordered pairs exist.

Step 2: Count all ordered pairs.
With $5$ elements, $A \times A$ has $5 \times 5 = 25$ ordered pairs.

Step 3: Understand reflexive.
A relation is reflexive if it contains every diagonal pair $(a,a)$. With $5$ elements there are $5$ such diagonal pairs, and all of them MUST be present.

Step 4: Separate forced pairs from free pairs.
Of the $25$ pairs, $5$ are forced in. That leaves $25 - 5 = 20$ off-diagonal pairs, each of which we may include or leave out as we like.

Step 5: Count the choices.
Each of those $20$ pairs has $2$ options (in or out), so the number of reflexive relations is $2^{20}$.

Step 6: State the answer.
Hence the count of reflexive relations on a $5$-element set is $2^{20}$. \[ \boxed{2^{20}} \]