Exercise 7.6

Proof. Following the hint, we define two sequences of sets recursively:

and

for integer $n>1$. Now define a function from $A$ to $B$ by

for any $x\in A$.

First, we show that $B$ really is the range of $h$ as this is not readily apparent. So consider any $x\in A$. Clearly if $x\in A_n-B_n$ for some $n\in {\mathbb{Z}}_{\text{+}}$ then $h(x)=f(x)\in B$ since $B$ is the range of $f$. On the other hand, if this is not the case then $x\notin A_n-B_n$ for any $n\in {\mathbb{Z}}_{\text{+}}$, and $h(x)=x$. In particular, $x\notin A_1-B_1=A-B$ so that it has to be that $h(x)=x\in B$, for otherwise, it would be that $x\in A-B$ since $x\in A$. Hence, in either case, $h(x)\in B$ so that $h$ is indeed a function from $A$ to $B$.

To show that $h$ is injective, consider any $x,x^{\prime }\in A$ where $x\ne x^{\prime }$.

1.

Case: $x\in A_n-B_n$ for some $n\in {\mathbb{Z}}_{\text{+}}$. Then by definition $h(x)=f(x)$.

(a)

Case: $x^{\prime }\in A_m-B_m$ for some $m\in {\mathbb{Z}}_{\text{+}}$. Then we clearly have $h(x)=f(x)\ne f(x^{\prime })=h(x^{\prime })$ since $f$ is injective and $x\ne x^{\prime }$.

(b)

Case: $x^{\prime }\notin A_m-B_m$ for all $m\in {\mathbb{Z}}_{\text{+}}$. Then $h(x^{\prime })=x^{\prime }$. Since $x\in A_n$, we have that $f(x)\in f(A_n)=A_{n+1}$. If it were the case that $f(x)\in B_{n+1}=f(B_n)$, then there would be a $y\in B_n$ such that $f(y)=f(x)$. Of course, since $f$ is injective, it would have to be that $x=y\in B_n$, which we know is not the case since $x\in A_n-B_n$. Hence it has to be that $f(x)\notin B_{n+1}$ so that $f(x)\in A_{n+1}-B_{n+1}$. From this, it is clear that it cannot be that $x^{\prime }=f(x)$ so that $h(x^{\prime })=x^{\prime }\ne f(x)=h(x)$.

2.

Case: $x\notin A_n-B_n$ for all $n\in {\mathbb{Z}}_{\text{+}}$. Then by definition $h(x)=x$.

(a)

Case: $x^{\prime }\in A_m-B_m$ for some $m\in {\mathbb{Z}}_{\text{+}}$. This is the same as case 1b above with the roles of $x$ and $x^{\prime }$ reversed.

(b)

Case: $x^{\prime }\notin A_m-B_m$ for all $m\in {\mathbb{Z}}_{\text{+}}$. Then clearly $h(x)=x\ne x^{\prime }=h(x^{\prime })$.

Thus in all cases $h(x)\ne h(x^{\prime })$, which shows that $h$ is injective since $x$ and $x^{\prime }$ were arbitrary.

To show that $h$ is also surjective, consider any $y\in B$, noting that also $y\in A$ since $B\subset A$.

Case: $y\in A_n-B_n$ for some $n\in {\mathbb{Z}}_{\text{+}}$. It cannot be that $n=1$ since then $y\in A_1-B_1=A-B$, and we know that $y\in B$. Hence $n>1$ so that $n-1\in {\mathbb{Z}}_{\text{+}}$. Since $y\in A_n=f(A_{n-1})$, there is an $x\in A_{n-1}$ where $f(x)=y$. Suppose for a moment that $x\in B_{n-1}$ so that $y=f(x)\in f(B_{n-1})=B_n$, which we know not to be the case. Thus it must be that $x\notin B_{n-1}$ so that $x\in A_{n-1}-B_{n-1}$ and so by definition $h(x)=f(x)=y$.

Case: $y\notin A_n-B_n$ for all $n\in {\mathbb{Z}}_{\text{+}}$. Then clearly $h(y)=y$ by definition.

This shows that $h$ is surjective since $y$ was arbitrary.

Therefore it has been shown that $h$ is a bijection from $A$ to $B$, which shows that they have the same cardinality by definition. □

Proof. Clearly, $f$ is a bijection from $A$ to $f(A)$ since $f$ is injective. Also, clearly the function $g\circ f$ is an injective function from $C$ into $f(A)$ since both $f$ and $g$ are injective. Noting that obviously $f(A)\subset C$, it then follows from part (a) that $C$ and $f(A)$ have the same cardinality so that there is a bijection $h:f(A)\to C$. We then have that $h\circ f$ is a bijection from $A$ to $C$ so that they have the same cardinality by definition. □