2 ms·
In a similar vein, Cantor's original diagonalization proof of uncountability is one of the most satisfying results in real analysis. From https://www.cs.virgin
by avani 6y ago
In a similar vein, Cantor's original diagonalization proof of uncountability is one of the most satisfying results in real analysis. From https://www.cs.virginia.edu/luther/blog/posts/124.html https://www.cs.virginia.edu/luther/blog/posts/124.html:
"Any real number can be represented as an integer followed by a decimal point and an infinite sequence of digits. Let’s ignore the integer part for now and only consider real numbers between 0 and 1. Now we need to show that all pairings of infinite sequences of digits to integers of necessity leaves out some infinite sequences of digits.
Let’s say our candidate pairing maps positive integer i to real number r_i. Let’s also denote the digit in position i of a real number x as x_i. Thus, if one of our pairings was (17, 0.651249324…) then r_17^4 would be 2. Now, consider the special number z, where z_i is the bottom digit of r_i^i + 1.
The number z above is a real number between 0 and 1 and is not paired with any positive integer. Since we can construct such a z for any pairing, we know that every pairing has at least one number not in it. Thus, the lists aren’t the same size, meaning that the list of real numbers must be bigger than the list of integers."
- kmill 6y agoBefore the diagonalization argument, Cantor had another proof of the uncountability of the reals. Looking it up again, it's actually pretty much the Alice-Bob game! See theorem 2: https://www.maa.org/sites/default/files/pdf/upload_library/22/Ford/Gray819-832.pdf https://www.maa.org/sites/default/files/pdf/upload_library/2... (To see the correspondence, it's helpful to think of limits as being a kind of game. You claim the limit is a particular value, another party challenges you with an epsilon, and then you respond to the challenge by saying an index in the sequence after which all the entries are within epsilon of the claimed limit.)
- jwilk 6y agoThe proof on this page has a small gap: it fails to take into account that some numbers don't have unique decimal expansion. For example, if all digits on the diagonal were 8, then z = 0.(9) = 1, which is not between 0 and 1.
- eru 6y agoYes. Though that problem is repairable.
- eru 6y agoCantor's diagonal argument is interesting, because it's not just a nifty proof, but seen as an entirely new proof strategy. Those don't get invented often.