Talk:Cantor's first uncountability proof

WikiProject Mathematics (Rated B-class, Low-importance)
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
 B Class
 Low Importance
Field: Foundations, logic, and set theory

Older discussion is archived at /Archive1

The rationals

Copied from the main article:

(Could someone who understands explain why the set of rational numbers does not have property 4?)

Property 4 says that if you partition the set into two halves, then there must be a boundary point in the set. This is not true for the rationals: take as A the set of all rationals smaller than √2 and as B the set of all rational above √2. Then all rationals are covered, since √2 is irrational, so this is a valid partition. There is no boundary point in the set of rational numbers that separates A from B however. AxelBoldt 02:09, 23 May 2006 (UTC)

• Ok, but could you clarify a little please... in as much as if you have your boundry, and A contains the elements less that that boundry, and B the elements greater than it, the the boundry is not in A or B. Probably missing something here, just can't see what.
• That isn't a partition. If c is in R, then for {A,B} to be a partition of R, c needs to be in A or in B. Eg, for property 4, c would have to be either the largest member of A or the smallest member B. Aij (talk) 02:13, 15 April 2008 (UTC)

@AxelBoldt - In your example, why can't the boundary point be the largest rational in A or the smallest rational in B? Then, all rationals less than the boundary will be in A and all rationals greater than the boundary will be in B. Or am I misunderstanding the meaning of the word "every point" as "every point in R"? Vijay (talk) 08:36, 11 January 2010 (UTC)

Axel may not be watching anymore — he made that comment in 2006.
Anyway, for A and B as defined, A doesn't have a largest element, and B doesn't have a smallest element. --Trovatore (talk) 09:40, 11 January 2010 (UTC)

There's an explicit exercise in Walter Rudin's Principles of Mathematical Analysis that asks the student to show for any rational number less than √2 how to find a larger rational number that is still less than √2, and similarly for those larger than √2. Michael Hardy (talk) 02:04, 24 January 2010 (UTC)

For Failed to parse (unknown function "\lt"): a\lt\sqrt2

, one possible choice would be $a+1/\lceil1/(\sqrt2-a)\rceil$. Paradoctor (talk) 13:27, 16 December 2013 (UTC)

Proposed Changes to Article

I am very happy to see a Wikipedia article about Cantor's first uncountability proof. Since I have studied Cantor's 1874 article and some of his correspondence, I started adding material and making some changes. The result of this work can be found at: Talk:Cantor's first uncountability proof/Temp. I hope you find my revisions interesting and relevant. I'm looking forward to your suggestions, modifications, and feedback. Here's a section-by-section summary of my revisions:

Introduction: Made some changes and mentioned two controversies that have developed around Cantor's article. The "emphasis" controversy ("Why does Cantor's article emphasize the countability of the set of real algebraic numbers?") is already discussed in the current article. The "constructive/non-constructive" controversy concerns Cantor's proof of the existence of transcendental numbers.

Development and Publication: Expanded the current "Publication" section by adding material that comes mostly from Cantor's correspondence. Like the current section, this new section discusses the "emphasis" controversy, but I did add some material here.

The Article: Replaces the current "The theorem" section. Contains statements of the theorems that Cantor proves in his article. Also, uses Cantor's description of his article to bring out the article's structure. This structure is the key to handling the "constructive/non-constructive" controversy.

The Proofs: Contains proofs of Cantor's theorems.

Cantor’s Method of Constructing Transcendental Numbers: Replaces the current "Real algebraic numbers and real transcendental numbers" section. Also, discusses the "constructive/non-constructive" controversy.

I have also added a "Notes" section, and I have added references to the current "References" section.

I highly recommend reading Cantor's original article, which is at: "Über eine Eigenschaft des Ingebriffes aller reelen algebraischen Zahlen". A French translation (which was reviewed and corrected by Cantor) is at: "Sur une propriété du système de tous les nombres algébriques réels". Unfortunately, I have not found an English translation on-line. However, an English translation is in: Volume 2 of Ewald's From Immanuel Kant to David Hilbert: A Source Book in the Foundations of Mathematics (ISBN 9780198532712).

