Talk:Cantor's diagonal argument/Archive 2

Archive 1

Archive 2

Archive 3

Request to delete this article Cantor's Argument is False

See link:

http://www.spacetimeandtheuniverse.com/math/4507-0-999-equal-one-499.html#post26517

197.79.24.192 (talk) 13:45, 27 January 2014 (UTC)

Off-topic discussion. This talk page is for discussions about the article, not about the subject - see warnings on top of this page

I couldn't understand the argument given on that page. What precisely is the definition of the bijection between real numbers in (0,1) and natural numbers? Moreover, I wonder which number the diagonal sequence s (see 1st picture in the article) would be assigned to. Maybe, the jpg image "diagonal.jpg" could give the answer, but it is not accessible without registration. Overall, I guess I'll keep being a "mainstream baboon" (cited from linked web page). - Jochen Burghardt (talk) 17:44, 27 January 2014 (UTC) Your article claims that given an enumeration of arbitrary members from T, say, s_1 = 0 0 1 ... s_2 = 1 0 1 ... s_3 = 1 1 1 ... then there is a member s such that s = 1 1 0 ... which is not in the binary tree. But this is false because 1 1 0 ... is in the binary tree. If the theorem means only from the arbitrary enumeration, then it really proves nothing, because all the members can be listed from the binary tree, that is, the strings form unique names for each member. A top-down followed by left-right traversal produces every member of T. To answer your question: The bijection is explained in terms of unique identifiers preceding each type of real number. For example, +, - and *. So there are three types which cover finite representations, non-terminating repeating representations and non-terminating non-repeating representations. It is then trivial to create a bijection as follows: 0 1 2 3 4 5 6 7 8 9 ... + - * + - * + - * ... by visiting each node of the tree with the traversal occurring top-down followed by left-right for each level. Now, it is not necessary to find a bijection in order to prove the countability of the set of real numbers on the assumption they can be represented as decimal strings. That's not what it means to be countable. See the following links: http://www.spacetimeandtheuniverse.com/math/4507-0-999-equal-one-505.html#post26575 http://www.spacetimeandtheuniverse.com/math/4507-0-999-equal-one-505.html#post26577 41.119.46.195 (talk) 18:21, 19 February 2014 (UTC)

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

As long as it doesn't have any non-zero digits after the decimal point, isn't it an integer no matter what? — Preceding unsigned comment added by 98.195.88.33 (talk) 00:23, 11 February 2016 (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.

Note that ...333 is not an integer, on that basis this argument is flawed. 195.195.217.140 (talk) 16:42, 21 May 2017 (UTC)

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\leq m{\mbox{ and }}n{\mbox{ is the smallest natural number such that }}\phi (n)\\1/2,&{\mbox{if there is no }}n\leq 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)

The only intention that I see in Cantor's Diagonal Argument is to show that the set of real numbers is not only infinite, but also order-less. Denumeration requires an unbreakable biunique correspondence. Biunique correspondence needs some sense of order. No matter how exhaustive finite set of real numbers one comes up with, Cantor can still add another real number somewhere inside (in the middle or so) the presented set, using diagonal argument, thus destroying the presented biunique correspondence of the set. Kawaikx15 (talk) 01:08, 25 September 2012 (UTC) Saurabh

But to show that one doesn't need a diagonal argument. You can just choose an open interval, say (0, 1) to begin with, and ask someone to try to enumerate real numbers. Whenever a number falls into your interval you remove a half of it, so the remaining half doesn't contain the number just spelled. The interval gets shorter and shorter, but it still remains not empty. As thing go on, the left and right end of the interval may converge to a single number, their common limit—and that number is guaranteed to be absent in the sequence (otherwise you would have avoided it by removing appropriate half of the interval at some step of the procedure). That shows that for any sequence of real numbers (function N → R) there exists a number not included in the sequence. --CiaPan (talk) 12:42, 25 September 2012 (UTC)

BTW, you wrote 'No matter how exhaustive finite set of real numbers one comes up with' — please note that finite sets are not a problem, the proof is most important for infinite sets. CiaPan (talk)

