BREAKING NEWS

## Summary

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\leq m , 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  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, we consider only the subset $T$  of the product space, $(X\times Y)^{<\omega }$ , containing only sequences whose even elements come from $X$  and odd elements come from $Y$  (e.g., $\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, $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 $[X^{<\omega }]\times [Y^{<\omega }]$  with $[T]$  for over the product space. 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]\}$ .