Talk:Cantor's diagonal argument/Arguments

From Wikipedia, the free encyclopedia
Jump to: navigation, search
This page is for arguments over the validity of Cantor's diagonal argument. This is not an archive; you may feel free to edit this page. Please use this page for comments not directly relevant to improving the article Cantor's diagonal argument.

Argument not work[edit]

Trovatore deleted the following 1 minute after post:

The argument, as presented, (for reals, sets of bits, or sets of naturals) cannot work even if its conclusion is true because

For proof A to prove B to be FALSE it must allow B room to be true.

Consider someone asking you to count all 1000 three digit numbers, on 3 lines so only 3 numbers fit! Or they ask you to count all 1 digit numbers and after you count 1 number they say count all 2 digit numbers and after you count a second number they say count all 3 digit numbers …!

The height of the list HAS TO BE the exponential of the width to make room for all the sets to be counted per the statement of the proof 'count all the...' for it to be a PROOF. Saying that doesn't count with ∞ because with ∞ one can do magic has to be PROVEN for the rest to be a proof! Example of proper counting: In set theory Aleph infinity is infinite increase without end. Set the rate of increase of the height of the sets, the real numbers, to normal, have the digits of each real number produced by separate algorithms for each line, small to large algorithms, they can produce true random bits. Force the first digits to be a count sequence so each line is different. Set rate of increase of number of digets of nonrandom reals to normal, random reals to the (same base) logarithm of normal, this will force the diagonal to the same rate. The sort is by algorithm, like a program but programing language very complex so will always produce infinite list of digits, and in reasonable time as function of the number of digits yet produced by the algorithm. The width of the random numbers relative to the number of numbers counted is the same as natural numbers. The height keeps pace with the increase of possible numbers per the size of the algorithms and number of bits of randomness used to make any random real. Thus π is not ∞ly far thru the list. The height counts as Aleph0 not Aleph1 per analogy to the height : width relation of the set of natural numbers. π , for example, would be as precise in digits as the number of reals counted. Victor Kosko (talk)

How is it a proof of any kind?[edit]

So, I enumerate

S_0 = 0 0 1... S_1 = 1 0 1... S_2 = 1 1 1...

Then, S_n = 1 1 0...

And so, how does that prove anything at all? It's pretty obvious S_n will not be in my enumeration because I have not enumerated all the elements from the binary tree. Am I missing something? :-) (talk) 09:09, 20 February 2014 (UTC)

Well, that is kind of the point. You start off assuming that you can list all real numbers (in this case between 0 and 1) and then come up with a number that isn't on the list. That is a contradiction, so the assumption that you can list the real numbers must be wrong. (talk) 21:20, 21 February 2014 (UTC)

Simple disproof[edit]

Unfortunately Cantor only succeeds in proving that the list is infinite. Given that for any set of binary digits, 2^N integers can be defined, in order to define an infinite number of integers you must of course have an infinite number of digits, since 2^N only approaches infinity as N approaches infinity. Thus the set of integers with a finite number of digits is a finite set.

By ordering the integer representation of the reals from 0-1 as follows

...0000 - 0.0000...
...0001 - 0.1000...
...0010 - 0.0100...
...0010 - 0.0100...
...0011 - 0.1100...
...0100 - 0.0010...
...0101 - 0.1010...

it is readily apparent that any 0-1 real can have its corresponding integer form computed bijectively. The counted reals with a finite number of integer digits are of course sparse in relation to the counted reals with an integer representation with an infinite number of digits. But this should not be surprising, since there are only a finite number of integers with a finite number of digits.

Cantor's s0 argument is therefore reduced to being a disproof by contradiction as to the infinite nature of the list. Once the list is infinite, up to sn, for n at infinity, you can never add another real for s0, because as Cantor shows, that would cause a contradiction. Therefore the list already contains all integer elements in a one to one correspondence with 0-1 reals. --Frederick Bryan 01:13, 3 October 2007 (UTC)

  • Every single element in your list contains an infinite amount of trailing zeroes at the end. Surely that doesn't correspond well with all possible sequences of infinite length. (talk) 05:49, 11 March 2008 (UTC)
    • The above list of the 0-1 reals in binary format does not only contain elements for infinite trailing zeroes. For instance the element: ...1111 - 0.1111... contains all 1s. Note that the list contains 0-1, exclusive, ie .1111... is the highest represented value. This is of no concern to its validity as a disproof, however, since a disproof over an range is sufficient. --Frederick Bryan (talk) 00:04, 25 August 2008 (UTC)
  • Which integer does 0.01010101010101... correspond to? Your chart would say ...1010101010101 but this is not an integer! --Paul Laroque (talk) 20:37, 13 April 2009 (UTC)
    • It would correspond to ...10101010101010. You simply flip the digits over. It's unclear why you would say it's not an integer. Granted, it is a large integer with an infinite number of base-2-representation digits. Frederick Bryan (talk) 17:48, 24 September 2013 (UTC)
  • From the common sense, it doesn't seem to be true that in order to define an infinite number of integers one must have an infinite number of digits. 'Infinite' means 'endless': there's no end to enumeration. But every other (enumerated) number does have a finite number of digits just like its predecessor: from time to time, the number of digits n increases by one, but it still has a successor n+1 and is a valid number; the digits can be all enumerated, and the end to enumeration comes when n digits have been enumerated. So, no enumaration of natural numbers, no matter how long, would dig out a number that has infinitely many digits. In fact, such a natural number would be an absurd: called a number, but doesn't have a value. Besides, you couldn't do anything to such a 'number', because you'd have no tools (definition, addition, subtraction, …). The number of the natural numbers is infinite, but the numbers themselves are not (and the lengths of their digit strings are not either). ;) — (talk) 00:00, 20 January 2013 (UTC)
    • That's absurd. The largest integer you've counted to is also the number of integers you've counted. If the number of integers is infinite, then the number you've counted to, to get an infinite number of integers, is also infinite. Most integers therefore have an infinite number of digits. --Frederick Bryan (talk) 17:57, 24 September 2013 (UTC)
      • That doesn't follow. Every integer has a finite number of digits. Sure, you can find an integer with an arbitrarily high number of digits, but no integer has an infinite number of digits. In addition, you don't count to "somewhere" to get an infinite number of integers. There's no point on the number line where it switches from finite to infinite. — Preceding unsigned comment added by (talk) 02:32, 16 July 2014 (UTC)

Other, "Rational" Cantor diagonalizations[edit]

Since the title of this article is about Cantor diagonilization, there are other such diagonalization proofs, e.g. to prove that the rationals are countable. Could we include this, please?

Are you sure it was Cantor that came up with that one? -Dan 04:25, 19 December 2005 (UTC)
It isn't a diagonalization proof in the same sense (though a common diagram for it uses diagonals); it doesn't belong here. There are other diagonalization proofs which share essential properties with the Cantor diagonal proof: they include the halting problem argument, standard proofs for Godel's incompleteness theorem and Tarski's theorem on the undefinability of truth, Curry's paradox (and Russell's paradox for that matter). Randall Holmes 21:17, 19 December 2005 (UTC)

Would be Amusing[edit]

There is more controversy and personal accusation here on a mathematics page than on some political pages! This all would be amusing if it were not so absurd. We have taught students who could not even imagine the concept of an infinite set, of a limit, or even how to count, nor understand the difference between 2.5 and .25 in decimal arithmetic, no matter who tried to enlighten them. Let alone try to understand successors or mathematical induction. This "discussion" reminds me of those experiences, only the students were polite.

MathStatWoman 18:41, 16 December 2005 (UTC)

Please don't use very long preformatted strings, they force user to scroll horizontally, that's not nice.


1. If you have original research to present, please don't present it here. This is wikipedia policy. Wikipedia is not a place for presenting original research. That is what professional journals and publishers are for.

2. If you have mathematical or philosophical objections to Cantorian set theory, please address these in a brief descriptive section of the article itself. However, please do not turn this talk page into a debate hall. It is not our purpose here to endlessly argue over whether Cantorian set theory is "right" at all.

3. If you want to write an article on a more detailed critique, or presentation of previous critiques, or Cantorian set theory, then please create a new article for this purpose. Regardless of the bickering in here, it is an emperical fact that something on the order of 90% or so of working mathematicians accept Cantorian set theory both in theory and in practice, to some extent. (Source: The Mathematical Experience, Davis/Hersh) Thus, this should article should focus on the conventional viewpoint and mention contrary views, but a thorough hashing of intuitionism or constructivism on this topic requires a separate article.

Only 90% of working mathemeticians accept Cantorian set theory? That is not very encouraging! What if the Pythagorean theorem had this same level of support!! —Preceding unsigned comment added by (talk) 18:34, 25 May 2008 (UTC)

Yeah this just keeps going.[edit]

Sorry for being anonymous, just don't know how to get a user name here.

Nobody could argue with the proof itself.. it's just what it means.

I have two problems with the results cantor got.. one naive and one not so el.

1: as many times as you like means just that,yeah it's clear that in mathematics cantor's proofs are solid as a rock.. but still... you wonder if maths is proving a result like this then is it completely right?

2: a more technical point.. i've looked at a few of his original proofs and at some stage they all involve a function with an infinite amount of arguments, either directly or in reasoning. I'm not saying it's a wrong thing to do... not an expert, but i just don't see how the result of such a function can be claimed to be well defined. In the proofing steps the results of these functions are '1' or true.

Anyway that's it.. and if that's what maths says re cantor is correct that's what it says.

I just know it's wrong, if maths can make infinity prove the things it does.. then it isn't using infinity.

J. _______________________________________________________________________

The following shows the vulnerability of cantor,s proof.

We consider a list of decimals L*={a1,a2,a3. . aw}, where aw is the limit of the seq. a1,a2,a3. . ,all ai's assumed to be different. The partial diagonals are D1,D2,D3,...and correspond to a1, a2,a3 and so on. The diagonal D* itself corresponds to aw. Thus, the existence of D* is based on the inclusion of aw in the list L*. It is also clear that D* is not equal to any of the ai (i in N). However, D* necessarily differs from aw only in the w-th place and hence may be equal to it.

Now, if the list L* is defined, then so is the list L=L*-{aw}. Corresponding to this list is a diagonal D. (This is the usual list and the usual diagonal). Now, D cannot correspond to any of the ai's(i is in N).Then, by the uniqueness of limit of the seq. D1,D2,D3. . ,D must be equal to D*. But this means that aw is in the list L.

Hence, neither the list L nor the list L* are well defined. That also means that the diagonal D or D* are also not well defined.


I don't understand why people insist on writing stuff like the above. First it says aw is the limit, but there's no reason given to think there is any limit: most sequences do not converge to any limit. Then it refers to the wth position. What position is that? Every position in the list occurs after only a finite number of steps, and others come after it. Which of those finite positions is this one? And why in the world should the limit correspond in any way to anything involving the diagonal? No explanation is given. Would the author of the above please try honesty for a change? If you have questions about mathematics, ask someone who knows. Michael Hardy 21:25, 26 August 2005 (UTC)

Mike, you would agree that Cantor’s argument is applicable to any list of reals. We can select a list, which does converge to a limit. For example, the list L* could be,

a1=0.01101010. . ., a2=0.11101010. . ., a3=0.10001010. . ., a4=0.101110101. . ., . . . aw=0.10101010.. . . (read w as omega). Each of the ai’s differs from 0.101010. . .,only in the i th place. Then, this sequence would converge to aw=0.101010. . . Further, each finite partial list can result in only a finite partial diagonal. The completed infinite diagonal can result only if the limit aw is included in the list. As is clear, this diagonal is equal to aw. Now, if the list L* exists, then so does L=L*-{aw}.If so, it would be the immediate predecessor of the list L*, and allow us to define the immediate predecessor of the limit ordinal w ! It is this (not well defined)list L and the corresponding diagonal that form the basis of the diagonal proof. I also believed in Cantor’s theory for thirty years. Now, I have doubts. [Apoorv1].

