Injection $ \bigcup_{\beta < \gamma} \alpha^\beta \to \alpha^\gamma$

ordinalsset-theory

Let $\alpha$ be any ordinal and $\gamma$ be a non-zero limit ordinal. Is it true that

$$\left|\bigcup_{\beta < \gamma} \alpha^\beta\right|\leq |\alpha^\gamma|$$

where $\alpha^\beta$ is the set of functions $\beta \to \alpha$, similarly for $\alpha^\gamma$.

I tried to define

$$(f: \beta \to \alpha) \mapsto \left(\gamma \to \alpha: \eta \mapsto \begin{cases}f(\eta)\quad \eta \in \beta \\0 \quad \eta \notin \beta \end{cases}\right)$$

but this does not seem to be an injection.

This question popped up in an exercise that I'm making where I have to show that $|\alpha^\beta| \leq |\alpha|^{|\beta|}$ (now $\alpha^\beta$ to be interpreted as ordinal exponentiation on the left and right $|\alpha|^{|\beta|}$ is cardinal exponentiation) and I proceeded by transfinite induction, and this is the limit step in my induction proof. So I assumed that

$$\forall \beta < \gamma: |\alpha^\beta| \leq |\alpha|^{|\gamma|}$$

and I want to prove that

$$|\alpha^\gamma|\leq |\alpha|^{|\gamma|}$$

So I did

$$|\alpha^\gamma| = \left|\bigcup_{\beta < \gamma} \alpha^\beta\right| \leq \sum_{\beta < \gamma}|\alpha^\beta| \leq \sum_{\beta < \gamma} |\alpha|^{|\beta|}$$

and I would like to see that this last sum becomes smaller than $|\alpha|^{|\gamma|}$ (interpreted as cardinal exponentiation).

Best Answer

First note, for $\alpha<2$ this is false. So we assume $2\leq\alpha$.

In the case that $\gamma$ is finite, this is either finite combinatorics (if $\alpha$ is finite), or all the cardinals involved are simply $|\alpha|$ and we're done.

In the case that $\gamma$ is infinite, note that $|\gamma|=|\gamma\times\gamma|$, so now you code all the non-zero maps to $F(x,y)$ being $f(y)$ when $x=\beta$, and $0$ otherwise (including when $y\geq\beta$); and for the constant $0$ map $\beta\to\alpha$, just map it to the function which is constant $1$ on $x=\beta$.

In either case, we can read off $\beta$ and $f$.

Now, to your actual question, you can prove (and this is perhaps a bit trickier, and where transfinite recursion comes into play), that $\alpha^\beta$, the ordinal exponentiation, can be defined as a certain order type on functions $\beta\to\alpha$ which are decreasing and admit only finitely many non-zero values. This is true even without the restriction $\alpha\geq 2$.

Now the result is trivial.

Also, note that if $\alpha$ or $\gamma$ are infinite, and $\alpha\geq 2$, then the ordinal exponentiation $\alpha^\gamma$ has cardinality $\max\{|\alpha|,|\gamma|\}$. To prove this, note that:

  1. If $\gamma$ is finite, this is a trivial consequence of cardinal arithmetic (as $\alpha$ now has to be infinite).

  2. If $\gamma$ is infinite, we prove by induction, starting from $\omega$.

    • Case 1: $\alpha$ is finite, $\alpha^\omega=\omega$, as ordinal exponentiation that is, so we are fine.

    • Case 2: Suppose that $|\alpha^\beta|=\max\{|\alpha|,|\beta|\}$ for all infinite $\beta<\gamma$.

      1. If $\gamma=\beta+1$, then $\alpha^\gamma = \alpha^\beta \cdot\alpha$, so $|\alpha^\gamma| = |\alpha^\beta| \cdot |\alpha|$, so the concluseion follows.

      2. If $\gamma$ is a limit, then $\alpha^\gamma=\sup\{\alpha^\beta\mid\beta<\gamma\}$, and therefore $|\alpha^\gamma|=|\gamma|\cdot\sup\{|\alpha^\beta|\mid\beta<\gamma\}$, and by the induction hypothesis, this is just $|\gamma|\cdot\sup\{\max\{|\alpha|,|\beta|\}\mid\beta<\gamma\}$, which translates to $|\gamma|\cdot|\alpha|\cdot\sup\{|\beta|\mid\beta<\gamma\}$, which is equal to $|\gamma|\cdot|\alpha|$.

Related Question