A Proof that the power set of the natural numbers is bigger than the natural numbers themselves
To show that some infinities are larger than others!
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 . 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 ()||Evens|
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 , 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:
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 . is the empty set, which is a subset of every set.
We will now demonstrate that there is a subset 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 on the left is in based on the set it's partnered with, .
Here's the rule:
- Consider the row.
- If is in the partner set , then is not in .
- If is not in the partner set , then is in .
Then we know that and differ in at least one element (one and only one of the two sets has as a member), for every . Therefore, 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).
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
is an infinite string of infinitely larger infinities! Curiouser and curiouser....