Talk:Cardinality of the continuum

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Mathematics (Rated B-class, High-importance)
WikiProject Mathematics
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
High Importance
 Field:  Foundations, logic, and set theory

Proposed lead[edit]

(continuing the above)

The lead prose isn't very good. I think that perhaps mathematicians expect to see statement of "knowns" followed by the statement of "more interesting things." In contrast, good informative English prose puts an interesting fact at the beginning of each paragraph, to let the reader know what they can expect to find. One thing that makes the lead difficult is that both initial sentences are excessively long. Here is a proposed revision. I rearranged a little, tried to remove parenthetical phrases (which always impede readability) and unnecessarily verbose phrases like "sometimes called," and replaced some <math> tags with Unicode to improve page rendering.

The cardinality of the continuum or power of the continuum is the size of the infinite set of real numbers ℝ. It is denoted by |ℝ|, ℶ1 (beth-one), or (a lowercase fraktur script c).

1 is a transfinite cardinal number. It is greater than ℶ0, also known as ℵ0 (aleph-naught), the smallest transfinite, which represents the size of the set of natural numbers. These quantities were first distinguished by Georg Cantor in his 1871 uncountability proof, part of his greater study of different infinities.

There may be no cardinal numbers between |ℕ| = ℶ0 and |ℝ| = ℶ1, if the continuum hypothesis holds. In that case, ℶ1 is furthermore identical to ℵ1.

Things I removed:

  • "In mathematics": this only slows the reader. It is apparent that we are talking about math.
  • That the continuum is the set of real numbers. The link to Continuum (set theory) is removed, but that article only seems to restate a few things from real number. Anyway, this seems obvious and/or unnecessary, and can probably be re-added without crufting it up too much.

As for "Potatoswatter still cannot see how many logical steps are taken for granted there"… I never said it was a good proof, but we are not critiquing mathematical rigor here. The next thing I would criticize, after failure to put the conclusion in context, is that there is too much algebra. The change of base is unnecessarily cryptic. Of course, taking transfinite arithmetic for granted pretty much reduces it all to nonsense.

Michael, does this look better? Potatoswatter (talk) 04:18, 28 May 2011 (UTC)

Looks better. Might be worth mentioning the power set and/or |ℝ| = 2|ℕ|. -- cheers, Michael C. Price talk 11:40, 28 May 2011 (UTC)
Overall, it is a good job. Here are my suggestions for improvement:
  • Wikipedia articles in math commonly start with "In mathematics", "in linear algebra", "in set theory", "in geometry", etc. Here, "in set theory" seems appropriate and useful to me, as it provides a context, and a link from which a beginner can start studying the topic.
  • The sentence "|ℝ| is greater than |ℕ|, which represents the size of the set of natural numbers" must be highlighted, as it is the most interesting piece of information in the lead. It really catches the attention of beginners, as the notion of "different infinites" is highly counterintuitive, almost unbelievable for those who don't know set theory. SO, it should be at the beginning of a paragraph. Your text does not fail to provide this information, but the sentence is mixed with less important details. For instance "the smallest transfinite" is a detail that should not be in the middle of this sentence.
  • I suggest to use |ℝ| and |ℕ| as the first symbols given for both the sizes of R and N. They are easy to remember, and |ℝ| is the first symbol given for the cardinality of the continuum.
So, here's how I would write the introduction (I showed in bold typeface the parts I edited; I also rearranged the second paragraph):
In set theory, the cardinality of the continuum or power of the continuum is the size of the infinite set of real numbers ℝ. It is a transfinite cardinal number, denoted by |ℝ|, ℶ1 (beth-one), or (a lowercase fraktur script c).
The cardinality of the continuum is greater than the size of the set of natural numbers, denoted as |ℕ|, ℶ0 (beth-zero), or ℵ0 (aleph-naught). These quantities were first distinguished by Georg Cantor in his 1871 uncountability proof, part of his greater study of different infinities. Cantor showed that |ℕ| is the smallest transfinite cardinal number, and |ℝ| coincides with the size of the power set of ℕ, thus |ℝ| = 2|ℕ|. As a consequence, |ℝ| > |ℕ|.
If the continuum hypothesis holds, there are no cardinal numbers between |ℕ| = ℶ0 and |ℝ| = ℶ1. In that case, |ℝ| is furthermore identical to ℵ1 (aleph-one).
Paolo.dL (talk) 12:26, 29 May 2011 (UTC)
I like it. -- cheers, Michael C. Price talk 16:57, 29 May 2011 (UTC)
I also suggest to use the <math> format for ℝ, ℕ, ℶ and ℵ (see current format in the lead), because in Internet Explorer 9, with zoom 100%, the Unicode format suggested above is too small to show the correct shape of these letters (particularly aleph and beth). The <math> format is also used in the articles Aleph number and Beth number. Paolo.dL (talk) 19:31, 29 May 2011 (UTC)

Pretty productive changes mostly. I'd trim it back a little and try to reduce the average sentence length.

  • Maybe better to stick with one name for the cardinality of the naturals. ℶ0 needs less introduction because the first sentence contains ℶ1, and ℵ0 is very famous, but I think |ℕ| has the best of both worlds — analogy to the previously-mentioned concepts and very common usage.
  • Separate notation from basic definition in the first paragraph. This improves flow, and segues into the math.
  • I'm suggesting to begin the second paragraph with a symbol, simply because the proper name is so verbose.
  • Break up sentences in the second paragraph. Group math at the beginning and bio at the end. Spruce up bio.
  • Remove "size of the" and magnitude signs, and replace notion of causality with mere difference of notation, in the new sentence of the second paragraph.
  • Just a note, "As a consequence, |ℝ| > |ℕ|" is a simple restatement of the paragraph thesis. I think it's worthwhile here, but there's an element of "repetition in lieu of proof."
  • Avoid starting the third sentence with a clause about the continuum hypothesis. Beginners may be interested to know that there is perhaps no x for |ℕ| < x < |ℝ|, or that the status of this inequality is unknown. That motivates moving on to the hypothesis. Perhaps my original text was problematically ambiguous; I fixed that by breaking up the sentence.

