The order type of the rational numbers

Take any set and place an order on it. If the order is a well-order (i.e. if every subset has a least element), then the set has the same order type as some particular ordinal. But the notion of order type can be extended beyond well-ordered sets. Any two ordered sets are said to have the same order type if they are order isomorphic: if there’s a bijective map f from one set to the other such that both f and f-1 preserve the ordering of elements.

One structure that has a very interesting order type is the rational numbers. After all, the rationals are a countable set, but every rational number resembles a “limit ordinal” in the sense that it has no immediate predecessor.

One question that we can ask to get some insight about the order type of the rational numbers is: what ordinals can be found within the rationals? That is, take some well-ordered subset of the rationals. Look at the order type of this subset. This order type corresponds to some ordinal. And different choices of well-ordered subsets of the rationals give us different ordinals! So which ordinals can we “find” within the rationals in this sense?

First off, every finite ordinal can obviously be found. To find the ordinal n, just take the subset {0, 1, 2, …, n-1}. We can also find ω! You can just take the subset {0, 1, 2, 3, …}. What about ω+1? Try for yourself: can you construct a subset of the rationals with the order type of ω+1?

There’s no unique way to do it, but one easy way is to take the subset {1/2, 3/4, 7/8, …, 1}. This set has a countable infinity of elements, one for each natural number, after all of which comes a single element: exactly the order type of ω+1!

If we want a subset of the rationals with order type ω+2, we can use the same trick: {1/2, 3/4, 7/8, …, 1, 2}. And clearly this extends for any ω+n. But how about ω+ω? Can you construct a subset of the rationals with this order type? (Do it yourself before reading on!)

Here’s one way: {1/2, 3/4, 7/8, …, 1+1/2, 1+3/4, 1+7/8, …}. It should be easy to see how to extend this trick to get ω⋅3, ω⋅4, and indeed ω⋅n for any finite n. You can even naturally extend this to get to ω⋅ω. But then what? Are we finished?

If you guessed no, you’re right! We can find subsets of the rationals with order type ω3, and ωn for any finite n, and ωω. (Try it!) And we can keep going beyond that as well. So how high can you go?

Turns out that EVERY countable ordinal can be embedded into the rationals, under the usual order! So in some sense the order type of the rationals is as complicated as possible while still being countable. Also, remember that the set of countable ordinals is uncountably large. So this means that the rationals are a countable ordered set that has all of the uncountably many countable ordinals embedded within it! Isn’t that great?

(One thing that makes this seem less insane is that when we’re looking at what ordinals can be embedded in the rationals, we’re searching through different subsets of the rationals. And even though the rationals are countable, the set of all subsets of the rationals is uncountably large.)

One more interesting thing: the set of all subsets of the rationals has cardinality ℶ1. But the set of all ordinals that can be embedded into the rationals is ω1, which has cardinality ℵ1. So if we start with the set of all subsets of the rationals, then strip away all but those that are well-ordered, and then choose just a single representative for each order type, we get a set of cardinality ℵ1. And there is no guarantee that this final set has the same cardinality as the original set, because this is the continuum hypothesis! This is a way to think about how to “construct” a real life set with cardinality ℵ1: look at the set of well-ordered subsets of the rationals, and split it into order-type equivalence classes.

Leave a Reply