Tree (descriptive set theory): Difference between revisions

Revision as of 05:56, 1 September 2005

Revision as of 16:30, 11 July 2006

Line 3:

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

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

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

then

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

In particular, every nonempty tree contains the empty sequence.

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

Line 23 ⟶ 25:

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 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 X\}</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.

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>

== See also ==