3
$\begingroup$

Suppose that $S$ is a well-ordered set; how can we prove that the following is a total order on the power set of $S$? $A\prec B\Longleftrightarrow \min(A\triangle B)\in A.$

1 Answers 1

3

To prove that a relation $<$ is a total order you need to show:

  1. Given $A,B$ exactly one of the $A is true
  2. $A and $B has as a consequence $A

The first one: Take two sets $A,B\in P(S)$. Then if $A\neq B$ their symmetric difference $A\triangle B\neq\varnothing$. Thus it has a least element (since $S$ is well ordered). If this element is a member of $A$ then $A and if it's a member of $B$ then $B. Both of the $A and $B cannot be true since the symmetric difference contains only elements that belong in exactly one of the $A,B$. If on the other hand $A=B$ then $A\triangle B=\varnothing$ so we cannot have $A or $B.

The second one: Let $A and $B. That means that the least element of $A\triangle B$ is in $A$ and the least element of $B\triangle C$ is in $B$. Let $x\in A\triangle B$ be its least element which is in $A$ by the definition of $A. Let $y\in C$ such that $y. Because $B either $y\in B$ or there is a $z\in B$ such that $z (otherwise $y$ would be the least of $B\triangle C$ which is impossible). To put it shortly there is a $z\in B$ such that $z\leq y$. Then since $z\leq y we have that $z. But $x$ is the least element of $A\triangle B$ thus $z\in A$. I just showed that any element of $C$ less that $x$ is in $A$. therefore $A\leq C$. If $A=C$ then we would have $A and $B which is impossible because of (1). Thus $A.