Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

The transfinite subway puzzle (see http://mathforum.org/kb/message.jspa?messageID=229112) is one of those clever puzzle only mathematicians can enjoy (other ones being the blue-eyed islanders puzzle (see http://terrytao.wordpress.com/2011/04/07/the-blue-eyed-islanders-puzzle-repost/ ), or the use of axiom of choice to guess almost always the content of all but a finite number of boxes, see (in French) http://www.madore.org/~david/weblog/2009-05.html#d.2009-05-16.1643). My question (about the tranfinite subway) is : is there any relationship between this strange property of $\omega_1$ (i.e. that the subway arrives always empty) and the existence of $\aleph_1$-Aronszajn trees ?

share|improve this question
add comment

1 Answer

up vote 6 down vote accepted

To my of thinking, the subway puzzle does not have to do with the fact that there is an $\aleph_1$-Aronszajn tree, but rather simply with the fact that $\omega_1$ has uncountable cofinality. The reason is that the subway will also be empty at $\aleph_2$, at $\aleph_3$ and indeed, at any ordinal having uncountable cofinality, but these ordinals might not have corresponding Aronszajn trees.

Specifically, for the case of $\omega_1$, the operative fact is that every function $f:\omega_1\to\omega_1$ has unboundedly many closure points, ordinals $\gamma\lt\omega_1$ such that $f[\gamma]\subset\gamma$. This can be proved simply by iterating the function countably many times and taking a supremum, the point being that since $\omega_1$ has uncountable cofinality, the supremum is still less than $\omega_1$.

For the subway puzzle, at any countable stage $\alpha$, there are at most countably many subway occupants, so let $f(\alpha)$ be the supremum of the countable stages at which those occupants who will eventually get off before $\omega_1$, do get off. This supremum is below $\omega_1$, and so $f:\omega_1\to\omega_1$. Anyone on the train at stage $\alpha$ who does get off, will get off before $f(\alpha)$. Applying the key fact, there are unboundedly many countable ordinals $\gamma$ that are closed under $f$, and the train must be empty at any such $\gamma$, since otherwise there would be an occupant on board who gets off right then, but by the definition of $f$ they should have gotten off earlier. So in fact, the subway empties out completely cofinally often before $\omega_1$, and is therefore empty at $\omega_1$, as every person who ever boarded the train eventually also got off before time $\omega_1$.

My point, now, is that the argument works just as well with any ordinal of uncountable cofinality. For example, the subway would be empty also at $\omega_2$, $\omega_3$, at $\omega_3+\omega_2^5$ and so on. But it is consistent with the axioms of set theory that there is no $\aleph_2$-Aronszajn tree, and similarly at other larger cardinals. Thus, I conclude, the relevant property is uncountable cofinality rather than the tree property.


Incidentally, let me remark that an analogue of the subway argument arises at the very center of my proof that Every group has a terminating transfinite automorphism tower (Proc. Amer. Math. Soc., vol. 126, iss. 11, pp. 3223-3226, 1998). The automorphism tower of a group $G_0$ is obtained by iteratively taking the automorphism group $G_{\alpha+1}=\text{Aut}(G_\alpha)$, and mapping homomorphically in by inner automorphisms. $$G_0\to G_1\to\cdots\to G_\omega\to G_{\omega+1}\to\cdots\to G_\alpha\to\cdots$$ One takes the direct limit of the system at limit stages and continues the tower transfinitely. The tower is said to terminate if a group is reached which is isomorphic to its automorphism group by the natural map; this will be a complete group, a centerless group having only inner automorphisms. Note that the center of each group is killed at each stage, since conjugating by an element in the center is the identity automorphism. Furthermore, Simon Thomas proved that every centerless group has a terminating tower. What I proved, essentially by the subway argument, is that every group leads eventually to a centerless group: let $f(\alpha)$ be the supremum of the stages by which the elements of $G_\alpha$ that eventually get mapped to the identity, do get mapped this way. If $\gamma$ is closed under $f$, then everybody born before $\gamma$ who will get killed, is killed before $\gamma$. Thus, $G_\gamma$ is centerless---the subway is empty at stage $\gamma$---and so by Thomas's theorem, the tower terminates after this.

share|improve this answer
    
Just a couple small comments. First, the background of the puzzle is a bit obscure from the link in the original question. Transfinite Subway is due to Scott Huddleston, 8/3/1991, possibly viewable from this URL: groups.google.com/forum/?fromgroups=#!search/… . The first solution: Robert Solovay (in that thread). Huddleston solution is that of the answer. The same reasoning holds when some higher cardinal of passengers embark at each stop, in the obvious way - empty at a higher cardinal. –  TLss Jan 7 '13 at 6:24
    
Thanks, TLss, for the historical information. Your link, however, doesn't quite work---it points merely at a search for 'transfinite', but it seems that you probably intended a more specific link. –  Joel David Hamkins Jan 7 '13 at 10:00
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.