Question

If $A$ is a finite set having $n$ elements, then the number of relations which can be defined in $A$ is

• A. $2^n$
• B. $n^2$
• C. $2^{n^2}$
• D. $n^n$

Answer 1

The correct option is C $2^{n^2}$

A relation is simply a subset of cartesian product $A\times A$.

If $A\times A=\left[\right(a_1,a_1),(a_1,a_2),.....(a_1,a_n),$

$(a_2,a_1),(a_2,a_2),........(a_2,a_n)$

$......$

$(a_n,a_1),(a_n,a_2).........(a_n,a_n)]$

We can select first element of ordered pair in $n$ ways and second element in $n$ ways.

So, clearly this set of ordered pairs contain $n^2$ pairs.

Now, each of these $n^2$ ordered pairs can be present in the relation or can't be. So, there are $2$ possibilities for each of the $n^2$ ordered pairs.

Thus, the total no. of relations is $2^{n^2}$.

Hence, option C is correct.