The set which we assumed to be infinite but fixed in denumeration before applying diagonal argument turns out to be not so fixed in numeration! kawaikx15 Saurabh (talk) 10:14, 29 September 2012 (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}&{\text{if }}x=w_{2i-1}={\tfrac {1}{3^{2i-1}}}{\text{ for some }}i\in \mathbb {N} ^{*}\\f_{0}\left({\tfrac {1}{3^{i}}}\right)=f_{0}(w_{i})\in T_{0}&{\text{if }}x=w_{2i}={\tfrac {1}{3^{2i}}}{\text{ for some }}i\in \mathbb {N} ^{*}\\f_{0}(x)\in T_{0}&{\text{otherwise (i.e. if }}x\neq w_{i}{\text{ for all }}i\in \mathbb {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)

It would be (9×X + 1) = 1000... And it consists of the elements "1","2","3","4","5","6","7","8","9","0" and has no decimal or fractional part, so it is actually an integer.→Olavisjo (talk) 13:08, 18 November 2014 (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)

I’ve read both the text in the article (the last paragraph before section 1.1) and your explanation here at least five times, and each time the article’s wording felt (intuitively) suspect and yours felt sound. But I can’t tell what part of the text triggers the intuitive difference. Perhaps you should try to rewrite the article’s paragraph somehow? bogdanb (talk) 08:57, 12 July 2013 (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]

Try reading the Laplace's demon article, section Arguments against Laplace's demon, last paragraph. --CiaPan (talk) 10:23, 15 May 2012 (UTC)

Also Borel hierarchy

"The most famous examples are perhaps Russell's paradox, the first of Gödel's incompleteness theorems, and Turing's answer to the Entscheidungsproblem." — Also, that Borel hierarchy does not collapse. Boris Tsirelson (talk) 12:50, 30 July 2012 (UTC)

Suggestions

I have only suggestions, besides, I am not a mathematician and am not an English native (which must be evident from my posting anyway), so I don't do any editing myself.

1. The article needs restructuring. Currently it concerns two important topics at once (the diagonal argument itself and its application to the sets of numbers). This is no good. I think there should be two articles, and the more general article should link to the less general one.

2. The article seems to need rephrasing. Why not state it explicitly that what we did was we have enumerated an arbitrarily chosen countable set A of some real numbers? The proof is that the set of all real numbers R cannot be a subset of any A, that's what the argument deals with. This way, the temptation to 'create' a new natural number and add it back to the list vanishes away, because this is going to be stated explicitely that A has been mapped to the set of all natural numbers, and no natural numbers have been overlooked. Readability counts!

3. The article needs expansion. It is important for both topics (especially for the second one) why Cantor decided to consider the argument and the sets of numbers and what general consequences these considerations had for development of mathematics and of human culture. Wikipedia is about knowledge; but knowledge is not a collection of facts, it is their system.

4. Also, the point that natural numbers are finite and can only have finite number of digits in their written representation could better be referred to explicitely, even if unobtrusively, in the article. The article is interesting mainly for common people, not for mathematicians (who better learn the things like these in university and not here), because it deals with fundamentals of our mental existence and of our mind. Anyway, it's for all and can be made for all, so why not? - 91.122.83.41 (talk) 17:51, 1 February 2013 (UTC)

Point 2. suggests one can not add anything to any infinite list. But that's wrong. Say, we have a countable list of some numbers:
      8, 10, 12, 14, 16, ...
Can't we add 5, √7 and −π to the list, just because 'no natural numbers have been overlooked'...? Of course we can! The nice property of an infinite set is that it is equipollent with some its proper subset, so we can inject it into itself leaving some members not covered. That means just shift the sequence terms a bit to make a room for new terms, and here it is:
      8, 10, √7, 12, −π, 5, 14, 16, ...
CiaPan (talk) 21:27, 1 February 2013 (UTC)

One can add 'anything', only one wouldn't. What is of interest are natural numbers, and the fact that there is no action to them during the course of the reasoning, only (sub)sets of real numbers are considered. No? Anyway, this point is not the most important one. I'd say, the most important are #3 and #1 (structure and topics), then #4 and #2 (readability). - (I) 89.110.18.181 (talk) 22:42, 1 February 2013 (UTC)

In other words: no, 'point 2.' doesn't suggest anything like that. - 91.122.11.64 (talk) 11:45, 2 February 2013 (UTC)

References added

Noting here that I added a reference to Ethan Bloch's real analysis book to try and fulfill the request in the article for more references. The section in Bloch's text is entitled "Application of Sequences." In it, he proves the Nested Interval Theorem, then uses this result after a discussion of Cantor's diagonal argument in a proof that ℝ is uncountable, which is in fact Cantor's earlier proof that is mentioned in the article.

John (talk) 03:07, 29 October 2014 (UTC)

I have now added references to three analysis textbooks (see the article citation list). If one performs a web search, it is not hard to find a pdf of the book by Bloch. I can provide a pdf scan of relevant pages from the Rudin text if anyone wants to review that citation for accuracy. The other reference is viewable on google books, just follow the link. These books constitute reliable, published sources from major, established publishing houses.

Therefore I suggest that the {{One source|date=August 2013}} line at the beginning of the article be removed. I have spent some time in a university library browsing analysis books; it is easy to find examples of this mathematical concept in print. More refs can be added if someone else wants to do the legwork. Just browse the QA 300 shelf in your neighborhood math library. Cantor's diagonal argument is clearly part of the analysis canon in modern mathematics, so I would argue that the "one source" objection is not relevant. I will wait a few days or indefinitely longer before removing the one source tag if there are no objections. I have no idea what the relevant etiquette is here. I am not in a hurry.

--John (talk) 19:48, 29 October 2014 (UTC)

Redundant parts of section "Uncountable set"?

In section Cantor's diagonal argument#Uncountable set, I had commented out on 6 Dec 2013 some text that I considered redundant.

On 5 Jan 2014, 174.3.125.23 has uncommented that text again to ease discussion of inclusion.

Since I still consider that text redundant (and confusing since it starts the proof all over again after it just had been finished), I move the text to here (the last kept sentence given in red as context):

... This contradicts the original assumption, so T must be uncountable.

The elements s_1,1, s_2,2, s_3,3, and so on, are here highlighted, showing the origin of the name "diagonal argument". Each element in s₀ is, by definition, different from the highlighted element in the corresponding column of the table above it. In short, s_0,n ≠ s_n,n.

Therefore this new sequence s₀ is distinct from all the sequences in the list. This follows from the fact that if it were identical to, say, the 10th sequence in the list, then we would have s_0,10 = s_10,10. In general, we would have s_0,n = s_n,n, which, due to the construction of s₀, is impossible. In short, by its definition s₀ is not contained in the countable sequence S.

Let T be a set consisting of all infinite sequences of 0s and 1s. By its definition, this set must contain not only the sequences included in S, but also s₀, which is just another sequence of 0s and 1s. However, s₀ does not appear anywhere in S. Hence, T cannot coincide with S.

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. If T was countable, there would be some S that did have exactly the same members as T, namely, any S that simply enumerates all the elements of T. But the preceding proof shows no S contains all the elements of T. Thus T is uncountable: it cannot be placed in one-to-one correspondence with the set of natural numbers $\mathbb {N}$.

- Jochen Burghardt (talk) 09:38, 6 January 2015 (UTC)

Does the set of positive integers not show the same property? (Layman consumer here)

For any n however large, I can "construct" an m by incrementing n by 1. Are positive integers uncountable then?

Also, just omitting the index of one of T's elements (which element is known to be in some relationship to the rest of the elements) (that is omitting the index of the constructed s in the exposition) makes T uncountable?

-- TheNightManager (talk) 09:24, 13 September 2015 (UTC)

You might go to the wp:Reference desk/Mathematics with this. Here we discuss the article, not the subject—see wp:Talk page guidelines. Good luck. - DVdm (talk) 09:47, 13 September 2015 (UTC)

Cantor's proof takes an enumeration of T 's elements and constructs an element that is not covered. Your (first) argument takes an element and constructs another one. I guess you are unable to start from the trivial enumeration of positive integers (i.e. mapping each element to itself) and construct from it an element that isn't covered. Therefore, this set is countable. - I didn't understand your second argument; there is no need to "make" T uncountable, since it is uncountable, anyway (as shown by Cantor's proof). - Jochen Burghardt (talk) 16:29, 13 September 2015 (UTC)

More text please

This expression of the construction loses me:

he constructs the sequence s by choosing its nth digit 
as complementary to the nth digit of sn, for every n. 

Could someone clarify? e.g. The sequence looks like a series of series of numbers rather than a series of numbers, though it couild be made into a series of numbers by deleting all the commas between the numbers in each row. So what is the nth digit of a 2D matrix? What does "complimentary" mean here? The nth digit of sn is for example the 5th digit of the 5th row of the series? And that nth digit is .. complimentary to ... ?

HELP!

ps IMO (though I think I've seen it written someplace) Wiki articles should start from simple explanations suitable for e.g non-mathematicians to comprehend (without having to research terminology or go on a course) and proceed to increasingly technical explanations. LookingGlass (talk) 18:24, 17 February 2016 (UTC)

I made this change. Note that I added a wikilink to complementary. Is this okay with you? - DVdm (talk) 18:47, 17 February 2016 (UTC)

Maybe, "... by choosing its nth digit to be different from the nth digit of sn ..." is easier to understand, and doesn't need a wikilink? - Jochen Burghardt (talk) 06:35, 18 February 2016 (UTC)

I made another tweak, adding the text from the linked article. - DVdm (talk) 09:34, 18 February 2016 (UTC)

Thank you for your help folks. I think my initial query was too vague so the following is an attempt to clarify what I misunderstand of the original version:

he constructs a sequence s by choosing its nth digit 

"he constructs a sequence of numbers (sequence of sequences of binary numbers?) s, in which the nth digit of the nth number in the sequence..."

as complementary to the nth digit of sn, for every n. 

"... is complimentary to the ... " and from this point you will hopefully see how I become lost. Sn would seem to be being referred to twice which can't be but this seems necessary for both first and second parts as there is no nth digit in the sequence otherwise, as the sequence forms a 2D matrix with both dimensions being infinite ... and the term "nth" digit has only one dimension so doesn't specify any element. On a minor note, I understand the term complimentary but is it necessarily or would a less technical term (with the technical one in parenthesis maybe) be as good? Also, the sequence S seems like it is a sequence (s0...sn) of binary number sequences, rather than a sequence of numbers. Would referring to this as a binary thing at the outset enable a clearer explanation? I hope this makes the confusion clearer... p.s The intro begins:

given an enumeration of arbitrary members from T, like e.g.

yet the numbers in the sequence are specifically constructed so the term "arbitrary" doesn't readily jibe with the common usage of the term. If arbitrary is specifically defined mathematically then it would be helpful to use some brief phrase instead, again with a link if appropriate. These are only suggestions of course as I don't understand what is intended to be communicated here. Thanks again. LookingGlass (talk) 22:23, 20 February 2016 (UTC)

I think you still missed essential points of the proof, and I'd like to find out how to improve the text in order to avoid your misunderstandings. The proof assumes an arbitrary (in the usual sense) sequence s0,s1,...,sn,... of elements of T, i.e. of sequences of digits. For this reason, it is represented 2-dimensional, each row being a sequence of digits. Form this, Cantor constructs a new sequence of digits, called just s; it is presented in the article as an own row. Only this single row is constructed, not the whole matrix. The construction is such that it guarantees that s cannot coincide with any of the (infinitely many) given sequences s0,s1,...,sn,... - Is this attempt of explanation more clear? Maybe the article should be more explicit about sequence of digits vs. sequence of digit-sequences? - Jochen Burghardt (talk) 23:11, 20 February 2016 (UTC)

Thanks Jochen, that really helps, and I think you're absolutely right both about my assumptions and your suggestions. I had assumed that elements of s were constructed one from the other by some algorithm. So, the sequence s0 ... sn (adding in s0 helps clarify I think) lists something akin to the elements of a set (may I call this X for convenience) each of which is made up of an arbitrary sequence of binary numbers. Neither the elements of X nor the digits that make up each element are random ... but this would mean that sequences could repeat such that for instance the series s5 could be the same as the series s107... anyway, The series s is not an element of the set X but rather is constructed by reference to it such that it's nth digit is the inverse of the nth digit of element sn of the set X. My explanation can't be correct, as if s0..sn are elements of a set X then those elements can't be represented more than once so there must be something "more than" arbitrariness defining them, but hopefully it will help you understand how I'm interpreting the information and how it could perhaps be clarified. Thanks again for your interest in this tangle of mine. LookingGlass (talk) 15:17, 21 February 2016 (UTC)

Perhaps I can lend a hand here. Firstly, a minor issue, I don't think that the 0 indexing is useful in this situation, as it forces one to use un-natural language. I think that a major part of the problem here is in the phrase " ... an enumeration of arbitrary elements of T." I would point out first that this is incorrect and should read "...an arbitrary enumeration of the elements of T." Secondly, I would say that we should stay away from the fancy language and simply say what is meant, that is "List, in any order you like, all the elements of T. Thus, each item in the list is a binary sequence." This phrasing, while not quite encyclopedic, does make it clear that there is nothing arbitrary about the set T (after it has been selected), the only thing that is arbitrary is the order in which its elements are placed in the list. There is a tacit assumption here, namely, when you are creating this list you do not repeat elements (each element of T appears only once in the listing). The elements of T are specific binary sequences (nothing random or arbitrary about them), however, to illustrate the method you have to write something down and for illustrative purposes you may write down arbitrary sequences, just to show how general the method is ... that is, it will work on anything you throw at it. Finally, the construction builds a single binary sequence (s) which can not be an element of T because it differs from the ith sequence on the list (i.e., an element of T) in the ith position of that sequence (and probably in lots of other positions as well, but you only need one difference to see that it is not the same as the ith entry on the list for every i ). Since the list contains all the elements of T, our sequence s can not be in T. I hope this helps. Bill Cherowitzo (talk) 06:48, 22 February 2016 (UTC)

Sorry, I was confusing the two part argument as given by Cantor (see below) because I didn't pay enough attention to the definition of T as consisting of all binary sequences; so of course s is in T because s is a binary sequence. Now that I am thinking about this correctly, I see another source of confusion; that being the use of the word enumeration. The term is too packed with meaning and needs to be spelled out. I think that Cantor actually used something like "a simply infinite sequence of elements of T." I can see why we would not want to use "sequence" twice (as in, "a sequence of sequences"), so would not advocate for the original terminology, but I think that an "(infinite) list of elements of T" could be made to work and is more visually tied to the argument than the more abstract "enumeration". Bill Cherowitzo (talk) 18:07, 22 February 2016 (UTC)

Noticing the confusion with "enumeration of arbitrary members from T", I have replaced it with "enumeration of elements from T". This way it duplicates the wording of the theorem; the word "arbitrary" seemed to confused a couple of readers. There is no "tacit assumption" needed that you do not repeat elements, the proof works fine with repeated elements.

The statement "the construction builds a single binary sequence (s) which can not be an element of T" is a common confusion. What the proof shows is "there is always an element s of T which corresponds to no s_n in the enumeration." (Boldface is for emphasis, not in article text. Note that s is an element of T.)

The point here is not to confuse the construction of the element s that is not in the enumeration with the proof by contradiction needed to prove the set T is uncountable. This comes later in the section:

Based on this theorem, Cantor then uses an indirect argument to show that: The set T is uncountable. He assumes for contradiction that T was countable. Then (all) its elements could be written as an enumeration s₁, s₂, … , s_n, … . Applying the previous theorem to this enumeration would produce a sequence s not belonging to the enumeration. However, s was an element of T and should therefore be in the enumeration. This contradicts the original assumption, so T must be uncountable.

It's important to realize that Cantor's argument constructs an element s not in the enumeration because Turing uses it in this way in his answer to the Entscheidungsproblem. Also, Gödel uses it in this way to construct a statement in arithmetic that is true but not provable. Hope this clarifies the situation a bit. RJGray (talk) 16:29, 22 February 2016 (UTC)

Thanks again all. I believe I now get it! The penny seemed to drop in RJGray's comment (why I don't know).

What the proof shows is "there is always an element s of T which 
corresponds to no sn in the enumeration."

Could it read simply "an element of T which correspnds"? Omitting it allows it to be reintroduced at the same time as its construction is explained. Including it suggests, to an unfamiliar reader, that it is part of the enumerated list s1..sn. Are the only uncountable sets those proved by this diagonal argument? The introduction seems to say so and the proof/arugument itself is titled Uncountable set. Anyway, could the "explanation" be shortened, including only the second enumerated list (the only difference is the emboldened digits), to something like:

To prove this, for any given enumeration of elements from T, he constructs a sequence s such that its 1st digit is complementary to the 1st digit of s1 (swapping 0 for 1 and vice versa), the 2nd digit is complementary to the 2nd digit of s2, and generally such that its nth digit is complementary to the nth digit of element sn.

From the list enumerated in the example below the sequence s shown is then produced:

Thanks again. LookingGlass (talk) 12:14, 24 February 2016 (UTC)

Right now, I'll just deal with your first point about "there is always an element s of T which corresponds to no sn in the enumeration." Would it help to eliminate "corresponds" and just say: "there is always an element s of T which is not in the enumeration." ? We could even eliminate the "always" since it's not really needed. RJGray (talk) 16:11, 24 February 2016 (UTC)

Hi, sorry for the delay in replying. What you say is really interesting. It's completely logical and yet ... I find, for some reason, eliminating those two redundant words makes it harder to read, and therefore harder to understand, despite being I guess more accurate. Odd. But I think the redundancy helps me by skirting around other issues and thereby not requiring the reader to consider anything, at first encounter, apart from the core of the argument. Are the numbers the same numbers? I guess they are, obviously they are when we think about it, but in the real world there are no two things that are actually identical - so the difference between numerally identical and identical isn't something we generally need to be familiar with. So there's a conflict. We feel we know what numbers are but in actuality we aren't because we don't need to be, if you follow me. The same sort of thing applies to the word 'always' here. There are an infinite number of enumerations s1-sn. Removing the word always is correct because we're talking about the relationship of the diagonal to the enumeration in ALL cases. It's a bit like something being grammatically correct but more confusing that the error .. and that's how natural language evolves I guess. Whenever I use the indefinite article with a word beginning with 'h' I know I should use 'an' and yet in most cases I use 'a' as that's what I say and hear. Drifting offline now but I'm sure you know what I mean.

On the same lines I notice the diagram has red numerals for the diagonal in the matrix but that the inversion/compliment is in blue. Makes sense but still made me stop and think. LookingGlass (talk) 18:56, 1 March 2016 (UTC)

Russell's Paradox

is it accurate in any sense to suggest in this article that this technique is used in Russell's paradox?? ...as it does in the intro etc..68.48.241.158 (talk) 19:48, 11 July 2016 (UTC)

Certainly nowhere near accurate enough to include it so yes deleting that is a good edit thanks. Dmcq (talk) 14:57, 12 July 2016 (UTC)

Russell explicitly mentioned Cantor's diagonal argument in his formulation of the paradox in the Principia. The same general technique was used. Sławomir Biały (talk) 15:50, 12 July 2016 (UTC)

I'm not convinced as yet...can you source it/quote it? I don't see how the lemma is actually used in any way whatsoever in the formal/logical demonstration of Russell's paradox...perhaps there will be others who come along here or at the help desk to explain if it's in fact the case (which it may be...)..I think Russell stumbled upon the paradox when thinking about Cantor's work but this is a bit different.. 68.48.241.158 (talk) 16:53, 12 July 2016 (UTC)

From the Stanford encyclopedia of philosophy: 'As Russell tells us, it was after he applied the same kind of reasoning found in Cantor's diagonal argument to a “supposed class of all imaginable objects” that he was led to the contradiction' Sławomir Biały (talk) 16:59, 12 July 2016 (UTC)

it seems we lost the section break for some reason...anyway, I agree the lemma is used in the technical demonstrations of the work of Godel and Turing cited here (the proofs)...still not sure about Russell's paradox though..and the article suggests that the lemma is used in the proof of Russell's paradox...68.48.241.158 (talk) 17:06, 12 July 2016 (UTC)

The article says "it demonstrates a powerful and general technique that has since been used in a wide range of proofs". It does not suggest that "the lemma" (is there a specific lemma you mean?) was used. Sławomir Biały (talk) 17:21, 12 July 2016 (UTC)

perhaps I'm getting too nit-picky but I read it as suggesting a diagonal argument/method is used in the proof (the formal, logical demonstration) of Russell's paradox...I don't think this is true...I think the formal demonstration involves no such diagonal technique...I agree the technique is used in the formal proofs of Godel and Turing....68.48.241.158 (talk) 17:29, 12 July 2016 (UTC)

Sure, the method is used in the proof. Russell's antimony is the Cantor diagonal of the identity function. Sławomir Biały (talk) 18:24, 12 July 2016 (UTC)

I do think it can be thought of that way or looked at in that way but I don't think the formal, symbolic proof specifically uses a diagonal method or needs to use one in the way Godel and Turing's work do..if one or two others come along and concur with you I certainly have no problem going along with the notion..68.48.241.158 (talk) 18:38, 12 July 2016 (UTC)

Well I disagree with Sławomir, if the paradox was based on Russel's original thinking it would certainly be a recognizable application of Cantor's diagonal proof, but the actual version he came up with is just too far away from Cantor's diagonal proof. It is a straightforward reductio ad absurdum without Cantor's trick. Dmcq (talk) 18:46, 12 July 2016 (UTC)

I don't really think it's that controversial. Russell's paradoxical set is exactly gotten by applying Cantor's method. He even acknowledges this in Principia: "when we apply the reasoning of [Cantor's] proof to the cases in question we find ourselves met by definite contradictions, of which the one discussed in Chapter x is an example." (p. 362) Sławomir Biały (talk) 18:51, 12 July 2016 (UTC)

and, again, just to be clear I'm focusing specifically on the formal, technical, symbolicproof itself..which may be a little nit-picky but it's what the sentence in the article says, "proof"..68.48.241.158 (talk) 18:58, 12 July 2016 (UTC)

Yes, that is being awfully nit-picky. Typically, the construction of a contradiction is regarded as part of a proof by contradiction. So, the construction of the paradoxical set is indeed a part of the formal mathematical proof. Anyway, I have changed the word "proof" to "mathematical construction". Hopefully that is completely uncontentious. Sławomir Biały (talk) 19:07, 12 July 2016 (UTC)

perhaps..I'm still leaning toward thinking it's a bit misleading to list it along with the other two in that sentence, but maybe not..don't think it's a big deal either way...but perhaps a couple others will come along too..68.48.241.158 (talk) 19:13, 12 July 2016 (UTC)

You're welcome to go and read paragraphs 346-349 in Russell's Principles of mathematics. He discusses Cantor's original argument, presents his own version of it, and shows how this argument leads to the paradoxical class. Pretty black-and-white really. Sławomir Biały (talk) 19:42, 12 July 2016 (UTC)

your recent edits to the article probably make things more inline with the exact, nit-picky facts..so I'm satisfied and think I now understand things better...68.48.241.158 (talk) 21:54, 12 July 2016 (UTC)

I've had a read of what Russell says and with a reference to that in the article I think it works okay even if it doesn't look like the diagonal argument at first. Dmcq (talk) 21:57, 12 July 2016 (UTC)

Why is it that the main argument cannot be applied to countable sets with infinite elements

The following discussion is closed. Please do not modify it. Subsequent comments should be made on the appropriate discussion page. No further edits should be made to this discussion.

---

Let's repeat exactly the same argument used in the main article but for a different set, say the integers. Let T be the set of all integers. Let s₁, s₂, ..., s_n, ... be an enumeration of T such that: s₁ = 1, s₂ = 2, s₃ = 3, ... Then, there is always an element s of T which corresponds to no s_n in the enumeration: s = 1 + (s₁ + s₂ + s₃ + ...). Hence, T is uncountable (which follows by using the same proof by contradiction). But the set of all integers is countable by definition. So, what is wrong here? Why is it that the argument used in the main article fails here? — Preceding unsigned comment added by Swoun (talk • contribs) 17:09, 7 September 2016 (UTC)

Hi Swoun. Article talk pages are for discussing what should appear in the article, not for general discussion of the subject matter. If you ask this question at Wikipedia:Reference Desk/Mathematics, there will be people happy to help you out. --Trovatore (talk) 17:11, 7 September 2016 (UTC)

Hello Trovatore. I'm using this article page to discuss exactly what appears in the article, not for a general discussion of the subject matter. I thought this was very clear. I'm giving an example of a situation where the exact same argument used in the article (around which everything else in the article revolves) fails in order to show that the argument is flawed as is, or that it needs to be improved. To be more explicit, the argument says that, given an enumeration, whenever we can construct a new element out of the old ones which is not in the enumeration, then the set will be uncountable. This is clearly wrong and I'm giving a counterexample. — Preceding unsigned comment added by Swoun (talk • contribs) 17:22, 7 September 2016 (UTC)

Please sign all your talk page messages with four tildes (~~~~). Thanks.

It appears that the main argument in the article is backed by reliable sources. If you have a proper reliable source to back your argument, then we can discuss it here. Otherwise we are not allowed to do that. Please go to the reference desk. DVdm (talk) 18:10, 7 September 2016 (UTC)

I do not mean to be impolite, but it appears that you have not read the article. Please provide me with a single reliable source that backs the exact same argument used in the article, as you say that it exists. Please note that the sources referenced in the article do not provide such an argument. Regarding your second statement, I just gave a clear counterexample and you are asking me to back my counterexample with something from the literature. How do I back a logical reasoning with a citation? If I tell you that A=B and B=C implies A=C, will you ask me to back my remark with a source? Finally, the Wolfram webpage on this subject provides the correct proof that the power set of a given set always has larger cardinality (which is what this is about): http://mathworld.wolfram.com/CantorDiagonalMethod.html Swoun (talk) 18:27, 7 September 2016 (UTC)

It is on page 76 of the very first reference, Ueber eine elementare Frage der Mannigfaltigkeitslehre. --Trovatore (talk) 18:53, 7 September 2016 (UTC)

Do have a look at the policies regarding wp:NOR: 'Wikipedia does not publish original thought: all material in Wikipedia must be attributable to a reliable, published source. Articles may not contain any new analysis or synthesis of published material that serves to reach or imply a conclusion not clearly stated by the sources themselves.' So we cannot discuss your unpublished logical arguments here.

If you have doubts about something that is (or appears to be) unsourced in an article, then you can tag it with {{citation needed}}. And if indeed that passage is unsourced and no sources can be provided, then it should and probably will be removed. - DVdm (talk) 18:45, 7 September 2016 (UTC)

This discussion you are trying to have is becoming somewhat absurd and completely unrelated to the original topic: 1) Why did you say "the main argument in the article is backed by reliable sources" when you cannot provide a single one? 2) Why do you insist in saying that "Wikipedia does not publish original thought" or that "Articles may not contain any new analysis" when I'm not trying to publish absolutely anything? I'm not asking you to move my original comments from the Talk page to the front page. I opened a new section in this Talk page to bring to the attention of the readers that the main argument in the article is flawed (for the reasons above) and that it needs to be improved. That's it. I'm not trying to achieve absolutely anything else, as you seem to be implying. So please do not quote Wikipedia policies inappropriately. And please, let us not continue with this discussion since it is completely unrelated to the content of the article and the purpose of this section. Swoun (talk) 18:59, 7 September 2016 (UTC)