Your argument is full of mistakes. You say we can select a list that does converge. So what? The point is to show that ALL lists, not just the ones that converge, fail to enumerate all reals. And it's trivial to show that a convergent sequence of reals cannot enumerate all reals, without any sort of diagonal argument. You propose to delete "aw" from your list. But "aw" is never in any finite position in your list in the first place; you've just appended it at the end. The argument is supposed to be about lists in which each entry is in some finite position. Moreover, a "list" containing one entry in each finite position and then an ωth entry would correspond to the ordinal ω + 1, not to ω. Michael Hardy 22:55, 28 August 2005 (UTC)

Mike,you have made three observations.I deal with the second and third observations first. Let’s look at this table

ordinal------1---------2---------3--------. . .(w-1)?------------w

mem. list----a1--------a2--------a3------. . .???-----------aw

partlist-----a1-------a1a2-----a1a2a3--. . .a1a2a3.??---a1a2a3. . aw

diagonal------d1-------d2-------d3-------. ..D???-----------D*

(pardon the poor formatting).

It is clear that aw does not correspond to any finite ordinal. Moreover, it is the first member of the list that does not so correspond to a finite ordinal. Since w is the first infinite ordinal, aw corresponds to w. We also have the correspondence between the members aj in row 2 and the partial lists a1a2. . aj (comprising of that member and all members preceding it) as shown in row 3. It is clear then that the diagonal D* and the diagonal D are both equal (being in the w and (w-1)th position in the seq. of partial diagonals), although they correspond to the two (supposedly)distinct lists L* and L.

Re. Your first observation, the idea is to show that the diagonal method does not necessarily lead to a member not in the list. The convergence of the seq ai, is not essential to the demonstration; the essential point is that the lists a1,a2,a3. . . and a1,a2,a3. . aw (aw being any number) can be shown to correspond to ordinals (w-1) and w.


I guess this is your major error:
"The completed infinite diagonal can result only if the limit aw is included in the list."
In an infinite sequence there is no last element, so you can not talk about removing the last one from L* and calling L a predecessor in the sense of finite partial lists - note that neither L nor L* are finite. I hope I got you right - could you please explain the term completed infinity? Misza13 18:39:42, 2005-08-27 (UTC)
Oh, and by the way - what's a list? I've heard of sets and sequences, but lists? Could you define it, please? 'Cause I'm afraid you consider it as something in between these two and thus not properly defined. Misza13 12:47:50, 2005-08-28 (UTC)

Misza,my comments above refer. [Apoorv1]

All right, let's say I can live through your "lists" (still not formally defined?) up to the point where you construct diagonals out of "partlists". BUT! Now comes the big one - D*. Being a diagonal it is supposed to be a real number. But in your "proof" it seems to be an infinite sequence of digits followed by a single digit. Hey, this is not a real number at all. But even then, which digit would that be (the last one)? If you say the -th (infinieth? ;-) digit of then you're in trouble, 'cause doesn't have such. So what is D* then? Misza13 11:41:48, 2005-08-30 (UTC)

Misza,the interpretation of D* is a subsidiary issue;the essential point is that the partial lists (or the corresponding diagonals) can be interpreted as a representation of the ordinals, and this representation allows an immediate predecessor of the limit ordinal w to be defined. [Apoorv1]

I think I know where's your error. I asked you to define those "lists" and "partlists" for a reason. Without proper mathematical definitions you can prove anything. Try defining a list properly and then rewrite the table above - I'm especially interested in the "partlist" row. I don't know what are the last two elements in it are they finite? What do those .'s and ?'s mean there. Please be pedantic in mathematics - it's much harder to make errors then. From what I see right now is that corresponds to and corresponds to and thus has a predecessor - and everything's fine. Misza13 17:42:11, 2005-09-01 (UTC)

Misza, As to the interpretation of the partlists, you can take them to be sets. The correspondence given in the table is clear:1--a1--{a1},2--a2--{a1,a2},and so on till,w--aw--{a1,}.For every ordinal counted, you push the corresponding a into the list/set.As you count w ,you push aw into the list/set.So why do you say that L corresponds to w and L* corresponds to (w+1)? [Apoorv1]

The problem is in the words "and so on till". Let's say your algorithm begins with an empty set and the starts adding and so on to it. But it will never cease doing so and thus will never arrive at the step "push to the set". You used the words "As you count ..." but here's the catch - the ordinal numbers are uncountable! Every finite ordinal will be counted, but will not. A side note: the set with the order where i,j are ordinals corresponds to the ordinal . Misza13 10:40:41, 2005-09-03 (UTC)

Misza, you say that I will never be able to push aw into the list.At the same time you define L to be the infinite union a1Ua2Ua3...Is this union also equal to ... [[[{a1}U{a2}]U{a3}]U{a4}]...?That is,is the infinite union the same as what is obtained by successive pairwise unions? [Apoorv]

The infinite union (like any union) is the set of all elements of the unioned sets: .
The expression is a bit informal to me (but that's just me). Nevertheless, yes it's the same thing because every element of L will be added (soooner or later but will be). However, if you say that after all of them you want add one more element then you're wrong - you'll never get to because all the previous ones will take you literally eternity to add. Misza13 10:27, 13 September 2005 (UTC)

Misza,Are we saying that the set ...((((a1Ua2)Ua3)Ua3)Ua4)...does not exist but the indexed union U{ai:i€N} exists?We could express L in this form because we used N as the index set. What about N itself? N is the smallest inductive set closed under the successor operation.So, N is {1}U{2}U{3}. . .We cannot write N as U{i:i€N} as it would be an obviously circular definition.If N ={1}U{2}U{3}... does not take an eternity to add, then why should L=a1Ua2Ua3...? [Apoorv1]

We are not saying. You are. I only said that writing unions this way is a bit informal to me. Similarly, I prefer writing series as one expression under a big sigma (where every element of the series is given explicitly) instead of guessing what do those 3 suspension dots mean - guess the next symbol is more appropriate in an IQ test. ;-)
I.e. I prefer the left side of this, although I don't say that the right one is wrong (because it is right ;-p ):
But that's a side note that doesn't have anything to do with eternity. Again, I didn't say that N={1}U{2}U{3}U... doesn't take eternity to add. Please stop putting words in my mouth... erm... under my pen... under my fingers... whatever - just don't. And reconsider this:
Plan for today:
1. Count all natural numbers.
2. Do something else.
And tell me, how on earth do you think you will ever arrive at point 2? Misza13 09:40, 14 September 2005 (UTC)

BC's stuff[edit]

[I moved BC's stuff to its own section, it didnt seem to be part of the flow - William M. Connolley 08:55:06, 2005-09-07 (UTC)]

With the domain of r changed to the closed unit interval [0,1] <instead of the open unit interval (0,1)>, the Cantor's diagonal argument presented is fatally flawed ab initio because the two endpoints 0 (0.000...) and 1 (0.111... in binary system) are anti-diagonal numbers of each other --- that is, their presence refute Cantor's diagonal argument from the beginning. If you claim that both all 0's and all 1's as diagonal terms is not possible for row-listing all the real numbwrs, then you have already excluded two real numbers 0 and 1 from your domain without even applying Cantor's diagonal argument. Thus, Cantor's diagonal proof is typically presented with (0,1) as the domain of r.

Dunno really what you're saying here. Why is 0.0000... so different from 0.1000... or 0.010000...? William M. Connolley 08:55:06, 2005-09-07 (UTC).
In the row-listing of real numbers, the diagonal digits form an _inherent list inclusion and imposition of order_ condition on the row-listed numbers [once you understand this, you will comprehend the intrinsic self-contradiction in Cantor's diagonal argument -- that is, the anti-diagonal number is _indubitably excluded_ by the very nature of the row-listing -- in plain words, however one specifies the list inclusion and imposition of order on the real numbers to be row-listed, it redounds to the condition that for every row-listed number, its column-digit at the row-number position (that is, diagonal digit) is _that digit_ so the anti-diagonal number is evidently excluded being different digit-for-digit diagonally from the row-listed numbers -- that is, it does not satisfy the row-listing specification so it cannot be included in the row-list in the first place] -- thus, the row-listing condition of all 0s intrinsically excludes the number with all 1s for its digits (and vice versa). This is a fact that refutes Cantor's diagonal argument ab initio -- taking it as a counter-example -- so, the common domain for Cantor's diagonal argument is (0,1). In plain words, a list inclusion and imposition of order condition for row-listing real numbers that redounds to having 0s in all the diagonal position excludes 1 (0.111...) [and vice versa] even without applying Cantor's diagonal argument. It must also be emphasized that Cantor's diagonal argument presupposes that row-listing of all the fractional numbers in the enumeration form r1, r2,r3,... is possible (so one can deny it in the reductio ad absurdum argument) -- so this entails a list inclusion and imposition of order for uniquely row-listing the fractional real numbers. It is the very fact that whatever list inclusion and imposition of order for the row-listing you specify initially, it is tantamount to specifying that the diagonal digits are as they are so the anti-diagonal number is excluded ab initio without the need for Cantor's diagonal argument. This discussion would now lead to the antinomies of vacuous truth, material implication, and Frege's logic. Briefly, my position on this issue is that modern mathematics is suffering from a _foundational crisis_ because of the imprudent relegation of Aristotle's three "laws of thought" (principles of identity, non-contradiction, and excluded middle) as mere theorem's in Frege's to Russell's to Hilbert's to Godel's systems (that is, the former first principles are derivable from "more primitive" axioms by the latter's systems) as well as the fashionable supplanting of Aristotle's "potential infinity" by Cantor's "actual infinity". I summarize all of these in one word -- antinomy or self-contradiction. "Modern" mathematics supports "vacuous truths" (for examples: with truth-functional material implication, both ~P -> Q as well as ~P -> ~Q are true; with set theory, the empty set is an element of the power set of any given set as well as the power set of the given set's complement set -- these make logic and set theory inherently inconsistent) and also "unrealizable falsities" (for example: 100 meter dash in 1 second, completed infinite set, etc.). Aristotle's first principle of non-contradiction bars self-contradiction ab initio -- that is, as long as you don't apply, say ~P -> Q and ~P -> ~Q, AT THE SAME TIME IN THE SAME RESPECT (which is tantamount to ~P <-> P by contraposition (by Karl Popper, contraposition is also a first principle since it checks infinite regression of reasoning) of the second, a self-contradiction), then everything is fine in "modern" mathematics. I have documented that most of the crisis in modern mathematics is brought on by a self-contradiction (Note: Cantor's diagonal argument is a self-contradiction!). Godel's incompleteness theorems which uses self-contradictory proposition ("This statment cannot be proved" --- yet Godel went ahead and "proved" that "it cannot be proved") are untenable ab initio (one cannot use reductio ad absurdum argument to prove or disprove a self-contradictory proposition) but even in theoretical computer science and artificial intelligence -- with the P vs NP problem which involve the self-contradiction in "polynomial" and "exponential" "computational complexity" considering that, by the binomial theorem, 2**n is equal to 1 + n + n(n-1)/2 + . . . + n(n-1)/2 + n + 1 ... (([ (13 Sep 2005)]

Cantor's diagonal argument does not also work for fractional rational numbers because the "anti-diagonal real number" is indeed a fractional irrational number --- hence, the presence of the prefix fractional expansion point is not a consequence nor a valid justification for the argument that Cantor's diagonal argument does not work on integers.

In Cantor's diagonal argument, the Cantorians make a humungous deal of the sole "excluded real number" limit point (with their insistence on the standard enumeration form r1, r2, r3, ...) of a countably infinite sequence of _rational_ numbers. However, with their insistence on the open interval (0,1) [0 < r < 1] as their domain of argument (I have already noted earlier my objection to this article's use of the closed unit interval as domain), they do not seem able to appreciate that they are already excluding the 2 endpoints (0 = 0.000...) and (1 = 0.111... in binary system) of an interval (is there really an interval with no endpoints?). Anyway, the prefix fractional expansion point is a consequence of the open unit interval (0,1) and it is untenably used as a justification for Cantor's diagonal argument that already excludes the endpoints 0 and 1 --- which are known ab initio to be anti-diagonal real numbers of each other.

