Editing Tree (set theory) (section)

==Definition==
[[File:Finite set-theoretic trees.png|thumb|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 {{math|''x''<sub>1</sub> < ''x''<sub>3</sub>}} and {{math|''x''<sub>2</sub> < ''x''<sub>3</sub>}}, but {{math|''x''<sub>1</sub>}} is not comparable to {{math|''x''<sub>2</sub>}} (dashed orange line).]]

A '''tree''' is a [[partially ordered set]] (poset) <math>(T,<)</math> such that for each <math>t\in T</math>, the set <math>\{s\in T: s<t\}</math> is [[well-ordered]] by the relation <math><</math>. In particular, each well-ordered set <math>(T,<)</math> is a tree. For each <math>t\in T</math>, the [[order type]] of <math>\{s\in T: s<t\}</math> is called the ''height'', ''rank'',<ref name=gs/> or ''level''<ref name=monk>{{cite book |last=Monk |first=J. Donald |title=Mathematical Logic |publisher=Springer-Verlag |location=New York |year=1976 |page=[https://archive.org/details/mathematicallogi00jdon/page/517 517] |isbn=0-387-90170-1 |url-access=registration |url=https://archive.org/details/mathematicallogi00jdon/page/517 }}</ref> of <math>t</math>. The ''height'' of <math>T</math> itself is the least [[Ordinal number|ordinal]] greater than the height of each element of <math>T</math>. A ''root'' of a tree <math>T</math> 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 <math>T</math> is a tree whose height is greater than the smallest infinite ordinal number <math>\omega</math>, then the Hasse diagram definition does not work. For example, the partially ordered set <math>\omega + 1 = \left\{0, 1, 2, \dots, \omega\right\}</math> does not have a Hasse Diagram, as there is no predecessor to <math>\omega</math>. Hence a height of at most <math>\omega</math> is required to define a graph-theoretic tree in this way.

A ''branch'' of a tree is a maximal [[total order#Chains|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 number|ordinal]] that is [[Order isomorphism|order isomorphic]] to the branch. For each ordinal <math>\alpha</math>, the ''<math>\alpha</math>th level'' of <math>T</math> is the set of all elements of <math>T</math> of height <math>\alpha</math>. A tree is a <math>\kappa</math>-tree, for an ordinal number <math>\kappa</math>, if and only if it has height <math>\kappa</math> and every level has [[cardinality]] less than the cardinality of <math>\kappa</math>. The ''width'' of a tree is the supremum of the cardinalities of its levels.

Any single-rooted tree of height <math>\leq \omega</math> 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 <math>\left\{a, b\right\}</math> 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 <math>\left\{0, 1, 2, \dots, \omega_0, \omega_0'\right\}</math> where <math>\omega_0, \omega_0'</math> are not comparable.

A ''subtree'' of a tree <math>(T,<)</math> is a tree <math>(T',<)</math> where <math>T' \subseteq T</math> and <math>T'</math> is [[downward closed]] under <math> < </math>, i.e., if <math>s, t \in T</math> and <math> s < t</math> then <math>t \in T' \implies s \in T'</math>. The height of each element of a subtree equals its height in the whole tree.<ref name=gs>{{cite journal
 | last1 = Gaifman | first1 = Haim | author1-link = Haim Gaifman
 | last2 = Specker | first2 = E. P. | author2-link = Ernst Specker
 | doi = 10.1090/S0002-9939-1964-0168484-2 | doi-access = free
 | journal = [[Proceedings of the American Mathematical Society]]
 | jstor = 2034337
 | mr = 168484
 | pages = 1–7
 | title = Isomorphism types of trees
 | volume = 15
 | year = 1964}}. Reprinted in ''Ernst Specker Selecta'' (Springer, 1990), pp. 202–208, {{doi|10.1007/978-3-0348-9259-9_18}}.</ref> This differs from the notion of subtrees in graph theory, which often have different roots than the whole tree.