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

$<x_{0},x_{1},\ldots ,x_{n-1}>\in T$

and

$m<n$,

then

$<x_{0},x_{1},\ldots ,x_{m-1}>\in T$.

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]$.

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, $<x_{0},x_{1},\ldots ,x_{n-1}>\in T$ is terminal if there is no element $x$ of $X$ such that that $<x_{0},x_{1},\ldots ,x_{n-1},x>\in T$. A tree with no terminal nodes is called pruned.

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 $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 })<{\vec {x}},{\vec {y}}>\in [T]\}$

See also

• Infinite tree (graph theory)