25  Cardinal Numbers

We know quite a bit about cardinal numbers by now, but we still do not know what they are. Speaking vaguely, we may say that the cardinal number of a set is the property that the set has in common with all sets equivalent to it. We may try to make this precise by saying that the cardinal number of \(X\) is equal to the set of all sets equivalent to \(X\), but the attempt will fail; there is no set as large as that. The next thing to try, suggested by analogy with our approach to the definition of natural numbers, is to define the cardinal number of a set \(X\) as some particular carefully selected set equivalent to \(X\). This is what we proceed to do.

For each set \(X\) there are too many other sets equivalent to \(X\); our first problem is to narrow the field. Since we know that every set is equivalent to some ordinal number, it is not unnatural to look for the typical sets, the representative sets, among ordinal numbers.

To be sure, a set can be equivalent to many ordinal numbers. A hopeful sign, however, is the fact that, for each set \(X\), the ordinal numbers equivalent to \(X\) constitute a set. To prove this, observe first that it is easy to produce an ordinal number that is surely greater, strictly greater, than all the ordinal numbers equivalent to \(X\). Suppose in fact that \(\gamma\) is an ordinal number equivalent to the power set \(\mathcal{P}(X)\). If \(\alpha\) is an ordinal number equivalent to \(X\), then the set \(\alpha\) is strictly dominated by the set \(\gamma\) (i.e., \(\text{card } \alpha < \text{card } \gamma\)). It follows that we cannot have \(\gamma \le \alpha\), and, consequently, we must have \(\alpha < \gamma\). Since, for ordinal numbers, \(\alpha < \gamma\) means the same thing as \(\alpha \in \gamma\), we have found a set, namely \(\gamma\), that contains every ordinal number equivalent to \(X\), and this implies that the ordinal numbers equivalent to \(X\) do constitute a set.

Which one among the ordinal numbers equivalent to \(X\) deserves to be singled out and called the cardinal number of \(X\)? The question has only one natural answer. Every set of ordinal numbers is well ordered; the least element of a well ordered set is the only one thet seems to clamor for special attention.

We are now prepared for the definition: a cardinal number is an ordinal number \(\alpha\) such that if \(\beta\) is an ordinal number equivalent to \(\alpha\) (i.e., \(\text{card } \alpha = \text{card } \beta\)), then \(\alpha \le \beta\). The ordinal numbers with this property have also been called initial numbers. If \(X\) is a set, then \(\text{card } X\), the cardinal number of \(X\) (also known as the power of \(X\)), is the least ordinal number equivalent to \(X\).

Exercise 25.1 Prove that each infinite cardinal number is a limit number.

Since each set is equivalent to its cardinal number, it follows that if \(\text{card } X = \text{card } Y\), then \(X \sim Y\). If, conversely, \(X \sim Y\), then \(\text{card } X \sim \text{card } Y\). Since \(\text{card } X\) is the least ordinal number equivalent to \(X\), it follows that \(\text{card } X \le \text{card } Y\), and, since the situation is symmetric in \(X\) and \(Y\), we also have \(\text{card } Y \le \text{card } X\). In other words \(\text{card } X = \text{card }Y\) if and only if \(X \sim Y\); this was one of the conditions on cardinal numbers that we needed in the development of cardinal arithmetic.

A finite ordinal number (i.e., a natural number) is not equivalent to any finite ordinal number distinct from itself. It follows that if \(X\) is finite, then the set of ordinal numbers equivalent to \(X\) is a singleton, and, consequently, the cardinal number of \(X\) is the same as the ordinal number of \(X\). Both cardinal numbers and ordinal numbers are generalizations of the natural numbers; in the familiar finite cases both the generalizations coincide with the special case that gave rise to them in the first place. As an almost trivial application of these remarks, we can now calculate the cardinal number of a power set \(\mathcal{P}(A)\): if \(\text{card } A = a\), then \(\text{card } \mathcal{P}(A) = 2^{\alpha}\). (Note that the result, though simple, could not have been stated before this; till now we did not know that \(2\) is a cardinal number.) The proof is immediate from the fact that \(\mathcal{P}(A)\) is equivalent to \(2^{A}\).

If \(\alpha\) and \(\beta\) are ordinal numbers, we know what it means to say that \(\alpha < \beta\) or \(\alpha \le \beta\). It follows that cardinal numbers come to us automatically equipped with an order. The order satisfies the conditions we borrowed for our discussion of cardinal arithmetic. Indeed: if \(\text{card } X < \text{card } Y\), then \(\text{card } X\) is a subset of \(\text{card } Y\), and it follows that \(X \precsim Y\). If we had \(X \sim Y\), then, as we have already seen, we should have \(\text{card } X = \text{card } Y\); it follows that we must have \(X \prec Y\). If, finally, \(X \prec Y\), then it is impossible that \(\text{card } Y \le \text{card } X\) (for similarity implies equivalence), and hence \(\text{card } X < \text{card } Y\).

As an application of these considerations we mention the inequality

\[ a < 2^{a}, \]

