Infinitely many Infinities

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:

  1. $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$
  2. $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$.

Share:

Get updates on new content.

No spam, no sales pitch, I promise. I don't like these myself.

Leave a Reply