Perhaps you missed my comment above. It is on page 76 of the very first reference, Ueber eine elementare Frage der Mannigfaltigkeitslehre. --Trovatore (talk) 19:02, 7 September 2016 (UTC)

The same proof also appears in Rudin's PMA, referenced in the article. Sławomir Biały (talk) 23:08, 7 September 2016 (UTC)

The discussion above is closed. Please do not modify it. Subsequent comments should be made on the appropriate discussion page. No further edits should be made to this discussion.

Powerful and general technique

Twice I have restored the phrase "powerful and general technique", which was removed by anon (no comment), ("Deleted peacock verbiage"). I have now added a source backing the phrase ([2]), and left another warning at anon's talk page ([3]). - DVdm (talk) 15:04, 20 May 2017 (UTC)

Just an opinion: I think there is some "peacockness" in the wording. Isn't it sufficient to have the variety of applications listed and let it speak for itself? What information beyond that application list does "powerful and general" convey? - Jochen Burghardt (talk) 20:02, 20 May 2017 (UTC)

I'm ok with either version. Or perhaps just remove "powerful" and leave "general" in. I don't think we need "powerful and general", which does come across a little bit peacocky. Sławomir Biały (talk) 11:45, 21 May 2017 (UTC)

I don't really see anyting peacockery here. The cited source says: "The general method of diagonalization is a powerful technique..." So if we really must make a change here, I propose we change it to "However, the general method demonstrates a powerful technique that...". But again, I don't sense peackockerism at all here. - DVdm (talk) 11:53, 21 May 2017 (UTC)

