# Functions from ordinals to ordinals

I'm trying to solve this problem, which appears in Schimmerling's "A Course in Set Theory."

Problem. Find two functions

$$f:\omega\rightarrow\omega\cdot2$$

and

$$g:\omega\cdot2\rightarrow\omega\cdot3$$

such that $\sup\{f(\omega)\}=\omega\cdot2$ and $\sup\{g(\omega\cdot2)\}=\omega\cdot3$, but if $h=g\circ f$, then $\sup\{h(\omega)\}<\omega\cdot3$.

Setting $f(n)=n\cdot2=n+n$ for all $n<\omega$, as well as

\begin{aligned} g(m) & = m & \text{if $m<\omega$}\\ g(m) & = \omega+\omega +m & \text{otherwise} \end{aligned}

it seems that $g\circ f(n)=g(n\cdot2)=n\cdot2$ (since $n\cdot2<\omega~~\forall n<\omega$). Thus it follows that $\sup\{g\circ f(\omega)\}=\omega\cdot2<\omega\cdot3$.

So far so good. But it turns out that the next exercise requires us to show the following.

Theorem. Let $\kappa<\lambda<\mu$ be three limit ordinals and

$$f:\kappa\rightarrow\lambda$$

and

$$g:\lambda\rightarrow\mu.$$

Suppose $\sup\{f(\kappa)\}=\lambda$ and $\sup\{g(\lambda)\}=\mu$, and that $g$ is nondecreasing, i.e., if $\alpha\le\beta<\lambda$ then $g(\alpha)\le g(\beta)$. Then letting $h=g\circ f$ we must have $\sup\{h(\kappa)\}=\mu$.

It now seems that my construction for the first problem is a counterexample to the theorem to be proved in the second. Could someone explain to me the loophole in my argument? Thanks!

• If you want to talk about direct image of a set of ordinal it is better to use $f[\omega]$ or $f''\omega$. The reason is that $f(\omega)$ can be mistaken to the value of $\omega$ under the function (which is not defined, and so -- confusing). – Asaf Karagila Nov 12 '13 at 14:17
• Also, writing $\sup\{f(\omega)\}$ would be taking the supremum of the singleton $f(\omega)$. It should either be $\sup\{f(n)\mid n<\omega\}$ or $\sup f(\omega)$ (or better yet $\sup f''\omega$). – Asaf Karagila Nov 12 '13 at 14:19
• Ok, apologies for the bad notation. Indeed, I meant the supremum of the entire set, and the direct image of $\omega$ under $f$. – youngtableaux Nov 12 '13 at 14:21
• Your $f$ is no good, since doubling any finite number leaves you with a finite number. So $\sup\{f(n): n < \omega\} = \omega$; you require it to be $\omega\cdot 2$. Further your $g$ doesn't work, since, for example $g(\omega + 1) = \omega + \omega + \omega + 1 = 3\omega+1$, which is not in the required range. – HTFB Nov 12 '13 at 14:36

The main problem is that your first example doesn’t work: $f[\omega]$ isn’t cofinal in $\omega\cdot 2$. In fact $\sup f[\omega]=\omega$. Note that the theorem requires $g$ to be non-decreasing; this suggests that in the first problem you should look for functions $f$ and $g$ such that $g$ is not non-decreasing. Here’s one possibility: let $f(n)=\omega+n$, and then let
$$g(\alpha)=\begin{cases} \omega\cdot 2+\alpha,&\text{if }\alpha<\omega\\ 0,&\text{if }\alpha\ge\omega\;. \end{cases}$$
If you want to make $g$ injective, let $g(\omega+n)=n$ for $n\in\omega$.