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 initial segments.

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

$\langle x_{0},x_{1},\ldots ,x_{n-1}\rangle \in T$

and $0\leq 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^{\omega }$ with the product topology (treating X as a discrete 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 ,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 < x₀ } is well-ordered is isomorphic to a tree described here, assuming that all elements have finite height.

See also

• Laver tree
• Tree (set theory)
• König's lemma

References

• Kechris, Alexander S. (1995). Classical Descriptive Set Theory. Graduate Texts in Mathematics 156. Springer. ISBN 0-387-94374-9 ISBN 3-540-94374-9.