2
$\begingroup$

Let $\alpha$ be a limit ordinal, such that $\big | \alpha \big | = \omega$. Prove that there is a strictly increasing function $f: \omega \to \alpha$ such that for all $\zeta < \alpha$ there is $n \in \omega$ with $\zeta < f(n)$.

$\textbf{My Attempt:}$ I am trying to construct maybe a recursive function. Since both sets are well-ordered and countable there exists some enumeration on the elements, $\{0,1,2, \dots\}$ and $\{\zeta_0,\zeta_1, \dots\}$

$f(0)=\alpha_{\in_{\zeta_0}}$, the initial segment up to $\zeta_0$

$f(1)=\alpha{\in_{\zeta_1}}$, the initial segment up to $\zeta_1$.

$\vdots$

$f(n+1)=\alpha{\in_{\zeta_n}}$, the initial segment up to $\zeta_n$

Then $f(0) < f(1)$ because $\alpha_{\in_{\zeta_0}} \in \alpha_{\in_{\zeta_1}}$ so the function is strictly increasing.

And for every $\zeta_i \in \alpha$, there exists $n \in \omega$ such that $f(n)=\alpha_{\in_{\zeta_{(i+1)}}}$ and so $\zeta \le f(n)$.

I am not sure if this is correct. Any advice?

$\endgroup$
  • $\begingroup$ I don't quite follow your notation. What is $\alpha_{\in_{\zeta_0}}$? Do you mean $f(0) = \alpha \cap \zeta_0$? $\endgroup$ – Ben Millwood Mar 23 '14 at 15:58
  • $\begingroup$ Yes. We have learned that notation to just represent an initial segement. $\endgroup$ – user7090 Mar 23 '14 at 16:02
1
$\begingroup$

HINT: Write the ordinal $\alpha$ as $\{\gamma_n\mid n\in\omega\}$. Now by recursion pick larger and larger ordinals by going over this enumeration, and show that the sequence that you have chosen is the intended function.

$\endgroup$
1
$\begingroup$

To complement Asaf's correct approach, I should point out your approach is incorrect. In particular, it's not necessarily the case that $\zeta_0 < \zeta_1$, so the initial segment up to $\zeta_0$ may not be smaller than the initial segment up to $\zeta_1$.

Think about it like this: suppose $\alpha > \omega$. Then $\omega$ has got to appear as an output of $f$, and only finitely many things can have appeared before it. Therefore, whatever $f$ you come up with to answer this question cannot be surjective (except where $\alpha = \omega$).

$\endgroup$

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.