Let's say I take a set $S$, where $S$ can be well ordered. From what I understand, one can use that well ordering to totally order $\mathscr{P}(S)$.

How does a body actually use the well ordering of $S$ to construct a total ordering of $\mathscr{P}(S)$?

Perhaps construct is too strong a word. Is there a way to prove that a total ordering of $\mathscr{P}(S)$ just exists, no need to explicitly state what it is, since that might be very difficult.


1 Answer 1


If $\lt$ is a well-ordering of $S$, then we may define the lexical ordering on the power set $P(S)$, by which $A\lt_{lex} B$, if and only if the $\lt$-least element of the symmetric difference $A\triangle B$ is in $B$ and not in $A$. That is, we look to the first place where the sets differ, and then put the set without this element before the set with this element. This is just like the order in a dictionary, hence the name, since two words in a dictionary are put in order by comparing the first letter on which they differ.

To see that this is a total order, we check first that it is transitive. If $A\lt_{lex}B\lt_{lex} C$, then the first difference between $A$ and $C$ must be in $C$, since either this occurs before the first difference between $A$ and $B$, in which case it is in $C$ and not in $B$ and hence in $C$ and not in $A$, or else it occurs at or after the first difference between $A$ and $B$, in which case it occurs exactly at this difference, which is in $C$ and not in $A$. The order it linear since any two sets do indeed have a least difference, since $\lt$ is a well-order.

  • 1
    $\begingroup$ This theorem also generalizes to mappings: If $A$ is well-ordered and $B$ is totally ordered, then the lexical ordering totally orders the set $B^A$ of functions from $A$ to $B$ (and you can get the result for powersets by exploiting the bijection from $2^S$ to $P(S)$). $\endgroup$ Commented May 22, 2015 at 4:33
  • $\begingroup$ I want to prove the same thing by only using ZF (and not AC). Does your proof fulfill this? (And if so, why/how do you see this?) $\endgroup$
    – Studentu
    Commented Jan 21, 2019 at 16:38
  • $\begingroup$ @Studentu The definition of lexical ordering does not use choice. Where do you think JDH or Carneiro used AC? Bear in mind that $S$ was assumed to come already equipped with a well-ordering. $\endgroup$ Commented May 24, 2023 at 19:26

You must log in to answer this question.

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