Exercise 9.1.13

Proof. Since $n<\left|A\right|$, it follows that there is an injective function $f:n\to A$ but that $f$ cannot be onto. Thus there is an $a\in A$ such that $a\notin \mathrm{ran}(f)$. Noting that $n+1=n\cup \left\{n\right\}$, for any $k\in n+1$, define a mapping $g$ by

Clearly in either of these cases we have that $g(k)\in A$ so that $g$ is in fact a function from $n+1$ into $A$.

To see that $g$ is injective, consider any $k_1$ and $k_2$ in $n+1$ where $k_1\ne k_2$. If $k_1=n$ then $g(k_1)=a$ and it has to be that $k_2\in n$ since $k_2\ne k_1=n$. Hence clearly $g(k_2)=f(k_2)\in \mathrm{ran}(f)$ whereas $g(k_1)=a\notin \mathrm{ran}(f)$ so that $g(k_1)\ne g(k_2)$. If $k_1\in n$ but $k_2=n$ then this is analogous the previous case, so assume that also $k_2\in n$. Here clearly $g(k_1)=f(k_1)\ne f(k_2)=g(k_2)$ since $f$ is injective and $k_1\ne k_2$. Therefore, in all cases we have that $g(k_1)\ne g(k_2)$, which shows that $g$ is injective since $k_1$ and $k_2$ were arbitrary.

The existence of the injection $g$ thus shows that that $n+1\le \left|A\right|$ as desired. □

Proof. Suppose that $⟨A_i\mid i\in I⟩$ are mutually disjoint sets where $\left|A_i\right|={\kappa }_i$ for every $i\in I$, and that $⟨B_i\mid i\in I⟩$ are sets where $\left|B_i\right|={\lambda }_i$ for each $i\in I$. Since we have $\left|A_i\right|={\kappa }_i\le {\lambda }_i=\left|B_i\right|$ , we can assume that $A_i\subseteq B_i$ (for every $i\in I$). We show the result by constructing an injective function that maps ${\bigcup <!--\; FUNCTION\; APPLICATION\; -->}_{i\in I}{A}_i$ into ${\prod <!--\; FUNCTION\; APPLICATION\; -->}_{i\in I}{B}_i$, since we clearly would then have

by the definitions of cardinal sum and product, which is the desired result.

First, if $I=\varnothing$ then we have that ${\sum <!--\; FUNCTION\; APPLICATION\; -->}_{i\in I}{\kappa }_i=\left|{\bigcup }_{i\in \varnothing }{A}_i\right|=\left|\text{∅}\right|=0$. The only function with domain $I=\varnothing$ is $\text{∅}$ itself so that ${\prod <!--\; FUNCTION\; APPLICATION\; -->}_{i\in I}{\lambda }_i=\left|{\prod }_{i\in \varnothing }{B}_i\right|=\left|\left\{\text{∅}\right\}\right|=1$. Hence clearly ${\sum <!--\; FUNCTION\; APPLICATION\; -->}_{i\in I}{\kappa }_i=0\le 1={\prod }_{i\in I}{\lambda }_i$ so that the hypothesis is true. So assume in what follows that $I\ne \varnothing$ so that there is an $i_0\in I$.

Now, for every $i\in I$, since $1<{\kappa }_i\le {\lambda }_i=\left|B_i\right|$, it follows from Lemma 1 that $2\le \left|B_i\right|$. Hence, for each $i\in I$ we can choose two distinct elements ${\alpha }_i$ and ${\beta }_i$ from $B_i$, though this requires the Axiom of Choice. So, for any $x\in {\bigcup <!--\; FUNCTION\; APPLICATION\; -->}_{i\in I}{A}_i$, there is an $i_x\in I$ such that $x\in A_{i_x}$. Them, for any $i\in I$, set

and let $f(x)=⟨a_i\mid i\in I⟩$. Clearly, for any such $x$ and $i\in I$, we have $a_i=x\in A_{i_x}=A_i$ if $i=i_x$ so that $a_i\in B_i$ since $A_i\subseteq B_i$. In the other cases either $a_i={\alpha }_i\in B_i$ or $a_i={\beta }_i\in B_i$. Therefore $f(x)=⟨a_i\mid i\in I⟩\in {\prod <!--\; FUNCTION\; APPLICATION\; -->}_{i\in I}{B}_i$ so that $f$ is a function from ${\bigcup <!--\; FUNCTION\; APPLICATION\; -->}_{i\in I}{A}_i$ into ${\prod <!--\; FUNCTION\; APPLICATION\; -->}_{i\in I}{B}_i$.

