Basic Ordinal and Cardinal Arithmetic II

This entry is going to push our discussion of set theory a little bit further.

One of the first results of this entry will expand on the result that Ordinal addition is strictly increasing. But first, this mini-lemma.

Mini-Lemma: Something like Ordinal Subtraction

Proof

In the proof that ordinal addition is strictly increasing we defined a class of functions, \( f_{\alpha} \) for each ordinal, \( \alpha \), where \( f_{\alpha}(\beta) = \alpha \dot{+} \beta \). We showed that \( f_{\alpha} \) is strictly increasing. Therefore, there can be at most one \( \delta \), such that \( \alpha \dot{+} \delta = \beta \).

Now, we’ll show that the range of \( f_{\alpha} \) is the class of ordinals greater than or equal to \( \alpha \).

Suppose, for a contradiction, that there are some ordinals, greater than or equal to \( \alpha \) which are not in the range of \( f_{\alpha} \). Let \( \eta \) be the least such ordinal. Notice that \( f_{\alpha}(0) = \alpha \), so \( \alpha \lneq \eta \).

\( \eta \) cannot be a successor ordinal, since then \( \eta = \xi \dot{+} 1 \), and since \( \eta \) is the least ordinal not in the range of \( f_{\alpha} \) there is an ordinal, \( \sigma \), such that \( f_{\alpha}(\sigma) = \xi \). This means that

\[ \eta = f_{\alpha}(\sigma \dot{+} 1) = f_{\alpha}(\sigma) \dot{+} 1 \]

a contradiction. Thus, \( \eta \) must be a limit ordinal.

Since \( \eta \) is a limit ordinal, \( \eta = \sup\limits_{\xi < \eta} \{ \xi \} \). We want to prove that this is equal to \( \nu := \sup\limits_{\alpha \dot{+} \zeta < \eta} \{ \alpha \dot{+} \zeta \} \). Note that \( \nu = \sup\limits_{\zeta : \alpha \dot{+} \zeta < \eta} \{ \displaystyle f_{\alpha}(\zeta) \} \).

Since every element of \( \{ \alpha \dot{+} \zeta | \alpha \dot{+} \zeta < \eta \} \) is less than \( \eta \), by definition, we know that \( \nu \leq \eta \). Suppose that \( \nu \lneq \eta \). Then, since \( \eta \) is a limit ordinal, it cannot be equal to \( \nu \dot{+} 1 \), which means that \( \nu \dot{+} 1 \) is not in the range of \( f_{\alpha} \), which is impossible, since it is strictly less than \( \eta \), which we assumed was the least ordinal greater than or equal to \( \alpha \) which is not in the range of \( f_{\alpha} \). A contradiction.

QED

Note: We can think of \( \delta \) a little bit like subtracting \( \alpha \) from \( \beta \), but it’s not exactly like what you might expect from your experience with finite ordinals (i.e. the natural numbers). For example, if \( \alpha = 1 \text{ billion} \) (or any other finite ordinal, like “one googol”) and \( \beta = \omega_0 \), the least infinite ordinal, then \( \delta \) is also equal to \( \omega_0 \).

Mini-Lemma: Multiplication by a Limit Ordinal is a Limit Ordinal

Proof

Let \( \lambda \) be a limit ordinal, and \( \alpha > 0 \). Then, by the definition of ordinal multiplication by a limit ordinal, we have

$$ \alpha \times \lambda = \sup\limits_{\eta < \lambda} \{ \alpha \times \eta \} $$

Suppose, for a contradiction, that this is equal to a successor ordinal, call it \( \delta \dot{+} 1 \). Then,

$$ \delta = \max\limits_{\eta < \lambda} \{ \alpha \times \eta \} $$

which means that there is some \( \eta’ < \lambda \), such that

$$ \delta = \alpha \times \eta' $$

but since \( \lambda \) is a limit ordinal, we know that \( \lambda’ \dot{+} 1 < \lambda \), which means that

$$ \begin{align} \delta &= \max\limits_{\eta < \lambda} \{ \alpha \times \eta \} \\ &= \alpha \times \eta’ \\ &\geq \alpha \times (\eta’ \dot{+} 1) \\ &= \alpha \times \eta’ \dot{+} \alpha \\ \end{align} $$

