Content deleted Content added
No edit summary |
No edit summary |
||
Line 1:
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'''.
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>,
: <math>p[T]=\{\vec x\in X^{\omega} | (\exists \vec y\in Y^{\omega})<\vec x,\vec y>\in [T]\}</math>
{{math-stub}}
| |||