I would say that there is a little "peacockness" here, but it is quite subtle and most people would not pick up on it. There is also a difference between saying that "the general method is ..." and "a method is general and ...". So, in keeping with the cited source, I think DVdm's suggestion is the right way to go. --Bill Cherowitzo (talk) 16:53, 21 May 2017 (UTC)

At first glance, the diagonal argument appears to be a one trick pony. The import of that sentence is to point out the significant and counterintuitive fact, that the diagonal argument has far more force, and wider applicability, than one might otherwise suppose. So no I don't really see any peacockness here. Paul August ☎ 19:00, 21 May 2017 (UTC)

Peacock verbiage has been sourced to peacock verbiage. — Preceding unsigned comment added by 99.230.158.94 (talk) 08:28, 24 May 2017 (UTC)

Set theory isn't real

Non-editorial comments moved to Talk:Cantor's diagonal argument/Arguments#Set theory isn't real. --Trovatore (talk) 06:16, 16 August 2017 (UTC)

Proof of uncountability of R is too clever

The recent back-and-forth between RJGray and DVDm is a little hard to follow; they both say true things. Sure, the argument given (if correct; I haven't bothered to check the whole thing) shows that there is a bijection between T and R, as RJGray says, and R is also a subset of R, as DVDm says.

But more to the point, why are we bothering to construct a bijection here at all? The claim is that the reals are uncountable; that's established by showing an injection from T to R. And you can get that very easily by using ternary notation, where for example 01011101110... maps to 0.02022202220... base 3. That there is a bijection is true, but kind of beside the point here, and it strikes me as a little misleading to drag the reader through all that, as it suggests that it's necessary, which it isn't. --Trovatore (talk) 08:52, 18 July 2017 (UTC)

I don't really care either way. In order to avoid such back-and-forths—it hasn't stopped yet—, something should be there that is backed up by a proper inline source. - DVdm (talk) 09:06, 18 July 2017 (UTC)

In order to find a source, I looked up Cantor's 1891 article and Halmos' 1968 textbook "Naive Set Theory" (German translation 1976). Both give the proof that the article explains under Cantor's_diagonal_argument#General sets, hence they aren't concerned about applying it to natural and real numbers. Unless we eventually find a better apraoch in literature, I'd agree with Trovatore's suggestion to simplify the proof by restricting to construct an injection. I also agree that using ternary numbers is a good idea; mapping e.g. 01011101110 to 0.01011101110 is even simpler and does the trick, too. - Sorry for my precipitate revert of DVdm's edit. - Jochen Burghardt (talk) 09:34, 18 July 2017 (UTC)

On second thought, using (most familiar) decimal numbers is more understandable to a broader audience, and mapping e.g. 01011101110 to 0.01011101110 will still do the trick. - Jochen Burghardt (talk) 09:39, 18 July 2017 (UTC)

Jochen, no problem :-)

