Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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}$.)

share|improve this question
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

up vote 8 down vote accepted

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$.

share|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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