## Friday, August 24, 2007

### Infinite trees

If you followed Andy Drucker's series of posts on infinite trees and were craving more, be prepared for more foliage:

Via Ars Mathematica, a pointer to Keith Devlin's column on a bizarre counter-version of Konig's tree lemma: namely, if you have an uncountably large tree with countably large levels, then it is not necessarily true that an uncountable path must exist.

#### 1 comment:

1. Thanks, Suresh!

This construction took me a while to understand, so let me share some points that helped me:

-the 'countably transfinite increasing sequences' of rationals are not necessarily sequences in the ordinary sense of the word, but may include things like

{1/2, 3/4, 7/8, 15/16, ... , 2}.

-in fact, all sequences on level T_k have order type k. So, if the sequence above were in the tree, it would be on the level of the successor of the first infinite order type.

-the sequences are: rational, to prevent uncountable branches; individually well-ordered, so that they form a tree; chosen in a way that is selective enough to preserve countability of individual levels but generous enough to create sequences of every countable order type.

-how big is the resulting tree? It's the size of the smallest uncountable cardinal, which is the continuum assuming CH.
On the other hand, suppose we can build a continuum-sized tree (with or without uncountable branches) whose levels are each countable. Then we can express the continuum as the union of an increasing family of countable sets, which can be shown to imply the CH.