Talk:Cantor's first uncountability proof

From Wikipedia, the free encyclopedia

Is it really true that most mathematicians believe that the diagonal proof was Cantor's first proof of uncountability? I'm no mathematician, but even my topical interest in the matter turned up that fact long before this article was created. Is the misconception really that prevalent? -- Cyan 20:51, 3 Nov 2003 (UTC)

I haven't carefully polled mathematicians to ascertain this, but I keep finding it asserted in print, and I've spoken with a number of intelligent mathematicians who were under that impression. Michael Hardy 19:53, 4 Nov 2003 (UTC)

I would not have been certain if the diagonal proof was the first one, but my guess (if I would have to bet) would have been that it was, as this is the proof that is most known and famous, so in this sense, I think it's a misconception. Also, mathematicians are pretty sloppy historians (see Fermat number re: Gauss n-gon construction) so it's best to assume we don't know what we're doing, I think. Revolver

I've looked up Cantor's 1874 paper in Journal für die Reine und Angewandta Mathematik, and the argument given in that article is indeed the one given here. See also Joseph Dauben's book about Cantor. This was indeed his first proof of this result. Michael Hardy 22:17, 12 Jan 2004 (UTC)

Was it really in 1877 that Cantor discovered the diagonal method, or was it later? I cannot find any proof for this. -- Zwaardmeester 19:52, 15 Jan 2006 (GMT+1)

This "proof" is logically flawed

The constructivists' counterargument to the preceding "proof" of the "uncountability" of the set of all real numbers hinges on their firm belief that there is no greatest natural number --- hence, there is no last term in the sequence {Xn}. The completed constructibility of the monotone sequences {An} and {Bn} from {Xn} is also dubious for the same reason --- hence, the limit point C is "unreachable" (that is, it perpetually belongs to the elements of R denoted by the 3-dot ellipsis ". . ."). One could state in more familiar terminology that C is an irrational number which does not have a last, say, decimal expansion digit since there is no end in the progression of natural numbers.

For a simple counterargument, even granting arguendo Georg Cantor's own hierarchy of transfinite ordinal numbers, we merely note that the infinite set whose size is "measured" by the ordinal number, say, w+1 = {0,1,2,3,...,w} (here, w is omega)) is also countable. To elaborate, "ordinal numbers" are "order types of well-ordered sets". A well-ordering is an imposition of order on a non-empty set which specifies a first element, an immediate successor for every "non-last element", and an immediate successor for every non-empty subset that does not include the "last element" (if there is one). For examples: (1) The standard imposition of order on all the non-negative rational numbers: { 0, . . ., 1/4, . . ., 1/2, . . ., 3/4, . . ., 1, . . ., 5/4, . . ., 3/2, . . ., 7/4, . . ., 2, . . ., 9/4, . . . } is not a well-ordering — because, for example, there is no positive rational number immediately following 0. (2) The following imposition of order on all the non-negative rational numbers is a well-ordering but not a countable ordering or enumeration: { 0, 1, 2, 3, . . ., 1/2, 3/2, 5/2, . . ., 1/3, 2/3, 4/3, . . ., 1/4, 3/4, 5/4, . . ., 1/5, 2/5, 3/5, . . . } (3) The following imposition of order on all the non-negative rational numbers is a well-ordering that is also a countable ordering or enumeration: { 0, 1, 1/2, 2, 1/3, 3, 1/4, 2/3, 3/2, 4, 1/5, 5, 1/6, 2/5, 3/4, 4/3, 5/2, 6, 1/7, 3/5, 5/3, 7, . . . } It must be emphasized that, while the first two representations are not countable ordering or enumeration of the non-negative rational numbers, nevertheless, the set of non-negative rational numbers is countable as the third representation shows.

Rigorously, let us grant arguendo Georg Cantor's claim of completed totality of infinite sets. The sequences {An} and {Bn} were defined to form a sequence of nested closed intervals [An,Bn] that "microscopes" to the limit point C which must be a member of R. The assumption that all the elements of R can be enumerated in the sequence {Xn} carries with it the imposition of a countable ordering --- which deviates from the standard ordering based on the numerical values --- of the members of R. Given an arbitrary countably ordered sequence {Xn}, by the very definition of the construction of {An} and {Bn} stipulated by Georg Cantor, there is only one sequence of nested closed intervals [An,Bn] that can be so constructed --- hence, only one same limit point C for both {An} and {Bn}. In other words, the enumeration scheme of the sequence {Xn} determines exactly the sequences {An} and {Bn} as well as the limit point C. A rearrangement of a finite number of terms of {Xn} is still a countable ordering of the elements of R --- if a rearrangement results in different sequences {An} and {Bn}, then a different limit point C is obtained but, always, there is only one limit point C that is "excluded" in any specified sequence {Xn}. We emphasize that in Cantor's tenet of completed totality of an infinite set, the limit point C of both the sequences {An} and {Bn} is known "all at once" in advance.

