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

:$langle\; x\_0,x\_1,ldots,x\_\{n-1\}\; angle\; in\; T$

and

then

:$langle\; x\_0,x\_1,ldots,x\_\{m-1\}\; angle\; in\; T$.

In particular, every nonempty tree contains the empty sequence.

A branch through $T$ is an infinite sequence

:$vec\; xin\; X^\{omega\}$ of elements of $X$

such that, for every natural number $n$,

:$vec\; x|nin\; 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\}\; angle\; 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\; angle\; 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,\; xin\; X\}$). Conversely, every set $[T]$ is closed.

Frequently trees on cartesian products $X\; imes\; Y$ are considered. In this case, by convention, the set $(X\; imes\; Y)^\{omega\}$ is identified in the natural way with a subset of $X^\{omega\}\; imes\; Y^\{omega\}$, and $[T]$ is considered as a subset of $X^\{omega\}\; imes\; Y^\{omega\}$. We may then form the projection of $[T]$,: $p\; [T]\; =\{vec\; xin\; X^\{omega\}\; |\; (exists\; vec\; yin\; Y^\{omega\})langle\; vec\; x,vec\; y\; angle\; in\; [T]\; \}$

Every tree in the sense described here is also a tree in the wider sense, i.e., the pair ("T", &lt;), where &lt; is defined by:"x"<"y" &hArr; "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", &lt;) 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)