Exercise 7.2.1

Proof. Clearly for $\gamma =\beta$ we have $\gamma =\beta <\alpha$ and $\left|\beta \right|=\left|\gamma \right|$ so that $\left|\beta \right|\le \left|\gamma \right|$ is true. □

Proof. First let $f$ be the isomorphism from $\alpha$ to $A$. Clearly by Lemma 1 there is an ordinal $\gamma <\alpha$ such that $\left|\beta \right|\le \left|\gamma \right|$. Now let $a=f(\gamma )$ so that clearly $a\in A$, and let

Now, we claim that $X=f[\gamma ]$. So consider any $x\in X$ so that $x\prec a$. It then follows that $f^{-1}(x)<f^{-1}(a)=\gamma$ since $f^{-1}$ is an isomorphism since $f$ is. Hence $f^{-1}(x)\in \gamma$ so that clearly $x=f(f^{-1}(x))\in f[\gamma ]$. Since $x$ was arbitrary it follows that $X\subseteq f[\gamma ]$. Now consider any $x\in f[\gamma ]$ so that there is a $\delta \in \gamma$ such that $x=f(\delta )$. Then $\delta <\gamma$ so that $x=f(\delta )\prec f(\gamma )=a$ since $f$ is an isomorphism so that by definition $x\in X$. Hence $f[\gamma ]\subseteq X$. This shows that $X=f[\gamma ]$. Then, since $f$ is bijective, it follows that $\left|\beta \right|\le \left|\gamma \right|=\left|f[\gamma ]\right|=\left|X\right|$. □

Proof. Suppose that $\left|\alpha \right|\le \left|\beta \right|$ but that $\alpha >\beta$. Then clearly $\beta$ is isomorphic (and therefore equipotent) to an initial segment of $\alpha$ so that $\left|\beta \right|\le \left|\alpha \right|$. Then by the Cantor-Bernstein Theorem we have $\left|\alpha \right|=\left|\beta \right|$. However since $\alpha$ is an initial ordinal and $\beta <\alpha$ it cannot be that $\left|\alpha \right|=\left|\beta \right|$. Thus we have a contradiction so that it must be that $\alpha \le \beta$ as desired. □

Proof. We show this by induction on $\alpha$. For $\alpha =0$ we have ${\omega }_{\alpha }={\omega }_0=\omega$ so that there is no infinite initial ordinal $\mathrm{\Omega }$ such that $\mathrm{\Omega }<{\omega }_{\alpha }=\omega$. Hence the hypothesis is vacuously true. Now suppose that, for every infinite initial ordinal $\mathrm{\Omega }<{\omega }_{\alpha }$, there is a $\gamma <\alpha$ such that $\mathrm{\Omega }={\omega }_{\gamma }$. Consider any infinite initial ordinal $\mathrm{\Omega }<{\omega }_{\alpha +1}$. Then $\mathrm{\Omega }<{\omega }_{\alpha +1}=h({\omega }_{\alpha })$ so that $\mathrm{\Omega }$ is equipotent to some subset of ${\omega }_{\alpha }$ by the definition of the Hartogs number. From this it clearly follows that $\left|\mathrm{\Omega }\right|\le \left|{\omega }_{\alpha }\right|$ and hence $\mathrm{\Omega }\le {\omega }_{\alpha }$ by Lemma 3 since both $\mathrm{\Omega }$ and ${\omega }_{\alpha }$ are initial ordinals. If $\mathrm{\Omega }={\omega }_{\alpha }$ then we are finished but if $\mathrm{\Omega }<{\omega }_{\alpha }$ then by the induction hypothesis there is a $\gamma <\alpha$ such that $\mathrm{\Omega }={\omega }_{\gamma }$ so that we are also finished.

