Talk:Cantor's diagonal argument

Archive of old discussion: May 2002 — May 2004

This is the talk page for discussing changes to the Cantor's diagonal argument ARTICLE. Please place discussions on the underlying mathematical issues on the Arguments page. Non-editorial comments on this talk page may be removed by other editors.
Please sign your comments using four tildes (~~~~). Place comments that start a new topic at the bottom of the page and give them == A Descriptive Header ==. If you're new to Wikipedia, please see Welcome to Wikipedia and frequently asked questions.	Talk page guidelines Please respect Etiquette, assume good faith and be nice.

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)

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

I think an explanation of this point would certainly help. I've spent some time this evening trying to work out how to get from s₀ being both in and not in T to the conclusion that T is not countable. It seems to revolve around the idea that a list of s_n can be constructed using the method Cantor describes but that a list of natural numbers cannot. If this is a correct assumption on my part then some words to explain this would be very useful. But the only way I can see such a construction of an infinite list of natural numbers being impossible is if an infinite string of digits does indeed not represent an integer. This brings two questions to mind for a non-mathematician such as myself. 1) "Why does such an infinite string of digits not represent an integer?" (I think you've answered this with your discussion of convergence above) and 2) "What does it represent if not an integer?" EntropyWrangler (talk) 01:16, 21 January 2008 (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)

Before people go off into tangents (and the real reason that Connolley viewed this as naivist). Integers are a very standard set constructed in a very standard way. You can't add crazy new elements to the set and except them to remain a viable group under addition (or that the positive ones form a group under multiplication) or that distributivity or associativity or commutativity or any of the familiar rules hold. What dclr used is an axiom of Peano which still doesn't contradict the subsetness of naturals within integers. Moreover, there are sets which are considered to be "extensions" of naturals. Consider naturals to be the set of finite ordinals, then the first uncountable ordinal is certainly said to be as a linear order greater than all the remaining ordinals. And therefore only finite ordinals are taken to be naturals. There is nothing wrong with non-specialists asking questions, but the non-specialists should understand that some questions are really not very interesting (therefore might not garner much attention). 76.181.242.239 (talk) 19:10, 1 January 2011 (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)

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

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)

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)

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)

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)

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

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)

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)

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)

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)

Constructivist interpretations

The late User:Futonchild added a problematic section which I tried to shape into something that was at least meaningful, but frankly it's still problematic. It goes like this at present:

The interpretation of Cantor's result will depend upon one's view of mathematics, and more specifically on how one thinks of mathematical functions. In the context of classical mathematics, functions need not be computable, and hence the diagonal argument establishes that, there are more infinite sequences of ones and zeros than there are natural numbers. To those constructivists who countenance only computable functions, Cantor's proof (merely) shows that there is no recursively enumerable set of indices (for example, Gödel numbers) for the programs computing them.

Now, I think it is true that constructivists, or at least some of them, do not accept the "quantity" interpretation of the argument. It seems to me, though, that to deny the quantity interpretation, they're pretty much obliged by the argument to deny that the sequences of zeroes and ones can be collected into a completed totality. They are not really saying, that is, that there are only as many sequences of zeroes and ones as there are natural numbers, even if the only sequences they accept are the computable ones, because for coherency's sake the only enumeration of sequences they could accept is a computable one (say, a computable enumeration of Turing machines that produce total sequences, or a global computable function giving the nth bit of the mth sequence), and Cantor's argument (which by the way is intuitionistically valid) excludes that possibility. (I don't know any intuitionistic proof, on the other hand, that there's no injection from the sequences into the naturals; it's conceivable that some intuitionists believe that the existence of such an injection is "not false".)

Anyway, I think the current text is unsatisfactory, but I don't want to just delete it out of hand; there probably are constructivist interpretations that deny the proof is about "quantity", and they should be fairly represented. Can anyone help out here, especially with versions that might be attributed to specific constructivist/intuitionist thinkers? --Trovatore 07:00, 14 March 2007 (UTC)

