Tree (descriptive set theory)
In descriptive set theory, a tree on a set X is a set of finite sequences of elements of X that is closed under initial segments.
More formally, it is a subset T of X ^{< ω}, such that if
and ,
then
- .
In particular, every nonempty tree contains the empty sequence.
A branch through T is an infinite sequence
- of elements of X
such that, for every natural number n,
- ,
where denotes the sequence of the first n elements of . The set of all branches through T is denoted [T] and called the body of the tree T.
A tree that has no branches is called wellfounded; a tree with at least one branch is illfounded.
A node (that is, element) of T is terminal if there is no node of T properly extending it; that is, is terminal if there is no element x of X such that that . A tree with no terminal nodes is called pruned.
If we equip X^{ω} with the product topology (treating X as a discrete space), then every closed subset of X^{ω} is of the form [T] for some pruned tree T (namely, ). Conversely, every set [T] is closed.
Frequently trees on cartesian products are considered. In this case, by convention, the set is identified in the natural way with a subset of , and [T] is considered as a subset of . We may then form the projection of [T],
Every tree in the sense described here is also a tree in the wider sense, i.e., the pair (T, <), where < is defined by
- x<y ⇔ x is a proper initial segment of y,
is a partial order in which each initial segment is well-ordered. The height of each sequence x is then its length, and hence finite.
Conversely, every partial order (T, <) where each initial segment { y: y < x_{0} } is well-ordered is isomorphic to a tree described here, assuming that all elements have finite height.
Thanks for reading my article
With warm regards
Debasish mishra
(mishradews.webnode.com)