In set theory, 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 <. For each t ε T, the order type of {s ε T : s < t} is called the idxheight, or 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 length at most α. A root of a tree T is an element of height 0. Frequently trees are assumed to have only on root. 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. Set theory is the mathematical theory of sets, which represent collections of abstract objects. ... In mathematics, especially order theory, a partially ordered set (or poset for short) is a set equipped with a partial order relation. ... Ordinal numbers, or ordinals for short, are numbers used to denote the position in an ordered sequence: first, second, third, fourth, etc. ... A labeled tree with 6 vertices and 5 edges In graph theory, a tree is a graph in which any two vertices are connected by exactly one path. ...

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. A tree is a κ-tree iff it has height κ and every level has size less than κ. For each ordinal α, the α-th level of T is the set of all elements of T of height α. The width of a tree is the supremum of the cardinalities of its levels. Ordinal numbers, or ordinals for short, are numbers used to denote the position in an ordered sequence: first, second, third, fourth, etc. ... In the mathematical field of order theory an order isomorphism is a special kind of monotone function that constitutes a suitable notion of isomorphism for partially ordered sets. ...

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. König proved 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 κ-Souslin 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 κ-Souslin tree. In fact, for any infinite cardinal κ, every κ-Souslin tree is a κ-Aronszajn tree (the converse does not hold). Suslins problem in mathematics is a question about orders posed by M. Suslin in the early 1920s. ... Zermelo-Fraenkel set theory, commonly abbreviated ZFC, is the most common form of axiomatic set theory, and as such is the most common foundation of mathematics. ... An infinite cardinal number κ is called regular if cf(κ) = κ, where cf is the cofinality operation. ...

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 ω₁. In mathematics, a total order or linear order on a set X is any binary relation on X that is antisymmetric, transitive, and total. ... Let S be a partially ordered set. ...

See also

• Tree (descriptive set theory)

In descriptive set theory, a tree on a set is a set of finite sequences of elements of that is closed under subsequences. ...

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.