Talk:Cantor's diagonal argument

From Wikipedia, the free encyclopedia

Archive of old discussion: May 2002 — May 2004

1 Other, "Rational" Cantor diagonalizations
2 Would be Amusing
3 A SUGGESTION AND COMMENTS
4 If anyone's still reading this talk page
5 Why this does not work on integers
6 Yeah this just keeps going.
7 BC's stuff
8 Yet another rant
9 rm: POSSIBLE COUNTERARGUMENTS
10 why not just use an open interval?
11 ... or consider the number of generators (re infinite sets)
12 clarification re the proof of Cantor's theorem in New Foundations
13 NEW PROOF:
14 A word of caution
15 A Small Suggestion
16 Exact date of publication?
17 the NF argument
18 Self-contradiction in “proof by contradiction”
19 Self-contradiction in one-to-one correspondence (About the incomplete totality of the set of all prime natural numbers)
20 Intention of Cantor's Diagonal Argument
21 A layperson's objection to Cantor's proof
22 MY 2 cents
23 Further Musings of a Layperson on Cantor's Proof

[edit] Other, "Rational" Cantor diagonalizations

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)

[edit] Would be Amusing

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.

[edit] A SUGGESTION AND COMMENTS

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.

[edit] If anyone's still reading this talk page

biedermann@clix.pt 23.9.05

I'm wondering whether we shouldn't outline (and refute) some of the counterarguments that have been made here (the ones that actually illustrate useful mathematical ideas, that is) in the article itself in a section called, for example, Possible counterarguments (one subsection of which would be the current Why this does not work on integers section). In particular, the article should probably explicitly state why this argument doesn't depend on the Axiom of Choice, and why the argument depends not on an infinity of infinite steps, but only an infinite number of steps (i.e., if one were to "completely" determine x). Assuming I'm correct on both counts, of course. - dcljr (talk) 13:51, 2 Jun 2005 (UTC)

[edit] Why this does not work on integers

Not to offend the author, but this section seems a bit half-assed. I'm not sure how to improve it though, any ideas? Autodeist 18:15, 23 Jun 2005 (UTC)

Can you be more specific about what you think is wrong with this section? Paul August ☎ 18:41, Jun 23, 2005 (UTC)

Speaking as the person who wrote that section, based upon the number of times that people *do* think the argument applies to the integers... I'm happy to hear criticism but it has to be more precise. I say that that section is (a) concise and (b) accurate and (c) complete. If it isn't also clear, what is unclear? William M. Connolley 21:02, 23 Jun 2005 (UTC).

Of course. "The trouble is that an infinite sequence of non-zero digits does not represent an integer." I am not a mathematician, just someone interested, but I didn't see why this was true (although I can sort of guess why). Also, I wouldn't have called it "half-assed" if I weren't in a very angry mood...sorry.

OK, fair enough. Firstly, an infinite sequence of digits behind a decimal point *is* a real number, because 0.abcdefgh... converges because a/10+b/100+c/1000+d/10000+... converges. So then consider the infinite string "abcdefgh..." or (to make the argument easier) the string "...gfedcba". This latter does *not* represent a number because a+10*b+100*c+1000*d+... does *not* converge (unless all the digits are zero beyond some point). Is that any better? It really is worth trying to explain this clearly because people do make this same mistake frequently. William M. Connolley 22:08, 25 Jun 2005 (UTC).

Hmm. Lemme try a different approach. Do you agree that any proposed "integer" (in standard form, not allowing unnecessary leading zeros) with an infinite number of digits is automatically greater than any integer you can specify? (dcljr)

No. An infinite string of non-zero digits is not a very large integer, its not an integer at all. William M. Connolley 2005-07-03 19:45:49 (UTC).

Yes, that's why I put it in quotes. Perhaps you misunderstood my intention... - dcljr (talk) 4 July 2005 11:59 (UTC)

