Cardinal Arithmetic

Definition one in this chapter

When $\cardfont{a}$source and $\cardfont{b}$source are cardinals:

where $\funfromto{X}{Y} = \Setabs{f}{f \text{ is a function } X \to Y}$source. (It is easy to show that $\funfromto{X}{Y}$source exists for any sets $X$source and $Y$source; we leave this as an exercise.)

Exercise one in this chapter

Prove in $\Zminus$source that $\funfromto{X}{Y}$source exists for any sets $X$source and $Y$source. Working in $\ZF$source, compute $\setrank{\funfromto{X}{Y}}$source from $\setrank{X}$source and $\setrank{Y}$source, in the manner of lemma four in chapter “Ordinal Arithmetic”.

Proposition one in this chapter

$\cardplus$source and $\cardtimes$source are commutative and associative.

Proof

For commutativity, by the lemma on Cardinals Behave Right it suffices to observe that $\cardeq{(\cardfont{a} \disjointsum \cardfont{b})}{(\cardfont{b} \disjointsum \cardfont{a})}$source and $\cardeq{(\cardfont{a} \times \cardfont{b})}{(\cardfont{b} \times \cardfont{a})}$source. We leave associativity as an exercise.

Exercise two in this chapter

Prove that $\cardplus$source and $\cardtimes$source are associative.

Proposition two in this chapter

$A$source is infinite iff $\card{A} \cardplus 1 = 1 \cardplus \card{A} = \card{A}$source.

Proof

As in theorem one in chapter “Cardinals”, from lemma five in chapter “Ordinal Arithmetic” and the lemma on Cardinals Behave Right.

Lemma one in this chapter

$\card{\Pow{A}} = \cardexpo{2}{\card{A}}$source, for any $A$source.

Proof

For each subset $B \subseteq A$source, let $\chi_B \in \funfromto{A}{2}$source be given by:

Now let $f(B) = \chi_B$source; this defines a bijection $f \colon \Pow{A} \to \funfromto{A}{2}$source. So $\cardeq{\Pow{A}}{\funfromto{A}{2}}$source. Hence $\cardeq{\Pow{A}}{\funfromto{\card{A}}{2}}$source, so that $\card{\Pow{A}} = \card{\funfromto{\card{A}}{2}} = 2^{\card{A}}$source.

Corollary one in this chapter

$\cardfont{a} < \cardexpo{2}{\cardfont{a}}$source for any cardinal $\cardfont{a}$source.

Proof

From Cantor's Theorem (the theorem on cantor) and the lemma on Size Powersettwo Exp.

Theorem one in this chapter

$\card{\Real} = \cardexpo{2}{\omega}$source

Proof

[Proof skeleton] There are plenty of ways to prove this. The most straightforward is to argue that $\cardle{\Pow{\omega}}{\Real}$source and $\cardle{\Real}{\Pow{\omega}}$source, and then use Schröder-Bernstein to infer that $\cardeq{\Real}{\Pow{\omega}}$source, and the lemma on Size Powersettwo Exp to infer that $\card{\Real} = \cardexpo{2}{\omega}$source. We leave it as an (illuminating) exercise to define injections $f \colon \Pow{\omega} \to \Real$source and $g \colon \Real \to \Pow{\omega}$source.

Exercise three in this chapter

Complete the proof of theorem one in chapter “Cardinal Arithmetic”, by showing that $\cardle{\Pow{\omega}}{\Real}$source and $\cardle{\Real}{\Pow{\omega}}$source.

Definition two in this chapter

We define a canonical ordering, $\canonord$source, on pairs of ordinals, by stipulating that $\tuple{\alpha_1, \alpha_2} \canonord \tuple{\beta_1, \beta_2}$source iff either:

1. $\max(\alpha_1, \alpha_2) < \max(\beta_1, \beta_2)$source; or

2. $\max(\alpha_1, \alpha_2) = \max(\beta_1, \beta_2)$source and $\alpha_1 < \beta_1$source; or

3. $\max(\alpha_1, \alpha_2) = \max(\beta_1, \beta_2)$source and $\alpha_1 = \beta_1$source and $\alpha_2 < \beta_2$source

Lemma two in this chapter

