Tree (descriptive set theory): Difference between revisions

Revision as of 19:28, 5 December 2013

Revision as of 00:29, 13 December 2013

Line 1:

{{for|the concept in set theory|Tree (set theory)}}

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

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

:<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> 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'''''.

Line 29:

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

Line 36:

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.

Line 47:

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

{{math-stub}}

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