The open unit interval is often defended by invoking their essence as a _set_ [the closed unit interval set less 2 elements]. No logical contradiction arises from this "definition". However, what is being assailed in Cantor's diagonal argument is its claim of "uncountability" of the open unit interval whose "anti-diagonal real number" is untenably justified merely by the prefix fractional expansion point --- in other words, the same Cantor's diagonal argument does not apply to the closed unit interval with its known anti-diagonal endpoints.

The contextual diference issue of 0.r1r2r3.... as a _variable_ or an _arbitrary constant_ (that is, the r's as just place-value holders ("the form") for the fractional expansion digits ("the substance") of a _real_ number) --- one that only _possibly_ _represents_ a real number but may _actually_ _not_ be a true fractional real number such as square root of 2, or pi, or e --- is another concern that is relevant here. In plain words, it is not correct to take a representation such as 0.r1r2r3... as a _real_ number just because of its prefixed fractional expansion point. [ (6 SEP 2005)]

I don't understand your objection to 0.r1r2r3r4r5... being a real number. 0.r1, 0.r1r2, 0.r1r2r3, 0.r1r2r3r4, ..., provably converges to a real number. What is your problem with that? William M. Connolley 08:55:06, 2005-09-07 (UTC).
First, is it a real number point or an _interval_? If you claim it to be the former, you _must_ also accept its having a digit at the omegath position ...
Second, the supposed enumeration r1,r2,r3,... must row-list the fractional real numbers _uniquely_ and _exhaustively_ --- any list inclusion and imposition of order on the row-listing redounds to the specification that the nth digit of the nth row-listed number must be rnn (that is, the diagonal digits) so the anti-diagonal is indubitably not included in the row-listed "real numbers" (or intervals?) . . .
Cantor's anti-diagonal number, Borel's number, Chaitin's number, etc. are _not_ real numbers -- just as 0.r1r2r3... is not a real number -- on the other hand, 5, 1.25, square root of 2, pi, e, are real numbers -- they have well-defned expansion digits ... every mathematical object (as any other object) has both _substance_ and _form_ ... in plain words, everyone in the mathematical world agree that, say, the 5th decimal digit of pi-3 is 9 --- on the other hand, what is the 5th decimal digit of Cantor's anti-diagonal number (or Borel's number, or Chaitin's number)? --- well, it _varies_ from individual to tindividual so it is a variable, or at best, an arbitrary constant, whose claim for being a "real number" merely emanates from the prefixed decimal expansion point.

[ (13 Sep 2005)]

Yet another rant[edit]

All the nonsense of Cantors Diagonal Method derives from his contradictory claim to be able to conceive of the INFINITE list of all infinite decimal sequences as of a COMPLETE LIST! Haven’t we learned that ‘omega+1 = omega’! He was tremendously overestimating his own mental capacities (his first step in direction of the asylum!). Cantors brain was just as finite as are ours today with no space for infinite lists. To demonstrate his diagonal argument on a small finite list of finite sequences is just a lousy trick to cheat the uncritical reader into accepting ‘Cantors Paradise of higher Infinities’ (Hilbert) as a new field of mathematics. Nobody is capable of ‘giving’ any real number in the form of an infinite decimal sequence instead of by presenting an algorithm that allows to determine as many of its decimals as any one desires. But these algorithms may lexicographically be ordered, so they are countable!

Thaks so much to you (I guess it is Mr William M CONNOLLY !? [Its Dr to you; and try to learn how to spell - William M. Connolley 15:50, 10 October 2005 (UTC)])for calling this a RANT! So I add the following proof:

For all thouse who still won’t believe it: every mathematician should be familiar with the definition of real numbers as ‘Dedekind cuts’. On page 22 of ‘Das Kontinuum’ by Hermann Weyl (1918) we read: ‘under a real number @ (read : alpha) we understand the set of all rational numbers which are smaller than @’ ! This definition (apart from it’s nonsensical selfreference!) implies that the smallest possible difference between two real numbers @’ and @" is the one rational number that belongs to @" but not to @’. So there can impossibly exist more different real numbers than there are rational ones! And certainly no @ can be ‘given’ unless by an algorithm out of the above mentioned lexicographically ordered list. Dr.Eginhart Biedermann 28.9.2005 -- 09:56, 28 September 2005 (UTC)
If you're going to write stuff like a lousy trick to cheat the uncritical reader then get used to accusations of ranting. The reals can be defined as dedekind cuts, but they can also be defined in other ways. Sequences, which are roughly decimal expansions, is another valid way. I don't understand why you consider the defn of cuts about as selfreferential. I also don't understand why you think the above is a proof: by your understanding of cuts, every real is also a rational; clearly this is false. William M. Connolley 15:17, 28 September 2005 (UTC).Sorry Sir, I could’nt know about your Dr.- title. [Indeed not. And had you not "Mr"'d me unnecessarily, you wouldn't have been corrected. WMC is fine William M. Connolley 19:07, 13 October 2005 (UTC)]

As to your remarks:

  • From my ‘RANT’ you may easily derive that I am well familiar with the definition of real numbers as ‘sequencies’ as ‘decimal expansions’, more precisely, I insist, as never ending sequencies, as decimal expansions that cannot be defined other than by algorithms that allow the determination of as many decimals as any one desires, yet never coming to an end. You need not waste your time on telling me that.
  • The definition of a real number as a Dedekind-cut is selfreferent since it defines (tries to define !) @ by @ ! And it is nonsensical, selfcontradictory since it defines @ not to be @ itself but the set of all rationals smaller than @ , with the effect that, @ being by chance a rational number, it is claimed not to be this rational number but the set of all smaller ones !
    • If you think this, you are firmly on "original research" grounds. You cannot edit wikipedia on this basis. William M. Connolley 19:07, 13 October 2005 (UTC).
  • You claim that by MY understanding of cuts every real would be a rational. Sorry, I stick to the Dedekind-Weyl wording that every real is the set of all the (infinitely many!) rationals smaller than that real. What makes you come to your contrary claim?
    • Your So there can impossibly exist more different real numbers than there are rational ones
  • On the basis of what consideration do you question my argument that the definition of the reals on the basis of the rationals, with the smallest possible difference between two reals being one single rational, prooves that there cannot be more reals than rationals ?

Biedermann 12:04, 13 October 2005 (UTC)

This is basically a waste of time. You need a good basic book, and a tutor. Or perhaps you could read the wiki dedekind cut page. William M. Connolley 19:07, 13 October 2005 (UTC).

21.10.2005 Biedermann 11:31, 21 October 2005 (UTC)

  • Well then, just for the fun of it, I will ‘waste’ some more minutes on this subject.
  • First of all: thanks a lot, W.M.C., for your kind textbook advice. Yet that leaves me with the question: which tutors and textbooks were it that may have taught you a lot of ‘shape of the earth thinking’, but apparently failed to teach you to SEE what is right before your eyes: else you would not have had to ask me for an explanation of the selfreference in a definition of the kind a = a  ! For anything so near at sight the ‘flat-earth’ concept is perfectly adequate! And what on earth could be more flat-earthly than the Wiki-exposition of the Diagonal Argument?
  • Certainly, your Dedekind-cut definition of the square root of 2 looks much nicer than the Weyl-wording to which I took reference. Yet it can serve as example only for those coutably many reals that are defined by some algorithm!
  • If you question what seems to me to be selfevident, i.e. defining the reals on the basis of the countably many rationals can impossibly yield uncountably many more reals, I would like to see a convincing proof for this claim.
  • Finally, Im am glad to realize that calling my RANT a RANT did not disprove any of my arguments.
    • In any case, I wish you and all the Cantor fans much fun in your paradise of ever higher infinities, where Cantor even believed to find a proof for the existence of GOD, before entering the asylum.

Biedermann 11:31, 21 October 2005 (UTC)

... or consider the number of generators (re infinite sets)[edit]

Possibly here: "constructible" is equivalent to "countable";-)

Cantor's uncountable reals R on [0,1) are an abstract concept, shown to not be (Peano-) 'countable', via his diagonal argument.

They are hardly 'numbers' in the realistic/computable sense, but abstract entities satisfying certain arithmetic-like syntax rules. So they rather belong to the broad category of 'languages & data structures'. AFAIK considering them as 'elements', or 'real numbers', on a linear number-line breeds at lot of confusion.

Not so much their cardinality ('amount' of reals;-) but their generation in a closed system R(+,*) with arithmetic & sequencing properties distinquishes them from Peano's naturals N(+) with one generator: 1 under (+), eqv. to iterating the 'successor FUNCTION'...

This is not true for the reals R on [0,1) -- which map into Z! , the 2-generator group of all permutations of the integers Z.

These again map into the 3-generator semigroup Z^Z of all transformations of Z = all FUNCTIONS: Z --> Z (closing the Peano circle;-)

- NB -

Nico Benschop 13-dec-2005

Self-contradiction in “proof by contradiction”[edit]

One of the “absorption laws” of propositional logic or statement calculus is: (P --> (Q AND R)) <--> ((P --> Q) AND (P --> R)). Thus, (P --> (Q AND ~Q)) <--> ((P --> Q) AND (P --> ~Q)).

The formal argument in the “proof” of general Cantor’s theorem can be summarized as follows ---

If there is a 1:1 correspondence between S and P(S), then the generator of T is in T. [1]
If there is a 1:1 correspondence between S and P(S), then the generator of T is not in T. [2]
Therefore, there is no 1:1 correspondence between S and P(S).

The conclusion follows from the “belief” that propositions [1] and [2] are contradictory. It might be argued that the conclusion follows from the contradiction “the generator of T is in T” AND “the generator of T is not in T”. However, the “absorption law” equivalence could not be discounted — that is, the latter contradiction claim also asserts the former “contradiction” claim. Moreover, it is the claims P --> Q and P --> ~Q that are separately demonstrated in this type of “proof by contradiction” and not the claim P --> (Q AND ~Q).

The following discussion by Alice Ambrose and Morris Lazerowitz in their book entitled “Fundamentals of Symbolic Logic” (New York: Holt, Rinehart and Winston; 1962) is enlightening in pointing out the logical defect in the preceding Cantor’s reasoning ---

Any two propositions of ordinary discourse are related in one of the seven ways described (pages 85 – 92) [equivalence, superimplication, subalteration, subcontrariety, contrariety, contradiction, and logical independence]. Failure to understand their relationships is responsible for many of the fallacies in reasoning. For example, contradictories and contraries, contraries and subcontraries, are frequently confused, and propositions are sometimes supposed to be equivalent when they are not.
As an illustration of a further logical relation commonly confused, take the two propositions ---
If it rains, the crops will be good. [1]
If it rains, the crops will not be good. [2]
It might be supposed that these two propositions could not both be true, and that, hence, a person who made both these statements would be uttering an inconsistency. One needs merely to note that both propositions are true under the condition that it does not rain, to see that they are consistent with each other, and that therefore the supposition of their inconsistency is a mistake. These propositions are subcontraries.

In symbolic logic, both Georg Cantor’s argument as well as Alice Ambrose and Morris Lazerowitz’s example are of the form: P --> Q and P --> ~Q. Moreover, ((P --> Q) AND (P --> ~Q)) --> ~P is a tautology --- it is a flawed (particularly when there is no relevant relation between P and Q) variant of “proof by contradiction”.