Now suppose that $\alpha$ is a nonzero limit ordinal and that for every $\beta <\alpha$ and infinite initial ordinal $\mathrm{\Omega }<{\omega }_{\beta }$ there is a $\gamma <\beta$ such that $\mathrm{\Omega }={\omega }_{\gamma }$. Consider then any infinite initial ordinal $\mathrm{\Omega }<{\omega }_{\alpha }$. Then since ${\omega }_{\alpha }=\sup <!--\; FUNCTION\; APPLICATION\; -->\left\{{\omega }_{\beta }\mid \beta <\alpha \right\}$ it follows that $\mathrm{\Omega }$ is not an upper bound of $\left\{{\omega }_{\beta }\mid \beta <\alpha \right\}$ so that there is a $\beta <\alpha$ such that $\mathrm{\Omega }<{\omega }_{\beta }$. But then by the induction hypothesis there is a $\gamma <\beta$ such that $\mathrm{\Omega }={\omega }_{\gamma }$. This completes the transfinite induction. □

Proof. First, if $\beta$ is finite then clearly $\beta <\omega$ so that $\beta \in \omega$. Then $\beta \subseteq \omega$ since $\omega$ is transitive (since it is an ordinal number). Hence $\left|\beta \right|\le \left|\omega \right|={\aleph }_0$ (i.e. $\gamma =0$ so that $\gamma <\alpha$). On the other hand if $\beta$ is infinite then by Theorem 7.1.3 $\beta$ is equipotent to some initial ordinal $\mathrm{\Omega }$. Clearly $\mathrm{\Omega }$ is infinite since $\beta$ is and clearly $\mathrm{\Omega }<{\omega }_{\alpha }$ since $\beta <{\omega }_{\alpha }$ and ${\omega }_{\alpha }$ is an initial ordinal. It then follows from Lemma 4 that there is a $\gamma <\alpha$ such that $\mathrm{\Omega }={\omega }_{\gamma }$. Then we have $\left|\beta \right|=\left|\mathrm{\Omega }\right|=\left|{\omega }_{\gamma }\right|={\aleph }_{\gamma }$ so that $\left|\beta \right|\le {\aleph }_{\gamma }$ is true. □

Proof. Suppose that $\alpha$ is an infinite initial ordinal and that it a successor so that $\alpha =\beta +1$. It was shown in Lemma ?? that $\left|\beta \right|=\left|\beta +1\right|=\left|\alpha \right|$, but since clearly $\beta <\alpha$ this contradicts the fact that $\alpha$ is an initial ordinal. Hence $\alpha$ must be a limit ordinal. □

Proof. By Theorem 6.1.3 we have:

Case: $A$ and $B$ are isomorphic. Let $f$ be the isomorphism from $A$ to $B$. Then clearly $f$ is a bijection so that $\left|A\right|=\left|B\right|$. Also since $f$ is injective $\left|A\right|\le \left|B\right|$. Clearly also $f^{-1}$ is bijective from $B$ to $A$ so that $\left|B\right|\le \left|A\right|$ as well.

Case: $A$ is isomorphic to an initial segment of $B$. Then if $f$ is the isomorphism clearly $f$ is an injective function from $A$ to $B$ so that $\left|A\right|\le \left|B\right|$.

Case: $B$ is isomorphic to an initial segment of $A$. Then if $f$ is the isomorphism clearly $f$ is an injective function from $B$ to $A$ so that $\left|B\right|\le \left|A\right|$.

Since these cases are exhaustive by Theorem 6.1.3 clearly the result has been shown.

Note that this did not require the Axiom of Choice. □

Proof. ( $\to$) Suppose that $\left|A\right|\nleqq \left|B\right|$. Then it follows from Lemma 7 above that $\left|B\right|\le \left|A\right|$. Suppose that $\left|B\right|=\left|A\right|$. Then there is a bijection $f$ from $B$ to $A$. But then clearly $f^{-1}$ is also a bijection and therefore injective. Hence by definition $\left|A\right|\le \left|B\right|$, a contradiction. So it cannot be that $\left|B\right|=\left|A\right|$. Hence $\left|B\right|<\left|A\right|$ by definition as desired.

