Ordinals and Cardinals

To speak with any precision about higher infinities, we need to develop the basic theory of ordinal and cardinal numbers. We do that here, but first we need some even more basic notions about orders.

(We won’t be very formal here, but this informality may also lead to a lack of clarity. If anything is not clear, please let me know!)

Well-orderings

You probably have an intuitive idea of what an ordering is. You have examples like the usual ordering $\leq$ on the set of real numbers, $\mathbb{R}$, or on the set of natural numbers, $\mathbb{N}$. But we need to be a bit more precise. For us, if $X$ is a set, then $\leq_X$ is a linear ordering on $X$ if the following conditions hold:

1. (Reflexivity) For all $x \in X$, $x \leq_X x$.
2. (Transitivity) For all $x, y,z \in X$, if $x \leq_X y$ and $y \leq_X z$, then $x \leq_X z$.
3. (Anti-symmetry) For all $x,y \in X$, if $x \leq_X y$ and $y \leq_X x$, then $x = y$.
4. (Linearity) For all $x,y \in X$, it must be the case that $x \leq_X y$ or $y \leq_X x$.

If $\leq_X$ is a linear ordering on $X$, then we define the strict order $<_X$ by letting $x <_X y$ if $x \leq_X y$ and $x \neq y$.

You are invited to check that the usual orderings on $\mathbb{R}$ and $\mathbb{N}$ satisfy the definition given above. We will be interested in a stronger notion, that of a well-ordering: If $\leq_X$ is a linear ordering on a set $X$, then we say $\leq_X$ is a well-ordering if every non-empty subset of $X$ has a $\leq_X$-least element, i.e. for every non-empty $Y \subseteq X$, there is $y \in Y$ such that, for all $x \in Y$, $y \leq_X x$.

Returning to our familiar examples, we see that the usual ordering on $\mathbb{R}$ is not a well-ordering. For example, the let $\{\frac{1}{n+1} \mid n \in \mathbb{N}\}$ has no least element. On the other hand, the usual ordering on $\mathbb{N}$ is a well-ordering (Exercise: Why?).

Ordinals

Ordinal numbers (or ordinals) describe the order types of well-orderings. A key fact is that the class of ordinal numbers is itself well-ordered. And what are these ordinal numbers? For us, an ordinal number is precisely the set of ordinal numbers less than it.

This is all rather imprecise and probably confusing. It should help to look at some ordinals, starting from the smallest.

To begin with, every natural number is an ordinal, describing the unique order type of an ordering with that number of elements. (For example, there’s essentially only one way to order three elements: there’s a first element, a second, and a third. As we’ll see, this is no longer true for infinite sets, for which there are many essentially different well-orderings.) But we said that an ordinal is precisely the set of ordinals smaller than it. There are no ordinals smaller than $0$, so, by our convention, $0=\emptyset$. Then $1 = \{0\}$, $2 = \{0,1\}$, etc.

This takes care of the natural numbers. What comes next? Well, next comes the least ordinal greater than all of the natural numbers. And remember, being greater means ‘contains as an element,’ so the next ordinal is precisely the set of all natural numbers, $\mathbb{N}$. As an ordinal, we refer to this as $\omega$.

Now for a general observation: every ordinal $\alpha$ has a least ordinal greater than it. This ordinal is referred to as the successor of $\alpha$ and is denoted $\alpha + 1$. As a set, it is $\alpha \cup \{\alpha\}$, i.e. it contains all of the elements of $\alpha$ and $\alpha$ itself. The successor of $\alpha + 1$ is $\alpha + 2$, and so on.

Thus, after $\omega$ comes $\omega + 1$. What order type does this describe? Let $X = \mathbb{N} \cup \{\infty\}$, and define an ordering $\leq_X$ by saying $x \leq_X y$ if either $x$ and $y$ are both natural numbers and $x \leq y$ in the usual ordering or $y = \infty$. Thus, $\leq_X$ orders $\mathbb{N}$ as usual and stipulates that $\infty$ is larger than every natural number. The order type of $\leq_X$ is precisely $\omega + 1$.

After $\omega+1$ comes $\omega+2, \omega+3$, and so on. Then comes $\omega + \omega$, also denoted by $\omega \cdot 2$. Skipping ahead, we get $\omega \cdot 3, \omega \cdot 4$. Further down the line, we get $\omega \cdot \omega$, also denoted by $\omega^2$. We then get $\omega^3, \omega^4, \ldots, \omega^\omega$. We could keep going like this for quite a while.

Cardinals

Cardinal numbers (or cardinals) are, unsurprisingly, numbers that describe cardinality. We’ve already discussed cardinality in the Sets, Functions, and Cardinality page. One way to state the Axiom of Choice, one of the standard axioms of set theory, is that, for every set, there is a bijection between that set and an ordinal. Therefore, for every cardinality, there is an ordinal of that cardinality. And, because the class of ordinals is well-ordered, there is in fact a least ordinal of that cardinality. We will associate each cardinality with the least ordinal of that cardinality, and call such an ordinal a cardinal.

A consequence of the fact that the ordinals are well-ordered is the fact that the cardinals are also well-ordered. We have seen that there is a least infinite cardinal, corresponding to the cardinality of the set of natural numbers. This is typically denoted $\aleph_0$. There is thus a next smallest infinite cardinal, denoted by $\aleph_1$. There is then $\aleph_2, \aleph_3, \ldots, \aleph_\omega, \ldots$ and so on.

Every natural number is therefore a cardinal. $\omega$ is the least countably infinite ordinal, so $\omega$ is a cardinal. As noted in the previous paragraph, this cardinal is also denoted $\aleph_0$. (Typically, the $\omega$-notation is used when thinking of it as an ordinal and the $\aleph$-notation when thinking of it as a cardinal, though, in practice, the two are interchangeable.) All of the other ordinals described in the section on Ordinals turn out to be countable. The least uncountable ordinal, corresponding to the cardinal $\aleph_1$, is denoted by $\omega_1$. As a set, $\omega_1$ is precisely the set of all countable ordinals. The ordinal corresponding to $\aleph_2$ is $\omega_2$, the ordinal corresponding to $\aleph_\omega$ is $\omega_\omega$, and so on.