Tree (descriptive set theory)

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 ${\displaystyle T}$ is a tree in the descriptive set theory sense, then it corresponds to a graph with one vertex for each sequence in ${\displaystyle 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 ${\displaystyle T}$ and ${\displaystyle U}$ are ordered by ${\displaystyle T<U}$ if and only if ${\displaystyle T}$ is a proper prefix of ${\displaystyle 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 ${\displaystyle X}$ (denoted as ${\displaystyle X^{\omega }}$) may be given the product topology, treating X as a discrete space. In this topology, every closed subset ${\displaystyle C}$ of ${\displaystyle X^{\omega }}$ is of the form ${\displaystyle [T]}$ for some pruned tree ${\displaystyle T}$. Namely, let ${\displaystyle T}$ consist of the set of finite prefixes of the infinite sequences in ${\displaystyle C}$. Conversely, the body ${\displaystyle [T]}$ of every tree ${\displaystyle T}$ forms a closed set in this topology.

Frequently trees on Cartesian products ${\displaystyle X\times Y}$ are considered. In this case, by convention, we consider only the subset ${\displaystyle T}$ of the product space, ${\displaystyle (X\times Y{)}^{<\omega }}$, containing only sequences whose even elements come from ${\displaystyle X}$ and odd elements come from ${\displaystyle Y}$ (e.g., ${\displaystyle ⟨x_0,y_1,x_2,y_3\dots ,x_{2m},y_{2m+1}⟩}$). Elements in this subspace are identified in the natural way with a subset of the product of two spaces of sequences, ${\displaystyle X^{<\omega }\times Y^{<\omega }}$ (the subset for which the length of the first sequence is equal to or 1 more than the length of the second sequence). In this way we may identify ${\displaystyle [X^{<\omega }]\times [Y^{<\omega }]}$ with ${\displaystyle [T]}$ for over the product space. We may then form the projection of ${\displaystyle [T]}$,

${\displaystyle p[T]=\{\overrightarrow{x}\in X^{\omega }|(\mathrm{\exists }\overrightarrow{y}\in Y^{\omega })⟨\overrightarrow{x},\overrightarrow{y}⟩\in [T]\}}$.