Proof

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”).

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\}$ .

Definition

Proof

Complement

Sources :