For a set A containing n elements, how many binary relations can be defined on…
1999
For a set A containing n elements, how many binary relations can be defined on A?
- A.
n²
- B.
2^n
- C.
2^(n²)
- D.
None of the above
Attempted by 63 students.
Show answer & explanation
Correct answer: C
The correct answer is: 2^(n²).
Let A be a set with n elements. A binary relation on A is any subset of A × A.
The Cartesian product A × A contains n² ordered pairs because there are n choices for the first component and n choices for the second component.
Every subset of A × A is one possible binary relation. A set with n² elements has 2^(n²) subsets.
Therefore, the number of binary relations on a set with n elements is 2^(n²).