Basic Ordinal and Cardinal Arithmetic
This entry will mostly focus on some foundational results in Ordinal and Cardinal arithmetic. It will provide a firmer base for dealing with infinite sets.
We defined ordinal arithmetic here. Now we’ll prove a few facts about it.
Mini-Lemma: Ordinal addition is strictly increasing
Let \( \alpha \), \( \beta \), and \( \gamma \) be arbitrary ordinals, then
$$ \begin{align} \alpha \dotplus \beta &< \alpha \dotplus \gamma \\ \Leftrightarrow \beta &< \gamma \\ \end{align} $$
Proof
For each \( \alpha \), we consider the class function,
$$ \begin{align} &f_{\alpha} : ON \rightarrow ON \\ &\text{such that} \\ &f_{\alpha}(\beta) = \alpha \dotplus \beta \\ \end{align} $$
Since
$$ f_{\alpha}(\beta) = \begin{cases} f_{\alpha}(\delta) \dotplus 1, &\beta = \delta \dotplus 1 \\ \sup\limits_{\delta < \beta} \{ f_{\alpha}(\delta) \}, &\beta \text{ a limit ordinal} \\ \end{cases} $$
by the definition of ordinal addition. From this we see that \( f_{\alpha} \) is order-preserving.
QED
Mini-lemma: Addition of a limit ordinal equals a limit ordinal
Let \( \lambda = \alpha \dotplus \beta \), where \( \beta \) is a limit ordinal, then \( \lambda \) is also a limit ordinal.
Proof
Suppose, for a contradiction, that
$$ \alpha \dotplus \beta = \delta \dotplus 1 $$
then,
$$ \sup\limits_{\epsilon < \beta} \{ \alpha \dotplus \epsilon \} = \delta \dotplus 1 $$
by the previous mini-lemma, this means that
$$ \delta \dotplus 1 = \sup\limits_{\alpha \dotplus \epsilon < \alpha \dotplus \beta} \{ \alpha \dotplus \epsilon \} $$
thus
$$ \delta = \max\limits_{\alpha \dotplus \epsilon < \alpha \dotplus \beta} \{ \alpha \dotplus \epsilon \} $$
so let \( \epsilon_{0} \) be the \( \epsilon < \beta \) such that
$$ \delta = \alpha \dotplus \epsilon_{0} $$
then, by the previous lemma, we have
$$ \epsilon_0 = \max\limits_{\epsilon < \beta} \{ \epsilon \} $$
which means that \( \beta = \epsilon_0 \dotplus 1 \), a contradiction.
QED
Lemma: Ordinal Arithmetic is Associative and Distributes on the Right
Let \( \alpha \), \( \beta \) and \( \gamma \) ordinals. Then,
- \(\displaystyle (\alpha \dotplus \beta) \dotplus \gamma \) = \( \displaystyle \alpha \dotplus (\beta \dotplus \gamma) \).
- \(\displaystyle (\alpha \dot{\times} \beta) \dot{\times} \gamma \) = \(\displaystyle \alpha \dot{\times}(\beta \dot{\times} \gamma) \).
- \(\displaystyle \alpha \dot{\times}(\beta \dotplus \gamma) \) = \(\displaystyle (\alpha \dot{\times}\beta) \dotplus (\alpha \dot{\times}\gamma) \).
However
\(\displaystyle (\beta \dotplus \gamma) \dot{\times} \alpha \) = \(\displaystyle (\beta \dot{\times} \alpha) \dotplus ( \gamma \dot{\times}\alpha ) \) does not hold, in general.
Proof
1 and 2 are easy to prove from the definitions of ordinal. We will prove 1 and leave 2 to the reader (it’s similar). We’ll prove 3 by induction. Notice that all 3 conditions hold when \( \gamma = 0 \), so we can assume the results hold for the base case.
- First, if \( \gamma = \delta \dotplus 1 \), then
$$ \begin{align} &(\alpha \dotplus \beta) \dotplus \gamma = \\ & (\alpha \dotplus \beta) \dotplus (\delta \dotplus 1) = \\ & ((\alpha \dotplus \beta) \dotplus \delta) \dotplus 1 \\ \end{align} $$
by the definition of addition of a successor ordinal. Then, by induction, this is equal to
$$ \begin{align} &( \alpha \dotplus (\beta \dotplus \delta) ) \dotplus 1 = \\ &\alpha \dotplus ((\beta \dotplus \delta) \dotplus 1 ) \\ \end{align} $$
where the last line is (again) from the definition of addition of a successor ordinal. Now, the same rule gives us
$$ \begin{align} &\alpha \dotplus( \beta \dotplus (\delta \dotplus 1) ) = \\ &\alpha \dotplus ( \beta \dotplus \gamma ) \\ \end{align} $$
Second, if \( \gamma \) is a limit ordinal, then \( \gamma = \sup\limits_{\delta < \gamma} \{ \delta \} \).
$$ \begin{align} &(\alpha \dotplus \beta) \dotplus \gamma = \\ &\sup\limits_{\delta < \gamma} \{ (\alpha \dotplus \beta) \dotplus \delta \} = \\ &\text{by induction} \\ &\sup\limits_{\delta < \gamma} \{ \alpha \dotplus (\beta \dotplus \delta) \} = \\ &\sup\limits_{ \beta \dotplus \delta < \beta \dotplus \gamma } \{ \alpha \dotplus ( \beta \dotplus \delta ) \} \\ \end{align} $$
where the last line is a result of the preceeding mini-lemma. Then, by the definition of ordinal addition with a limit ordinal, we can conclude that the last line is equal to
$$ \begin{align} &\alpha \dotplus \sup\limits_{\beta \dotplus \delta < \beta \dotplus \gamma} \{ \beta \dotplus \delta \} \\ = & \alpha \dotplus \sup\limits_{\delta < \gamma} \{ \beta \dotplus \delta \} \\ = & \alpha \dotplus ( \beta \dotplus \gamma ) \\ \end{align} $$
-
Left to you.
-
First, if \( \gamma = \delta \dotplus 1 \), then
$$ \begin{align} &\alpha \dot{\times}(\beta \dotplus (\delta \dotplus 1)) \\ =&\alpha \dot{\times}((\beta \dotplus \delta) \dotplus 1) \\ \end{align} $$
by part 1. By the definition of ordinal arithmetic (for \( \dot{\times} \)), we have that this is equal to
\[ \alpha \dot{\times}(\beta \dotplus \delta) \dotplus \alpha \]
and by induction (since \( \delta < \gamma \)), we have that this is equal to
\[ ((\alpha \dot{\times} \beta) \dotplus ( \alpha \dot{\times}\delta )) \dotplus \alpha \]
and, by applying part 1, we know that this is equal to
\[ (\alpha \dot{\times} \beta) \dotplus ( (\alpha \dot{\times}\delta) \dotplus \alpha ) \]
and by the definition of ordinal arithmetic for \( \dot{\times} \), we have that this is equal to
\[ (\alpha \dot{\times} \beta) \dotplus (\alpha \dot{\times}\gamma) \]
Second, if \( \gamma \) is a limit ordinal, then \( \gamma = \sup\limits_{\delta < \gamma}\{ \delta \} \). By the definition of ordinal addition, that means that
$$ \begin{align} \beta \dotplus \gamma &= \\ \sup\limits_{\delta < \gamma} \{ \beta \dotplus \delta \} &= \lambda \\ \end{align} $$
where \( \lambda \) is a limit ordinal. Then, by the definition of ordinal multiplication, we have
$$ \begin{align} \alpha \dot{\times} \lambda &= \sup\limits_{\xi < \beta \dotplus \gamma = \lambda } \{ \alpha \dot{\times} \xi \} \\ &= \sup\limits_{\delta < \gamma} \{ \alpha \dot{\times} ( \beta \dotplus \delta ) \} \\ \end{align} $$
by induction, this is equal to
\[ \sup\limits_{\delta < \gamma} \{ (\alpha \dot{\times} \beta) \dotplus (\alpha \dot{\times} \delta) \} \]
and, by the definition of ordinal addition, this is equal to
\[ (\alpha \dot{\times}\beta) \dotplus \sup\limits_{\delta < \gamma} \{ \alpha \dot{\times}\delta \} \]
and, by the definition of ordinal multiplication, this is equal to
\[ (\alpha \dot{\times} \beta) \dotplus (\alpha \dot{\times}\gamma) \]
This finishes the proof of part 3.
Now we’ll show why left distributivity doesn’t always hold. I.e. the following equation doesn’t always work!
\[ (\beta \dotplus \gamma) \dot{\times} \alpha = (\beta \dot{\times} \alpha) \dotplus ( \gamma \dot{\times}\alpha ) \]
Let \( \beta = \gamma = 1 \), and \( \alpha = \omega_0 \), where (as mentioned before)
\[ \omega_0 := \sup\{ n | n \in ON \text{ and } n \text{ is finite } \} \]
then
$$ \begin{align} 2 \dot{\times} \omega_{0} &= \sup\limits_{n \in \omega_0} \{ 2n \} \\ &= \omega_0 \\ \end{align} $$
whereas,
$$ \begin{align} \omega_0 &\dotplus \omega_0 = \\ \sup\limits_{n \in \omega_0} \{ \omega_0 &\dotplus n \} \end{align} $$
which is strictly greater than \( \omega_0 \).
QED
Now we’re going to switch from dealing with ordinals to cardinals. Here we prove the “Fundamental Theorem of Cardinal Arithmetic.” It shows that, for the most part, dealing with infinite cardinals is fairly easy.
Lemma: If S is well-ordered, we can well-order SxS
Let \( (S, <_w) \) be a well-ordered set, then there exists a relation, \( <_c \) such that \( (S \times S, <_c) \) is well-ordered.
Proof
Let
$$ (s_1, s_2) <_c (t_1, t_2) \Leftrightarrow \begin{cases} \max \{ s_1, s_2 \} <_w \max \{ t_1, t_2 \} \\ s_1 <_w t_1, \max \{ s_1, s_2 \} = \max \{ t_1, t_2 \} \\ s_2 <_w t_2, \max \{ s_1, s_2 \} = \max \{ t_1, t_2 \} \text{ and } s_1 = t_1 \\ \end{cases} $$
Notice that \( <_c \) is a linear ordering and that every subset of \( S \times S \) has a \( <_c\)-least element.
QED
Theorem: Fundamental Theorem of Cardinal Arithmetic
Let \( \kappa \) and \( \mu \) be infinite cardinals, then
- \( \displaystyle \kappa + \mu = \max \{ \kappa, \mu \} \).
- \( \displaystyle \kappa \cdot \mu = \max \{ \kappa, \mu \} \).
Proof
Without loss of generality, suppose \( \kappa \leq \mu \).
We can easily find 1-1 functions:
$$ \begin{align} f_1 &: \kappa + \mu \xrightarrow{\text{1-1}} \mu \cdot \mu \\ f_2 &: \kappa \cdot \mu \xrightarrow{\text{1-1}} \mu \cdot \mu \\ \end{align} $$
Therefore, we’ll focus our efforts on showing that \( \mu \cdot \mu = \mu \).
Suppose, for a contradiction, that for some infinite cardinals, we have \( \mu < \mu \cdot \mu\). Let \( \xi \) be the least such cardinal.
By definition, \( \xi \cdot \xi = |\xi \times \xi| \), and by the previous lemma, we can well-order \( \xi \times \xi \), so it’s order type has to be equal to an ordinal, \( \zeta \) (by this theorem). So we have an order-preserving function,
$$ g : \xi \times \xi \xrightarrow{\text{1-1, onto}} \zeta $$
And, since we’re assuming that \( \xi < |\xi \times \xi|\), we have
$$ \xi < |\xi \times \xi| = |\zeta| \leq \zeta $$
so, \( \xi \in \zeta \). Then we can take
\[ g^{-1}(\xi) = (\sigma, \tau) \in \xi \times \xi \]
Since \( g \) is order-preserving, \( g^{-1} \) is also order-preserving. Thus,
$$ \begin{align} A &= \{ g^{-1}(\eta) | \eta < \xi \} \\ &\subseteq \max \{ \sigma, \tau \} \times \max \{ \sigma, \tau \} \\ \end{align} $$
but since \( \xi \) is a cardinal, that means that every smaller ordinal has a smaller cardinality. So we have
$$ \begin{align} |A| &\leq |\max\{ \sigma, \tau \} \times \max\{ \sigma, \tau \}| \\ &= |\max\{ \sigma, \tau \}|^{2} \\ &= \max \{ |\sigma|, |\tau| \}^{2} \\ &= \max \{ |\sigma|^2, |\tau|^2 \} \\ \end{align} $$
but since \( \xi \) is the smallest infinite cardinal such that \( \xi < \xi^2 \), and \( \max \{ |\sigma|, |\tau| \} < \xi \), we must have \( \max \{ |\sigma|^2, |\tau|^2 \} < \xi \), and so \( |A| < \xi \). But this is impossible, because
\[ (g \upharpoonright A) : A \xrightarrow{\text{1-1, onto}} \xi \]
QED
Definitions: Infinite Sums and Products
Let \( \beta \) be an ordinal, and \( \{ \kappa_{\delta} \}_{\delta < \beta} \) a set of cardinals, then we define
$$ \begin{align} &(1) &\sum\limits_{\delta < \beta} \kappa_{\delta} &= \left | \bigcup\limits_{\delta < \beta} \{ \delta \} \times \kappa_{\delta} \right | \\ &(2) &\prod\limits_{\delta < \beta} \kappa_{\delta} &= \left | \left \{ f : \beta \rightarrow \bigcup\limits_{\delta < \beta} \kappa_{\delta} | f(\delta) \in \kappa_{\delta} \right \} \right | \\ \end{align} $$
Corollary: Bounds on Sums
Let \( \{ \kappa_{\delta} \}_{\delta < \beta} \) be a set of cardinals indexed by an ordinal, \( \beta \), where
\[ \kappa_{\delta} \leq \max \{ |\beta|, \aleph_0 \} \]
then
\[ \sum\limits_{\delta < \beta} \kappa_{\delta} \leq \max\{ |\beta|, \aleph_0 \} \]
Proof
An easy application of the Fundamental Theorem of Cardinal Arithmetic.
QED
We’ll finish up this entry with a few definitions.
Definition: Cofinality
Let \( \kappa \) be a cardinal, and \( K = \{ \mu_{\delta} \}_{\delta < \beta} \) be a subset of \( \kappa \), such that \( \text{sup}(K) = \kappa \), then \( K \) is said to be a cofinal subset of \( \kappa \).
If we have the condition that every cofinal subset of \( \kappa \) has cardinality greater than or equal to \( \lambda \), then \( \kappa \) is said to have cofinality of \( \lambda \).
It is often written:
\[ cf(\kappa) = \lambda \]
Definitions: Singular and Regular Cardinals
Let \( \kappa \) be an infinite cardinal.
- If \( cf(\kappa) \lneq \kappa \), then \( \kappa \) is said to be a singular cardinal.
- If \( cf(\kappa) = \kappa \), then \( \kappa \) is said to be a regular cardinal.