Exercise 7.1.6

Proof. Suppose that $R$ is a well-ordering of $A$.

$\text{(→)}$ Suppose that $f$ is a function from $A$ onto $B$. If $A$ is empty then clearly $B$ must be as well or else $f$ could not be onto. Thus we have $\left|B\right|=\left|\text{∅}\right|=0\le 0=\left|\text{∅}\right|=\left|A\right|$. So we can assume that $A$ is nonempty so that if $B$ is empty then $\left|B\right|=\left|\text{∅}\right|=0<\left|A\right|$. Hence we can assume that $B$ is nonempty as well.

Then, for each $b\in B$, define the set $A_b=\left\{a\in A\mid f(a)=b\right\}$, which clearly not empty since $f$ is onto. Then, since $R$ is a well-ordering of $A$ and $A_b\subseteq A$, there is a unique least element of $a_b$ of $A_b$ according to $R$. We then define $g:B\to A$ by simply setting $g(b)=a_b$ for any $b\in B$.

We then claim that $g$ is injective. So consider $b_1$ and $b_2$ in $B$ where $b_1\ne b_2$. Then since $a_{b_1}\in A_{b_1}$ clearly $f(a_{b_1})=b_1$. Similarly $f(a_{b_2})=b_2$ so that clearly $a_{b_1}\ne a_{b_2}$ since $f$ is a function and $b_1\ne b_2$. Hence $g(b_1)=a_{b_1}\ne a_{b_2}=g(b_2)$, which shows that $g$ is injective since $b_1$ and $b_2$ were arbitrary. Then by definition $\left|B\right|\le \left|A\right|$ as desired.

$\text{(←)}$ Now suppose that $\left|B\right|\le \left|A\right|$ so that there is an injective $f:B\to A$. If $B$ is empty then clearly it has to be that $\left|B\right|=\left|\text{∅}\right|=0\le \left|A\right|$ regardless of $A$. So we can assume that $B$ is nonempty so that there is a $b\in B$. Since $f$ is injective, the inverse $f^{-1}$ is a function from $\mathrm{ran}(f)$ onto $B$. Now we construct a function $g:A\to B$ by setting

for any $x\in A$. It should be clear that $g$ maps $A$ onto $B$ since, for any $b\in B$, we have $f(b)\in \mathrm{ran}(f)$ (hence also $f(b)\in A$) so that $g(f(b))=f^{-1}(f(b))=b$. □

Proof. Suppose to the contrary that there is a function $f$ from $A$ onto $\alpha$. Then since $0<(A)\le \alpha$ clearly $0\in (A)$ and $(A)\subseteq \alpha$. So we define a function $g:A\to (A)$ by

for any $a\in A$. Clearly each $g(a)\in (A)$ but we also claim that $g$ is onto. To this end consider any $\beta \in (A)$. Since $(A)\subseteq \alpha$ we have that $\beta \in \alpha$ also. Then, since $f$ is onto $\alpha$ there is an $a\in A$ such that $f(a)=\beta$. Since $f(a)=\beta \in (A)$ it follows by definition that $g(a)=f(a)=\beta$. Since $\beta$ was arbitrary this shows that $g$ is onto. However, the existence of $g$ contradicts the definition of $(A)$ so that it must be that there is no such function from $A$ onto $\alpha$. □

Proof. Suppose to the contrary that $(A)$ is not an initial ordinal so that there is an $\alpha <(A)$ such that $\left|\alpha \right|=\left|(A)\right|$. Let $f$ then be a bijection from $\alpha$ onto $(A)$. Also since $\alpha <(A)$ it follows from the definition of $(A)$ that there is a function $g$ from $A$ onto $\alpha$ (since otherwise $(A)$ would not be the least such ordinal for which such a function does not exist). But then $f\circ g$ is a function from $A$ onto $(A)$, which contradicts the definition of $(A)$. Hence it has to be that $(A)$ is in fact an initial ordinal. □

Proof. Suppose to the contrary that $h(A)>(A)$. Then by the definition of $h(A)$ there is a subset $X\subseteq A$ such that $(A)$ is equipotent to $X$. So let $f$ be a bijection from $(A)$ to $X$. We then define a function $g:A\to (A)$ by

for any $a\in A$, noting that $0<(A)$ so that $0\in (A)$. Clearly $g$ is into $(A)$ but we also claim that it is onto. So consider any $\alpha \in (A)$ and let $a=f(\alpha )$ so that $a\in X$ and therefore $a\in A$ since $X\subseteq A$. We then have $g(a)=f^{-1}(a)=f^{-1}(f(\alpha ))=\alpha$ since $a\in X$. Since $\alpha$ was arbitrary this shows that $g$ is onto. However, the existence of $g$ contradicts the definition of $(A)$ so that it must be that in fact $h(A)\le (A)$ as desired. □