$\tuple{\alpha \times \alpha, \canonord}$source is a well-order, for any ordinal $\alpha$source.

Proof

Evidently $\canonord$source is connected on $\alpha \times \alpha$source. For suppose that neither $\tuple{\alpha_1, \alpha_2}$source nor $\tuple{\beta_1, \beta_2}$source is $\canonord$source-less than the other. Then $\max(\alpha_1, \alpha_2) = \max(\beta_1, \beta_2)$source and $\alpha_1 = \beta_1$source and $\alpha_2 = \beta_2$source, so that $\tuple{\alpha_1, \alpha_2} = \tuple{\beta_1, \beta_2}$source.

To show well-ordering, let $X \subseteq \alpha\times\alpha$source be non-empty. Since $\alpha$source is an ordinal, some $\delta$source is the least member of $\Setabs{\max(\gamma_1, \gamma_2)}{\tuple{\gamma_1, \gamma_2} \in X}$source. Now discard all pairs from $\Setabs{\tuple{\gamma_1,\gamma_2} \in X}{\max(\gamma_1, \gamma_2) = \delta}$source except those with least first coordinate; from among these, the pair with least second coordinate is the $\canonord$source-least element of $X$source.

Proposition three in this chapter

If $\cardeq{\alpha}{\beta}$source, then $\cardeq{\alpha \times \alpha}{\beta \times \beta}$source.

Proof

Just let $f \colon \alpha \to \beta$source induce $\tuple{\gamma_1, \gamma_2} \mapsto \tuple{f(\gamma_1), f(\gamma_2)}$source.

Lemma three in this chapter

$\cardeq{\alpha}{\alpha \times \alpha}$source, for any infinite ordinal $\alpha$source

Proof

For reductio, let $\alpha$source be the least infinite ordinal for which this is false. proposition “Enumerability of pairs of natural numbers” in chapter “The Size of Sets” shows that $\cardeq{\omega}{\omega\times\omega}$source, so $\omega \in \alpha$source. Moreover, $\alpha$source is a cardinal: suppose otherwise, for reductio; then $\card{\alpha} \in \alpha$source, so that $\cardeq{\card{\alpha}}{\card{\alpha} \times \card{\alpha}}$source, by hypothesis; and $\cardeq{\card{\alpha}}{\alpha}$source by definition; so that $\cardeq{\alpha}{\alpha\times\alpha}$source by proposition three in chapter “Cardinal Arithmetic”.

Now, for each $\tuple{\gamma_1, \gamma_2} \in \alpha \times \alpha$source, consider the segment:

Letting $\gamma = \max(\gamma_1, \gamma_2)$source, note that $\tuple{\gamma_1, \gamma_2} \canonord \tuple{\gamma+1, \gamma + 1}$source. So, when $\gamma$source is infinite, observe:

So $\ordtype{\alpha\times \alpha, \canonord} \leq \alpha$source, and hence $\cardle{\alpha \times \alpha}{\alpha}$source. Since of course $\cardle{\alpha}{\alpha \times \alpha}$source, the result follows by Schröder-Bernstein.

Theorem two in this chapter

If $\cardfont{a}, \cardfont{b}$source are infinite cardinals, then:

Proof

Without loss of generality, suppose $\cardfont{a} = \max(\cardfont{a}, \cardfont{b})$source. Then invoking lemma three in chapter “Cardinal Arithmetic”, $\cardfont{a}\cardtimes\cardfont{a} = \cardfont{a} \leq \cardfont{a} \cardplus \cardfont{b} \leq \cardfont{a} \cardplus \cardfont{a} \leq \cardfont{a} \cardtimes \cardfont{a}$source.

Proposition four in this chapter

Let $\cardfont{a}$source be an infinite cardinal. For each ordinal $\beta \in \cardfont{a}$source, let $X_\beta$source be a set with $\card{X_\beta} \leq \cardfont{a}$source. Then $\card{\bigcup_{\beta \in \cardfont{a}} X_\beta} \leq \cardfont{a}$source.

Proof

