3
$\begingroup$

I am new to set theory and need a little clarification.

Cardinals are generalization of natural number, so they can tell us how big a set is. After we run out of natural numbers 1,2,3,... 10000000,...... we continue with $\aleph_0$, $\aleph_1$, $\aleph_3$,...¨ The $\aleph_0$ is called the first transfinite cardinal number.

Then there is $\omega$ - the lowest transfinite ordinal number, according to Wikipedia.

My questions are:

  1. Which of $\aleph_0$ and $\omega$ is "bigger" in terms of cardinality?

  2. $\aleph_0$ is cardnality of natural numbers. What are some examples of sets that have cardinality $\omega$, or also cardinality $\aleph_0$?

  3. $\mathbb{R}$ has cardinality $\mathfrak{c}$ - "infinite cardinal number". I know $\mathfrak{c}$ > $\aleph_0$, but what about $\omega$ and $\aleph_1$, $\aleph_2$ etc.?

Thank you in advance. If I get something in this concept completely wrong, please correct me so I can edit the question accrodingly.

$\endgroup$
12
  • 6
    $\begingroup$ $\aleph_0$ is a cardinal while $\omega$ is an ordinal. The cardinality of $\omega$ is $\aleph_0$. Saying "The $\aleph_0$ is called the first transfinite ordinal number" is wrong. So too is "examples of sets that have cardinality $\omega$" $\endgroup$
    – Henry
    Aug 13, 2021 at 13:01
  • 1
    $\begingroup$ @TerezaTizkova, we do not really say "the cardinality of $\omega$ is $\aleph_0$". I think we instead say "the cardinality of the set associated with $\omega$ is $\aleph_0$". This should alleviate confusion $\endgroup$
    – FShrike
    Aug 13, 2021 at 13:14
  • 1
    $\begingroup$ I edited in some resources for you + a brief overview of differences between ordinals and cardinals $\endgroup$
    – FShrike
    Aug 13, 2021 at 13:20
  • 2
    $\begingroup$ @TerezaTizkova: In a standard development a set theory, an ordinal is represented by the set of (the representations of) all smaller ordinals. Therefore "the cardinality of $\omega$ is $\aleph_0$" is short for what perhaps ought to be expressed "There are $\aleph_0$ different ordinals that come before $\omega$". $\endgroup$ Aug 13, 2021 at 14:08
  • 5
    $\begingroup$ Adding to the confusion is that set theory usually uses a representation of cardinal numbers where each of them is represented by the first ordinal to have the cardinality in question. (This works because it can be proved that every set has the same cardinality as some ordinal, which is a deep result requiring the Axiom of Choice). So in the standard development, the set representing the concept $\omega$ is literally the same set that represents the concept $\aleph_0$. The different notations indicate that we use that set in different ways when we treat it as an ordinal vs a cardinal. $\endgroup$ Aug 13, 2021 at 14:12

2 Answers 2

10
$\begingroup$

$\omega$ and $\aleph_0$ are the same set (the natural numbers $\{0,1,2,3,\ldots\}$) by different names. $\omega$ stresses the fact that we see it as an ordinal number (the smallest one that is infinite) while $\aleph_0$ is a name that says it is the first (i.e. of index $0$) in the transfinite sequence of cardinal numbers. All cardinals are special ordinal numbers, which in turn are transitive sets well-ordered by $\in$. All this is standard modern set theory (assuming ZFC standard axioms, including well-foundedness). As to the continuum $\mathfrak{c}$ we can say that $\mathfrak{c} \ge \aleph_1$ (it's uncountable) but not much more. Also, there is a theorem that $\text{cf}(\mathfrak{c})$ (the cofinality) cannot be $\omega$, so that $\mathfrak{c}=\aleph_{\omega}$ is not possible; but other than that restriction it can be any uncountable aleph (consistently).

So it's more correct to say sets of cardinality $\aleph_0$ (not cardinality $\omega$, though one does see it occasionally). Ordinals are for "order things", cardinals for "sizes" of sets.

$\endgroup$
0
6
$\begingroup$
  1. $\omega$ considered as an ordinal is not "bigger in terms of cardinality" since $\omega$ is an ordinal, $\aleph_0$ is a cardinal - the two represent different things, and cannot be compared like this. Note: see Rob Arthan’s comment about how $\omega$ has the cardinal $\aleph_0$ associated with it, and in a certain context it is valid to say $\omega=\aleph_0$, but always bear in mind a difference between ordinal and cardinal - a difference in usage, since I have learnt now that formally we take $\omega$ and $\aleph_0$ to be the very same object.
  2. No sets have cardinality $\omega$, since $\omega$ is not a cardinal. Examples of "countable" sets (i.e. have cardinality lesser or equal to $\aleph_0$) are the evens, the odds, the integers, the rationals, the algebraic numbers,... Note: same note as in $1)$ - see the comments.
  3. $\frak{c}$ is an infinite cardinal, but so is $\aleph_0$. The idea that $\frak{c}$ is the second smallest infinite cardinal is called the continuum hypothesis, which I believe is not provable in ZF. $\aleph_1=\frak{c}$ is the continuum hypothesis.

