Pruned tree

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^\left\{<\omega\right\}$, such that if

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

and

then

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

In particular, every nonempty tree contains the empty sequence.

A branch through $T$ is an infinite sequence

$\vec x\in X^\left\{\omega\right\}$ 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 $\left[T\right]$ 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_\left\{n-1\right\}\rangle \in T$ is terminal if there is no element $x$ of $X$ such that that $\langle x_0,x_1,\ldots,x_\left\{n-1\right\},x\rangle \in T$. A tree with no terminal nodes is called pruned.

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

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

$p\left[T\right]=\\left\{\vec x\in X^\left\{\omega\right\} | \left(\exists \vec y\in Y^\left\{\omega\right\}\right)\langle \vec x,\vec y\rangle \in \left[T\right]\\right\}$

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<yx 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.