What is the possible number of reflexive relations on a set of 5 elements?
2010
What is the possible number of reflexive relations on a set of 5 elements?
- A.
2^{10}
- B.
2^{15}
- C.
2^{20}
- D.
2^{25}
Attempted by 536 students.
Show answer & explanation
Correct answer: C
Answer: There are 2^{20} = 1,048,576 reflexive relations on a 5-element set.
Key insight: Count total ordered pairs, fix diagonal pairs required by reflexivity, and count choices for the remaining pairs.
Total ordered pairs on a 5-element set: 5 × 5 = 25.
Reflexivity requires the 5 diagonal pairs (a,a) for each element to be included, so those are fixed.
Remaining pairs: 25 − 5 = 20. Each of these 20 pairs can either be included or excluded independently, giving 2^{20} possibilities.
A video solution is available for this question — log in and enroll to watch it.