Georg Cantor was one of the great mathematicians. He invented set theory (which all modern math is based on), showed the world an infinity of infinities, and became increasingly insane.
Now, on to the theorem. I didn't get this theorem the first time I heard it. Or the second. Or for a few years of hearing it. I had to really think about it before I understood what was going on. I'll try to include all of those little intuitive leaps that no one tells you about, but that you need to make in order to really understand why it works. The theorem states that the Real numbers are "more numerous" than the counting numbers. Clearly both are infinite, but the Real infinity is larger than the countable infinity. I will prove that the Real numbers between 0 and 1 are "more numerous" than the counting numbers. If that set is uncountable, then the entire set of the Real numbers must be at least that big and thus uncountable as well. It is more difficult to prove that the Real numbers and the Real numbers between 0 and 1 are the same infinite size. It is also more difficult to prove that the Real plane is yet a bigger infinity than the Real number line, but that is a post for another time (although probably not, because this post is the most interesting part).
Outline:
- Come up with an arbitrary way of counting the Real numbers between 0 and 1. By arbitrary, I don't mean a particular way chosen at random. Instead, arbitrary means a way that encompasses all possible ways. There isn't a way to count them that isn't covered by this arbitrary method.
- Show that the arbitrary method misses a Real number. This missed number is constructed out of the arbitrary counting method, so you can't just add it to the counting method and try again.
- Following the unique pairing idea in Infinities part 1, show that there is no counting number pair for the missed Real number.
The biggest problem that I had with this was the arbitrary counting method. I didn't believe that it really took care of all of the possible ways that you could order and count the Real numbers. Heck, the proof that the rational numbers are countable requires a pretty clever ordering and counting method, so why couldn't that exist here?! Let's look at the arbitrary counting method.
Every Real number between 0 and 1 can be written as an infinite decimal number: 0.1232454729063373.... In some cases, like with 1/2 or .5, we can write it as 0.5000000.... I will introduce a little notation in order to describe the counting method. Consider one of these infinite decimals which we'll refer to as d1 (read dee one). We're going to want to refer to specific digits of each number that we count, so we'll say that d1 = d11d12d13d14d15.... Suppose d1 is pi/10 (0.31415926....) Then d11 is 3, d12 is 1, d13 is 4, d14 is 1, and so on. Our next number would be d2 = d21d22d23d24d25.... We end up with a matrix:
d1 = 0.d11d12d13d14....
d2 = 0.d21d22d23d24....
d3 = 0.d31d32d33d34....
...
dn = 0.dn1dn2dn3...dnn....
This counting method is arbitrary. Whatever counting method is chosen, there will be a d1, a d2, and so on. This matrix represents any possible counting method since it doesn't state what the ordered numbers are. It allows you to fill in the d's with whatever counting system you want to try. This is the tricky part. If you don't believe that this represents any possible counting of the Real numbers from 0 to 1, then you won't believe the rest of the proof, so I'll rephrase the point. The way that you show that an infinite set is countable (like with the integers or the rationals) is to create a unique pair for every element of the two sets. Thus, you have to pair 1 with something, 2 with something else, 3 with something else, and so on. Moreover, you can't miss any elements of the set you are trying to count. When pairing the counting numbers to the integers, you could choose a way that works, but you could also choose a way that doesn't. The way that works is to oscillate between positive and negative numbers in order to cover the entire set of integers with the counting numbers. A counting method that wouldn't work is if you just matched 1:1, 2:2, 3:3, and so on. You would miss all of the negative numbers! What we are proving with this matrix is not just why a particular counting method doesn't work, like matching 1:1, 2:2, and so on, but why ANY counting method doesn't work. By not putting actual numbers in for d1, d2, etc., we have allowed any pairing of 1:d1, 2:d2, 3:d3, .... No matter how clever you can get, you will still have to match 1 with something. d1 is a placeholder for that something. d2 is the placeholder for what you match 2 with, and so on. If you don't get this yet, don't feel bad. This is the hard part of the proof.
Whatever numbers you would choose for each d of this counting method, you would always miss at least one Real number between 0 and 1. Let's construct this number; we'll call it c. The digits of c are chosen based on the digits of the d's. c is going to be an infinitely long decimal, and we'll denote it as c = c1c2c3c4.... Here's where the diagonalization comes in to play: choose c1 to be any number between 0 and 9 except whatever d11 is. c2 will be between 0 and 9, but different from d22. c3 is between 0 and 9, but different from d33. In other words, if you take that matrix of d's above and create a number, call it b, by drawing a diagonal line from the top left to the bottom right, each digit you hit in the matrix becomes the next digit of b; b = d11d22d33d44d55.... The c number is different from the b number at every digit. We have created this c number very specifically so that it doesn't exist as any d. By being different from the diagonal AT EVERY DIGIT, the c number can't be one of the d numbers. Consider d7. c is not d7, since d7 = 0.d71d72d73d74d75d76d77.... but c = c1c2c3c4c5c6c7.... where c7 is different from d77. Consider d2. d2 = 0.d21d22d23.... but c = c1c2c3.... where c2 is different from d22. You can see that for any d, there will be a digit of the c number that will be in the same location but different in value from the d number. Thus the c number isn't any of the d numbers!
c is a real number between 0 and 1 that falls outside of any given counting method. Notice the word given. I'm saying that once a counting method is chosen, whichever one it is, it will miss at least one number. Adding that one number to the counting method doesn't fix this, because by modifying the d's with the new number, you modify the diagonal and thus the missed number. The number c that is left out depends on the counting method. Whatever counting method is chosen, this c number will exist and it won't be counted. You can't come up with some super-clever counting method that beats this, because whatever that counting method is, there will be a c number that crops up which isn't covered.
I will finish with some intuition. The Real numbers consist only of rational and irrational numbers. We know that the rational numbers are countable, so it is the irrational numbers that are uncountably infinite. Somehow, the irrational numbers are "more numerous" than the rationals. The intuition that helps here is that irrational numbers all end in non-repeating infinite decimals. Rational numbers either end, or end in repeating infinite decimals. The amount of "information" in an irrational number is infinite, while in a rational number it is finite. The rationals are an infinite set of finites, while the irrationals are an infinite set of infinites.
No comments:
Post a Comment