The transfinite subway

Today, we move from the countable to the uncountable and encounter another counter-intuitive infinite thought experiment. I first heard this one in a bar in Toronto in 2012, though it’s been around for much longer.

The math in this post is not extraordinarily difficult, but it is substantially more sophisticated than anything we’ve done here before. There is a new page, Ordinals and Cardinals, that contains some relevant definitions and facts. In particular, you will need to know what ordinals are and that $\omega_1$ is the least uncountable ordinal. We will also need the following fact:

• Any countable union of countable sets is itself countable. As a consequence, if $A$ is a countable subset of $\omega_1$ (i.e. $A$ is a countable set of countable ordinals), then $A$ is bounded below $\omega_1$ in the sense that there is $\beta < \omega_1$ such that, for every $\alpha \in A$, $\alpha < \beta$. This is illustrated in the following crude drawing.

Without further ado, down to the subway tracks.

There’s a subway line (the Transfinite Line) running from the airport to the Hilbert Hotel. The stations are labeled in order by ordinal numbers, with the airport at Station 0 and the Hilbert Hotel at Station $\omega_1$. The Transfinite Line has other peculiarities in addition to its transfinite length. On each run it makes from the airport to the hotel, the following rules must be followed. First, before leaving the airport, countably infinitely many passengers (i.e. one for each natural number) get on the train. Upon arriving at each later station prior to the Hilbert Hotel, two things happen:

• First, if there are any passengers on the train when it arrives at the station, exactly one of them gets off. This passenger cannot board this train again during this run, either at this or any later station.
• Second, countably infinitely many new passengers get on the train.

The question is simply this: How many passengers are on the train when it pulls into the Hilbert Hotel at Station $\omega_1$? Take a few moments to consider this.

I imagine a typical thought process when first encountering this problem might be roughly as follows. First, you probably think, ‘There are so many more people getting on the train than there are getting off at each station, so there must be lots of people on the train, probably uncountably many, when the train arrives at the Hilbert Hotel.’ Thinking a bit more, you might notice that this problem bears a certain similarity to the problem discussed here on Monday about gold coins. You might realize that we haven’t specified which passenger gets off the train when the train arrives at a station, and you might suspect that, as was the case with the gold coins, the answer can vary depending on this choice. You might thus argue that we have not given enough information to determine the answer.

This is a tempting thought, but, somewhat surprisingly, it is incorrect. There is a definite answer to the question, and it is not dependent on the choice of which passenger gets off at each station. To see this, though, we’re going to have to do a bit of work. We first need some facts about functions from $\omega_1$ to $\omega_1$.

Definition: Suppose $f:\omega_1 \rightarrow \omega_1$ is a function. An ordinal $\beta < \omega_1$ is called a closure point for $f$ if, for every $\alpha < \beta$, we also have $f(\alpha) < \beta$.

Lemma: Suppose $f:\omega_1 \rightarrow \omega_1$ is a function, and suppose $\alpha < \omega_1$. Then there is an ordinal $\beta$ such that $\alpha < \beta < \omega_1$ and $\beta$ is a closure point for $f$.

Proof: We will define an infinite increasing sequence of countable ordinals $\alpha_0 < \alpha_1 < \alpha_2 < \ldots$, one for each natural number, as follows. First, let $\alpha_0 = \alpha$. Next, consider the set $A_0 = \{f(\xi) \mid \xi < \alpha_0\}$, i.e. $A_0$ is the set of all values $f$ takes when applied to ordinals less than $\alpha_0$. Since $\alpha_0$ is a countable ordinal, $A_0$ is a countable set. Therefore, $A_0$ is bounded below $\omega_1$, i.e. we can find $\gamma_0 < \omega_1$ such that, for all $\eta \in A_0$, $\eta < \gamma_0$. Choose $\alpha_1 < \omega_1$ to be large enough so that $\alpha_1$ is larger than both $\alpha_0$ and $\gamma_0$.

To define $\alpha_2$, repeat the process, but with $\alpha_0$ replaced by $\alpha_1$. More precisely, let $A_1 = \{f(\xi) \mid \xi < \alpha_1\}$ and choose $\alpha_2 < \omega_1$ large enough so that $\alpha_2 > \alpha_1$ and, for all $\eta \in A_1$, $\alpha_2 > \eta$. Continue in this way to define $\alpha_n$ for every natural number $n$.

At the end of this process, let $\beta$ be the least ordinal such that $\beta > \alpha_n$ for every natural number $n$. Since there are only countably many $\alpha_ns$, we know that $\beta < \omega_1$. It is clear that $\alpha < \beta$. I claim that $\beta$ is a closure point for $f$. To see this, we must show that, for every $\xi < \beta$, $f(\xi) < \beta$. So let $\xi < \beta$. Since $\beta$ is the least ordinal greater than all of the $\alpha_ns$, there is some $m < \omega$ such that $\xi < \alpha_m$. But then $f(\xi) \in A_m$ and, when we defined $\alpha_{m+1}$, we made sure that $\alpha_{m+1} > \eta$ for every $\eta \in A_m$. Therefore, $f(\xi) < \alpha_{m+1} < \beta$, so $\beta$ is indeed a closure point for $f$. This completes the proof of the Lemma. $\square$

Now let us return to our subway. Suppose we consider a specific run of the train. For each ordinal $\alpha < \omega_1$, let $B_\alpha$ be the set of $\eta < \omega_1$ such that a passenger who boarded the train at Station $\alpha$ got off the train at Station $\eta$. Since only countably many passengers got on at Station $\alpha$, $B_\alpha$ is a countable set and therefore is bounded below $\omega_1$.

We now define a function $f:\omega_1 \rightarrow \omega_1$ as follows. For every $\alpha < \omega_1$, let $f(\alpha)$ be the least ordinal $\gamma$ such that $\gamma > \eta$ for all $\eta \in A_\alpha$ (i.e. $f(\alpha)$ is the least strict upper bound for $A_\alpha$).

Claim: If $\beta < \omega_1$ is a closure point for $f$, then the subway was empty upon arriving at Station $\beta$.

Proof: Let $\beta < \omega_1$ be a closure point for $f$, and suppose that the train was not empty when it arrived at Station $\beta$. We will derive a contradiction.

Since the train was not empty when it arrived at the station, one passenger had to disembark at Station $\beta$. Therefore, there must have been some $\alpha < \beta$ such that this passenger got on the train at Station $\alpha$. Therefore, there is a passenger who got on the train at Station $\alpha$ and off at Station $\beta$, so $\beta \in A_\alpha$. By our definition of $f$, this means that $f(\alpha) > \beta$. However, $\beta$ is a closure point for $f$ and $\alpha < \beta$, which means $f(\alpha) < \beta$. This is a contradiction, and we have finished the proof of the claim. $\square$

We are now ready to reach our conclusion.

Solution: The train was empty when it arrived at the Hilbert Hotel!

Proof: Suppose the train was not empty. We will again reach a contradiction.

Since the train was not empty, we can choose a passenger who was on the train when it got to the hotel. There must be an ordinal $\alpha < \omega_1$ such that this passenger boarded the train at Station $\alpha$. But now we can invoke our Lemma and find some ordinal $\beta < \omega_1$ such that $\alpha < \beta$ and $\beta$ is a closure point for $f$. But now, by our previous claim, the train was empty upon arriving at Station $\beta$, so our passenger who got on at Station $\alpha$ must in fact have gotten off before Station $\beta$ and, by the rules of the subway, could not have reboarded the train. This passenger therefore could not have been on the train when it arrived at the Hilbert Hotel! $\square$

Comparing this with the result from the gold coins puzzle, we get our first indication that the class of infinities is not some undifferentiated mass and that different sizes of infinity can in fact behave quite differently. We will hopefully see many more such instances of this phenomenon in later posts.

The real lesson here, though, is that if you’re going to the Hilbert Hotel, don’t take the Transfinite Line; you’ll never get there. Instead, shell out the extra money to take a cab.

P.S. You may notice that this problem is not exactly analogous to the gold coins problem in the following sense. In this problem, the passenger who gets off at a given station must have gotten on at a strictly earlier station, whereas, in the gold coins problem, on a given night, the demon is allowed to remove a coin that it placed on that night. Indeed, if the rules of the subway were revised so that, at each station, the passengers boarded the train before one passenger (possibly one who had just gotten on) disembarked, then we are in the same indeterminate situation we were in with the gold coins. (Of course, this would go against standard subway etiquette.) However, there still is a real difference between the gold coin scenario and this one. If we restrict the demon so that it can only remove coins that were placed on previous nights, we have not actually changed anything and are still in an indeterminate case (Exercise: Why?). The mathematical difference responsible for this is that, though functions from $\omega_1$ to $\omega_1$ necessarily have closure points, functions from $\omega$ to $\omega$ might not.