Exercise WO.5

Proof. For any $(A,<)\in A$ we have that it is not equal to a section of itself since then it would then clearly have the same order type as its own section, which would violate Exercise .2 part (b). Hence it is not true that $(A,<)\prec (A,<)$ by definition, which shows that $\prec$ is nonreflexive.

Now consider $(A,<)$, $(A^{\prime },{<}^{\prime })$, and $(A^{\mathit{\prime \prime }},{<}^{\mathit{\prime \prime }})$ in $A$ where $(A,<)\prec (A^{\prime },{<}^{\prime })$ and $(A^{\prime },{<}^{\prime })\prec (A^{\mathit{\prime \prime }},{<}^{\mathit{\prime \prime }})$. Then $(A,<)$ is a section of $(A^{\prime },{<}^{\prime })$. Also $(A^{\prime },{<}^{\prime })$ is a section of $(A^{\mathit{\prime \prime }},{<}^{\mathit{\prime \prime }})$ so that clearly any section of $(A^{\prime },{<}^{\prime })$ is also a section of $(A^{\mathit{\prime \prime }},{<}^{\mathit{\prime \prime }})$. Since $(A,<)$ is such a section we have that $(A,<)$ is a section of $(A^{\mathit{\prime \prime }},{<}^{\mathit{\prime \prime }})$ so that $(A,<)\prec (A^{\mathit{\prime \prime }},{<}^{\mathit{\prime \prime }})$. This shows that $\prec$ is transitive.

This completes the proof that $\prec$ is a strict partial order. □

Proof. First we must show that $B^{\prime }$ is simply ordered by ${<}^{\prime }$.

First consider any $(x,y)\in {<}^{\prime }$ so that there is a $(B,<)\in B$ where $(x,y)\in <$ and $x,y\in B$. Clearly then $x$ and $y$ are in the union $B^{\prime }$ so that $(x,y)\in B^{\prime }\times B^{\prime }$. This shows that ${<}^{\prime }\subset B^{\prime }\times B^{\prime }$ so that ${<}^{\prime }$ is a relation on $B^{\prime }$.

Next consider any $x$ and $y$ in $B^{\prime }$ where $x\ne y$. Then there are well-ordered sets $(B_1,{<}_1)$ and $(B_2,{<}_2)$ in $B$ where $x\in B_1$ and $y\in B_2$. Since $B$ is simply ordered by $\prec$ we have that $(B_1,{<}_1)\prec (B_2,{<}_2)$ or $(B_2,{<}_2)\prec (B_1,{<}_1)$. Without loss of generality, we can assume the former case (since otherwise, we can just swap the roles of $x$ and $y$). Then $(B_1{<}_1)$ is a section of $(B_2,{<}_2)$ and is thus also a subset so that $x,y\in B_2$, It then follows that $x$ and $y$ are comparable by ${<}_2$ since $x\ne y$ and ${<}_2$ is a well-order and therefore a simple order. Thus $(x,y)$ or $(y,x)$ are in ${<}_2$. Since ${<}^{\prime }$ is the union of all relations $<$ where $(B,<)\in B$, clearly we have that $(x,y)$ or $(y,x)$ are in ${<}^{\prime }$ since ${<}_2$ is such a relation. This shows that ${<}^{\prime }$ has the comparability property.

Now consider any $x\in B^{\prime }$ so that there is a $(B,<)\in B$ where $x\in B$. Consider also any $(B^{\mathit{\prime \prime }},{<}^{\mathit{\prime \prime }})\in B$. Then, since $B$ is simply ordered, it follows that $(B,<)$ and $(B^{\mathit{\prime \prime }},{<}^{\mathit{\prime \prime }})$ are comparable in $\prec$. If $(B,<)\prec (B^{\mathit{\prime \prime }},{<}^{\mathit{\prime \prime }})$ then $(B,<)$ is a section of $(B^{\mathit{\prime \prime }},{<}^{\mathit{\prime \prime }})$ so that $x\in B^{\mathit{\prime \prime }}$ as well. Then it cannot be that $x{<}^{\mathit{\prime \prime }}x$ since ${<}^{\mathit{\prime \prime }}$ is a simple order. If $(B^{\mathit{\prime \prime }},{<}^{\mathit{\prime \prime }})\prec (B,<)$ then $(B^{\mathit{\prime \prime }},{<}^{\mathit{\prime \prime }})$ is a section of $(B,<)$. If $x\in B^{\mathit{\prime \prime }}$ then again it cannot be that $x{<}^{\mathit{\prime \prime }}x$ since ${<}^{\mathit{\prime \prime }}$ is a simple order. If $x\notin B^{\mathit{\prime \prime }}$ then $(x,x)\notin {<}^{\mathit{\prime \prime }}$ since it is a relation on $B^{\mathit{\prime \prime }}$. Thus in all cases and sub-cases it is not true that $x{<}^{\mathit{\prime \prime }}x$ so that $x{<}^{\prime }x$ does not hold since ${<}^{\mathit{\prime \prime }}$ was arbitrary and ${<}^{\prime }$ is their union. This shows that ${<}^{\prime }$ is nonreflexive.

