en.wikipedia.org

Tree (descriptive set theory) - Wikipedia

From Wikipedia, the free encyclopedia

This article is about mathematical trees described by prefixes of finite sequences. For trees described by partially ordered sets, see Tree (set theory).

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

Branches and bodies

[edit]

A branch through a tree {\displaystyle T} is an infinite sequence of elements of {\displaystyle X}, each of whose finite prefixes belongs to {\displaystyle T}. The set of all branches through {\displaystyle T} is denoted {\displaystyle [T]} and called the body of the tree {\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} is called a terminal node if it is not a prefix of a longer sequence in {\displaystyle T}. Equivalently, {\displaystyle \langle x_{0},x_{1},\ldots ,x_{n-1}\rangle \in T} is terminal if there is no element {\displaystyle x} of {\displaystyle X} such that that {\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.

Relation to other types of trees

[edit]

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).

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 \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 }} (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]=\{{\vec {x}}\in X^{\omega }|(\exists {\vec {y}}\in Y^{\omega })\langle {\vec {x}},{\vec {y}}\rangle \in [T]\}}.