Exercise 9.8

Proof. Since $A$ and $B$ have the same cardinality there is a bijection $f:A\to B$. We define a bijection $g:P\left(A\right)\to P\left(B\right)$. So, for any $X\in P\left(A\right)$, set $g(X)=f(X)$. Clearly $f(X)\subset B$, since $B$ is the range of $f$, so that $g(X)=f(X)\in P\left(B\right)$ and hence $P\left(B\right)$ can be the range of $g$.

To show that $g$ is injective, consider sets $X$ and $Y$ in $P\left(A\right)$ so that $X,Y\subset A$. Also suppose that $X\ne Y$ so, without loss of generality, we can assume that there is an $x\in X$ where $x\notin Y$. Clearly $f(x)\in f(X)$ since $x\in X$. Were it the case that $f(x)\in f(Y)$ then there would be a $y\in Y$ such that $f(y)=f(x)$. But then we would have that $y=x$ since $f$ is injective and hence $x=y\in Y$, which we know not to be the case. Hence $f(x)\notin f(Y)$ so that it has to be that $g(X)=f(X)\ne f(Y)=g(Y)$ since $f(x)\in f(X)$. Since $X$ and $Y$ were arbitrary this shows that $g$ is injective.

To show that $g$ is surjective consider any $Y\in P\left(B\right)$ so that $Y\subset B$. Let $X=f^{-1}(Y)$, noting that $f^{-1}$ is a bijection from $B$ to $A$ since $f$ is bijective. Clearly $X\subset A$ since $A$ is the range of $f^{-1}$ so that $X\in P\left(A\right)$. Now consider any $y\in f(X)$ so that there is an $x\in X$ where $f(x)=y$. Then, since $X=f^{-1}(Y)$, there is a $y^{\prime }\in Y$ where $x=f^{-1}(y^{\prime })$, and hence $y=f(x)=f(f^{-1}(y^{\prime }))=y^{\prime }$. Thus $y=y^{\prime }\in Y$ so that $f(X)\subset Y$ since $y$ was arbitrary. Now consider $y\in Y$ and let $x=f^{-1}(y)$ so that clearly $x=f^{-1}(y)\in f^{-1}(Y)=X$. Moreover, $f(x)=f(f^{-1}(y))=y$ so that $y\in f(X)$. Thus $Y\subset f(X)$ as well since $y$ was arbitrary. This shows that $g(X)=f(X)=Y$, from which we conclude that $g$ is surjective since $Y$ was arbitrary.

Hence $g:P\left(A\right)\to P\left(B\right)$ is a bijection so that $P\left(A\right)$ and $P\left(B\right)$ have the same cardinality by definition. □

Proof. We show this using the Cantor-Schroeder-Bernstein (CSB) Theorem, which was proven in Exercise 7.6 part (b).

First, we construct an injective function $f$ from $ℝ$ to $P\left(\mathbb{Q}\right)$. For any $x\in ℝ$ let $Q=\left\{q\in \mathbb{Q}\mid q<x\right\}$ so that clearly $Q\subset \mathbb{Q}$ and hence $Q\in P\left(\mathbb{Q}\right)$. Therefore setting $f(x)=Q$ means that $f$ is a function from $ℝ$ to $P\left(\mathbb{Q}\right)$. To show that $f$ is injective consider $x,y\in ℝ$ where $x\ne y$. Without loss of generality, we can assume that $x<y$ so that there is a $q\in \mathbb{Q}$ where $x<q<y$ since the rationals are order-dense in the reals. Also set $Q=f(x)$ and $P=f(y)$. Since $q>x$ we have that $q\notin Q$. Analogously, since $q<y$ we have that $q\in P$. Thus it has to be that $f(x)=Q\ne P=f(y)$, which shows that $f$ is injective since $x$ and $y$ were arbitrary.

Now, it was shown in Exercise 7.1 that $\mathbb{Q}$ is countably infinite and thus has the same cardinality as ${\mathbb{Z}}_{\text{+}}$. From Lemma 1 it then follows that $P\left(\mathbb{Q}\right)$ has the same cardinality as $P\left({\mathbb{Z}}_{\text{+}}\right)$ so that there is a bijection $g:P\left(\mathbb{Q}\right)\to P\left({\mathbb{Z}}_{\text{+}}\right)$. Clearly then $g\circ f$ is an injection from $ℝ$ to $P\left({\mathbb{Z}}_{\text{+}}\right)$.

Now let $X=\left\{0,1\right\}$, and we construct an injection $h:X^{\omega }\to ℝ$. For any sequence $x=\left(x_1,x_2,\dots \right)\in X^{\omega }$ set $h(x)$ to the decimal expansion $0.x_1{x}_2{x}_3\dots$, where clearly each $x_n$ is the digit 0 or 1. Clearly $h(x)$ is a real number so that $h$ is a function from $X^{\omega }$ to $ℝ$. It is easy to see that $h$ is injective since different sequences will result in different decimal expansions. Since none of the expansions end in an infinite sequence of 9’s, clearly the corresponding real numbers will be different.

Now, it was shown in Exercise 7.3 that $P\left({\mathbb{Z}}_{\text{+}}\right)$ and $X^{\omega }$ have the same cardinality so that there is a bijection $i:P\left({\mathbb{Z}}_{\text{+}}\right)\to X^{\omega }$. It then follows that $h\circ i$ is an injection of $P\left({\mathbb{Z}}_{\text{+}}\right)$ into $ℝ$. Since we have shown the existence of both injections, the result follows from the CSB Theorem. □