Tree (descriptive set theory)

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

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

A branch through a tree ${\displaystyle T}${\displaystyle T} is an infinite sequence of elements of ${\displaystyle X}${\displaystyle X}, each of whose finite prefixes belongs to ${\displaystyle T}${\displaystyle T}. The set of all branches through ${\displaystyle T}${\displaystyle T} is denoted ${\displaystyle [T]}${\displaystyle [T]} and called the body of the tree ${\displaystyle T}${\displaystyle 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.

A finite sequence that belongs to a tree ${\displaystyle T}${\displaystyle T} is called a terminal node if it is not a prefix of a longer sequence in ${\displaystyle T}${\displaystyle T}. Equivalently, ${\displaystyle \langle x_{0},x_{1},\ldots ,x_{n-1}\rangle \in T}${\displaystyle \langle x_{0},x_{1},\ldots ,x_{n-1}\rangle \in T} is terminal if there is no element ${\displaystyle x}${\displaystyle x} of ${\displaystyle X}${\displaystyle X} such that that ${\displaystyle \langle x_{0},x_{1},\ldots ,x_{n-1},x\rangle \in T}${\displaystyle \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.

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}${\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}${\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}${\displaystyle T} and ${\displaystyle U}${\displaystyle U} are ordered by ${\displaystyle T<U}${\displaystyle T<U} if and only if ${\displaystyle T}${\displaystyle T} is a proper prefix of ${\displaystyle U}${\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).

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

Frequently trees on Cartesian products ${\displaystyle X\times Y}${\displaystyle X\times Y} are considered. In this case, by convention, we consider only the subset ${\displaystyle T}${\displaystyle T} of the product space, ${\displaystyle (X\times Y)^{<\omega }}${\displaystyle (X\times Y)^{<\omega }}, containing only sequences whose even elements come from ${\displaystyle X}${\displaystyle X} and odd elements come from ${\displaystyle Y}${\displaystyle Y} (e.g., ${\displaystyle \langle x_{0},y_{1},x_{2},y_{3}\ldots ,x_{2m},y_{2m+1}\rangle }${\displaystyle \langle x_{0},y_{1},x_{2},y_{3}\ldots ,x_{2m},y_{2m+1}\rangle }). 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 }}${\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 }]}${\displaystyle [X^{<\omega }]\times [Y^{<\omega }]} with ${\displaystyle [T]}${\displaystyle [T]} for over the product space. We may then form the projection of ${\displaystyle [T]}${\displaystyle [T]},

${\displaystyle p[T]=\{{\vec {x}}\in X^{\omega }|(\exists {\vec {y}}\in Y^{\omega })\langle {\vec {x}},{\vec {y}}\rangle \in [T]\}}${\displaystyle p[T]=\{{\vec {x}}\in X^{\omega }|(\exists {\vec {y}}\in Y^{\omega })\langle {\vec {x}},{\vec {y}}\rangle \in [T]\}}.

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

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

• Descriptive set theory
• Trees (set theory)
• Determinacy