( $\leftarrow$) We show this by proving the contrapositive. So suppose that $\left|A\right|\le \left|B\right|$. Also suppose that $\left|B\right|\le \left|A\right|$ so that by Lemma 7 above $\left|A\right|=\left|B\right|$. Thus we have shown that

thereby showing the contrapositive. □

Proof. Suppose that $A_1$ and $A_2$ are disjoint sets that are both equipotent to ${\omega }_{\alpha }$ for some ordinal $\alpha$. Then there are bijections $f_1$ and $f_2$ from $A_1$ and $A_2$, respectively, to ${\omega }_{\alpha }$. We define a well-ordering $\prec$ of $A=A_1\cup A_2$ as follows: for $a$ and $b$ in $A$ we let $a\prec b$ if and only if

• $a$ and $b$ are in $A_1$ and $f_1(a)<f_1(b)$, or
• $a$ and $b$ are in $A_2$ and $f_2(a)<f_2(b)$, or
• $a\in A_1$ and $b\in A_2$ and $f_1(a)\le f_2(b)$, or
• $a\in A_2$ and $b\in A_1$ and $f_2(a)<f_1(b)$.

First we show that $\prec$ is transitive. So consider $a$, $b$, and $c$ in $A$ such that $a\prec b$ and $b\prec c$.

Case: $a\in A_1$

Case: $b\in A_1$

Case: $c\in A_1$. Then $f_1(a)<f_1(b)<f_1(c)$ so that $f_1(a)<f_1(c)$ and hence $a\prec c$.

Case: $c\in A_2$. Then $f_1(a)<f_1(b)\le f_2(c)$ so that $f_1(a)\le f_2(c)$ is true and hence $a\prec c$.

Case: $b\in A_2$

Case: $c\in A_1$. Then $f_1(a)\le f_2(b)<f_1(c)$ so that $f_1(a)<f_1(c)$ and hence $a\prec c$.

Case: $c\in A_2$. Then $f_1(a)\le f_2(b)<f_2(c)$ so that $f_1(a)\le f_2(c)$ is true and hence $a\prec c$.

Case: $a\in A_2$

Case: $b\in A_1$

Case: $c\in A_1$. Then $f_2(a)<f_1(b)<f_1(c)$ so that $f_2(a)<f_1(c)$ and hence $a\prec c$.

Case: $c\in A_2$. Then $f_2(a)<f_1(b)\le f_2(c)$ so that $f_2(a)<f_2(c)$ and hence $a\prec c$.

Case: $b\in A_2$

Case: $c\in A_1$. Then $f_2(a)<f_2(b)<f_1(c)$ so that $f_2(a)<f_1(c)$ and hence $a\prec c$.

Case: $c\in A_2$. Then $f_2(a)<f_2(b)<f_2(c)$ so that $f_2(a)<f_2(c)$ and hence $a\prec c$.

Since all cases imply that $a\prec c$ and $a$, $b$, and $c$ were arbitrary this shows that $\prec$ is transitive.

Now we show that for any $a$ and $b$ in $A$, that either $a\prec b$, $a=b$, or $b\prec a$ and that only one of these is true. So consider any $a$ and $b$ in $A$. Then we have

Case: $a\in A_1$

Case: $b\in A_1$. Then clearly exactly one of the following is true: $a\prec b$ if $f_1(a)<f_1(b)$, $a=b$ if $f_1(a)=f_1(b)$ since $f_1$ is a bijection, and $b\prec a$ if $f_1(b)<f_1(a)$.

Case: $b\in A_2$. Clearly $a=b$ is not possible since $A_1$ and $A_2$ are disjoint. Then if $f_1(a)\le f_2(b)$ then $a\prec b$ and if $f_1(a)>f_2(b)$ then $b\prec a$, noting that these are mutually exclusive.

Case: $a\in A_2$

