Cantor's Theorem

Statement of the theorem

Let $A$ be a non-empty set, then there does not exist any onto function $f$ from $A$ to $P(A)$.

Proof of the theorem

Let $f: A \rightarrow P(A)$ be a function. For each $x \in A$, we have $f(x) \in P(A)$, so $f(x) \subset A$.

Define the set $X = \{x \in A \mid x \notin f(x)\}$. Since $X \subseteq A$, it follows that $X \in P(A)$.

Now, if $f$ is onto, then the set $X$, defined above, has a preimage, i.e., there exists an $\alpha \in A$ such that $f(\alpha) = X$.  Now consider the following cases-

Case (i): If $\alpha \in X$, then by the definition of $X$, we have $\alpha \notin f(\alpha)$.

Since $f(\alpha) = X$, this implies $\alpha \notin X$, which is a contradiction.

Case (ii): If $\alpha \notin X$, then by the definition of $X$, we have $\alpha \in f(\alpha)$.

Since $f(\alpha) = X$, this implies $\alpha \in X$, which is a contradiction.

In both cases, we arrive at a contradiction.

Therefore, our initial assumption that $f: A \rightarrow P(A)$ is onto must be false. Hence, $f: A \rightarrow P(A)$ is not onto.

Application of Cantor's theorem

For any set $A$, by Cantor's Theorem $|P(A)| > |A|$. In particular  $|P(\mathbb{N})| > |\mathbb{N}|$, hence $P(\mathbb{N})$ is uncountable set.