A set which has $\omega$ as its greatest ordinal has cardinality $\aleph_0$. However, $\omega+1\gt\omega$, but the set associated with this does not naively have cardinality $\aleph_0+1\gt\aleph_0$. See Hilbert's Hotel for a classic description of this. Two sets have the same cardinality if and only if there exists a bijection between them. Two sets have the same ordinals (I think) if each element can be uniquely attached a different ordinal. In this way, strangely, $1+\omega=\omega$ but $\omega+1\gt\omega$. See ordinal arithmetic.

I should also add for the sake of your understanding that all sets described by the maximum ordinal of $\omega,\omega+1,\omega+2,\omega+3,\omega+4,\omega+5,\cdots,2\omega,3\omega,\cdots,\omega^2,\omega^3,\cdots,\omega^\omega,\cdots,\omega^{\omega^\omega},\cdots$ have cardinality $\aleph_0$ - they are countable ordinals. Moreover, $\omega^{\omega^{\omega^{\omega^\cdots}}}=\varepsilon_0$ is also a countable ordinal. It is only when a set has $\Omega=\omega_1$ as its largest ordinal that the set has a cardinality greater than $\aleph_0$. This set is the set of all countable ordinals, and an example of this (if you take the continuum hypothesis to be true) is the real numbers.

Even more unintuitively (for some), the set of reals has the same cardinality as the interval $(0,1)$. In fact, $\mathbb{R}^2,\mathbb{R}^3,\mathbb{R}^4,\cdots$ all have the same cardinality, the cardinality of the continuum $\frak{c}$. We know this because there are ways to construct bijections between all of these.

P.S. any expert reading this who knows a proof / a link to a proof that $\mathbb{R}^n$ has a bijection with $\mathbb{R}$, it would be much appreciated if you could comment a link!

$\endgroup$
11
  • 2
    $\begingroup$ I thought $\aleph_1=\frak{c}$ is the continuum hypothesis, rather than $\aleph_2$. $\endgroup$
    – Henry
    Aug 13, 2021 at 13:06
  • $\begingroup$ Excuse me - as I wrote I momentarily interpreted subscript $2$ as the second cardinal @Henry $\endgroup$
    – FShrike
    Aug 13, 2021 at 13:06
  • 3
    $\begingroup$ That $\mathbb{R}^n$ has the same cardinality of $\mathbb{R}$ can just be seen by interlacing digits and working instead with $(0,1)^n$ and $(0,1)$: take $0.a_0 a_1 a_2 ...$ and $0.b_0 b_1 b_2...$ and combine to make $0.a_0 b_0 a_1 b_1 a_2 b_2 ...$. The same principle works with larger products, and also countable products: place (for example) the first real's digits on the powers of first prime, the second real's digits on the powers of the second prime, and so on. The only concern is that you need to pick a unique representation for the real number, but that's not really hard. $\endgroup$ Aug 13, 2021 at 15:56
  • 2
    $\begingroup$ Your points 1 and 2 are plain wrong in the standard way of viewing ordinals and cardinals in set theory. As pointed out in comments and @HennoBrandsma's answer $\omega = \aleph_0$ in the standard approach. Yes $\omega + 1 > \omega$, when you use $>$ to denote the ordering relation on the ordinals, but $\omega + 1 = \omega$ when you use $>$ to denote the ordering relation on the cardinals - this is an ambiguity in the use of the symbol $<$, not an ambiguity in the meaning of the first infinite ordinal $\omega$ and the first infinite cardinal $\aleph_0$, which are equal in the usual approach. $\endgroup$
    – Rob Arthan
    Aug 13, 2021 at 23:01
  • 1
    $\begingroup$ I think I understand your thinking and, as I don't teach, I am not qualified to comment on the pedagogical side(but I will anyway $\ddot{\smile}$). But if you are teaching set theory along the usual lines (using ordinals to represent cardinals), then $\omega$ and $\aleph_0$ are equal objects in the world of sets that we are talking about. This would have driven me to distraction as an undergraduate: if $\omega = \aleph_0$ how can $\aleph_0$ be a cardinal if $\omega$ is not? If you want to "drill in a difference", then you need to use a different definition of cardinal. $\endgroup$
    – Rob Arthan
    Aug 13, 2021 at 23:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.