A beautiful proof

There are some proofs, for which the very fact of being acquainted with the working of the mind which came up with such beautiful ideas can transport you to a state of ecstasy.

Georg Cantor (1845-1918) gave a beautifully simple proof for proving that the power set of the set of natural numbers (N) has “more” elements than the set N itself, i.e. 2^N is uncountably infinite.

Assume to the contrary that 2^N is countably infinite. In other words, there exists a bijection between the set N and the set 2^N. (This is what is meant by a set S being countably infinite, i.e. if a set S is countably infinite, then there exists a bijection between S and the set, N of natural numbers.)

2^N = {R_0, R_1, R_2, … }  [R_0, R_1 etc are elements of 2^N i.e. subsets of N.]

Assuming that 2^N is countably infinite implies that every element of 2^N is equal to R_i for some i \in N.

Now, consider this set. Call it D.

If  0 \in R_0, then 0 \notin D.
Else if, 0 \notin R_0, then 0 \in D.

Similarly, deciding whether or not each i \in N belongs to D, is done based on whether or not i belongs to R_i.

If R_i contains i, then we do not include i in D.

And if R_i does not contain i, then we include i in D.

What do we get now?

We get a set D that is different from each R_i. (It is different from R_5 in whether or not ‘5’ is contained in it; it is different from R_345 in whether or not ‘345’ is contained in it. Hence, D can not be equal to set R_5. And, D can not be equal to set R_345.)

So, we see that D can not be equal to any of the sets R_i.

But, D is also a subset of N.

Hence, D should ideally be an element of the power set of N. By assumption, 2^N = {R_i : i \in N}.

We just saw that D can not be equal to any R_i.

Hence D is NOT a part of 2^N.

This is a contradiction!

We are done. 2^N can not have a bijection with N. 2^N is uncountably infinite.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: