# Proving properties of enumeration of infinite cardinals

I am doing the following exercise from Just/Weese: where $F$ is defined as follows: (a) I'm not sure whether the following passes as "convince myself": Apparently $F$ is defined for all ordinals hence its domain is $\mathbf{ON}$. It is similarly apparent that the values of $F$ are infinite cardinals. Also, $F$ is well-defined: assume $\alpha = \alpha'$. Then it immediately follows from (i) -(iii) that $F(\alpha) = F(\alpha')$. Finally, assume $G$ is another enumeration of the infinite cardinals. Let $\alpha$ be the smallest ordinal such that $F(\alpha) \neq G(\alpha)$. It is clear that $\alpha$ must be greater than zero. It is also clear that if $F,G$ agree on all $\beta < \alpha$ then they also have to agree for $\alpha$. Hence $F=G$ so that $F$ is unique.

(b) By transfinite induction. If $\alpha = 0$ then it immediately follows from (i)-(iii) that $F(\beta) > F(0) = \omega$ for all $\beta > 0$.

Now assume that $F(\beta) < F(\beta')$ for all $\beta, \beta' < \alpha$. We want to show that $\beta < \alpha$ implies that $F(\beta) < F(\alpha)$. If $\alpha$ is a successor ordinal then $F(\alpha) = F(\delta + 1) = F^+(\delta)$ where $\delta < \alpha$. Since there are no ordinals between $\delta$ and $\delta + 1 = \alpha$ we must have $\beta \le \delta$ and hence by assumption $F(\beta) \leq F(\delta)$. Hence $F(\beta) \leq F(\delta) < F^+(\delta) = F(\alpha)$.

This is the bit I am not so sure of:

If $\alpha$ is a limit ordinal then $F(\alpha) = \bigcup_{\gamma < \alpha} F(\gamma)$. Since $\beta < \alpha$ we then have $F(\beta) \subseteq F(\alpha)$ and hence $F(\beta) \le F(\alpha)$. Assume $F(\alpha) = F(\beta)$. Then $F(\beta) = \bigcup_{\gamma \le \beta} F(\gamma) < \bigcup_{\gamma < \alpha} F(\gamma) = F(\beta)$ which would be a contradiction.

(c) By transfinite induction. The claim is clearly true for $\alpha = 0$. Assume for all $\beta < \alpha$ we have $\omega_\beta \geq \beta$. We want to show that $\omega_\alpha \ge \alpha$. If $\alpha$ is a successor ordinal then $\alpha = \delta + 1$ for some $\delta \in \mathbf{ON}$. Then by assumption, $\delta \leq \omega_\delta$. Also, $\omega_\alpha = F(\alpha) = F(\delta + 1) = F(\delta)^+ = \omega_\delta^+ > \omega_\delta \ge \delta$ so that $\alpha = \delta + 1 \le \omega_\delta^+ = \omega_\alpha$.

If $\alpha$ is a limit ordinal, $\omega_\alpha = F(\alpha) = \bigcup_{\beta < \alpha} F(\beta) = \bigcup_{\beta < \alpha} \omega_\beta$. Since there are no finite limit ordinals, $\alpha = \omega_\beta$ for some $\beta < \alpha$ and the claim follows.

(d) We claim that the range of $F$ is the class of all infinite cardinals. It immediately follows from the definition of $F$ that the range of $F$ is a subset of the class of all infinite cardinals. It remains to be shown that $F$ is surjective. To this end, let $\kappa$ be an infinite cardinal. We proceed by transfinite induction. Assume that $\lambda \in \mathrm{range}(F)$ for all $\lambda < \kappa$. If $\kappa$ is a successor cardinal then $\kappa = \lambda^+$ for some $\lambda$ in the range of $F$ so that $\kappa = F(\alpha)^+ = F(\alpha+1)$. If $\kappa$ is a limit cardinal then $\kappa = \bigcup_{\gamma < \kappa} \gamma$ and since all $\gamma$ are in the range of $F$, $\kappa = \bigcup_{F(\beta) < \kappa} F(\beta)$. How do I finish from here?

(e) $\implies$: Let $F(\alpha) = \omega_\alpha$ be a limit cardinal. Then by the definition of $F$, $F(\alpha) = \bigcup_{\beta < \alpha}F(\beta)$ and $\alpha$ is a limit ordinal.

$\Longleftarrow$: Let $\alpha$ be a limit ordinal. Then (iii) applies so that $F(\alpha)$ is a limit caridnal.

Is this correct? And will you help me fill in the missing bits? Thank you for your help!

A few notes:

• In the proof of the limit case in (b), you have probably seen that if $A$ is any set of cardinals with no greatest element, then $\bigcup A$ is the smallest cardinal exceeding each cardinal in $A$. (Just-Weese probably mentioned something like this at about the point of some prior question you had.) If $\alpha$ is a limit cardinal, and $F$ is known to be strictly increasing below $\alpha$, then $A = \{ F(\beta) : \beta < \alpha \}$ will be a set of cardinals with no greatest element.

• For the limit case of (c), you seem to imply that all limit ordinals are cardinals. This is clearly not true: Consider $\omega + \omega$. However, if $\alpha$ is a limit ordinal, then, by the induction hypothesis, $\alpha = \bigcup_{\beta < \alpha} \beta \leq \bigcup_{\beta < \alpha} F(\beta) = F(\alpha)$.

• For (d) and (e) note the following. If $\kappa$ is a limit cardinal (and every infinite cardinal less than $\kappa$ is in the range of $F$), then for each $\lambda < \kappa$ there is a $\alpha_\lambda$ such that $F ( \alpha_\lambda ) = \lambda$. By (b) it follows that if $\lambda < \mu < \kappa$, then $\alpha_\lambda < \alpha_\mu$, and so $A = \{ \alpha_\lambda : \lambda < \kappa \}$ is a set of ordinals with no maximum. Consider $\alpha = \sup A$. What is $F(\alpha)$?

• In (d) a well-foundedness argument might be a bit cleaner. Suppose that the range of $F$ is not all infinite cardinals. Then there is a least cardinal $\kappa$ which is not in the range. Handle the cases $\kappa$ is limit, $\kappa$ is successor separately.

• In the $\Rightarrow$ direction of (e), you do not seem to have done anything. Perhaps show the contrapositive instead (should be very easy). In the $\Leftarrow$ direction, how do you know that $\bigcup_{\beta < \alpha} F(\beta)$ is a limit cardinal? (The reasoning already appears somewhere above.)

• For (e) $\implies$: If $\alpha = \delta + 1$ then $\omega_\alpha = F(\alpha) = F(\delta + 1) = F^+(\delta)$ is a successor cardinal. – Rudy the Reindeer Dec 12 '12 at 12:27
• For (e) $\Longleftarrow$: $\bigcup_{\beta < \alpha}F(\beta)$ is a limit cardinal because the set $\{F(\beta) \mid \beta < \alpha \}$ where $\alpha$ is a limit ordinal is a set of cardinals such that for every element $a$ in it there is an element $b$ in it with $a < b$ (by (b)). Then by a previous theorem the union over this set is a limit cardinal. (Thm 3, p 174) – Rudy the Reindeer Dec 12 '12 at 12:29
• @Matt: Your new proof of (e) seems fine to me! – user642796 Dec 12 '12 at 20:36