Editing Tree (set theory) (section)

==Examples of infinite trees==
[[File:An infinite tree with a non-trivial well-ordering-color.gif|300px|thumb|Set-theoretic tree of height <math>\omega \cdot 2</math> and width <math>2^{\omega \cdot 2}</math>. Each node corresponds to a junction point of a red and a green line. Due to space restrictions, only branches with a [[prefix (computer science)|prefix]] ({{color|#ff0000|0}},{{color|#ff0000|0}},{{color|#ff0000|0}},...) or ({{color|#008000|1}},{{color|#008000|1}},{{color|#008000|1}},...) are shown in full length. ]]

* Let <math>\kappa</math> be an ordinal number, and let <math>X</math> be a set. Let <math>T</math> be set of all functions <math>f:\alpha \mapsto X</math> where <math>\alpha < \kappa</math>. Define <math>f < g</math> if the [[domain of a function|domain]] of <math>f</math> is a proper subset of the domain of <math>g</math> and the two functions agree on the domain of <math>f</math>. Then <math>(T,<)</math> is a set-theoretic tree. Its root is the unique function on the empty set, and its height is <math>\kappa</math>. <!---its width is <math>\chi^\kappa</math>, provided <math>\chi</math> is isomorphic to a well-ordering on <math>X</math>---> The union of all functions along a branch yields a function from <math>\kappa</math> to <math>X</math>, that is, a [[Sequence#Set_theory|generalized sequence]] of members of <math>X</math>. If <math>\kappa</math> is a [[limit ordinal]], none of the branches has a [[maximal element]] ("[[leaf node|leaf]]"). The picture shows an example for <math>\kappa = \omega \cdot 2</math> and <math>X = \{0,1\}</math>.

* Each [[tree (data structure)|tree data structure]] in computer science is a set-theoretic tree: for two nodes <math>m,n</math>, define <math>m < n</math> if <math>n</math> is a proper descendant of <math>m</math>. The notions of ''root'', node ''height'', and branch ''length'' coincide, while the notions of tree ''height'' differ by one.

* Infinite trees considered in automata theory (see e.g. ''[[tree (automata theory)]]'') are also set-theoretic trees, with a tree height of up to <math>\omega</math>.

* A [[tree (graph theory)|graph-theoretic tree]] can be turned into a set-theoretic one by <!---arbitrarily---> choosing a root node <math>r</math> and defining <math>m < n</math> if <math>m \neq n</math> and <math>m</math> lies on the (unique) undirected path from <math>r</math> to <math>n</math>.

* Each [[Cantor tree]], each [[Kurepa tree]], and each [[Laver tree]] is a set-theoretic tree.
<!---* Each [[tree (descriptive set theory)|descriptive-set-theoretic tree]] is a set-theoretic tree of height at most <math>\omega</math>: its root is the empty sequence, for two sequences <math>s,t</math> define <math>s < t</math> is <math>s</math> is a proper prefix of <math>t</math>.--->