Infinity offers many results that are at first counter-intuitive. A classic example is Hilbert's Hotel, which has infinitely many rooms, each one labeled by a natural number printed on the door: Room 1, Room 2, Room 3, etc., all the way through the natural numbers. One night, a traveler arrives at the front desk only to be told be the clerk that the hotel is full. "But don't worry, sir," says the clerk, "I just took a mathematics course at my local college, and so I know how to find you a room. Just give me a minute to make some phone calls." And a short while later, the traveler has his room for the night. What the clerk did was ask every guest to move to the room with the room number the next integer. Thus, the occupant of Room 1 moved into Room 2, the occupant of Room 2 into Room 3, etc. Everyone moved room, no one was ejected from the hotel, and Room 1 became vacant for the newly arrived guest.
This example is well known, and I expect all regular readers of MAA Online will be familiar with it. But I expect many of you will not know what happens when you step up one level of infinity. No sooner have you started to get the hang of the countable infinity (cardinality aleph-0), and you encounter the first uncountable infinity (cardinality aleph-1) and you find there are more surprises in store.
One result that surprised me when I first came across it concerns trees. Not the kind the grow in the forest, but the mathematical kind, although there are obvious similarities, reflected in the terminology mathematicians use when studying mathematical trees.
A tree is a partially ordered set (T,<) such that for every member x of T, the set {y in T : y < x} of elements below x in the tree is well ordered. This means that the tree has a preferred direction of growth (often represented as upwards in diagrams), and branching occurs only in the upward direction. It is generally assumed that a tree has a unique minimum element, called the root. (If you encounter a tree without such a root, you can simply add one, without altering the structure of the remainder of the tree.)
Since each element of a tree lies at the top of a unique well ordered set of predecessors, it has a well defined height in the tree - the ordinal number of the set of predecessors. For each ordinal number k, we can denote by T_k the set of all elements of the tree of height k. T_k is called the k'th level of T. T_0 consists of the root of the tree, T_1 is the set of all immediate successors of the root, etc.
Thus, the lower part of a tree might look something like this:
(It could be different. There is no restriction on how many elements there are on each level, or how many successors each member has.)
A classical result of set theory, sometimes called König's Lemma, says that if T is an infinite tree, and if each level T_n, for n a natural number, is finite, then T has an infinite branch, i.e., an infinite linearly ordered subset.
It's easy to prove this result. You define a branch {x_n : n a natural number} by recursion. To start, you take x_0 to be the root of the tree. Since the tree is infinite, but T_1 is finite, there is at least one member of T_1 that has infinitely many elements above it. Let x_1 be one such element of T_1. Since x_1 has infinitely many elements above it and yet only finitely many successors on T_2, there is at least one successor of x_1 on T_2 that has infinitely many elements above it. Let x_2 be such an element of T_2. Now define x_3 in T_3 analogously so it has infinitely many elements of the tree above it, and so on. This simple process clearly defines an infinite branch {x_n : n a natural number}.
Having seen why König's Lemma holds, it's tempting to argue by analogy that if you have an uncountable tree T (i.e., a tree whose cardinality is at least aleph-1) and if every level T_k, for k a countable ordinal, is countable, then T has an uncountable branch, i.e., a linearly ordered subset that meets level T_k for every countable ordinal k.
But it turns out that this cannot be proved. It is possible to construct an uncountable tree, all of whose levels T_k, for k a countable ordinal, are countable, for which there is no uncountable branch. Such trees are called Aronszajn trees, after the Russian mathematician who first constructed one.
Here is how to construct an Aronszajn tree. The members of the tree are strictly increasing (finite and countably transfinite), bounded sequences of rational numbers. The tree ordering is sequence extension. It is immediate that such a tree could not have an uncountable branch, since its limit (more precisely, its set-theoretic union) would be an uncountable strictly increasing sequence of rationals, contrary to the fact that the rationals form a countable set.
You build the tree by recursion on the levels. T_0 consists of the empty sequence. After T_k has been constructed, you get T_(k+1) by taking each sequence s in T_k and adding in every possible extension of s to a strictly increasing (k+1)-sequence of rationals. That is, for each s in T_k and for each rational number q greater than or equal to the supremum of s, you put into T_(k+1) the result of appending q to s. Being the countable union of countably many sets, T_(k+1) will itself be countable, as required.
In the case of regular recursion on the natural numbers, that would be all there is to the definition, but with a recursion that goes all the way up through the countable ordinals, you also have to handle limit ordinals - ordinals that are not an immediate successor of any smaller ordinal.
To facilitate the definition of the limit levels of the tree, you construct the tree so as to satisfy the following property, which I'll call the Aronszajn property: for every pair of levels T_k and T_m, where k < m, and for every s in T_k and every rational number q that exceeds the supremum of s, there is a sequence t in T_m which extends s and whose supremum is less than q.
The definition of T_(k+1) from T_k that I just gave clearly preserves this property, since I threw in EVERY possible sequence extension of every member of T_k.
Suppose now that m is a limit ordinal and we have defined T_k for every k < m. Given any member s of some level T_k for k < m, and any rational number q greater than the supremum of s, we define, by integer recursion, a path (s_i : i a natural number) through the portion of the tree already constructed, such that its limit (as a rational sequence) has supremum q.
You first pick some strictly increasing sequence of rationals (q_i : i a natural number) such that q_0 exceeds the supremum of s and whose limit is q.
You also pick some strictly increasing sequence (m_i : i a natural number) of ordinals less than m that has limit m and such that s lies below level m_0 in the tree.
You can then use the Aronszajn property to construct the sequence (s_i : i a natural number) so that s_i is on level m_i and the supremum of s_i is less than q_i.
Construct one such path (s_i : i a natural number) for every such pair s, q, and let T_k consist of the limit (as a sequence of rationals) of every sequence so constructed. Notice that T_k so defined is countable.
It is clear that this definition preserves the Aronszajn property, and hence the construction may be continued.
And that's it.
NOTE: The above article first appeared in Devlin’s Angle in January 2006. Seeing Frenkel’s Numberplay article prompted me to revive it and give it another airing.