Your parenthetical remark about injections is close. I'm not sure but I think your proposed injection is still inconsistent, on the other hand it is quite consistent to assert a partial surjection from the naturals to the infinite bit sequences, i.e. that the infinite bit sequences are subcountable. Clearly this contradicts the "quantity interpretation" because although the naturals and infinite bit sequences are not in bijection, each one can be seen as a partial image of the other. Now pardon me while I fix this redlink. --99.234.59.230 (talk) 03:34, 4 January 2008 (UTC)

Dates?

Beginning of article:

• Cantor's diagonal argument, [...] was published in 1891 by Georg Cantor

Next paragraph:

• The diagonal argument was not Cantor's first proof of the uncountability of the real numbers; it was actually published three years after his first proof, which appears in 1874.

I don't understand... J Casanova 09:45, 22 April 2007 (UTC)

Yes, how can something published in 1891 be only three years after 1874??? same problem in Georg Cantor Ling.Nut 07:14, 29 May 2007 (UTC)

application in economics?

I dunno cats from catywumpii when it comes to mathematics, but this looks like it might be some interesting gravy to mention in this article. --Ling.Nut 00:49, 5 June 2007 (UTC)

I do not quite understand it. If every good has a price, a countably infinite number of goods requires a countably infinite list of prices, and an uncountable set of goods requires an uncountable set of prices. I do not see the diagonal argument here.--Patrick 07:55, 7 June 2007 (UTC)

Yeah, I'm a Libertarian myself, but I have to say this paper looks fairly silly. There's a finite (not merely countable) bound to the number of goods that the Central Planning Board might plausibly have to price, and while there's always the implausible possibility that might wind up outside their predictions, no one expects an economic system to be perfect. The Austrians should stick to the "subjective theory of value" argument (the Planning Board can't know how much utility individuals actually recover from the goods); here they're on much firmer ground. --Trovatore 08:31, 7 June 2007 (UTC)

About the "Real numbers" section: Can we remove the assertion "(I)t can be shown ..." and just show it?

"The uncountability of the real numbers was already established by Cantor's first uncountability proof, but it also follows from this result. It can be shown that the set T can be placed into one-to-one correspondence with the real numbers, that is, it has the cardinality of the continuum. As T is uncountable, it follows that the real numbers must also be uncountable."

Because I don't know how to show that the set T can be placed into one-to-one correspondence with the real numbers, I thought readers with similar ignorance levels would be interested in a quick and dirty demonstration (without any discussion of set T, etc.) of the uncountability of the reals, and added an external link (http://scidiv.bcc.ctc.edu/Math/diag.html) that does just that. This was removed immediately with the notice that it didn't add anything to the article. I can see it wouldn't add anything for somebody who knows how to place set T in a 1-1 correspondence with the reals, but for people who don't, like me, I thought it did. That said, I don't really want the link: what I'd prefer is if somebody would add something to this part that does show how to place set T in a 1-1 correspondence instead of merely asserting that it can be done. I'd do it, if I knew how, but I don't. Would someone who does know, please do it? Chopbox 18:47, 7 June 2007 (UTC)

Actually, the proof in the link is not quite right, because it doesn't address the 999... problem. If I wanted to put an inline proof in this page that the set of reals is uncountable, I wouldn't do it quite that way. I would argue instead that there's an injection from T into the reals, which is sufficient. (To get a 1-1 correspondence between T and the reals, what you do is argue there's an injection from T into the reals and another one from the reals into T, and then piece them together by the technique used to prove the Schroeder-Bernstein theorem).

We probably ought to address this issue here, I suppose, even though it's not what Cantor literally proved in the paper. Can anyone source it? --Trovatore 18:59, 7 June 2007 (UTC)