which is impossible since \( \alpha > 0 \) and ordinal addition is strictly increasing.

QED

Corollary: Ordinal Multiplication is Strictly Increasing

Proof

Suppose \( \alpha > 0 \), and \( \beta < \gamma \). Then, there exists a unique \( \delta \), such that \( \beta \dot{+} \delta = \gamma \). Then, since Ordinal multiplication distributes on the right, we have

$$ \begin{align} \alpha \times \gamma &= \\ \alpha \times ( \beta \dot{+} \delta ) &= \\ \alpha \times \beta \dot{+} \alpha \times \delta &\gneq \alpha \times \beta \\ \end{align} $$

The last line holds, because \( \alpha \times \delta > 0 \), since \( \alpha > 0 \) and since \( \beta \lneq \gamma \) (so \( \delta > 0 \)), and (as we mentioned earlier in this entry) ordinal addition is strictly increasing.

QED

Corollary: Exponentiation by a Limit Ordinal is a Limit Ordinal

Proof

This proof is very similar to the one we gave above showing that multiplication by a limit ordinal is equal to a limit ordinal.

By the definition of exponentiation with a limit ordinal, we have

$$ \alpha^{\lambda} = \sup\limits_{\eta < \lambda} \{ \alpha^{\eta} \} $$

Suppose, for a contradiction, that this is equal to a successor ordinal. I.e.

$$ \sup\limits_{\eta < \lambda} \{ \alpha^\eta \} = \delta \dot{+} 1 $$

Then

$$ \delta = \max\limits_{\eta < \lambda} \{ \alpha^\eta \} $$

So there is an \( \eta’ < \lambda \), such that \( \delta = \alpha^{\eta’} \). But, since \( \lambda \) is a limit, \( \eta’ \dot{+} 1 < \lambda \), so we would have to have

$$ \begin{align} \delta &= \alpha^{\eta’} \\ &\geq \alpha^{\eta’ \dot{+} 1} \\ &= \alpha^{\eta’} \dot{\times} \alpha \\ \end{align} $$

which is impossible, since multiplication (on the right) is strictly increasing.

QED

Corollary: Ordinal Exponentiation Distributes

Proof

We’ll prove this by induction. Suppose the result holds for all \( \delta < \gamma \) for a given \( \beta \). Notice this works when \( \delta = 0 \), so the base case holds.

There are two cases to consider.

1. Let \( \gamma \) be a successor ordinal, then \( \gamma = \delta \dot{+} 1 \). Then, we have

$$ \begin{align} \alpha^{\beta \dot{+} \gamma} &= \alpha^{\beta \dot{+} (\delta \dot{+} 1)} \\ \text{(by def of ordinal add) } &= \alpha^{ (\beta \dot{+} \delta) \dot{+} 1 } \\ \text{(by def of ordinal exp) } &= \alpha^{ \beta \dot{+} \delta } \dot{\times} \alpha \\ \text{(by induction) } &= (\alpha^{\beta} \dot{\times} \alpha^{\delta}) \dot{\times} \alpha \\ \text{(mult is associative) } &= \alpha^{\beta} \dot{\times} (\alpha^{\delta} \dot{\times} \alpha) \\ \text{ (by def of ordinal exp) } &= \alpha^{\beta} \dot{\times} ( \alpha^{\gamma} ) \\ \end{align} $$

2. Let \( \gamma \) be a limit ordinal, then \( \gamma = \sup\limits_{\delta < \gamma} \{ \delta \} \), and, since addition of a limit ordinal equals a limit ordinal, we know that \( \alpha \dot{+} \gamma \) will be a limit ordinal. Then, by the definition of exponentiation with a limit ordinal, we have

$$ \begin{align} \alpha^{\beta \dot{+} \gamma} &= \sup\limits_{\delta < \gamma} \{ \alpha^{\beta \dot{+} \gamma }\} \\ \text{(by induction) } &= \sup\limits_{\delta < \gamma} \{ \alpha^{\beta} \dot{\times} \alpha^{\delta} \} \\ \text{(by mult of limit) } &= \alpha^{\beta} \dot{\times} \sup\limits_{\delta < \gamma} \{ \alpha^\delta \} \\ \text{(by exp of limit) } &= \alpha^{\beta} \dot{\times} \alpha^{\gamma} \\ \end{align} \\ $$

