Exercise 9.7

Proof. Clearly the function that maps $a\in A$ to $\left\{a\right\}\in P\left(A\right)$ is an injection. However, we know from Theorem 7.8 that there is no injection from $P\left(A\right)$ to $A$. Together these show that $P\left(A\right)$ has greater cardinality than $A$ as desired. □

Proof. Suppose that $A$ is any uncountable set. Clearly $A$ is not finite for then it would be countable. Hence it is infinite and so there is a injection from ${\mathbb{Z}}_{\text{+}}$ to $A$ by Theorem 9.1. There also cannot be an injection from $A$ to ${\mathbb{Z}}_{\text{+}}$, for if there were then $A$ would be countable by Theorem 7.1. This shows that $A$ has greater cardinality than ${\mathbb{Z}}_{\text{+}}$ by definition. □

Proof. Since $A$ has greater cardinality than $B$, there is an injection $f:B\to A$. Likewise, since $B$ has greater cardinality than $C$, there is an injection $g:C\to B$. It then follows that $f\circ g$ is an injection of $C$ into $A$. Now suppose that $h:A\to C$ is injective. Then $g\circ h$ would be an injection of $A$ into $B$, which we know cannot exist since $A$ has greater cardinality than $B$. Hence it must be that no such injection $h$ exists, which shows that $A$ has greater cardinality than $C$ as desired. □

Proof. First we show that each $A_n$ is infinite by induction. Clearly $A_1={\mathbb{Z}}_{\text{+}}$ is infinite. Now assume that $A_n$ is infinite for $n\in {\mathbb{Z}}_{\text{+}}$ so that there is an injection $f:{\mathbb{Z}}_{\text{+}}\to A_n$ by Theorem 9.1. Then, by Lemma 1 , $A_{n+1}=P\left(A_n\right)$ has greater cardinality than $A_n$ so that there is an injection $g:A_n\to A_{n+1}$. Then $g\circ f$ is an injection from ${\mathbb{Z}}_{\text{+}}$ to $A_{n+1}$ so that $A_{n+1}$ is infinite as well by Theorem 9.1. This completes the induction.

Finally, for any $n\in {\mathbb{Z}}_{\text{+}}$ we have that $n+1>1$ so that $A_{n+1}=P\left(A_{(n+1)-1}\right)=P\left(A_n\right)$. Then clearly $A_{n+1}$ has greater cardinality than $A_n$ by Lemma 1 . This shows the desired result. □

Proof. Consider any $n\in {\mathbb{Z}}_{\text{+}}$. Clearly $A_n\subset A$ so that the identity function $i_{A_n}$ is an injection of $A_n$ into $A$. Now suppose for the moment that $g:A\to A_n$ is injective. Since clearly also $A_{n+1}\subset A$, it follows that $g\upharpoonright A_{n+1}$ is then an injection of $A_{n+1}$ into $A_n$. However this contradicts the proven fact that $A_{n+1}$ has greater cardinality than $A_n$. Hence it has to be that no such injection $g$ exists, which shows that $A$ has greater cardinality than $A_n$. Since $n$ was arbitrary, this shows the desired result. □