Misplaced Pages

Revision as of 23:26, 11 August 2018

Mathematics B‑class High‑priority

This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Misplaced Pages. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics B This article has been rated as B-class on Misplaced Pages's content assessment scale. High This article has been rated as High-priority on the project's priority scale.

This is the talk page for discussing improvements to the Cantor's diagonal argument article. This is not a forum for general discussion of the article's subject.

Put new text under old text. Click here to start a new topic. New to Misplaced Pages? Welcome! Learn to edit; get help. Assume good faith Be polite and avoid personal attacks Be welcoming to newcomers Seek dispute resolution if needed Article policies Neutral point of view No original research Verifiability

Find sources: Google (books · news · scholar · free images · WP refs) · FENS · JSTOR · TWL

Archives: Index, 1, 2, 3Auto-archiving period: 12 months

This page is not a forum for general discussion about Cantor's diagonal argument. Any such comments may be removed or refactored. Please limit discussion to improvement of this article. You may wish to ask factual questions about Cantor's diagonal argument at the Reference desk. Please place discussions on the underlying mathematical issues on the Arguments page.

Archives

Index 1, 2, 3

This page has archives. Sections older than 365 days may be automatically archived by ClueBot III when more than 8 sections are present.

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)

  s_1 = 0 0 1 ...
  s_2 = 1 0 1 ...
  s_3 = 1 1 1 ...

0 1 2 3 4 5 6 7 8 9 ...
+ - * + - * + - * ...

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 ${\displaystyle \infty }$. But here's the catch: "${\displaystyle \infty }$" is not a real number (just an abstract mathematical symbol), though together with "${\displaystyle -\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 ;