I'm OK with going back to TeX formatting. The problem on Firefox is that math renders larger than the rest of the text, but a problem with smallness trumps that.

In set theory, the cardinality of the continuum or power of the continuum is the size of the infinite set of real numbers ℝ. It is denoted by |ℝ|, ℶ1 (beth-one), or (a lowercase fraktur script c). It is a transfinite cardinal number.

|ℝ| is greater than the size of the set of natural numbers, denoted as |ℕ|, which is the smallest transfinite cardinal number. ℝ coincides with the power set of ℕ, denoted ℝ = 2. As a consequence, |ℝ| > |ℕ|. This was proven by Georg Cantor in his 1871 uncountability proof, part of his groundbreaking study of different infinities.

There may be no cardinal numbers between |ℕ| and |ℝ|. This is true if the continuum hypothesis holds. In that case, |ℝ| is furthermore identical to ℵ1 (aleph-one), the second-smallest transfinite cardinal number.

Potatoswatter (talk) 07:16, 30 May 2011 (UTC)

  • ℝ = 2 is clearly wrong. I wish it were true: it would make our job simpler. As Michael C. Price suggested, we need to state the relationship between |ℝ| and |ℕ|, i.e. |ℝ| = 2|ℕ|. In this context, this is an important piece of information.
  • I would rather not remove the alternative symbols for |ℕ|. They are useful as readers can compare them with the corresponding symbols for |ℝ|, and understand the subscripts for aleph and beth. (I know you don't like parentheses, but they can be removed without removing the symbols.)
  • Good job in the third paragraph (thank you for correctly guessing and respecting my rationale).
Paolo.dL (talk) 08:22, 30 May 2011 (UTC)
ℝ = 2 does seem incorrect. Perhaps |ℝ| = 2|ℕ|, or ℝ = ℘(ℕ). (Symbol being copied from power set.) These changes seem more mathematically accurate, although, as an expert mathematician, I can't really say whether it's more understandable. — Arthur Rubin (talk) 09:19, 30 May 2011 (UTC)
The reals and the powerset of the natural numbers are not the same set, and the article makes no such claim. However, they are equinumerous as the article proves. JRSpriggs (talk) 11:29, 30 May 2011 (UTC)
Arthur, when you wrote ℝ = ℘(ℕ) what did you mean? As far as I understand, ℘(ℕ) is just another symbol for the powerset of ℕ (denoted 2 in previous contributions). In this case, ℝ = ℘(ℕ) can't be correct, as by definition the power set of ℕ is different from ℝ (they only have "a few" elements in common). JRSpriggs, we are discussing a proposal by Potatoswatter for a new lead (see comment posted at 07:16, 30 May 2011). Paolo.dL (talk) 11:41, 30 May 2011 (UTC)
|ℝ| = 2|ℕ| is fine with me. -- cheers, Michael C. Price talk 13:01, 30 May 2011 (UTC)

TeX versus Unicode symbols for [edit]

On a computer with Windows XP and Internet Explorer 8 (standard settings; UTF-8 encoding), both updated with Microsoft Update, I cannot correctly visualize the Unicode symbols for aleph, beth, R and N used by Potatoswatter. I see a square instead. The same is true for most of the "Math and logic" symbols provided in the Editing page. (By the way, I can see most "Symbols", and all the Latin, Hebraic, Arabic, Greek and Cyrillic characters). Paolo.dL (talk) 14:48, 30 May 2011 (UTC)

That sounds like a general problem that needs addressing elsewhere. -- cheers, Michael C. Price talk 15:54, 30 May 2011 (UTC)
I think this is relevant to this discussion. I don't think this is a problem that can be solved by Wikipedia. Millions of people throughout the world use English Wikipedia with IE 8 in Windows XP (not compatible with IE 9). They might solve the problem by downloading some plugin or another browser, but it seems plausible that most of them would not want or be skilled enough to do it. So, if we use Unicode font for aleph, beth, R and N in the introduction, they simply would not be able to read it. Paolo.dL (talk) 19:09, 30 May 2011 (UTC)
Honestly I'm against blackboard bold N and R. Let's just use bold. --Trovatore (talk) 19:22, 30 May 2011 (UTC)
I guess you mean and . I prefer this format (although it is too large), as bold capital letters are also used for matrices. E.g., R is typically a rotation matrix with elements in . But if somebody else agrees with you, I will abide.
We also need consistency in font format, at least within this article.
Paolo.dL (talk) 19:36, 30 May 2011 (UTC)
Almost all mathematical symbols are overloaded; not too much we can do about that. My usual feeling is, blackboard bold is for the blackboard. That's not to say I've never used it, but I don't see why we need it for N and R. --Trovatore (talk) 20:00, 30 May 2011 (UTC)
Yes, clearly would require very inconveniently defining several operators. Sorry about that, I'm definitely not a mathematician. And, I definitely prefer the TeX, blackboard-bold notation to boldface. It is a bit oversized, but it's universally understood and unambiguous. "For blackboards" does not reflect reality; these symbols have been common in typeset books for a long time, not to mention other Wikipedia articles. Many readers will fail to see the relation between N and . TeX-to-HTML (in the Wikipedia preferences under "Appearance") will one day fix the size and portability problems, although it doesn't yet. (Hopefully before IE 8 becomes unpopular.) Potatoswatter (talk) 06:40, 31 May 2011 (UTC)
Some books use them; some don't. Some books also use the (useful abbreviation but hideous when abbreviation is unnecessary) iff; consensus at the math project is clearly against the latter. I see the bbb symbols as a bit of a similar issue (though I certainly don't feel as strongly about them as about iff). --Trovatore (talk) 09:57, 31 May 2011 (UTC)

