Talk:Cantor's diagonal argument/Arguments

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.

Simple disproof

Latest comment: 17 years ago2 comments2 people in discussion

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)Reply

• 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.69.114.83.91 (talk) 05:49, 11 March 2008 (UTC)Reply

Other, "Rational" Cantor diagonalizations

Latest comment: 19 years ago1 comment1 person in discussion

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 indefinability of truth, Curry's paradox (and Russell's paradox for that matter). Randall Holmes 21:17, 19 December 2005 (UTC)Reply

Would be Amusing

Latest comment: 19 years ago1 comment1 person in discussion

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)Reply

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

A SUGGESTION AND COMMENTS

Latest comment: 17 years ago1 comment1 person in discussion

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 66.67.96.142 (talk) 18:34, 25 May 2008 (UTC)Reply

Yeah this just keeps going.

Latest comment: 19 years ago4 comments2 people in discussion

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.

[apoorv1]

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)Reply

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)Reply

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.

[Apoorv1]

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 ${\displaystyle \infty }$ -th (infinieth? ;-) digit of ${\displaystyle a_{\omega }}$  then you're in trouble, 'cause ${\displaystyle a_{\omega }}$  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 ${\displaystyle L=(a_{1},a_{2},a_{3},...)}$  corresponds to ${\displaystyle \omega }$  and ${\displaystyle L*=(a_{1},a_{2},a_{3},...,a_{\omega })}$  corresponds to ${\displaystyle \omega +1}$  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,a2...aw}.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 ${\displaystyle a_{1},a_{2},a_{3}}$  and so on to it. But it will never cease doing so and thus will never arrive at the step "push ${\displaystyle a_{\omega }}$  to the set". You used the words "As you count ${\displaystyle \omega }$ ..." but here's the catch - the ordinal numbers are uncountable! Every finite ordinal will be counted, but ${\displaystyle \omega }$  will not. A side note: the set ${\displaystyle L^{*}=\bigcup _{i=1}^{\infty }\{a_{i}\}\cup \{a_{\omega }\}}$  with the order ${\displaystyle a_{i}<a_{j}\iff i<j}$  where i,j are ordinals corresponds to the ordinal ${\displaystyle \omega +1}$ . 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: ${\displaystyle L=\bigcup _{i=1}^{\infty }\{a_{i}\}:=\{x:\exists _{i}x=a_{i}\}}$ .

The expression ${\displaystyle (((a_{1}\cup a_{2})\cup a_{3})\cup a_{4})\ldots }$  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 ${\displaystyle a_{\omega }}$  because all the previous ones will take you literally eternity to add. Misza13 10:27, 13 September 2005 (UTC)Reply

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 ): ${\displaystyle \sum _{i=1}^{\infty }{\frac {1}{2^{n}}}=1={\frac {1}{2}}+{\frac {1}{4}}+{\frac {1}{8}}+\ldots }$ 

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)Reply

BC's stuff

[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 ... (([[e-mail] (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. [[e-mail] (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.

[[e-mail] (13 Sep 2005)]

Yet another rant

Latest comment: 19 years ago8 comments3 people in discussion

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:Reply

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 --195.23.195.43 09:56, 28 September 2005 (UTC)Reply

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)]Reply

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).Reply
• 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)Reply

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).Reply

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

• 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)Reply

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

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 - http://home.iae.nl/users/benschop/cantor.htm

http://home.iae.nl/users/benschop/ism.htm

http://home.iae.nl/users/benschop/func.htm

Nico Benschop 13-dec-2005

Self-contradiction in “proof by contradiction”

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”. [[e-mail] --- 10 February 2006]

A layperson's objection to Cantor's proof

Latest comment: 17 years ago3 comments3 people in discussion

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

69.209.148.136 01:10, 24 May 2006 (UTC)Reply

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)Reply

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)Reply

MY 2 cents

Latest comment: 19 years ago1 comment1 person in discussion

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 69.209.148.136 00:34, 25 May 2006 (UTC)Reply

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.[User:[e-mail]|BenCawaling]] 03:23, 25 May 2006 (UTC)

Further Musings of a Layperson on Cantor's Proof

Latest comment: 19 years ago6 comments3 people in discussion

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 69.209.131.123 23:36, 25 May 2006 (UTC)Reply

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 69.209.131.123 07:23, 26 May 2006 (UTC)Reply

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)Reply

(Oh, BTW, "you" means "Steve" more than "Dan", but Dan does seem to be enabling here....) --Trovatore 15:27, 26 May 2006 (UTC)Reply

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)Reply

---

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)Reply