We also claim that $f$ is injective. To see this, consider $x$ and $y$ in ${\bigcup <!--\; FUNCTION\; APPLICATION\; -->}_{i\in I}{A}_i$ where $x\ne y$, and let $i_x$ and $i_y$ be those elements of $I$ such that $x\in A_{i_x}$ and $y\in A_{i_y}$. Also let $f(x)=⟨a_i\mid i\in I⟩$ and $f(y)=⟨b_i\mid i\in I⟩$.

The following involves a lot of messy case work, so we shall number the cases for easy reference:

1.

Case: $i_x=i_y$. Then $a_{i_x}=x\ne y=b_{i_y}=b_{i_x}$.

2.

Case: $i_x\ne i_y$.

(a)

Case: $i_x\ne i_0$ and $i_y\ne i_0$.

i.

Case: $a_{i_x}=x={\alpha }_{i_x}$.

A.

Case: $b_{i_y}=y={\alpha }_{i_y}$. Then, since $i_x\ne i_y$ and $i_x\ne i_0$ and $y={\alpha }_{i_y}$, we have $b_{i_x}={\beta }_{i_x}\ne {\alpha }_{i_x}=a_{i_x}$.

B.

Case: $b_{i_y}=y\ne {\alpha }_{i_y}$. Then, since $i_0\ne i_x$ and $i_0=i_0$ and $x={\alpha }_{i_x}$, we have $a_{i_0}={\alpha }_{i_0}$. Also, since $i_0\ne i_y$ and $i_0=i_0$ and $y\ne {\alpha }_{i_y}$, we have $b_{i_0}={\beta }_{i_0}\ne {\alpha }_{i_0}=a_{i_0}$.

ii.

Case: $a_{i_x}=x\ne {\alpha }_{i_x}$.

A.

Case: $b_{i_y}=y={\alpha }_{i_y}$. This is analogous to case 2.a.i.B with $a_{i_x}=x$ and $b_{i_y}=y$ reversed so that again $a_{i_0}\ne b_{i_0}$.

B.

Case: $b_{i_y}=y\ne {\alpha }_{i_y}$. Then, since $i_x\ne i_y$ and $i_x\ne i_0$ and $y\ne {\alpha }_{i_y}$, we have $b_{i_x}={\alpha }_{i_x}\ne a_{i_x}$.

(b)

Case: $i_x\ne i_0$ and $i_y=i_0$.

i.

Case: $a_{i_x}=x={\alpha }_{i_x}$.

A.

Case: $b_{i_y}=y={\alpha }_{i_y}$. Since $i_x\ne i_y$ and $i_x\ne i_0$ and $y={\alpha }_{i_y}$, we have $b_{i_x}={\beta }_{i_x}\ne {\alpha }_{i_x}=a_{i_x}$.

B.

Case: $b_{i_y}=y\ne {\alpha }_{i_y}$. Since $i_y\ne i_x$ and $i_y=i_0$ and $x={\alpha }_{i_x}$, we have $a_{i_y}={\alpha }_{i_y}\ne b_{i_y}$.

ii.

Case: $a_{i_x}=x\ne {\alpha }_{i_x}$.

A.

Case: $b_{i_y}=y={\alpha }_{i_y}$. Since $i_y\ne i_x$ and $i_y=i_0$ and $x\ne {\alpha }_{i_x}$, we have $a_{i_y}={\beta }_{i_y}\ne {\alpha }_{i_y}=b_{i_y}$.

B.

Case: $b_{i_y}=y\ne {\alpha }_{i_y}$. Since $i_x\ne i_y$ and $i_x\ne i_0$ and $y\ne {\alpha }_{i_y}$, we have $b_{i_x}={\alpha }_{i_x}\ne a_{i_x}$.

(c)

Case: $i_x=i_0$ and $i_y\ne i_0$. This is analogous to the previous case 2.b with the roles of $i_x$ and $i_y$ reversed.

(d)

Case: $i_x=i_0$ and $i_y=i_0$. This is impossible since $i_x\ne i_y$.

Thus, in all cases, there is an $i\in I$ such that $a_i\ne b_i$ so that clearly $f(x)=⟨a_i\mid i\in I⟩\ne ⟨b_i\mid i\in I⟩=f(y)$. This shows that $f$ is injective since $x$ and $y$ were arbitrary. This completes the proof as described above. □