{{Short description|Collection of prefixes of finite sequences}} {{about|mathematical trees described by prefixes of finite sequences|trees described by partially ordered sets|Tree (set theory)}} In descriptive set theory, a '''tree''' on a set <math>X</math> is a collection of finite sequences of elements of <math>X</math> 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 <math>X</math> is denoted <math>X^{<\omega}</math>. With this notation, a tree is a nonempty subset <math>T</math> of <math>X^{<\omega}</math>, such that if <math>\langle x_0,x_1,\ldots,x_{n-1}\rangle</math> is a sequence of length <math>n</math> in <math>T</math>, and if <math>0\le m<n</math>, then the shortened sequence <math>\langle x_0,x_1,\ldots,x_{m-1}\rangle</math> also belongs to <math>T</math>. In particular, choosing <math>m=0</math> shows that the empty sequence belongs to every tree.
===Branches and bodies=== A '''branch''' through a tree <math>T</math> is an infinite sequence of elements of <math>X</math>, each of whose finite prefixes belongs to <math>T</math>. The set of all branches through <math>T</math> is denoted <math>[T]</math> and called the '''''body''''' of the tree <math>T</math>.
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 <math>T</math> is called a '''terminal node''' if it is not a prefix of a longer sequence in <math>T</math>. Equivalently, <math>\langle x_0,x_1,\ldots,x_{n-1}\rangle \in T</math> is terminal if there is no element <math>x</math> of <math>X</math> such that that <math>\langle x_0,x_1,\ldots,x_{n-1},x\rangle \in T</math>. 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 <math>T</math> is a tree in the descriptive set theory sense, then it corresponds to a graph with one vertex for each sequence in <math>T</math>, 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 <math>T</math> and <math>U</math> are ordered by <math>T<U</math> if and only if <math>T</math> is a proper prefix of <math>U</math>. 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 <math>X</math> (denoted as <math>X^\omega</math>) may be given the product topology, treating ''X'' as a discrete space. In this topology, every closed subset <math>C</math> of <math>X^\omega</math> is of the form <math>[T]</math> for some pruned tree <math>T</math>. Namely, let <math>T</math> consist of the set of finite prefixes of the infinite sequences in <math>C</math>. Conversely, the body <math>[T]</math> of every tree <math>T</math> forms a closed set in this topology.
Frequently trees on Cartesian products <math>X\times Y</math> are considered. In this case, by convention, we consider only the subset <math>T</math> of the product space, <math>(X\times Y)^{<\omega}</math>, containing only sequences whose even elements come from <math>X</math> and odd elements come from <math>Y</math> (e.g., <math>\langle x_0,y_1,x_2,y_3\ldots,x_{2m}, y_{2m+1}\rangle</math>). Elements in this subspace are identified in the natural way with a subset of the product of two spaces of sequences, <math>X^{<\omega}\times Y^{<\omega}</math> (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 <math>[X^{<\omega}]\times [Y^{<\omega}]</math> with <math>[T]</math> for over the product space. We may then form the '''projection''' of <math>[T]</math>, : <math>p[T]=\{\vec x\in X^{\omega} | (\exists \vec y\in Y^{\omega})\langle \vec x,\vec y\rangle \in [T]\}</math>.
==See also== *Laver tree, a type of tree used in set theory as part of a notion of forcing
==References== * {{Cite book| last = Kechris | first = Alexander S. | authorlink = Alexander S. Kechris | title = Classical Descriptive Set Theory | others = Graduate Texts in Mathematics 156 | publisher = Springer | year = 1995 | id = {{isbn|0-387-94374-9}} {{isbn|3-540-94374-9}}}}
{{DEFAULTSORT:Tree (Descriptive Set Theory)}} Category:Descriptive set theory Category:Trees (set theory) Category:Determinacy