valid for all cardinal numbers \(a\). Proof: if \(A\) is a set with \(\text{card } A = a\), then \(A \prec \mathcal{P}(A)\), hence \(\text{card } A < \text{card } \mathcal{P}(A)\), and therefore \(a < 2^{a}\).

Exercise 25.2 If \(\text{card } A = a\), what is the cardinal number of the set of all one-to-one mappings of \(A\) onto itself? What is the cardinal number of the set of all countably infinite subsets of \(A\)?

The facts about the ordering of ordinal numbers are at the same time facts about the ordering of cardinal numbers. Thus, for instance, we know that any two cardinal numbers are comparable (always either \(a < b\), or \(a = b\), or \(b < a\)), and that, in fact, every set of cardinal numbers is well ordered. We know also that every set of cardinal numbers has an upper bound (in fact, a supremum), and that, moreover, for every set of cardinal numbers, there is a cardinal number strictly greater than any of them. This implies of course that there is no largest cardinal number, or, equivalently, that there is no set that consists exactly of all the cardinal numbers. The contradiction, based on the assumption that there is such a set, is known as Cantor’s paradox.

The fact that cardinal numbers are special ordinal numbers simplifies some aspects of the theory, but, at the same time, it introduces the possibility of some confusion that it is essential to avoid. One major source of difficulty is the notation for the arithmetic operations. If \(a\) and \(b\) are cardinal numbers, then they are also ordinal numbers, and, consequently, the sum \(a + b\) has two possible meanings. The cardinal sum of two cardinal numbers is in general not the same as their ordinal sum. All this sounds worse than it is; in practice it is easy to avoid confusion. The context, the use of special symbols for cardinal numbers, and an occasional explicit warning can make the discussion flow quite smoothly.

Exercise 25.3 Prove that if \(\alpha\) and \(\beta\) are ordinal numbers, then \(\text{card} (\alpha + \beta) = \text{card } \alpha + \text{card} \beta\) and \(\text{card } (\alpha \beta) = (\text{card } \alpha)(\text{card } \beta)\). Use the ordinal interpretation of the operations on the left side and the cardinal interpretation on the right.

One of the special symbols for cardinal numbers that is used very frequently is the first letter \((\aleph, \text{aleph})\) of the Hebrew alphabet. Thus in particular the smallest transfinite ordinal number, i.e., \(\omega\), is a cardinal number, and, as such, it is always denoted by \(\aleph_{0}\).

Every one of the ordinal numbers that we have explicitly named so far is countable. In many of the applications of set theory an important role is played by the smallest uncountable ordinal number, frequently denoted by \(\Omega\). The most important property of \(\omega\) is that it is an infinite well ordered set each of whose initial segments is finite; correspondingly, the most important property of \(\Omega\) is that it is an uncountably infinite well ordered set each of whose initial segments is countable.

The least uncountable ordinal number \(\Omega\) clearly satisfies the defining condition of a cardinal number; in its cardinal role it is always denoted by \(\aleph_{1}\). Equivelently, \(\aleph_{1}\) may be characterized as the least cardinal number strictly greater than \(\aleph_{0}\), or, in other words, the immediate successor of \(\aleph_{0}\) in the ordering of cardinal numbers.

The arithmetic relation between \(\aleph_{0}\) and \(\aleph_{1}\) is the subject of a famous old problem about cardinal numbers. How do we get from \(\aleph_{0}\) to \(\aleph_{1}\) by arithmetic operations? We know by now that the most elementary steps, involving sums and products, just lead from \(\aleph_{0}\) back to \(\aleph_{0}\) again. The simplest thing we know to do that starts with \(\aleph_{0}\) and ends up with something larger is to form \(2^{\aleph_{0}}\). We know therefore that \(\aleph_{1} \le 2^{\aleph_{0}}\). Is the inequality strict? Is there an uncountable cardinal number strictly less than \(2^{\aleph_{0}}\)? The celebrated continuum hypothesis asserts, as a guess, that the answer is no, or, in other words, that \(\aleph_{1} = 2^{\aleph_{0}}\). All that is known for sure is that the continuum hypothesis is consistent with the axioms of set theory.

For each infinite cardinal number \(a\), consider the set \(c(a)\) of all infinite cardinal numbers that are strictly less than \(a\). If \(a = \aleph_{0}\), then \(c(a) = \emptyset\); if \(a = \aleph_{1}\), then \(c(a) = \{ \aleph_{0} \}\). Since \(c(a)\) is a well ordered set, it has an ordinal number, say \(\alpha\). The connection between \(a\) and \(\alpha\) is usually expressed by writing \(a = \aleph_{\alpha}\). An equivalent definition of the cardinal numbers \(\aleph_{\alpha}\) proceeds by transfinite induction; according to that approach \(\aleph_{\alpha}\) (for \(\alpha > 0\)) is the smallest cardinal number that is strictly greater than all the \(\aleph_{\beta}\)’s with \(\beta < \alpha\). The generalized continuum hypothesis is the conjecture that \(\aleph_{\alpha + 1} = 2^{\aleph_{\alpha}}\) for each ordinal number \(\alpha\).