580- Specker trees

In his proof that the axiom of infinity holds in Quine’s New Foundations, Specker associated to each set {X} a tree, now called the Specker tree of {X}. (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 {\sim} on subsets of {X} by saying that {A\sim B} iff {|A|=|B|}. The nodes of the tree are equivalence classes of subsets of {X} under {\sim}. Specifically, at the root we have the class of {X}, and the immediate successors of a class {[Y]} are the classes {[Z]} such that {|{\mathcal P}(Z)|=|Y|}.

Of course, under choice we can simply use cardinals {|Y|} as nodes, rather than the classes {[Y]}.

If {X} is a set, let {\aleph(X)}, the Hartogs function of {X}, be the set of all ordinals {\alpha} that inject into {X}, so {\aleph(X)} is the first ordinal that cannot inject. Sierpiński proved that {\aleph(X)\preceq{\mathcal P}^3(X)} and therefore {\aleph(X)<\aleph({\mathcal P}^3(X))}. This observation gives us immediately that the Specker tree of any set {X} 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.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: