Definition
Let $E$ be a set, there does not exist a bijective function between $E$ and $2^E$.
This implies that no set is equipotent to its power set. But not only that. To learn more, the Wikipedia page on Cantor’s theorem is very comprehensive (section: “Consequences of the theorem”).
Proof
To demonstrate this theorem, let’s reason by contradiction:
Let $f : E \rightarrow 2^E$ be a bijective function.
Set $X := \{e \in E : e \notin f(e) \}$.
$X$ is a subset of $E$ (= element of $2^E$) defined as the set of elements of $E$ that do not belong to their image by $f$.
To understand why we take this $X$, let’s take an example: For $E = \{a,b,c\}$, and $f(a) = \{a,b\}$ and $f(b) = \{\}$, $f(c)=\{a\}, $ $X =\{b,c\}$, $X$ is indeed a subset of $E$, yet it has no antecedent by $f$. See Cantor’s diagonal argument
$\exists y \in E$ such that $f(y) = X$.
A function $f$ from $E$ to $2^E$ is said to be surjective if for every element $y$ of $2^E$, there is at least one element $e$ of $E$ such that $f(e) = y$. Formally, we have: $\forall y \in 2^E \ \exists e \in E ; f(e)=y$. As an element of $2^E$, $X$ must admit an antecedent $y$ by $f$ because $f$ is surjective.
We have 2 cases:
- If $y \in X$, then, by definition of $X$, $y \notin f(y)$. Thus $y \notin X$, which is contradictory.
- If $y \notin X$, then by definition of $X$, $y \in \bar{X}^E$. Therefore $y \in f(y)$, so $y \in X$, which is again contradictory.
$X$, although an element of $2^E$ does not have an antecedent by $f$. Therefore, $f$ is neither surjective nor bijective. Hence Cantor’s theorem.
Complement
Cantor’s theorem can also be formulated as follows: For any set $E$, $|E| < |2^E|$. This is naturally demonstrated by the non-existence of surjectivity (demonstrated above) and the existence of the injective function $f(x)=\{x\}$.
For example, for $E = \{a,b\}$, $2^E = \{\{\},\{a\},\{b\},\{a,b\}\}$, $a$ is associated with $\{a\}$ and $b$ with $\{b\}$.