Proof. We show that $(A)\le h(A)$, from which the result clearly follows since also $(A)\ge h(A)$ by part (c). So suppose to the contrary that $(A)>h(A)$. Then by the definition of $(A)$ it follows that there is a function from $A$ onto $h(A)$. It then follows from Lemma 1 that $\left|h(A)\right|\le \left|A\right|$ since $A$ is well-orderable. However, this contradicts Lemma ?? so that it must be that $(A)\le h(A)$ so that the result follows. □

Proof. Consider any set $A$ and let $S$ denote the set of well-orderings of some partition of $A$ into equivalence classes, noting that it could be that $S=\varnothing$. Since each $R\in S$ is isomorphic to a unique ordinal, let $H$ be the set of ordinals that are isomorphic to some $R\in S$, which exists by the Axiom Schema of Replacement. Then let $\alpha =\left\{0\right\}\cup H$ and we claim that $\alpha =(A)$.

First we show that $\alpha$ is indeed an ordinal number. Since $\alpha$ is a set of ordinals clearly it is well-ordered by Theorem 6.2.6d. We also must show that $\alpha$ is transitive, so consider any $\beta \in \alpha$. Then either $\beta =0$ or $\beta \in H$. If $\beta =0=\varnothing$ then clearly $\beta \subseteq \alpha$. On the other hand if $\beta \in H$ then there is a partition $P$ of $A$ and a well-ordering $R$ of $P$ such that $(P,R)$ is isomorphic to $(\beta ,<)$. Now consider any $\gamma \in \beta$ so that $\gamma <\beta$. It then follows that $\gamma$ is isomorphic to an initial segment of $\beta$ and therefore also to an initial segment $P^{\prime }$ of $P$ ordered by $R$. Let $L$ be the least element of $P$ (which is also the least element of $P^{\prime }$), which exists since $R$ is a well-ordering. Then let

i.e. $L^{\prime }$ is the set containing the elements of $L$ and any elements of $A$ that are not covered in the initial segment $P^{\prime }$. Then let

i.e. $P^{″}$ is $P^{\prime }$ but with $L$ replaced with $L^{\prime }$. It is easy to show that $P^{″}$ is a partition of $A$ and that it is isomorphic to $\gamma$ with the same ordering as $R$ except with $L$ replaced by $L^{\prime }$. Hence by definition we have that $\gamma \in \alpha$. Since $\gamma \in \beta$ was arbitrary this shows that $\beta \subseteq \alpha$, and since $\beta \in \alpha$ was arbitrary this shows that $\alpha$ is transitive and hence an ordinal number.

Now we show that there is no function from $A$ onto $\alpha$. So suppose to the contrary that there is such a function $f$. We then define the set

It is trivial to show that this is an equivalence relation on $A$ so that $A∕E$ is a partition of $A$ by Theorem 4.4.7. Moreover let $g$ be the mapping from $A∕E$ to $\alpha$ defined as follows: for any $B\in A∕E$ let $g(B)$ be the least element of $\left\{f(x)\mid x\in B\right\}$, noting that $\left\{f(x)\mid x\in B\right\}$ contains only a single element since $B$ is an equivalence class where $f(x)=f(y)$ for any $x$ and $y$ in $B$. It is trivial to show that $g$ is a bijective function so that we can well-order $A∕E$ according to the ordinal $\alpha$ since $\alpha$ is the range of $g$. However, it then follows by definition that $\alpha \in \alpha$, which contradicts Lemma 6.2.7. Hence it must be that there is no function from $A$ onto $\alpha$.

Lastly we show that there is a function from $A$ onto $\beta$ for every nonzero $\beta <\alpha$. So consider any such $\beta$ so that $\beta \in \alpha$. Then either $\beta =0$ or $\beta \in H$, but since $\beta$ is nonzero it must be that $\beta \in H$. Then by definition there is is a partition $P$ of $A$ and well-ordering $R$ of $P$ such that $(P,R)$ is isomorphic to $(\beta ,<)$. Let $f$ then be the isomorphism from $P$ to $\beta$. We then define the mapping $g:A\to \beta$ as follows: for any $a\in A$ there is a unique $B\in P$ such that $a\in B$ since $P$ is a partition of $A$. We then set $g(a)=f(B)$. It is easy to show that $g$ is onto.

It follows from what has been shown that indeed $\alpha =(A)$. □