1
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
8
  • $\begingroup$ Thanks for the answer. My definition is $\alpha^\gamma = \bigcup_{\beta < \gamma} \alpha^\beta$ where $\gamma$ is a limit ordinal and $\alpha^\beta$ is defined by $\alpha^{\beta+1} = \alpha^\beta \alpha, \alpha^0 = 1$. $\endgroup$
    – user745578
    Mar 23 '20 at 9:17
  • $\begingroup$ I'm confused as to which of your exponents are ordinal, and which of them are cardinal exponentiation. It would be good to clarify this. $\endgroup$
    – Asaf Karagila
    Mar 23 '20 at 9:20
  • $\begingroup$ I will edit my question. $\endgroup$
    – user745578
    Mar 23 '20 at 9:26
  • $\begingroup$ I added more details and context. Please do let know if something is still unclear. $\endgroup$
    – user745578
    Mar 23 '20 at 9:31
  • $\begingroup$ Your definition is confusing, still. Cardinal exponentiation (that is, the cardinal of the set of all functions from $\gamma$ to $\alpha$) is generally not continuous at limit points. So the definition as the union cannot possibly be that. You are playing far too much on the notation overload here, and it's very hard for me to say what you're asking exactly. If you switch to $\sup$ when talking about ordinals (yes, it's the same, but it is notationally clearer), it might be easier to follow. $\endgroup$
    – Asaf Karagila
    Mar 23 '20 at 9:35

Your Answer

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