Exercise 5.2.1

Proof. Let $F$ denote the set of all finite sets of reals. First we construct an injective $f:F\to {𝑹}^{𝑵}$ So consider any $A\in F$. Then $|A|=n$ for an $n\in 𝑵$ so that there is a finite sequence $⟨a_k\mid k\in n⟩$ where $\mathrm{ran}(a)=A$. Now we define an infinite sequence of reals $â\in {𝑹}^{𝑵}$ by

so that clearly we have $\mathrm{ran}(â)=A$ as well. Note that this only works if $A\ne \varnothing$ since otherwise there is no $a_0$. In the case where $A=\varnothing$ we set ${â}_k=k$ for $k\in 𝑵$ so that $\mathrm{ran}(â)=𝑵$. In any case we set $f(A)=â$.

Now we claim that $f$ is injective. So consider any $A,B\in F$ where $A\ne B$. If one of them is the empty set, say $A$, then since $B$ is finite $m=\max <!--\; FUNCTION\; APPLICATION\; -->(\lceil \max <!--\; FUNCTION\; APPLICATION\; -->(B)\rceil +1,0)$ exists so that clearly $m\notin B$. Hence $m\notin \mathrm{ran}(f(B))=B$. However $m\in \mathrm{ran}(f(A))=𝑵$ since $m\in 𝑵$. It thus follows that $\mathrm{ran}(f(B))\ne \mathrm{ran}(f(A))$ so that $f(A)\ne f(B)$. On the other hand if neither $A$ nor $B$ is the empty set (but still $A\ne B$) then there is an $a\in A$ where $a\notin B$ or vice versa. Without loss of generality we need only consider the first case. Clearly then $a\in \mathrm{ran}(f(A))=A$ but $a\notin \mathrm{ran}(f(B))=B$ so that again $f(A)\ne f(B)$. Hence in all cases we’ve shown that $f$ is injective.

Thus we have that

where the last equality was shown in Theorem 5.2.3d. Now define

so that clearly $E\subseteq F$ and $|E|=|𝑹|$. Hence we have

by Exercise 4.1.3. Thus by the Cantor-Bernstein Theorem $|F|=2^{{\aleph }_0}$ as required. □