As the title says, my question is, how one can use only ZF-theory to prove that the power set of A, whereby (A, <) is a well-ordering, can be linearly ordered?

  • 1
    $\begingroup$ Lexicograpohically, by first difference? Where's the snag? $\endgroup$ – bof Jan 21 at 6:20

Find the earliest element in the well order of A where they differ-where it is in one and not the other. Lexicographic order would take the one with the element first.

  • $\begingroup$ Not that it matters, but I thought it was usual to represent membership by a $1$ and nonmembership by a $0$, and $0$ comes before $1$. $\endgroup$ – bof Jan 21 at 6:22
  • $\begingroup$ @bof: I was thinking of each set as a string. If we use the alphabet, a string beginning with ab comes before one beginning with ac because the b is present. $\endgroup$ – Ross Millikan Jan 21 at 15:11
  • $\begingroup$ @RossMillikan Thanks for your reply! I hve thought of this, as it was suggested in this thread math.stackexchange.com/questions/90078/… but I don't know how to explain that it only uses ZF-theory? $\endgroup$ – Studentu Jan 21 at 16:28
  • $\begingroup$ Once you have a well order on $A$ (you really just need a total order) you just start down the list. Is the first element in only one subset? If so, that one comes first. Otherwise, keep going. ZF can answer is $x \in X$. $\endgroup$ – Ross Millikan Jan 21 at 16:46
  • $\begingroup$ You don't "just need a total order", you need a well-order. How would you order the power set of $\mathbb R$? Which comes first, $\mathbb Q$ or $\mathbb R\setminus\mathbb Q$? I don't believe you can prove in ZF that there is a total order on the power set of $\mathbb R$. $\endgroup$ – bof Jan 22 at 1:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.