I’m writing this month’s column from the Arctic Circle, Rovaniemi in Finland to be precise, home of the University of Lapland, where I am visiting to give a lecture, and home too for the real Santa Claus, or so they say around these parts. Surrounded by trees as far as the eye can see - which is not very far at this time of the year when the sun never rises above the horizon - my thoughts turned to trees even taller than those in the Finnish forests. Infinite trees that can be found only in the conceptual forest where mathematicians tread.
This brief foray into the fascinating world of the infinite extends my discussion last month of the Recursion Principle, and shows not only that infinity has a habit of surprising us, but even seemingly “obvious” constructions and proofs involving infinity can require powerful axioms, in the case of this month’s column not only the Recursion Principle again, but a principle far better known to non-professional mathematics aficionados called the Axiom of Choice.
So fasten your seat belt and prepare for a wild ride into the world of infinite trees.
To the mathematician, a tree is a well-founded, partially ordered set such that the set of all predecessors of any element is totally ordered, having a unique minimal element (called the root of the tree). Well-founded means that every nonempty subset has a minimal element, so there can be no infinite chains going downwards.
At first encounter that formal definition looks pretty complicated, but the notion is a pretty simple one that a diagram quickly makes clearer. A tree typically looks like this.
In terms of its basic structure, this is not unlike the trees that surround me here in Lapland.
To keep the diagram simple, I have drawn only a few nodes (the points). The partial order is represented by the lines that connect nodes. Each node can have any number of immediate successors in the tree (i.e., nodes immediately above it in the partial ordering), possibly an infinite number. Some nodes may have no immediate successors (and hence no successors at all).
A totally ordered path through the tree that follows the connecting lines is called a branch. Because nodes can have more than one immediate successor, a branch going up through the tree can at some node split into two or more separate branches. But going in the opposite direction, downwards, from a node there is exactly one branch, leading all the way down to the root of the tree. Thus, when you climb a tree, you have opportunities to “branch out”, like Robert Frost in his famous walk through the wood, but there is only one way to get back down to the bottom.)
Mathematical trees arise in studies of family descendancy in history or genetics, such as the tree that represents all women and their female offspring, though in those studies the trees are conventionally drawn growing downwards, with their roots at the top.
Since the unique branch that leads up to a given node is a well-ordered set (i.e., totally ordered and well-founded), each node can be assigned a unique “height” in the tree. The root has height 0, all immediate successors of the root have height 1, all their immediate successors height 2, etc. All the nodes having a specific height N in the tree are said to constitute the N’th “level” of the tree.
Trees that arise in history or genetics are finite, and hence there will be one or more nodes that have maximum height in the tree and constitute a “top level”, but mathematicians consider infinite trees. When they started to do that, they encountered a number of surprises, as is often the case with the infinite.
One initial curiosity is that whereas infinite trees can have infinite paths going upwards, heading in different directions, all paths downwards are finite and end at the root. (A path, whether it goes upward or downward, has to be specified in terms of step-by-step instructions: start here, then go there, then go there, etc., possibly into the transfinite. More specifically, you need to specify a function from an ordinal number into the tree.)
But a far bigger surprise came from trying to generalize a fairly simple result about infinite trees called Koenig’s Lemma: an infinite tree, all of whose levels are finite, must have an infinite branch (i.e., a path that goes all the way to the top of the tree - though even there you have to be careful, since an infinite tree does not necessarily have a top level).
Proving Koenig’s Lemma is fairly straightforward. You apply the Recursion Principle, which I discussed in last month’s column. Using that principle, you define an infinite branch by recursion. Call the branch you will construct B. To determine B, you specify for each natural number N the node in B on level N, and you do that in such a way that B(N) always has infinitely many nodes above it. B(0) is the root of the tree. With B(N) defined, for B(N+1) you take any immediate successor of B(N) that itself has infinitely many successors.
A simple induction proof shows that for every N, with B(N) suitably defined there always will be at least one node above it on level N+1 that has infinitely many nodes above it, so the above recursive definition works. Here is that proof.
Since the tree is infinite, there are infinitely many nodes above the root. Level 1 is finite, so at least one node on level 1 must have infinitely many nodes above it. (Because a finite union of finite sets is finite.) Likewise, if the node B(N) has infinitely many nodes above it, then because level N+1 is finite, at least one node above B(N) on that level must also have infinitely many nodes above it, and can be taken for B(N+1). So the recursive definition is sound.
But note that this process of defining an infinite branch assumes that it is possible to make infinitely many choices. (At each stage N we choose for B(N+1) one node above B(N) on level N+1 that has infinitely many nodes above it.) Unless the tree has some additional structure that provides a uniform means of making this selection, this requires a basic assumption about infinite sets called the Axiom of Choice. Though the Axiom of Choice in its full generality has been the subject of much discussion in the history of mathematics regarding its assumption as an axiom for mathematics, the simple version used for proving Koenig’s Lemma, called the Axiom of Dependent Choices, has generally been spared most of the attention.
Most people find Koenig’s Lemma intuitively obvious and accept the proof I just sketched. The surprise comes when you try to generalize it. The most obvious generalization is to uncountable trees all of whose levels are countable. (An infinite set is called uncountable is it cannot be put into a one-to-one correspondence with the natural numbers. In the 19th century, Georg Cantor famously proved that the real numbers constitute an uncountable set.)
An uncountable tree all of whose levels are countable has to have an uncountable number of levels, so the natural numbers are not sufficient to number them; you need the transfinite ordinal numbers, which extend counting beyond the natural numbers. But apart from that tweak, at first encounter most people feel sure they can generalize the proof of Koenig’s Lemma to show that an uncountable tree all of whose levels are countable must have an uncountable branch. (Again, this will require the Axiom of Choice, this time to make an uncountably-infinite number of selections.)
That was definitely my reaction when I came across this question as a first-year graduate student in set theory. I was therefore surprised when I sat down and tried to sketch the proof and ran into an unexpected obstacle at limit ordinals. Those are transfinite ordinals that do not have an immediate predecessor, a phenomenon that does not arise for the finite ordinals (aka the natural numbers together with 0).
My difficulty turned out to be more than my inability to make the proof work. The generalization is false. In 1934, a Polish-American mathematician called Nachman Aronszajn constructed a specific uncountable tree that has only countable levels yet has no uncountable branch.
For anyone who feels comfortable with transfinite recursion (i.e., recursion that allows you to define functions whose domain extends into the transfinite ordinals), it is easy to work out Aronszajn’s construction if I give you a couple of clues. A cryptic clue, that will help get you started but won’t spoil your enjoyment when you get the construction yourself, is that it is important to think rationally. With that, you should give it a try.
STOP READING NOW IF YOU WANT TO TRY IT ENTIRELY ON YOUR OWN.
Here are some more extensive clues to Aronszajn’s construction. The tree will have an N’th level for every countable ordinal N. The nodes on level N will be strictly increasing, bounded N-sequences of positive rational numbers. You define the tree by transfinite recursion (using the Axiom of Choice as well as the Principle of Transfinite Recursion). To ensure that the recursion works, you give every node countable-infinitely many immediate successors, and do it so as to preserve the condition that for every level N, for every N-sequence S of rationals on level N, for every countable ordinal M above N, and for every positive rational Q greater than the supremum of S, there is an M-sequence on level M that extends S, whose supremum is less than Q. From here on it’s all your’s. Enjoy!