In descriptive set theory, a tree on a set X {\displaystyle X} is a collection of finite sequences of elements of X {\displaystyle 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 {\displaystyle X} is denoted X < ω {\displaystyle X^{<\omega }} . With this notation, a tree is a nonempty subset T {\displaystyle T} of X < ω {\displaystyle X^{<\omega }} , such that if
⟨ x 0 , x 1 , … , x n − 1 ⟩ {\displaystyle \langle x_{0},x_{1},\ldots ,x_{n-1}\rangle } is a sequence of length n {\displaystyle n} in T {\displaystyle T} , and if 0 ≤ m < n {\displaystyle 0\leq m<n} , then the shortened sequence ⟨ x 0 , x 1 , … , x m − 1 ⟩ {\displaystyle \langle x_{0},x_{1},\ldots ,x_{m-1}\rangle } also belongs to T {\displaystyle T} . In particular, choosing m = 0 {\displaystyle m=0} shows that the empty sequence belongs to every tree.
Branches and bodies A branch through a tree T {\displaystyle T} is an infinite sequence of elements of X {\displaystyle X} , each of whose finite prefixes belongs to T {\displaystyle T} . The set of all branches through T {\displaystyle T} is denoted [ T ] {\displaystyle [T]} and called the body of the tree 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, an infinite tree on a finite set must necessarily be illfounded.
Terminal nodes A finite sequence that belongs to a tree T {\displaystyle T} is called a terminal node if it is not a prefix of a longer sequence in T {\displaystyle T} . Equivalently, ⟨ x 0 , x 1 , … , x n − 1 ⟩ ∈ T {\displaystyle \langle x_{0},x_{1},\ldots ,x_{n-1}\rangle \in T} is terminal if there is no element x {\displaystyle x} of X {\displaystyle X} such that that ⟨ x 0 , x 1 , … , x n − 1 , x ⟩ ∈ 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.
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 {\displaystyle T} is a tree in the descriptive set theory sense, then it corresponds to a graph with one vertex for each sequence in 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 T {\displaystyle T} and U {\displaystyle U} are ordered by T < U {\displaystyle T<U} if and only if T {\displaystyle T} is a proper prefix of 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).
… excerpt ends here. Continue reading the full article.
