Trees on $\omega$

2012-07-04T04:53:55Z

I am going to give a construction of a tree on $\omega$ that at first appears as though it is well founded. However, this tree cannot be well-founded because, using the rank function on finite sequences from $\omega$ into the ordinals $\phi_T(u) = supremum\{\phi(u$^(x))+1|u^(x)$\in T\}$, $\phi(\emptyset)=\omega^\omega$ . Because $\phi$ is onto $\omega^\omega$ we get that T is of size continuum, which is impossible.

The construction proceeds as follows:

1) Create a tree $T_0$ s.t. $\phi_{T_0}(\emptyset)=\omega$ by having a branch of length n for all $n\in\omega$ Note $T_0$ is well founded.

2) Create a tree $T_1$ s.t. $\phi_{T_1}(\emptyset)=\omega+\omega$ by having level 1 branches $u_i$ s.t. $\phi(u_i)=\omega+i$ . Note $T_1$ is well_founded (each $T[u_i]=\{v\in T|$ v is compatible with $U_i\}$ is well founded.)

3) Similarly create trees $T_n$ s.t. `$\phi_{T_n}(\emptyset)=n*\omega$

4) Create a tree $T_\omega$ with level 1 branches $T_n$ so that $\phi_{T_\omega}(\emptyset)=\omega*\omega$ . Note that because each of the branches is well founded.

5) Similarly create trees $T_{n*\omega}$ s.t. $\phi_{T_{n*\omega}}(\emptyset)=\omega^n$

6) Finally, using the $T_{n*\omega}$ as level 1 branches, make a tree T s.t. $\phi_T(\emptyset)=\omega^\omega$ . It would seem that this T is well founded (each $T_{n*\omega}$ ) is well-founded. However this is impossible because the set of finite sequences from $\omega$ to $\omega$ is countable.

Is it the case that all of the infinite branches of this tree are undefinable? Am I missing something? Is it not the case that supremum $\{\omega^n|n\in\omega\}$ is $\omega^\omega$ ?

Answer by Grace for Trees on $\omega$

2012-07-04T05:47:16Z

You are considering the ordinal arithmetic. Then $\omega^{\omega}$ is the limit of $\omega^{n}$'s. So it is a countable ordinal.

Trees on $\omega$ - MathOverflow

Trees on $\omega$

Answer by Grace for Trees on $\omega$