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 κ in which all levels have size less than κ and all branches have height less than κ (so Aronszajn trees are the same as -Aronszajn trees). They are named for Nachman Aronszajn, who constructed an Aronszajn tree in 1934; his construction was described by Kurepa (1935).
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 -Aronszajn trees do not exist.
The existence of -Aronszajn trees is undecidable (assuming a certain large cardinal axiom): more precisely, the continuum hypothesis implies the existence of an -Aronszajn tree, and Mitchell and Silver showed that it is consistent (relative to the existence of a weakly compact cardinal) that no -Aronszajn trees exist.
Cummings & Foreman (1998) showed (using a large cardinal axiom) that it is consistent that no -Aronszajn trees exist for any finite n other than 1.
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() implies that all Aronszajn trees are special. The stronger proper forcing axiom implies the stronger statement that for any two Aronszajn trees there is a club set of levels such that the restrictions of the trees to this set of levels are isomorphic, which says that in some sense any two Aronszajn trees are essentially isomorphic (Abraham & Shelah 1985). On the other hand, it is consistent that non-special Aronszajn trees exist, and this is also consistent with the generalized continuum hypothesis plus Suslin's hypothesis (Schlindwein 1994).
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.
- If α + 1 is a successor then Uα+1 consists of all extensions of a sequence x in Uα by a rational greater than sup x.
- If α is a limit then let Tα be the tree of all points of level less than α. For each x in Tα and for each rational number q greater than sup x, choose a level α branch of Tα containing x with supremum q. Then Uα consists of these branches.
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.
- Abraham, Uri; Shelah, Saharon (1985), "Isomorphism types of Aronszajn trees", Israel Journal of Mathematics, 50: 75–113, doi:10.1007/BF02761119
- Cummings, James; Foreman, Matthew (1998), "The tree property", Adv. Math., 133 (1): 1–32, doi:10.1006/aima.1997.1680, MR 1492784
- Kunen, Kenneth (2011), Set theory, Studies in Logic, 34, London: College Publications, ISBN 978-1-84890-050-9, Zbl 1262.03001
- Kurepa, G. (1935), "Ensembles ordonnés et ramifiés", Publ. math. Univ. Belgrade, 4: 1–138, JFM 61.0980.01, Zbl 0014.39401
- Schlindwein, Chaz (1994), "Consistency of Suslin's Hypothesis, A Nonspecial Aronszajn Tree, and GCH", The Journal of Symbolic Logic, The Journal of Symbolic Logic, Vol. 59, No. 1, 59 (1): 1–29, doi:10.2307/2275246, JSTOR 2275246
- Schlindwein, Ch. (2001) , "Aronszajn tree", in Hazewinkel, Michiel, Encyclopedia of Mathematics, Springer Science+Business Media B.V. / Kluwer Academic Publishers, ISBN 978-1-55608-010-4
- Todorčević, S. (1984), "Trees and linearly ordered sets", Handbook of set-theoretic topology, Amsterdam,: North-Holland, pp. 235–293, MR 0776625