Cantor's theorem is better stated as "Let X be infinite. If f: powerset(X) to X, then f is not injective.". This is completely uncontroversial, and its proof is by diagonalisation in a context where it really does intuitively "just work". Set X to the naturals, and prove that the reals are equipotent with the powerset of N, to obtain "the reals are uncountable".
A most merry and illustrated explanation of the diagonal argument: <a href="http://www.coopertoons.com/education/diagonal/diagonalargument.html" rel="nofollow">http://www.coopertoons.com/education/diagonal/diagonalargume...</a>
I've long had a question that might be a variation of the third concern listed: couldn't diagonalisation just show that considering all real numbers to be an infinite sequence of digits is a flawed representation? Not necessarily that they don't exist somehow or that they are necessarily countable, just the diagonalization argument seems flawed to me.<p>Edit: Actually maybe this is just the first concern mentioned :/.<p>Edit2: Maybe clearer explanation: you can produce an infinite sequence of digits from many real numbers, but it doesn't seem to me to be valid to consider that infinite sequence to actually be the real number.
Here's an argument I've found sometimes works better for people who can't see what the diagonal from the list is supposed to do, or if they think it's rather arbitrary. It's essentially the same argument, just written differently.<p>Definitions: 2 is the set {0,1}. N is the set of natural numbers {0,1,2,...}. An infinite sequence of 0's and 1's c_0,c_1,c_2,... can be thought of as a function c : N -> 2 (that is, the values in a sequence are a function of their position: c_i = c(i)). A set X is countably infinite if there is an invertible function f : N -> X (which, in other words, is a sequence f_0,f_1,f_2,... where each element of X appears exactly once). Let's write A -> B for the set of functions from A to B, rather than the usual B^A.<p>Suppose for sake of contradiction (N -> 2) is countably infinite, so there is an invertible function f : N -> (N -> 2). Let F : (N -> 2) -> N be the inverse, so I can save having to type f^-1. Let g : N -> 2 be defined by g(n) = 1 - f(n)(n). Then, g(F(g)) = 1 - f(F(g))(F(g)) = 1 - g(F(g)), so g(F(g)) must be 1/2, contradicting the fact that it ought to be 0 or 1 instead.
Sure, that's the story the government tells everyone. It sounds plausible enough, but is it the whole story?<p>* Apply Downward Lowenheim-Skolem to get a countable model of set theory<p>* Construct the reals using whichever technique you want.<p>* Since the base set theory is countable, so is the set of constructed reals.<p>The same technique can give you countably many groups, countably many rings, countably many points in the plane, etc. Everything is countable.
I think this blog post will delight anyone who liked this submission: <a href="http://math.andrej.com/2007/04/08/on-a-proof-of-cantors-theorem/" rel="nofollow">http://math.andrej.com/2007/04/08/on-a-proof-of-cantors-theo...</a>
Genuinely asking:<p>Consider decimal numbers between 0 and 1 in binary.<p>Here's how I am going to synthesize this set.<p>Step 1: Take non-decimal binary numbers and consider them to be padded with an infinite of zeros at the left.<p>...0000000<p>...0000001<p>...0000010<p>...0000011<p>...0000100<p>...0000101<p>...0000110<p>..........<p>Do we agree that this will contain <i>all</i> the non-decimal non-negative binary numbers?<p>In particular, is the following number in the above set? ...111111 (all ones, not zero-padding on the left). If not, why not. And if not, this seems to be a matter of definition to me. If yes, move on.<p>Step 2: Place a decimal at the end of each line above and flip left and right.<p>0.0000000...<p>0.1000000...<p>0.0100000...<p>0.1100000...<p>0.0010000...<p>............<p>Do we agree that this contains <i>all</i> the decimal positive binary numbers between zero and one: [0, 1).<p>Let's now apply diagonalisation on this.<p>It says that the number 0.11111111... will not be present in the above set.<p>Perhaps someone can see my confusion and enlighten me. :-) Thanks!
This seems to come up over and over again, and it always comes down to what assumptions you start with. If you accept all of the axioms and methods, the proof holds. If you don't, it doesn't. Articles like this one, aimed at an audience that already assumes that its techniques are valid, are never going to convince a non-mathematical audience that doesn't know what the basic assumptions are, because that's not their goal.
This theorem blew my mind on the Set Theory 101. A particularly interesting implication is that we can't say anything about the vast majority of the real numbers. Anything we say or write, all texts created by the humanity now and in the future creates a countable set. Since the real numbers are not countable, we can't assign them with the definitions.