Trees on $\omega$ - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T13:10:52Z http://mathoverflow.net/feeds/question/101282 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/101282/trees-on-omega Trees on $\omega$ alfred 2012-07-04T04:53:55Z 2012-07-04T05:47:16Z <p>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 <code>$\phi_T(u) = supremum\{\phi(u$^(x))+1|u^(x)$\in T\}$</code>, <code>$\phi(\emptyset)=\omega^\omega$</code>. Because $\phi$ is onto <code>$\omega^\omega$</code> we get that T is of size continuum, which is impossible. </p> <p>The construction proceeds as follows: </p> <p>1) Create a tree <code>$T_0$</code> s.t. <code>$\phi_{T_0}(\emptyset)=\omega$</code> by having a branch of length n for all $n\in\omega$ Note <code>$T_0$</code> is well founded. </p> <p>2) Create a tree <code>$T_1$</code> s.t. <code>$\phi_{T_1}(\emptyset)=\omega+\omega$</code> by having level 1 branches <code>$u_i$</code> s.t. <code>$\phi(u_i)=\omega+i$</code>. Note <code>$T_1$</code> is well_founded (each <code>$T[u_i]=\{v\in T|$</code> v is compatible with <code>$U_i\}$</code> is well founded.) </p> <p>3) Similarly create trees <code>$T_n$</code> s.t. `$\phi_{T_n}(\emptyset)=n*\omega$ </p> <p>4) Create a tree <code>$T_\omega$</code> with level 1 branches <code>$T_n$</code> so that <code>$\phi_{T_\omega}(\emptyset)=\omega*\omega$</code>. Note that because each of the branches is well founded. </p> <p>5) Similarly create trees <code>$T_{n*\omega}$</code> s.t. <code>$\phi_{T_{n*\omega}}(\emptyset)=\omega^n$</code> </p> <p>6) Finally, using the <code>$T_{n*\omega}$</code> as level 1 branches, make a tree T s.t. <code>$\phi_T(\emptyset)=\omega^\omega$</code>. It would seem that this T is well founded (each <code>$T_{n*\omega}$</code>) is well-founded. However this is impossible because the set of finite sequences from $\omega$ to $\omega$ is countable. </p> <p>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<code>$\{\omega^n|n\in\omega\}$</code> is <code>$\omega^\omega$</code>?</p> http://mathoverflow.net/questions/101282/trees-on-omega/101287#101287 Answer by Grace for Trees on $\omega$ Grace 2012-07-04T05:47:16Z 2012-07-04T05:47:16Z <p>You are considering the ordinal arithmetic. Then $\omega^{\omega}$ is the limit of $\omega^{n}$'s. So it is a countable ordinal.</p>