GATE CS 1993 Q8.4 — Propositional and First Order Logic

To find the number of elements in the power set of $A \times A$, we can break the problem down into two simple steps:

1. Find the size of the Cartesian product $A \times A$:
   Given that the set $A$ has $n$ elements, i.e., $|A| = n$.
   The Cartesian product $A \times A$ consists of all ordered pairs $(x, y)$ where $x, y \in A$.
   Therefore, the cardinality of $A \times A$ is: $$\lvert A \times A \rvert = \lvert A \rvert \times \lvert A \rvert = n \times n = n^2$$
2. Find the size of the power set of $A \times A$:
   For any finite set $S$, the number of elements in its power set $\mathcal{P}(S)$ is $2^{\lvert S \rvert}$.
   Substituting $S = A \times A$, we get: $$\lvert \mathcal{P}(A \times A) \rvert = 2^{\lvert A \times A \rvert} = 2^{n^2}$$

Thus, the number of elements in the power set of $A \times A$ is $2^{n^2}$, which corresponds to Option B.