Tree (descriptive set theory): Difference between revisions

Revision as of 03:33, 8 July 2005

Latest revision as of 19:58, 3 January 2021

(44 intermediate revisions by 29 users not shown)

Line 1:

{{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 subset <math>T</math> of <math>X^{<\omega}</math> (that is, a set of finite sequences of elements of <math>X</math>) that is closed under subsequence (that is, if <math><x_0,x_1,\ldots,x_{n-1}>\in T</math> and <math>m<n</math>, then <math><x_0,x_1,\ldots,x_{m-1}>\in T</math>). A '''branch''' through <math>T</math> is an infinite sequence <math>\vec x\in X^{\omega}</math> of elements of <math>X</math> such that, for every natural number <math>n</math>, <math>\vec x|n\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>. A tree that has no branches is called '''wellfounded'''; a tree with at least one branch is '''illfounded'''.

In [[descriptive set theory]], a '''tree''' on a set <math>X</math> is a collection of [[finite sequence]]s of elements of <math>X</math> such that every [[Prefix (computer science)|prefix]] of a sequence in the collection also belongs to the collection.

==Definitions==

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><x_0,x_1,\ldots,x_{n-1}>\in T</math> is terminal if there is no element <math>x</math> of <math>X</math> such that that <math><x_0,x_1,\ldots,x_{n-1},x>\in T</math>. A tree with no terminal nodes is called '''pruned'''.

===Trees===

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

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

: <math>p[T]=\{\vec x\in X^{\omega} | (\exists \vec y\in Y^{\omega})<\vec x,\vec y>\in [T]\}</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===

{{math-stub}}

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 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 [[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.

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 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).

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 (mathematics)|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]]