A
tree is a
partially ordered set (poset) (T, such that for each t\in T, the set \{s\in T: s is
well-ordered by the relation . In particular, each well-ordered set (T, is a tree. For each t\in T, the
order type of \{s\in T: s is called the
height,
rank, of 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. 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 whose height is greater than the smallest infinite ordinal number \omega, then the Hasse diagram definition does not work. For example, the partially ordered set \omega + 1 = \left\{0, 1, 2, \dots, \omega\right\} does not have a Hasse Diagram, as there is no predecessor to \omega. Hence a height of at most \omega is required to define a graph-theoretic tree in this way. 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 \alpha, the
\alphath level of T is the set of all elements of T of height \alpha. A tree is a \kappa-tree, for an ordinal number \kappa,
if and only if it has height \kappa and every level has
cardinality less than the cardinality of \kappa. The
width of a tree is the supremum of the cardinalities of its levels. Any single-rooted tree of height \leq \omega forms a meet-semilattice, where the meet (common predecessor) is given by the maximal element of the intersection of predecessors; this maximal element exists as the set of predecessors is non-empty and finite. Without a single root, the intersection of predecessors can be empty (two elements need not have common ancestors), for example \left\{a, b\right\} where the elements are not comparable; while if there are infinitely many predecessors there need not be a maximal element. An example is the tree \left\{0, 1, 2, \dots, \omega_0, \omega_0'\right\} where \omega_0, \omega_0' are not comparable. A
subtree of a tree (T, is a tree (T', where T' \subseteq T and T' is
downward closed under , i.e., if s, t \in T and s then t \in T' \implies s \in T'. The height of each element of a subtree equals its height in the whole tree. This differs from the notion of subtrees in graph theory, which often have different roots than the whole tree. ==Set-theoretic properties==