Aronszajn tree
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 cardinality "κ" in which all levels have size less than "κ" and all branches have height less than "κ" (so Aronszajn trees are the same as formula_1-Aronszajn trees). They are named for Nachman Aronszajn, who constructed an Aronszajn tree in 1934; his construction was described by . 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 formula_2-Aronszajn trees do not exist. The existence of Aronszajn trees (formula_3-Aronszajn trees) was proven by Nachman Aronszajn, and implies that the analogue of Kőnig's lemma does not hold for uncountable trees. The existence of formula_4-Aronszajn trees is undecidable (assuming a certain large cardinal axiom): more precisely, the continuum hypothesis implies the existence of an formula_4-Aronszajn tree, and Mitchell and Silver showed that it is consistent (relative to the existence  of a weakly compact cardinal) that no formula_4-Aronszajn trees exist. Jensen proved that V = L implies that there is a "κ"-Aronszajn tree (in fact a "κ"-Suslin tree) for every infinite successor cardinal "κ". 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(formula_1) 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 . 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 . 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 "T" is the union of the sets "U" for all countable α. We construct the countable levels "U" by transfinite  induction on α as follows starting with the empty set as "U": The function "f"("x") = sup "x" is rational or −∞, and has the property that if "x" < "y" then "f"("x") < "f"("y"). Any branch in "T" is countable as "f" maps branches injectively to −∞ and the rationals. "T" is uncountable as it has a non-empty level "U" for each countable ordinal "α" which make up the first uncountable ordinal. This proves that "T" is a special Aronszajn tree. 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.