New paragraph[edit]

I also propose to add this paragraph:

  • The term continuus refers to an ordered collection of elements such that, between any two of them, no matter how close they are to each other, there's always an infinite number of other elements. For instance, there are infinitely many real numbers between 0 and 1, or 0 and 0.01. Interestingly, it can be shown that they are as many as those in the whole set . In other words, the interval [0,1], or in general [a,b], has the same size as . This is also true for many other continuous sets, such as any n-dimensional Euclidean space (see Space filling curve). Thus:

Paolo.dL (talk) 12:56, 31 May 2011 (UTC)

I'm opposed. Assuming that you mean distinct elements (else no total order is continuous), this describes the rational numbers which are strictly smaller than the reals. So it muddies the waters needlessly. CRGreathouse (t | c)
No, I absolutely did't mean distinct, nor rational. I meant continuous, which clearly implies some notion of "order" of elements, such that you can say, for any element in the set, whether it is smaller or greater than another, or (for points in ) less/more distant than the other from an origin. I probably misused the expression "ordered set". I wanted to use the word "sequence", but then I realized that "sequence" is only related to discrete sets. It is clear, however, that we need the property that I described above to tell a continuous set from a discrete set, or a set with "gaps", because otherwise it would be impossible to identify which elements of a set are "between" two other elements of the same set. Paolo.dL (talk) 17:50, 31 May 2011 (UTC)
You misunderstand. You left the word "distinct" out of your definition of "continuous". Using your definition as written, the real numbers under < are not continuous because there are only finitely many real numbers between 1 and 1. If we change the definition to
The term continuus refers to an ordered set such that, between any two distinct elements there are infinitely many elements between them.
then the rational numbers are continuous under <.
CRGreathouse (t | c) 19:11, 31 May 2011 (UTC)
It's also not standard terminology. The standard term for this is dense (specifically, order-dense). As CRG says, this does not exclude countable sets like the rationals, so it seems like it would be confusing to bring it up in this context. --Trovatore (talk) 19:42, 31 May 2011 (UTC)

I see. Thank you both for explaining. The most important part of my "new paragraph", however, is the idea that a subset of R can have the same cardinality as the whole set, and even more surprisingly, |R| = |Rn|. In my opinion, this should be mentioned in the introduction, for two reasons: (1) there's a section in the article which lists several sets with cardinality , and (2) the idea that some "infinites" are identical while they definitely and deceptively appear to be different is even more fascinating than the idea that there are "different infinites". This is the first purpose of my text. A secondary purpose is to show that all of this sets which surprisingly share with R the same cardinality appear "continuous", or more properly "dense"..., and this explains the term "continuum" in the expression "cardinality of the continuum" (although there are dense sets which have a strictly smaller or greater cardinality).

I have a doubt, however: is the power set of N a dense set? I wrote that all the sets with cardinality are dense. Is this correct?

Paolo.dL (talk) 20:40, 31 May 2011 (UTC)

If by your purposes you mean making the article accessible to more readers, then I'm with you there. But it's not clear to me how much this article should serve as an introduction to cardinal arithmetic. I'm not opposed, on the whole, but would prefer to see what other experienced editors think.
I still disagree with the particulars you bring up, though. Consider the real numbers and the (total) order
0 ≺ r for all r in R, 1 ≺ r for all r in R \ {0}, a ≺ b if a, b in R \ {0, 1} and a < b
under which the interval (0, 1) is empty and yet the set is uncountable.
CRGreathouse (t | c) 20:47, 31 May 2011 (UTC)
To address your addition: as my example shows, you can't look at a set alone to determine that, you need its ordering or topology as well. CRGreathouse (t | c) 20:48, 31 May 2011 (UTC)

