Tree (set theory)

In set theory, a tree is a partially ordered set (T, <) such that for each t ∈ T, the set {s ∈ T : s < t} is well-ordered by the relation <. Frequently trees are assumed to have only one root (i.e. minimal element), as the typical questions investigated in this field are easily reduced to questions about single-rooted trees.

For other notions of tree in set theory, see tree (descriptive set theory) and tree (disambiguation).

Definition

A tree is a partially ordered set (poset) (T, <) such that for each t ∈ T, the set {s ∈ T : s < t} is well-ordered by the relation <. In particular, each well-ordered set (T, <) is a tree. For each t ∈ T, the order type of {s ∈ T : s < t} is called the height of t (denoted ht(t, T)). The height of T itself is the least ordinal greater than the height of each element of T. A root of a tree T is an element of height 0. Frequently trees are assumed to have only one root. Note that trees in set theory are often defined to grow downward making the root the greatest node.

Trees with a single root may be viewed as rooted trees in the sense of graph theory in one of two ways: either as a tree (graph theory) or as a trivially perfect graph. In the first case, the graph is the undirected Hasse Diagram of the partially ordered set, and in the second case, the graph is simply the underlying (undirected) graph of the partially ordered set. However, if T is a tree of height > ω, then the Hasse diagram definition does not work. For example, the partially ordered set ${\displaystyle \omega +1=\left\{0,1,2,\dots ,\omega \right\}}$ does not have a Hasse Diagram, as there is no predecessor to ω. Hence we require height at most omega in this case.

A branch of a tree is a maximal chain in the tree (that is, any two elements of the branch are comparable, and any element of the tree not in the branch is incomparable with at least one element of the branch). The length of a branch is the ordinal that is order isomorphic to the branch. For each ordinal α, the α-th level of T is the set of all elements of T of height α. A tree is a κ-tree, for an ordinal number κ, if and only if it has height κ and every level has size less than the cardinality of κ. The width of a tree is the supremum of the cardinalities of its levels.

Any single-rooted tree of height ${\displaystyle \leq \omega }$ forms a meet-semilattice, where meet (common ancestor) is given by maximal element of intersection of ancestors, which exists as the set of ancestors is non-empty and finite well-ordered, hence has a maximal element. Without a single root, the intersection of parents can be empty (two elements need not have common ancestors), for example ${\displaystyle \left\{a,b\right\}}$ where the elements are not comparable; while if there are an infinite number of ancestors there need not be a maximal element – for example, ${\displaystyle \left\{0,1,2,\dots ,\omega _{0},\omega _{0}'\right\}}$ where ${\displaystyle \omega _{0},\omega _{0}'}$ are not comparable.

A subtree of a tree ${\displaystyle (T,<)}$ is a tree ${\displaystyle (T',<)}$ where ${\displaystyle T'\subseteq T}$ and ${\displaystyle T'}$ is downward closed under ${\displaystyle <}$, i.e., if ${\displaystyle s,t\in T}$ and ${\displaystyle s<t}$ then ${\displaystyle t\in T'\implies s\in T'}$.

Set-theoretic properties

There are some fairly simply stated yet hard problems in infinite tree theory. Examples of this are the Kurepa conjecture and the Suslin conjecture. Both of these problems are known to be independent of Zermelo–Fraenkel set theory. Kőnig's lemma states that every ω-tree has an infinite branch. On the other hand, it is a theorem of ZFC that there are uncountable trees with no uncountable branches and no uncountable levels; such trees are known as Aronszajn trees. A κ-Suslin tree is a tree of height κ which has no chains or antichains of size κ. In particular, if κ is singular (i.e. not regular) then there exists a κ-Aronszajn tree and a κ-Suslin tree. In fact, for any infinite cardinal κ, every κ-Suslin tree is a κ-Aronszajn tree (the converse does not hold).

The Suslin conjecture was originally stated as a question about certain total orderings but it is equivalent to the statement: Every tree of height ω₁ has an antichain of cardinality ω₁ or a branch of length ω₁.

See also

• Cantor tree
• Kurepa tree
• Laver tree
• Tree (descriptive set theory)
• Continuous graph
• Prefix order

References

• Jech, Thomas (2002). Set Theory. Springer-Verlag. ISBN 3-540-44085-2.
• Kunen, Kenneth (1980). Set Theory: An Introduction to Independence Proofs. North-Holland. ISBN 0-444-85401-0. Chapter 2, Section 5.
• Monk, J. Donald (1976). Mathematical Logic. New York: Springer-Verlag. p. 517. ISBN 0-387-90170-1.
• Hajnal, András; Hamburger, Peter (1999). Set Theory. Cambridge: Cambridge University Press. ISBN 9780521596671.
• Kechris, Alexander S. (1995). Classical Descriptive Set Theory. Graduate Texts in Mathematics 156. Springer. ISBN 0-387-94374-9 ISBN 3-540-94374-9.

External links

• Sets, Models and Proofs by Ieke Moerdijk and Jaap van Oosten, see Definition 3.1 and Exercise 56 on pp. 68–69.
• tree (set theoretic) by Henry on PlanetMath
• branch by Henry on PlanetMath
• example of tree (set theoretic) by uzeromay on PlanetMath