The infinite subway paradox—extending into the transfinite

We extend the infinite subway paradox into the countable ordinals. Can you meet the infinite subway challenge?

Welcome to this series of essays on the infinite subway paradox. We began with an introduction to the infinite subway paradox, and then explored a fuller range of paradox in in last week’s essay. Today, we shall explore the extension of the paradox to higher ordinals. Can you meet the transfinite subway challenge? To which ordinal station can your reach with a bounded-size train, while still having disembarkments at every station along the way?

Extending the subway line transfinitely

I am so pleased to tell you of the wondrous feat of mathematical construction that has recently been achieved in the city of Infinitopolis—the inhabitants have come out in a grand celebration, for the city engineers have just completed a vast new extension of the subway line to many further stations at the transfinite ordinals beyond ω. We now have stations up to ω + ω, and ω · 3, indeed ω² and much larger ordinals still.

How far does it go? This was kept a closely guarded secret during construction, and the full plans were known at first only to the chief engineer. But with the line now completed, the question of extent is open for general discovery as the residents explore their new subway line. Perhaps there is a station for every countable ordinal? Might we hope for stations at uncountable ordinals?

The transfinite subway challenge

With the new line in place, 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?

Naturally various teams of city residents embark competitively with carefully planned secret systems of passenger itineraries, and it is now a festive friendly competition as teams go further and further. The best records are announced on a large public display at the town center. The civic custom is altogether similar in spirit to the practice in their sister city Königsberg, whose residents famously make their late-night attempts to traverse the bridges, subject to the requirement of crossing each bridge exactly once.

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? What is your plan? Will your team make it to the big board?

Interlude

Small trains running long

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.

Interlude

More generally, with a train capacity of n passengers, how far can the train go while still having someone disembark at every stop?