Content deleted Content added
cat DST |
format and make simpler intro |
||
Line 1:
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 subsequences.
More formally, it is a subset <math>T</math> of <math>X^{<\omega}</math>, such that 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'''''.
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'''.
| |||