Trees on $\omega$

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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
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 at 5:41

1 Answer

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

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 13, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9261390566825867, "perplexity_flag": "middle"}