Case: $b\in A_1$. Then again clearly $a=b$ is not possible since $A_1$ and $A_2$ are disjoint. Then if $f_2(a)<f_1(b)$ then $a\prec b$ and if $f_2(a)\ge f_1(b)$ then $b\prec a$, noting that these are mutually exclusive.

Case: $b\in A_2$. Then clearly exactly one of the following is true: $a\prec b$ if $f_2(a)<f_2(b)$, $a=b$ if $f_2(a)=f_2(b)$ since $f_2$ is a bijection, and $b\prec a$ if $f_2(b)<f_2(a)$.

Thus we have shown that $\prec$ is a total (strict) order on $A$.

Now we show that $\prec$ is also a well-ordering. So let $X$ be a nonempty subset of $A$. Let $B=f_1[X\cap A_1]\cup f_2[X\cap A_2]$, noting that this is a nonempty set of ordinals. Then let $B$ has a least element $\alpha$.

Case: $\alpha \in f_1[X\cap A_1]$. Then we claim that $x=f_1^{-1}(\alpha )$ is the $\prec$-least element of $X$, noting that $x\in A_1$. Note also that clearly then $f_1(x)=f_1(f_1^{-1}(\alpha ))=\alpha$. So consider any $y\in X$.

Case: $y\in A_1$. Then $y\in X\cap A_1$ so that $f_1(y)\in f_1[X\cap A_1]$ so $f_1(y)\in B$. Thus $f_1(x)=\alpha \le f_1(y)$ since $\alpha$ is the least element of $B$. Clearly if $f_1(x)=f_1(y)$ then $x=y$ since $f_1$ is bijective. On the other hand if $f_1(x)<f_1(y)$ then by definition $x\prec y$. Hence in either case we have $x\preccurlyeq y$.

Case: $y\in A_2$. Then $y\in X\cap A_2$ so that $f_2(y)\in f_2[X\cap A_2]$ so that $f_2(y)\in B$. Thus $f_1(x)=\alpha \le f_2(y)$ so that by definition $x\prec y$. Hence again $x\preccurlyeq y$ is true.

Case: $\alpha \notin f_1[X\cap A_1]$. Then it has to be that $\alpha \in f_2[X\cap A_2]$. Then we claim that $x=f_2^{-1}(\alpha )$ is the $\prec$-least element of $X$, noting that $x\in A_2$. Note also that clearly then $f_2(x)=f_2(f_2^{-1}(\alpha ))=\alpha$. So consider any $y\in X$.

Case: $y\in A_1$. Then $y\in X\cap A_1$ so that $f_1(y)\in f_1[X\cap A_1]$ so $f_1(y)\in B$. Thus $f_2(x)=\alpha \le f_1(y)$ since $\alpha$ is the least element of $B$. Now, it cannot be that $f_2(x)=\alpha =f_1(y)$ for then $\alpha$ would be in $f_1[X\cap A_1]$. So it must be that $f_2(x)=\alpha <f_1(y)$ so that by definition $x\prec y$ so that $x\preccurlyeq y$ is true.

Case: $y\in A_2$. Then $y\in X\cap A_2$ so that $f_2(y)\in f_2[X\cap A_2]$ so that $f_2(y)\in B$. Thus $f_2(x)=\alpha \le f_2(y)$. Then if $f_2(x)=\alpha =f_2(y)$ then $x=y$ since $f_2$ is bijective. On the other hand if $f_2(x)=\alpha <f_2(y)$ then $x\prec y$ by definition. In either case we have $x\preccurlyeq y$.

Hence in all cases we have shown that $X$ has a $\prec$-least element so that $\prec$ is a well-ordering of $A$.

Now we show by transfinite induction that ${\aleph }_{\alpha }+{\aleph }_{\alpha }={\aleph }_{\alpha }$ for all ordinals $\alpha$. First it was already shown in a previous chapter that ${\aleph }_0+{\aleph }_0={\aleph }_0$. So now consider any $\alpha >0$ and suppose ${\aleph }_{\gamma }+{\aleph }_{\gamma }={\aleph }_{\gamma }$ for all $\gamma <\alpha$.