Therefore, Georg Cantor could have just as well specified the also countable set {X1,X2,X3,...} U {C} = {X1,X2,X3,...,C} [note that there is no real number immediately preceding C] --- instead of the standard enumeration {X1,X2,X3,...} that he assumed in the first sentence of his "proof" as having all of R as its range so that C is clearly not in the sequence {X1,X2,X3,...} but C is in R = {X1,X2,X3,...,C} and no contradiction would be reached.

Furthermore, {Xn} = {Yn} U {An} U {Bn} U {C} [1] where the sequence {Yn} consists of all the terms Xi of the sequence {Xn} that were bypassed in the construction of the sequences {An} and {Bn}. If we accept Cantor's reductio ad absurdum argument above, then we deny equality [1] and the easily proved fact that the union set of a finite collection of countable sets is countable.

BenCawaling@Yahoo.com

After carefully reading the above post, I conclude that the author is making a mistake similar to those made by many people encountering diagonal-method proofs for the first time. The problem is that if the initial set chosen is {X1,X2,X3, ... C} (with C inserted between two Xi's -- this is not captured by the notation), then the limit value produced by Cantor's argument will not be C, but something else.

Even a good high school student would balk at the above objection --- are you saying that a monotone sequence could have a middle-term limit? [BenCawaling@Yahoo.com (27 Sep 2005)]

No. You're saying "For a given proposed enumeration (x_n) of the reals, Cantor presents a number c which is not captured. So let's just throw c in and we have enumerated the reals." The objection to your argument is: once you have thrown in c, Cantor will happily present a new number (different from c) that is still not covered by your new proposed enumeration. He will always catch you. AxelBoldt 18:17, 30 March 2006 (UTC)

This is the same commonest mistake in Cantor's diagonal argument --- once you have thrown in c and claim a complete list of the real numbers then you're done; a re-application of Cantor's diagonal argument does present a number (different from c) but that new anti-diagonal number was included in the list when c was the anti-diagonal number. You merely made a new enumeration or re-arranged the row-listed real numbers to get a different anti-diagonal number! → I hope you teach my counter-counterargument to your counterargument in your math classes ... Best regards ... [BenCawaling@Yahoo.com (16 Oct 2006)]

"Cantor's first proof" is new to me, and I have to say it's delightful. I agree that mathematicians generally believe the diagonal argument to be Cantor's first. However, I'm not completely convinced that this isn't really a diagonal argument in disguise. I need to think about this a bit. Dmharvey Talk 22:45, 6 Jun 2005 (UTC)

[edit] Simplifications

I'm hesitant to make changes to the statement of the theorem and its proof, since we may want to retain historical accuracy, and I don't have access to Cantor's formulation. There's five things I would change:

1. R needs to be non-empty which is currently not required. (but see 2 below)
2. if we require that R have at least two points, then we can get rid of the endpointlessness requirement. (The first step of the proof would then read "pick the first element of the sequence that's not the largest element of R"; everything else stays the same.)
3. The proof emphasizes "greater than the one considered in the previous step" twice, but that's not needed; just always pick the first member of the sequence that works.
4. The proof should make a bit more explicit how the existence of c follows from the given properties of R. I.e.: How the sets A and B are defined.
5. The proof should make explicit how the density property is used.

What do people think about these changes? AxelBoldt 17:49, 30 March 2006 (UTC)

[edit] "contrary to what most mathematicians believe"

Those six words add nothing to the article but an unverified claim based on the personal experience of wikipedia editors. They're unencyclopedic language and not really appropriate. Night Gyr 22:15, 29 April 2006 (UTC)

As mentioned above, it's true that the claim hasn't been formally verified, though anecdotal evidence is strong. I don't see what's wrong with the language. How does removing this statement help our readers? AxelBoldt 00:20, 30 April 2006 (UTC)

Because it makes us less reliable as an encyclopedia to include information that can't be relied upon to be anything but the anecdotal experiences of our editors. It's the whole reason behind WP:V. Night Gyr 01:13, 30 April 2006 (UTC)

So if I change "most" to "many" and find two sources where mathematicians make the false claim, would you be happy? AxelBoldt 14:17, 30 April 2006 (UTC)

I still don't understand why wikipedia needs to state that a misconception exists more prominently than the truth itself. We're here to provide facts, and the fact that a large number mathematicians of mathematicians have a fact incorrect seems less important to the first phrase of the entire article than the fact itself. Night Gyr 02:26, 1 May 2006 (UTC)

I agree, it doesn't need to be in the first sentence, or even the first paragraph. But it should be documented nevertheless. AxelBoldt 14:42, 3 May 2006 (UTC)

[edit] The rationals

Copied from the main article:

(Could someone who understands explain why the set of rational numbers does not have property 4?)

Property 4 says that if you partition the set into two halves, then there must be a boundary point in the set. This is not true for the rationals: take as A the set of all rationals smaller than √2 and as B the set of all rational above √2. Then all rationals are covered, since √2 is irrational, so this is a valid partition. There is no boundary point in the set of rational numbers that separates A from B however. AxelBoldt 02:09, 23 May 2006 (UTC)