I'm asking a question following the reading of Set Theory from Jech (page 126).

For the record, a $\kappa$-sequence of functions $\langle f_\alpha : \alpha < \kappa\rangle$ is called a $\kappa$-scale if $f_\beta < f_\alpha$ whenever $\beta < \alpha$, and if for every $g\colon \omega \rightarrow \omega$ there exists an $\alpha$ such that $g < f_\alpha$.

Suppose that $\aleph_1 = 2^{\aleph_0}$. A scale $\langle f_\alpha : \alpha < \omega_1 \rangle$ is constructed by transfinite induction to $\omega_1$:

Let $\{g_\alpha : \alpha < \omega_1\}$ enumerate all functions from $\omega$ to $\omega$. At stage $\alpha$, we construct, by diagonalization, a function $f_\alpha$ such that for all $\beta < \alpha$, $f_\alpha > f_\beta$ and $f_\alpha > g_\beta$. Then $\langle f_\alpha : \alpha < \omega_1 \rangle$ is an $\omega_1$-scale.

I don't see how to manage the transfinite induction in order to avoid for limit ordinals that $f_\alpha$ becomes infinite.

Thanks for your support!

  • $\begingroup$ At any step (limit or not) you have only countably many functions to worry about so you can list them in order type $\omega$ and then construct the next $f$ above all of them. $\endgroup$ Feb 4, 2013 at 18:05

1 Answer 1


The inequality relation between functions $\omega\to\omega$ that is written $f<g$ in the question must mean that $f$ is eventually (not everywhere) below $g$, i.e., that $f(n)<g(n)$ holds for all sufficiently large $n$. (If it meant "for all $n$, then the induction would indeed break down at the first limit ordinal.) Now to construct an upper bound for countably many functions $f_\alpha$, first re-enumerate them in an $\omega$-sequence, say as $g_n$, and then use the function $k\mapsto 1+\max\{g_n(k):n<k\}$.

By the way, the usual notation for the "eventually $<$" relation is not $<$ but $<^*$.


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.