Then consider two disjoint sets $A_1$ and $A_2$ that are both equipotent to ${\omega }_{\alpha }$ and the well-ordering $\prec$ on $A=A_1\cup A_2$ as defined above, also again letting $f_1$ and $f_2$ be the isomorphisms from $A_1$ and $A_2$, respectively, to ${\omega }_{\alpha }$. Now let $a$ be any element of $A$ and define

Let $X_1=X\cap A_1$ and $X_2=X\cap A_2$ so that clearly $X_1$ and $X_2$ are disjoint and $X=X_1\cup X_2$. From this it follows from the definition of cardinal addition that $\left|X\right|=\left|X_1\right|+\left|X_2\right|$.

If $a\in A_1$ then define $\beta =f_1(a)\in {\omega }_{\alpha }$ so that $\beta <{\omega }_{\alpha }$. It follows from this and Lemma 5 that there is a $\gamma <\alpha$ such that $\left|\beta \right|\le {\aleph }_{\gamma }$ since $\alpha >0$, noting also that ${\aleph }_{\gamma }<{\aleph }_{\alpha }$ by the remarks following Definition 7.1.8. Now consider any $x_1\in X_1$ so that also $x_1\in X$. Then by definition $x_1\prec a$ so that by the definition of $\prec$ we have $f_1(x_1)<f_1(a)=\beta$ since $x_1\in A_1$ and $a\in A_1$. Hence $f_1(x_1)\in \beta$ so that $f_1[X_1]\subseteq \beta$ since $x_1$ was arbitrary. Hence, since $f_1$ is bijective, we have $\left|X_1\right|=\left|f_1[X_1]\right|\le \left|\beta \right|\le {\aleph }_{\gamma }$. Next, consider any $x_2\in X_2$ so that $x_2\in X$ and hence $x_2\prec a$. Then, again by the definition of $\prec$, we have that $f_2(x_2)<f_1(a)=\beta$ since $x_2\in A_2$ and $a\in A_1$. Hence $f_2(x_2)\in \beta$ so that $f_2[X_2]\subseteq \beta$ since $x_2$ was arbitrary. Thus we have $\left|X_2\right|=\left|f_2[X_2]\right|\le \left|\beta \right|\le {\aleph }_{\gamma }$ since $f_2$ is bijective.

A similar argument shows that $\left|X_1\right|\le {\aleph }_{\gamma }$ and $\left|X_2\right|\le {\aleph }_{\gamma }$ for some $\gamma <\alpha$ in the case when $a\in A_2$. However, in this case we must set $\beta =f_2(a)+1$, noting that $\beta \in {\omega }_{\alpha }$ since $f_2(a)\in {\omega }_{\alpha }$ and ${\omega }_{\alpha }$ is a limit ordinal by Lemma 6.

Thus in all cases we have

Thus we have shown that $\left|X\right|<{\aleph }_{\alpha }=\left|{\omega }_{\alpha }\right|$ for any $a\in A$, and hence $\left|{\omega }_{\alpha }\right|\nleqq \left|X\right|$ by Corollary 8 since ${\omega }_{\alpha }$ and $X$ are both well-ordered. If $\delta$ is the ordinal isomorphic to $(A,\prec )$ (which exists by Theorem 6.3.1 since we have shown that $\prec$ is a well-ordering), then it follows from the contrapositive of Lemma 2 that $\delta \le {\omega }_{\alpha }$ and hence $\left|A\right|=\left|\delta \right|\le \left|{\omega }_{\alpha }\right|={\aleph }_{\alpha }$. Thus we have

Since obviously $0\le {\aleph }_{\alpha }$ it follows again from property (d) in section 5.1 that

Hence, by the Cantor-Bernstein Theorem we have that ${\aleph }_{\alpha }={\aleph }_{\alpha }+{\aleph }_{\alpha }$, which completes the inductive step. □