Cantor’s diagonal argument (please!)
In: 0
[removed]
Imagine a long list of numbers that are between 0 and 1. The list is so long that it goes on forever! But we can still number those numbers; the first is #1. The second is #2. The third is #3. And so on.
We won’t run out of whole numbers for numbering our list, because whole numbers go on forever.
But does this list have all the numbers between 0 and 1 on it? NO! It CAN’T! And I can prove it. All I have to do is find a magic number that’s not on the list.
The magic number has a different digit 1 place after the decimal than the #1 number. So, for example, if #1 was 0.673903240, the magic number starts with 0.3 (because 3 is not 6, so this magic number I am making is not the same as #1 on the list).
The magic number has a different digit 2 places after the decimal than the #2 number. So, for example, if #2 was 0.743603557, the magic number now starts with 0.38 (because 8 is not 4).
The magic number has a different digit 3 places after the decimal than the #3 number. So, for example, if #3 was 0.9745378, the magic number now starts with 0.381 (because 1 is not 4).
And so on, forever… I always pick a digit that is different from the Nth digit than the Nth digit of #N on the list.
The list of numbers goes on forever, but I can still find a magic number that is not on the list. (Actually, I can make as many magic numbers as I like, and none of them will be on the list! Can you see how?)
The numbered list may go on forever, and there may be an endless number of numbers between 0 and 1, but there are more numbers between 0 and 1 than there are on the list! SOME INFINITIES ARE BIGGER THAN OTHERS! ACK!
Its about showing how countable and uncountable infinites describe different amounts.
So you can count from one element to another with natural, whole and rational numbers. For rational numbers its not trivial but you can count them by arranging them in a table and labeling them going diagonally back and forth.
Uncountable infinites are larger, often referred to as a continuum. How many points there are in a line for example, analogous to how many real numbers there are. In analysis you basically introduce the continuum of the real numbers like this: for every upper bounded set of real numbers its supremum is exists and its also a real number. Sup is the smallest upper bound. And this states that real numbers must fill a continuum. Well if I have an interval [0,a) its sup is a but what if a is missing? Than we have a “hole” in the number line. So this requirement means tha a must be part of the line and a could be any number.
So question? Are there more real numbers than any other kind? Well yes but how you show that? Since the number of natural, whole and rational numbers are equal as they can be paird up one to one. (If the elements of two sets can be paid one to one they have the same number of elements, in fancy words samd cardinality.) So show that real numbers can’t be paired one to one with naturals for example!
Ok, Cantor said and came up with the diagonalization argument. Lets look at the interval (0,1) this interval has a continuum of real numbers, you cant start anywhere so lets just randomly pick real numbers. Pair them up with naturals (so count them) and lets say we paired up every natural with a real number. We have an infinity of both of them so lets just say we did that. Can I come up with a new real number one that I haven’t counted. If so the continuum has more things to it than a countable infinity.
So lets make a new real number and for that lets imagine we listed the ones we generated with the infinity long decimal representation. Lets grab the first decimal digit of the first and add one, then go diagonally down and grab the second decimal digit of the second and add one, then the third of the third and the forth of the forth. If we hit a nine we can subtract one. This way we are making a real number that is different from all the ones we listed in at least one digit. Put the new number at the bottom of the list and continue. You can go forever. So a continuum is kinda infinitely larger than a countable infinity.
Ok when is this whole thing useful? Lets look at an example. If I have a function f which has an integral for lets say 0 to 1 which is I. Than I select a similar function f’ which is different from f in a couple of points. As it turns one or two points of difference still makes the integral of f’ I. So f and f’ are in the same equivalence class. And one or two points, well if f and f’ are different in a set of points which set counting a countable infinity of points their integral is still the same. So from the perspective of an integral equivalence only matters in continous lines. This is important when you build functions with series expansions with other functions like a Fourier series. So when discussing equivalence classes of functions, a question like how do you define the sgn function at 0? The answer is: I couldn’t care less.
Latest Answers