A Proof that the power set of the natural numbers is bigger than the natural numbers themselves

Objective

To show that some infinities are larger than others!

Method

We use a technique sometimes called "diagonalization", and the notion of a one-to-one correspondence.

Equally Big Infinite Sets

Because we cannot "count" two infinite sets to see which is bigger, we need another method. The method we use it so show that two sets are the same size is to find a bijection (one-to-one and onto) mapping between the two sets (which sets up unique partners, essentially).

For simplicity, we'll focus on the natural number $\mathbb {N} =\{1,2,3,4,\ldots \}$. For example, to show that the even natural numbers are equally numerous as the natural numbers themselves, we can set up the one-to-one correspondence given by

Natural Numbers ($\mathbb {N}$)	Evens
1	2
2	4
3	6
4	8
5	10
$\vdots$	$\vdots$
n	2n
$\vdots$	$\vdots$

Our conclusion: the even naturals are as numerous as the naturals themselves. Certainly this counts as a non-intuitive idea, because we're used to proper subsets being smaller than the sets from which they derive.

Bigger Infinite Sets

So, in order to show that there is a bigger infinite set, we need to show that there is no one-to-one mapping from one set to the other. In particular, we're going to show that the power set of the naturals, denoted $\wp (\mathbb {N} )$, is larger than the naturals themselves.

The proof is by contradiction: suppose that there exists a one-to-one correspondence between the two sets. It might begin like this:

To show that the even natural numbers are equally numerous as the natural numbers themselves, we can set up the one-to-one correspondence given (for example) by the following:

$\mathbb {N}$	$\wp (\mathbb {N} )$
1	$\emptyset$
2	$\mathbb {N}$
3	{1,2,6}
4	Evens
5	Primes
$\vdots$	$\vdots$
$\left.n\right.$	$\left.S(n)\right.$
$\vdots$	$\vdots$

That is, for each natural number on the left there corresponds a unique partner subset of the natural numbers. Clearly there are infinitely many subsets, because, for example $(\forall i\in \mathbb {N} )(\{i\}\in \wp (\mathbb {N} ))$. $\emptyset$ is the empty set, which is a subset of every set.

We will now demonstrate that there is a subset $M\in \wp (\mathbb {N} )$ which is not found on the right hand side, contradicting the claim that the mapping is one-to-one.

We do it by construction, through a process called diagonalization: we are going to go down the (infinite) list, and decide whether each natural number $\left.n\right.$ on the left is in $\left.M\right.$ based on the set it's partnered with, $\left.S(n)\right.$.

Here's the rule:

1. Consider the $\left.n^{th}\right.$ row.
2. If $\left.n\right.$ is in the partner set $\left.S(n)\right.$, then $\left.n\right.$ is not in $\left.M\right.$.
3. If $\left.n\right.$ is not in the partner set $\left.S(n)\right.$, then $\left.n\right.$ is in $\left.M\right.$.

Then we know that $\left.S(n)\right.$ and $\left.M\right.$ differ in at least one element (one and only one of the two sets has $\left.n\right.$ as a member), for every $\left.n\right.$. Therefore, $\left.M\right.$ is not found on the right hand side, and the mapping was not a one-to-one correspondence.

This is a contradiction, and we conclude that there is no one-to-one correspondence between the two sets. Hence one is larger than the other (and the larger set is the power set).

Even Bigger Infinite Sets

We now know that there are at least two sizes of infinity: big and bigger. We want to now show that there are infinitely many sizes of infinity! That's rich....

Theorem: the power set of a set $\left.S\right.$ is always larger than $\left.S\right.$ (punch line: there is always a bigger infinity than the one you already have).

Proof: By contradiction. Consider $\left.f:S\longrightarrow \wp (S)\right.$ a one-to-one correspondence between $\left.S\right.$ and $\left.\wp (S)\right.$). That is, every set of $\left.\wp (S)\right.$ is represented by an element of $\left.S\right.$. (We will show that this is impossible.)

Denote by $\left.f(S)\right.$ the set of subsets that are the images of all the elements of $\left.S\right.$): $\left.f(S)\equiv \{f(x)|x\in S\}\right.$). Then we have asserted that $\left.f(S)=\wp (S)\right.$ -- that is, that every subset of $\left.S\right.$ is the image of some element of $\left.S\right.$).

However, consider the subset of $\left.S\right.$ given by

$\left.A=\{x\in S|x\notin f(x)\}\right.$

But $\left.A\notin f(S)\right.$ (because it's different from every element $\left.f(x)\right.$ of $\left.f(S)\right.$)), by design; and yet $\left.A\in \wp (S)\right.$). This is a contradiction: we asserted that the mapping was one-to-one -- i.e., that $\left.f(S)=\wp (S)\right.$.

Just to try to make the nature of the set $\left.A\right.$ a little clearer, assume that we're talking about $\left.S=\Re \right.$, the real numbers; and suppose that we map $\left.\pi \right.$ to the interval $\left.(0,1)\right.$. Then $\left.f(\pi )=(0,1)\right.$. Now, since $\left.\pi \notin f(\pi )\right.$, we have that $\left.\pi \in A\right.$. On the other hand, suppose that we map $\left.{\sqrt {2}}\right.$ to the interval $\left.(0,4)\right.$. Then $\left.f({\sqrt {2}})=(0,4)\right.$. Now, since $\left.{\sqrt {2}}\in f({\sqrt {2}})\right.$, we have that $\left.{\sqrt {2}}\notin A\right.$. In either case, we note that $\left.A\neq f(x)\right.$.

But $\left.A=\{x\in S|x\notin f(x)\}\right.$ is different from each of the sets "on the right-hand side", by construction, and hence $\left.A\notin f(S)\right.$; the purported bijection between $\left.S\right.$ and $\left.\wp (S)\right.$ does not exist, contradicting the equivalence of the cardinalities of the two sets.

Therefore, since the power set of a set is always bigger than the set itself, even for infinite sets, there is a countable infinity of larger and larger infinities. Amazing!

Conclusion

So, some infinite sets are larger than others. How many sizes of infinite sets are there?

Turns out that there is an infinite chain of infinitely larger sets. The proof can be extended to show that the power set of S is always larger than the set S itself (whether S is finite or infinite); hence, if we start with an infinite set S, the chain

$\left.S,\wp (S),\wp (\wp (S)),\wp (\wp (\wp (S))),\ldots \right.$

is an infinite string of infinitely larger infinities! Curiouser and curiouser....