In set theory, an Aronszajn tree is a tree of uncountable height 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).
Kőnig's lemma states that -Aronszajn trees do not exist.
The existence of Aronszajn trees (-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 -Aronszajn trees is undecidable in ZFC: 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.
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 -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, a proposition sometimes abbreviated by EATS. 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 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 U0:
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. Uα + 1 is countable as it consists of countably many extensions of each of the countably many elements in Uα.
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. Uα is countable as it consists of countably many branches for each of the countably many elements in Tα.
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.
Schlindwein, Chaz (1989), "Special non-special -trees", Set Theory and its Applications, 1401: 160–166, doi:10.1007/BFb0097338
Todorčević, S. (1984), "Trees and linearly ordered sets", Handbook of set-theoretic topology, Amsterdam: North-Holland, pp. 235–293, MR 0776625
External links
PlanetMath
February 14, 2023
aronszajn, tree, theory, tree, uncountable, height, with, uncountable, branches, uncountable, levels, example, every, suslin, tree, more, generally, cardinal, tree, height, which, levels, have, size, less, than, branches, have, height, less, than, same, displa. In set theory an Aronszajn tree is a tree of uncountable height with no uncountable branches and no uncountable levels For example every Suslin tree is an Aronszajn tree More generally for a cardinal k a k Aronszajn tree is a tree of height k in which all levels have size less than k and all branches have height less than k so Aronszajn trees are the same as ℵ 1 displaystyle aleph 1 Aronszajn trees They are named for Nachman Aronszajn who constructed an Aronszajn tree in 1934 his construction was described by Kurepa 1935 A cardinal k for which no k Aronszajn trees exist is said to have the tree property sometimes the condition that k is regular and uncountable is included Contents 1 Existence of k Aronszajn trees 2 Special Aronszajn trees 3 Construction of a special Aronszajn tree 4 See also 5 References 6 External linksExistence of k Aronszajn trees EditKonig s lemma states that ℵ 0 displaystyle aleph 0 Aronszajn trees do not exist The existence of Aronszajn trees ℵ 1 displaystyle aleph 1 Aronszajn trees was proven by Nachman Aronszajn and implies that the analogue of Konig s lemma does not hold for uncountable trees The existence of ℵ 2 displaystyle aleph 2 Aronszajn trees is undecidable in ZFC more precisely the continuum hypothesis implies the existence of an ℵ 2 displaystyle aleph 2 Aronszajn tree and Mitchell and Silver showed that it is consistent relative to the existence of a weakly compact cardinal that no ℵ 2 displaystyle aleph 2 Aronszajn trees exist Jensen proved that V L implies that there is a k Aronszajn tree in fact a k Suslin tree for every infinite successor cardinal k Cummings amp Foreman 1998 showed using a large cardinal axiom that it is consistent that no ℵ n displaystyle aleph n Aronszajn trees exist for any finite n other than 1 If k is weakly compact then no k Aronszajn trees exist Conversely if k is inaccessible and no k Aronszajn trees exist then k is weakly compact Special Aronszajn trees EditAn Aronszajn tree is called special if there is a function f from the tree to the rationals so that f x lt f y whenever x lt y Martin s axiom MA ℵ 1 displaystyle aleph 1 implies that all Aronszajn trees are special a proposition sometimes abbreviated by EATS 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 amp 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 EditA 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 a we write Ua for the elements of the tree of level a so that the elements of Ua are certain sets of rationals with order type a The special Aronszajn tree T is the union of the sets Ua for all countable a We construct the countable levels Ua by transfinite induction on a as follows starting with the empty set as U0 If a 1 is a successor then Ua 1 consists of all extensions of a sequence x in Ua by a rational greater than sup x Ua 1 is countable as it consists of countably many extensions of each of the countably many elements in Ua If a is a limit then let Ta be the tree of all points of level less than a For each x in Ta and for each rational number q greater than sup x choose a level a branch of Ta containing x with supremum q Then Ua consists of these branches Ua is countable as it consists of countably many branches for each of the countably many elements in Ta The function f x sup x is rational or and has the property that if x lt y then f x lt 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 Ua for each countable ordinal a which make up the first uncountable ordinal This proves that T is a special Aronszajn tree This construction can be used to construct k Aronszajn trees whenever k is a successor of a regular cardinal and the generalized continuum hypothesis holds by replacing the rational numbers by a more general h set See also EditKurepa tree Aronszajn lineReferences EditAbraham 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 Advances in Mathematics 133 1 1 32 doi 10 1006 aima 1997 1680 MR 1492784 Kunen Kenneth 2011 Set theory Studies in Logic vol 34 London College Publications ISBN 978 1 84890 050 9 Zbl 1262 03001 Kurepa G 1935 Ensembles ordonnes et ramifies 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 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 1994 Aronszajn tree Encyclopedia of Mathematics EMS Press Schlindwein Chaz 1989 Special non special ℵ 1 displaystyle aleph 1 trees Set Theory and its Applications 1401 160 166 doi 10 1007 BFb0097338 Todorcevic S 1984 Trees and linearly ordered sets Handbook of set theoretic topology Amsterdam North Holland pp 235 293 MR 0776625External links EditPlanetMath Retrieved from https en wikipedia org w index php title Aronszajn tree amp oldid 1106564428, wikipedia, wiki, book, books, library,