QED

Corollary: Ordinal Exponentiation is Strictly Increasing

Proof

Since \( \beta < \gamma \), by the “something like ordinal subtraction” from earlier in this post, we have a \( \delta > 0 \), such that \( \gamma = \beta \dot{+} \delta \). And, by the previous result, we know that ordinal exponentiation distributes, so we have

$$ \begin{align} \alpha^{\gamma} &= \alpha^{\beta + \delta} \\ &= \alpha^\beta \dot{\times} \alpha^{\delta} \\ \end{align} $$

and since ordinal multiplication is strictly increasing on the right, we have

$$ \alpha^{\gamma} > \alpha^{\beta} $$

since \( \alpha > 1 \) and \( \delta > 0 \) implies \( \alpha^{\delta} > 1 \).

QED

Theorem: Ordinal Division with Remainder

This should remind you of a Eucliden Domain. It’s not, though, because we don’t have negative ordinals, and addition isn’t commutative, etc…

Proof

There are two cases. For this proof and elsewhere on this site, we will not use the dot above the “\(+\)” or the “\( \times \)” symbol, even when dealing with ordinal arithmetic.

1. \( \alpha < \beta \). Then we set \( \gamma = 0 \) and \( \rho = \alpha \).

2. \( \alpha \geq \beta \).

First, consider the set

\[ E := \{ \eta | \beta \times \eta \leq \alpha \} \]

Since \( \beta > 0 \), we know that this is a set (and not a proper class), since every ordinal in the set will be less than or equal to \( \alpha \). We also know that, since \( \alpha \geq \beta \) that \( E \neq \emptyset \).

Next, consider the set

\[ D := \{ \delta | \exists \eta \in E, \beta \times \eta + \delta = \alpha \} \]

Since \( E \) is non-empty, \( D \) is also non-empty. Furthermore, since right-multiplication and addition of ordinals are strictly increasing, there is a unique \( \delta \in D \) for each \( \eta \in E \). Let’s give this mapping a name,

$$ f : E \mapsto D $$

where

$$ \beta \times \eta + f(\eta) = \alpha $$

As we mentioned earlier, \( f \) is 1 to 1. It is also onto \( D \) by construction. Thus, it is a bijection.

Now, notice that since \(D\) is a set of ordinals, it must have a unique smallest ordinal, let’s call that “\( \delta_0 \)”. Let \( \eta_0 = f^{-1}(\delta_0) \). Then, \( \eta_0 \) is the maximal element of \( E \), and so \( \delta_0 \leq \beta \). Otherwise we would have

$$ \begin{align} \beta \times (\eta_0 + 1) &= \beta \times \eta_0 + \beta \\ &\leq \beta \times \eta_0 + \delta_0 \\ &\leq \alpha \\ \end{align} $$

which means that \( \eta_0 + 1 \in E \) and \( \eta_0 \) wouldn’t be the maximal element of \(E\), a contradiction.

QED

A fairly surprising consequence of the previous few results is the following, due to Cantor.

Corollary: Cantor’s Normal Form Theorem

Proof

We’ll use induction. Notice that if \( \alpha < \omega_0 \), then \( \{ \epsilon_1 = 0 \} \), \( \{ q_1 = \alpha \} \) works, because \( \omega_0^0 = 1 \). This takes care of every finite ordinal.

Now, suppose the result holds for every ordinal \( < \alpha \).

Note: The following argument is very similar to what we used in the above in the proof of the “Ordinal Division with Remainder” Theorem. We won’t go into as much detail here.

Consider the sets

$$ \begin{align} E &:= \{ \epsilon | {\omega_0}^\epsilon \leq \alpha \} \\ D &:= \{ \delta | \exists \epsilon \in E, {\omega_0}^\epsilon \dot{+} \delta = \alpha \} \\ \end{align} $$

Since ordinal exponentiation is strictly increasing, there is a bijection between the two sets. \( D \) is a set of ordinals, so it has a smallest ordinal, \( \delta’ \) which corresponds to a unique greatest ordinal in \( E \). We’ll call that one “\( \epsilon’ \)”. Then

$$ {\omega_0}^{\epsilon’} \leq \alpha $$

