# Fixed points and cardinal exponentiation

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.

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.

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

• @Stefan: It is certainly provable that $\aleph_\omega$ is not a fixed point. – Asaf Karagila May 29 '16 at 14:53
• (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! :-)) – Asaf Karagila May 29 '16 at 14:57

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.