• Oridnals and cardinals
• The System
• Day 1 - Explosion at infinity, or a ghost train?
• Day 2 - Infinitely many on each stop, but empty at ω
• Day 3 - Building to infinity
• Observations and constraints
• The transfinite subway challenge
• At most 1 passenger
• At most 2 passengers
• At most n
• Finite extensible trains
• Any countable ordinal
• Can we go further?

The following is largely stolen bits from a series published by Professor of Math and Philosophy Joel David Hamkins. I’ve left in the first-person statements he makes, not to take credit, but because I’m lazy about editing. Some of it is behind a paywall, but as I’m only taking some excerpts, and don’t plan on doing this with all his content, I’m sure he won’t mind my sharing a bit here, with all 24 of you. A novel construction, dubbed “The Infinite Subway System,” is explored to reveal some deep and surprising aspects of the behavior of infinite processes and ordinals.

If you’ve ever encountered the paradox of Hilbert’s Inifinite Hotel, and found that enjoyable, I encourage you to delve into this more sophisticated variant.

§Oridnals and cardinals

First, a very brief refresher on ordinals (and cardinals). Informally, they are the collection of numbers which extend the usual inuition of counting, starting with 0, 1, 2, etc. and continuing with no bound. A bit more formally, they are the canonical representatives of all well-ordered sets (linear orders with the property that any nonempty subset has a unique least member). A couple diagrams to help the intuition below:

^{Depiction of the finite ordinals, and the first infinite ordinal, ω}

^{Continuing past ω. Note the notation for addition, multiplication, and exponentiation (not shown here) is intuitive and well-defined} Keep in mind that there is no end to this sequence. The even more precise Set Theoretic definition starting with the empty set, ∅, we label as 0, {∅} as 1, {∅,{∅}} as 2, etc., where the order is just the elementhood set relation, may seem pedantic, but has advantages of making clear how to construct other ordinals (e.g. ω is just the union/supremum of the sets just defined, and ω + 1 is just the set of that set and all the prior ones, etc.).

Lastly, the subclass of ordinals which cannot be put in 1-to-1 correspondence with any lesser ordinal are called the cardinal numbers; they generalize the concept of size beyond the finite numbers, and into higher sizes of infinity. It can be shown that there is no largest such number. We’ll mostly be concerning ourselves with finite and countably-infinite (cardinality ω) sets here, but we’ll touch on larger sizes and point to further generalizations of the subway system which involve these higher infinite sizes.

§The System

Every morning in the island city of Infinitopolis, a train begins at the downtown terminal, station 0, and then proceeds uptown to station 1, station 2, station 3, and so forth—there is a station for every natural number—until finally arriving at the uptown terminus, station ω.

Different size trains are used on different days, with some able to accommodate only a fixed finite number of passengers in total, while others are finite but extensible, having a stretching capacity to accommodate any desired finite number of passengers, although not infinitely many at once. Fortunately, when these expandable trains run there are special helpers at every station wearing clean white linen gloves, tasked when necessary with gently pushing the boarding passengers onto the train, taking advantage of the stretchy extensible nature of the trains. Meanwhile, on other days there are larger trains able to accommodate an actually infinite collection of passengers at once, although some can hold only a countable infinity of passengers, while others hold uncountable multitudes.

§Day 1 - Explosion at infinity, or a ghost train?

On a particular day recently, there was a peculiar pattern of passengers embarking and disembarking the train. The train was of the finite but stretchy extensible kind and began at station 0, where a single passenger boarded an empty train. He rode just one stop and got off at station 1, whereupon two passengers boarded. One of them got off at the next stop, station 2, but three passengers boarded there. At station 3, again just one passenger disembarked, while four new people got on the train. Indeed, this pattern continued through all the finite stations—the train would pull in, a single passenger would disembark, and then increasingly large crowds would board the train. The train was therefore steadily accumulating riders with each subsequent stop, increasingly stretched and becoming stuffed more and more with passengers.

What would happen at station ω? Would the train suddenly burst apart at the terminal limit in a catastrophic explosion of mechanical train parts and humanity?

On this particular day, despite the increasingly crowded conditions on board, what was found sleekly gliding into station ω was a ghostly empty train—not a single passenger was on board. In fact, the conductors knew all along that it would happen like this, and so they weren’t worried about bursting the train’s capacity—they had checked the schedule of passenger itineraries in advance, and they knew the train would be empty at station ω. Here’s what the itinerary looked like:

It follows from this arrangement that whenever a person gets on the train, they are in some seat number n, and it will be station n at which they disembark. In particular, under this arrangement everyone who boards the train at some finite station will also exit the train at a finite station, and so there will be nobody left on the train when it arrives at station ω. This is how it becomes the ghostly empty train arriving at station ω.

§Day 2 - Infinitely many on each stop, but empty at ω

On another day I witnessed a different curious pattern. This train was of the actually infinite variety, and indeed, at station 0 infinitely many passengers boarded the train. At each subsequent finite station, one passenger disembarked, and infinitely many additional passengers got on. So at every stop, the train was accumulating infinitely many additional passengers. And yet, when the train pulled into station ω, it was again completely empty! Once again, the particulars of the ititnerary make this clear:

§Day 3 - Building to infinity

On yet another day, however, the train started empty at station 0, and two passengers boarded. At station 1, one passenger got off the train, and two passengers got on. Indeed, at every subsequent finite station n, one passenger got off the train, and two passengers got on. And on this particular day, the train pulled into station ω with infinitely many passengers. Here’s an itinerary that explains this:

§Observations and constraints

As you can see, the outcome is dependent on the particulars of the itinerary, since different itineraries and seating arrangements can affect the final outcome. An interesting question we can ask is what can we say for sure, given a scenario, about the possible final states at arrival.

As a simple example, consider a that two passengers get on board an empty train at station 0, and at every subsequent station, one passenger gets off and another passenger gets on the train. What can we assert about the state at station ω? It’s simple to come up with itineraries which result in either an empty train, or a single passenger (one person simply never disembarks), but arriving with 2 on board is impossible since at no station N onward can the same two people stay on board, given we require one to get off and we’ve only got two seats to work with.

There are some basic results about constraints which can be shown, but they’re not particularly interesting and a bit tedious to go through for this write up. What’s more interesting is to think about the following challenge.

§The transfinite subway challenge

It has become something of a local custom for the residents of Infinitopolis to challenge themselves with schemes of passenger itineraries that will enable someone to arrive at a very distant station, while still having at least one passenger disembark at every station along the way. To which stations can the residents of Infinitopolis travel this way, while obeying the challenge requirement that someone gets off at every station? How far can they go?

Of course, for any target ordinal station λ, if we allow a sufficient infinity of passengers boarding the train at the start, then we can simply have λ + 1 many passengers board at the start, assigning each passenger α ⩽ λ to disembark at station α, which will thereby make it to the target station λ. With a countable infinity of passengers boarding at the start, we can in this way reach any desired countable ordinal, while still having at least one disembarkment at every station along the way.

The smart challenge, of course, is to get as far as possible with always only finitely many passengers on board at any time. How far can you get?

So we have set ourselves the challenge to go a long way, but with a small train, perhaps of the finite extensible kind or perhaps with a rigidly fixed finite bound on the size. If the train can fit at most twenty-five people, for example, then how many ordinal stations can we traverse, while still having at least one passenger disembark at every station? Each disembarking passenger might be replaced by a new passenger boarding, within the limits of the train capacity. And we assume that passengers never reboard the train once having disembarked.

§At most 1 passenger

Trivial to see we can reach any finite ordinal, but must arrive at station ω empty because no passenger can stay on more than a single stop.

§At most 2 passengers

A two-seater train, I claim, can make it all the way to station ω², with a passenger disembarking at every single stop (and a new passenger boarding), before finally arriving empty for the first time at station ω². And furthermore, I claim, this distance ω² is the best possible.

Let me show first how we can get that far. Two people, Atticus and Adeline, board at station 0. Adeline will ride just one stop, while Atticus will stay on board until ω. At station 1, Adeline gets off, replaced by Abigail, who gets off at station 2, replaced by Andrea, who gets off at station 3, and so forth. At the finite stations, the women ride just one stop, while Atticus stays aboard. At station ω, he is the only one on board, and so he disembarks, while Benjamin and Beatrice board the train. Benjamin will stay aboard until ω+ω, while Beatrice will ride just one stop, replaced at station ω+1 by Bernadette, who rides just one stop, and so forth. At each station, the departing train has one man and one woman, but the women will always ride just one stop, while the man rides ω many stops. In this way, arriving at the limit stations ω · n, the man is on board alone and ready to disembark, at which point the process starts again until the next limit at ω · (n+1). So the train will be nonempty at every station up to ω², but it will become empty at that stage.

