Tree (descriptive set theory)

From Wikipedia, the free encyclopedia

In descriptive set theory, a tree on a set <math>X</math> is a set of finite sequences of elements of <math>X</math> that is closed under subsequences.

More formally, it is a subset <math>T</math> of <math>X^{<\omega}</math>, such that if

<math>\langle x_0,x_1,\ldots,x_{n-1}\rangle \in T</math>

and <math>0\le m<n</math>,

then

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

In particular, every nonempty tree contains the empty sequence.

A branch through <math>T</math> is an infinite sequence

<math>\vec x\in X^{\omega}</math> of elements of <math>X</math>

such that, for every natural number <math>n</math>,

<math>\vec x|n\in T</math>,

where <math>\vec x|n</math> denotes the sequence of the first <math>n</math> elements of <math>\vec x</math>. The set of all branches through <math>T</math> is denoted <math>[T]</math> and called the body of the tree <math>T</math>.

A tree that has no branches is called wellfounded; a tree with at least one branch is illfounded.

A node (that is, element) of <math>T</math> is terminal if there is no node of <math>T</math> properly extending it; that is, <math>\langle x_0,x_1,\ldots,x_{n-1}\rangle \in T</math> is terminal if there is no element <math>x</math> of <math>X</math> such that that <math>\langle x_0,x_1,\ldots,x_{n-1},x\rangle \in T</math>. A tree with no terminal nodes is called pruned.

If we equip <math>X^\omega</math> with the product topology (treating X as a discrete space), then every closed subset of <math>X^\omega</math> is of the form <math>[T]</math> for some pruned tree <math>T</math> (namely, <math>T:= \{ \vec x|n: n \in \omega, x\in X\}</math>). Conversely, every set <math>[T]</math> is closed.

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

<math>p[T]=\{\vec x\in X^{\omega} | (\exists \vec y\in Y^{\omega})\langle \vec x,\vec y\rangle \in [T]\}</math>

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₀ } is well-ordered is isomorphic to a tree described here, assuming that all elements have finite height.