2
$\begingroup$

I've been told that Cantor sees a relationship between the countable ordinals (Cantor's second number class) and the powerset of the natural numbers.

I've read the "Grundlagen" a few times, but can't seem to locate what he takes this relation to be.


I'm suspecting this is related to the continuum hypothesis CH, though I do not know if my suspicion is correct. Here is why I suspect that this is related to CH. According to wikipedia,

There is no set whose cardinality is strictly between that of the integers and that of the real numbers.

The |powerset of integers| = |powerset of naturals| = |reals| = $2^{\aleph_0}$.

The cardinality of the countable ordinals (the second number class) is identified with $\aleph_1$.

Cantor took $2^{\aleph_0} = \aleph_1$. Hence my suspicion.

My questions:

  1. Am I right that Cantor "conjectured" that the relationship between the countable ordinals and the power set of the naturals is that they are of the same cardinality?
  2. Am I right in my suspicion that this is (or is related to) the continuum hypothesis?

A direct answer to these questions and some commentary would be most appreciated.

Thanks

  • 2
    Sees? ${}{}{}{}$2012-06-12
  • 0
    Yes, Cantor knew that the power set of the naturals was equipollent to the real numbers, and that the cardinality of the countable ordinals was the $\aleph_1$. He also conjectured the Continuum Hypothesis: that $\aleph_1 = 2^{\aleph_0}$; i.e., that the set of all countable ordinals was equipollent to the power set of the natural numbers/of $\omega$. That is, that there does not exist a set $C$ such that $\aleph_0 \lt |C| \lt 2^{\aleph_0}$, which implies $\aleph_1 = 2^{\aleph_0}$.2012-06-12
  • 4
    Note that Cantor did not "take" $2^{\aleph_0}=\aleph_1$": he **conjectured** it, but did not assert it as true.2012-06-12
  • 0
    @QiaochuYuan: I assume the OP means present tense from the point of view of the author at the time of writing, here.2012-06-12
  • 2
    @Arturo: Cantor *did* claim he could prove the continuum hypothesis on various occasions, e.g. in [a letter to Mittag-Leffler dated August 26, 1884](http://i.stack.imgur.com/LXF15.png) (from G.H. Moore, Zermelo's axiom of choice).2012-06-12
  • 0
    @t.b.: And then later reversed himself in each occasion, did he not? As far as I am aware he never *published* an attempted proof that was later retracted/shown to be false, though he did think a few times he had proven it only to discover a problem (something I'm sure we've all been through at one time or another... (-: )2012-06-12
  • 0
    @Arturo: well, yes, in the same year he also wrote in another letter that he could prove the negation of CH. I do not know what conviction he had in the end, whether he thought that he could prove CH or its negation or whether he came to the conclusion that he had no argument at all. Yes, I think you're right that he never published a claim in either direction, but I haven't checked thoroughly.2012-06-12
  • 1
    The [BBC Documentary: Dangerous Knowlege](http://www.youtube.com/watch?v=iALZYHW_5bU) might be of interest to the OP.2012-06-12
  • 0
    @Arturo: "get rid of yelling" -- haha :) I just made it big 'n' bold to be clearer. Is my "suspicion" correct? That's really what I want to know.2012-06-12
  • 2
    @pichael: Yes on the first; the second is rather like saying that one suspects that water is sort of wet. That conjecture **is** the continuum hypothesis. "Continuum" in fact refers to the *real line*. Bold is fine, but large fonts and all caps tend to "raise the volume" rather than provide emphasis.2012-06-12
  • 0
    Cantor proved that every countable ordinal embeds into the rationals. This is what I have to add to this discussion at this point...2012-06-12
  • 0
    @Asaf: I'm trying to understand ordinals now...but can I say that since no function surjects $\omega$ onto its powerset, $\omega$ (or its corresponding ordinal? if that's even right) is therefore not a member of the second number class?2012-06-15
  • 0
    @pichael: That made very little sense to me. Because $\omega$ cannot surject onto its power set we are only assured that any ordinal of cardinality similar to $\cal P(\omega)$ is uncountable. However there are many ordinals like this, and we cannot prove their exact value from ZFC (as this would solve the Continuum Hypothesis).2012-06-15
  • 0
    @Asaf: "any ordinal of cardinality similar to P(ω) is uncountable. However there are many ordinals like this." I don't understand the relationship between P($\omega$) and ordinal numbers. If we knew the cardinality of P($\omega$) would we say "it is an ordinal number"? or "it corresponds to an ordinal number"? In my head, I picture ordinal numbers as sets with a specific order, but I don't think about P($\omega$) that way. I just picture it as a jumbled collection of subsets of $\omega$...if that helps you understand where I'm coming from...2012-06-15
  • 1
    @pichael: Assuming the axiom of choice we can prove that $\mathcal P(\omega)$ can be well-ordered and therefore be put in bijection with an ordinal. As a set it is not an ordinal number, but we can index its element using an ordinal. Such ordinal would have to be uncountable, but there are many different uncountable ordinals, and there are many of those which are in bijection with $\mathcal P(\omega)$ (and even more that are not).2012-06-15
  • 0
    @Asaf: And if we didn't assume choice?2012-06-15
  • 0
    @pichael: Then it *may* be the case that every well-orderable subset of $\matcal P(\omega)$ is countable. In this case there are no corresponding ordinals to the power set of $\omega$ at all.2012-06-15
  • 0
    @Asaf: If you can't well-order P($\omega$) then why could you well-order its subsets? Is it because we're talking about $\omega$ and $\omega$ is well-ordered?2012-06-15
  • 0
    @pichael: Consider the singleton $\{\{\omega\}\}\subseteq\mathcal P(\omega)$. It is finite, and finite things are surely well ordered. Consider the sets $\{0,\ldots,n\}$ for any $n\in\omega$, do you see how these sets can be well ordered? The fact that you cannot well order *the entire* set need not mean that you cannot well order *parts* of that set.2012-06-15
  • 0
    @Asaf: My guess is that they would be well-ordered by <. I thought $\omega$ was countably infinite. Ah, you changed it.2012-06-15
  • 0
    @pichael: You need to understand better what does it mean for a set to be well-ordered, and what does it mean that a set is well-orderable. Let me give the next analogy, $\omega$ is infinite, but it still has finite subsets. Being infinite, as being non well-orderable, is *not* a hereditary property with respect to subsets.2012-06-15
  • 0
    @Asaf: Ok, my translation: (1) A well-ordered set $A$ means that any subset of $A$ has a least element. (2) I _don't_ know what it means to say that a set is well-orderable (3) just because some some sets are infinite or well-orderable doesn't mean that their subsets will be so. (4) To go back just a little earlier, is this right: No function surjects ω onto its powerset. Assuming Choice, there is no well-ordering of ω s.t. ω bijects with some coutnable ordinal. Thus, the cardinality of ω is at least $\aleph_1$. Cantor hypothesized that |ω| = $\aleph_1$.2012-06-15
  • 1
    (1) yes; (2) it means that there is an order on $A$ which is a well-order, and equivalently that there is a bijection between $A$ and an ordinal; (3) Well-orderablility *is* in fact hereditary for subsets, much like finiteness - if $A$ is finite then every subset of $A$ is finite; (4) exactly.2012-06-15
  • 0
    @Asaf: I meant that just because some set is not well-orderdable doesn't mean that its subsets are. Obviously, if a set is well-orderable then every subset is. But, I'm still unclear why non-well-orderness is not hereditary...2012-06-15
  • 1
    The exactly about finite subsets is not enough? If a set is non well-orderable it surely cannot be finite. However every finite subset is surely well-orderable! In the case of $\mathcal P(\omega)$ we can also assure that there are countably infinite subsets (and countability by definition means well-orderability).2012-06-15
  • 0
    @Asaf: How do you define countable ordinal? Is it simply an ordinal that is in a bijection with $\omega$ (which itself is trivially a countable ordinal)? Or equivalently (perhaps?) an ordinal that belongs to the second number class (since every ordinal here is countable)? Also, do you say that a number class "has" some cardinality or "corresponds" to some aleph?2012-06-15
  • 0
    First, I don't use "second class" terminology. So I don't say that at all. Second, countable ordinals are ordinals in bijection with $\omega$; and $\omega_1$ is by definition the collection of all those ordinals. We define the $\aleph$ numbers as the ordinals which cannot be put in bijection with smaller ordinals. $\omega$ and $\omega_1$ are such ordinals. We say that a set has cardinality $\aleph_2$, for example, if it can be put in bijection with the collection of all ordinals which are finite; countable; or of the same size as $\omega_1$.2012-06-15
  • 0
    @Asaf: So the alephs are defined in terms of _limit ordinals_? Or is this not right (as $\omega$+$\omega$ is a limit ordinal able to be bijected with $\omega$)?2012-06-15
  • 1
    Aleph numbers are called *initial ordinals*. Those are by definition limit ordinals, but as you note not all limit ordinals are initial ordinals. Formally speaking $\alpha$ is an initial ordinal if it is infinite and for every $\beta<\alpha$ there is no bijection between $\alpha$ and $\beta$. We can prove that there is an unbounded collection of initial ordinals (in the class of ordinals).2012-06-15
  • 0
    @Asaf: Are you familiar with Cantor's number classes? I'm trying to understand them as they appear in a letter he wrote to Dedekind. This is what I've gathered (also with your comments): A countable ordinal α is an ordinal in a bijection with ω. The class of all countable ordinals α forms Cantor’s second number class (II). ω is the least element of (II). $\aleph_0$ is the cardinality of ω (and therefore every ordinal α ∈ (II)). $\aleph_1$ is the cardinality corresponding to (II). (This is the background for understanding my "(4)" a few comments back)2012-06-15
  • 0
    I am not familiar with the classes at all. From what I gather from Martin's answer, $\omega$ is a first class number. Second class is the collection of all countable ordinals and therefore $\omega_1$ is the least element of the second class. Cantor tried to prove that this is the size of the continuum, but we know now that this proof is impossible from ZFC.2012-06-15

2 Answers 2

4

As Wikipedia says in article about Cantor:

Cantor was the first to formulate what later came to be known as the continuum hypothesis or CH: there exists no set whose power is greater than that of the naturals and less than that of the reals (or equivalently, the cardinality of the reals is exactly aleph-one, rather than just at least aleph-one). Cantor believed the continuum hypothesis to be true and tried for many years to prove it, in vain.

I'll add two quotes from the book Georg Cantor: His Mathematics and Philosophy of the Infinite by Joseph Warren Dauben,

Cantor's second number class is what we would call today $\omega_1$, the smallest uncountable ordinal, which might perhaps be interesting for you in connection with this question.

p.110

Despite all that the Grundlagen had accomplished, there was a serious lacuna. Though Cantor had made it clear that his introduction of the transfinite numbers, particularly those of the second number class, was essential to sharpening the concept of power, the question of the power of the continuum was still unanswered. He hoped a proof would be forthcoming, establishing his continuum hypothesis that the power of the continuum was none other than that of the second number class (II). The benefits of such a proof would be numerous. It would immediately follow that all infinite point sets were either of the power of the first or second number class, something Cantor had long claimed. It would also establish that the set of all functions of one or more variables represented by infinite series was necessarily equal in power to the second number class. Likewise, the set of all analytic functions or that of all functions represented in terms of trigonometric series would also be shown to have the power of the class (II).

The Grundlagen went no further in settling any of these issues. Instead, Cantor published a sequel in the following year as a sixth in the series of papers on the Punktmannigfaltigkeitslehre. Though it did not bear the title of its predecessor, its sections were continuously numbered, 15 through 19; it was clearly meant to be taken as a continuation of the earlier 14 sections of the Grundlagen itself. In searching for a still more comprehensive analysis of continuity, and in the hope of establishing his continuum hypothesis, he focused chiefly upon the properties of perfect sets and introduced as well an accompanying theory of content.

p.137

In the fall of 1884 he again took up the intricate problem of the continuum hypothesis. On August 26, 1884, little more than a week after his letter of reconciliation to Kronecker, Cantor had written to Mittag-Leffler announcing, at last, an extraordinarily simple proof that the continuum was equal in power to the second number class (II). The proof attempted to show that there were closed sets of the second power. Based upon straightforward decompositions and the fact that every perfect set was of power equal to that of the continuum, Cantor was certain that he had triumphed. He summarized the heart of his proposed proof in a single sentence: "Thus you see that everything comes down to defining a single closed set of the second power. When I've put it all in order, I will send you the details."

But on October 20 Cantor sent a lengthy letter to Mittag-Leffler followed three weeks later by another announcing the complete failure of the continuum hypothesis. On November 14 he wrote saying he had found a rigorous proof that the continuum did not have the power of the second number class or of any number class. He consoled himself by saying that "the eventual elimination of so fatal an error, which one has held for so long, ought to be all the greater an advance." Perhaps he was thinking back to the similar difficulties he had encountered in trying to decide whether or not the real numbers were denumerable, or how lines and planes might be corresponded. Cantor had come to learn that one should never be entirely surprised by the unexpected. Nevertheless, within twenty-four hours he had decided that his latest proof was wrong and that the continuum hypothesis was again an open question. It must have been embarrassing for him to have been compelled to reverse himself so often within such a short period of time in his correspondence with Mittag-Leffler. But even more discouraging must have been the realization that the simplicity of the continuum hypothesis concealed difficulties of a high order, ones that, despite all his efforts and increasingly sophisticated methods, he seemed no better able to resolve.

In attempting to find a solution for his continuum hypothesis, Cantor was led to introduce a number of new concepts enabling more sophisticated decompositions of point sets. These, he hoped, would eventually lead to a means of determining the power of the continuum. His attempt to publish these new methods and results marked the final and most devastating episode responsible for his disillusionment with mathematics and his discontent with colleagues both in Germany and abroad.

EDIT: You've added clarification to your question that you would like to know this:

  1. Am I right that Cantor "conjectured" that the relationship between the countable ordinals and the power set of the naturals is that they are of the same cardinality?
  2. Am I right in my suspicion that this is (or is related to) the continuum hypothesis?

(1) Yes, I believe that the excerpts I provided above give sufficient support for this claim.

(2) I am used to $\aleph_1=2^{\aleph_0}$ as the usual formulation of CH. And this is the same thing as you wrote in your Question 1. However, we should be careful if we want to avoid Axiom of Choice.

If we are working in ZF, i.e. without Axiom of Choice, this formulation is not equivalent to "There is no set whose cardinality is strictly between that of the integers and that of the real numbers." The reason is that $\aleph_1$ and $2^{\aleph_0}$ can be incomparable.

The relation between these two claims (which are in ZFC both equivalent formulations of CH) is explained in detail here.

  • 1
    Thanks for these excerpts. A lot of background on Cantor's trying to come to grips with the well-ordering principle and CH is also given in chapter 1 (especially section 1.5 -- at least in my older edition) of G.H. Moore, *[Zermelo's Axiom of Choice: Its Origins, Development, and Influence](http://books.google.com./books?id=ZzJ8tQAACAAJ)*.2012-06-12
  • 0
    @Martin: Your post did provide sufficient support. I was hasty and didn't read but a couple of comments before I figured that my question wasn't clear enough for my anal-retentiveness. Thanks for the great post!2012-06-12
  • 1
    It should be mentioned that Cantor implicitly used the axiom of choice in his work. In fact he proved the famous Cantor-Bernstein theorem as a very simple corollary from the fact that every two cardinalities are comparable, which we know is an equivalent of choice.2012-06-12
  • 0
    This is like good all times: t.b. adding interesting historical remarks and plenty of references; Asaf stressing the use of Axiom of Choice. There are so many questions where I have seen this.2012-06-12
4

The only clarification I would make is the following: Cantor didn't see how to show that there was a subset of the reals of cardinality strictly between $\aleph_0$ and $\mathfrak{c}:=2^{\aleph_0}$--in fact, as Arturo points out in the comments below, every infinite subset of the reals he tried had cardinality either $\aleph_0$ or $\mathfrak{c}$--and so conjectured (not the same as concluded, as Arturo points out in the comments above) that $\aleph_1=\mathfrak{c}$.

One can show that the set of countable ordinals is not "bigger" than the power set of the natural numbers. Of this, Cantor was aware.

  • 2
    More than just not seeing how to show there *was* such a set, every set he tried he could show it was either equipollent to $\mathbb{R}$ or to $\mathbb{N}$. (A bit more, since the way you phrased it, it might have been that he had a set he could not tell *whether* it as bijectable with $\mathbb{N}$, with $\mathbb{R}$, or with neither...)2012-06-12
  • 0
    @Arturo: Is there a reference for "every set he tried he could show it was either equipollent to ℝ or to ℕ"?2012-06-12