In set theory, an Aronszajn tree is an uncountable tree with no uncountable branches and no uncountable levels. For example, every Suslin tree is an Aronszajn tree. More generally, for a cardinal κ, a κ-Aronszajn tree is a tree of height κ such that all levels have size less than κ and all branches have height less than κ (so Aronszajn trees are the same as
Contents
- Existence of Aronszajn trees
- Special Aronszajn trees
- Construction of a special Aronszajn tree
- References
A cardinal κ for which no κ-Aronszajn trees exist is said to have the tree property. (sometimes the condition that κ is regular and uncountable is included.)
Existence of κ-Aronszajn trees
König's lemma states that
The existence of Aronszajn trees (=
The existence of
Jensen proved that V=L implies that there is a κ-Aronszajn tree (in fact a κ-Suslin tree) for every infinite successor cardinal κ.
Cummings & Foreman (1998) showed (using a large cardinal axiom) that it is consistent that no
If κ is weakly compact then no κ-Aronszajn trees exist. Conversely if κ is inaccessible and no κ-Aronszajn trees exist then κ is weakly compact.
Special Aronszajn trees
An Aronszajn tree is called special if there is a function f from the tree to the rationals so that f(x)<f(y) whenever x<y. Martin's axiom MA(
Construction of a special Aronszajn tree
A special Aronszajn tree can be constructed as follows.
The elements of the tree are certain well-ordered sets of rational numbers with supremum that is rational or −∞. If x and y are two of these sets then we define x≤y (in the tree order) to mean that x is an initial segment of the ordered set y. For each countable ordinal α we write Uα for the elements of the tree of level α, so that the elements of Uα are certain sets of rationals with order type α. The special Aronszajn tree is the union of the sets Uα for all countable α.
We construct Uα by transfinite induction on α as follows.
The function f(x) = sup x is rational or −∞, and has the property that if x<y then f(x)<f(y), so this tree is special.
This construction can be used to construct κ-Aronszajn trees whenever κ is a successor of a regular cardinal and the generalized continuum hypothesis holds, by replacing the rational numbers by a more general η set.