Tree (descriptive set theory)

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.

Uses your system voice; voice and rate in settings.

≈ 4 min read

Cite, export and learn8 citation formats · 8 exports · lesson and quiz

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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.

Trees

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 \langle x_0,x_1,\ldots,x_{n-1}\rangle is a sequence of length n in T , and if 0\le m , then the shortened sequence \langle x_0,x_1,\ldots,x_{m-1}\rangle 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, an infinite tree on a finite set must necessarily be illfounded.

Terminal nodes

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, \langle x_0,x_1,\ldots,x_{n-1}\rangle \in T is terminal if there is no element x of X such that that \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 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 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).

Topology

The set of infinite sequences over X (denoted as X^\omega ) may be given the product topology, treating X as a discrete space. In this topology, every closed subset C of X^\omega 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\times Y are considered. In this case, by convention, we consider only the subset T of the product space, (X\times Y)^{ , containing only sequences whose even elements come from X and odd elements come from Y (e.g., \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^{ (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^{ with [T] for over the product space.

We may then form the projection of [T] , 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

Text derived from https://en.wikipedia.org/w/index.php?oldid=1371015898 under CC BY-SA 4.0; modifications have been made.

Words in each sectionRelation to other types…Relation to other types of treesRelation to other types of trees: 234 words234TopologyTopologyTopology: 223 words223TreesTreesTrees: 83 words83Branches and bodiesBranches and bodiesBranches and bodies: 75 words75Terminal nodesTerminal nodesTerminal nodes: 75 words75See alsoSee alsoSee also: 38 words38
Words in each section. Measured from the stored article body; sections below the minimum are not plotted.

Provenance

snapshot enwiki-001371015898 · captured 2026-08-24 · ledger · version history

Cite this page as: encyclopegia.org, “Tree (descriptive set theory)”, snapshot enwiki-001371015898. https://encyclopegia.org/a/tree-descriptive-set-theory

Sources cited in this revision

No external citation was extracted for this revision. That is a statement about the source, not a claim that none exists.