For each $\beta \in \cardfont{a}$source, fix an injection $f_\beta \colon X_\beta \to \cardfont{a}$source.Footnote: How are these “fixed”? See section “Countable Choice” in chapter “Choice”. Define an injection $g \colon \bigcup_{\beta \in \cardfont{a}} X_\beta \to \cardfont{a} \times \cardfont{a}$source by $g(v) = \tuple{\beta, f_\beta(v)}$source, where $v \in X_\beta$source and $v \notin X_\gamma$source for any $\gamma \in \beta$source. Now $\bigcup_{\beta \in \cardfont{a}} X_\beta \preceq \cardfont{a} \times \cardfont{a} \approx \cardfont{a}$source by theorem two in chapter “Cardinal Arithmetic”.

Proposition five in this chapter

$\cardexpo{\cardfont{a}}{\cardfont{b} \cardplus \cardfont{c}} = \cardexpo{\cardfont{a}}{\cardfont{b}} \cardtimes \cardexpo{\cardfont{a}}{\cardfont{c}}$source and $\cardexpo{(\cardexpo{\cardfont{a}}{\cardfont{b}})}{\cardfont{c}} = \cardexpo{\cardfont{a}}{\cardfont{b} \cardtimes \cardfont{c}}$source, for any cardinals $\cardfont{a}, \cardfont{b}, \cardfont{c}$source.

Proof

For the first claim, consider a function $f \colon (\cardfont{b}\disjointsum\cardfont{c}) \to \cardfont{a}$source. Now “split this”, by defining $f_\cardfont{b}(\beta) = f(\beta, 0)$source for each $\beta \in \cardfont{b}$source, and $f_\cardfont{c}(\gamma) = f(\gamma, 1)$source for each $\gamma \in \cardfont{c}$source. The map $f \mapsto (f_{\cardfont{b}} \times f_\cardfont{c})$source is a bijection $\funfromto{\cardfont{b} \disjointsum \cardfont{c}}{\cardfont{a}} \to (\funfromto{\cardfont{b}}{\cardfont{a}} \times \funfromto{\cardfont{c}}{\cardfont{a}})$source.

For the second claim, consider a function $f \colon \cardfont{c} \to (\funfromto{\cardfont{b}}{\cardfont{a}})$source; so for each $\gamma \in \cardfont{c}$source we have some function $f(\gamma) \colon \cardfont{b} \to \cardfont{a}$source. Now define $f^*(\beta, \gamma) = (f(\gamma))(\beta)$source for each $\tuple{\beta, \gamma} \in \cardfont{b} \times \cardfont{c}$source. The map $f \mapsto f^*$source is a bijection $\funfromto{\cardfont{c}}{(\funfromto{\cardfont{b}}{\cardfont{a}})} \to \funfromto{\cardfont{b} \cardtimes \cardfont{c}}{\cardfont{a}}$source.

Proposition six in this chapter

If $2 \leq \cardfont{a} \leq \cardfont{b}$source and $\cardfont{b}$source is infinite, then $\cardexpo{\cardfont{a}}{\cardfont{b}} = \cardexpo{2}{\cardfont{b}}$source

Proof

Proposition seven in this chapter

If $\cardfont{a}$source is infinite and $n \in \omega$source then $\cardexpo{\cardfont{a}}{n} = \cardfont{a}$source

Proof

$\cardexpo{\cardfont{a}}{n} = \cardfont{a} \cardtimes \cardfont{a} \cardtimes \ldots \cardtimes \cardfont{a} = \cardfont{a}$source, by theorem two in chapter “Cardinal Arithmetic”.

Proposition eight in this chapter

If $2 \leq \cardfont{b} < \cardfont{a} \leq \cardexpo{2}{\cardfont{b}}$source and $\cardfont{b}$source is infinite, then $\cardexpo{\cardfont{a}}{\cardfont{b}} = \cardexpo{2}{\cardfont{b}}$source

Proof

$\cardexpo{2}{\cardfont{b}}\leq \cardexpo{\cardfont{a}}{\cardfont{b}} \leq \cardexpo{(\cardexpo{2}{\cardfont{b}})}{\cardfont{b}} = \cardexpo{2}{\cardfont{b}\cardtimes\cardfont{b}} = \cardexpo{2}{\cardfont{b}}$source, reasoning as in proposition six in chapter “Cardinal Arithmetic”.

Definition three in this chapter

Where $\cardsucc{\cardfont{a}}$source is the least cardinal strictly greater than $\cardfont{a}$source, we define two infinite sequences:

