# Extensions of the partial order of the power set

Consider the set $\mathcal{P}(\mathbb{R})$ of all subsets of $\mathbb{R}$, the set of real numbers. It has a natural partial order: $A \leq B$ iff $A \subseteq B$.

Can one extend this order to a total order?

(I was discussing this with a friend and we didn't know if this is possible. If we replace $\mathbb{R}$ by any finite set, this is possible. We were not sure even when we replace $\mathbb{R}$ by $\mathbb{N}$.)

-
You can extend every partial order to a total order: en.wikipedia.org/wiki/Szpilrajn_extension_theorem –  Michael Greinecker Jan 5 '12 at 22:14
Thanks for the reference! –  expmat Jan 5 '12 at 23:02
add comment

## 1 Answer

Michael Greinecker's answer (in a comment) is correct in the context of the usual axioms of set theory, including the axiom of choice. If one works in set theory without the axiom of choice, then one cannot prove that $\mathcal P(\mathbb R)$ admits any total order at all (even without the requirement that it extend $\subseteq$). On the other hand, the $\subseteq$ ordering of $\mathcal P(\mathbb N)$ can be explicitly extended to a total ordering, given by lexicogaphically ordering the characteristic functions of subsets of $\mathbb N$.

-
Uhm...it's Michael, actually. :-) –  Michael Greinecker Jan 5 '12 at 23:20
That's true... :) –  expmat Jan 6 '12 at 0:40
See also mathoverflow.net/questions/26861/… where I explain why ${\mathcal P}({\mathbb R})$ lacks a linear ordering in some well studied models of set theory without choice. –  Andres Caicedo Jan 6 '12 at 3:51
Apologies to Michael for my error, and thanks to Andres for correcting it. –  Andreas Blass Jan 6 '12 at 15:09
add comment