Aronszajn tree

From Encyclopedia of Mathematics
Jump to: navigation, search

An Aronszajn tree (specifically, an $\omega_1$-Aronszajn tree) is an uncountable tree with no uncountable levels and no uncountable branches. The study of such trees is of central concern in infinitary combinatorics and also has applications in general topology (cf. also Combinatorial analysis; Topology, general). The existence of Aronszajn trees is a theorem of ZFC set theory; however, many questions concerning their properties are known to be undecidable in ZFC. For example, an Aronszajn tree with no uncountable anti-chain is called a Suslin tree; the existence of a Suslin tree is equivalent to failure of the Suslin hypothesis and is thus undecidable. The formulation of Suslin's hypothesis in terms of trees facilitated its study using set-theoretic methods, particularly forcing (cf. Forcing method). Another example of an undecidable question is whether every Aronszajn tree, when viewed as a topological space, is normal (cf. Normal space).

A special Aronszajn tree is one which admits an order-preserving mapping into $\mathbf{Q}$. This is sometimes also referred to as a regular Aronszajn tree; in that case the adjective "special" is reserved for the case in which the range of the order-preserving mapping is $\mathbf{R}$. Assuming the principle $\diamondsuit$, these two notions are not equivalent. The existence of a special Aronszajn tree is a theorem of ZFC. Under Martin's axiom plus the negation of the continuum hypothesis, every Aronszajn tree is special, and consequently Suslin's hypothesis is true. Under the proper forcing axiom, one has the stronger property that any two Aronszajn trees are essentially isomorphic in the sense that there is a closed unbounded set of levels $\mathcal{C}$ such that the restrictions of the trees to $\mathcal{C}$ are isomorphic.

Weaker notions of "being special" have been studied, for example by restricting the domain of the order-preserving mapping to a subset of the tree, leading to yet more undecidability results via advanced forcing methods. Also notable is the fact that, consistently, Suslin's hypothesis does not imply that every Aronszajn tree is special.

By generalizing to larger cardinal numbers, one can obtain more undecidable statements, and the methods of inner models come into play. In contrast with the case of $\omega_1$-Aronszajn trees, these results typically entail large-cardinal assumptions, and the exact consistency strength has been obtained in many cases. A $\kappa$-Aronszajn tree is a tree of height $\kappa$ all of whose levels have cardinality less than $\kappa$ and with no branch of cardinality equal to $\kappa$. The non-existence of $\omega_2$-Aronszajn trees is equi-consistent with the existence of a weakly compact cardinal, and the non-existence of special $\omega_2$-Aronszajn trees (with the notion of "special" appropriate for $\omega_2$) is equi-consistent with the existence of a Mahlo cardinal. Under the generalized continuum hypothesis, such trees exist. For $\kappa$ inaccessible, non-existence of $\kappa$-Aronszajn trees is equivalent with weak compactness of $\kappa$.

Aronszajn trees are examples of a larger class of trees called $\omega_1$-trees. An $\omega_1$-tree is an uncountable tree with no uncountable levels and no nodes of uncountable rank. The existence of an $\omega_1$-tree with uncountably many branches is a theorem of ZF (without the axiom of choice). A Kurepa tree is an $\omega_1$-tree with at least $\aleph_2$-many uncountable branches; the Kurepa hypothesis asserts that a Kurepa tree exists. This is yet another undecidable assertion; the failure of Kurepa's hypothesis is equi-consistent with the existence of an inaccessible cardinal.

A comprehensive reference is [a7]. For various notions of "being special" , see [a1], [a2] and [a6]. Aronszajn trees are treated in the standard texts [a3] and [a4]. For $\omega_2$-Aronszajn trees, see [a5] and [a6].


[a1] J. Baumgartner, "Iterated forcing" A.R.D. Mathias (ed.) , Surveys in Set Theory , Cambridge Univ. Press (1979)
[a2] J. Baumgartner, J. Malitz, W. Reinhardt, "Embedding trees in the rationals" Proc. Nat. Acad. Sci. USA , 67 (1970) pp. 1748–1753
[a3] T. Jech, "Set theory" , Acad. Press (1978)
[a4] K. Kunen, "Set theory: an introduction to independence proofs" , North-Holland (1980)
[a5] W. Mitchell, "Aronszajn trees and the independence of the transfer property" Ann. Math. Logic , 5 (1972) pp. 21–46
[a6] S. Shelah, "Proper forcing" , Springer (1982)
[a7] S. Todorcevic, "Trees and linearly ordered sets" K. Kunen (ed.) J.E. Vaughan (ed.) , Handbook of Set Theoretic Topology , North-Holland (1984)
How to Cite This Entry:
Aronszajn tree. Encyclopedia of Mathematics. URL:
This article was adapted from an original article by Ch. Schlindwein (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article