I claim that ω² is the best possible, in terms of distance reached under the requirements. To see this, observe that if the train holds at most two people and someone gets off at every station, then the in-station counts are always at most 1. In this case, the arrival passenger count at the limit stations ω · n must be at most 1, which means that the in-station counts at these stations will be zero. So cofinally often in ω² the train is empty in the station. So there could be nobody on board to arrive at station ω², and so the train will arrive empty at that station [this isn’t immediately obvious, so take some time to think about it].

§At most n

With some induction (left to the reader), you can prove the expected result: with a finite train of capacity n, we can get to station ωⁿ before the train arrives empty, if our itineraries have at least one passenger disembarking at every station along the way.

§Finite extensible trains

How far can we get with a finite extensible train, holding only finitely many passengers at any one time, with the feature that at every station, at least one passenger gets off?

The first easy observation to make is that we can get to ω^ω by combining the methods we have just discussed, which show that with n passengers allowed we can go ωⁿ many steps. Let us divide the overall trip to ω^ω into separate legs, viewing it as a journey from 0 to ω, and then from ω to ω², and then from ω² to ω³, and so on. All we need to do is arrange within each leg of the journey that we can get to the start of the next leg with a nonempty train. But that is precisely what we have already done, since with two passengers we can arrive with a passenger at ω, and with three passengers boarding at that point, we can arrive with a passenger at ω², and so on. In this way, with a finite extensible train, we can get all the way to ω^ω before the train arrives empty.

Is ω^ω the optimal result? After all, with n passengers we can get to ωⁿ, and so with arbitrary finite passengers, we should expect the supremum of these ordinals. Will ω^ω therefore be the best we can achieve?

§Any countable ordinal

Actually, we can do much better. What I claim is that with a finite extensible train, capable of holding any finite number of passengers (but never infinitely many), we can reach any desired countable ordinal with a nonempty train, while still having a passenger disembark at every station along the way.

Let us prove this by induction on the station target α. We have already seen how to do this for ordinals up to ω^ω. And if we can reach ordinal α with a nonempty train, then clearly we can reach ordinal α + 1 with a nonempty train, since we can just have a passenger board at station α and ride one more stop. (Alternatively, we can have a single extra passenger board at station 0 and stay on board the whole trip until station α, at which point they can ride to station α + 1.)

Consider now a countable limit ordinal station λ, and suppose inductively that there are systems of itineraries able to reach any particular ordinal α < λ. Since λ is a countable ordinal, we may find an increasing cofinal sequence λ₀ < λ₁ < ··· with λ = sup_n λ_n. Now, for each n, fix a system of passenger itineraries that will go up to (and including) λ_n steps—in particular, it arrives at λ_n with someone on board to disembark. We combine these itineraries as follows. At station zero, we mount the λ₀ system, plus one extra person, Leonardo, who will last until station λ. At station λ₀, everyone disembarks except Leonardo, and new people board in accordance with the λ₁ system. Between λ₀ and λ₁ we undertake the λ₁ system. And so forth. Leonardo stays on for the duration, but between λ_n and λ_n+1 we follow the λ_n+1 system of itineraries. So we will always have only finitely many people on board, and someone will disembark at every station. And yet Leonardo will remain on the train to disembark at station λ.

§Can we go further?

Can we reach the first uncountable ordinal ω₁ itself this way? That is, can we unify all the various particular solutions reaching the various countable ordinals with a single uncountable schedule of passenger itineraries that proceeds all the way to ω₁? We know how to reach any particular countable ordinal α, yes, each with a separately defined schedule aimed at reaching that particular ordinal, but the question I am asking is whether we can do so in a fully uniform manner, whether we can describe a single uncountable trip, a single schedule of passenger itineraries in the finite extensible train that proceeds through every countable ordinal station in one run, while still having a disembarkment at every station stop along the way.

Unfortunately, no, it is impossible to reach the first uncountable ordinal ω₁ by such a process. There is no schedule of passenger itineraries with a finite extensible train car that passes through every countable ordinal with at least one disembarkment at every station. Station ω₁ will thus never itself be realized in the Infinitopolis subway challenge.

In fact, it can be shown that even with countably infinite capacity, it cannot be done. Proof is a bit long and involved, so it will not be included here. Perhaps a follow up post…