Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am doing the following exercise from Just/Weese:

enter image description here

where $F$ is defined as follows:

enter image description here


(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!

share|improve this question
add comment

1 Answer

up vote 1 down vote accepted

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.)

share|improve this answer
    
For (e) $\implies$: If $\alpha = \delta + 1$ then $\omega_\alpha = F(\alpha) = F(\delta + 1) = F^+(\delta)$ is a successor cardinal. –  Matt N. 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) –  Matt N. Dec 12 '12 at 12:29
1  
@Matt: Your new proof of (e) seems fine to me! –  Arthur Fischer Dec 12 '12 at 20:36
add comment

Your Answer

 
discard

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.