MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
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. – Ramiro de la Vega Feb 4 '13 at 18:05
up vote 5 down vote accepted

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 $<^*$.

share|cite|improve this answer

Your Answer


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.