If $X$ is well-ordered set, how to prove that $\mathcal{P}(X)$ can be linearly ordered?

Question

I'm having troubles solving the following exercise, proposed in T. Jech, 'Set theory' Exercises 5.4.

Let $X$ is well-ordered set then $\mathcal{P}(X)$ can be linear ordered.

[Let $X<Y$ if the least element of $X\triangle Y$ belongs to $X$.]

I can prove that $<$ satisfies totality (i.e. $X<Y$ or $X=Y$ or $Y<X$) and $X\not< X$, but I can't prove transitivity of $<$. Thanks for any help.

Answer 1

Suppose that $A<B$ and $B<C$; Let $a=\min(A\mathbin{\triangle}B)\in A$ and $b=\min(B\mathbin{\triangle}C)\in B$. Then $a\notin B$, so $a\ne b$.

• Suppose that $a<b$. If $x\in X$ and $x<a$, then $x\in A$ iff $x\in B$ iff $x\in C$, so $x\notin A\mathbin{\triangle}C$. Since $a\notin B$ and $a<b$, $a\notin C$, and therefore $a=\min(A\mathbin{\triangle}C)$, i.e., $A<C$.

• Now suppose that $b<a$. If $x\in X$ and $x<b$, then $x\in A$ iff $x\in B$ iff $x\in C$, so $x\notin A\mathbin{\triangle}C$. And $b\in A\setminus C$ (why?), so $b=\min(A\mathbin{\triangle}C)\in A$, and again $A<C$.