Then why not just use an open interval in step 1? -Grick() 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 . 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 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 ${\displaystyle 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 , since we can write the Cauchy sequence ${\displaystyle 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)

Constructivist interpretations

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

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

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

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

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

Could someone explain how ${\displaystyle f:s\rightarrow T}$ can have a partial surjection (i.e. be subcountable)? If the proof shows that there exists ${\displaystyle T_{x}}$ such that there does not exist a corresponding ${\displaystyle s_{x},}$ doesn't that mean that f is not surjective? If I'm understanding partial surjection correctly, it just means that the function is surjective and it is also a partial function. If f is not surjective, how can it have a partial surjection? StardustInTheDark (talk) 15:10, 25 November 2017 (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 + s_i,2 x 2 + s_i,3 x 2 ...  ? --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. ${\displaystyle 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 .

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 is defined on W tems for even indices only: g(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 and f₀). The remaining W terms are mapped to V terms and cover T₁ set. This way we get a desired S → T bijection:

${\displaystyle 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, 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 ${\displaystyle T\to \mathbf {R} }$ and ${\displaystyle \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 ${\displaystyle \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 ${\displaystyle \mathbb {N} }$.

These steps contain three crucial comparisons:

1. Between S and ${\displaystyle \mathbb {N} }$ (step 1).
2. Between T and S (step 3).
3. Between T with ${\displaystyle \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:

${\displaystyle |\mathbb {Z} |=2|\mathbb {N} |=|\mathbb {N} |}$

${\displaystyle |\mathbb {Q} |=|\mathbb {N} |^{2}=|\mathbb {N} |}$

In short, ${\displaystyle |\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,

${\displaystyle |\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:

${\displaystyle \aleph _{0}+1=\aleph _{0}}$

${\displaystyle \aleph _{0}\cdot n=\aleph _{0}}$ (n = 1, 2, 3, ...)

${\displaystyle {\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₀.
• 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 , 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 ${\displaystyle \mathbb {N} }$ and S, if there existed (contrary to what we concluded above) a bijection between T and ${\displaystyle \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.

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)

Confusion

In the section An uncountable set, it says

This sequence s_i is countable, as to every natural number n we associate one and only one element of the sequence.

And then below the example sequence, it goes on to state

For each m and n let s_m,n be the n element of the m sequence on the list. So, for instance, s_2,1 is the first element of the second sequence.

Is the n above and below the same? The same goes for the words "sequence" and "element".

Above the example sequence, the text appears to use the terms "sequence" and "element" in terms of the higher hierarchy, i.e. "sequence" referring to the list of numbers, and "elements" referring to individual sequences (i.e. lines), and n appears to refer to the numbering of the elements of the list of sequences.

Below the example sequence, individual sequences from the list (i.e. the "meta-sequence") are discussed as sequences, and now "element" refers to the position after decimal point within each individual sequence.

Could this be clarified? Maybe I'm just not understanding it properly, but I believe it's not just superficially confusing but actually nonsensical because the same terms (and the variable n) are used first in higher-order context, then in lower-order context. Or am I missing something here? --84.44.158.71 (talk) 18:38, 6 October 2012 (UTC)

No, there's no confusion as both n are preceded by words 'every' or 'each'. These two are separate statements, each of them describes its domain and each of them uses its own n to denote a variable from the domain. Of course we might force using different character to denote variables for each sentence in the text, but there is no need to do so. Anyway our alphabet is too short to do that even in medium-size mathematical text, not to mention integral tables... --CiaPan (talk) 18:51, 7 October 2012 (UTC)

And there's no 'decimal point' in any of the sequences discussed in that section. --CiaPan (talk) 18:38, 9 October 2012 (UTC)

You don't understand the mathematics involved. --213.196.218.202 (talk) 11:48, 6 November 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. Misplaced Pages 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 ${\displaystyle \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 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 Misplaced Pages: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: 'Misplaced Pages does not publish original thought: all material in Misplaced Pages 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 "Misplaced Pages 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 Misplaced Pages 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)

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 (), and left another warning at anon's talk page (). - 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)

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

1. :Erich Kamke (1950). Theory of sets. Dover series in mathematics and physics. New York: Dover Publications. ISBN 978-0486601410.

The introductory sentence is unchanged. I omitted the argument about and R having the same cardinality, and the introduction of ${\displaystyle {\mathfrak {c}}}$ and ${\displaystyle 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 . If 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)

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)

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" , in Ch. I "Aus den Anfängen der Mengenlehre" 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 Misplaced Pages 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)

Does this create only a single sequence that falls outside of the enumeration rules?

I'm not a mathematician, but the way the article is currently worded, a very cursory glance implies that this argument results in the construction of one and only one sequence that is present in the collection but not given in the enumeration.

If that is the case, why couldn't the enumeration rules be redefined to simply give that one single special case as S1 as the rest of the sequences starting at S2, S3, S4, etc. ? Seems like a rather obvious solution. If functions can have piecewise definitions; why not enumerations? Element S1 equals == Foo, Elements S2-S == Bar.

The article on countability says "Whether finite or infinite, the elements of a countable set can always be counted one at a time and, although the counting may never finish, every element of the set is associated with a unique natural number." Right. I think I get that. So, uhhhhhh...just adjust your enumeration ordering rules to be slightly messier. Problem solved? At least in the context of Cantor's Argument.

But if Cantor's argument implies the existence of more than one sequence excluded from the enumeration and these exclusions cannot be ordered, perhaps the article could make that more clear?

I'm not trying to claim I've revolutionized mathematics here with my 5 minutes of article skimming and thought; I'm just saying the description of the proof as-is fails to clearly explain why one could not write a set of piecewise-defined enumeration rules to put the elements of T in a one to one relationship with the natural numbers. Blue Rock (talk) 19:52, 25 October 2017 (UTC)

No, the proof is fine as it is. What you're missing is that the proof works for any proposed enumeration. If there is one, you reach a contradiction; therefore, there isn't one. This is a fundamental point of logic.

If you want to discuss how the point can be made clearer, we can do that here, but if you want more explanation on a personal level, please ask a question at WP:RD/Math. --Trovatore (talk) 20:01, 25 October 2017 (UTC)

I understand how proof by contradiction works, thank you. Please read my post more carefully. The article does not explain at all how this would apply to any possible enumeration scheme; in fact it completely glosses over Cantor's chosen scheme, which I have not dissected or thought about yet in any great detail. If Cantor's diagonalization argument does not construct more than this one single contradiction, then one could simply construct a new enumeration scheme simply by specifying that one known, definable sequence as my S1, then use Cantor's rules--new S2 is Cantor's S1, new S3 is Cantor's S2, etc. I'm still reading but the article on this argument, as it is currently worded, does not appear to address how Cantor's diagonalization could be used to rule out piecewise defined enumeration rules. Blue Rock (talk) 20:15, 25 October 2017 (UTC)

The article does in fact explain how it would apply to any possible enumeration scheme. --Trovatore (talk) 20:18, 25 October 2017 (UTC)

Mmmm... sort of. Not terribly well but yes after a few more minutes of thought I think I see what the main idea is that I've completely overlooked here. The construction of the contradiction is permitted to be even more "piecewise" as you are basically are allowed to "look" at the entire sequence and contradict each term individually. Uh, well ok then. Nevermind. There is actually still an interesting argument (not for this talk page, sure sure) to be had here in that what happens if you allow the rules for enumeration to explicitly contradict the rules for generating the contradicting sequence, which results in an undecidable stalemate (between the enumeration ruleset would be trying to defeat the ruleset for generating the contradiction). I grant that said stalemate would result in no enumeration being possible for an infinite set of infinite sequences, so in that respect I guess Cantor wins. But what do you call a self-referential set of rules that cannot in fact end up generating any enumeration because they (impossibly) seek to deny the possibility of this particular hand-crafted contradiction? The rule set I am describing exists. It has no logically consistent interpretation, but it surely exists in the same way that undecidable statements in formal logic exist.

So...on reflection, I must insist I do still have a point, but it's convoluted enough to fall outside of the scope of the article. Carry on, then. Blue Rock (talk) 21:02, 25 October 2017 (UTC)

Summary: my own brief comprehension issue was that in the "Uncountable set" section, the article did not seem to provide either the function to generate the ordered sequences or the function to generate the contradiction. If it had, it might have been clear at a glance that a generalization of the formalization to generate the contradiction was, well, just a wrapper around the function to generate the sequences. In that case, of course you can't ever beat it. But you CAN "tie" it. If the function to generate the ordered sequences were able to refer to the function that generates the proof-by-contradiction sequence--if it were a FAIR fight, so to speak, with the contradiction function and the enumeration function both allowed to refer to each other--you could at least create an unsolvable contradiction such that no stable enumeration was possible. Which I maintain is not the same thing as merely generating an incomplete enumeration. The significance of that observation, I don't know. But I do believe I have a small point here about the clarity of the article, and there is thus an argument for a more formal treatment in the Uncountable Set section, though I'd understand if we're just trying to keep the example as simple to grasp as possible. But these misunderstanding will tend to crop up when infinity is involved. Blue Rock (talk) 21:51, 25 October 2017 (UTC)

"Cantor" as agent in the argument

As the article currently explains the argument, there's a lot of Cantor does this, Cantor does that, as though he were personally constructing the counterexample to a proposed enumeration.

I know we didn't actually invent this style; I've seen it before, and it probably does exist in some RS. But that doesn't mean we have to use it. It kind of grates on me. Does anyone object to changing the exposition so that we can give Cantor's spirit some rest, instead of constantly requiring him to be involved in the argument? --Trovatore (talk) 22:18, 25 October 2017 (UTC)

Cantor killed my father. He deserves no rest. Blue Rock (talk) 22:19, 25 October 2017 (UTC)

(I have no opinion on it as a matter of style but I did feel unable to resist adding that, sorry) Blue Rock (talk) 22:21, 25 October 2017 (UTC)

Trovatore makes a good point that Cantor is mentioned too often in the diagonal argument proof. I eliminated some of the mentions of Cantor and only kept those relevant to the strategic decisions that he made. Namely, he separated his proof into two parts: a constructive part and a proof by contradiction to prove uncountability. This mention of Cantor is important because it's historically accurate and because Cantor used this approach whenever possible. Too many accounts of Cantor's work leave out the constructive part of his proofs. This has led to Cantor being credited for non-constructive proofs that he did not publish and then these proofs are critiqued as just pure existence proofs. Another example of Cantor giving constructive arguments can be found in Cantor's first set theory article where his constructive argument leads to both the construction of transcendental numbers and the uncountability of the real numbers. By the way, I also made a small change to the non-constructive proof of "T is uncountable" that clarifies the contradiction. --RJGray (talk) 21:50, 14 January 2018 (UTC)

Interpretations section

This is currently very problematic, as it claims that the reals can be subcountable in constructivist logics, which as far as I know is not true. In constructivism, Cantor's diagonal argument simply shows that the natural numbers (any countable set) cannot "exhaust" the reals, but indeed there is a trivial injection from the naturals into the real, so the reals can hardly be subcountable!

2A02:C7F:C617:6600:8426:D508:2908:C46F (talk) 21:46, 28 October 2017 (UTC)

du Bois-Raymond and Cantor's diagonal argument

An edit saying du Bois-Raymond invented the argument earlier was reverted, correctly I believe. However there probably should be something here about the attribution and why it is wrong and there is the chance that Cantor was inspired by d Bois-Raymond's proof as he had an interest in infinity and infinitesimals. See note 1 page 187 in Simmons, Keith (1993). Universality and the Liar: An Essay on Truth and the Diagonal Argument. CUP. p. 187.. Dmcq (talk) 18:02, 9 January 2018 (UTC)

The line removed was

Historically, the diagonal argument first appeared in the work of Paul du Bois-Reymond in 1875.

Dmcq (talk) 18:09, 9 January 2018 (UTC)

The article does not include any proof that "there are actually more infinite sequences of ones and zeros than there are natural numbers."

The article asserts that:

the diagonal argument establishes that, although both sets are infinite, there are actually more infinite sequences of ones and zeros than there are natural numbers.

No, it doesn't. The diagonal argument only establishes that, given an enumeration of real numbers, which is not an enumeration of all real numbers, then another real number can be defined in terms of that enumeration. Form this we can further conclude that there cannot be an enumeration of all real numbers, since then we would have a number that was both in and not in the enumeration.

What the article omits is that the notion that the reals constitute some sort of "bigger" infinity arise from one specific argument, which involves different levels of language, for example:

If every real number could be expressed in some language as some finite combination of symbols, then we could easily have a method of matching the natural numbers to these combinations of symbols. All that is required is an alphabetical style ordering of all the symbols used to define real numbers (in the same way as a, b, c … is the order for the English alphabet), and then you simply list them in the same way as you would order the words in a dictionary. And if you could list them, you can obviously attach natural numbers to every item in the list. But this would contradict the Diagonal argument, so there must be real numbers that cannot have any finite representation.

However, that argument forces the enumeration of the reals to be in a different language system (a meta-language) from the real numbers of the list, where every combination of symbols that defines a real number in that system is simply an object in that meta-language, and which has no inherent numerical value in that meta-language. Hence that meta-language has no method of generating a diagonal number from that enumeration.

In short, that argument introduces different levels of language while at the same time completely ignoring whether that introduction of different levels of language might affect the overall proof. — Preceding unsigned comment added by Jamesrmeyer (talk • contribs) 14:56, 12 January 2018 (UTC)

Different languages are irrelevant to the proof. A particular real number stays the same real number however it is represented and they can all be represented as a sequence of 0's and 1's. The construction would produce a number not in the sequence . If it was in the weird symbols sequence then the number in 0's and 1's would be in the 0's and 1's sequence. Dmcq (talk) 08:54, 15 January 2018 (UTC)

The assertion that all real numbers "can all be represented as a sequence of 0's and 1's" is patently false. On the other hand it can be asserted that every real number has an expansion in whatever base one chooses. And that irrationals have infinite expansions in every base - hence irrationals cannot have any representation as a sequence of 0's and 1's.

The point made was that the diagonal argument, of itself, does not establish that there are "more infinite sequences of ones and zeros than there are natural numbers." And as I pointed out above, any proof that there are "more infinite sequences of ones and zeros than there are natural numbers" requires an argument that specifically necessitates an introduction of different levels of language.

Hence the claim that "Different languages are irrelevant to the proof" is inherently absurd, since different levels of language are necessarily used to obtain the result that there are more real numbers than natural numbers, which is a result that is additional to the result that there cannot be an enumeration of real numbers.

I would note that the definition of a diagonal number is a definition that is stated in terms of the enumeration function, and hence that definition has to be in the same language system as that enumeration function. If one wants to imagine a method of circumventing this inconvenient fact, then one can plead a reliance on Platonist assertions that real numbers somehow "exist" independently of any definition, and by this pleading any considerations of language are ignored. When that is done, it is hardly surprising that one ends up with the conclusion that there "exist" real numbers that have no finite definition. Jamesrmeyer (talk) 13:07, 15 January 2018 (UTC)

Using base two all real numbers can be represented as a sequence of 0's and 1's, exactly the same as in base ten they can be represented as a sequence of the digits from 0 to 9. There are no real numbers which can be represented in one but not the other. Hyper languages do not magically generate more real numbers. For instance π in binary starts 11.001001000011111101101010100010001000010110100011... Dmcq (talk) 14:19, 15 January 2018 (UTC)

You don't seem to understand the difference between a representation and a definition that defines an infinite expansion (which can never be represented). The base is irrelevant - irrationals have infinite expansions in every base.

But tell you want, just write down a representation of an irrational's infinite expansion for me and then I will concede. Jamesrmeyer (talk) 19:32, 15 January 2018 (UTC)

I am sorry but it is not my job to convince you of anything. The purpose of this page is to propose improvements using WP:reliable sources. If you can find some reliable source for what you are saying then I'll look at that. Dmcq (talk) 20:42, 15 January 2018 (UTC)

It is the job of Misplaced Pages to convince people of what it asserts. I pointed out that while there is a claim under the Interpretation heading that claims

"the diagonal argument establishes that, although both sets are infinite, there are actually more infinite sequences of ones and zeros than there are natural numbers."

the previous section only referred to a proof regarding the presence or absence of a total enumeration. Hence there should be some evidence provided for the additional assertion that there are more elements of one set than the other. Jamesrmeyer (talk) 22:13, 15 January 2018 (UTC)

• B-Class mathematics articles
• High-priority mathematics articles