Thanks for looking at this, Trovatore. Two questions about your proposal. (I think I'm starting to get it.) Do we only need an injection from T into the reals (and not a surjection as well) because we're just trying to show the reals are uncountable, and so we don't really care if there are "more" reals than there are sequences in T (though if we were interested in proving the statement that T has the "cardinality of the continuum", we would also want the surjection)? And two, would a function like the following (which simply treats the sequence as a sort of base 2 number and translates it into a decimal in base 10) work? For any sequence s_i = (s_i,1, s_i,2, s_i,3, ...), let d_i = f(s_i) = s_i,1 x 2^-1 + s_i,2 x 2^-2 + s_i,3 x 2^-3 ...  ? --Chopbox 07:15, 10 June 2007 (UTC)

Yes to the first question, no to the second. You have the same problem in base 2 -- for example 0.010100111111111111... is the same number as 0.01010100000000000..... However it would work if you interpreted the same string of zeroes and ones in base 3. --Trovatore 08:19, 10 June 2007 (UTC)

I would also be very interested to a proof or a reference about this statement. --nct 22:33, 8 September 2007 (UTC)

I've incorporated some of the above suggestions into the discussion of the reals.

Nbarth 21:38, 2 October 2007 (UTC)

Correct notation?

There was some notation in this article that looks odd to me. $T \neq f(s)$

T is a subset of S, s is an element of S and f is a function from S -> P(S). It doesn't make sense to me to indicate that the set T is not equal to some element in the image of f. We need to say that T is not in the image of f which maybe this statement would imply if extended with some set notation for all s?

Can someone with a more rigorous math background review this statement and clarify it if needed? 69.114.83.91 (talk) 05:42, 11 March 2008 (UTC)

New "arguments" subpage -- please reserve talk page for discussions relevant to improving the article

I have created a new "arguments" subpage, talk:Cantor's diagonal argument/Arguments, according to the model of talk:0.999.../Arguments and talk:Gödel's incompleteness theorems/Arguments. If you have points to make related to the underlying correctness of Cantor's proof, please use that page and not this one, which, per WP:TALK, is for discussions relating to improving the article, and not about whether its subject matter is valid.

I have moved existing sections to the subpage, trying to follow that criterion as best possible, though it's not always completely cut-and-dried (especially as I moved whole sections at a time, the only really practical way, and some sections that were primarily arguments about validity may have had some parts of them that were editorially relevant). So I may have made some errors in trying to demarcate them.

I hope everyone will respect this distinction. Really arguments subpages are an indulgence and are not truly officially sanctioned; the policy-wonk approach is simply to remove non-editorial discussions, and not put them anywhere. But I'm hoping everyone will accept this as a less heavy-handed compromise. --Trovatore (talk) 08:09, 2 June 2008 (UTC)

Possible counterexample

Although the result from the currently used version of Cantor's diagonal argument is correct (R>Z,) I think it must be pointed out that the argument has a counterexample. The counterexample is easily sidestepped, but should be recognized.

Take this series of numbers

.1000000000....

.1011111111....

.1101111111....

.1110111111....

.1111011111....

....

....

In this case, the diagonal is 100000000....., which corresponds to the number .011111111...

However, .01111111...=.1000000, which is equal to the very first row. Thus, the diagonal does not create a new number.

Again, this says nothing of the validity of the theorem. Indeed123 (talk) 20:17, 24 June 2008 (UTC)

Actually, if you read it again, you'll see that the exposition (which closely parallels Cantor's) is careful to talk about "strings of 0s and 1s", not binary representations of reals. 01111... is not equal to 10000... as a string. --Trovatore (talk) 20:35, 24 June 2008 (UTC)

Why the m, w?

Why does the main picture use m and w instead of 0 and 1? It seems like a conflict in the exposition. 146.96.107.185 (talk) 20:41, 7 November 2008 (UTC)

Georg Ferdinand Ludwig Phillip Cantor (...) was a German mathematician — may be it is something like Heads or Tails or Obverse and reverse in German? --CiaPan (talk) 20:54, 28 January 2010 (UTC)

Stating the obvious?

Isn't this just stating that, for a string of length containing 1s and 0s, a set of n strings is necessarily incomplete? There are 2^n strings available in the binary case (obvious), and 2^n > n for all n (also obvious). If we are talking about a square matrix and its diagonal, aren't we just talking about an incomplete set of size n? What is the point of discussing the diagonal? Forgive me if I've missed some implication of this, but if we are just saying that there cannot be a 1:1 mapping to a discrete 1 dimensional system, isn't talking about the diagonal overkill? Could someone please express the significance of this over the obvious nature of the size of the complete set? -Andy

That 2ⁿ > n might be obvious — for finite n. The novelty here is showing that it's also true for infinite n. There are many other such relationships that don't generalize to the infinite case — for example n+1 > n for all finite n, but not for n an infinite cardinal. --Trovatore (talk) 22:16, 10 November 2009 (UTC)