Lastly, suppose that $x{<}^{\prime }y$ and $y{<}^{\prime }z$. Then it has to be that there is a $(B_1,{<}_1)$ and $(B_2,{<}_2)$ in $B$ where $z{<}_{1}y$ and $y{<}_{2}z$. Then $(B_1,{<}_1)$ and $(B_2,{<}_2)$ are comparable in $\prec$ since $B$ is simply ordered. Hence one is a section of the other so that, in either case, it follows that $x<y$ and $y<z$ where either $<={<}_1$ or $<={<}_2$. Then clearly $x<z$ since both ${<}_1$ and ${<}_2$ are transitive since they are simple orders. Thus $x{<}^{\prime }z$ since ${<}^{\prime }$ is the union of all the orders in $B$ and $<$ is such an order. This shows that ${<}^{\prime }$ is transitive.

This completes the proof that ${<}^{\prime }$ is a simple order on $B^{\prime }$. To show that it is a well-order, consider any nonempty subset $A\subset B^{\prime }$. Then there is an $x\in A$ so that $x\in B^{\prime }$ as well. It then follows that there is a $(B,<)\in B$ where $x\in B$. Then clearly $B\cap A$ is a nonempty subset of $B$ since $x\in B$ and $x\in A$. Let $b$ be the $<$-smallest element in $B\cap A$, and we claim that this is the smallest element of $A$ by ${<}^{\prime }$. First, obviously $b\in A$ since $b\in B\cap A$. Next, consider any $y\in A$ so that $y\in B^{\prime }$ as well. Then there is a $(B^{\mathit{\prime \prime }},{<}^{\mathit{\prime \prime }})\in B$ where $y\in B^{\mathit{\prime \prime }}$. Since $B$ is simply ordered by $\prec$ we have that $(B,<)$ and $(B^{\mathit{\prime \prime }},{<}^{\mathit{\prime \prime }})$ are comparable. Hence $(B,<)$ is a section of $(B^{\mathit{\prime \prime }},{<}^{\mathit{\prime \prime }})$ or vice-versa.

In the first case, we have that both $b$ and $y$ are in $B^{\mathit{\prime \prime }}$. If $y\in B$ then also $y\in B\cap A$ so that $b\le y$ since it is the smallest element of $B\cap A$ by $<$. If $y\notin B$ then $b{<}^{\mathit{\prime \prime }}y$ since $B$ is a section of $B^{\mathit{\prime \prime }}$, and therefore $b{\text{≤}}^{\mathit{\prime \prime }}y$ is true. In the second case in which $(B^{\mathit{\prime \prime }},{<}^{\mathit{\prime \prime }})$ is a section of $(B,<)$ we have that both $b$ and $y$ are in $B$ and hence in $B\cap A$. Then, again $b\le y$ since $b$ is the smallest element of $B\cap A$ by $<$. Hence in all cases either $b\le y$ or $b{\text{≤}}^{\mathit{\prime \prime }}y$. Either way, it follows that $b{\text{≤}}^{\prime }y$ as well since ${<}^{\prime }$ is the union. This shows that $b$ is the smallest element of $A$ by ${<}^{\prime }$ as desired. Since $A$ was an arbitrary nonempty subset, this shows that $B^{\prime }$ is well-ordered by ${<}^{\prime }$. □