"Cantor's proof is one of the wonders of the world, like the hanging gardens of Babylon or the pyramids of Egypt."
Georg Cantor, German (1845-1918), was interested in Mathematics from a young age. Cantor was also of a philosophical bent so he was drawn to mathematical inquiry that might lead to discoveries about a concept or a notion that had long intrigued yet troubled serious thinkers: infinity.
Is the notion of infinity simply an intuitive idea we humans feel but which lies beyond our capacity to inquire into its nature? That is: is infinity just infinity and that's all we can really say about it? Or, is it something we can delve into systematically in order to discover truths about its characteristics just as we have about molecules and atoms? Georg Cantor was compelled to look into all this.
At some point Cantor began thinking about what he termed "sets." In fact, Cantor is credited with inventing "set theory," which is now thought of as one of the most fundamental branches of mathematics. A set is a group of things that share a common quality or share common qualities. Some examples: the set of all circles. The set of all counting numbers. The set of all humans. The set of all female humans.
Cantor soon noticed, of course, that some sets consist of infinite members (the counting numbers) while others consist of finite members (the humans). So in order to compare the size of sets Cantor began using what he dubbed one-to-one correspondence. What he would do is have the members of one set "stand" in one long line while having the members of the other set line up its members in a parallel line with the first. Like this:
Set of Counting Numbers: 1 2 3 4 5 6...
Set of all even Counting Numbers: 2 4 6 8 10 12...
As you can see there is a perfect one-to-one correspondence between the counting numbers and the even counting numbers. So it is the case that both sets contain the exact same number of members (an equivalent infinity). This jives with humanity's strange notions about infinity because the conclusion it draws seems to make perfect sense yet be nonsensical all at the same time. This is because our intuitions tell us that, yes, both sets should be infinite. But at the same time our intuitions are telling us that the two sets should not be equivalent because one of them (the evens) should be half the size of the other (the evens and odds). But the fact is simply this: both sets contain exactly the same number of members and both sets contain an infinite number of members. We proved what was just stated above in a cursory fashion though I assure you that the technicians of mathematics (Cantor etc.) have proved it systematically and formally. That is to say: it is for all intents and purposes the truth.
Now, quickly, let's compare two different kinds of sets, two finite sets:
Set of all female humans: (F F F F F F F...)
Set of all humans: ((F F F F F F F...)M M M...)
We have F standing for female, of course, and M standing for male. The parentheses are there to alert us to the fact that these two sets are closed or finite (not infinite). This, obviously, is because we know that there are neither an infinite number of female humans nor an infinite number of all humans. Now, what the above line-up shows us (which is consistent with our intuitions) is that there is NOT a one-to-one correspondence between these two sets. One set (all humans) consists of more members than the other set (the female humans). We have proved this, again, in a cursory fashion, by lining up all of the females from one set with the females in the other set. And because the females in each set can be matched off perfectly with each other, the set of all humans is left with a bunch of males that cannot be matched off with anything in the set of all female humans.
So, Cantor has now determined that sets can have either infinite members or finite members. And he has also determined that two finite sets can be of equal or different sizes (like the above humans) while two infinite sets can at least be shown to be equal (like the above numbers).
Now, Cantor's true tour de force came when he next asked himself if he could find two sets that both contained infinite members that were at the same time unequal. That is, quite simply, could Cantor prove that some infinities are larger than other infinities?
It turns out, amazingly, that Cantor had to go no further than comparing the set of all real numbers to the set of all counting numbers to indeed prove that some infinities are in fact larger than others! That is, Cantor proved (by showing there is NOT a one-to-one correspondence between the two) that the real numbers are a larger infinity than the counting numbers! In fact, the real numbers are infinitely more numerous than the counting numbers even though the counting numbers are themselves infinite! Now, for how Cantor went about this proof:
Wait! It is first important for us to define the real numbers: the real numbers are the set of all rational and irrational numbers. A rational number is a number that can be expressed with a terminating decimal (like 1.175 or 2.0). On the other hand, an irrational number is a number that can be expressed with only an infinite decimal representation (like p or 2.3785120936593).
Understanding this we can now truly move on to the magnificent proof: Cantor invented and then employed what is now known as a "diagonal argument." This technique can basically be said to be an algorithm/scheme that can be used to demonstrate the existence of a real number that CANNOT find a partner in any given attempt to pair off the counting numbers with the real numbers on a one-to-one corresponding basis. Consider the following attempt, for example:
Now, notice the darkened and enlarged numerals and then have a look at the number I create below, which I will name "Miss-Won't-Line-Up," or "MWLU" for short.
You will notice that Miss-Won't-Line-Up has been created by simply changing each numeral in the diagonal to ONE numeral higher than itself. So the three has become a four, the two has become a three, the three has, again, become a four, the one has become a two, etcetera, etcetera.
Now, for the shocking ramification of what we have laid out visually above (and do not be concerned if coming to terms with this takes a period of timehopefully a finite period of time J): the diagonal discovery of MWLU proves to us that MWLU can never show up on ANY attempted scheme to pair off the counting numbers with the real numbersthat is, MWLU is a real number that will forever be left out of ANY infinitely long pairing off scheme between the counting numbers and the real numbers!
And this is all because any MWLU is itself a real number (as it is an irrational number) but one that cannot be the first real number in ANY pairing off sequence because the first numeral of MWLU has been distinguished from the first sequenced real number by +1. And, likewise, MWLU cannot be the second real number in any pairing off scheme because its second numeral has been distinguished from the second sequenced real number by +1. And, likewise, MWLU cannot be the third real number in any pairing off scheme because its third numeral has been distinguished from the third sequenced real number by +1
And on and on forevermeaning the entirety of the counting numbers (an infinite set) can be paired off with a unique real number but our friend, Miss-Won't-Line-Up, will never appear on that or any infinitely long line of paired off real numbers! What logically follows from this, of course, is that there are strictly more real numbers than counting numbers even though the set of counting numbers and the set of real numbers are both infinite!
After the truth of this argument sinks in you may find yourself making the following objection: but why not after establishing the MWLU for any pairing off scheme just slide all of the pairs down one spot and place MWLU at the beginning of the sequence, paired with zero? This seems to be a fine objection until we soon realize that as soon as the new order has been placed a new MWLU can just as simply be created!
And, in fact, we could do this sliding down technique indefinitely and create new MWLUs forever. Which brings us to the final strange implication of Cantor's proof: not only are there more real numbers than counting numbers but there are, actually, infinitely more!
Understanding an intellectual achievement like Cantor's for the first time is a unique, even transcendental experience. And it is your birth right as a human being to experience this. This is all to say: refuse to give in easily if it all does not immediately hit you.