Tree (set theory)

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 each t ∈ T, the order type of {s ∈ T : s < t} is called the height of t, denoted ht(t, T).

Frequently trees are assumed to have only one root.

Trees in set theory are often defined to grow downward making the root the greatest node.

[citation needed] 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

does not have a Hasse Diagram, as there is no predecessor to ω.

Hence a height of at most ω is required in this case.

The width of a tree is the supremum of the cardinalities of its levels.

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

[citation needed] There are some fairly simply stated yet hard problems in infinite tree theory.

Both of these problems are known to be independent of Zermelo–Fraenkel set theory.

By Kőnig's lemma, every ω-tree has an infinite branch.

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 ω1 has an antichain of cardinality ω1 or a branch of length ω1.

If (T,<) is a tree, then the reflexive closure ≤ of < is a prefix order on T. The converse does not hold: for example, the usual order ≤ on the set Z of integers is a total and hence a prefix order, but (Z,<) is not a set-theoretic tree since e.g. the set {n ∈Z: n < 0} has no least element.

A branch (highlighted green) of a set-theoretic tree. Here dots represent elements, arrows represent the order relation, and ellipses and dashed arrows represent (possibly infinite) un-pictured elements and relationships.
Small finite examples: The three partially ordered sets on the left are trees (in blue); one branch of one of the trees is highlighted (in green). The partially ordered set on the right (in red) is not a tree because x 1 < x 3 and x 2 < x 3 , but x 1 is not comparable to x 2 (dashed orange line).
Set-theoretic tree of height and width . Each node corresponds to a junction point of a red and a green line. Due to space restrictions, only branches with a prefix ( 0 , 0 , 0 ,...) or ( 1 , 1 , 1 ,...) are shown in full length.