Suppose $A$ is a simply ordered set. Is there a natural induced simple order on the power set $\mathcal{P}(A)$ ?

If A happens to be well ordered the following seems to define a simple order on $\mathcal{P}(A)$

1.) We call the empty set to be less than every non empty set. Further if $X$ and $Y$ are unequal subsets of $A$ such that $ X \subset Y $ then we call $ X < Y$

2.) Suppose $X$ and $Y$ are disjoint non empty sets, then $ X < Y $ iff min ($X$) $<$ min($Y$)

3.) If X and Y are two intersecting sets neither of which is a subset of the other than $X < Y$ iff min ($X-X\cap Y) < $ min ($X-X\cap Y$)

My second question is :

Does the above prescription make the power set $\mathcal{P}(A)$ a simply ordered set ? If yes, is there a standard name for it ?

  • $\begingroup$ $\min(X)$ need not exist. And if you use $\inf$ instead, note that you can have both $X \cap Y = \varnothing$ yet $\inf(X) = \inf(Y)$. $\endgroup$ – Hurkyl Apr 9 '14 at 18:54
  • $\begingroup$ @Hurkyl Thanks, but my second question is about the case when the original set is well ordered. So these problems do not arise. $\endgroup$ – Ishan Mata Apr 9 '14 at 18:56
  • $\begingroup$ @Hurkyl: Or $\inf$ might not exist. $\endgroup$ – Asaf Karagila Apr 9 '14 at 18:58
  • $\begingroup$ ... and $3$ and $1$ have contradictory motivations which contradict transitivity: e.g. if $X \subseteq Y$ and $z$ is an element larger than every element of $Y$, and $w$ is an element of $Y$ larger than every element of $X$, then $Y < X \cup \{z\} < \{ w \} < Y$. $\endgroup$ – Hurkyl Apr 9 '14 at 18:59

The answer is no.

If the answer was yes, we could have proved that $\mathcal P(\Bbb R)$ can be linearly ordered without appealing to the axiom of choice. However it is consistent that the power set of the real numbers cannot be linearly ordered without the axiom of choice.

So there is no way to define from a linear order a linear order of its power set. Of course using the axiom of choice (and in fact weaker fragments of it) we can prove that every set can be linearly ordered. But this linear order of the power set is not [necessarily] definable from a linear order of the original set.

  • $\begingroup$ Thanks for your answer, but what if the original set is well ordered. Which of the axiom fails with if I try to define an order with the prescription I have mentioned ? $\endgroup$ – Ishan Mata Apr 9 '14 at 18:53
  • $\begingroup$ If the set is well-ordered, then indeed there is a definable linear order on its power set. If the order is not a well-order then the notion of $\min(A)$ is not well-defined. So everything sorta fails. $\endgroup$ – Asaf Karagila Apr 9 '14 at 18:58

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.