Exercise 3.6.7 (Lesser or equal cardinality)

Proof .

We first prove the forward direction. Suppose $A$ has lesser or equal cardinality to $B$. Then there exists an injection $f:A\to B$. Since $f$ is one-to-one, we have, by part (d) of Proposition 3.6.14, that $\#(f(A))=\#(A)$. By definition of the forward image, we have $f(A)\subseteq B$. With both of them finite, we have, by part (c) of Proposition 3.6.14, that $\#(f(A))\le \#(B)$. But we had that $\#(f(A))=\#(A)$. Thus, substituting, we get $\#(A)\le \#(B)$, as was to be shown.

We now prove the backward direction. Suppose $\#(A)\le \#(B)$. Let $\#(A)=m$ and $\#(B)=n$, implying $m\le n$. By Definitions 3.6.1, 3.6.5, the following bijections exist: $g:A\to \{i\in \mathbb{N}:1\le i\le m\}$ and $h:\{j\in \mathbb{N}:1\le j\le n\}\to B$.

We want to show there exists an injection $f:A\to B$, since that would then imply $A$ has lesser or equal cardinality to $B$. We will show this by using $g$ above and a slightly different version of $h$ above.

Consider the partial function $h^{\prime }:\{j\in \mathbb{N}:1\le j\le m\}\to B$ defined by $h^{\prime }(j)=h(j)$ for all $1\le j\le m$. This is well-defined since $h(j)\in B$ for all $1\le j\le m$. Let us show that $h^{\prime }$ is injective. For any $j_1,j_2\in \{j\in \mathbb{N}:1\le j\le m\}$, suppose $h^{\prime }(j_1)=h^{\prime }(j_2)$; we want to show this implies $j_1=j_2$. By definition of $h^{\prime }$, this implies $h(j_1)=h(j_2)$. Since $h$ is injective (since it’s bijective), we have $j_1=j_2$. Hence, $h^{\prime }$ is injective.

The composition $f:=h^{\prime }\circ g$ is well-defined since $g$ maps into the domain of $h^{\prime }$. Thus, we have the mapping $f:A\to B$. Since both $h^{\prime }$ and $g$ are injective, we have, by Exercise 3.3.2, that $f$ is injective. This shows $A$ has lesser or equal cardinality to $B$, as was to be shown.