Tree (descriptive set theory)

12/10/2011 15:25

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

\langle x_0,x_1,\ldots,x_{n-1}\rangle \in T

and 0\le m<n,

then

\langle x_0,x_1,\ldots,x_{m-1}\rangle \in T.

In particular, every nonempty tree contains the empty sequence.

A branch through T is an infinite sequence

\vec x\in X^{\omega} of elements of X

such that, for every natural number n,

\vec x|n\in 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}\rangle \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\rangle \in T. 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, T:= \{ \vec x|n: n \in \omega, x\in X\}). Conversely, every set [T] is closed.

Frequently trees on cartesian products X\times Y are considered. In this case, by convention, the set (X\times Y)^{\omega} is identified in the natural way with a subset of X^{\omega}\times Y^{\omega}, and [T] is considered as a subset of X^{\omega}\times Y^{\omega}. We may then form the projection of [T],

p[T]=\{\vec x\in X^{\omega} | (\exists \vec y\in Y^{\omega})\langle \vec x,\vec y\rangle \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 < x0 } 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)

Back