Jump to content

Tree (descriptive set theory)

From Wikipedia, the free encyclopedia

This is the current revision of this page, as edited by David Eppstein (talk | contribs) at 19:58, 3 January 2021 (Undid revision 998041846 by Hellacioussatyr (talk) please do not convert properly formatted mathematics markup into junk pseudo-math templates). The present address (URL) is a permanent link to this version.

(diff) ← Previous revision | Latest revision (diff) | Newer revision → (diff)

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.