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, 2019 at 6:20

1 Answer 1


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, 2019 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$ Jan 21, 2019 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, 2019 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$ Jan 21, 2019 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, 2019 at 1:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .