Having seen that the rationals are *countably infinite* and the reels are *uncountably infinite*, the natural questions to ask is:

## How many types of infinities are there?

It turns out there are *infinitely many* types of infinity, and we can even give a way to construct them by looking at power sets.

The power set $P(A)$ of a set $A$ is the **set of all subsets** of $A$. For example, $P(\mathbb{1,2,3})=\{\emptyset, \{1\}, \{2\}, \{3\}, \{1,2\}, \{1,3\}, \{2,3\}, \{1,2,3\}\}$. For finite sets the size of the powerset of $A$ is $|P(A)|=2^{|A|}$ (proof by induction). The powerset of *non-finite* sets are defined the same way, as the set of all of its subsets. Cantor’s theorem then states:

*The size $|P(A)|$ is strictly greater than the size $|A|$*, i.e., there is no bijection (one-to-one) correspondence between $A$ and $P(A)$. This gives us our desired result, as we can start with an infinite set (say $\mathbb{N}$) and just repeatedly apply the power set construction $\mathbb{N}, P(\mathbb{N}), P(P(\mathbb{N})), P(P(P(\mathbb{N}))), \ldots$, and each set in this sequence is of a different type of infinity.

The proof of Cantor’s theorem again uses self-referentiality similar to the diagonal argument for the reels.

Assuming the statement was true, there would be a bijective $f:A \rightarrow P(A)$. The key argument is finding a subset of A (an element of the powerset) which leads to a contradiction. We choose $B = \{ x \in A \mid x \notin f(x) \}$ as the set of all elements $x$ of $A$, such that **$x$ itself is not in the set $f(x)$**, the subset of $A$ that $x$ maps to using the power set mapping $f$. As $f$ is surjective, there is an $x$ mapping to $B$, i.e., $f(x)=B$. For this $x$, we have two possibilities, either $x$ is in $B$, or $x$ is *not* in $B$, however both cases lead to a contradiction:

- $x \in B \stackrel{f(x)=B}{\leftrightarrow} x \in f(x)$. In $B$ are only the $y$ s.t. $y \notin f(y)$, but $x \in f(x)$, so $x \notin B$
- $x \notin B \stackrel{f(x)=B}{\leftrightarrow} x \notin f(x)$. But that’s exactly the membership definition of $B$, so this is equivalent to $x \in B$

We then arrive at the contradiction $x \in B \leftrightarrow x \notin B$.

### Previous ProjectNext Project

**Categories:****Share:**