Editing Tree (set theory)

{{Short description|Concept in set theory, a topic in mathematics}}
{{for|other notions of tree in set theory|Tree (descriptive set theory)|Tree (disambiguation)}}
{{no footnotes|date=January 2021}}
[[File:Infinite set-theoretic tree.png|thumb|A branch (highlighted green) of a set-theoretic tree. Here dots represent elements, arrows represent the order relation, and [[ellipsis|ellipses]] and dashed arrows represent (possibly infinite) un-pictured elements and relationships.]]

In [[set theory]], a '''tree''' is a [[partially ordered set]] <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>. Frequently trees are assumed to have only one root (i.e. [[minimal element]]), as the typical questions investigated in this field are easily reduced to questions about single-rooted trees.

==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.

==Set-theoretic properties==
There are some fairly simply stated yet hard problems in infinite tree theory. Examples of this are the [[Kurepa conjecture]] and the [[Suslin conjecture]]. Both of these problems are known to be independent of [[Zermelo–Fraenkel set theory]]. By [[Kőnig's lemma]], every <math>\omega</math>-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 tree]]s. Given a [[cardinal number]] <math>\kappa</math>, a ''<math>\kappa</math>-[[Suslin tree]]'' is a tree of height <math>\kappa</math> which has no chains or antichains of size <math>\kappa</math>. In particular, if <math>\kappa</math> is a [[singular cardinal]] then there exists a <math>\kappa</math>-Aronszajn tree and a <math>\kappa</math>-Suslin tree. In fact, for any infinite cardinal <math>\kappa</math>, every <math>\kappa</math>-Suslin tree is a <math>\kappa</math>-Aronszajn tree (the converse does not hold). One of the equivalent ways to define a [[weakly compact cardinal]] is that it is an [[inaccessible cardinal]] <math>\kappa</math> that has the [[tree property]], meaning that there is no <math>\kappa</math>-Aronszajn tree.<ref name=monk/>

The Suslin conjecture was originally stated as a question about certain [[totally ordered set|total orderings]] but it is equivalent to the statement: Every tree of whose height is the [[first uncountable ordinal]] <math>\omega_1</math> has an [[antichain]] of cardinality <math>\omega_1</math> or a branch of length <math>\omega_1</math>.

If <math>(T,<)</math> is a tree, then the [[reflexive closure]] <math>\le</math> of <math><</math> is a [[prefix order]] on <math>T</math>.
The converse does not hold: for example, the usual order <math>\le</math> on the set <math>\mathbb{Z}</math> of [[integer]]s is a [[total order|total]] and hence a prefix order, but <math>(\mathbb{Z},<)</math> is not a set-theoretic tree since e.g. the set <math>\{n\in\mathbb{Z}:n <0\}</math> has no least element.

==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>.--->

== See also ==
*[[Tree (descriptive set theory)]]
*[[Continuous graph]]

==Notes==
{{reflist}}

==Further reading==
{{refbegin}}
* {{cite book |last=Jech |first=Thomas |title=Set Theory |publisher=Springer-Verlag |year=2002 |isbn=3-540-44085-2}}
* {{cite book |last=Kunen |first=Kenneth |authorlink=Kenneth Kunen |title=[[Set Theory: An Introduction to Independence Proofs]] |publisher=North-Holland |year=1980 |isbn=0-444-85401-0}} Chapter 2, Section 5.
* {{cite book |last1=Hajnal |first1=András |authorlink1=András Hajnal |last2=Hamburger |first2=Peter |title=Set Theory |publisher=Cambridge University Press |location=Cambridge |year=1999 |isbn=9780521596671 |url=https://archive.org/details/settheory0000hajn |url-access=registration }}
* {{Cite book| last = Kechris | first = Alexander S. | authorlink = Alexander S. Kechris | title = Classical Descriptive Set Theory | others = [[Graduate Texts in Mathematics]] 156 | publisher = Springer | year = 1995 | isbn = 0-387-94374-9 | id = {{isbn|3-540-94374-9}}}}
{{refend}}

== External links ==
* [http://www.math.uu.nl/people/jvoosten/syllabi/logicasyllmoeder.pdf Sets, Models and Proofs] by [[Ieke Moerdijk]] and [http://www.math.uu.nl/people/jvoosten/ Jaap van Oosten], see Definition 3.1 and Exercise 56 on pp.&nbsp;68–69.
* [https://web.archive.org/web/20070930230404/http://planetmath.org/encyclopedia/TreeSetTheoretic.html tree (set theoretic)] by [http://planetmath.org/?op=getuser&id=455 Henry] on [http://planetmath.org/ PlanetMath]
* [https://web.archive.org/web/20070712031425/http://planetmath.org/encyclopedia/Branch.html branch] by [http://planetmath.org/?op=getuser&id=455 Henry] on [http://planetmath.org/ PlanetMath]
* [https://web.archive.org/web/20070930231713/http://planetmath.org/encyclopedia/ExampleOfTreeSetTheoretic.htm example of tree (set theoretic)] by [http://planetmath.org/?op=getuser&id=4983 uzeromay] on [http://planetmath.org/ PlanetMath]

[[Category:Set theory]]
[[Category:Trees (set theory)|*]]