Infinite tree (graph theory)
|
|
In mathematics, an infinite tree is a partially ordered set (poset) in which there is a single unique minimal element and in which the set of elements less than a given element is well ordered.
A branch of a tree is any totally ordered chain in the tree. The length of a branch is the ordinal that it order isomorphic to the branch. The height of a tree is the least ordinal A such that any branch has length at most A. If we have an element x of our tree and the well ordered section of the tree smaller than it is order isomorphic to A then we say x has height A. The width of a tree is the supremum of the cardinalities of the sets {x | x has height A}.
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.
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 ω1 has an antichain of cardinality ω1 or a branch of length ω1.