580- Specker trees

In his proof that the axiom of infinity holds in Quine’s New Foundations, Specker associated to each set a tree, now called the Specker tree of . (The name is due to Randall Holmes.)

In order to make sense of the definition without needing to appeal to the axiom of choice, let us define an equivalence relation on subsets of by saying that iff . The nodes of the tree are equivalence classes of subsets of under . Specifically, at the root we have the class of , and the immediate successors of a class are the classes such that .

Of course, under choice we can simply use cardinals as nodes, rather than the classes .

If is a set, let , the Hartogs function of , be the set of all ordinals that inject into , so is the first ordinal that cannot inject. Sierpiński proved that and therefore . This observation gives us immediately that the Specker tree of any set is well-founded.

Under choice, it follows that all trees have finite rank. This is because any branch through the tree is finite (its nodes being a strictly decreasing sequence of cardinals). Moreover, the smallest cardinal in a branch is larger than the smallest cardinal in any larger branch. But an infinite-rank tree must have arbitrarily large branches, so there is no smallest cardinal in the tree, which is absurd.

Remarkably, it is still open whether in the absence of choice it is consistent that there is a Specker tree of infinite rank.

Typeset using LaTeX2WP. Here is a printable version of this post.

Advertisement