View source for 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 <math>\mathbb{N}=\{1,2,3,4,\ldots\}</math>. 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
<center>
<table border=1 cellpadding=5>
<tr><td>Natural Numbers (<math>\mathbb{N}</math>)</td><td>Evens</td></tr>
<tr><td>1</td><td>2</td></tr>
<tr><td>2</td><td>4</td></tr>
<tr><td>3</td><td>6</td></tr>
<tr><td>4</td><td>8</td></tr>
<tr><td>5</td><td>10</td></tr>
<tr><td><math>\vdots</math></td><td><math>\vdots</math></td></tr>
<tr><td>n</td><td>2n</td></tr>
<tr><td><math>\vdots</math></td><td><math>\vdots</math></td></tr>
</table>
</center>

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 <math>P(\mathbb{N})</math>, 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:
<center>
<table border=1 cellpadding=5>
<tr><td><math>\mathbb{N}</math></td><td><math>P(\mathbb{N})</math></td></tr>
<tr><td>1</td><td><math>\emptyset</math></td></tr>
<tr><td>2</td><td><math>\mathbb{N}</math></td></tr>
<tr><td>3</td><td>{1,2,6}</td></tr>
<tr><td>4</td><td>Evens</td></tr>
<tr><td>5</td><td>Primes</td></tr>
<tr><td><math>\vdots</math></td><td><math>\vdots</math></td></tr>
<tr><td><math>\left.n\right.</math></td><td><math>\left.S(n)\right.</math></td></tr>
<tr><td><math>\vdots</math></td><td><math>\vdots</math></td></tr>
</table>
</center>
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 <math>(\forall i \in \mathbb{N})(\{i\}\in P(\mathbb{N}))</math>. <math>\emptyset</math> is the empty set, which is a subset of every set.

We will now demonstrate that there is a subset <math>M\in P(\mathbb{N})</math> 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 <math>\left.n\right.</math> on the left is in <math>\left.M\right.</math> based on the set it's partnered with, <math>\left.S(n)\right.</math>. 

Here's the rule: 
# Consider the <math>\left.n^{th}\right.</math> row.
# If <math>\left.n\right.</math> '''is in''' the partner set <math>\left.S(n)\right.</math>, then <math>\left.n\right.</math> '''is not in''' <math>\left.M\right.</math>.
# If <math>\left.n\right.</math> '''is not in''' the partner set <math>\left.S(n)\right.</math>, then <math>\left.n\right.</math> '''is in''' <math>\left.M\right.</math>.
Then we know that <math>\left.S(n)\right.</math> and <math>\left.M\right.</math> differ in at least one element (one and only one of the two sets has <math>\left.n\right.</math> as a member), for every <math>\left.n\right.</math>. Therefore, <math>\left.M\right.</math> 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).

== 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
<center>
<math>\left.S, P(S), P(P(S)), P(P(P(S))), \ldots\right.</math>
</center>
is an infinite string of infinitely larger infinities! Curiouser and curiouser....

<center>
[http://img27.photobucket.com/albums/v80/harnett65/sb2.jpg [[Image:Mirrors_infinity.jpg]]]
</center>