Suppose $T$ is a well-founded tree on $\mathbb{N}$, that is, a set of finite sequences of $\mathbb{N}$ closed under taking initial segments. Well-founded means that there is no infinite sequence $(x_n)$ such that for all $k$, $(x_1, x_2, \dots,x_k)\in T$. Put $T_0:=T$ and for any succesor ordinal $\alpha$ define $T_\alpha$ to be the tree obtained by removing the maximal elements from $T_{\alpha-1}$. If $\alpha$ is a limit ordinal, $T_\alpha:=\cap_{\gamma<\alpha} T_{\gamma}$. The order $o(T)$ of the tree is defined as the smallest ordinal $\delta$ for which $T_{\delta}=\emptyset$.

Can one provide a reference, or a brif explanation if it is not too complicated, for the following facts, which I found mentioned, without any explanation, in a paper.

  • For any tree $T$ on $\mathbb{N}$, $o(T)<\omega_1$.
  • For any $\alpha<\omega_1$, there exists a tree $T_\alpha$ such that $o(T_\alpha)=\alpha$.

1 Answer 1


The two main references for descriptive set theory will be of much use:

In case, the answers to your questions are pretty straightforward.

Since $T$ is countable (and wellfounded), at each successor step you erase some node. Having $O(T)$ where $\geq\omega_1$ would require erasing uncountably many nodes, an absurdity.

Finally, fix a wellorder $R$ of $\mathbb{N}$ in ordertype $\alpha$ and define $T_\alpha$ to be the tree of strictly decreasing $R$-chains.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .