GATE CSE 1993 | Question: 8.4

Question

Let A be a finite set of size n. The number of elements in the power set of $A\times A$ is:

• A. $2^{2^n}$
• B. $2^{n^2}$
• C. $\left(2^n\right)^2$
• D. $\left(2^2\right)^n$
• E. None of the above

Comments

Asking for number of elements in $A \times A$ is same as asking for number of relations possible over set $A.$

Every relation on set $A$ is subset of $A \times A.$ Every subset of $A \times A$ is a relation over set $A$.

Power set of $A \times A$ contains subsets of $A \times A$. So, Every element in power set of $A \times A$ is a relation on set $A.$

Hence, the cardinality of $P(A \times A)$ is same as number of relations possible on set $A.$

If $|A| = n, $ then $|P(A)| = 2^n, |A \times A| = n^2$, So, $|P(A \times A)| = 2^{n^2} = 2^{(n^2)}$

Detailed Video Solution

Answer 1

Cardinality of $A\times A = n^2$
Cardinality of power  set of $A\times A = 2^{n^2}$

Correct Answer: $B$

Comments

Say set is A= {1,2,3}=n

Subset of set A ={phi, {1} , {2} , {3} , {1,2} , {2,3}, {1,3} , {1,2,3}}=2ⁿ

Now, $A\times A=\left \{ 1,2,3 \right \}\times \left \{ 1,2,3 \right \}$

                        $=\left \{ \left \{ 1,1 \right \},\left \{ 1,2 \right \} \left \{ 1,3 \right \}\left \{ 2,1 \right \}\left \{ 2,2 \right \}\left \{ 2,3 \right \}\left \{ 3,1 \right \}\left \{ 3,2 \right \}\left \{ 3,3 \right \}\right \}$

So, number of subsets will be$2^{n^{2}}$

---

This is same as the total number of relations on Set A

Answer 2

$|A| = n$  ,  $ |p(A)| = 2^n$

$| A×A| =n^2$

$| p(A×A)|$ =$2^{n^{2}}$

Option (B) is the correct answer.