Tree (descriptive set theory): Difference between revisions

Revision as of 00:34, 5 April 2014

Latest revision as of 19:58, 3 January 2021

(17 intermediate revisions by 14 users not shown)

Line 3:

==Definitions==

===Trees===

The collection of all finite sequencesequences 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>,

Line 12 ⟶ 13:

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önigKőnig's lemma]], a tree on a [[finite set]] with an infinite number of sequences must necessarily be illfounded.

===Terminal nodes===

Line 30 ⟶ 31:

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, thewe setconsider ofonly finitethe sequencessubset of members<math>T</math> of the product space, <math>(X\times Y)^{<\omega}</math>, iscontaining 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 offor memberswhich the length of the secondfirst productsequence foris whichequal bothto sequencesor have1 themore samethan the length of the second sequence).

In this way a tree <math>[T]</math> over the product spacewe may be considered as a subset ofidentify <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>.

Line 38 ⟶ 39:

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

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