Tree (descriptive set theory): Difference between revisions

Revision as of 19:28, 5 December 2013

Latest revision as of 19:58, 3 January 2021

(19 intermediate revisions by 15 users not shown)

Line 1:

{{forabout|themathematical concepttrees indescribed setby theoryprefixes 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 setcollection of [[finite sequencessequence]]s of elements of <math>X</math> such that isevery closed[[Prefix under(computer initialscience)|prefix]] segments.of a sequence in the collection also belongs to the collection.

{{technical|date=November 2013}}

In [[descriptive set theory]], a '''tree''' on a set <math>X</math> is a set of finite sequences of elements of <math>X</math> that is closed under initial segments.

==Definitions==

More formally, it is a subset <math>T</math> of <math>X^{<\omega}</math>, such that if

===Trees===

:<math>\langle x_0,x_1,\ldots,x_{n-1}\rangle \in T</math>

The collection of all finite sequences of elements of a set <math>X</math> is denoted <math>X^{<\omega}</math>.

MoreWith formallythis notation, ita 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===

and <math>0\le m<n</math>,

whereA '''branch''' through a tree <math>\vec x|nT</math> denotesis thean infinite sequence of theelements firstof <math>nX</math>, elementseach of whose finite prefixes belongs to <math>\vec xT</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.

then

===Terminal nodes===

:<math>\langle x_0,x_1,\ldots,x_{m-1}\rangle \in T</math>.

A nodefinite sequence (that is,belongs element)to ofa tree <math>T</math> is called a '''terminal node''' if thereit is nonot nodea prefix of a longer sequence in <math>T</math>. properly extending it; that isEquivalently, <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 withthat nodoes not have any terminal nodes is called '''pruned'''.

==Relation to other types of trees==

In particular, every nonempty tree contains the empty sequence.

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 [[Tree (set theory)|order-theoretic tree]] is a [[partially ordered set]] with one [[minimal element]] in which each element has a [[well-ordered]] set of predecessors.

A '''branch''' through <math>T</math> is an infinite sequence

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==

:<math>\vec x\in X^{\omega}</math> of elements of <math>X</math>

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 product]]s <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).

such that, for every natural number <math>n</math>,

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} |n (\exists \vec y\in Y^{\omega})\langle \vec x,\vec y\rangle \in [T]\}</math>, .

where <math>\vec x|n</math> denotes the sequence of the first <math>n</math> elements of <math>\vec x</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'''''.

A node (that is, element) of <math>T</math> is '''terminal''' if there is no node of <math>T</math> properly extending it; that is, <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 with no terminal nodes is called '''pruned'''.

If we equip <math>X^\omega</math> with the [[product topology]] (treating ''X'' as a [[discrete space]]), then 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, <math>T:= \{ \vec x|n: n \in \omega, x\in C\}</math>). Conversely, every set <math>[T]</math> is closed.

Frequently trees on [[cartesian product]]s <math>X\times Y</math> are considered. In this case, by convention, the set <math>(X\times Y)^{\omega}</math> is identified in the natural way with a subset of <math>X^{\omega}\times Y^{\omega}</math>, and <math>[T]</math> is considered as a subset of <math>X^{\omega}\times Y^{\omega}</math>. 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>

Every tree in the sense described here is also a [[tree (set theory)|tree in the wider sense]], i.e., the pair (''T'', &lt;), where &lt; is defined by

:''x''<''y'' &hArr; ''x'' is a proper initial segment of ''y'',

is a partial order in which each initial segment is well-ordered. The height of each sequence ''x'' is then its length, and hence finite.

Conversely, every partial order (''T'', &lt;) where each initial segment { ''y'': ''y'' < ''x''₀ } is well-ordered is isomorphic to a tree described here, assuming that all elements have finite height.

==See also==

*[[Laver tree]], a type of tree used in [[set theory]] as part of a notion of [[Forcing (mathematics)|forcing]]

*[[Laver tree]]

* [[Tree (set theory)]]

* [[König's lemma]]

==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 {{isbn|0-387-94374-9}} ISBN {{isbn|3-540-94374-9}}}}

{{math-stub}}

{{DEFAULTSORT:Tree (Descriptive Set Theory)}}