The number of binary relations on a set with n elements is: A. 2^n B. n^2 C. 2^(n^2) D. None of the above

GATE 1999 · Discrete Mathematics · Relations · easy

Answer: C. 2^(n^2)

1. Count ordered pairs in A x A: A set A with n elements: A x A has n choices for the first component and n for the second, giving n^2 ordered pairs total.
2. Count subsets of A x A: Each of the n^2 pairs independently belongs or does not belong to the relation. By the product rule: 2 * 2 * ... * 2 (n^2 times) = 2^(n^2). This is the number of binary relations on A.