By the very definition of material implication, both P --> Q and P --> ~Q are true at the same time when P is false (regardless of the presence or absence of material relevance of the antecedent P to the consequent Q or ~Q) — so, invoking that these 2 propositional forms are inconsistent with each other is indeed preposterous. It might be argued (in fact, as guaranteed by the tautology scheme cited above) that the simultaneous truth of these two propositions _implies_ the falsity of the antecedent P. What I am counter-arguing is that they are _defined_ to be so — that is, it is a gross self-contradiction to call upon a definition to rationalize an argument. However, I reiterate that, as presented, the flaw in Cantor’s argument is in the false belief that [1] and [2] are contradictories (that is, when 2 propositions cannot both be true or both be false at the same time or that their conjunction is always false for all truth-value assignments to their atomic formulas or prime constituents).
Georg Cantor inferred his conclusion without regard for the material or factual truth of his two implication premises. In the simpler-to-analyze example by Ambrose and Lazerowitz on the “rain” and “good crops” relation, we can easily see that both the given implication-premises lack material truth:
There are countless of actual true-to-life circumstances whereby either “the crops will be good” or “the crops will not be good” is true without their truth being a direct consequence of the truth or falsity of “it rains”.
On the other hand, if “it rains” adequately only then “the crops will be good” is true while if “it rains” exceedingly hard so that flooding occurs then “the crops will not be good” is also true.

Ambrose and Lazerowitz expounded on the issue of escaping commitment to the conclusion of an inference which is also particularly relevant in pointing out the flaw in Cantor’s line of reasoning ---

It is to be noted that whenever an inference is made, not only is an implication asserted to hold between premises and conclusion, but both premises and the conclusion are asserted to be true [it is emphasized that modus ponens ((P --> Q) AND P) --> Q is a tautology]. Both these facts are relevant to a consideration of the means of escaping commitment to the truth of an inferred conclusion. There are, in general, two ways of doing this. One way is to deny that the implication holds. This amounts to pointing out that the argument is formally invalid. The second way is to take exception to the material truth of the asserted premises; that is, either to refuse to agree to the initial assumptions or to point out their actual falsity. The relevance of denying the truth of the premises depends upon a logical fact about the relation between the antecedent and consequent of any implication when the antecedent is false.
Consider the argument ---
If it rains, it pours.
It is raining.
Therefore, it is pouring.
This asserts, in part, that if the first two propositions are true then “It is pouring” must be true. Suppose now that either the implicative proposition “If it rains, it pours” is false or that “It is raining” is false. The conjunction of the two is in either case false. . . . the falsity of the antecedent (P --> Q) AND P is consistent with the falsity of Q as well as with its truth; hence, the truth of Q does not follow from the falsity of (P --> Q) AND P.
The function ~((P --> Q) AND P) --> Q is not tautologous --- the truth-value of Q is not uniquely determined by ~((P --> Q) AND P). In general, if one denies the material truth of the premises or refuses to assent to it, there is no logical necessity of assenting to the truth of the conclusion.

Applying Ambrose and Lazerowitz’s well-informed logical declarations to Georg Cantor’s alleged ”proof” of his hierarchy-of-infinite-power-sets theorem, it is easily seen that Georg Cantor’s argument is not a valid application of “proof by contradiction” deduction — we firmly deny the material truth of its implication premises or we refuse to assent to them on the ground that T [the set of all the elements of the infinite set S which are not contained in their respective images for the presumed one-to-one correspondence between S and its power set P(S)] is not really a completely constructible set (as defined, T is an indeterminate infinite set) or the contradiction with regard to the generator of T occurs only if we look at T as a completed totality of an infinite set.

The simultaneous truth of P --> Q and P --> ~Q when P is false are embodied in the definition of modern Fregean logic’s material implication (regardless of the presence or absence of material relevance of the antecedent P to the consequent Q or ~Q) --- so, it is a gross self-contradiction to call upon some definition (which cannot be contradicted) to rationalize a faulty alleged “proof by contradiction” argument. Furthermore, because both P --> Q and P --> ~Q are defined true when P is false, then they do not form a contradiction. The self-contradiction is in invoking that they form a contradiction in spite of the concerted efforts by present-day logicians justifying the modern meaning of material implication that they do not.

It might be argued that the defect is merely in the nomenclature “proof by contradiction” which could be immediately remedied by just dropping the “contradiction” reference to the argumentation. However, it is stressed that this is not simply the case --- rather, it is the abandonment by modern Fregean logic of the existential import of the universal quantifier that jettisoned such relations as subcontraries and left only contradiction relations in the traditional so-called Aristotle’s “square of opposition” (relating “All S is P”, “No S is P”, “Some S is P”, “Some S is not P”) --- the sides (contrariety, subcontrariety, superimplication, and subalternation) are discarded while the diagonal (contradiction) is retained.
In other words, in the classical Aristotlean logic, “All S is P” (also expressible as “No S is non-P”) and “No S is P” (also expressible as “All S is non-P”) implies the existence of S. With the Fregean logic interpretation dropping the existential import of a universal quantifier (cajoled by the seeming simplification offered by adhering to a Boolean algebra implementation), comes the definition of material implication with P --> Q and P --> ~Q being both true when P is false without any regard for any factual relevance relating the antecedent P and the consequent Q or ~Q. As a consequence, in modern Fregean logic, “it will be necessary to accept what at first sight is paradoxical” --- for example, “both ‘All leprechauns are bearded’ [which can also be stated as “No leprechauns are not bearded”] and ‘No leprechauns are bearded’ [which can also be expressed as “All leprechauns are not bearded”] will be counted true, given the circumstance that there are no leprechauns” [Ambrose and Lazerowitz].
Scientific theories rigorously observe the Aristotlean logic’s implied existential import of the universal quantifier so they are successfully applied in practice. In Fregean predicate logic, the formula (For all)vP --> (There exist)vP is a generally accepted theorem which makes explicit what was implicit in Aristotlean logic. However, the rationalization for defining material implication to be true whenever the antecedent is false had already been forgotten --- hence, the hidden self-contradiction (in the example cited about leprechauns, the apparent contradiction is easily seen when the statements with the same quantifier are compared).
It is noted that every model for a first-order theory is prescribed to have a non-empty domain. It is also stressed that any specification of a self-contradiction serves to define an empty set.

Related as “vacuous truths” to logic’s material implication “paradox” is the inherent “paradox” in set theory --- if the empty set is an element of any set’s power set (or a subset of any set), then the empty set is also an element of the power set of the given set’s complement set (or a subset of the given set’s complement set) --- thus, the set of all subsets of a given set and the set of all subsets of its complement set are not mutually exclusive despite the fact that their intersection set contains the empty set (this means a hierarchical level of interpretation for the supposedly unique empty set). In the present case, the self-contradiction is in discarding the existential import of the universal quantifier while giving existential attribute to the empty set — that is, the empty set has cardinal number 0 while the set that contains the empty set has cardinal number 1.

This engenders positive motivation for formulating some set theory based on the primitive concepts “set” and “subset” by considering power sets or sets of subsets instead of sets of individual elements (that is, {a} instead of just a) — the isomorphism with the incompletable set of all natural numbers whose every element has a successor is evident from the fact that every subset implies a superset. Thus, paradoxes involving the comparison of the sizes of two distinct sets with respect to “one being a subset of the other” and “one-to-one correspondence of their respective individual elements” would be mooted ab initio — that is, there will be no “uncountable set” unless the latter signifies “every subset (or, element) always has a superset (or, successor element)” or “not a completeable set”.

Every semantic paradox has its analog in set theory, and every set theory paradox has its semantic analog --- that is, every truth-value statement can be rephrased as a statement about sets, and vice versa. The liar-paradox assertion --- “This statement is false” --- can be translated into --- “This statement is a member of the set of all false statements”. The correlation with the completed infinite set self-contradiction is evident — that is, the countably infinite set of all false statements cannot be truly completed. Also, the more basic association with the general inexpressibility of the negation of a countably infinite whole (that is, “the set of all false statements” as the negative of “the set of all true statements”) in terms of its elements and their negatives (that is, the truth or falsity of every statement) is equally manifest. It is further stressed that the assertion “This statement is an element of the set of all true statements” is not a self-contradiction.

The preceding discussion is simply stated in symbolic logic. The truth of a countably infinite disjunction P1 OR P2 OR P3 OR … could be simply established by the truth of just one of its variables even though the latter are countably infinite; however, the truth of a negated countably infinite disjunction ~( P1 OR P2  OR P3 …) = ~P1 AND ~P2 AND ~P3 … could only be ascertained from the truth of all of its negated variables which might be impossible to establish for a domain with countably infinite number of elements.

This provides a very simple proof for Godel’s incompleteness theorem (the relevance of the encompassed natural number system is clear). Please read my discussion text in the Wikipedia article “Godel’s Incompleteness Theorems”. [ --- 10 February 2006]

A layperson's objection to Cantor's proof[edit]

I have a question and possible objection to Cantor's diagonal proof. I am not a mathematician, so please don't jump on me if there are technical errors in how I express this.

To the best of my understanding, the basic idea of the diagonal proof is this. Make a list that you imagine to contain all the real numbers between 0 and 1. Then it is always possible to construct a number not on that list by defining the constructed number to differ from the first number in the frst decimal place, from the second number in the second decimal place, and so on. It may simplify thinking about the argument to specify that all the numbers are expressed in binary. That will insure that for any given list, one and only one number can be constructed using Cantor's method.

Now let's make our list and construct our "Cantor number".

Now here's the slick trick. Create a second auxilary list, call it "Extras" (or whatever). Place the newly constructed number on that list. Now if we combine the original list with the "extra" list, we have a list that contains precisely the number that was suposedly "not on the (original) list".

But there's an obvious objection. We now have a new list that is subject anew to the diagonalization process. We can still create a number not on the new list.

No problem. Just put that number as the second entry in the "extra" list, recombine the extra and original lists, and you have a new list. Sure you can now construct another number not on the list. And I can put it on the list. For as long as you can construct numbers not on the newest list, I can put those numbers on a newer list.

Maybe I missed something obvious, but this process looks a lot like enumeration to me. I would suggest that far from proving that the reals cannot be enumerated, Cantor in fact provided precisely the method for enumerating them.

I'm sure that the overwhelming majority of mathematicians here who accept Cantor's proof will see flaws in this argument, but I would be very interested to know what they might be. I have thought about it a lot, and I can't see any obvious objection.

Although, there is one possible question that occurs to me, but I don't know enough to answer it. It can be objected that we are not actually enumerating "all" the reals in the specified interval, because even if we construct diagonal numbers and amend our list "forever", there would be reals that would never show up on the list. If so, this would disprove my argument. But is it so?

Comments invited -Steve 01:10, 24 May 2006 (UTC)

So this is an objection that occurs to lots of people from time to time. Many of them come to the conclusion that they've discovered a simple error that more than a century of mathematicians have somehow missed; I have to say it's refreshing to see your quite different attitude.
The thing to keep in mind is that the argument applies to every enumeration. Yes, if you start with an incomplete enumeration, the argument will find some you forgot to include. But, if a complete one exists, then why start with an incomplete one? Just throw the complete one in from the start.
But of course if you did, then the argument would give you a contradiction. So you can't. But if it existed, you could. So it doesn't exist. --Trovatore 03:48, 24 May 2006 (UTC)

Suppose that you were correct. By the same reasoning, let L be a finite list of integers. There is an integer not on the list, so add it. Continue this process, generating new lists. The problem is that after doing this infinitely many times, the list is no longer finite. In your case above, if you could some how carry out the process; it still does not mean that the list will remain countable. On an aside, the Baire Category Theorem can be used to show that the reals are not equipotent the integers, hence, even if Cantor did make an error; the reals are still nondenumerable.Phoenix1177 (talk) 05:03, 2 January 2008 (UTC)

