0
$\begingroup$

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

$\endgroup$
1
  • 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$ Jul 4, 2012 at 5:41

1 Answer 1

3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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