Suslin trees

It gets worse. A countably infinite tree can fail to have an infinite branch if you allow a node to have infinitely many successor nodes: the tree becomes infinitely wide rather than infinitely tall. This suggests that if we impose a growth condition that prevents an uncountable tree from becoming uncountably wide, maybe we can force it to have an uncountable branch.

Requiring that each node have at most countable successor nodes is not sufficient. Aronszajn trees only split a countable number of times at each node, but still has no uncountable branch. A stronger condition is that the tree has no uncountable antichain. An antichain is a subset of the tree such that no node in the set is the descendent of any other node. The size of the largest antichain gives a rough measure of the width of the tree. If we force the tree to have a countable width by this measure, then possibly this will force the tree to have an uncountable branch. This is a much stronger property than requiring each node to have only a countable number of successors. For example, an countable binary tree has a countable antichain, but it has lots of countable branches.

Does it work? Intuition from the countably infinite frequently fails when we consider uncountable sets, as the case of Aronszajn trees shows. At the same time, we have imposed a very strong condition, so perhaps that would be enough to settle it. So the result is plausibly true, and plausibly false. Which is it?

Neither. The existence of an uncountable tree with neither an uncountable antichain or an uncountable branch, known as a Suslin tree, is undecidable by the axioms of set theory. The question is equivalent to the Souslin problem, which has been shown to be independent of ZFC. (The axiom of constructability implies the existence of a Suslin tree. Assuming Martin’s Axiom and that the continuum hypothesis is false implies the non-existence of a Suslin tree. Both setups are known to be consistent with ZFC, which means that the existence of a Suslin tree must be independent.)

Uncountable trees are bad news.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>