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

  • 2
    $\begingroup$ 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. $\endgroup$ – 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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.