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, 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 {\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).
Topology
The set of infinite sequences over X {\displaystyle X} (denoted as X ω {\displaystyle X^{\omega }} ) may be given the product topology, treating X as a discrete space. In this topology, every closed subset C {\displaystyle C} of X ω {\displaystyle X^{\omega }} is of the form [ T ] {\displaystyle [T]} for some pruned tree T {\displaystyle T} . Namely, let T {\displaystyle T} consist of the set of finite prefixes of the infinite sequences in C {\displaystyle C} . Conversely, the body [ T ] {\displaystyle [T]} of every tree T {\displaystyle T} forms a closed set in this topology.
Frequently trees on Cartesian products X × Y {\displaystyle X\times Y} are considered. In this case, by convention, we consider only the subset T {\displaystyle T} of the product space, ( X × Y ) < ω {\displaystyle (X\times Y)^{<\omega }} , containing only sequences whose even elements come from X {\displaystyle X} and odd elements come from Y {\displaystyle Y} (e.g., ⟨ x 0 , y 1 , x 2 , y 3 … , x 2 m , y 2 m + 1 ⟩ {\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, X < ω × Y < ω {\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 [ X < ω ] × [ Y < ω ] {\displaystyle [X^{<\omega }]\times [Y^{<\omega }]} with [ T ] {\displaystyle [T]} for over the product space. We may then form the projection of [ T ] {\displaystyle [T]} ,
p [ T ] = { x → ∈ X ω | ( ∃ y → ∈ Y ω ) ⟨ x → , y → ⟩ ∈ [ T ] } {\displaystyle p[T]=\{{\vec {x}}\in X^{\omega }|(\exists {\vec {y}}\in Y^{\omega })\langle {\vec {x}},{\vec {y}}\rangle \in [T]\}} .See also
- Laver tree, a type of tree used in set theory as part of a notion of forcing
- Kechris, Alexander S. (1995). Classical Descriptive Set Theory. Graduate Texts in Mathematics 156. Springer. ISBN 0-387-94374-9 ISBN 3-540-94374-9.