and it is the greatest power of \( \omega_0 \) which is \( \leq \alpha \). Now, apply the above “Division with Remainder” Theorem, to get

$$ \alpha = {\omega_0}^{\epsilon’} \dot{\times} \gamma \dot{+} \rho $$

Notice that \( \gamma < \omega_0 \), since otherwise there would be an \( \epsilon > \epsilon’ \) such that \( {\omega_0}^\epsilon \leq \alpha \), which we showed can’t happen. We also know that

$$ \begin{align} \rho &< {\omega_0}^{\epsilon’} \\ &\leq \alpha \\ \end{align} $$

Thus, by induction we can find a finite sequence of \( q_i \)’s and \( \epsilon_i \)’s which work for it. Simply set \( \epsilon_1 = \epsilon’ \) and \( q_1 = \gamma \), then increase the index of each \( q_i \) and \( \epsilon_i \) from the result you obtained for \( \rho \).

QED

---

Next we’re going to prove a fundamental result about cardinal arithmetic. It is a generalization of Cantor’s Theorem.

Theorem: Konig’s Theorem

Recall, we defined sums and products of cardinals earlier, and although we wrote it for infinite sums and products, the definitions still work for finite sums and products.

Proof

Suppose, for a contradiction, that the result does not hold. I.e. we have

$$ \begin{align} K &:= \sum\limits_{\alpha < \beta} \kappa_{\alpha} \\ \Lambda &:= \prod\limits_{\alpha < \beta} \lambda_{\alpha} \\ |K| &\geq |\Lambda| \\ \end{align} $$

Let \( g : K \xrightarrow{\text{onto}} \Lambda \) be an onto function from \( K \) to \( \Lambda \). (We’re treating both \( K \) and \( \Lambda \) as the sets defined earlier.)

That means that \( g \) maps the disjoint union (Note the “\( \times \)” below means “Cartesian Product” and not multiplication!)

$$ K = \bigcup\limits_{\alpha < \beta} \{ \alpha \} \times \kappa_{\alpha} $$

to the set of functions

$$ \Lambda = \left \{ f : \beta \rightarrow \bigcup\limits_{\alpha < \beta} \lambda_{\alpha} | f(\alpha) \in \lambda_{\alpha} \right \} $$

So, now we can consider, for each \( \alpha \), the set

$$ P_{\alpha} := \{ g(x)(\alpha) | x \in \{ \alpha \} \times \kappa_{\alpha} \} $$

Let’s take a moment to think about what this set is. Each \( g(x) \), for \( x \in K \) is a function in \( \Lambda \). So \( P_{\alpha} \) is the set of all of the values taken by the functions \( g \) sends the elements of the set \( \{ \alpha \} \times \kappa_{\alpha} \) (which is a subset of \( K \), the domain of \( g \)) at \( \alpha \). (Just look back at the definitions, if this is getting confusing.)

By the definition of \( \Lambda \), we see that \( P_{\alpha} \subset \lambda_{\alpha} \). We know that it has to be a proper subset (so they cannot be equal), because there are only \( \kappa_{\alpha} \) distinct \( x \in \{ \alpha \} \times \kappa_{\alpha} \), and so \( P_{\alpha} \) can have at most \( \kappa_{\alpha} \) elements.

So, now consider the function,

$$ h : \beta \rightarrow \bigcup\limits_{\alpha < \beta} \lambda_{\alpha} $$

where

$$ h(\alpha) \in \lambda_{\alpha} \setminus P_{\alpha} $$

is a choice function (i.e. it chooses an arbitrary element of \( \lambda_{\alpha} \setminus P_{\alpha} \) at each \( \alpha \in \beta \)).

We see that \( h \in \Lambda \), but \( h \) can not be in the range of \( g \), since it misses the value of every function in the range of \(g\) at every \( \alpha < \beta \). A contradiction.

QED

It is a generalization of Cantor’s Theorem, because if you set \( \kappa_\alpha = 1 \) and \( \lambda_\alpha = 2 \), then you get

$$ \left | \sum\limits_{\alpha < \mu} 1_{\alpha} \right | < \left | \prod\limits_{\alpha < \mu} 2_{\alpha} \right | $$

I.e.

$$ \mu < 2^{\mu} $$

for any cardinal, \( \mu \).

That’s all for this entry. Thanks for reading!!