Is there some reason why L'Hopital's rule cannot be applied for n^2 / n -> 2n/1 for lim (n -> +infinity) ( .: n^2/n > 1, .: n^2 > n) ? Sorry for the nomenclature, I've never typed this stuff in ascii :) Is there some distinction to the scope of L'Hopital's rule that I am missing? Or the nature of the infinite number in question? E.g. that it is not approachable to begin with (with the limit) :) -Andy

L'Hôpital's rule (spelling note: either l'Hospital or l'Hôpital; the ô corresponds to os) does not apply to this situation; it's for finding limits of differentiable functions on the real (or complex) numbers. In this case we're (i) not trying to find a limit; (ii) not working in the real numbers, but rather in the cardinal numbers; (iii) there is no notion of differentiability around. --Trovatore (talk) 00:01, 12 November 2009 (UTC)

Just along the line of Andys argument I define my list: The list of all different sequences of length N, with N towards infinite. There is never a chance to apply the diagonal argument and obtain a sequence that would not be in the list. But all proofs of the diagonal argument refer to a square matrix! My list grows much faster in length than in width, and certainly will not become square for N = infinite. So what could Cantors argument be good for ? Gino --83.223.160.193 (talk) 20:07, 29 July 2010 (UTC) 83.223.160.193 (talk) 21:12, 21 July 2010 (UTC)

True---the set of all sequences of finite length from a finite alphabet is countably infinite, not uncountably infinite. Michael Hardy (talk) 00:39, 22 July 2010 (UTC)

About the "Real numbers" section - 2

I'd like to answer a question from the section above (#About the "Real numbers" section: Can we remove the assertion "(I)t can be shown ..." and just show it?).

The problem 'how to place the set T and the real numbers into one-to-one correspondence' is quite simple, but the solution can't be explained in one or two sentences, so it is quite hard to insert it as something like a dependent clause into a main sentence in the paragraph.

First let's note that the we can easily partition the set T into two parts: T₀ containing binary sequences with infinite number of zeros, and T₁ containing sequences with finite number of zeros. Let's put a zero and a decimal point in front of each sequence — this makes each string from T₀ a standard binary expansions of some number from interval [0,1), and each string from T₁ an expansion with repeating 1 of some number from interval (0,1].

It is quite clear that T₀ is already in 1-to-1 correspondence with the S=[0,1) interval (each sequence represents a number from the interval and each number has its expansion in the T₀ set). Let f₀ denote this bijection from S onto T₀.

Now we'll show the T₁ is countable. Let's temporarily convert each sequence into a standard form. That means we replace the 0111... tail with 1000... Additionally we remove all trailing zeros. Now we have a set of finite binary sequences. These in turn can be easily put into 1-to-1 correspondence with natural numbers simply by reverting their digits, like 0.1101 → 1011 or 0.00110101 → 10101100. If we sort T₁ strings by those resulting natural numbers (and insert the 0.111..., which would not pass the tail replacement, in front of them all), we get an infinite sequence V of all T₁ strings—so T₁ is countably infinite.

Now to put T = T₀ ∪ T₁ into 1-to-1 correspondence with S=[0,1) we need to modify f₀ : S→T₀ map to 'free' a countably infinite subset of S for T₁ mapping. Let's take the sequence W = (1/3ⁱ) for natural (positive integer) i. We can define an injection on w values: g(w_i) = w_2i. Its image contains every other term of W, so the inverse function g^–1 is defined on W tems for even indices only: g^–1(w_2i) = w_i.

Now we can define f() to map all non-W numbers from S directly to T₀ (with f₀) and every other term of W to remaining sequences in T₀ (with g^–1 and f₀). The remaining W terms are mapped to V terms and cover T₁ set. This way we get a desired S → T bijection:

$f(x) = \begin{cases} v_i \in T_1 & \textrm{if\ } x = w_{2i-1} = \tfrac 1{3^{2i-1}} \textrm{\ for\ some\ } i\in \Bbb N^* \\ f_0\left(\tfrac 1{3^i}\right) = f_0(w_i) \in T_0 & \textrm{if\ } x = w_{2i} = \tfrac 1{3^{2i}} \textrm{\ for\ some\ } i\in \Bbb N^* \\ f_0(x) \in T_0 & \textrm{otherwise\ (i.e.\ if\ } x\ne w_i \textrm{\ for\ all\ } i\in \Bbb N^* \textrm{)} \end{cases}$

