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.