Thank you. I appreciate your detailed explanations. The total order described in your example is extremely complex (I don't even know exactly the meaning of the symbol ≺, but I trust you that it makes (0,1) empty). I tend to think that it is safe to assume that those who are able to imagine such an order are also able to understand my text. It is easy to guess that the expression "between two of them" in the first sentence of my "new paragraph" refers implicitly to two distinct elements of a set totally ordered under an elementary relation such as <. However, as you pointed out previously, my sentence is misleading for another reason. So, let's forget my "secondary purpose" (explaining the term "continuum"). A link to Continuum (set theory) somewhere in the intro will suffice.

My "main purpose" was another. For the two above-listed reasons, I proposed to state in the lead that the real numbers between 0 and 1 are as many as those in R or Rn, i.e.

(Notice that I purposedly avoided technical terms such as interval and equinumerous in this sentence, to make it easier to understand for beginners). This statement is not referred to a generic "totally ordered set", but to R, which is typically well-ordered under <. In this case, we can safely assume that whoever is both interested to read this article and able to understand the first sentence of the lead will also be able to guess that "between 0 and 1" means 0<x<1. If you agree with me about this, I will try and re-write my "new paragraph" accordingly.

Paolo.dL (talk) 15:45, 1 June 2011 (UTC)

(Counter-) intuitive argument[edit]

We temporarily stopped a discussion about the section "Intuitive argument" to discuss about the introduction. The latter discussion seems to have reached a reasonable degree of consensus, and a new introduction has been published. Feel free to continue above the discussion about the new introduction, if you like, but I think that now the "Intuitive argument" deserves more attention.

Some contributors previously agreed that the "Intuitive argument" provides an absolutely counter-intuitive proof for |R| = 2|N|. This prooof is based on cardinal arithmetics, which is in turn based on Cantor's distinction between |N| and |R|. That distinction is used as an axiom, thus the proof is, in my opinion, of little use.

Paolo.dL (talk) 12:15, 5 June 2011 (UTC)

Proposal 1[edit]

There's probably no intuitive proof that |R| > |N|, but I propose to replace the (alleged) "intuitive argument" with an "informal introduction" such as this:

Although there are infinitely many natural numbers, it can be shown that the number of digits in any natural number is finite. 10 distinct digits are available if numbers are written using the standard decimal notation. Hence, there are 10n possible ways to compose a natural number with n digits.

.... [Question: how comes then that there are infinitely many natural numbers? Can someone answer this without using cardinal arithmetic?] ...

On the contrary, every real number has an infinite number of digits in its decimal expansion. For example,

1/2 = 0.50000...
1/3 = 0.33333...
= 3.14159....

Note that this is true even when the expansion repeats as in the first two examples. In any given case, the number of digits is countable since they can be put into a one-to-one correspondence with the set of natural numbers . This fact makes it sensible to talk about (for example) the first, the one-hundredth, or the millionth digit of . Since the natural numbers have cardinality each real number has digits in its expansion. Hence, there are possible ways to compose the decimal expansion of a real number. This implies that there are real numbers in the interval from 0 to 0.999... (unit interval).

Any real number is composed of an integer part and a decimal expansion. Since the integer part is a natural number, and there are natural numbers, then there are real numbers. Similarly, if the real numbers are represented using a binary notation, such as that used by computers, we conclude that there are real numbers. Since there is a one-to-one correspondence between the real numbers represented in the commonly used decimal numeral system, and those in other numeral systems, such as the binary one, mathematicians agree that

Cantor showed that it is also possible to define a one-to-one correspondence between the unit interval and the whole set of real numbers. Thus

However, it is impossible to define such a correspondence between the natural numbers and the real numbers. Thus

I need your help to refine this text. Paolo.dL (talk) 12:15, 5 June 2011 (UTC)

Your bracketed question seems to be answered by the following sentence: most real numbers can't be expressed as terminating decimals. CRGreathouse (t | c) 00:23, 6 June 2011 (UTC)
This does work well as an informal introduction but only if the reader is familiar with the concept of and exponentiation. It's easy to conclude that , but that shouldn't intuitively imply that . Taking the argument at that point and saying "Cantor said so" may be very disappointing to the reader.
I put this article on my watchlist after being inspired by a conversation. I met a local math professor at a party and he described Cantor's Diagonal Argument, verbally without writing anything. To me, that was intuitive. But I already had enough background in set theory to grasp the importance of finding an element not already in the set. (Not enough, however, to have heard of aleph-naught. Intro to abstract algebra at my college stopped at the countability of rational numbers.)
Perhaps the first section can be a gentler introduction to the Diagonal Argument, or an exposition of its significance. As a bonus, the Diagonal Argument applied to scalars intuitively proves uncountability of the interval [0,1) ⊂ ℝ, which you can extend to the reals by mapping the "short" interval to the "long" one.
Or, to construct another more complete "intuitive" argument:
Consider a possibly-infinite, increasing sequence of natural numbers ai. Such sequences clearly correspond to members of 2 since each number is either included or excluded.
Each sequence corresponds to a real number 0 ≤ r ≤ 1,
Therefore, |[0,1]| = |2|. [Hmm, that equality doesn't really follow. All I can really say is |[0,1]| ≥ |2|. Is there an "intuitive" way to deal with the asinine representations using trailing ones? Is it more appropriate to just ignore them?]
However, if we try to convert a sequence to a natural number using (a mapping which skips no numbers), the result is infinite for infinite sequences. Such a sum has no well-defined magnitude, cannot obey the familiar rules of arithmetic and hence cannot be a natural number. It seems difficult to map elements of 2 → ℕ. However, each finite sequence does terminate, therefore does correspond to a natural number. Clearly there are "more" infinite sequences than finite sequences. Cantor's diagonal argument reveals how the endlessness of the sequences implies uncountability of the set of sequences.
Hmmmmmmmmm. I think we can each write an argument which is most intuitive to himself. Here's hoping for more advice from novice readers, and consensus… Potatoswatter (talk) 07:26, 6 June 2011 (UTC)
My text was a gentle introduction, not a proof or formal argument. It says something that the current section surprisingly omits: bijections are needed to prove equinumerosity. It states a lot of "facts" that mathematicians take for granted and most readers assume to be impossible. That's a huge step forward relative to what is written in the current "intuitive argument". How can you arouse the curiosity of a reader more than by saying that the natural numbers cannot have an infinite number of digits, while the real numbers can? That's amazing, in my opinion.
The problem is that I cannot easily explain why |N| is not a natural number. Natural numbers are countable, so if they are infinitely many, then "infinitely many" should be a natural number, which means that 2n = |N|... however, this is incompatible with the fact that the number of digits n is finite, isn't it? Explaining the reason why a natural number cannot have an infinite number of digits is crucial. I guess this is what you need to understand if you want to understand the concept of countability.
In other words, is there an infinite powerset of a finite set? If yes, how's that possible? Paolo.dL (talk) 10:26, 6 June 2011 (UTC)
No, there is no infinite powerset of a finite set. I don't really follow your reasoning as to why there should be. --Trovatore (talk) 10:59, 6 June 2011 (UTC)

It's a matter of logic symmetry between these two statements (the first of which is stated in the article):

  1. There are |N| digits in the decimal expansion of a real. Hence |R| = 10|N|
  2. There are n digits in any natural number. Hence |N| = 10n


There must be a fault in this logic, but I can't find it. Where's the mistake? Notice that I have not studied Cantor's diagonal argument yet. However, this is the reason why my contribution may be useful in this discussion. I may be able to represent the readers who need a gentle introduction.

Isn't it natural for a beginner to look for symmetry? "Intuition" is based on easy logic rules, that can be applied quickly, without effort. Symmetry is one of them. Of course, as I wrote above, intuition may lead to wrong conclusions. This is why I insisted that "the truth is counterintuitive" in this case, and "intuitive argument" is a misleading title for a section in this article. Paolo.dL (talk) 13:19, 6 June 2011 (UTC)

To Paolo.dL: "There are n digits in any natural number." is only true if it is interpreted to mean
To infer the false sentence "|N| = 10n", you would need the stronger (and false) statement
Your argument concerning is a non sequitur (logic).
You should study Cantor's diagonal argument before you presume to write for this article! JRSpriggs (talk) 00:46, 8 June 2011 (UTC)

I wrote several parts of the new lead in this article, and you accepted most of my edits. I started this discussion because a section called "intuitive argument" is in my opinion one of the worst of its kind I have ever read on Wikipedia. I believe that the new text I proposed above is much better than the current one. I did this without knowing the details of Cantor's diagonal argument. I don't think that this section should introduce Cantor's diagonal argument. I believe it should arouse the curiosity of the reader by exploring propositions/results with simple terminology. As for the proof(s), it sufficies to explain that the existance/non-existance of a bijiection entails equinumerousity/different cardinality. A recent edit in my opinion made this section even worst, as the editor replaced the second half of the section with an argument based on counter-intuitive transfinite arithmetic, which in turn is based on what the section is supposed to introduce and readers are not supposed to know. I explained my rationale. If you disagree, just explain why. For sure, I am not here to impose my opinion, nor to gain a personal advantage, and that's what I expect from everybody else. Paolo.dL (talk) 20:58, 6 June 2011 (UTC)

Generally, your suggested sections are inaccurate and (to me) less intuitive than what is presently in the article. I'm sure there are reasonable disagreements to be had about the level of accuracy required in these sections: I would say that, apart from "(ignoring certain complications)"-type comments, the material should be strictly accurate, simply lacking details. For example, in an overview I would not feel the need to mention the minor difficulty posed by repeating decimals. CRGreathouse (t | c) 04:45, 7 June 2011 (UTC)

CRGreathouse, in the previous section, you explained the reason why one of my statements was misleading. That resulted in an accurate and easily readable short summary of an imporant section of the article, which I inserted in the lead. That summary was missing in the old version of the lead.

On the contrary, the generic comments in your latest contribution are not constructive at all. We are discussing here a section called "intuitive argument". Later, I am going to explain why in my opinion the current text is absolutely useless to beginners. The fact that that text is to you more intuitive than my version is absolutely meaningless, as that section should use a language accessible to most readers. In sum, I wish we could work together, instead of against each other. If you and JRSpriggs wish to fight, I'll quit the discussion and you'll have to find another enemy.

Paolo.dL (talk) 13:03, 7 June 2011 (UTC)

Paolo — Not knowing the diagonal argument is definitely a problem. Having a novice perspective here is nice, except that you have some foreknowledge (and preconceived notions) about the transfinite cardinals. Note the appearance of in your proposed text. The diagonal argument uses (countably) infinite sequences to show that uncountability exists. It works quite simply, without transfinite symbols. Without this knowledge, how can you dictate this article's relationship to it?
Curiosity is good, but the article (and this discussion) need to stay on topic. Beth-2 has nothing to do with the cardinality of the continuum. (See beth number for that topic.) "Exploring propositions/results with simple terminology" can quickly get confusing for a reader who expects an explanation (as good readers do), not tangents. "The existance/non-existance of a bijiection entails equinumerousity/different cardinality" is misleading… the non-existence of a bijection is hard to prove. Actually, I think this gets right to why the diagonal argument should be introduced earlier: by omitting it, the current text invites the reader to invent a simpler, false argument. Or to blindly trust in "Cantor proved," which isn't very educational.
As for constructiveness vs fighting… the important thing is that we all suggest enough that some subset meets the union of our goal criteria. Without that, there's no chance of success! We simply need both criticism and suggestions to make headway. In other words, stay as organized as we were for the last round. Potatoswatter (talk) 16:54, 7 June 2011 (UTC)
The "intuitive argument" is based on a simple idea: the decimal expansion of a real number has digits. Thus, possible sequences of digits. In my opinion, this is the only good part of the "intuitive argument". And this is what catched my attention. Even JRSpriggs started from this idea in his attempt to show that |R| = (see second part of the section). But again, I don't want to impose my opinion.
There's something however on which you, Potatoswatter, might agree with me: the current text is useless to beginners, and is supposed to be a gentle introduction for beginners. On that, there's no consensus with the other contributors to this discussion.
What's the problem in using the symbol of a cardinal number? This article is about a cardinal number. The definition of is given in the lead. Paolo.dL (talk) 20:42, 7 June 2011 (UTC)
Yes, aleph-naught is introduced in the lead, but "the decimal expansion of a real number has digits" is far from intuitive to someone who only just heard of it. And how are they supposed to intuitively guess that even though ?
I am attempting to intuitively reason that |ℝ| = |2| by counting, without transfinite symbols, which is how a derivation must be done before the introduction of transfinites — as you have admitted. Then, I go on to make a futile attempt at a bijective map between |2| and |ℕ|, hinting at the outcome of the diagonal argument. That goes much further than the existing text or your proposal. Potatoswatter (talk) 03:52, 8 June 2011 (UTC)
Paolo, I have no wish to fight either, but I also don't see your version as progress. I look forward to your critique; hopefully it will be more useful to improving this article. CRGreathouse (t | c) 04:06, 8 June 2011 (UTC)
Thank you. May be you are right. I'll slow down a little, but as soon as I can, I'll try to explain more specifically why in my opinion the second half of the current version is useless to the readers who are supposed to need a gentle introduction. In the meantime, I'll study Potatoswatter's proposal below. Most of his ideas for the new lead were great... Paolo.dL (talk) 18:17, 8 June 2011 (UTC)

Proposal 2[edit]

I think that this does a better job at piquing the reader's interest, informing about the elementary methods used with infinite sets, and preparing to understand the significance of the diagonal argument.

Consider an increasing sequence of natural numbers ai. This sequence may be finite like { 12, 42, 987 } or infinite like { 2, 4, 6, … } . Each such sequence corresponds to a subset of the natural numbers: every number is either contained or not. There is also only one way to write each subset as a sequence. The set of sequences thus corresponds 1-to-1 to the powerset of the naturals, written , where 2 represents the binary decision of including or excluding each number.

Each sequence can be transformed to a real number 0 ≤ r ≤ 2,

Some pairs of sequences map to the same number,[1] therefore the cardinality of this interval is bounded:

However, we can easily map the powerset to [0,1] or [0,4] by multiplying the summation formula by a constant factor. Thus, multiplying or dividing an infinite quantity by 2 has no effect. Applying this principle yields an exact identity:

The entire number line is infinitely long, of course. A mapping such as x → ​1x rearranges our finite interval to an infinite one — for this informal line of reasoning, we can ignore the resulting hole.

To recap, the distinct sets of natural numbers are equinumerous with the distinct increasing series of natural numbers. The increasing series are equinumerous with the real numbers in a finite interval. The real numbers in a finite interval are equinumerous with all the real numbers. The final result is

However, if we try to convert a sequence to a natural number using , the result is infinite for infinite sequences. Such a sum never stops growing and cannot equal any natural number. It seems difficult to map elements .[2] However, each finite sequence does terminate, therefore does correspond to a natural number. Clearly there are "more" infinite sequences than finite sequences. Cantor's diagonal argument reveals how the endlessness of each sequence implies uncountability for the set of sequences.

1. ^ Each finite subset pairs with an infinite subset. One example is { 0 } with { 1, 2, 3 … } ; these both map to 1. See 0.999... .
2. ^ Using Gödel numbering, much better maps can be formed. For example, we can map natural numbers to English text. The natural numbers thus map to all sets that can be described using natural language, without going on forever. Even this is too small, because infinite English text is inevitably required to describe an infinite subset with no underlying pattern. The real number line starts to seem unnaturally large!

Potatoswatter (talk) 05:29, 8 June 2011 (UTC)

I think that "cannot obey the familiar rules of arithmetic" is likely to cause greatly increased confusion in the less-mathematically-literate segment of readers. CRGreathouse (t | c) 18:51, 8 June 2011 (UTC)
Yes, I got tired of fighting with formatting and there are still a few things wrong. I've fixed that and several glaring omissions. Needs more polish and more suggestions! Potatoswatter (talk) 19:40, 8 June 2011 (UTC)
I am sorry, I know that writing this proposal was time consuming. However, I think it is too complex, and more importantly it assumes too much. For instance, you initially assume that the set you define starting from the power set of the natural numbers is equal to [0,2]. Then you assume that [0,2]*2 = [0,4]. That's the same as assuming that a segment with length 4 has the same number of points as a segment with length 2, or that |R| = |R|*2. The problem is that transfinite cardinal arithmetics is based on Cantor's results, not viceversa. This is exactly the reason why the current text is useless, in my opinion. Wouldn't it be more honest to delete the "intuitive argument" and let the readers read the rest of the article without conning them into believing that there's something intuitive in Cantor's results? Shouldn't we lead them to believe that the only way to understand that
is to study counterintuitive and complex arguments such as Cantor's diagonal argument?
Paolo.dL (talk) 21:43, 23 June 2011 (UTC)

About the current version of section "Intuitive argument"[edit]

The section Cardinality of the continuum#Intuitive argument as I left it last contains only arithmetic operations which are true for both finite and infinite numbers, excepting only

That is the sense in which it is intuitive for people who are only used to finitary mathematics. The only other concession to the infinite lies in the fact that one must use less-or-equal in some cases where strictly-less would be justified for finite numbers. Thus I fail to understand how you can say that this section is counter-intuitive. JRSpriggs (talk) 06:02, 24 June 2011 (UTC)

You seem to confuse what is easy to grasp with what you are familiar with. Your two "exceptions" are more than enough to confuse a non-mathematician. Let me try to convince you about the meaning of the term intuitive. Intuition is a "gut feeling", the ability to understand "without much reflection". So, intuitive means "easy to grasp". An argument is intuitive if it can be "readily learned or understood". There's wide consensus about the fact that Cantor's idea of "different infinites" is counter-intuitive for non-mathematicians. I doubt that Cantor' results were based on intuition (i.e. obtained without much reflection). Anyway, even if his study or part of it were based on his own intuition, that would not make his results intuitive for others. There's a huge difference between the intuition of a very well-educated mind such as Cantor's or yours, and the intuition of a non-mathematician. The latter is a wild beast. You can't expect it to follow the correct path. Your mind is so used to follow that path, that you forgot what's the easiest (i.e. most intuitive) path. In this case, the easiest path is incorrect. I wish we could agree at least about this.
Here's an example. In Cardinality of the continuum#Intuitive argument, the equation might be easier to grasp than you think. As the title of the section is "intuitive argument", I am sure that even readers which know nothing about set theory will be encouraged to try and understand that formula. They may digest it based on the incorrect but intuitive assumption that nothing can be larger than infinite, hence there's only one infinite (). This is the easiest path for a non-educated mind. (I guess you can't see it because you are too familiar with the correct path, so you should trust me in this case). However, this incorrect path would lead to the incorrect conclusion that
In other words, there's a non-negligible gap in the alleged "intuitive argument": Cantor's diagonal argument is taken for granted.
Let's imagine that the reader is not clever enough to "grasp" the equation . That would make that equation counter-intuitive. So the entire section, being based on that statement, would be perceived as counter-intuitive. I conclude that there's only one way to accept that section as intuitive: being familiar with the correct path, i.e. being a reader who does not need to read that section to understand the article.
By the way, there's also another logical gap in the current text. You did not explain the reason why the number of all possible combinations of decimal digits in a decimal expansion is . I can understand that there are 10n ways to fill n decimal positions, but in my opinion this is not easy to guess for a beginner. Also, I can't understand why you used "≤" (I would use "="), and that is a major source of doubts.
That's why the current version of section "intuitive argument" is totally useless, and far from intuitive for those who are supposed to read it. Paolo.dL (talk) 11:10, 24 June 2011 (UTC)
I suppose that someone trying to understand this article should first understand aleph null well enough to see the truth of
As for why one does not immediately get equality in
that is because some real numbers are represented by two decimal expansions rather than one. Of course, a little additional effort shows that this is not a problem. But why address that issue when it is irrelevant to the inequality I was trying to show in that calculation?
It would probably be no great loss to take out the section. However, what bothers me about your whole approach to this article is that you seem to be trying to use ignorance to justify degrading the article. You want to take out true and illuminating statements because they conflict with the irrational prejudices of some readers. You want to put in false or misleading statements because they are allegedly intuitive and only a little bit false (like a little bit pregnant?). This approach is counter-productive and unethical. JRSpriggs (talk) 23:30, 24 June 2011 (UTC)
How do you dare to say that I "want to put in false or misleading statements"? This is an unacceptable judgement about my intentions, which by the way reveals how biased is your opinion. I am not going to waste my time with you anymore. In the future, if you removed your blinders, you might be able to interact with someone else. Paolo.dL (talk) 11:42, 25 June 2011 (UTC)
I don't question your motives, but you do seem to add questionable or misleading material. CRGreathouse (t | c) 16:38, 25 June 2011 (UTC)
@Paolo.dL You are pretty familiar with the "good faith" aspect of Wikipedia, yes? Show your critics good faith (i.e. learn from them and have fun!) and I'm sure you will get plenty of good faith and positive feedback in return. I always remember that for every topic, there is going to be an expert that knows more than I do, and am prepared to defer. The last thing you want to do is get indignant  :) Rschwieb (talk) 20:49, 5 July 2011 (UTC)
He moved it to User talk:Rschwieb, if anyone was robbed of their chance to comment. Rschwieb (talk) 19:06, 6 July 2011 (UTC)

I am not answering personal messages here. Please use this talk page to discuss about the article. Paolo.dL (talk) 16:05, 6 July 2011 (UTC)

Moving the "intuitive argument" section[edit]

Stepping back and reading the article afresh, the "intuitive argument" section is definitely misplaced. Our first goal should be to convey the basic information about the topic at hand, and not leap directly into a quasiproof of one specific fact mentioned in the article. (It is as nonsensical as an article beginning "Cardinality of a set: 1.Intuitive argument".) The "Properties" should immediately follow the introduction, followed by the examples and "Continuum hypothesis" sections, in some order. Beth cardinals are slightly peripheral so that section goes later.

I concur with JRSpriggs that taking out the intuition section would be no loss, and I vote that it be moved, at the very least. It is both misplaced and unnecessary, but that said, I think the content in that section would make a fine external or internal link labeled "Alternative explanation for c=2^aleph_0". Rschwieb (talk) 15:35, 8 July 2011 (UTC)

It's entirely possible that no harm would be done to the article by removing the section in its present state. But I strongly support having material directed toward nonexpert readers, probably in its own section.
Most readers would not be able to follow a typical rigorous "properties" section. So to them, that content may as well not be there. In that light I can see the value of that placement of the section: all they can read is the opening and that section.
If there's a serious proposal to rework that framework, perhaps to make the other sections each open with a basic (readable by high school students, say) paragraph then I'd consider it. But if the proposal is to make the article inaccessible to lay readers, I'm not in favor.
CRGreathouse (t | c) 15:53, 8 July 2011 (UTC)
Good, because it was far from my intention to make the article inaccessible. Other introductory material motivated by the properties mentioned would be excellent, but not one person's extensive thought process about one specific fact. Highschool readers will definitely not understand carrdinal arithmetic in the section we are talking about, so I gather that you meant to say you want a basic section in that location, but you do not like the current one. Rschwieb (talk) 16:08, 8 July 2011 (UTC)
I agree that the intuitive argument section is misplaced. To immediately jump into heuristics after the introduction is akin to showing someone a single semi-random tree rather than an overview of the forest. Furthermore, to a non-expert reader an intuitive proof is just as difficult to follow as a rigorous proof.ActuariallySound (talk) 16:16, 8 July 2011 (UTC)

I'm curious to see what you have in mind, Rschwieb. CRGreathouse (t | c) 18:10, 8 July 2011 (UTC)

First we must decide: What ideas in this article are worth explaining to a layperson? My cadidates are: |R| is uncountable; and every (nondegenerate) interval has the same cardinality. I don't think that showing 2^aleph_0=c is a priority.
IMHO, an explanation of why |R| is uncountable should be based on Cantor's diagonal argument: why avoid such a beautiful piece of mathematics? I have found it rather easy to explain to laypeople, I might add. The problem with including this point is that it belongs on the CDA page. The thing about intervals definitely belong on this page, and explaining it simply is feasible. The field is open for more candidates too, but please keep in mind it is neither possible nor necessary to explain *everything* in layperson terms. Rschwieb (talk) 18:52, 8 July 2011 (UTC)
What ideas... hmm... I think that |R| ≠ |Z|, that |[a, b]| = |[c, d]| for a < b, c < d, and that |R| = |R^n|. CRGreathouse (t | c) 18:58, 8 July 2011 (UTC)
It would be pretty easy for us to explain the first two points you mentioned follow from the ones I mentioned. That |R|=|R^n| is a good one, but it kind of seems like that belongs on the cardinal arithmetic page... Rschwieb (talk) 19:13, 8 July 2011 (UTC)
I dunno, |R^n| has the cardinality of the continuum too, why exclude it? But it's not critical to include, perhaps -- though I think it's important, more so than the intervals. CRGreathouse (t | c) 02:45, 9 July 2011 (UTC)
If you have an idea for a concise proof it would be a good addition. For the interval thing, there is a very nice picture of a function from (a,b) onto R, which I think laypeople will like. Rschwieb (talk) 13:26, 9 July 2011 (UTC)

I moved section "intuitive argument" and renamed it to "Alternative explanation for c=2^aleph_0", as suggested by Rschwieb (see also the previous sections in this talk page). I appreciate your attempt to explain the contents of this article to beginners. Please consider that, in my opinion, the article Cantor's diagonal argument is not yet accessible to beginners. As I explained in the relevant talk page, at least one crucial logical step is taken for granted. So, if you are able to explain Cantor's diagonal argument to beginners, you might also want to try and fill the gaps in the main article. Paolo.dL (talk) 18:56, 9 July 2011 (UTC)

Recent reverts about cardinality of real numbers with non-unique binary representation[edit]

I have not checked this completely, I'm just arguing off the top of my head. As far as I know, the only ambiguity arising as expressing numbers as binary expansions is that 0.1=1.0 and 0.01=0.10 . At least, I think this is the case, analogously to 0.9=1.0 in decimal. If this is true that the only real numbers without unique representation are the ones terminating in 1, isn't it obvious only countably many numbers suffer this problem? It would be equivalent to counting the finite sequence of digits that come before the infinite repeating tail, and there are only countably many such finite sequences. Addendum: Rereading the reverts, maybe I have misunderstood what the problem really is. Maybe the mistake, meriting removal, is at a juncture other than this. If so, nevermind! Rschwieb (talk) 18:45, 2 February 2012 (UTC)

I quite agree with your interpretation. I don't understand the opposing view at all. — Arthur Rubin (talk) 18:52, 2 February 2012 (UTC)
I think the problem is at another juncture; Isn't it obvious that the interleaving function is well defined when only one of the inputs does not terminate in 1? Interleaving a sequence ending in 1 with one that does not would result in one that does not. Rschwieb (talk) 18:53, 2 February 2012 (UTC)
That's worse, I'm afraid. If x and y both have nonunique expansions (x0, x1; y0, y1 respectively, then all 4 possibilities are different reals:
although the first and last also have different representations as reals. If only one is non-unique, then there are two possible results, both unique. — Arthur Rubin (talk) 20:09, 2 February 2012 (UTC)
Oh, it is supposed to have domain and range with real numbers. In that case, then the map works, it's just that the statement about the countability of nonuniquely expressable reals is irrelevant. That particular blurb seems to have appeared here, contributed by a user who has a history of adding not-quite-correct and questionably relevant statements to this article. Rschwieb (talk) 20:35, 2 February 2012 (UTC)
As the person that made the original revert perhaps i should clarify. The problem is that the interleaving function is not a surjection. Consider the reverse of the interleaving function with (in decimal) and , both of these will map to the same . Since it's not a bijection it doesn't say that the cardinality of and is the same. The placement in the article makes it seem as if this function was somehow an argument for their cardinalities being equal, which is why it doesn't belong there.The statement that it is only a countable number of points that should be removed is false because the function is not surjective for an uncountable number of points in the unit square. For all where y is non-unique this problem exists (for example and that set is uncountable.
I'll concede the point if someone can tell me where and map to in ?
Nevermind, you're right the map obviously isn't onto X! I was so distracted by the task of removing the irrelevant analysis of where the interleaving map was defined and didn't stop to question that statement. Any more surgery on the domain and range of this function is will make the interleaving example useless, so perhaps it is best to leave it out. Rschwieb (talk) 14:34, 4 February 2012 (UTC)


(Per request on my talk page) I have added proofs for some of the examples listed because I believe that it's helpful for the reader's understanding. The list of examples itself is justified for the same reason. DavidLeighEllis (talk) 01:43, 26 April 2014 (UTC)

Well, what I really wanted to know was, how far are you planning to take this? Are you planning on adding more examples/more proofs? How many, how detailed? Do you have a grand vision, and could you let us in on it? --Trovatore (talk) 01:48, 26 April 2014 (UTC)
I'm pretty much done with this article, actually. DavidLeighEllis (talk) 01:50, 26 April 2014 (UTC)
OK, I don't want to discourage you. I think the additions are probably an improvement on balance. I was just a little concerned about where this might end up. --Trovatore (talk) 01:58, 26 April 2014 (UTC)