Now the inverse function, f^–1, maps T onto S, which is obviously (?) uncountable.
CiaPan (talk) 22:52, 28 January 2010 (UTC)

Question

Let's say I have an set of all possible (infinite length) sequences consists of the elements "1","2","3","4","5","6","7","8","9" (0 is excluded) If you write them down from the last element to the first element in the following fashion

(1,1,2,3,5,4,3,2,...) → ......23453211

then every such string can be written as an integer (0 is excluded so there is no leading zeros and as such every element is uniquely transformed into some (infinite-length) integer), and as such the set of all possible sequences should be a subset of the integer set.

Yet the cantor diagonal argument suggests (I have 9 elements, cantor used 2, so I should have at least as much elements that way) that the set is uncountable. Please tell me whether this is valid, and if not where I have faulted in the reasoning. K61824 (talk) 23:09, 13 February 2010 (UTC)

An integer cannot have an infinite number of digits. — Carl (CBM · talk) 23:43, 13 February 2010 (UTC)

May I ask where does that appear in the definition of "integer"? K61824 (talk) 03:26, 14 February 2010 (UTC)

I'd suggest asking further on the mathematics reference desk. — Carl (CBM · talk) 03:42, 14 February 2010 (UTC)

Let X=....1111 What would be (9×X + 1) then? Is it actually an integer? --CiaPan (talk) 16:02, 11 March 2010 (UTC)

number of elements?

The uncountable sets section says that there are infinite elements, how many exactly does that mean? i.e. is that aleph₀ or aleph₁ elements? 0¹⁸ (talk) 15:35, 11 March 2010 (UTC)

Sorry, I guess I was really wondering, is there a number of digits where you can know that you have every real covered? i.e. is aleph₀ enough digits to specify pi or sqrt(2), or do you need aleph₁ elements? 0¹⁸ (talk) 15:38, 11 March 2010 (UTC)

aleph-nought is enough for that; every digit has only finitely many predecessors. And you should confuse "infinite elements" with "infinitely many elements". "Infinite elements" could mean six elements, each one of which is infinite. "Infinitely many elements" certainly implies more than six. Michael Hardy (talk) 15:40, 11 March 2010 (UTC)

Is that obvious or should it be mentioned? 0¹⁸ (talk) 15:53, 11 March 2010 (UTC)

I don't think our article should dwell on the difference in English between "infinite elements" and "infinitely many elements". As long as our article uses the words correctly, there's no problem. M. Hardy was just pointing it out to you on the talk page, but in the article itself we would simply use the correct word. — Carl (CBM · talk) 15:57, 11 March 2010 (UTC)

Changes to "Real numbers" section

My changes to the "Real numbers" section were motivated by a desire to make it more self-contained—namely, by constructing all the bijections.

