Tree (set theory)
This article includes a improve this article by introducing more precise citations. (January 2021) ) |
In
Definition
A tree is a
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 of height > ω, then the Hasse diagram definition does not work. For example, the partially ordered set does not have a Hasse Diagram, as there is no predecessor to ω. Hence a height of at most ω is required in this case.
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 α, the α-th level of T is the set of all elements of T of height α. A tree is a κ-tree, for an ordinal number κ, if and only if it has height κ and every level has cardinality less than the cardinality of κ. The width of a tree is the supremum of the cardinalities of its levels.
Any single-rooted tree of height forms a meet-semilattice, where meet (common ancestor) is given by maximal element of intersection of ancestors, which exists as the set of ancestors is non-empty and finite well-ordered, hence has a maximal element. Without a single root, the intersection of parents can be empty (two elements need not have common ancestors), for example where the elements are not comparable; while if there are an infinite number of ancestors there need not be a maximal element – for example, where are not comparable.
A subtree of a tree is a tree where and is
Set-theoretic properties
There are some fairly simply stated yet hard problems in infinite tree theory. Examples of this are the
The Suslin conjecture was originally stated as a question about certain
of cardinality ω1 or a branch of length ω1.If (T,<) is a tree, then the reflexive closure ≤ of < is a prefix order on T. The converse does not hold: for example, the usual order ≤ on the set Z of integers is a total and hence a prefix order, but (Z,<) is not a set-theoretic tree since e.g. the set {n ∈Z: n < 0} has no least element.
Examples of infinite trees
- Let be an ordinal number, and let be a set. Let be set of all functions where . Define if the domain of is a proper subset of the domain of and the two functions agree on the domain of . Then is a set-theoretic tree. Its root is the unique function on the empty set, and its height is . The union of all functions along a branch yields a function from to , that is, a generalized sequence of members of . If is a leaf"). The picture shows an example for and .
- Each tree data structure in computer science is a set-theoretic tree: for two nodes , define if is a proper descendant of . 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 .
- A graph-theoretic tree can be turned into a set-theoretic one by choosing a root node and defining if and lies on the (unique) undirected path from to .
- Each Laver treeis a set-theoretic tree.
See also
- Tree (descriptive set theory)
- Continuous graph
References
- Jech, Thomas (2002). Set Theory. Springer-Verlag. ISBN 3-540-44085-2.
- ISBN 0-444-85401-0. Chapter 2, Section 5.
- Monk, J. Donald (1976). Mathematical Logic. New York: Springer-Verlag. p. 517. ISBN 0-387-90170-1.
- ISBN 9780521596671.
- ISBN 3-540-94374-9.
External links
- Sets, Models and Proofs by Ieke Moerdijk and Jaap van Oosten, see Definition 3.1 and Exercise 56 on pp. 68–69.
- tree (set theoretic) by Henry on PlanetMath
- branch by Henry on PlanetMath
- example of tree (set theoretic) by uzeromay on PlanetMath