Exercise 10.11

Proof. $\text{(⇒)}$ Suppose that there is an injection $f:A\to B$ and $A\ne \varnothing$. Then there is an $a\in A$. We then construct a surjection $g:B\to A$ as follows. For any $y\in B$ if $b\in f(A)$ then there is a unique $x\in A$ where $y=f(x)$. It is unique since, if $x$ and $x^{\prime }$ are in $A$ where $f(x)=y=f(x^{\prime })$, then $x=x^{\prime }$ since $f$ is injective. So in this case set $g(y)=x$. If $b\notin f(A)$, then set $g(y)=a$. Clearly, $g$ is a function from $B$ to $A$. To show that $g$ is surjective, consider any $x\in A$ and let $y=f(x)$, which is clearly an element of $B$. Then, since obviously $y\in f(A)$ and $x$ is the unique $x\in A$ such that $y=f(x)$, we have that $g(y)=x$ by definition. This shows that $g$ is surjective since $x$ was arbitrary.

$\text{(⇐)}$ Now suppose that $g:B\to A$ is surjective. We then construct an injection $f:A\to B$ as follows. For any $x\in A$ we have that the set $B_x=\left\{y\in B\mid g(y)=x\right\}$ is nonempty since $g$ is surjective. Hence $B_x$ has a unique smallest element $y$ since it is a nonempty subset of $B$ and $B$ is well-ordered. So simply set $f(x)=y$. Clearly, $f$ is a function from $A$ to $B$. To show that $f$ is injective, consider $x,x^{\prime }\in A$ where $x\ne x^{\prime }$. Then clearly the sets $B_x$ and $B_{x^{\prime }}$ have to be disjoint for otherwise there would be a $y\in B$ where $g(y)=x$ and $g(y)=x^{\prime }$, which is impossible if $x\ne x^{\prime }$ since $g$ is a function. Hence, since $f(x)$ and $f(x^{\prime })$ are defined to be the smallest elements of $B_x$ and $B_{x^{\prime }}$, respectively, we have $f(x)\ne f(x^{\prime })$. This shows that $f$ is injective since $x$ and $x^{\prime }$ were arbitrary. □

Proof. First suppose that $A$ and $B$ are each well-ordered, which follows from the well-ordering theorem. Also, suppose that $A$ and $B$ do not have the same cardinality so that it suffices to show that either $B$ has greater cardinality than $A$ or vice versa. If $A=\varnothing$ then it cannot be that $B=\varnothing$ as well since then they would have the same cardinality ($\text{∅}$ would be a trivial bijection between them). Hence $B\ne \varnothing$ so that clearly $B$ has greater cardinality than $A$. Thus in what follows assume that $A\ne \varnothing$.

Suppose that there is an injection from $A$ to $B$. Then there cannot be an injection from $B$ to $A$ since, if there were, then $A$ and $B$ would have the same cardinality by the Cantor-Schroeder-Bernstein Theorem (shown in Exercise 7.6 part (b)). Thus $B$ has greater cardinality than $A$ by definition.

On the other hand, if there is no injection from $A$ to $B$ then there is no surjection from $B$ to $A$ by Lemma 1 since they are both well-ordered and $A\ne \varnothing$. It then clearly follows that no section of $B$ can be a surjection onto $A$ since then any extension of such a function to all of $B$ would also be a surjection onto $A$. From this, we have by Exercise 10.10 that there is a unique function $h:B\to A$ with the property that

where of course $S_x$ is the section of $B$ by $x$.

We claim that $h$ is injective. So consider any $y$ and $y^{\prime }$ in $B$ where $y\ne y^{\prime }$. Without loss of generality, we can assume that $y<y^{\prime }$ (by the well-ordering on $B$). It then follows that $y\in S_{y^{\prime }}$ so that clearly $h(y)\in h(S_{y^{\prime }})$. However, we have that $h(y^{\prime })$ is the smallest element of $A-h(S_{y^{\prime }})$ so that obviously $h(y^{\prime })\notin h(S_{y^{\prime }})$. Hence it must be that $h(y)\ne h(y^{\prime })$, which shows that $h$ is injective since $y$ and $y^{\prime }$ were arbitrary.

Therefore there is an injection from $B$ to $A$ but none from $A$ to $B$ so that $A$ has greater cardinality than $B$ by definition. This shows the desired result since these cases are exhaustive. □