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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \left.n\right.} is not in the partner set Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \left.S(n)\right.} , then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \left.n\right.} is in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \left.M\right.} .

Then we know that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \left.S(n)\right.} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \left.M\right.} differ in at least one element (one and only one of the two sets has Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \left.n\right.} as a member), for every Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \left.n\right.} . Therefore, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \left.S\right.} is always larger than Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \left.S\right.} (punch line: there is always a bigger infinity than the one you already have).

Proof: By contradiction. Consider Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \left.f:S \longrightarrow \wp(S)\right.} a one-to-one correspondence between Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \left.S\right.} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \left.\wp(S)\right.} ). That is, every set of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \left.\wp(S)\right.} is represented by an element of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \left.S\right.} . (We will show that this is impossible.)

Denote by Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \left. f(S)\right.} the set of subsets that are the images of all the elements of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \left.S\right.} ): Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \left. f(S) \equiv \{f(x) | x \in S\}\right.} ). Then we have asserted that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \left. f(S) = \wp(S)\right.} -- that is, that every subset of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \left.S\right.} is the image of some element of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \left.S\right.} ).

However, consider the subset of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \left. S\right.} given by

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \left. A = \{x \in S | x \notin f(x)\} \right.}

But Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \left. A \notin f(S)\right.} (because it's different from every element Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \left. f(x)\right.} of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \left. f(S)\right.} )), by design; and yet Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \left.A \in \wp(S)\right.} ). This is a contradiction: we asserted that the mapping was one-to-one -- i.e., that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \left. f(S)= \wp(S)\right.} .

Just to try to make the nature of the set Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \left.A\right.} a little clearer, assume that we're talking about Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \left. S = \Re \right.} , the real numbers; and suppose that we map Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \left. \pi \right.} to the interval Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \left. (0,1)\right.} . Then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \left. f(\pi)=(0,1)\right.} . Now, since Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \left. \pi \notin f(\pi)\right.} , we have that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \left. \pi \in A\right.} . On the other hand, suppose that we map Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \left. \sqrt{2} \right.} to the interval Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \left. (0,4)\right.} . Then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \left. f(\sqrt{2})=(0,4)\right.} . Now, since Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \left. \sqrt{2} \in f(\sqrt{2})\right.} , we have that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \left. \sqrt{2} \notin A\right.} . In either case, we note that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \left. A \neq f(x)\right.} .

But Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \left.A \notin f(S)\right.} ; the purported bijection between Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \left.S\right.} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \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

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \left.S, \wp(S), \wp(\wp(S)), \wp(\wp(\wp(S))), \ldots\right.}

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