Exercise 8.1.2

Proof. Suppose that $<$ is a well-ordering of $A$. Then, following the hint, defined the relation $X\prec Y$ if and only if the $<$-least element of $X△Y$ is in $X$ for any $X$ and $Y$ in $𝒫\left(A\right)$. Note that, for any $x\in X△Y=(X-Y)\cup (Y-X)$, we clearly have that $x\in X$ or $x\in Y$ so that $x\in A$ since $X\subseteq A$ and $Y\subseteq A$. Hence $X△Y\subseteq A$ so that it is also well-ordered by $<$.

First we show that $\prec$ is a (strict) order on $𝒫\left(A\right)$. Hence we must show that it is asymmetric and transitive. So consider any $X$ and $Y$ in $𝒫\left(A\right)$ where $X\prec Y$. Then by definition the $<$-least element $x$ in $X△Y$ is in $X$. Suppose also that $Y\prec X$ so that, since $Y△X=X△Y$, $x$ is also in $Y$. Then clearly $x$ can be neither in $X-Y$ nor $Y-X$, but then it cannot be that $x\in (X-Y)\cup (Y-X)=X△Y$. This is a contradiction since $x$ was defined to be in $X△Y$. Hence it cannot be that $Y\prec X$ as well, which shows that $\prec$ is asymmetric since $X$ and $Y$ were arbitrary.

To see that $\prec$ is transitive, consider any $X,Y,Z\in 𝒫\left(A\right)$ where $X\prec Y$ and $Y\prec Z$. Then the least element $x$ of $X△Y$ is in $X$ and the least element $y$ of $Y△Z$ is in $Y$. Thus it has to be that $x\in X-Y$ and $y\in Y-Z$ so that $x\in X$, $x\notin Y$, $y\in Y$, and $y\notin Z$. Note that, in particular, this means that $x\ne y$. Since clearly $\left\{x,y\right\}\subseteq A$, it follows that it has a $<$-least element $a$. Thus either $a=x$ or $a=y$. For each case we show that

1.

$a\in X$

2.

$a\in X△Z$

3.

$a$ is a lower bound of $X△Z$

Case: $a=x$. Then clearly $a=x\le y$ so that $a<y$ since $a=x\ne y$.

1.

Clearly $a\in X$ since $a=x$.

2.

Suppose that $a\in Z$. Then, since $a=x\notin Y$, we have that $a\in Z-Y$ so that $a\in Y△Z$. Hence $y\le a$ since $y$ is the least element of $Y△Z$, but this contradicts the fact that $y>a$. So it must be that in fact $a\notin Z$ so that $a\in X-Z$. Thus $a\in X△Z$.

3.

Now consider any $z\in X△Z$.

Case: $z\in X-Z$. Then, if $z\in Y$, we have that $z\in Y-Z$ so that $z\in Y△Z$. It then follows that $a=x\le y\le z$ since $y$ is the least element of $Y△Z$. On the other hand, if $z\notin Y$, then we have $z\in X-Y$ so that $z\in X△Y$. Hence $a=x\le z$ since $x$ is the least element of $X△Y$.

Case: $x\in Z-X$. Then, if $z\in Y$, we have $x\in Y-X$ so $z\in X△Y$. Then $a=x\le z$ since $x$ is the least element of $X△Y$. On the other hand, if $z\notin Y$, then we have $z\in Z-Y$ so that $z\in Y△Z$. Then, as before, $a=x\le y\le z$ since $y$ is the least element of $Y△Z$.

Hence in all cases $a\le z$ so that $a$ is a lower bound since $z$ was arbitrary.

Case: $a=y$. Then clearly $a=y\le x$ so that $a<x$ since $a=y\ne x$.

1.

Suppose that $a\notin X$. Then since $a=y\in Y$ we have that $a\in Y-X$ so that also $a\in X△Y$. But then $x\le a$ since $x$ is the least element of $X△Y$, which contradicts the fact that $x>a$. Hence it has to be that $a\in X$.

2.

We already know that $a=y\notin Z$ so that $a\in X-Z$ since we just showed that $a\in X$. Hence $a\in X△Z$.

3.

Consider any $z\in X△Z$.

Case: $z\in X-Z$. If also $z\in Y$ then clearly $z\in Y-Z$ so that $z\in Y△Z$. It then follows that $a=y\le z$ since $y$ is the least element of $Y△Z$. On the other hand, if $z\notin Y$, then clearly $z\in X-Y$ so that $z\in X△Y$. Hence $a=y\le x\le z$ since $x$ is the least element of $X△Y$.

Case: $z\in Z-X$. Then, if $z\in Y$, clearly $z\in Y-X$ so that $z\in X△Y$. We then have that $a=y\le x\le z$ since $x$ is the least element of $X△Y$. On the other hand, if $z\notin Y$, then $z\in Z-Y$ so that $z\in Y△Z$. Then clearly $a=y\le z$ since $y$ is the least element of $Y△Z$.

Hence in all cases $a\le z$ so that $a$ is a lower bound since $z$ was arbitrary.

Thus in all cases we have that $a$ is the least element of $X△Z$ (since it is in $X△Z$ and also is a lower bound) and $a\in X$. By definition, this shows that $X\prec Z$ so that $\prec$ is transitive. This also shows that $\prec$ is a (strict) order.

Lastly, we show that $\prec$ is a linear ordering. So consider any $X,Y\in 𝒫\left(A\right)$. Assume that $X\ne Y$ so that $X-Y\ne \varnothing$ or $Y-X\ne \varnothing$ (or both). From this it follows that $X△Y\ne \varnothing$. Since also clearly $X△Y\subseteq A$, it has a least element $a$. If $a\in X-Y$ then $a\in X$ so that $X\prec Y$. Similarly, if $a\in Y-X$ then $a\in Y$ so that $Y\prec X$. Hence we have shown that either $X=Y$, $X\prec Y$, or $Y\prec X$ so that $\prec$ is in fact linear since $X$ and $Y$ were arbitrary.

This completes the proof since we have shown that $\prec$ is a linear ordering of $𝒫\left(A\right)$. □