Tree (descriptive set theory)

In descriptive set theory, a tree on a set $X$ is a collection of finite sequences of elements of $X$ such that every prefix of a sequence in the collection also belongs to the collection.

Definitions

Trees

The collection of all finite sequences of elements of a set $X$ is denoted $X^{<\omega}$. With this notation, a tree is a nonempty subset $T$ of $X^{<\omega}$, such that if $\langle x_0,x_1,\ldots,x_{n-1}\rangle$ is a sequence of length $n$ in $T$, and if $0\le m<n$, then the shortened sequence $\langle x_0,x_1,\ldots,x_{m-1}\rangle$ also belongs to $T$. In particular, choosing $m=0$ shows that the empty sequence belongs to every tree.

Branches and bodies

A branch through a tree $T$ is an infinite sequence of elements of $X$, each of whose finite prefixes belongs to $T$. 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. By König's lemma, a tree on a finite set with an infinite number of sequences must necessarily be illfounded.

Terminal nodes

A finite sequence that belongs to a tree $T$ is called a terminal node if it is not a prefix of a longer sequence in $T$. Equivalently, $\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 that does not have any terminal nodes is called pruned.

Relation to other types of trees

In graph theory, a rooted tree is a directed graph in which every vertex except for a special root vertex has exactly one outgoing edge, and in which the path formed by following these edges from any vertex eventually leads to the root vertex. If $T$ is a tree in the descriptive set theory sense, then it corresponds to a graph with one vertex for each sequence in $T$, and an outgoing edge from each nonempty sequence that connects it to the shorter sequence formed by removing its last element. This graph is a tree in the graph-theoretic sense. The root of the tree is the empty sequence.

In order theory, a different notion of a tree is used: an order-theoretic tree is a partially ordered set with one minimal element in which each element has a well-ordered set of predecessors. Every tree in descriptive set theory is also an order-theoretic tree, using a partial ordering in which two sequences $T$ and $U$ are ordered by $T<U$ if and only if $T$ is a proper prefix of $U$. The empty sequence is the unique minimal element, and each element has a finite and well-ordered set of predecessors (the set of all of its prefixes). An order-theoretic tree may be represented by an isomorphic tree of sequences if and only if each of its elements has finite height (that is, a finite set of predecessors).

Topology

The set of infinite sequences over $X$ (denoted as $X^\omega$) may be given the product topology, treating X as a discrete space. In this topology, every closed subset $C$ of $X^\omega$ is of the form $[T]$ for some pruned tree $T$. Namely, let $T$ consist of the set of finite prefixes of the infinite sequences in $C$. Conversely, the body $[T]$ of every tree $T$ forms a closed set in this topology.

Frequently trees on Cartesian products $X\times Y$ are considered. In this case, by convention, the set of finite sequences of members of the product space, $(X\times Y)^{<\omega}$, is identified in the natural way with a subset of the product of two spaces of sequences, $X^{<\omega}\times Y^{<\omega}$ (the subset of members of the second product for which both sequences have the same length). In this way a tree $[T]$ over the product space may be 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]\}$.

See also

• Laver tree, a type of tree used in set theory as part of a notion of forcing

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.