Most of the material I added to this Wikipedia article comes from Cantor's article, Cantor's correspondence, Dauben's biography of Cantor (ISBN 0674348710), and the article "Georg Cantor and Transcendental Numbers".

Finally, I wish to thank all the people who have worked on this Wikipedia article. Without the excellent structuring of your article and the topics you chose to cover, I suspect that I would not have written anything. (This is the first time I've written for Wikipedia.) It's much easier to add and revise rather than develop from scratch. RJGray (talk) 23:30, 5 May 2009 (UTC)

Rewrote the section "Cantor’s method of constructing transcendental numbers" and renamed it "Is Cantor’s proof of the existence of transcendentals constructive or non-constructive?" The old section did not explain this constructive/non-constructive controversy. The new section quotes mathematicians on different sides of the controversy, analyzes their versions of "Cantor's proof," looks at relevant letters of Cantor's, mentions some computer programs, and then shows Cantor's diagonal method in a simpler context -- namely, generating the digits of an irrational (rather than the more difficult job of generating the digits of a transcendental).

--RJGray (talk) 02:55, 5 August 2009 (UTC)

Oops, I forgot to thank Michael Hardy for the feedback that he has given me on my proposed changes. His feedback made me realize that my old section was inadequate. I hope that my new section is more adequate -- I welcome your feedback on it. --RJGray (talk) 03:11, 5 August 2009 (UTC)

Revisions to proposed changes. I have added more material and restructured my proposed changes. The revised text contains the following sections:

• The article
• The proofs
• Is Cantor’s proof of the existence of transcendentals constructive or non-constructive?
• The development of Cantor's ideas
• Why does Cantor's article emphasize the countability of the algebraic numbers?

The biggest changes are the ordering of the sections, and the last two sections. Now the two mathematical sections come first. This was done for several reasons: Since the introduction is about the mathematics, it's natural that the first sections should be mathematical. Also, these two sections prepare the way for the other sections.

The last two sections are a rewrite of the old section: "Development and publication." This rewrite was necessary because I learned of the book: Labyrinth of Thought: A History of Set Theory and Its Role in Mathematical Thought by José Ferreirós. Ferreirós has a different point of view than Joseph Dauben on who influenced Cantor's article. Hence, I felt that Wikipedia's NPOV policy required that I talk about both Dauben's and Ferreirós' opinions.

Finally, various smaller edits appear in the other sections. I welcome your feedback. --RJGray (talk) 01:54, 23 January 2010 (UTC)

I've moved RJGray's draft to the article space and merged its edit history with that of the article as it appeared before. Michael Hardy (talk) 03:54, 23 January 2010 (UTC)

B class

I am going to change the math rating to B class. Here are my specific thoughts about ways the article could be improved:

• There is an obvious relationship between Cantor's proof and the Baire category theorem: the BCT follows immediately by the same proof technique, and the BCT proves Cantor's theorem as a corollary. Somebody must have discussed this in print.
• Is the claim about certain processes requiring sub-exponential time in the source by Gray? I scanned through the reference, but didn't see it.
• In the paragraph beginning "The constructive nature of Cantor's work is most easily demonstrated by using it to construct an irrational number. " — isn't this using the diagonal method rather than the method of Cantor's first proof? Why not make an example that uses the method of the first proof.

I'll read through the article again today to copyedit again. — Carl (CBM · talk) 13:09, 24 January 2010 (UTC)

Thank you very much for your feedback:

• Concerning the relationship between Cantor's proof and the Baire category theorem: I regard the current article as mostly historical and Baire proved his theorem in 1899. Also, the versions of the Baire category theorem as stated at Baire category theorem require some form of the axiom of choice, which Cantor's methods do not need. So I suspect you are talking about a weaker form of the Baire category theorem. Perhaps a note could be added about the relationship between Cantor's 1874 method and the proof of the Baire category theorem if a source could be located.
• Sorry, I left out some references. I have added references to the locations in Gray 1994 where the computer program times are mentioned. (The sub-exponential time is at bottom p. 822 - top p. 823.)
• The diagonal method was used because it is simpler and the idea was just to demonstrate the constructive nature of Cantor's work. In this section, both of Cantor's methods are mentioned so I felt free to use the simplest method. Using Cantor's 1874 method gives the intervals [1/3, 1/2], [2/5, 3/7], [7/17, 5/12], … or in decimals [.33…, .50…], [.400…, 428…], [.4117…, .4166…], … It seems to me that the number generated by the diagonal method is more easily seen to be irrational than the number generated by the 1874 method. I'd like some feedback from other readers before changing methods. Of course, both methods could be illustrated.
• As for the class rating, I'll let the experts on class ratings discuss this. By the way, could you give me a Wiki reference to the definitions of each rating?

RJGray (talk) 21:34, 24 January 2010 (UTC)

By Baire category theorem I mean: the intersection of a sequence of dense open sets in the real line is dense. This fact does not require the axiom of choice; the proof is completely effective. In particular, if the sequence Un of dense open sets is computable, then there is a computable function that takes a rational interval [a,b] as input and returns a real in $[a,b] \cap \bigcap_n U_n$. The axiom of dependent choice is only needed to prove the version of BCT for non-separable complete metric spaces.
A description of the recommendations for math article assessments is at Wikipedia:WikiProject_Mathematics/Wikipedia_1.0/Grading_scheme. However, the "A" class is in limbo right now: there was a system set up to try to review articles before they were rated A class, but that system never caught on, and now it is defunct. — Carl (CBM · talk) 00:23, 25 January 2010 (UTC)

On Feb. 20, I followed your suggestion of having an example of generating an irrational number by using Cantor's 1874 method. This follows the example of generating an irrational number by using Cantor's diagonal method. — RJGray (talk) 01:19, 3 March 2010 (UTC)

Restrict polynomials to irreducible ones in proof of countability of algebraic numbers?

As far as I understood Cantor's 1874 article, he considers in his proof of countability of algebraic numbers only irreducible polynomials (p.258: "und die Gleichung (1.) irreducibel denken" = "and consider equation (1.) to be irreducible"). These are sufficient to get all algebraic numbers, and each of them corresponds to at most one algebraic number, viz. its root (if in ℝ). In this setting it is more clear what it means to "order the real roots of polynomials of the same height by numeric order" (cited from Cantor's first uncountability proof#The proofs). Maybe the article should also restrict polynomials to irreducible ones - ?

Jochen Burghardt (talk) 15:10, 13 December 2013 (UTC)

I made a list of algebraic numbers, ordered by Cantor's rank, as a collapsible table. Maybe it is illustrative to include it (in collapsed form) into the article. At least I my self learned (1) that "irreducible" should mean "cannot be written as product of smaller polynomials with integer coefficients", and (2) an irreducible polynomial in that sense can well have several solutions; two facts that I should have remebered from my school time. - Jochen Burghardt (talk) 16:40, 13 December 2013 (UTC)

When I wrote the section "The Proofs", my intent was to emphasize the proof of Cantor's second theorem, so I simplified his proof of the countability of algebraic numbers by leaving out "irreducible" so readers wouldn't have to know what an irreducible polynomial is. I'm sorry that you found my method less clear than Cantor's on the ordering of the algebraic numbers of a particular height. Using your enumeration table, the polynomials of height 2 give 0, -1, 1, 0 as roots, so the ordering will be -1, 0, 0, 1. In this enumeration, duplicates often appear within a height and between heights, but Cantor's proof of his second theorem does handle duplicates.
However, you do bring up an excellent question: Shall we mention Cantor's use of irreducible polynomials? I see two ways to mention it: Add it to the text or add a footnote at the end of the paragraph that points out the text's ordering produces duplicates and that Cantor's original enumeration eliminates duplicates by using irreducible polynomials. By the way, the reason for some of the longer footnotes in this article was to explain points in more depth—readers just wanting the main points can skip the footnotes. Which is better in this case? I don't know. Maybe some readers can give us feedback.
I like your enumeration table. A few suggestions: Label it "Cantor's enumeration of algebraic numbers". Change "not coprime" to "not irreducible". Coprime refers to a set of two or more integers so it doesn't apply to polynomials such as 2x. The definition of irreducible polynomial states that: "A polynomial with integer coefficients, or, more generally, with coefficients in a unique factorization domain F is said to be irreducible over F if it is not invertible nor zero and cannot be factored into the product of two non-invertible polynomials with coefficients in F." This definition factors: 2x = (2)(x) and it factors: 2x+2 = (2)(x+1). Finally, the exponent 1 in your table always appears in gray and it's well understood that "x" means "x1". Try leaving out this exponent. I think this might visually simply your table. - RJGray (talk) 01:58, 15 December 2013 (UTC)
When I started this talk section, I had in mind the construction of rationals from integers, and I thought that algebraic numbers could be constructed from rationals in a similar way. The former is done by computing with pairs (p,q) ∈ ℤ×(ℤ\{0}) with the intended meaning p/q; I thought the latter could be done by computing with polynomials, where one polynomial would denote one algebraic number, "viz. its root". Meanwhile I saw that even an irreducible polynomial has several roots, so that there can't be a one-to-one correspondence between polynomials and algebraic numbers, anyway. So I lost my original motivation for asking for irreducibility. Probably the proof is simplest in its current form; maybe a footenote could be added as you suggested.
In the enumeration table, I tried to distinguish several reasons for excluding a polynomial, a non-coprime set of coefficients being one of them, non-irreducibility being another one (admittely subsuming the former); when changing the table to produce duplicates these reasons would disappear, anyway. I used the gray parts to indicate (to myself, in the first place) the systematic way the polynomials are enumerated (nevertheless, I missed all polynomials containing x3 and x4; see the new table; I hope it is complete now ...), but you are right: at least the exponent of "x1" isn't needed for that; I now deleted it. Concerning duplicates: should we have a reason "repetition" (or "duplicate"?) and not assign them a number; or should we assign them a number and mention somewhere that the enumeration is not bijective, but surjective, which suffices for countability? The former case would save some indentation space, since the x4 column could be immediately adjacent to the leftmost (number) column, as in each row at least one of them is empty. The latter case wouldn't save much, as "(-1 ± √5) / 2" (to be kept) is about as long as "repetition". - Jochen Burghardt (talk) 12:38, 16 December 2013 (UTC)
I think some readers may find the current text ambiguous on the question of whether duplicates appear in the sequence (of course, it doesn't matter for applying his second theorem). There are two ways to eliminate duplicates and both give the same result. Below is my first attempt at a footnote to clarify the situation and to introduce readers to Cantor's approach and your table:
"Using this ordering and placing only the first occurrence of an real algebraic number in the sequence produces a sequence without duplicates. Cantor obtained the same sequence by using irreducible polynomials: INSERT YOUR TABLE HERE"
Your table is looking better, some more suggestions: remove the "·" in 2·x, etc. In the enumeration, you can use x1 instead of "1.", etc. (This would connect your table closer to the article where all the sequences are x1, x2, ….) Also, in front of the first coefficient, you can leave out the "+" since every polynomial starts with a positive coefficient. Finally, concerning irreducible polynomials versus coprimes, I apologize for not being clearer. I should have quoted the following from "Irreducible polynomial":
"It is helpful to compare irreducible polynomials to prime numbers: prime numbers (together with the corresponding negative numbers of equal magnitude) are the irreducible integers. They exhibit many of the general properties of the concept of 'irreducibility' that equally apply to irreducible polynomials, such as the essentially unique factorization into prime or irreducible factors:"
This means that you factor 6x = (2)(3)(x). Basically, the terms to use when working with factoring polynomials are "reducible" and "irreducible" (they are the counterparts to "composite" and "prime"). I think that you may be generalizing the term coprime to single integers to handle polynomials, such as 3x, when you call this polynomial "not coprime". I've done a Google search and I only found the term "coprime" referring two or more integers. So I think your table would be more accurate and clearer if you used the term "not irreducible". Also, I have the philosophy of placing minimal demands on the reader (whenever possible). By only using the word "irreducible", the reader is not required to understand "coprime".
I hope you don't mind all my suggestions (I can be a bit of a perfectionist when it comes to tables). I think your table is an excellent addition to the article and will definitely help readers understand the ordering. In fact, it motivated me to reread Cantor's article and I noticed a detail that I had forgotten: Cantor gives the number of algebraic reals of heights 1, 2, and 3, which (of course) agree with your table. --RJGray (talk) 18:20, 17 December 2013 (UTC)
I changed the table according to your suggestions (perfectionism in writing optimizes the overall workload, since the table is written only once, but read -hopefully- a lot of times). Maybe the indices like in x3 should not be in boldface? And: are you sure that no algebraic number may occur as root of two different irreducible polynomials? I've forgotten almost all my algebra knowledge... - Jochen Burghardt (talk) 20:40, 17 December 2013 (UTC)
I like your attitude about perfectionism—I agree, we should think about the reader's workload. I also like the way you nicely simplified the table to have just 2 columns, by putting using "xn =" with the roots. I think that x3 is preferable to x3 because the text doesn't use boldface and it looks better. Some other suggestions: I found double indexing "x11,16" confusing. Try "x11, x16" or, perhaps better, "x16, x11" to match the way that the + of the ± goes with x16, and the – goes with x11 (or maybe there's a minus-plus symbol with minus on top of the plus). Also, I see no need for the large space between the "xn =" and the roots at the top of the table. I can see you're lining up with the roots at the bottom of the table, but on a first reading, many users may not go to the bottom of the table and may wonder about the space. Finally, try moving the "…" over a bit at the end of the table.
Your question about the possibility of an algebraic number occurring as the root of two different irreducible polynomials is very relevant. At the site: Algebraic Number (Encyclopedia of Math), you can read about the minimal polynomial of an algebraic number. This minimal polynomial is the polynomial of least degree that has α as a root, has rational coefficients, and first coefficient 1. It is irreducible. By multiplying by the least common denominator of all its coefficients, you obtain α's irreducible polynomial with integer coefficients that Cantor uses. The minimal polynomial Φ(x) of the algebraic number α can be easily shown to be a factor of any polynomial p(x) with rational coefficients that has root α. You start by dividing p(x) by Φ(x) using long division. This gives: p(x) = q(x) Φ(x) + r(x) where deg(r(x)) < deg(Φ(x)). Assume r(x) ≠ 0. Since p(α) = Φ(α) = 0, we then have r(α) = 0 which contradicts the fact that the minimal polynomial Φ(x) is the polynomial of least degree with root α. So r(x) must be 0. Therefore: p(x) = q(x) Φ(x) so the minimal polynomial is a factor of p(x). --RJGray (talk) 20:32, 18 December 2013 (UTC)
I didn't have web access during xmas holidays, but now I updated the table according to your recent suggestions. There is a "∓" symbol, but I think it looks unusual in an expression, so I instead changed the order of the lhs variables. I moved the final dots into the "=" column and simulated vertical dots by a colon, as I couldn't find an appropriate symbol or template.
I like your suggestion for a footnote containing our table. As you are currently editing the article anyway, would you insert your footnote and move the table? Maybe it is best to remove it from the talk page, to avoid confusion about where to do possible later table edits.
Last not least: Thank you for your explanation why there is only one minimal irreducible polynomial for an algebraic number; it helped me to bring back my memories about algebra. - Jochen Burghardt (talk) 14:09, 27 December 2013 (UTC)
Sorry to be so slow in getting back to you. I've been busy and haven't watching my Watchlist. I see that you've already made the necessary changes, which is great--you deserve the credit. I think that the way you improved your table is much better than my suggestion. Keep up your excellent Wikipedia work! --RJGray (talk) 18:36, 8 April 2014 (UTC)

Contrast 2nd theorem with sequence of rational numbers?

Cantor's 2nd theorem seems obvious at first glance to many people, as we usually are unable to imagine a sequence that could completely fill a whole interval. However, there are sequences (like that of all positive rational numbers) whose set of accumulation points equals a whole interval (or even whole ℝ+; cf. the picture there). Mentioning this in the article might prevent novice readers from thinking "Mathematicians make a big fuzz proving things that are obvious, anyway", and might generally help to sharpen one's intuition about what a sequence can do in relation to an interval and what it cannot. It would require, however, to explain the notion of an accumulation point (which is poorly represented in English Wikipedia in general). - Jochen Burghardt (talk) 11:52, 17 December 2013 (UTC)