Tree (descriptive set theory)

In descriptive set theory, a tree on a set [math]\displaystyle{ X }[/math] is a collection of finite sequences of elements of [math]\displaystyle{ X }[/math] 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 [math]\displaystyle{ X }[/math] is denoted [math]\displaystyle{ X^{\lt \omega} }[/math]. With this notation, a tree is a nonempty subset [math]\displaystyle{ T }[/math] of [math]\displaystyle{ X^{\lt \omega} }[/math], such that if [math]\displaystyle{ \langle x_0,x_1,\ldots,x_{n-1}\rangle }[/math] is a sequence of length [math]\displaystyle{ n }[/math] in [math]\displaystyle{ T }[/math], and if [math]\displaystyle{ 0\le m\lt n }[/math], then the shortened sequence [math]\displaystyle{ \langle x_0,x_1,\ldots,x_{m-1}\rangle }[/math] also belongs to [math]\displaystyle{ T }[/math]. In particular, choosing [math]\displaystyle{ m=0 }[/math] shows that the empty sequence belongs to every tree.

Branches and bodies

A branch through a tree [math]\displaystyle{ T }[/math] is an infinite sequence of elements of [math]\displaystyle{ X }[/math], each of whose finite prefixes belongs to [math]\displaystyle{ T }[/math]. The set of all branches through [math]\displaystyle{ T }[/math] is denoted [math]\displaystyle{ [T] }[/math] and called the body of the tree [math]\displaystyle{ T }[/math].

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 [math]\displaystyle{ T }[/math] is called a terminal node if it is not a prefix of a longer sequence in [math]\displaystyle{ T }[/math]. Equivalently, [math]\displaystyle{ \langle x_0,x_1,\ldots,x_{n-1}\rangle \in T }[/math] is terminal if there is no element [math]\displaystyle{ x }[/math] of [math]\displaystyle{ X }[/math] such that that [math]\displaystyle{ \langle x_0,x_1,\ldots,x_{n-1},x\rangle \in T }[/math]. 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 [math]\displaystyle{ T }[/math] is a tree in the descriptive set theory sense, then it corresponds to a graph with one vertex for each sequence in [math]\displaystyle{ T }[/math], 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 [math]\displaystyle{ T }[/math] and [math]\displaystyle{ U }[/math] are ordered by [math]\displaystyle{ T\lt U }[/math] if and only if [math]\displaystyle{ T }[/math] is a proper prefix of [math]\displaystyle{ U }[/math]. 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 [math]\displaystyle{ X }[/math] (denoted as [math]\displaystyle{ X^\omega }[/math]) may be given the product topology, treating X as a discrete space. In this topology, every closed subset [math]\displaystyle{ C }[/math] of [math]\displaystyle{ X^\omega }[/math] is of the form [math]\displaystyle{ [T] }[/math] for some pruned tree [math]\displaystyle{ T }[/math]. Namely, let [math]\displaystyle{ T }[/math] consist of the set of finite prefixes of the infinite sequences in [math]\displaystyle{ C }[/math]. Conversely, the body [math]\displaystyle{ [T] }[/math] of every tree [math]\displaystyle{ T }[/math] forms a closed set in this topology.

Frequently trees on Cartesian products [math]\displaystyle{ X\times Y }[/math] are considered. In this case, by convention, we consider only the subset [math]\displaystyle{ T }[/math] of the product space, [math]\displaystyle{ (X\times Y)^{\lt \omega} }[/math], containing only sequences whose even elements come from [math]\displaystyle{ X }[/math] and odd elements come from [math]\displaystyle{ Y }[/math] (e.g., [math]\displaystyle{ \langle x_0,y_1,x_2,y_3\ldots,x_{2m}, y_{2m+1}\rangle }[/math]). Elements in this subspace are identified in the natural way with a subset of the product of two spaces of sequences, [math]\displaystyle{ X^{\lt \omega}\times Y^{\lt \omega} }[/math] (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 [math]\displaystyle{ [X^{\lt \omega}]\times [Y^{\lt \omega}] }[/math] with [math]\displaystyle{ [T] }[/math] for over the product space. We may then form the projection of [math]\displaystyle{ [T] }[/math],

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

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.