4
$\begingroup$

Let the function $F: On \rightarrow On$ be defined by the following recursion:

$F(0) = \aleph_0$

$F(\alpha+1) = 2^{F(\alpha)}$ (cardinal exponentiation)

$F(\lambda) = \sup\{F(\alpha):\alpha \in \lambda\}$ for $\lambda$ a limit ordinal

Prove that there is a fixed point for $F$, i.e. an ordinal $\kappa$ with $F(\kappa) = \kappa$.

Are such fixed points always cardinals?

Thoughts: So I can see that such a fixed point is going to have to be for a limit ordinal, since the function is strictly increasing for successor ordinals.

$F(\lambda) = \sup\{\aleph_{\alpha}: \alpha \in \lambda\}$

I feel as if $\aleph_{\omega}$ might be a fixed point and suspect that any fixed points have to be cardinals, but I don’t have a justification for either.

I’m not sure how to go about proving a fixed point exists and whether it has to always be a cardinal.

$\endgroup$
6
$\begingroup$

What you have defined is in fact the $\beth$ function.

It is a continuous function, namely, it is increasing and the limit is evaluated as the limit of previous results. Therefore there is a proper class of fixed points. The fact that cardinal exponentiation returns a cardinal, and the supremum of cardinals is a cardinal ensures that such fixed points will necessarily be cardinals.

$\aleph_\omega$ is never a fixed point, though. Because even if $\aleph_\omega$ is a strong limit (namely, $2^{\aleph_n}<\aleph_\omega$ for all $n<\omega$), it is not the case that $\aleph_\omega=F(\omega_\omega)$. The first fixed point, with---and certainly without---assuming some relatively tame continuum function is going to be unfathomably larger than $\aleph_\omega$. How large is it going to be? Well, just think about it. It will be an ordinal which satisfies $\alpha=F(\alpha)$. It will have $\alpha$ cardinals which are strictly smaller than itself. $\aleph_\omega$ has only $\omega$ (well, $\omega+\omega$ if you count the finite cardinals).

There is no way to describe it "nicely" from below in any reasonable way.

$\endgroup$
4
$\begingroup$

I think you'd need the Generalised Continuum Hypothesis to prove that $\aleph_\omega$ is a fixed point for $F$, though I'm willing to be corrected by people more knowledgeable than me.

To show that all such fixed points are cardinals, suppose $\gamma$ is a fixed point and not a cardinal. As you correctly point out, $\gamma$ must be a limit ordinal, so we have $$\gamma = F(\gamma) = \sup \{F(\alpha): \alpha \in \gamma \}$$ Thus in particular, for any $\alpha \in \gamma$, $\alpha + 1 \in \gamma$ (as $\gamma$ is a limit) so $F(\alpha+1) = 2^{\alpha + 1} \in \gamma$. Since $\gamma$ is not a cardinal, we can find $\beta \in \gamma$ such that $\beta \cong \gamma$. Then $2^{\beta+1} \in \gamma$, a contradiction as ordinals do not contain sets larger than themselves.

Edit: I misread the question; I thought $F(0) = 0$. My mistake. I've removed my erroneous answer to the first part...

$\endgroup$
  • 2
    $\begingroup$ @Stefan: It is certainly provable that $\aleph_\omega$ is not a fixed point. $\endgroup$ – Asaf Karagila May 29 '16 at 14:53
  • 1
    $\begingroup$ (Or, in other words, you will need to assume that $0=1$ in order to prove that $\aleph_\omega$ is a fixed point; but you'd still be able to prove that it's not! :-)) $\endgroup$ – Asaf Karagila May 29 '16 at 14:57
3
$\begingroup$

This is a consequence of a very useful lemma whose general proof is almost as simple as providing a fixed point in this special case.

Let's say that a function $F \colon \operatorname{On} \to \operatorname{On}$ is normal iff it is strictly increasing (i.e. $\alpha < \beta$ implies $F(\alpha) < F(\beta)$) and continuous (i.e. $F(\lambda) = \sup_{\alpha < \lambda} F(\alpha)$ for all limit ordinals $\lambda$).

The 'Normal Function Lemma' states: Let $F \colon \operatorname{On} \to \operatorname{On}$ be a normal function. Then the class $F' := \{ \alpha \in \operatorname{On} \mid F(\alpha) = \alpha \}$ is closed (i.e. if $(\alpha_{\xi} \mid \xi < \theta)$ is a strictly increasing sequence of $F$-fixed points, then $\alpha := \sup_{\xi < \theta} \alpha_{\xi}$ is an $F$-fixed point) and unbounded (i.e. for all $\alpha \in \operatorname{On}$ there is some ordinal $\alpha < \beta$ such that $F(\beta) = \beta$). Moreover, for any regular ordinal (recall that regular ordinals are cardinals) $\omega \le \lambda$ there are arbitrarily large fixed points of $F$ of cofinality $\lambda$.

Proof. If $(\alpha_{\xi} \mid \xi < \theta)$ is a strictly increasing sequence in $F'$, then $$F(\sup_{\xi < \theta} \alpha_{\xi}) = \sup_{\xi < \theta} F(\alpha_{\xi}) = \sup_{\xi < \theta} \alpha_{\xi}.$$

It thus suffices to prove that for any regular cardinal $\lambda \geq \omega$ and any $\alpha_{0} \in \operatorname{On}$ there is some $\alpha_{0} < \alpha$ such that $F(\alpha) = \alpha$ and $\alpha$ has cofinality $\lambda$: Recursively construct a sequence $(\alpha_{\xi} \mid \xi < \lambda)$ as follows. $\alpha_{0}$ is as above and given $\alpha_{\xi}$, we let $\alpha_{\xi+1} := F(\alpha_{\xi})$. If $\theta < \lambda$ is a limit ordinal and $(\alpha_{\xi} \mid \xi < \theta)$ has already been constructed, let $\alpha_{\theta} := \sup_{\xi < \theta} \alpha_{\xi}$. Finally, let $\alpha := \sup_{\xi < \lambda} \alpha_{\xi}$. Since $(\alpha_{\xi} \mid \xi < \lambda)$ is strictly increasing, we have that $\operatorname{cf}(\alpha) = \operatorname{cf}(\lambda) = \lambda$ and furthermore, by the construction of $(\alpha_{\xi} \mid \xi < \lambda)$, $$ \begin{eqnarray*} F(\alpha) &= \sup_{\beta < \alpha} F(\beta) \\ &= \sup_{\xi < \lambda} F(\alpha_{\xi}) \\ &= \sup_{\xi < \lambda} \alpha_{\xi +1} \\ &= \alpha. \end{eqnarray*} $$ Since $\alpha_{0} < \alpha_{1} < \alpha$, the claim follows. QED

In your case, the range of $F$ constists only of cardinals (which is trivial for $F(\alpha +1)$ and follows for $F(\lambda)$, $\lambda$ limit, because limits of cardinals are cardinals). Thus, in your case, any fixed point is a cardinal. This does not hold for general normal functions.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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