Exercise 10.6

Proof. If we let $C=A-B$, then clearly $A=C\cup B$. If $C$ were countable then $A=C\cup B$ would be countable by Theorem 7.5 since $B$ is also countable. Since we know that $A$ is uncountable it, therefore, must be that $C=A-B$ is uncountable as well. □

Proof. Suppose to the contrary that $S_{\mathrm{\Omega }}$ does have a largest element $\alpha$. Then, for any $x\in S_{\mathrm{\Omega }}$, we have that $x\le \alpha$. Hence either $x\in \left\{y\in S_{\mathrm{\Omega }}\mid y<\alpha \right\}=S_{\alpha }$ or $x=\alpha$. Therefore $S_{\mathrm{\Omega }}=S_{\alpha }\cup \left\{\alpha \right\}$ since clearly both $S_{\alpha }$ and $\left\{\alpha \right\}$ are both subsets of $S_{\mathrm{\Omega }}$. Now since $S_{\alpha }$ is a section of $S_{\mathrm{\Omega }}$, it is countable. Since $\left\{\alpha \right\}$ is also clearly countable, it follows from Theorem 7.5 that their union $S_{\alpha }\cup \left\{\alpha \right\}=S_{\mathrm{\Omega }}$ is countable. But this contradicts the fact that $S_{\mathrm{\Omega }}$ is uncountable! Hence it has to be that $S_{\mathrm{\Omega }}$ has no largest element as desired. □

Proof. Consider any $\alpha \in S_{\mathrm{\Omega }}$. Let $T_{\alpha }=\left\{x\in S_{\mathrm{\Omega }}\mid \alpha <x\right\}$ so that we must show that $T_{\alpha }$ is uncountable. Let ${\overline{S}}_{\alpha }=S_{\alpha }\cup \left\{\alpha \right\}$ so that clearly we have that ${\overline{S}}_{\alpha }=\left\{x\in S_{\mathrm{\Omega }}\mid x\le \alpha \right\}$. It is then easy to show that $T_{\alpha }=S_{\mathrm{\Omega }}-{\overline{S}}_{\alpha }$. Now, since $S_{\alpha }$ is a section of $S_{\mathrm{\Omega }}$, it is countable so that clearly ${\overline{S}}_{\alpha }=S_{\alpha }\cup \left\{\alpha \right\}$ is also countable by Theorem 7.5. Then, since $S_{\mathrm{\Omega }}$ itself is uncountable, it follows that $T_{\alpha }=S_{\mathrm{\Omega }}-{\overline{S}}_{\alpha }$ is also uncountable by Lemma 1 . □

Proof. First, we show that $X_0$ is not bounded above. Assume the contrary so that $\alpha \in S_{\mathrm{\Omega }}$ is an upper bound of $X_0$. It then follows that the set $T_{\alpha }=\left\{x\in S_{\mathrm{\Omega }}\mid \alpha <x\right\}$ is such that every element of $T_{\alpha }$ has an immediate predecessor since otherwise there would be a $\beta \in T_{\alpha }$ where $\beta \in X_0$ so that $\alpha$ would not be an upper bound of $X_0$ since then $\alpha <\beta$.

Now, we know from part (a) that $S_{\mathrm{\Omega }}$ has no largest element so it follows from Exercise 10.2 that every element of $S_{\mathrm{\Omega }}$ has an immediate successor. Since $T_{\alpha }\subset S_{\mathrm{\Omega }}$ it follows that each element $x\in T_{\alpha }$ has an immediate successor $y$. Moreover, we then have that $\alpha <x<y$ so that $y\in T_{\alpha }$ also. Hence every element of $T_{\alpha }$ has an immediate successor in $T_{\alpha }$.

Now, we know that $T_{\alpha }$ is uncountable by part (b) so that it has a smallest element $\beta$ since it is then a nonempty subset of the well-ordered $S_{\mathrm{\Omega }}$. We derive a contradiction by showing that $T_{\alpha }$ has the same order type as ${\mathbb{Z}}_{\text{+}}$ and is thus countable. We do this by defining an increasing bijection $f:{\mathbb{Z}}_{\text{+}}\to T_{\alpha }$. First, set $f(1)=\beta$ and then set $f(n)$ to the immediate successor of $f(n-1)$ for $n>1$, which was shown to exist above. Then the function $f$ uniquely exists by the principle of recursive definition. Clearly we have that $f(n+1)>f(n)$ for all $n\in {\mathbb{Z}}_{\text{+}}$ since $f(n+1)$ is the immediate successor of $f(n)$. Hence $f$ is increasing and therefore also injective.

To show that $f$ is surjective suppose the contrary so that the set $T_{\alpha }-f({\mathbb{Z}}_{\text{+}})$ is non-empty. Since clearly, this is a subset of the well-ordered $S_{\mathrm{\Omega }}$, it has a smallest element $y$. Now, we know that $f(1)=\beta$ so that $y\ne \beta$, and in fact $\beta <y$ since $\beta$ is the smallest element of $T_{\alpha }$. Since $y\in T_{\alpha }$ we know that it has an immediate predecessor $x$ and that $\alpha <\beta \le x$ so that $x\in T_{\alpha }$. However, it cannot be that $x\in T_{\alpha }-f({\mathbb{Z}}_{\text{+}})$ since $x<y$ and $y$ is the smallest element of $T_{\alpha }-f({\mathbb{Z}}_{\text{+}})$. Thus $x\in f({\mathbb{Z}}_{\text{+}})$ so that there is an $n\in {\mathbb{Z}}_{\text{+}}$ where $f(n)=x$. But then $f(n+1)=y$ since $y$ is the immediate successor of $x$. As this contradicts the fact that $y\notin f({\mathbb{Z}}_{\text{+}})$, it must be that $f$ is in fact surjective!

Therefore we have shown that $f$ is a bijection from ${\mathbb{Z}}_{\text{+}}$ to $T_{\alpha }$ so that $T_{\alpha }$ is countable. But we know from part (b) that $T_{\alpha }$ is uncountable. As mentioned above, this is a contradiction so it must be that indeed $X_0$ is not bounded above. From this, it immediately follows from the contrapositive of Theorem 10.3 that $X_0$ must be uncountable. □