# Trees on $\omega$

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$?

• You are confusing ordinal and cardinal exponentiation. The supremum of the ordinals $\omega^n$ is a countable ordinal, $\omega^\omega$ in the sense of ordinal exponentiation. Unfortunately, the same notation is sometimes used for cardinal exponentiation, and the cardinal exponential $\omega^\omega$ has the cardinality of the continuum. – Andreas Blass Jul 4 '12 at 5:41

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