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.

rsz_1order1

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.

960x600_subway_station_in_long_exposure
A disappointingly finite subway line.

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.

Advertisements

One thought on “The transfinite subway

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s