Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
2  
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

1 Answer 1

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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