(I'm restricting my attention to positive integers, or natural numbers if you prefer; a similar argument works for negatives.) For example, it would be greater than 1,000,000,000,000,000 or indeed any other number you can choose. Well, something that's greater than any integer cannot itself be an integer (dcljr)

Yes. Except, of course, since its not an integer it can't be "greater" than any of them. William M. Connolley 2005-07-03 19:45:49 (UTC).

Except infinity is greater than any integer! - dcljr (talk) 4 July 2005 11:59 (UTC)

Depends on which system you're working in. In most number systems, infinity doesn't exist, so is neither greater than or less than anything. In the (std) integers, it doesn't exist. William M. Connolley 2005-07-04 12:49:46 (UTC).

(if you don't buy this argument, consider that one axiom of the natural numbers is that every natural number is followed by a successor, which can be taken to be that number plus one — hence for any natural number, there must be a greater natural number). In fact, something that's greater than any integer is usually called infinity. And infinity is not an integer. How's that for an argument? - dcljr (talk) 2 July 2005 01:15 (UTC)

Its a naiv-ist view. In essence, it doesn't work. You just can't say "if it was an integer, it would be bigger than any, so in that case its not an integer". You *can* formalise it in the way I tried to, via sequences. William M. Connolley 2005-07-03 19:45:49 (UTC).

It may be "naiv-ist", but that was kinda the point. I was trying to give an easily understood argument for people who don't know anything about infinite series. FWIW, I don't believe there's anything actually wrong with my argument. So nyaa. :-) - dcljr (talk) 4 July 2005 11:59 (UTC)

And before you reply again, WMC, let me be more precise: my "proposed 'integer'" and your (divergent) series are exactly the same thing. My "greater than any integer" and your "does *not* converge" (actually, diverges to infinity) are exactly the same thing. Your argument and mine are exactly the same thing, I just tried to avoid unnecessay mathematical rigor because I was talking to a less mathematically-inclined audience. - dcljr (talk) 4 July 2005 12:17 (UTC)

"The trouble is that an infinite sequence of non-zero digits does not represent an integer." I am not a mathematician, just someone interested, but I didn't see why this was true

Because every integer is finite. Michael Hardy 2 July 2005 02:07 (UTC)

Hello there! Unless this discussion is dead I'd like to join it. I've read the thread and I've noticed that you often don't understand each other due to lack of precise definitions of used terms. I'm a matematician, so I could probably help clear some things. I'd start with (in)finite numbers. In reference to "every integer is finite": What do you mean by finite? Do you suggest that some numbers are infinite? Which ones? Misza13 13:13:48, 2005-07-24 (UTC)

Feel free to join in. Many here are mathematicians too. "What do you mean by finite" is an odd question (certainly in the context of the integers) to me William M. Connolley 13:28:27, 2005-07-24 (UTC).

I know it's odd - that's why I asked it. Furthermore, "being (in)finite" has no sense even in the context of all real numbers. Most people would say reals are finite because they are less than $\infty$ . But here's the catch: " $\infty$ " is not a real number (just an abstract mathematical symbol), though together with " $-\infty$ " it is used to enclose the set of reals. Other would categorize reals depending on their expansions' length. This is wrong from 2 reasons:

* The (in)finity of a numbers' expansion length may depend on the radix (base) of representation.

* See a general note on digits below.

The only place where we can say about (in)finite numbers are cardinal numbers which measure the power of a set. {0,1,2,3,...} are finite cardinal numbers and the others are infinite (and there's an awful lot of different infinities). Another note: do not confuse cardinals with naturals just because they look the same - the axioms don't say a word about about digits - theoretically we could have a unique symbol for each number (actually that's the way it is but they are composed from a set of digits). Very good definitions are in Natural number#Formal definitions.

Hopefully this bunch of chaotic thoughts clears out anything for those who still have troubles understanding infinity and the Cantor's diagonal. Misza13 14:39:04, 2005-07-24 (UTC)

[edit] Yeah this just keeps going.

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)

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.

[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 $\infty$ -th (infinieth? ;-) digit of

a ω

then you're in trouble, 'cause

a ω

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

L = (a 1, a 2, a 3,...)

corresponds to

ω

and

L * = (a 1, a 2, a 3,..., a ω)

corresponds to

ω + 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

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

a ω

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 $L^*=\bigcup_{i=1}^\infty\{a_i\}\cup\{a_\omega\}$ with the order $a_i<a_j\iff i<j$ where i,j are ordinals corresponds to the ordinal

ω + 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: $L=\bigcup_{i=1}^\infty\{a_i\}:=\{x:\exists_i x=a_i\}$ .

The expression $(((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

a ω

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 ): $\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)

[edit] 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 ... (([BenCawaling@Yahoo.com (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. [BenCawaling@Yahoo.com (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.

[BenCawaling@Yahoo.com (13 Sep 2005)]

[edit] Yet another rant

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

[edit] rm: POSSIBLE COUNTERARGUMENTS

I've removed the new section by the anon. It started:

All the difficulties with Cantors Diagonal Method, as demonstrated by the lengthy discussion in the talk section,

First of all, you cannot refer to a talk page in an article page. Secondly, please read the stuff at the very top of this page. You cannot get away with adding flat-earth arguments to the shape-of-the-earth article; you cannot get away with adding your own personal pet dislike of the diagonal argument to this article page. You couldn't do it even if it was well writtem. William M. Connolley 12:19, 30 September 2005 (UTC).

[edit] why not just use an open interval?

This is slightly awkward to do, though possible, for the closed interval [0,1];

Then why not just use an open interval in step 1? -Grick(^{talk to me!}) 08:51, 14 October 2005 (UTC)

[edit] ... 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

[edit] clarification re the proof of Cantor's theorem in New Foundations

The comprehension axiom of New Foundations is not a version of the separation axiom; both are versions of the naive axiom of comprehension. I added a brief indication of what does work in New Foundations.

Randall Holmes 17:40, 15 December 2005 (UTC)

It's a little off-topic, but I disagree with the claim (assuming that's what you meant) that the separation axiom is a version of naive comprehension. We don't motivate separation by claiming first that every property should have an extension, and then cutting back to avoid Russell's paradox. Rather, separation is to be understood in the context of the cumulative hierarchy; the motivation is that, since every subset of a given set appears at the next level above the level where that set appears, then in particular all its definable subsets must appear. There's nothing really special about the definable ones; you get them by choosing subsets "lawlessly" and then finding out that, just by accident, you picked all and only the elements that satisfy some formula. --Trovatore 06:07, 20 December 2005 (UTC)

I won't dispute that separation is not a variation of naive comprehension, as long as it is granted that stratified comprehension is not a variation of separation (which is what the page said originally)! But many do understand both principles as variants of naive comprehension... I have further argued elsewhere that stratified comprehension doesn't really have to be understood as a variant of the inconsistent naive comprehension either... Randall Holmes 20:18, 20 December 2005 (UTC)

[edit] NEW PROOF:

Consider a base-12 number system with / as the symbol for the digit 10 and – as the symbol for 11. Define the map φ: Q→N(12) (natural numbers base-12) by φ(a/b)=a/b, where on the left-hand side, a/b is the lowest terms representation of a typical element Q and on the right-hand side, a/b mean the base-12 number consisting of the digits of a (possibly preceded by a minus sign - ) followed by the division slash / and then the digits of b.

For example, φ(-5/12) = -5/12. Let σ: N(12)→N be the obvious injection converting a number from base-12 to base-10. Continuing our example, this means: σ (-5/12) = 11 ٠ 124 + 5 ٠ 123 + 10 ٠ 122 + 1 ٠ 121 + 2 ٠ 120 = 238,190

Then σ ○ φ: Q→N is an injection, where by |Q| ≤ |N|. Inclusion provides the reverse inequality and we conclude |Q| = |N|.

This method of enumerating sets certainly does not displace Cantor’s classic technique, but it does show another, more concrete way to accomplish the task. Though we applies it only to Q, the method presented here can, in theory, be used to count any set X, such that N ≤ X (so we may apply inclusion) for which a sufficiently clever function from X into N(n) for some base-n can be found.

I am not the author of the preceding. I separated this into a new section because it has nothing to do with what precedes it. I must note that it also has little to do with the topic under discussion (nor, I think is it new). Randall Holmes 15:26, 30 December 2005 (UTC)

It says:

σ (-5/12) = 11 ٠ 124 + 5 ٠ 123 + 10 ٠ 122 + 1 ٠ 121 + 2 ٠ 120.

It must have been intended to be

σ (-5/12) = 11 ٠ 12⁴ + 5 ٠ 12³ + 10 ٠ 12² + 1 ٠ 12¹ + 2 ٠ 12⁰.

Michael Hardy 00:53, 2 January 2006 (UTC)

[edit] A word of caution

I think that this discussion makes it clear that Cantor´s proof is not agreed about. In the beginning of the section, it should be said something like:

"The proof is still controversing, an not all agree that it´s right" This is so that readers know that this not an absolute fact.

The real numbers [0, 1) are countable with this bijection:

0 = 0,000... , 1 = 0,100... , 2 = 0,200... , 3 = 0,300... , ... , 10 = 0,0100... , 11 = 0,1100.... , ... , 4328 = 0,823400... , .... , (one-third is): ...333 = 0,333...

If we use the diagonal proof on this list, we found that 0,111... are not in the list, but it is obvios why, because the diagonal list grows in a much faster rate than the ordering.

No, this is not the case. Cantor's proof is universally agreed to be valid by mainstream mathematicians. The controversy here is an illusion. Randall Holmes 16:40, 12 January 2006 (UTC)

Many people don't understand how the Monty Hall problem works, ergo there must be "controversy" about it! - 216.61.33.187 23:52, 18 May 2006 (UTC)

Further, there are respectable mathematical objections to the proof made by predicativist or constructivist mathematicians of various stripes, but it is not my impression that any of these potentially legitimate objections are described in this page. Randall Holmes 16:42, 12 January 2006 (UTC)

"(It proves) that the real numbers are not countably infinite." I can't see a constructive objection. I might have one if it said there are more real numbers. -Dan 17:05, 12 January 2006 (UTC)

On a closer look, I see that the last section has this problem. It asserts that P(S) is bigger than S, and a bit later that there are more real numbers than integers. This is not a big deal, and I suppose sometime when someone is feeling pedantic, they might go in and qualify that.

One shouldn't "qualify" the statement as to what the classical result is -- but some indication of what the constructive theorem would be could be of interest -- maybe in a separate section. Randall Holmes 18:06, 17 January 2006 (UTC)

Now at the end of the first section, there is some handwaving between (0,1) and [0,1]. This is potentially more serious, because this is what gets us to the uncountability of all real numbers. I'm not quite sure what to do about it. Any ideas? -Dan 16:21, 16 January 2006 (UTC)

It isn't handwaving -- these sets are equinumerous classically. But they might not be, constructively... Randall Holmes 18:06, 17 January 2006 (UTC)

They aren't, and we can raise another objection about decimal expansions. The issue is "potentially more serious" because, unless someone sees a simple modification, it will change how the proof is presented. The size-of-sets business, on the other hand, just weakens the conclusion from "R is bigger than N" to "R is not the same size as N", without changing the proof.

But let me be clear: in the end, there is no bijection between N and R, even if we mention constructivism. My feeling, before it was mentioned, was that I didn't want to wander around a bunch of pages scribbling "non-constructive" all over them where it didn't make much difference. -Dan 19:26, 17 January 2006 (UTC)

[edit] A Small Suggestion

The present proof seems nice. The author might want to point out specifically that in choosing .4999... over .500... he is giving each number in [0,1] a unique infinite decimal representation. Thus later he can claim if two numbers differ at at least one decimal place then they are different numbers--so the constructed number is not on the list. He might also want to point out that since each digit of the constructed number is 4 or 5 the constructed number is one of the uniquely represented numbers (for example .5000... would not so qualify).

[edit] Exact date of publication?

I was wondering what the exact date of publication is. The information on this page is contradictory: in the header the year 1874+3 = 1877 is mentioned, at the bottom of the page there is a link to a German publication from 1891. Who can clear this up? - Zwaardmeester 14:59, 16 Jan 2006 (UTC+1)

the result that there are more reals than integers is older than the result that P(S) is bigger than S. The latter result is 1891. Randall Holmes 17:59, 17 January 2006 (UTC)

This page is pretty vague about dates. Shouldn't we do anything about it? Thanks for helping btw. zwaardmeester 20:38, 18 Jan 2006 (UTC+1)

[edit] the NF argument

I scrambled it seriously when I wrote it the first time; it's correct now! Randall Holmes 20:43, 31 January 2006 (UTC)

[edit] 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”. [BenCawaling@Yahoo.com --- 10 February 2006]

[edit] Self-contradiction in one-to-one correspondence (About the incomplete totality of the set of all prime natural numbers)

Essay moved to User:BenCawaling/Essay. Gandalf61 08:30, 14 April 2006 (UTC)

[edit] Intention of Cantor's Diagonal Argument

While Cantor's diagonal argument was not formalized origionally, nowhere else have I seen it assume decimal expansion (step 3). In fact, the link of the 1891 proof says that does not depend on considering irrational numbers. It furthermore does not use decimal expansion. It seems to me that assuming decimal expansion means assuming cantor's argument before proving it - as this step considers irrational numbers. If Cantor's argument does not depend on considering irrational numbers, then it would follow that if there hypothetically was an alphabet with no irrational numbers that represented all real numbers, that the origional argument would demonstrate this set uncountable. If I'm right there, then why does the argument presented use decimal expansion in the proof? —The preceding unsigned comment was added by Dr cayenne (talk • contribs) 12:06, 17 April 2006 (UTC)

I'm afraid I'm having a little trouble following your question; what do you mean by "considering" irrational numbers? There are only countably many rational numbers, so if you leave out the irrationals, of course the proof must fail.

The link you mention is not directly talking about real numbers at all. What it shows is that there are uncountably many infinite strings of characters, each of which has two possibilities (say, heads and tails, so such a string might be HTHHHTHTTTHTHHTHTHHHTHT...). This differs from the argument as applied to real numbers only in fairly inessential detail. --Trovatore 18:46, 17 April 2006 (UTC)

To make a parallel, to me it feels like the article is using multiplication in a proof of addition. That or the link is mislabeled. —The preceding unsigned comment was added by Dr cayenne (talk • contribs) 23:18, 17 April 2006 (UTC)

Please sign your comments on talk pages with four tildes: ~~~~.

The proofs are really the same. Figuring out why they're the same would be a good self-test of comprehension. All the same, it is possible you've identified a point on which the article's clarity could be improved. --Trovatore 23:27, 17 April 2006 (UTC)

After comparing them, I clarified the proof some. While I agree entirely with Cantor's diagonal argument, I am suspect to the assumption that all numeral systems of real numbers are comprable to decimal expansions.Dr cayenne 18:59, 19 April 2006 (UTC)

First, let me say I really don't want to sacrifice accessibility, so my feeling is that we should leave the proof alone. But I did allude to something along these lines a few months ago. Consider $r = \begin{cases} 1/2 + 2^{-n-1}, & \mbox{if }n\mbox{ is the smallest natural number such that }\phi(n) \\ 1/2, & \mbox{if there is no }n\mbox{ such that }\phi(n) \end{cases}$ ,

and phi(n) is the proposition that, for instance, 2n+4 is the sum of two primes. This really is a real number in the interval [0,1], since we can write the Cauchy sequence $r_m = \begin{cases} 1/2 + 2^{-n-1}, & \mbox{if }n \le m\mbox{ and }n\mbox{ is the smallest natural number such that }\phi(n) \\ 1/2, & \mbox{if there is no }n \le m\mbox{ such that }\phi(n) \end{cases}$ .

But when you get to step 3 in the proof, you can't decide between 0.4999... and 0.5000.... -Dan 14:57, 28 April 2006 (UTC)

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

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)

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)

[edit] MY 2 cents

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)

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:BenCawaling@Yahoo.com|BenCawaling]] 03:23, 25 May 2006 (UTC)

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

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)

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)

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)

Retrieved from "http://en.wikipedia.org../../../c/a/n/Talk%7ECantor%27s_diagonal_argument_016f.html"