GATE CS 2000 Q2.6 — Sets, Relations and Functions

We can evaluate the options by analyzing their definitions and cardinality:

• Option A: $P(P(S)) = P(S)$ is false. For any finite set $S$ with $n$ elements, $|P(S)| = 2^n$ and $|P(P(S))| = 2^{2^n}$. Since $2^n \neq 2^{2^n}$, their cardinalities differ.
• Option C: $P(S) \cap S = P(S)$ implies $P(S) \subseteq S$. This is false because $|P(S)| = 2^n > n = |S|$ for any finite set.
• Option D: $S \notin P(S)$ is false because every set is a subset of itself ($S \subseteq S$), which means $S \in P(S)$ is always true.

For Option B, let $X$ be an element in the intersection $P(S) \cap P(P(S))$:

1. $X \in P(S) \implies X \subseteq S$
2. $X \in P(P(S)) \implies X \subseteq P(S)$

The empty set $\emptyset$ is always a subset of any set, so $\emptyset \subseteq S$ and $\emptyset \subseteq P(S)$. Thus, $\emptyset \in P(S)$ and $\emptyset \in P(P(S))$, meaning $\emptyset \in P(S) \cap P(P(S))$.

If there were any non-empty set $X$ in the intersection, there would exist some element $x \in X$ such that $x \in S$ (since $X \subseteq S$) and $x \in P(S)$ (since $X \subseteq P(S)$). Under standard set theory where elements of a set are distinct from its subsets ($S \cap P(S) = \emptyset$), no such $x$ can exist. Thus, the only common element is $\emptyset$, making $P(S) \cap P(P(S)) = \{\emptyset\}$ always true.