In descriptive set theory, a tree on a set X is a collection of finite sequences of elements of 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 X is denoted X < ω . With this notation, a tree is a nonempty subset T of X < ω , such that if ⟨ x 0 , x 1 , … , x n − 1 ⟩ is a sequence of length n in T , and if 0 ≤ m < n , then the shortened sequence ⟨ x 0 , x 1 , … , x m − 1 ⟩ also belongs to T . In particular, choosing m = 0 shows that the empty sequence belongs to every tree.
Branches and bodies
A branch through a tree T is an infinite sequence of elements of X , each of whose finite prefixes belongs to T . The set of all branches through T is denoted [ T ] and called the body of the tree 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 T is called a terminal node if it is not a prefix of a longer sequence in T . Equivalently, ⟨ x 0 , x 1 , … , x n − 1 ⟩ ∈ T is terminal if there is no element x of X such that that ⟨ x 0 , x 1 , … , x n − 1 , x ⟩ ∈ T . A tree that does not have any terminal nodes is called pruned.
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 is a tree in the descriptive set theory sense, then it corresponds to a graph with one vertex for each sequence in 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 and U are ordered by T < U if and only if T is a proper prefix of 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 X (denoted as X ω ) may be given the product topology, treating X as a discrete space. In this topology, every closed subset C of X ω is of the form [ T ] for some pruned tree T . Namely, let T consist of the set of finite prefixes of the infinite sequences in C . Conversely, the body [ T ] of every tree T forms a closed set in this topology.
Frequently trees on Cartesian products X × Y are considered. In this case, by convention, we consider only the subset T of the product space, ( X × Y ) < ω , containing only sequences whose even elements come from X and odd elements come from Y (e.g., ⟨ x 0 , y 1 , x 2 , y 3 … , x 2 m , y 2 m + 1 ⟩ ). Elements in this subspace are identified in the natural way with a subset of the product of two spaces of sequences, X < ω × Y < ω (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 < ω ] with [ T ] for over the product space. We may then form the projection of [ T ] ,
p [ T ] = { x → ∈ X ω | ( ∃ y → ∈ Y ω ) ⟨ x → , y → ⟩ ∈ [ T ] } .