Proposition nine in this chapter

$\aleph_\alpha$source and $\beth_\alpha$source are cardinals, for every ordinal $\alpha$source.

Proof

Both results hold by a simple transfinite induction. $\aleph_0 = \beth_0 = \omega$source is a cardinal by corollary two in chapter “Cardinals”. Assuming $\aleph_\alpha$source and $\beth_\alpha$source are both cardinals, $\aleph_{\alpha+1}$source and $\beth_{\alpha+1}$source are explicitly defined as cardinals. And the union of a set of cardinals is a cardinal, by proposition three in chapter “Cardinals”.

Proposition ten in this chapter

If $\cardfont{a}$source is an infinite cardinal, then $\cardfont{a} = \aleph_\gamma$source for some unique $\gamma$source.

Proof

By transfinite induction on cardinals. For induction, suppose that if $\cardfont{b} < \cardfont{a}$source then $\cardfont{b} = \aleph_{\gamma_\cardfont{b}}$source. If $\cardfont{a} = \cardsucc{\cardfont{b}}$source for some $\cardfont{b}$source, then $\cardfont{a} = \cardsucc{(\aleph_{\gamma_\cardfont{b}})}= \aleph_{\gamma_\cardfont{b}+1}$source. If $\cardfont{a}$source is not the successor of any cardinal, then since cardinals are ordinals $\cardfont{a} = \bigcup_{\cardfont{b} < \cardfont{a}} \cardfont{b} = \bigcup_{\cardfont{b} < \cardfont{a}}{\aleph_{\gamma_\cardfont{b}}}$source, so $\cardfont{a} = \aleph_\gamma$source where $\gamma = \bigcup_{\cardfont{b} < \cardfont{a}}\gamma_\cardfont{b}$source.

Definition four in this chapter

Generalized Continuum Hypothesis (GCH). $\aleph_\alpha = \beth_\alpha$source, for all $\alpha$source.

Definition five in this chapter

Continuum Hypothesis (CH). $\aleph_1 = \beth_1$source.

Proposition eleven in this chapter

There is an $\aleph$source-fixed-point.

Proof

Using recursion, define:

Now $\kappa$source is a cardinal by proposition three in chapter “Cardinals”. But now:

Proposition twelve in this chapter

There is a $\beth$source-fixed-point, i.e., a $\kappa$source such that $\kappa= \beth_\kappa$source.

Proof

As in proposition eleven in chapter “Cardinal Arithmetic”, using “$\beth$source” in place of “$\aleph$source”.

Proposition thirteen in this chapter

$\card{V_{\omega+\alpha}} = \beth_{\alpha}$source. If $\omega \ordtimes \omega \leq \alpha$source, then $\card{V_\alpha} = \beth_\alpha$source.

Proof

The first claim holds by a simple transfinite induction. The second claim follows, since if $\omega \ordtimes \omega \leq \alpha$source then $\omega + \alpha = \alpha$source. To establish this, we use facts about ordinal arithmetic from chapter “Ordinal Arithmetic”. First note that $\omega \ordtimes \omega = \omega \ordtimes (1 \ordplus \omega) = (\omega \ordtimes 1) \ordplus (\omega\ordtimes\omega) = \omega \ordplus (\omega \ordtimes \omega)$source. Now if $\omega \ordtimes \omega \leq \alpha$source, i.e., $\alpha = (\omega\ordtimes\omega) \ordplus \beta$source for some $\beta$source, then $\omega \ordplus \alpha = \omega \ordplus ((\omega \ordtimes \omega) \ordplus \beta) = (\omega \ordplus (\omega \ordtimes \omega)) \ordplus \beta = (\omega \ordtimes \omega) \ordplus \beta = \alpha$source.

Corollary two in this chapter

There is a $\kappa$source such that $\card{V_\kappa} = \kappa$source.

Proof

Let $\kappa$source be a $\beth$source-fixed point, as given by proposition twelve in chapter “Cardinal Arithmetic”. Clearly $\omega \ordtimes \omega < \kappa$source. So $\card{V_\kappa} = \beth_\kappa= \kappa$source by proposition thirteen in chapter “Cardinal Arithmetic”.