Exercise 6.1.3

Proof. Consider any initial segment $S$ of $(A,<)$. Then by Lemma 6.1.2 there is an $n\in A\subseteq 𝑵$ such that $S=\left\{k\in A\mid k<n\right\}$. So consider any $k\in S$ so that $k\in A\subseteq 𝑵$ and $k<n$. Then by the definition of $<$ we have that $k\in n$. Since $k$ was arbitrary this shows that $S\subseteq n$ so that $|S|\le n$. From this it clearly follows that $S$ is finite since $n$ is. □

Proof. Throughout the following let $<$ denote the standard well-ordering on $𝑵$ and let $R$ be the set of all well-orderings defined on $𝑵$.

First we construct an injective $F:R\to {𝑵}^{𝑵}$. So for any $\prec \in R$ we have that $(𝑵,<)$ and $(𝑵,\prec )$ are two well-orderings of $𝑵$. Consider then Theorem 6.1.3. We show that (c) cannot be the case, i.e. that an initial segment of $(𝑵,<)$ cannot be isomorphic to $(𝑵,\prec )$. So suppose that this is the case so that $f$ is an isomorphism from an initial segment $S$ of $(𝑵,<)$ to $(𝑵,\prec )$. Then by Lemma 1, $S$ is finite whereas $𝑵$ is infinite, but since $f$ is a bijection this is impossible since it would imply that $|S|=|𝑵|={\aleph }_0$. Hence it must be that (a) $(𝑵,<)$ is isomorphic to $(𝑵,\prec )$ or (b) the former is isomorphic to an initial segment of the latter. In either case such an isomorphism $f$ is unique by Corollary 6.1.5c. So define $F(\prec )=f$, noting that clearly $f\in {𝑵}^{𝑵}$.

Now we show that $F$ is injective by considering two ${\prec }_1,{\prec }_2\in R$ where ${\prec }_1\ne {\prec }_2$. Without loss of generality we can the assume that there is an $(n,m)\in {\prec }_1$ where $(n,m)\notin {\prec }_2$. Thus $n{\prec }_{1}m$ but since ${\prec }_2$ is a linear, strict ordering and $\neg <!--\; FUNCTION\; APPLICATION\; -->(n{\prec }_{2}m)$ it has to be that $m{\prec }_{2}n$ since $n\ne m$. Now let $f_1=F({\prec }_1)$ and $f_2=F({\prec }_2)$. Since both $f_1$ and $f_2$ are bijective there are $k_1,l_1,k_2,l_2\in 𝑵$ such that

Since $f_1$ is an isomorphism and $f_1(k_1)=n{\prec }_{1}m=f_1(l_1)$ it follows that

and similarly since $f_2$ is an isomorphism and $f_2(l_2)=m{\prec }_{2}n=f_2(k_2)$ it follows that

Now we claim that either $f_1(k_1)\ne f_2(k_1)$ or $f_1(l_1)\ne f_2(l_1)$. Either case shows that $F({\prec }_1)=f_1\ne f_2=F({\prec }_2)$ so that $F$ is injective. To this end suppose that $f_1(k_1)=f_2(k_1)=n=f_2(k_2)$. Then since $f_2$ is injective it follows that $k_1=k_2$. Hence with the above we have

so that $m=f_2(l_2){\prec }_2{f}_2(l_1)$ and hence $m\ne f_2(l_1)$. Thus we have $f_1(l_1)=m\ne f_2(l_1)$ so that the disjunction is shown (since $\neg <!--\; FUNCTION\; APPLICATION\; -->P\to Q\equiv P\vee Q$) and $F$ is injective.

Hence since $F:R\to {𝑵}^{𝑵}$ is injective we have that

by Theorem 5.2.2c.

Now suppose that $B$ is the set of all bijections from $𝑵$ to $𝑵$. We then construct an injective $G:2^{𝑵}\to B$. So for any infinite sequence $a\in 2^{𝑵}$ we define an $f\in {𝑵}^{𝑵}$ by

for $n\in 𝑵$, i.e we swap $2n$ and $2n+1$ if $a_n=1$ and leave them alone if $a_n=0$. We then assign $G(a)=f$. It is trivial but tedious to show that $f$ is bijective so that indeed $f\in B$.

Now consider any $a,b\in 2^{𝑵}$ where $a\ne b$ and let $f=G(a)$ and $g=G(b)$. Since $a\ne b$ there is an $n\in 𝑵$ where $a_n\ne b_n$. Without loss of generality we can assume that $a_n=0\ne 1=b_n$. Then we have

since $a_1=0$ but $b_n=1$. Hence $f\ne g$ so that $G$ is injective, from which it follows that $|2^{𝑵}|\le |B|$.

Lastly we construct an injective $H:B\to R$. So for an $f\in B$ define

and set $H(f)=\prec$. Clearly by definition since $f$ is bijective it is an isomorphism from $(𝑵,<)$ to $(𝑵,\prec )$. This means that $(𝑵,\prec )$ is isomorphic to $(𝑵,<)$ so that clearly $\prec$ is a well-ordering since $<$ is. Hence indeed $H(f)=\prec \in R$.

Now we show that $H$ is injective. So consider $f_1,f_2\in B$ where ${\prec }_1=H(f_1)=H(f_2)={\prec }_2$. Then $f_1^{-1}\circ f_2$ is an isomorphism from $(𝑵,{\prec }_1)$ to $(𝑵,{\prec }_2)$ But since ${\prec }_1={\prec }_2$ these are the same well-ordered set so that it follows from Corollary 6.1.5b that the only isomorphism between them is the identity $i_{𝑵}$. Hence $f_1^{-1}\circ f_2=i_{𝑵}$, from which it follows that $f_1=f_2$. Therefore $H$ is injective so that $|B|\le |R|$.

Putting this together results in

It then follows from the Cantor-Bernstein Theorem that $|R|=2^{{\aleph }_0}$ as desired. □