Tree (set theory)

From Free net encyclopedia

In set theory, a tree is a partially ordered set (poset) in which there is a single unique minimal element (called the root) and in which the set of elements less than a given element is well ordered. Trees of this sort need not be trees in the graph-theoretical sense, because there is not necessarily an associated edge relation giving a unique path between any two elements of the tree.

A branch of a tree is a maximal totally ordered 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. The height of a tree is the least ordinal α such that any branch has length at most α. If we have an element x of our tree and the well ordered section of the tree smaller than it is order isomorphic to α then we say x has height α. The width of a tree is the supremum of the cardinalities of the sets {x | x has height α}.

There are some fairly simply stated yet hard problems in infinite tree theory. Examples of this are the Kurepa conjecture and the Souslin conjecture. Both of these problems are known to be independent of Zermelo-Fraenkel set theory. 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.

Note: the Souslin 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 ω₁.

[edit]