Tree (descriptive set theory)

(Redirected from Pruned tree)

In descriptive set theory, a tree on a set is a collection of finite sequences of elements of such that every prefix of a sequence in the collection also belongs to the collection.

Definitions

edit

Trees

edit

The collection of all finite sequences of elements of a set   is denoted  . With this notation, a tree is a nonempty subset   of  , such that if   is a sequence of length   in  , and if  , then the shortened sequence   also belongs to  . In particular, choosing   shows that the empty sequence belongs to every tree.

Branches and bodies

edit

A branch through a tree   is an infinite sequence of elements of  , each of whose finite prefixes belongs to  . The set of all branches through   is denoted   and called the body of the tree  .

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

edit

A finite sequence that belongs to a tree   is called a terminal node if it is not a prefix of a longer sequence in  . Equivalently,   is terminal if there is no element   of   such that that  . 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   is a tree in the descriptive set theory sense, then it corresponds to a graph with one vertex for each sequence in  , 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   and   are ordered by   if and only if   is a proper prefix of  . 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

edit

The set of infinite sequences over   (denoted as  ) may be given the product topology, treating X as a discrete space. In this topology, every closed subset   of   is of the form   for some pruned tree  . Namely, let   consist of the set of finite prefixes of the infinite sequences in  . Conversely, the body   of every tree   forms a closed set in this topology.

Frequently trees on Cartesian products   are considered. In this case, by convention, we consider only the subset   of the product space,  , containing only sequences whose even elements come from   and odd elements come from   (e.g.,  ). Elements in this subspace are identified in the natural way with a subset of the product of two spaces of sequences,   (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   with   for over the product space. We may then form the projection of  ,

 .

See also

edit

References

edit
  • Kechris, Alexander S. (1995). Classical Descriptive Set Theory. Graduate Texts in Mathematics 156. Springer. ISBN 0-387-94374-9 ISBN 3-540-94374-9.