After carefully reading the original section, I realized that two bijections are discussed. The first bijection is from T to a subset of R. This is done with the ternary expansion finesse. (By the way, another finesse is to correspond strings ending in all 1's with numbers in the interval (1, 2]. For example, correspond 0111… with 1.0111….) The second bijection is from T to R. It is pointed out that these sets can be shown to have the same cardinality by producing "injections $T \to \mathbf{R}$ and $\mathbf{R} \to T$, and applying the Cantor–Bernstein–Schroeder theorem."

I replaced this material by first constructing a bijection from T to the interval (0, 1). The basic idea behind this construction is in the original section. By modifying this idea, a bijection from T to (0, 1) is constructed. Next comes the construction of a bijection from T to R. This second construction uses the first bijection. At the end of the section, I give a link to the cardinality of the continuum article—this link appears at the end of the original section.

So my intent was to preserve the overall flow of the original section while building all the bijections. I look forward to your comments.--RJGray (talk) 16:32, 5 February 2011 (UTC)

Crucial logical steps are taken for granted in the article

It's the first time I read with attention a text about Cantor's diagonal argument. Schematically, the main section, called "An uncountable set" has the following structure:

1. S is an infinite numbered list of infinite binary sequences (sequences of 0s and 1s). Thus, there is a one-to-one correspondence between S and $\mathbb N$ (the natural numbers).
2. A binary sequence s₀ can be defined, which is not contained in S.
3. The set T, consisting of all infinite binary sequences, contains both s₀ (a binary sequence not included in S), and all the elements of S (each of which is a binary sequence as well). Hence, T does not coincide with S.
4. Therefore, T cannot be placed in one-to-one correspondence with $\mathbb N$.

These steps contain three crucial comparisons:

1. Between S and $\mathbb N$ (step 1).
2. Between T and S (step 3).
3. Between T with $\mathbb N$ (step 4).

Here's some feed-back for the authors of this section.

Comparison between S and N

My first reaction was: how can I be sure that such a sequence exists? I mean, a sequence of distinct infinite sequences which corresponds on-to-one with N. The answer was: yes, I can certainly imagine a set composed of the rows of an identity matrix with infinitely many rows and columns. In this case it would be very simple to define s₀ as either an infinite string of 0s, or any infinite sequence containing more than one 1 (e.g. an infinite string of 1s):

s₁ = (1, 0, 0, 0, 0, 0, ...)

s₂ = (0, 1, 0, 0, 0, 0, ...)

s₃ = (0, 0, 1, 0, 0, 0, ...)

s₄ = (0, 0, 0, 1, 0, 0, ...)

s₅ = (0, 0, 0, 0, 1, 0, ...)

...

s₀ = (0, 0, 0, 0, 0, 0 ...)

Thus, I was disappointed when I realized that:

• the article provided a much more compex example (I can't understand its construction)
• this example requires a much more complex definition of s₀.

Paolo.dL (talk) 19:27, 17 June 2011 (UTC)

Comparison between T and S

The comparison between T and S seems to repeat twice the same concept. The reductio ad absurdum starting with "Otherwise..." doesn't seem to add useful information. As far as I can understand after reading the whole section, the reductio ad absurdum is useless. It does not seem to make the argument clearer or more valid. Am I missing something? Did Cantor use a reductio ad absurdum? Do we really need a reductio ad absurdum? If yes, why?

Moreover, and much more importantly, the proof that |T| > |S| (as described here) seems to be based on the fact that T has an "additional element" (s₀) with respect to S. However, the integers Z have an even larger number of "additional elements", with respect to N. And the rational numbers Q have an even larger number of "additional elements". More exactly, the cardinality of Z, and Q is:

$|\mathbb Z| = 2 |\mathbb N| = |\mathbb N|$

$|\mathbb Q| = |\mathbb N|^2 = |\mathbb N|$

In short, $|\mathbb Z| = |\mathbb Q| = |\mathbb N|$

So, obviously it is not enough to say that T has an additional element with respect to S. Otherwise,

$|\mathbb T| = |\mathbb S| + 1 = |\mathbb S|$

which is exaxtly the opposite of what Cantor proved with his diagonal argument.

In ohter words, it is not clear at all how Cantor's diagonal argument (as described here) is compatible with the rules of transfinite cardinal arithmetics:

$\aleph_0 + 1 = \aleph_0$

$\aleph_0 \cdot n = \aleph_0$ (n = 1, 2, 3, ...)

${\aleph_0}^2 = \aleph_0$

Paolo.dL (talk) 12:45, 19 June 2011 (UTC)

The reason that it is enough to show that T has an element not in S is that S is an arbitrary sequence of binary sequences. If T was countable, there would be some S that did have exactly the same members as T (namely, any S that simply enumerated all the elements of T). — Carl (CBM · talk) 10:44, 20 June 2011 (UTC)

That's interesting. Notice that beginners do not know that all countable sets have the same cardinality. A beginner is likely to assume that |N| < |Z| < |Q|. A beginner would probably accept that, since S is an arblitrary countable list, then it may be made to correspond one-to-one not only with N, but also with Z and Q. This will only mean, for a beginner, that T is larger than the "largest possible S" (i.e. an S which can be mapped bijectively to Q). When Cantor published his diagonal argument, had he already proved that |N| = |Z| = |Q|? Do you agree that this step is taken for granted in this article? (see below for another example). Paolo.dL (talk) 14:48, 20 June 2011 (UTC)

Comparison between T and N

The conclusion seems to take for granted that the composition of a bijection (between S and N) with a non-bijection (between T and S) cannot be a bijection. Is that always valid? Doesn't it need to be proved? Paolo.dL (talk) 19:27, 17 June 2011 (UTC)

The proof does not do that. The idea is that if there was a bijection between S and T, then since there is already a bijection between N and S there would be a bijection between N and T. Because there is no bijection between N and T, though, this means there cannot be a bijection between S and T (this is just a contrapositive of the previous sentence). So the fact being used is that the composition of two bijections is again a bijection. — Carl (CBM · talk) 18:51, 19 June 2011 (UTC)

That is hard to understand from the article (and the reduction ad absurdum starting with "Otherwise..." seems useless in that context; see my comment in previous subsection). The statement that "there is no bijection between N and T", which is the statement based on which you can deny your initial if, and that you take for granted, is the conclusion of the argument in the article, not an intermediate step as in your comment.

There must be some basic information that you and the authors of the article take for granted and I cannot grasp. May be the results of some previous demonstration on which Cantor based his diagonal argument. To me (and possibly to other non-mathematicians), it seems that the first step, the easiest step, is to show that there's no bijection between S and T, as T contains an additional element. Moreover, if you can show that there's no bijection between T and N, you already have proved that there's an uncountable set, QED, and you can stop there. So, you don't need a reductio ad absurdum... Discovering what I am missing may be useful. Of course, the purpose is not at all to satisfy my personal curiosity, but to discover how the article can be made more accurate, and/or more accessible to non-mathematicians.

You might find it useful to read my other comments in the previous subsections. I have not read Cantor's article, nor a textbook describing it, so my doubts may be similar to those of most readers. Paolo.dL (talk) 19:58, 19 June 2011 (UTC)

If I am reading the history correctly, the language you are concerned about was added by you in this edit. I rephrased the article text. Note that there is no place in the proof where any two functions are composed, bijection or not. — Carl (CBM · talk) 03:38, 20 June 2011 (UTC)

As far as I can understand, your edit removed correct information, making the conclusion even more difficult to grasp. Some of this information was (purposedly) redundant. However, you also removed a crucial step, that was not added by me, and that I just restored (see my edit summary). Your edit also added a sentence which generalizes the comparison between S and T to any possible S and T. That is useful information (see first subsection of this section), but does not solve the above mentioned doubts. Before my edits, the article ended exactly with these sentences:

• ...since s0 does not appear anywhere on the list, T cannot contain s₀. [which is obviously wrong; this is true for S, not for T]
• Therefore T cannot be placed in one-to-one correspondence with the natural numbers. In other words, it is uncountable.

So, again, I confirm that the argument in the article ended (and is supposed to end, and still ends, even after your edit) with a comparison between T and N (see title of this subsection), which is what you took for granted and used as an intermediate step in your previous comment. In conclusion, I am now even more confused than I was before. Paolo.dL (talk) 09:16, 20 June 2011 (UTC)

In the proof before you edited it [1], the "T cannot contain s_0" sentence was already in the context of a counterfactual assumption: "From this it follows that the set T, consisting of all infinite sequences of zeros and ones, cannot be put into a denumerable list ... Otherwise, " higher in that paragraph. There was nothing wrong about that paragraph; the whole point of the proof is that it works for any sequence S, and therefore T cannot be put into such a sequence. — Carl (CBM · talk) 11:16, 20 June 2011 (UTC)

Your interpretation is far fetched. Although it may coincide with what the original author meant, the sentence used to express that concept meant something else. Syntactically, it was not depending on "Otherwise", because (for instance) the verb tense was not conditional. So, it was wrong and misleading. Moreover, as I already wrote, the counterfactual assumption in second last paragraph of the article, starting with "Otherwise, ..." is superfluous, and makes the paragraph unnecessarily lengthy.

The section "An uncountable set" schematically contains 4 logical steps (see my scheme above). The counterfactual assumption in the second last paragraph of that section is used to explain step 3, which actually in my opinion can be easily understood without a counterfactual assumption.

As I explained above, in my opinion some important logical steps are taken for granted in this section. One of them is the connection between steps 3 and 4, which might be represented by a counterfactual assumption. In sum, I doubt that Cantor used a counterfactual assumption to prove step 3. I guess he used it to prove step 4 (i.e. to justify the "Therefore" at the beginning of step 4).

Paolo.dL (talk) 12:04, 20 June 2011 (UTC)

I inserted at the end of the section "An uncountable set" the following paragraph. I think this is what CBM actually meant in his 18:51, 19 June 2011 contribution above. That contribution makes sense to me only if I substitute S with N, and vice versa.

It is possible to prove this conclusive statement by proving that the opposite would be impossible. Indeed, since there is a one-to-one correspondence (bijection) between $\mathbb N$ and S, if there existed (contrary to what we concluded above) a bijection between T and $\mathbb N$, there would be necessarily a bijection between S and T as well (see composition of bijections). But because actually there is no bijection between S and T, this hypotesis is absurd. In other words, the conclusive statement cannot be false, Q.E.D..

Paolo.dL (talk) 17:39, 21 June 2011 (UTC)

That text is not suitable for the article. First, nobody uses the word "conclusive" in that way in mathematics. Second, more importantly, the proof does not directly demonstrate that there is no bijection between T and S, it just proves that T is not equal to the particular S that was used in the construction. Only by pointing out that the result applies to all S do we get the conclusion that T is not countable. — Carl (CBM · talk) 02:38, 22 June 2011 (UTC)

Then again, you did not explain how step 4 "follows" from the previous ones. Clearly, you can easily "jump" to the "final result" in step 4, so you don't mind if a huge step is missing. But beginners cannot jump; I cannot either: we can barely walk. We need an intermediate step, which I am sure you can see even though you don't feel the need to use it.

Also, again, since my interpretation of your comment posted at 18:51, 19 June 2011, seems to be incorrect, and since that interpretation was the only way for me to understand it, I am now forced to confirm what I wrote above about that comment: I cannot accept it, as it uses the "final result" as an intermediate step ("Because there is no bijection between N and T, though, ..."). I pointed this out twice, and you never answered. Eventually I realized that your statement made perfectly sense to me if it were rewritten as follows (corrections in bold):

The idea is that if there was a bijection between S N and T, then since there is already a bijection between N and S there would be a bijection between N S and T. Because there is no bijection between N S and T, though, this means there cannot be a bijection between S N and T. So the fact being used is that the composition of two bijections is again a bijection.

And this is what I wrote in the article. But you rejected this interpretation.

Paolo.dL (talk) 09:39, 22 June 2011 (UTC)

I only wrote that in response to your comments about composing a bijection and a non-bijection, to explain how that is not an issue. However, the point of the middle part of the proof is to show that S and T are not the same, not to show that S and T cannot be put into bijection with each other. I do not have the energy to respond to all your comments on the talk page, and I am not trying to teach you the theorem. I just respond when I feel moved and edit the article if I think some wording needs to be improved. Perhaps you could as at WT:WPM if some other mathematicians would be interested in cleaning up the proof. — Carl (CBM · talk) 11:30, 22 June 2011 (UTC)

This is what the article currently says:

Because this argument applies to any countable set S of sequences of 0s and 1s, it follows that T cannot be equal to any such set. Thus T is uncountable: it cannot be placed in one-to-one correspondence with the set of natural numbers \mathbb N.

There is no missing step there. If T was countable, it would be equal to at least one countable set of sequences, namely T would be equal to T itself. But the previous part of the proof shows that T cannot be equal (contain exactly the same sequences as) any countable set of sequences. So T is not countable. — Carl (CBM · talk) 11:32, 22 June 2011 (UTC)

Well, this just moves the logical "gap" (missing step) somewhere else. There's no prove in the article that "this argument applies to any countable set S of sequences of 0s and 1s". This statement, which you recently inserted, is taken for granted. Before you inserted it, the situation was even worst, but the article is still incomplete. I hope somebody else will be able to fill the remaining gaps. Thank you for your help. Paolo.dL (talk) 12:20, 22 June 2011 (UTC)

Laplace's Demon

Could someone please clarify what the following sentence is supposed to mean? Thanks--345Kai (talk) 11:58, 13 August 2011 (UTC)

In 2008, diagonalization was used to "slam the door" on Laplace's demon.[1]