Exercise WO.8

Proof. First, to show that $\ll$ is well defined, suppose that $[(A,<)]\ll [(A^{\prime },{<}^{\prime })]$ and that $(B,\prec )\in [(A,<)]$ and $(B^{\prime },{\text{≺}}^{\prime })\in [(A^{\prime },{<}^{\prime })]$. Then $(A,<)$ has the same order type as a section of $(A^{\prime },{<}^{\prime })$ so that there is an order-preserving map $h$ from $A$ onto a section of $A^{\prime }$. We also then have that $(B,\prec )$ has the same order type as $(A,<)$ since they are in the same equivalence class. Thus there is an order-preserving bijection $f:B\to A$. Likewise, there is an order-preserving bijection from $g:B^{\prime }\to A^{\prime }$. It is then trivial to show that $g^{-1}\circ h\circ f$ is a bijection from $B$ onto a section of $B^{\prime }$ that preserves order. Hence $(B,\prec )$ has the same order type as a section of $(B^{\prime },{\text{≺}}^{\prime })$. Since $(B,\prec )$ and $(B^{\prime },{\text{≺}}^{\prime })$ were arbitrary elements in their respective equivalence classes, this shows that $\ll$ is well defined such that it does not matter which representatives we use from the equivalence classes.

Now consider any equivalence class $[(A,<)]$ in $E$. Then clearly it cannot be that $[(A,<)]\ll [(A,<)]$ since this would mean that $A$ has the same order type as a section of itself, which would contradict what was shown in Exercise WO.2 part (b). Thus $\ll$ is nonreflexive.

Next consider two distinct equivalence classes $[(A,<)]$ and $[(A^{\prime },{<}^{\prime })]$. Then it cannot be that $(A,<)$ and $(A^{\prime },{<}^{\prime })$ have the same order type, for then they would be the same equivalence class. Then, by EExercise WO.4 part (a), it must be that either $(A,<)$ has the same order type as a section of $(A^{\prime },{<}^{\prime })$ or vice-versa. Clearly then, in the former case $[(A,<)]\ll [(A^{\prime },{<}^{\prime })]$, and in the latter case $[(A^{\prime },{<}^{\prime })]\ll [(A,<)]$. This shows that $\ll$ has the comparability property.

Lastly, suppose that $[(A,<)]\ll [(A^{\prime },{<}^{\prime })]$ and $[(A^{\prime },{<}^{\prime })]\ll [(A^{\mathit{\prime \prime }},{<}^{\mathit{\prime \prime }})]$. Then $(A,<)$ has the same order type as section of $(A^{\prime },{<}^{\prime })$ so that there is an order-preserving bijection $f$ from $A$ onto a section of $A^{\prime }$ Likewise, there is an order-preserving bijection $g$ from $A^{\prime }$ onto a section of $A^{\mathit{\prime \prime }}$. It is then trivial to show that $f\circ g$ is an order-preserving bijection from $A$ onto a section of $A^{\mathit{\prime \prime }}$. It then clearly follows that $[(A,<)]\ll [(A^{\mathit{\prime \prime }},{<}^{\mathit{\prime \prime }})]$, which shows that $\ll$ is transitive.

Hence we have shown that $\ll$ satisfies all the requirements of a simple order. □

Proof. Following the hint, define the map $f:A\to E$ by setting

for any $x\in A$, noting that clearly $S_x(A)$ is well-ordered by the restricted $<$ so that the equivalence class is valid and in $E$.

Consider any $x$ and $y$ in $A$ where $x<y$. Then clearly $x\in S_y(A)$ but $x\notin S_x(A)$ (since it is not true that $x<x$) so that $S_x(A)$ and $S_y(A)$ are distinct sets. We also clearly have that $S_x(A)=S_x(S_y(A))$ so that $S_x(A)$ has the same order type (the identity function is the required order-preserving map) as a section of $S_y(A)$. Hence

so that $f$ preserves order since $x$ and $y$ were arbitrary.

Now we show that $f$ is onto $S_{\alpha }(E)$. So consider any equivalence class $[(B,\prec )]$ in $S_{\alpha }(E)$ and hence

so that by definition $(B,\prec )$ has the same order type as some section $S_x(A)$. Hence $[(B,\prec )]$ and $[(S_x(A),\text{restriction }<)]$ are the same equivalence class! Therefore

which of course shows the desired property since $[(B,\prec )]$ was arbitrary.

This shows that $f$ is an order-preserving map from $A$ onto $S_{\alpha }(E)$ so that they have the same order type. □

Proof. Consider any nonempty subset $D\subset E$. Thus there is an $\alpha =[(A,<)]\in D$. If $\alpha$ is the smallest element of $D$ then we are done, so assume that this is not the case so that there is a $\beta \in D$ where $\beta \ll \alpha$. Now, it was shown in part (b) that $(A,<)$ has the same order type as the section $S_{\alpha }(E)$ so this section must be well-ordered since $A$ is. Also we have that $\beta \in S_{\alpha }(E)$ since $\beta \ll \alpha$. Thus $\beta \in D\cap S_{\alpha }(E)$ so that $D\cap S_{\alpha }(E)$ is a nonempty subset of $S_{\alpha }(E)$ so has a smallest element $\gamma$ since $S_{\alpha }(E)$ is well-ordered. In particular, we of course have that $\gamma ⋘\beta$, where we use $⋘$ to denote $\ll$ or equal to.

We claim that $\gamma$ must be the smallest element of $D$. If not, then there is a $\delta \in D$ where $\delta \ll \gamma$. Of course, we also then have that $\delta \ll \gamma ⋘\beta \ll \alpha$ and hence $\delta \in S_{\alpha }(E)$. Therefore $\delta \in D\cap S_{\alpha }(E)$, but since $\delta \ll \gamma$ this contradicts the definition of $\gamma$ as the smallest element of $D\cap S_{\alpha }(E)$. So it must be that in fact, $\gamma$ is the smallest element of $D$, which shows that $E$ is well-ordered by $\ll$ since $D$ was an arbitrary subset. □

Proof. Following the hint, suppose that $E$ is countable so that there is a bijection $h:E\to {\mathbb{Z}}_{\text{+}}$. This of course gives rise to a well-ordering $<$ of $h(E)={\mathbb{Z}}_{\text{+}}$ by simply ordering its elements according to its bijection with $E$, which was shown to be well-ordered in part (c). Then we have that $({\mathbb{Z}}_{\text{+}},<)$ is an element of $A$ since ${\mathbb{Z}}_{\text{+}}$ is a subset of itself. Thus the equivalence class $\alpha =[({\mathbb{Z}}_{\text{+}},<)]$ is an element of $E$. But we know from part (b) that $({\mathbb{Z}}_{\text{+}},<)$ then has the same order type as the section $S_{\alpha }(E)$. Since we also know that $({\mathbb{Z}}_{\text{+}},<)$ has the same order type as $E$ itself, it follows that $E$ has the same order type as its section $S_{\alpha }(E)$ This was shown not to be possible in EExercise WO.2 (b) so that a contradiction has been reached. So it must be that in fact, $E$ is uncountable as desired □