Tree (descriptive set theory) explained
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
Trees
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
\langlex0,x1,\ldots,xn-1\rangle
is a sequence of length
in
, and if
,then the shortened sequence
\langlex0,x1,\ldots,xm-1\rangle
also belongs to
. In particular, choosing
shows that the empty sequence belongs to every tree.
Branches and bodies
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
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,
\langlex0,x1,\ldots,xn-1\rangle\inT
is terminal if there is no element
of
such that that
\langlex0,x1,\ldots,xn-1,x\rangle\inT
. 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
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
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.,
\langlex0,y1,x2,y3\ldots,x2m,y2m+1\rangle
). 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
,
p[T]=\{\vecx\inX\omega|(\exists\vecy\inY\omega)\langle\vecx,\vecy\rangle\in[T]\}
.
See also
References
- Book: Kechris, Alexander S. . Alexander S. Kechris
. Alexander S. Kechris . Classical Descriptive Set Theory . Graduate Texts in Mathematics 156 . Springer . 1995 . .
