Tree (descriptive set theory)
Tree (descriptive set theory)
In descriptive set theory, a tree on a set <math>X</math> is a collection of finite sequences of elements of <math>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>X</math> is denoted <math>X^{<\omega}</math>. With this notation, a tree is a nonempty subset <math>T</math> of <math>X^{<\omega}</math>, such that if <math>\langle x_0,x_1,\ldots,x_{n-1}\rangle</math> is a sequence of length <math>n</math> in <math>T</math>, and if <math>0\le m<n</math>, then the shortened sequence <math>\langle x_0,x_1,\ldots,x_{m-1}\rangle</math> also belongs to <math>T</math>. In particular, choosing <math>m=0</math> shows that the empty sequence belongs to every tree.
Branches and bodies A branch through a tree <math>T</math> is an infinite sequence of elements of <math>X</math>, each of whose finite prefixes belongs to <math>T</math>. The set of all branches through <math>T</math> is denoted <math>[T]</math> and called the *body* of the tree <math>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>T</math> is called a terminal node if it is not a prefix of a longer sequence in <math>T</math>. Equivalently, <math>\langle x_0,x_1,\ldots,x_{n-1}\rangle \in T</math> is terminal if there is no element <math>x</math> of <math>X</math> such that that <math>\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>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>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>T</math> and <math>U</math> are ordered by <math>T<U</math> if and only if <math>T</math> is a proper prefix of <math>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>X</math> (denoted as <math>X^\omega</math>) may be given the product topology, treating X as a discrete space. In this topology, every closed subset <math>C</math> of <math>X^\omega</math> is of the form <math>[T]</math> for some pruned tree <math>T</math>. Namely, let <math>T</math> consist of the set of finite prefixes of the infinite sequences in <math>C</math>. Conversely, the body <math>[T]</math> of every tree <math>T</math> forms a closed set in this topology.
Frequently trees on Cartesian products <math>X\times Y</math> are considered. In this case, by convention, we consider only the subset <math>T</math> of the product space, <math>(X\times Y)^{<\omega}</math>, containing only sequences whose even elements come from <math>X</math> and odd elements come from <math>Y</math> (e.g., <math>\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>X^{<\omega}\times Y^{<\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>[X^{<\omega}]\times [Y^{<\omega}]</math> with <math>[T]</math> for over the product space. We may then form the projection of <math>[T]</math>, : <math>p[T]=\{\vec x\in X^{\omega} | (\exists \vec y\in Y^{\omega})\langle \vec x,\vec y\rangle \in [T]\}</math>.