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.$
powerset total order
1 Answers
To prove that a relation $<$ is a total order you need to show:
- Given $A,B$ exactly one of the $A is true
- $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