MY 2 cents[edit]

The argument can be reduced to two statements. Statement 1: set A contains all real numbers in the interval [0,1]. Statement 2: a real number x in the interval, can be formed that is not in set A. The two statements are obviously inconsistent or contradictory. If one is true then the other is not, i.e. there are TWO choices. If statement 1 is true then the set A contains x, and is complete. If statement 2 is true then the set A is incomplete, and forming x is resuming the construction process.The second statement is inconsistent within the system because using the same set of axioms,it states that the element x can be formed outside the set but cannot be formed within the set, even though the same class of elements are already in the set. Cantor's error is to ignore the second statement as false. What process formed the numbers in the set, and why can't it form x? If his process forms x, why can't it form all elements? He also lived before the work of Goedel.-phyti 060526

Your comments give me a better understanding of the question. This is probably more desirable than coming up with the "right answer" in any case. Thanks guys. -Steve 00:34, 25 May 2006 (UTC)

You might want to read my (professional mathematician's) counterarguments to Cantor's diagonal argument -- then you decide. See for example: Archive of old discussion: May 2002 — May 2004 and BC's stuff above or Wikipedia discussion pages on Cantor's theorem article. If you send me an eMail stating your interest to read my technical papers (they are understandable by even high school math students), then I could send you copies in PDF form. I'm still working on their translations to HTML format for Internet publication.[|BenCawaling]] 03:23, 25 May 2006 (UTC)

Further Musings of a Layperson on Cantor's Proof[edit]

Well, I've been thinking more about the question and would like to share my thoughts. Again, I will use non-technical "common sense" language, and I may state things at length which are obvious. I find this helps keep my thinking clear.

First, lets take a look at the list that we would like to assume contains all the reals in the interval of interest. What can we say about this list? What do we mean if we claim to have produced one?

What we do not mean is that we have written out or printed out such a list on an infinite stack of paper which we can then have delivered via an infinite set of trucks to the infinite loading dock at our favorite Math professor's office building. For one thing, there's not that much paper available. Other more serious objections also apply. Producing an acual list would require an infinite amount of time. There is no point in future historical time when we can stop and say "Voila, the list is done".

So what we actually mean when we say we can make a list is that we can conceive, and describe in some finite statement, the (infinite) method by which such a list could be produced. For the positive integers, this is trivial "start at one and continue to add one".

So we imagine that for the list of reals we have what I would call an "ordering principle". There may be tecnincal objections to what I am going to say next, but from a common sense viewpoint (drawn from the example of the positive integers) it seems that such an ordering principle should meet several conditions.

(1) It should specify a starting point. (2) It should show you how to get from any number to the next number (3) For any specified number contained in the list it should tell you how to reach that number from the beginning.

Now I think I have come to accept Cantor's argument as proof that no single ordering principle can be stated which will include all the real numbers. I think he has shown that.

Where I now think that the question becomes interesting (in the sense of giving rise to further questions) is when we consider the question of devising further ordering principles.

For example, I could say, I will start out with a statement of how to list the rational numbers. This clearly falls short of including all the reals, but since I have accepted Cantor's diagonal argumnent, at least in a limited sense, that doesn't bother me. The list of rationals is merely a starting point.

Now, not surprisingly, I can use the diagonal argument to construct a number not on the list. Of course, I'm speaking loosely. I can't actually construct the number in finite time, but I can give a finite statement, employing the diagonal argument, of how the number is to be constructed. That statement will uniquely specify the number.

Now I will think very hard about this number. Perhaps I will describe it on the Internet to try to get the collaboration of other thinkers. My question will be "Is there an ordering principle which would have allowed me to specify a list containing my newly discovered number? "

Now, as a side comment, it's worth mentioning that we can "look at the back of the book" and discover other ordering principles already known or easily derivable in mathematics that will order other subsets of the reals. I suspect that there is a way of ordering real roots of polynomials, as well as the kinds of infinite series expansions familiar from the cases of e and pi. And almost certainly other classes of more exotic numbers.

But we can suppose we've accounted for all of these. We've found a number not on any of these lists. We want an ordering principle which would generate it.

Now the first question I find interesting is whether we believe that such an ordering principle is always there to be found. If not, we will someday come to the end of all the reals that can ever be ordered and find the first one of which it can be said "this number is from somewhere else. It has popped up from out of nowhere and we will never be able to track it to its lair." The first known unorderable real number!

The above question obviously rests in part on whether the diagonalization process itself can be used as the basis for an ordering principle. If so, you could obviously keep going forever just by doing repeated diagonalizations as I originally proposed.

I think is probably does not, based on the conditions I said such a principle should meet, because it cannot show you how to reach any specified number on its generated list, nor does it allow one to easily grasp how to construct the "next" number. Merely how to construct "another" number. (Is this new number the "next" one - why or why not - how would we know?)

So, what of other ways of coming up with ordering principles. This actually touches on the Artificial Intelligence question. Is there an algorithm which could produce new ordering principles? Could an algorithm be constructed that in infinite time would produce "all" ordering principles? If the answer to this last is yes, then I think the reals are countable after all, since the set of all possible ordering principles would "eventually" order all the reals (unless, as I wondered above, there are some number of reals which in principle have the characteristic that they can never appear on any list constructed acording to an ordering principle.)

Suppose we believe that an algorithm to find "all" ordering principles is impossible. Do we then accept that human intellect can find more ordering principles that any particular algorithm could not? If we say yes to this question, what are the further implications? Do we believe that the human intellect can "eventually" find "all" ordering principles? If we set up a foundation to employ mathematicians into perpetuity to devote themselves to discovering ever more obscure ordering principles for the ordering of ever odder subsets of the reals, does this mean that in infinite time we can order them "all"? And would that mean that they are actually countable - albeit by this rather unusual method?

Well, I don't claim to have any answers for these questions. But I think questions are more fun than answers anyway. Hopefully others agree. I have tried to be like the proverbial "fool" who can ask more questions in 20 minutes than a wise man could answer in 20 years. Hopefully the "wise men" here will not be offended by my effrontery. I just thought these musings might spark some enjoyable thoughts from this community.

Have fun, and thanks for listening.

-Steve 23:36, 25 May 2006 (UTC)

I like your approach.
Yes, there are ways to order roots of polynomials, and many other numbers. And applying the diagonal argument to them will give you a new number not on the list.
Can the diagonal argument be used to produce a new ordering principle? One answer: YES. New ordering principle, type A: Take an existing ordering principle. Apply diagonal argument. (1) starting number is the new number just produced. (2) Next number is the starting number of the old principle, and numbers after that take the same succession as in the old principle. (3) For any given number, either it is the number we just produced, or it isn't. If it is, it is at the start. If it isn't, we ask the old ordering principle where it is, and shift down one place to find it in the new list.
If we can use the diagonal argument as the basis for a new ordering principle, then you say we can go on forever doing diagonalizations as you say, and hope to get all real numbers. One answer: NOT SO. New ordering principle, type B: take existing ordering principle. (1) and (2): for even numbered positions 2n, fill with numbers from old ordering principle at position n. For odd numbered positions 2n-1, fill with numbers produced by diagonalizations as per new ordering principle type A, repeated n times. (3): for any given number, either it was produced by applying diagonalizations as per A for a certain number times -- let us call this number n -- or else it wasn't. If it was, it is at position 2n-1 in the list. If not, ask old ordering principle, and double the answer to get its position in the new list.
But, apply diagonal argument to this principle B to get yet another number ... so obviously we didn't get all numbers by doing this.
OBJECTION to those answers: you say, you don't actually print out the numbers on infinite amounts paper. How silly would that be! You have a process. So for new ordering principle type A, requirement (3), how do you determine whether a given number is actually the same as the new number just produced? For new ordering principle type B, requirement (3), the situation is even worse. You have to search an infinite list. Hah! Count to infinity, then do something else... silliness!
REPLY: Hey, why do we need (3) anyway? Do you not accept Cantor's argument as proof that no (1) and (2) can be stated which will include all the real numbers? I.e. even if you don't have a way to go in the other direction, we can guarantee the new number produced WILL NOT be on the list.
-Dan 03:00, 26 May 2006 (UTC)

Here's why I'm a little nervous about using diagonalization as an ordering principle. Perhaps this is less of a logical objection than an emotional one. I'm not sure. In the case of the ordering principle of the positive integers, the principle is related to the mathematical character of the numbers involved in a straightforward way. Knowing where a number is on the list tells us something about the number. This is also true, though less directly, of the method usually presented for ordering the rationals in a diagonal grid. But it seems to me that diagonalization is less of a mathematical operation that a mechanical one. We know that each successive diagonalization produces "another" number, and we can call it the "next" number, but does the sequence thus produced have any underlying theme other than accidental juxtaposition? Or does this even matter?

Let me state it another way. The ordering principles we are commonly familiar with are all intuitively graspable. At a certain point we go "aha - I see the pattern here". Now what we have with successive diagonalizations is a method of producing a sequence of numbers that may or may not have any underlying pattern. If we compare the easily graspable ordering principles with driving down a road where we can see ahead, then successive diagonalizations is like driving at night with no headlights. We never know where we're going until we get there.

I'm not sure whether this is an actual problem or not. But it bothers me.

-Steve 07:23, 26 May 2006 (UTC)

It might matter, but not in this case. Applying any mechanical operation to any pattern results in some sort of pattern. Maybe not a pattern which is easy on the intuition, but it's there; you can't suddenly get a "lawless" sequence. For that matter, I'm not sure how easily graspable your ordering principles really were to begin with. Remember, you were happy to order the real algebraic number field extended with some transcendentals like e and pi. I'd say this is more complicated than the mechanical operation we're contemplating. -Dan 14:53, 26 May 2006 (UTC)
Look, it's great that you're thinking about these things, but it's not really what talk pages are for. They're meant for discussing improvements to the article, not helping editors work through the issues raised by the article. Sometimes an "arguments" subpage is created for this sort of thing (see e.g. Talk:Gödel's incompleteness theorems/Arguments, and this talk page should probably be refactored along those lines (maybe I'll get to it), but a better idea might be to take the discussion to a Usenet newsgroup such as sci.math. --Trovatore 15:21, 26 May 2006 (UTC)
(Oh, BTW, "you" means "Steve" more than "Dan", but Dan does seem to be enabling here....) --Trovatore 15:27, 26 May 2006 (UTC)
Sorry... my bad. I could have tried to move it elsewhere. As for the article, I am inclined at this point to separate |N| =/= |R| (translation: "there is no enumeration of all the real numbers") into |N| =/= |2^N| ("there is no enumeration of all the infinite sequences of bits") and |2^N|=|R| ("there is a way to match every infinite sequence of bits with one, and only one, real number"). |N| =/= |2^N| is:
  • what Cantor actually did, at least in translation linked;
  • more transparent than our attempt to directly do |N| =/= |[0,1]| = |R| ("there is no enumeration of all real numbers between zero and one inclusive, and there is a way to match every real number in the same range with one, and only one, real number") -- aside from the discussions immediately above, and previously, about rationals, transcendantals, decimal expansions, and other issues, consider that we feel it necessary to have a whole page devoted to a proof that 0.999... equals 1;
  • is really the essence of a diagonal argument, and should not be obscured by other issues.
Now it would be dishonest of me to pretend my opinion was not also formed by the fact that |2^N|=|10^N|=|R| is also, in the end, non-constructive. I actually think one or two of the questions raised are therefore not totally off-base. I plead guilty. So, what do you all think? Shall I (or someone else) go ahead? -Dan 20:53, 26 May 2006 (UTC)
Having been prompted to read for the first time the linked translation of Cantor's proof, I see that Dan has correctly pointed out a problem with the article as now written, namely that the proof given here does not seem to be the Cantor's original one, as the article implies. Paul August 22:32, 26 May 2006 (UTC)

Done. ||N|| =/= ||2^N|| is emphasized, and ||2^N|| = ||R|| is de-emphasized. I think cardinality of the continuum had a more sound explanation of the latter to begin with. -Dan 02:11, 30 May 2006 (UTC) (Now, who wants to reorganize Gödel's incompleteness theorems ...)

I like this version better, and it has the advantage of being the proof that Cantor actually gave. Paul August 02:48, 30 May 2006 (UTC)

not a convincing argument[edit]

If the decimal expansion of a real number in the interval [0,1] is constructed as a sequence of integers, then each position has 10 possible elements: .n, 10 combinations, .nn, 100, etc. The list grows exponentially for each position added. If we use each element at each position, we have all possible combinations and no sequence would be missing.

If one infinite sequence is included then all must be included. Any diagonal sequence would have to be in the list.

1.If he could construct one such sequence, he could construct all of then. 2.Conversly if he can't constuct one, he can't constuct any.

The missing diagonal number is not true because Cantor shows an incomplete list and asks you to take his word. He cannot select the numbers he wants to prove his point. Statement 2 is the reason for no list. 02:21, 18 April 2007 (UTC)phyti

This way you will construct an array of digits, which:
  1. represents only real numbers with finite decimal expansions, ie. containing only finite number of non-zero digits, and
  2. has all digits on its diagonal (and above it) equal zero.
So the diagonal sequence is 000... (consists of zeros only) and the final sequence in the proof, made by modifying digits found on diagonal, contains no zero at all. As a result you get an infinite sequence of digits without zeros, which obviously does not appear in any row of your array (because the array contains only finite sequences with infinite zeros-only tails). And the whole proof still holds — you eventually get a real number which misses in the original sequence of real numbers, which means the original sequence did not contain all real numbers between 0 and 1. --CiaPan (talk) 09:21, 17 December 2009 (UTC)

can't accept this one[edit]

"Therefore it may be seen that this new sequence s0 is distinct from all the sequences in the list." The sequence s0 is distinct from all sequences in the partial list used to construct it. This does not prove it is distinct from other portions of the list, which haven't been compared. This to me, is an unqualified extrapolation from a sample to the entire population, and is more a conjecture. Another portion will show that same partial sequence.Phyti (talk) 01:09, 29 January 2008 (UTC)

No, it shows that it's distinct from all the sequences. Otherwise it would be the same as one of the sequences, but as has been shown, it can't be. That's really all there is to say about it -- it's ironclad and there is no subtletly remaining. --Trovatore (talk) 02:28, 29 January 2008 (UTC)
Looks like the list S already contains all the sequences S(i), because every index i corresponds to a position inside the sequences, and no new positions can be added because we have agreed that the sequences are already presented in full (although it is impossible to imagine them being presented so). Still, this all is counter-intuitive (intuition tells we cannot do anything to infinite lists and sequences because infinite lists and sequences do not exist in the real world where it's possible to act).
Probably, the article could better go into some detail on why and for what the diagonal argument being applied to natural and real numbers is important in mathematics as well as in the "real world", so that a lay reader like me could really understand there is no life without this argument in this or that important field of human activity or imagination. A layman's view is that generic real numbers correspond to nothing in the world we see and experince, and in this sense do not exist, that they are only idealizations of our real and always finite knowledge, and that infinite lists of numbers (be they real or natural) do not exist in the same way, so any layman and not only me is naturally interested why mathematicians study different kinds of non-existence. (talk) 00:51, 19 January 2013 (UTC)
Forget all that philosophy, what bothers me for real is this: how can one say he has picked all the natural numbers? One gave me a bucket of numbers and said: "That's all, there are no more natural numbers". I determined what number is the maximal one in the bucket (if that guy was able to pick them all, then I can inspect them all; and if the guy is not able to pick them all, then no infinite list can be built anyway) and then named a number that is greater by one, so that to add it into the bucket. Then I said, "Now all the natural numbers are in the bucket", and gave the bucket back to my friend, but he disagreed, on the same grounds. Something here must be wrong, but what exactly? - (talk) 05:27, 19 January 2013 (UTC)
Well, seems like the beaut is that the work is never done but the features of its state are the same at whatever point. I can imagine Cantor's devil as a machine that, first, declares it's going to do something abominable (names what and why), reserves B-1 infinite-length registers (B being the base of the numeral system to use), initializes the registers with empty sequences, and then proceeds: at each step, it picks a natural number, generates an (infinite: ???) sequence of digits, seeks a digit on the position that corresponds to the number just picked, makes a set of the other digits, and for each of them, adds a digit to the sequence in a reserved register. Of course, it never finishes its work, but whatever the finish can be, we'll see that when it has come, there are only so much natural numbers, but the sequences of digits outnumber the numbers anyway (whatever nonsense those sequences are).
The problem (my problem and all the readers') is that the finish can't be (from the habitual point of view), and thinking of it is meaningless, unless there is such and such reason to accept this way of thinking in this exactly situation. The rest is to understand what are the reasons to accept these or such things, and I think this is what the article fails to demonstrate, and that's why so many questions from us all. I guess it might be improved in this direction: i.e., show context. -- (the same user) (talk) 18:59, 19 January 2013 (UTC)

Cantor's Nonsense: Pseudo-mathematics at its best.[edit]

This so-called diagonal argument is an example of pseudo-mathematics at its best. To see why it is a false argument, simply switch the position of the two sets in the argument. That is, assume that the reals are "countable". Now "list them all" in the table on the left-hand side in any order. (This, of course, is impossible, but for Cantor and God, anything is possible.) We now have a "completed, countably infinite set" which we can use to compare with, say, the natural numbers.

Done? OK, we will now number each entry on the left using the natural numbers starting with "1" on the right-hand side. Don't forget to draw your 'diagonal" through each one. But wait! No matter how far down we go, there will always be a natural number on the right-hand side we haven't used! We now arrive at the inevitable conclusion (a la Cantor) that sets like the integers are NOT countably infinite. The set of natural numbers must, therefore, be larger than the set of irrationals. Frederick Bryan, you are right on the mark. Cantor may have been a madman, but his followers have no excuse. —Preceding unsigned comment added by (talk) 19:01, 23 May 2008 (UTC)

Don't understand you. The present proof begins by assuming the reals are countable. switch the position of the two sets in the argument. That is, assume that the reals are "countable" makes no sense William M. Connolley (talk) 16:06, 25 May 2008 (UTC)
The present "proof" begins by asserting that some sets (viz. the natural numbers) are both countable and infinite. This is not an "assumption" which is to be proved or disproved by the argument. The "assertion set" is on the left and the "assumption set" is on the right. The two sets are then compared. —Preceding unsigned comment added by (talk) 18:24, 25 May 2008 (UTC)
The proof does *not* assert that the natural numbers are countable. As it says a proof that there are infinite sets which cannot be put into one-to-one correspondence with the infinite set of natural numbers. I'm assuming that you don't dispute that the natural numbers are infinite, so I'm not sure what you're complaining about William M. Connolley (talk) 19:42, 25 May 2008 (UTC)
Quite right. I don't dispute that the natural numbers are infinite. I dispute that they are "countable" or "countably infinite" in any meaningful way. Cantor asserts that they are but makes no attempt to prove his assertion within the diagonal argument. His "proof" concerns the "assumption set". Switching the position of the two sets immediately exposes the fallacy of the diagonal argument. —Preceding unsigned comment added by (talk) 23:02, 25 May 2008 (UTC)
You don't seem to be listening, so I'm not sure what point there is in talking. To repeat: a proof that there are infinite sets which cannot be put into one-to-one correspondence with the infinite set of natural numbers. It *doesn't* assume the integers countably infinite (although given that the defn of countably infinite is can-be-put-in-1-1-corresp-with-integers, its not much of a step) William M. Connolley (talk) 22:16, 27 May 2008 (UTC)
If you don't understand what is meant by "switching the position of the two sets" I'm not sure how to help you. The argument consists in comparing two sets (these may be called Set A and Set B) about which certain assumptions and assertions are made. Apply the assumptions and assertions made about Set A to Set B, and vice versa. Now notice that the constructed number again does not appear on the list, but his time the constructed number must be a member of Set A, not Set B. This "proves" that Set A contains elements that can not be paired with elements from Set B- the opposite of what Cantor claims. Even when the two sets are identical, the diagonal argument allows for the construction of a number not in Set A. —Preceding unsigned comment added by (talk) 13:59, 28 May 2008 (UTC)

Maybe a more appropriate article to discuss these objections could be Controversy over Cantor's theory.--Pokipsy76 (talk) 07:22, 28 May 2008 (UTC)

Cantor's Diagonal Argument as Applied to the Natural Numbers[edit]

The following excerpt is taken from Ardeshir Mehta's excellent discusion of the logical fallacies inherent in the diagonal argument.

"It is to be noted that if we adapt Cantor's proof to natural numbers, we can "prove" that natural numbers themselves cannot all be put in one-to-one correspondence with (other) natural numbers! Talk about a reductio ad absurdum.

Note that if we put all the natural numbers in the left column of a table, and then put other natural numbers in the right column, we would get the following table

Natural Numbers Other Natural Numbers
1 D1 = 0.d11 d12 d13 d14 ... d1k ...
2 D2 = 0.d21 d22 d23 d24 ... d2k ...
3 D3 = 0.d31 d32 d33 d34 ... d3k ...
4 D4 = 0.d41 d42 d43 d44 ... d4k ...
... ...
n Dn = 0.dn1 dn2 dn3 dn4 ... dnk ...

In this table, D represents any natural number, d represents any digit between 0 and 9 inclusive, the first subscript of any particular d is the natural number to which that particular d corresponds, and the second subscript of that same d is the number of places that particular d lies to the right of the starting digit of the particular D to which that particular d belongs. (When we say "starting digit" we mean the first digit one normally writes down when one begins writing the natural number in question.)

Now each row of the table represents, of course, a natural number put in one-to-one correspondence with another natural number.

Now consider the natural number X = x1 x2 x3 x4 x5 ... xk ... , where x1 is any digit other than d11; x2 is different from d22; x3 is not equal to d33; x4 is not d44; and so on. Now, X is a natural number, so it should be in our list. But where is it?

The natural number X can't be the first in the list, since the first digit of X differs from the first digit of D1. Similarly, X can't be second in the list, because X and D2 have different second-place digits; and X can't be third in the list, because X and D3 have different third-place digits. In general, X can't be the nth in the list -- i.e., it cannot be equal to Dn -- since their nth digits are not the same.

The natural number X is nowhere to be found in the list, no matter how large n gets. In other words, we have exhibited a natural number that ought to be present in a huge, humongous, giganto list -- but it isn't. No matter how we try to list the natural numbers, and how long the list gets, at least one natural number will be left out.

Therefore, using Cantor's own argument, we have "proved" that putting the natural numbers in one-to-one correspondence with the natural numbers themselves is impossible!

But this is utterly absurd, and therefore something must be terribly wrong with Cantor's so-called "proof".

(Actually, what's really absurd is the way people keep on repeating Cantor's argument, and affirming it to be a solid cast-iron proof, virtually ad nauseam, in all the high school, college and university mathematics textbooks -- and even in prestigious volumes such as those of the major Encyclopaedias. One wonders where their authors' and editors' heads are at!) --Ardeshir Mehta

Comment: Somewhere below we find the assertion that nearly 9 in 10 "working mathemeticians accept Cantorian set theory. That is not very encouraging! What if the Pythagorean theorem had this same level of support!!" Good point!! -- (talk) 18:07, 27 May 2008 (UTC)
If you're referring to what I think you're referring to, then skepticism or rejection of "Cantorian set theory" isn't because the diagonal argument is taken to be wrong, at least, not in the sense you are making it out to be. It is actually already discussed in the article ("The intepretation of Cantor's result..."), although only very briefly I'm afraid. I am as it happens sympathetic to that position, but I am not at all impressed with this particular counterargument: the constructed sequence, called X here, is not in fact a natural number, as it would consistent of an infinite number of non-zero digits, whereas natural numbers are finite (and I assume their expansion is to be padded with 0's to the right). In the original argument, the set in question is the set of infinite sequences of 0's and 1's. The constructed infinite sequence of 0's and 1's called s_0 clearly is an infinite sequence of 0's and 1's. --Unzerlegbarkeit (talk) 02:35, 28 May 2008 (UTC)

I said it at the article on the Controversy on Cantor's Theory talk and I'll repeat it here. The Ardeshir Mehta "reference" is without merit. It's not affiliated with any university, academic organisation, or noted mathematician. The single community college link it offers is broken. Oh, and it makes a number of first year mistakes, such as:

  • Claiming that the diagonally constructed decimal appears on the list after the n'th decimal. Where then, on the list? The k'th number on the list, for k even bigger? Wouldn't the k'th decimal places of these numbers differ?
  • Claiming that a single point has positive non-zero probability within the interval [0,1]. Singletons sets have zero measure. Also, there's no such thing as an ifintesimally small probibility, only zero probability.
  • Claiming that natural numbers are expressible as infinitely long strings of digits. They're arbitrarily long but *finite*; the string 222..... doesn't represent any natural number. This is the issue mentioned by Unzerlegbarkeit.

The one working link the "reference" contains goes to some other irrelevant unaffiliated personal home page, which carries its own glaring mistakes:

  • Claiming that a list contains all infinite binary strings when it's quite clearly missing 01010101.... (yet admitting that non-repeating infinite decimals are necessary).
  • Assuming that 11111111... appears somewhere on the list, when by construction the k'th number only zeros after the log_2(k)'th digit.

Gauss' incorectness can be forgiven since he died in 1855, some 20 years before Cantor published his results. Today, the reference has no value. Endomorphic (talk) 17:59, 21 August 2008 (UTC)

The Missing Link[edit]

Connolley: I wasn't aware of the convention you refer to. Sorry about that. But the question remains. Why is their no link in this article to the Controversy over Cantor's theory? —Preceding unsigned comment added by (talk) 22:22, 29 May 2008 (UTC)

Possibly just because no-one has inserted one. Maybe people didn't know about it - I didn't. Or maybe because there is a vast conspiracy to deny its existence :-)? Maybe because the article isn't very good - most of it just summarises the theory itself; the objections appear, to me, to be badly stated and near incoherent. If you need to call in Wittgenstein as a witness to maths, you're in poor shape ("your" here means the page, not you) William M. Connolley (talk) 22:27, 29 May 2008 (UTC)
OK. I'll insert a link. —Preceding unsigned comment added by (talk) 22:50, 29 May 2008 (UTC)
It's a seriously substandard article, particularly the lede. It was conceived as a piece of original research by a contributor well known to those who frequent Usenet newsgroups such as sci.math and sci.logic; it couldn't possibly stay in that form, and others have made a valiant effort to turn it into a real WP article, but no one in my opinion has really justified its existence as a separate article at all.
The problem is that there's a certain current of interested amateurs that are conflating two things. Yes, there are serious mathematicians with objections to the assumptions used in the proof, or to the usual interpretation of the result, or even to the acceptance of certain rules of logic employed by the proof; these objections do need to be represented somehow. But there are no serious mathematicians whatsoever that have the same objections typically presented by these interested amateurs (such as the claim that the same proof shows that the natural numbers are uncountable, or the claim that you can get around the result by adding the "diagonal real" back to the list). Those objections simply represent basic misunderstandings and flat logical errors. --Trovatore (talk) 22:52, 29 May 2008 (UTC)
I think you misunderstood the 'proof' (showing that the naturals numbers are uncountable). I don't think the author intended it to be taken seriously. Evidently, the author believes that the diagonal argument is incapable of demonstrating anything at all because it employs the concept of 'completed infinite sets'. The 'proof' is used to expose this implicit but unstated assumption in the argument. As you may know, this same objection was raised by Cantor's contemporary and critic, Karl Freidrich Gauss (a very serious mathematician), and by many others. "Poincaré (hardly an amateur) referred to Cantor's ideas as a grave disease" infecting the discipline of mathematics". And by the way, adding the "diagonal real" back to the list makes perfect sense if you reject the notion of 'completed infinite sets'. —Preceding unsigned comment added by (talk) 04:11, 30 May 2008 (UTC)
No, I'm sorry, I think you're wrong -- the author of that proof just flat didn't get it, and I don't think you do, either. Rejecting completed infinite sets is a respectable position (though a severely limiting one), but if you do that you just can't get started on Cantor's proof; there's nothing left to analyze. So therefore, you're wrong in your last sentence as well. --Trovatore (talk) 07:04, 30 May 2008 (UTC)
Oh, and as for Gauss, he doesn't count for chronological reasons--he died before Cantor ever published any work on set theory. It's like saying Newton rejected quantum mechanics. --Trovatore (talk) 07:07, 30 May 2008 (UTC)
Cantor was not the first to try to extend set theory to infinite sets, nor was he the first to use the notion of "completed infinites". Both ideas lead to contradictions and mathematical difficulties. Gauss's objection "I protest against the use of infinite magnitude as something completed, which is never permissible in mathematics" still stands, and I give you credit for recognizing the legitimacy of this position. If you look closely, you'll see that most of the complaints about the diagonal argument in these pages (by both amateurs and serious mathematicians) center on this issue, though not always explicitly. It is true that Cantor was the first to use the notion of "completed infinities" to prove the existence of nondenumerable sets. In may be comforting to enter "Cantor's Paradise" but I'm still an atheist.
On re-reading the excerpt from Mehta's 'natural number' proof, I think my take on it is correct. He even puts the word "prove" in quotations to emphasize the point. Seeing the excerpt in the context of the whole article makes this very plain. I believe a pritable version is available on the web. —Preceding unsigned comment added by (talk) 17:55, 30 May 2008 (UTC)
So: in one small thing you're right; Cantor was not the first person to consider infinite sets. He was just the first person to show that something of value came out of considering them (e.g. the existence of transcendental numbers). Gauss died too soon to see the fruits of Cantor's work (for that matter, so did Cantor -- the most important applications didn't really get moving until the early 20th century). Whether Gauss would have continued to reject the completed infinite, in the face of all the great mathematics that came out of it, is speculation. Certainly there are many important workers who continued to reject it; perhaps he would have been one.
But that has nothing whatsoever to do with these arguments about the same proof showing there are uncountably many naturals, or with the thing about adding the diagonal real back to the list. Those are just flat misunderstandings -- in the first case, misunderstanding of what a natural number is (can't have infinitely many nonzero digits), and in the second case, of the nature of a proof by contradiction. You will find good mathematicians that reject the completed infinite; you will not find any at all that think those two arguments are valid reasons to reject it. --Trovatore (talk) 04:44, 1 June 2008 (UTC)
Could you please give a brief overview of these applications? Why are they important? Thank you. - (talk) 13:28, 27 April 2016 (UTC)
For a minute there, I thought you understood the significance of the "completed infinite" (CI) as applied to this argument. Apparently you don't. Those who reject CI can always counter Cantor's constructed real by simply adding a new natural number to correspond with it. It's really that simple. If you don't understand that, you don't understand the issue at all. And in this context, the diagonal argument yields no contradiction (and therefore no proof) because all infinite sets have the same cardinality. These are really very elementary notions that you should understand if you are going to defend Cantor. —Preceding unsigned comment added by (talk) 22:16, 1 June 2008 (UTC)
No, you're the one who doesn't understand. Cantor's argument says "assume a completed list exists", and then derives a contradiction. If there were such a completed list, the contradiction would follow; therefore there is none. That finishes it, period. If you don't understand this then you are the one who is missing the very elementary notions.
By the way, if you believe that there are no completed infinities, then you actually agree with the conclusion of the theorem, which says that there is no such completed list. --Trovatore (talk) 22:22, 1 June 2008 (UTC)
You almost have it. Cantor says (implicitly) "assume a completed infinite list exists". Here he is talking about 'denumerable sets' like the natural numbers, NOT the real numbers! Those who reject CI stop right there, and will go no further. For them, this assumption is unwarranted, unjustified, and meaningless.
Next, (and only for those who will go farther) Cantor says (explicitly) "assume that the reals" are also denumberable. Next he says, "but if both are denumerable, why is this newly constructed real not on the list? Conclusion: one infinte set must be larger than the other infinite set.
Now the conclusion of the theorem most definitely does NOT say there are no completed infinities. Quite the opposite! It relies on their existence from the outset. But only the explicit assumption is discarded by Cantor. —Preceding unsigned comment added by (talk) 05:30, 2 June 2008 (UTC)
No, you are wrong. You will not find a single professional mathematician to agree with you on this. You will find ones who deny completed infinities, but that has nothing to do with it; your arguments are simple logical errors, plain and simple, and you cannot hijack the respectability of those mathematicians who deny the completed infinite to support these claims that have zero respectability. This is not the forum for discussing this and I should not have indulged you this long. When I get a chance I will move these non-editorial discussions to an "arguments" subpage. --Trovatore (talk) 07:30, 2 June 2008 (UTC)
It's clear from what you say that you have no idea what is meant by a 'completed infinite set'. Acceptance of CI is absolutely essential for Cantor's argument to work for the reasons stated above. You will find no respectable mathematician who accepts Cantor who does not also accept CI. Your last statement only exposes your shallow understanding of the subject. It's too bad, because if you knew what you were talking about, this article could be of value to readers. —Preceding unsigned comment added by (talk) 13:51, 2 June 2008 (UTC)

Trovatore seems to be saying that the set of all infinite sequences of 0's and 1's is not a so-called "completed infinity". I'm not sure he really meant that. But I agree that some good mathematicians reject Cantorian Heaven with its well-ordered continuum, and that none will think the arguments given against it in this section are valid. If I were a good mathematician, I would be one of these people myself.

Even if the list is not a so-called "completed infinity" you still cannot simply "add a new natural number to correspond to" the extra sequence s_0. To see this, recall that in that case, the individual entries in the list are presumably not "completed infinities" either, and presumably neither is s_0 "completed". Thus, when you extend the list, you also extend s_0, and s_0 still isn't on the list. The reason this doesn't work for natural numbers is that these really are finite. When you "extend" a natural number, it's no longer the same number. Nothing prevents a number constructed earlier from appearing later on the list. s_0, on the other hand, is "one single" sequence throughout, and can never appear on the list at any time.

You may very well wonder what it means for an indefinitely proceeding sequence like s_0 to be "one single" sequence throughout. This is fair. I think it does not matter: in whatever sense the list is "one single" list, s_0 will be "one single" sequence in the same sense. And at a minimum, you must admit such a list can be given by a some sort of fixed rule, and then s_0 will be also given by the same sort of fixed rule, and it will never appear in the list, no matter how far it is extended. So at a minimum we conclude that no sort of fixed rule of lists all, and only, the sequences of 0's and 1's given by that same sort of fixed rule. While it may not cause you to enter Cantorian Heaven, this aspect of the argument is in fact quite correct. --Unzerlegbarkeit (talk) 00:21, 2 June 2008 (UTC)

Where did I say that "the set of all infinite sequences of 0's and 1's is not a so-called 'completed infinity'"? --Trovatore (talk) 03:41, 2 June 2008 (UTC)
The article 66.67 seems to be drawing from can be found here: [1] (pulled from Talk:Controversy_over_Cantor's_theory). It's a nasty peice of work, I'm not recommending anyone try to read it (it's really that nasty), I'm just including it for completeness, since wikipedia is about references.
I'm not sure you'll be able to find any mathematician who denies that "completed infinities exist", nor that Cantor's work is valid. Want to be able to take limits? That needs infinity. Set theory? topology? measure theory? functional analysis? even basic calcules? Lots of "completed infinities" all over the place. You know what: a single decimal expansion *itself* needs "completed infinity", since it's
\lim_{n \rightarow \infty} \left( \{sum}_{i=1}^{\n} \frac{a_i}{10^i} \right)
where 'a_i' is an infinite sequence within N \cap [0,9]. Endomorphic (talk) 18:40, 21 August 2008 (UTC)

Cantor Anti-Diagonal Argument — Clarifying Determinateness and Consistency in Knowledgeful Mathematical Discourse[edit]

Perhaps my unfinished manuscript "Cantor Anti-Diagonal Argument -- Clarifying Determinateness and Consistency in Knowledgeful Mathematical Discourse" would be useful now to those interested in understanding Cantor anti-diagonal argument. I was hoping to submit it to the Bulletin of Symbolic Logic this year. Unfortunately, since 1 January 2008, I have been suffering from recurring extremely blurred vision due to frequent “exploding optical nerves” brought on by my diabetes (I can’t afford laser eye surgery) and I had only about 20 productive days in the last 8 months. At this rate, it would take me a long while to finish my paper or may not be able to complete it if I go permanently blind soon. I just hope my endeavors to clarify mathematical infinity and modern logic would reach the next (if not the present) generations of mathematicians, philosophers, and logicians. [] BenCawaling (talk) 07:55, 4 September 2008 (UTC)

Enlarging the table[edit]

And what if we now consider infinitely many rows both upwards and downwards, using only 0 and 1 and arraying them like a truth table :


Wouldn't all diagonals be included as rows ? --Michel42 (talk) 16:25, 18 October 2008 (UTC)

Cantor's diagonal argument is false[edit]

  • The number of rows is infinite.
  • No matter how many diagonal elements you collect to construct your new row, the number of elements you have collected is finite.
  • Which means there are still an infinite number of rows in the table to go.
  • Any one of which could be identical with the elements you have collected from the diagonal so far.
  • Since you can never get to the end of the table, you can never construct a row that isn't already in it.

--Vibritannia (talk) 14:42, 9 May 2009 (UTC)

I have the exact same objection to Cantor's diagonal argument. I don't disagree with its result, that integers and reals can't be mapped to each other, but I don't see the fallacy in Vibratannia's point either.Mister Mormon (talk) 00:23, 11 September 2010 (UTC)

The visualization of a list screws up a lot of peoples intuition apparently. So I rewrote the proof any a more algebraic and precise way. I use function argument instead of subscript and g will denote the s_0 in the article:

Let X be set of sequences of ones and zeros, that is X={f: N->{0,1}}, where N is the set of naturals. In that article s is an arbitrary map from the naturals into X, that is

s: N->X.

Cantor asserts that s is not surjective, which means there is a sequence g in X such that for any natural n we have


To see this define g as


Now if g was in the range of s, then there would be a natural m such that


But consider the mth term of both sequences. By definition


on he other side


Their equality would imply s(m)(m)=0.5, which is impossible. So g and s(m) differ at the mth term. Therefore g!=s(m) for any m, thus s is not surjective. QED Scineram (talk) 09:57, 30 October 2009 (UTC)

proof or illusion?[edit]

A statement from 'Cantor's diagonal argument:

1. "Therefore this new sequence s' is distinct from all the sequences in the list".

It should say "is distinct from all the sequences in the sample list". There is no logical reasoning from 'some' to 'all'. You can't reach a conclusion for all, based on a comparison of some. For example, a doctor can't state with certainty that 100 people don't have disease A, based on examination of 10 from that group. Since the truth of statement 1 depends on the comparison of all sequences, it is based on information not available, i.e. speculation. The problem with isolated experiments is the denial of information that would assist in making an accurate conclusion. If the list L is ordered, and divided into two subsets, L0, all sequences beginning with '0', and L1, all sequences beginning with '1', the first comparison and symbol swap would exclude the subset L0, and it is only necessary to compare s' to a member of the subsets L10 and L11 for the next position. The process becomes more efficient by eliminating redundant comparisons. A simple pattern emerges with the choice for each position always the same, '0' or '1'. If s' is compared to a member of one subset, its symbol swap will place it in the complementary subset. Continuing with any arbitrary 7-symbol sequence, the next comparison would be with one of the following subsets, each containing an unlimited number of sequences not compared, that match s' to the current position.

L10111010={10111010...} (all sequences beginning with s' and appended with 0)

L10111011={10111011...} (all sequences beginning with s' and appended with 1)

conclusion: It's obvious that no matter which choice, there is an existing sequence matching s'. The refined process is equivalent to forming any sequence. The original process is not forming a 'new' sequence, it's just copying an existing one. Assuming a complete list, 10111... and 11111... differ in one position and 010101... and 101010... differ in all positions. If each sequence is unique, then each must differ from all others in at least one position. The fact of being different does not imply exclusion. Assuming in principle, if one complete sequence can be formed, then all possible sequences can be formed and presented as a complete ordered list L, otherwise there is no list. In either case the diagonal proof fails. The diagonal and partial list are instances of misdirection. Phyti (talk) 18:59, 21 March 2013 (UTC)

The sequence s' isn't being compared to 'some' of the sequences in the list, it's being compared to ALL of the sequences in the list. Your 'refined process' merely divides your list into several sub-lists. s' is not in any of these sub-lists because s' isn't in their union (the original list). Gazzawhite (talk) 02:20, 13 November 2013 (UTC)

You missed the part where the ordering of subsets eliminates redundant comparisons, and accounts for all possible combinations of 0 and 1. We could also just admit that even one infinite sequence cannot be constructed, and therefore no list. On a more fundamental level, no human can conceptualize infinity, since there is no related experience. To model it using finite entities doesn't work. Even if humans became immortal, they still have a beginning. Phyti (talk) 20:26, 14 February 2014 (UTC)

The ordering of the subsets (to "eliminate redundant comparisons", whatever that means) is irrelevant. If s' isn't in L, then it can't be in the subsets. Your change of format from a list to a collection of subsets does not prove that s' is in L any more so than our original assumption that L contains all binary sequences (and thus contains s'). Thus the contradiction is still there. Gazzawhite (talk) 04:52, 1 July 2014 (UTC)

Moved from talk:continuum hypothesis[edit]

Heading was "Proposed things to add"

Note: A one-to-one correlation between the set of all natural numbers and all real numbers between zero and one, exclusive, can be conceived of. Each integer would pair with the real number obtained by flipping all of its digits across the decimal point. For example, 5.0 would coincide with 0.5, 27.000 would coincide with 000.72, and 271828182845904.00000000 would coincide with 00000000.409548281828172. Two arguments against this are that the correlation is not consistent between bases. While that is correct, and while 0.125 coincides with 521 in base ten, 0.125 in base twelve would coincide with 73 in base twelve, the existence of a correlation between the two sets is constant throughout all bases. The other argument against it is that recurring and irrational decimals (like 1/3 and e-2) would coincide with integers with infinitely many digits. However, a number can be infinitely large and still be an integer. Despite the presence of a counterargument against both arguments against this one-to-one correlation, the validity of this correlation is still controversial.

If the correlation is valid, then it would make the amount of all real numbers aleph-nought, making the Countinuum Hypothesis meaningless. — Preceding unsigned comment added by (talk) 04:49, 9 February 2016 (UTC)

What do you mean by "a number can be infinitely high and still be an integer"? You must have a meaning of "integer" in mind which is very different from the meaning generally accepted by mathematicians. More important, however, is that your extended concept of "integers" does not have cardinality aleph zero, which destroys the whole point of your suggestion. The editor who uses the pseudonym "JamesBWatson" (talk) 16:00, 9 February 2016 (UTC)

High meant large, and I fixed that. Let me explain what I mean to you. Graham's Number has a ton of digits, and it's still an integer. My definition of an integer is a number that has no non-zero digits after the decimal point. It can have as many non-zero digits as it wants, even an infinite amount, before the decimal point, as long as it doesn't have any after. Also both the set of natural numbers and the set of integers have cardinality zero.

Wrong question[edit]

Folks, you're all asking the wrong question. The wrong question is: can every real number be enumerated? This question is too specific, it lacks generality, and detail. The real question is: is the situation conceivable, in which the creation of the set of all natural numbers has come to its end, the creation of the set of all real numbers has come to its end, the creation of all transitions from one natural number in the first set to one real number in the second set has come to its end, and no real number exists, such that it has no transition pointing to it from some natural number? Cantor says: no, one cannot conceive such situation, and here's why… Of course, one can argue that such situation is not conceivable simply because the completion of the set of all natural numbers is not conceivable, but that's another story, to which the argument does not apply. Sure, one needs to have finished the building actions about a set before saying it has the same cardinality as anything else. - (talk) 23:07, 26 April 2016 (UTC)

I think I can add some more to it.
Let's just ask ourselves the question: what is the difference between finite and infinite sets? The difference is, we can conceive of every object in a finite set at the same time, while the same is not true of an infinite set. That ability of ours has consequences for all procedures of enumeration, as enumeration over only a finite set has a limitation: it only can find objects that can all be known and constructed beforehand. But one can freely get used to the idea that it does not matter whether this simultaneous conception of all objects in a set is possible. A set is good enough without that possibility, because what is substantial for a set is the kind of argument that we can do with whatever element in this set. The principle goes, what is true for an arbitrary number in the set is true for every number in it.
So, what do we have? For a digital string whose digits are constructed in a certain way, it is true for an arbitrary string in the set of digital strings, on the condition that the string is put into a correspondence with a number in the set of integers, that that string is different than the string whose digits we can construct, because of the way those digits are constructed. Since it is true for an arbitrary string, it is true for every string that satisfies this condition. Therefore, the string that is different than all of them exists, and it satisfies all conditions that any member of the set of digital strings has to satisfy; that is, the set contains that string. It is not required that we actually construct all digits in the string; suffices that we may do so, because, again, what is true for an arbitrary digit in this string is true for all digits in the string.
Sure, the construction and rememberance is possible only for a finite number of objects. But for a set, the rememberance of all objects is simply not necessary: it is just the same whether it is or is not allowed. I think there are sets for which it is not even known (as of yet) whether they are finite or (actually) infinite. - (talk) 11:55, 24 November 2016 (UTC)

Set theory isn't real[edit]

Suppose you construct the sets like this:

0000...  (All zeros)
1000...  (1, then zeroes)
1100...  (11, then zeroes)
1110...  (111, then zeroes)

And so on. The 1s form a triangle. The diagonal pattern is the complement of a sequence of zeroes, so it's all 1s. Do we really believe that this triangle sequence, with a continuing number of 1s, is different from a constructed sequence that, so far, happens to be entirely 1s? (talk) 04:14, 16 August 2017 (UTC)

This question somehow resembles the one asked in the section #not a convincing argument above (although it's obviously not the same). --CiaPan (talk) 09:07, 16 August 2017 (UTC)
The diagonal is an infinite sequence of zeros, so the constructed pattern is an infinite sequence of ones. However, none of the rows used in the construction is built of ones only. Please note that if one was, it would introduce a '1' into the diagonal, which by design contains zeros only!
So the answer is:
YES, the resulting sequence of ones does NOT appear in the list of sequences used in the construction.
--CiaPan (talk) 13:29, 17 August 2017 (UTC)