2
$\begingroup$

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!

$\endgroup$
  • $\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$ – Ramiro de la Vega Feb 4 '13 at 18:05
5
$\begingroup$

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

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.