Preservation of cardinality under ordinal exponentiation.

Question

In Kenneth Kunen's The Foundations of Mathematics, he presents the following exercise and hint.

Exercise I.11.34 Ordinal arithmetic doesn't raise cardinality. That is, assume that $\alpha$, $\beta$ are ordinals with $2 \leq \text{min}(\alpha,\beta)$ and $\omega \leq \text{max}(\alpha,\beta)$. Then prove that $|\alpha + \beta| = |\alpha \cdot \beta| = |\alpha^\beta| = \text{max}(|\alpha|,|\beta|)$.

Hint. For $\alpha + \beta$ and $\alpha \cdot \beta$ this is easy from Theorem I.11.32 and the definition of $+$ and $\cdot$. The proof is slightly tricky for exponentiation, since the natural proof by induction on $\beta$ seems to use the Axiom of Choice (AC). Here, we take the recursive computation in Table I.1 to be the definition of $\alpha^\beta$. Now say we want to prove by induction on $\beta$ that $\alpha^\beta$ is countable whenever $\alpha, \beta$ are countable. If $\beta$ is a limit, we have $\alpha^\beta = \text{sup}_{\xi < \beta}(\alpha^\xi) = \bigcup_{\xi < \beta} (\alpha^\xi)$ which (applying induction) is a countable union of countable sets. But the well-known fact that a countable union of countable sets is countable uses AC. To avoid AC first fix a $\delta < \omega_1$ and then fix an $f: \delta \xrightarrow{1-1} \omega$. Now, we may now define, for $\alpha,\beta<\delta$, an injection from $\alpha^\beta$ into $\omega$; the definition uses $f$, and is done by recursion on $\beta$; the definition also uses a (fixed) injection from $\omega \times \omega$ into $\omega$.

I finished proving that $|\alpha + \beta| = |\alpha \cdot \beta| = \text{max}(|\alpha|, |\beta|)$ without issue. I'm stuck on following the hint for exponentiation. Usually I find the hints clear, but this time I'm confused. We are defining a function based off an injection from $\alpha^\beta$ into $\omega$ by recursion on $\beta$. I don't exactly follow the construction. I'm also wondering, this hint only gives the case that we are assuming that $\alpha$ and $\beta$ are countable. What about ordinals of arbitrary cardinality that satisfy the above conditions? Is it just a small modification of the argument we use for the countable case?

Answer 1

Prove this by induction on $\beta$.

1. $\alpha^2$ is $\alpha\cdot\alpha$, so you are back to multiplication.

2. $\alpha^{\gamma+1}=\alpha^\gamma\cdot\alpha$, by the induction hypothesis that's the same cardinality as $\alpha\cdot\alpha$, so we are back to multiplication again.

3. If $\beta$ is limit, then $\alpha^\beta=\sup\{\alpha^\gamma\mid \gamma<\beta\}$. Then either $\beta>\alpha$ is a cardinal, in which case $|\alpha^\gamma|<\beta$, and so $\alpha^\beta=\beta$. Or else we have a uniform way of enumerating $\alpha^\gamma$ for all $\gamma<\beta$. This means that we get an injection into $\max(\alpha,\beta)\times\beta$, so we're done.

   Or, if you don't mind using AC, just apply it judiciously to get $\max\{\alpha,\beta\}$ again.

Answer 2

Asaf's answer is good enough. Just to make this clearer, at the limit step, we define the injection $f: \alpha^\beta \to \max(\alpha,\beta)$ as follows:

$$f(x)=\Gamma(\delta,f_\delta(x)) \text{ where $\delta\in \beta$ is the smallest ordinal for which $x\in \alpha^{\delta}$ and $\Gamma$ is a paring function}.$$

This function is clearly injective (the first argument here is needed or else $f_\delta(x)$ could be equal to $f_\sigma(y)$ where $\delta\neq \sigma $ and $x\neq y$).

Answer 3

Here is a proof that follows Kunen's hint.

Let $\max\{|\alpha|,|\beta|\}=\kappa$. Fix ordinal $\delta$, s.t. $\delta>\alpha$, $\delta>\beta$ and $|\delta|=\kappa$ (e.g. $\delta=\max\{\alpha,\beta\}+1$).

Fix bijections $f\colon \delta \to \kappa$ and $\Gamma \colon \kappa \times \kappa \to \kappa$. We define injections $i_{\gamma} \colon \alpha^{\gamma} \to \kappa$ for all $\gamma \in \delta$ recursively.

1. $\gamma=0$. Define $i_0(\emptyset)=\emptyset$.
2. $\gamma=\sigma+1$. Let $h \colon \alpha^{\sigma} \cdot \alpha \to \alpha^{\sigma} \times \alpha$ be the canonical order isomorphism. $\forall \eta \in \alpha^{\gamma}$, we define $i_{\gamma}(\eta)=\Gamma(i_{\delta}(h_1(\eta)),f(h_2(\eta)))$.
3. $\gamma$ is a limit ordinal. $\forall \eta \in \alpha^{\gamma}$, let $\delta < \gamma$ be the least ordinal s.t. $\eta \in \alpha^{\delta}$, and define $i_{\gamma}(\eta) = \Gamma(i_{\sigma}(\eta),f(\sigma))$.

In particular, this gives an injection $i_{\beta}$ from $\alpha^{\beta}$ to $\kappa$, so $|\alpha^{\beta}| \leq \kappa$. It is not difficult to prove the other direction.