MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
You can extend every partial order to a total order: – Michael Greinecker Jan 5 '12 at 22:14
Thanks for the reference! – expmat Jan 5 '12 at 23:02
up vote 9 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|cite|improve this answer
1's Michael, actually. :-) – Michael Greinecker Jan 5 '12 at 23:20
That's true... :) – expmat Jan 6 '12 at 0:40
See also… where I explain why ${\mathcal P}({\mathbb R})$ lacks a linear ordering in some well studied models of set theory without choice. – Andrés E. 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

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.