# Proving the class of countable ordinals is closed under ordinal exponentiation in ZF

I managed to prove that given the axiom of choice, the class (or is it a set?) of countable ordinals is closed under exponentiation, since the axiom of choice implies that the countable union of countable sets is countable (although this is not true in ZF).

I managed to prove that $\omega^\omega$ is countable in ZF by comparing it to the set of polynomials in $\omega$ with natural coefficients, but am struggling to extend it to more general ordinals.

Any help would be most welcome. Thank you in advance

You're right that in ZF, the countable union of countable sets need not be countable. However, the countable union of counted sets is always countable: that is, if I have countably many sets $A_i$, and a set of injections $f_i: A_i\rightarrow \omega$, then $\bigcup A_i$ is indeed countable. The weird examples come when I have (in some model of ZF) a countable collection $\{A_i\}$ of countable sets, but I don't have a set of injections of the $A_i$s into $\omega$.

So the goal is to make $\alpha^\beta$ explicitly counted. Specifically:

Can you find an injection from $\alpha^\beta$ to $\omega$, given injections $f: \alpha\rightarrow\omega$ and $g:\beta\rightarrow\omega$?

HINT: it will be easier to do this if you work with the "explicit" description of ordinal exponentiation - that $\alpha^\beta$ is the set of all maps $\beta\rightarrow\alpha$ which are nonzero at only finitely many values, ordered lexicographically . . .

Note that the "given $f$ and $g$" can't be done away with: it is consistent with ZF that there is no map $H$ from $\{$countable ordinals$\}$ such that $H(\alpha)$ is an injection from $\alpha$ into $\omega$, that is, there's no "canonical" way to count each countable ordinal. (Indeed, such an $H$ existing implies that the union of countably many countable ordinals is countable - that is, that $\omega_1$ is regular!)

• I didn't know about the "explicit" description before this - if I am reading it right (two maps are compared starting from the least significant ordinal), it doesn't seem like the lexicograhical ordering makes use of $f$ or $g$. Could you go into more detail here? – HappyFeet Apr 26 '16 at 0:19
• @HappyFeet The lexicographic ordering itself doesn't make use of $f$ or $g$. However, it's also not what you want - you want a bijection between $\alpha^\beta$ and $\omega$! The point is to combine $f$ and $g$ with this explicit description. – Noah Schweber Apr 26 '16 at 0:27
• Would it go something like this: we can identify $\alpha^\beta$ with the set of all finite partial maps $\beta \rightarrow \alpha$ and thus with all finite sequences in $\beta \times \alpha$, and using $f$ and $g$, with the set of all finite sequences in $\omega \times \omega$. Since the set of finite sequences in $\omega \times \omega$ is countable, we are done. – HappyFeet Apr 26 '16 at 9:00

Here is a terribly indirect of proving this.

Supoose $\alpha, \beta$ are countable ordinals. Therefore there is a function $f$ with domain $\omega$, such that the even integers are in bijection with $\alpha$ (using $f$) and the odd numbers with $\beta$. In $L[f]$ we have that:

1. $f$ is an element, so $\alpha$ $\beta$ are countable.
2. $\sf ZFC$ holds.
3. Ordinals and their arithmetic is the same as in $V$. It is easy to prove for addition, then use induction to get multiplication and exponentiation.

Therefore $\alpha^\beta$ is countable in $L[f]$, so the witness for countability lies there, and therefore in $V$.

• The OP already knows that ZFC proves this. That is how the question begins. – Asaf Karagila Apr 26 '16 at 6:00
• Oops, missed that. (Although of course to use this the OP needs to show that $L[f]$ always satisfies ZFC . . . :P) – Noah Schweber Apr 26 '16 at 6:01
• I said terribly indirect, and I meant it! – Asaf Karagila Apr 26 '16 at 6:02
• (Also relevant, and shameless self promoting, arxiv.org/abs/1402.3048) – Asaf Karagila Apr 26 '16 at 6:06
• Dammit, I had stuff I was supposed to do tomorrow . . . – Noah Schweber Apr 26 '16 at 6:07

The following argument is overkill and probably not helpful to you. However, I thought I'd add it anyways - just for the heck of it.

It's easy to verify that ordinal arithmetic (i.e. addition, multiplication, exponentiation) is absolute between transitive models of $\operatorname{ZF}^{-}$. In particular, for any $\alpha, \beta < \omega_{1}$, we may calculate $\alpha^\beta$ in $L_{\omega_1}$ and obtain the correct value. Since $L_{\omega_1} \cap \operatorname{On}= \omega_1$, this implies that $\alpha^\beta$ is countable.

• How exactly do you show that ordinal exponentiation is absolute between transitive models of $ZF^-$ without already answering the question? – Noah Schweber Apr 25 '16 at 19:35
• @NoahSchweber By proving that the recursive definition is absolute, which is quite trivial. – Stefan Mesken Apr 25 '16 at 20:34
• That's not enough - you need to also show that it doesn't move you outside of a transitive model of $ZF^-$. This is implicit in the statement "we may calculate $\alpha^\beta$ in $L_{\omega_1}$." But showing this is essentially solving (a more general version of) the problem. – Noah Schweber Apr 25 '16 at 20:46
• @NoahSchweber No, you don't. The recursion theorem is provable in $\operatorname{ZF}^{-}$. In particular, for any ordinals $\alpha, \beta \in L_{\omega_1}$ we can prove that there is some $\gamma$ such that $L_{\omega_{1}} \models \alpha^\beta = \gamma$. However, since this recursion is absolut between transitive models of $\operatorname{ZF}^{-}$, $\gamma$ is actually $\alpha^\beta$ (from $V$'s point of view). In particular, since $L_{\omega_{1}}$ only contains countable ordinals, it follows that $\alpha^\beta$ is countable. – Stefan Mesken Apr 25 '16 at 20:50
• Why is the recursion theorem provable in $ZF^-$? It is, of course, but to actually prove it in $ZF^-$ you need to do . . . about the same amount of work as solving the problem! Your overkill solution relies on doing about the same amount of work, under the hood. – Noah Schweber Apr 25 '16 at 21:26