- 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 subsequences.More formally, it is a subset T of X^{
, such that if :langle x_0,x_1,ldots,x_{n-1} angle in T
and 0le m
, then
:langle x_0,x_1,ldots,x_{m-1} angle in T.
In particular, every nonempty tree contains the empty sequence.
A branch through T is an infinite sequence
:vec xin X^{omega} of elements of X
such that, for every natural number n,
:vec x|nin T,
where vec x|n denotes the sequence of the first n elements of vec x. 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, langle x_0,x_1,ldots,x_{n-1} angle in T is terminal if there is no element x of X such that that langle x_0,x_1,ldots,x_{n-1},x angle in T. A tree with no terminal nodes is called pruned.
If we equip X^omega with the
product topology (treating "X" as adiscrete space ), then every closed subset of X^omega is of the form T] for some pruned tree T (namely, T:= { vec x|n: n in omega, xin X}). Conversely, every set T] is closed.Frequently trees on
cartesian product s X imes Y are considered. In this case, by convention, the set X imes Y)^{omega} is identified in the natural way with a subset of X^{omega} imes Y^{omega}, and T] is considered as a subset of X^{omega} imes Y^{omega}. We may then form the projection of T] ,: p [T] ={vec xin X^{omega} | (exists vec yin Y^{omega})langle vec x,vec y angle in [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.
See also
*
Laver tree
*Tree (set theory)
Wikimedia Foundation. 2010.