Indeed, decimal numbers are more understandable, even if I wouldn't object to the ternary numbers either, provided—again—that an inline source is attached to it. They tend to nip back-and-forths in the bud. - DVdm (talk) 09:50, 18 July 2017 (UTC)

 

(ec) Well, the nice thing about ternary is that it naturally gives you the middle-thirds version of the Cantor set, and that could be mentioned.

But as DVDm says, we really shouldn't be giving original proofs here, even if they're routine (I haven't read WP:CALC recently but I doubt it extends that far). In fact it's not clear that we need to be giving proofs at all, other than the diagonal argument itself, and that one only because it's the subject of the article. I wouldn't want to be hardnosed on that point; it's a very natural question for the naive reader as to what all this has to do with the reals, and we should probably say something about it, but I think a textbook-style exposition is out of line. --Trovatore (talk) 09:55, 18 July 2017 (UTC)

I found a German source in

Erich Kamke (1965). Mengenlehre. Sammlung Göschen. Vol. 999/999a (5th ed.). Berlin: de Gruyter..

Kamke uses decimal numbers and omits sequences ending in '00000...' to get injectivity. I locally upload a scan File:Kamke.1965.012.jpg of his proof for the sake (and time span) of this discussion, hope that is covered by fair use. I'll try to find out whether an English translation exists, so we could cite that. - Jochen Burghardt (talk) 11:16, 18 July 2017 (UTC)

Probably,

Erich Kamke (1950). Theory of sets. Dover series in mathematics and physics. New York: Dover Publications. ISBN 978-0486601410. {{cite book}}: Cite has empty unknown parameter: |month= (help)

is an English translation. we could cite it with §3 (which should agree to the German version), rather than with the page number. - Jochen Burghardt (talk) 11:45, 18 July 2017 (UTC)

I partially agree with Trovatore, that it is significantly simpler to use ternary expansions to construct a bijection to a subset (actually the Cantor set!) I do think that some mention should be made, however, of why the naive binary expansions don't quite work. The technical details of separating out the so-called "problem elements" can probably be left out of the article; simply noting that they form a countable subset is sufficient. Sławomir Biały (talk) 14:19, 18 July 2017 (UTC)

Since there are no other suggestions, I came up with the following text, intended to replace section Cantor's diagonal argument#Real numbers:

The uncountability of the real numbers was already established by Cantor's first uncountability proof, but it also follows from the above result. Each infinite sequence from T, like e.g. s₅ = (1,1,0,1,0,1,1,...), can be mapped in a unique way to a decimal representation of a real number in the interval [0,1), e.g. f(s₅) = 0.1101011...; this defines an injective function f: T→R. Hence if R was countable, i.e. if another injective mapping φ: R→N existed, then the composition φ∘f: T→N was injective, too, contradicting the above-proved uncountability of T. For this reason, the set R of all real numbers is uncountable. In textbooks, the uncountability proofs of T and R are often amalgamated.

References

The introductory sentence is unchanged. I omitted the argument about [0,1] and R having the same cardinality, and the introduction of ${\mathfrak {c}}$ and $2^{\aleph _{0}}$; thus saving the tan(.) stuff. The Kamke reference doesn't fit perfectly, but I think, when called "amagalmated", it will do. A note about ternary numbers and Cantor sets could be added; however, I didn't dare, since originally the issue was to give a reference, not to add more unreferenced text. Comments are welcome. - Jochen Burghardt (talk) 11:17, 10 August 2017 (UTC)

Since there is concern about a lack of reference in the "Real Numbers" section, I have added a reference. I was the one who was responsible for putting in the current proof and failed to put in a reference. The proof technique may be "too clever", but I deserve no credit for it. It was devised by Cantor. So I have put in a reference to Cantor's work and apologize for not putting in a reference in the first place.

My reason for rewriting the "Real Numbers" section years ago was my attempt to resolve the issues raised in the Talk sections: #About the "Real numbers" section: Can we remove the assertion "(I)t can be shown ..." and just show it? and #About the "Real numbers" section - 2. My reply to these Talk sections is in: #Changes to "Real numbers" section.

As for my opinion in the present discussion, I'm happy with any proof that is clear and convincing to the readers. However, the recent suggested change is only proving the uncountability of R. I think that we should prove the stronger result that T and R have the same cardinality. If you want to just prove that the uncountability of T proves the uncountability of R, you might consider the approach of using binary representations of reals that is in Georg Cantor and Transcendental Numbers, p. 823. Applying this approach to the argument above, you get a bijection from T to the binary representations of the reals in [0, 1]. If [0, 1] is countable, this set of binary representations is also countable and you have a contradiction. However, my preference when dealing with Cantor's work is to present constructions like he did—he gave constructive arguments in his work despite what many people think. - RJGray (talk) 18:46, 17 August 2017 (UTC)

Rewrite of "Real numbers" section

Since I'm the one responsible for the rewrite of the "Real numbers" section that has generated so much discussion, I've decided to do a second rewrite. In this new rewrite, I've kept in mind the reasons behind my first rewrite and I have also been influenced by the current discussion (#Proof of uncountability of R is too clever).

To start: Trovatore wants an injection from T to R and Sławomir Biały wants some mention of why naive binary expansions don't quite work. Both are handled in the second paragraph of the rewrite: It starts off pointing out why the naive function f(t) = 0.t doesn't quite work, then the naive function is modified slightly to produce an injection.

Trovatore makes the excellent point that the current first paragraph just states that the uncountability of the reals follows from the uncountability of T, so why bother to construct a bijection? This is handled by the new first paragraph, which makes the same statement about the uncountability of the T implying that R is uncountable. However, it also points out that T and R have the same cardinality. If we are going to bring the real numbers into a discussion about T, I think that readers should be told that these sets have the same cardinality.

I do recognize that some readers may not be interested in the bijection construction, which is more complex that the injection construction. So now it starts off "hidden." However, I do see value in having a "hidden" bijection construction. The problem of "how to place the set T and the real numbers into one-to-one correspondence" was brought up earlier on this Talk page (see #About the "Real numbers" section: Can we remove the assertion "(I)t can be shown ..." and just show it? and #About the "Real numbers" section - 2). So there is interest in a bijection construction. This is why I put in such a construction years ago (this construction has been in the article since 5 February 2011). Also, as this rewrite points out, an 1878 method devised by Cantor is used to construct the bijection. So a construction method is used that was available when Cantor's devised his diagonal argument (an example of a later construction method is to build injections from T to R and R to T and then invoke the Schröder–Bernstein Theorem).

Also, I appreciate the work Jochen Burghardt has done in looking up references for proofs. His work motivated me to trace down the origin of the proof I used in my first rewrite. Not surprisingly, I traced it to Cantor. I've read a lot of Cantor's works and tend to use his arguments rather than more modern ones. I was pleased that Trovatore labeled the proof as "too clever" because he was really complimenting Cantor whose work I admire greatly.

I hope this rewrite is considered better than my last one. I welcome your comments and corrections. --RJGray (talk) 20:22, 22 August 2017 (UTC)

@RJGray: Thank you for your rewrite. I agree with having a simple proof of uncountability of R and a more complicated proof of T and R having the same cardinality. In the proof box for the latter, I experimented with {{multiple image}}; feel free to revert if I overlooked some drawbacks of that template.

For the simple uncountability proof, I still think it would be easier to use decimal expansions, since they are more familiar, and they circumvent the problem of trailing "1"s. I can imagine two reasons for keeping binary expansions: (1) as a preparatory step for the proof box (however, after careful reading I think it is understandable by its own); (2) following a historical proof from Cantor (however, no reference different from that in the proof box is given; also, we might trade simplicity for historic authenticity in the simple proof part, anyway).

In any case, additionally giving some standard-textbook reference for the simple proof would be a good idea imho; but I'm not sure if the Kamke reference will do. - Jochen Burghardt (talk) 11:32, 24 August 2017 (UTC)

Jochen — Thanks for your work on the proof box—it looks a whole lot better. As far as the simple proof that modifies f(t) to produce an injection, I had several reasons for using it:

• It gives a unity to the section, which currently consists of two ways to modify f(t). The first way is so obvious. It just maps the string 0111… (which makes f(t) non-injective) to someone else on the real line and then generalizes this to all strings ending in all 1's. I think nearly all readers can follow it and won't question its validity. The second way uses the more sophisticated method due to Cantor.
• It's use of binary follows the previous parts of the article that mention binary digits and base 2. The section "Uncountable set" starts with "In his 1891 article, Cantor considered the set T of all infinite sequences of binary digits (i.e. each digit is zero or one)." The first diagram in the article says: "An illustration of Cantor's diagonal argument (in base 2) for the existence of uncountable sets."
• It handles Sławomir Biały's desire of having some mention of why naive binary expansions don't quite work, which I think means why f(t) = 0.t doesn't work. Of course, if we go decimal, I would just move this to the proof box.
• I don't think that binary expansions are that foreign to readers. Most readers are aware that computers work in binary. In fact, I've seen binary numbers used in comics—for example, Foxtrot. I've also seen them in Dilbert comics.

However, I'm okay with whatever readers prefer. Anyone want to comment on this discussion?

Finally, I own a copy of the English translation of the second German edition of Kamke's book. Could you give the chapter and section number of the argument you are thinking of referencing? Also, a sentence or two in German would help me pinpoint the argument. Thanks, RJGray (talk) 20:38, 24 August 2017 (UTC)

In the 5th German Kamke edition, it is Sect.3 "Beispiel einet nichtabzählbaren Menge" ["Example of a non-countable set"], in Ch. I "Aus den Anfängen der Mengenlehre" ["From the beginnings of set theory"] on p.12-13. I wouldn't insist on decimal expansion, it's just a suggestion. - Jochen Burghardt (talk) 21:14, 24 August 2017 (UTC)

Jochen — What a difference a day can make! I remembered that I wrote in #Proof of uncountability of R is too clever: "I'm happy with any proof that is clear and convincing to the readers." Your proof using decimals is much clearer than my modification of the function f(t) = 0.t. As far as unity goes, I've come up with a way to unify your proof with the proof in the proof box. Namely, by defining the family of functions f_b(t) = 0.t_b where b is the base of the numeral system. I then point out that all members of this family excepting f₂(t) are injective and that this function will be modified to produce a bijection. Also, this takes care of ternary numbers, which were mentioned in the earlier section.

Concerning the translation of Kamke's book: Ch. I is "The Rudiments of Set Theory" and Sect. 4 is "An Example of a Nonenumerable Set", pp. 9-10 have the proof. However, it is not a proof using the uncountability of T to prove the uncountability of R. It's a proof of the uncountability of (0, 1] by listing the numbers as nonterminating decimal fractions (e.g., 1/2 = 0.499…) and then changing the numbers on the diagonal. I'm curious if your German 5th edition has a different proof.

So we may be stuck without a reference to your proof, which doesn't bother me since it's so simple it probably won't be questioned. It's so simple that it's just like a small calculation. Math proofs can be verified by just thinking them through carefully. Now and then, I've had to modify one, but most are error-free. Moving away from proofs to discussions about them, then, as we know, even math books can have errors (Cantor's first set theory article#The disagreement about Cantor's existence proof). So verifiability based on books doesn't always work. (However, I am a big fan of references and I'm often adding them, but I do recognize their limitations.)

By the way, I think the likelihood of a published proof deriving the uncountability of R from the uncountability of T is low—nearly all mathematicians would just construct a bijection. It's more likely to appear in Wikipedia because we do expository work and try to reach a broad audience.

I'm posting my most recent re-rewrite on my Talk page. Feel free to change it all you want—after all, you suggested the proof. --RJGray (talk) 17:41, 25 August 2017 (UTC)

@Robert: The Kamke proof appears to be similar in my German edition. I had uploaded p.12-13 here, but they have been deleted meanwhile due to fair-use restrictions. In my above suggestion (dated 11:17, 10 August 2017 UTC), I used "amalgamated" to relate Kamke's proof to the article's. Maybe we could add a similar sentence to your new version, until we find a better reference. I think your version is fine; possibly "0.t_b" should be enclosed in parantheses to avoid parsing "t_b" as an indexed variable. - Jochen Burghardt (talk) 18:33, 26 August 2017 (UTC)

Jochen — Thanks for your help and your feedback. Since the Kamke proof isn't dealing with the implication: "uncountability of T" implies "uncountability of R", I think the reference could just confuse readers. I'm familiar with a number of popular math books and I'll be checking them to see if they prove this implication. I don't quite understand what you mean by "In textbooks, the uncountability proofs of T and R are often amalgamated." Does this mean they are both proved, one after the other, with the diagonal argument?

As for "0.t_b", I used that notation to mimic "0.0111_b", which I have not seen written "(0.0111)_b". So I'm just going to update "Real numbers" as it is on my Talk page and encourage other readers to comment on it. On both issues, I can see valid arguments on both sides so I'd like to hear from other readers. Perhaps, some of the readers who have commented earlier will express their opinions.

Thanks for your short, concise example of an injection from T to R. I think it's the shortest possible example, which should be very convincing to readers. —RJGray (talk) 23:55, 26 August 2017 (UTC)

@Robert: I have to admit I didn't think too much about the "amalgamated" sentence; I wished to express that textbooks usually prove the uncountability of R directly, without proving that of our T first, but in way way that allows for a proof of the latter, too, by trivial modifications (as real numbers are considered infinite digit sequences in the former proof). If you find a better reference in one of your books, the issue is obsolete, anyway. As for the index _b, the current version is ok; unless someone complains about an "undefined variable t_b", we don't need to change "0.t_b" to e.g. "(0.t)_b". - Jochen Burghardt (talk) 07:49, 29 August 2017 (UTC)