Cantor's proof of the uncountability of the reals goes like this. Every real number in (0,1) has a unique nonterminating binary expansion [every word there is important; nonterminating means not ending in all zeros]. You show that the members if (0,1) are not countable by contradiction. If there were an exhaustive enumeration (i.e., 1-to-1 mapping between (0,1) and the naturals), we could always construct a new number by flipping the first bit of the first one, 2nd bit of the 2nd, one, and so on. Anyone seeing this for the first time should go look it up.
I have a student who insists he's broken Cantor's argument. Take the following list, he says:
.01111111....
.01011111....
.00111111....
.00011111....
.00001111....
.00000111...
and so on. If you construct a number by flipping the bits on the diagonal, you get
.1000000... = .0111111...
which is the first number on the list. Can someone explain why Cantor's theorem still holds? Ideally, the explanation would be provided by the student himself. What do you say, "D"? I gave you a hint after class...
Subscribe to:
Post Comments (Atom)
5 comments:
In my own defense, I don't claim that Cantor's argument is broken. I just claim that the argument is often presented incompletely, as it was in class (the same problem seems to show up in old 251 slides, but it looks like they've fixed it). Actually I'm curious now where I can find Cantor's own writings on the subject.
My claim is simply that if you diagonalize only over single digits in binary, the "counter-example" isn't a legitimate counter-example.
Any real number in base B with two representations must end with an infinite run of 0's or (B-1)'s. Thus base 4 or higher it's easy to see that only returning digits in {1,2} will construct a legitimate counter-example.
However it should be possible to fix things so that we can still diagonalize single digits in binary. Here's one idea:
Given an arbitrary input list L, construct a new list L' by sticking a 0 after every even-numbered element of L and a 0.11111111 after every odd-numbered element of L. Any number in L will also be in L'. A counter-example generated from L' cannot end with an infinite sequence of 0s or 1s, so the counter-example has a *unique* decimal expansion not equal to any other decimal expansion in L'. Thus the counter-example is not in the list L' and consequently not in L.
For Cantor's own writings, try here:
http://en.wikipedia.org/wiki/Georg_Cantor#Work
and go to the Bibliography section.
And yes, you're absolutely right that one must be careful with these constructions; I agree that the proof given in class glossed over these subtleties and I commend you for keeping us honest.
Hey Leo,
Here's how you can avoid any silly technicalities. I never liked the proofs where you have to talk your way out of 1=.9999... A better way to do it is show that a subset of the reals in [0,1] is uncountable. Take for your subset the set of r which has a decimal expansion containing only 0's and 1's. So sure, .099999... will be in there as .1000... but only appears once. Then carry out the usual argument without this pathological (though clever!) counterexample.
-Alex (just running a long computation so I finally have a chance to look over your blog)
http://kvant.mccme.ru/1990/10/chego_bolshe.htm (in Russain)
Yes, my mother explained this to me when I wasn't much older than 10. I was able to explain this to 12-year-olds with much success. There is absolutely no reason to dumb down our education system the way we do.
Post a Comment