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 these two axioms:

  1. Every partial order extends to a linear order.
  2. Every partial preorder (reflexive and transitive relation) extends to a linear preorder while preserving strict orderings: i.e., whenever $x<y$ (namely: $x\lesssim y$ but not $y\lesssim x$) holds in the original order, it holds in the extended order.

Question: Does 2 imply 1 in ZF?


A. In ZF, Boolean Prime Ideal implies 1 (but not conversely if ZF is consistent), and 1 implies 2 (take the quotient of the preordered set under $\sim$, where $x\sim y$ iff $x\lesssim y$ and $y\lesssim x$, and apply 1).

B. Also, 2+(every set has a linear order) implies 1. (Use 2 to extend the partial order $\le$ to a total preorder $\lesssim$ preserving strict orderings. We now need to turn $\lesssim$ into a linear order. To do that, we just need to linearly order within each equivalence class under $\sim$. Do that by taking a linear order on the whole set and using that to induce the order in each equivalence class---though not between them.)

C. Claim 2 implies Banach-Tarski and thus the existence of nonmeasurable sets (Pawlikowski's proof of Banach-Tarski from Hahn-Banach can be adapted), and hence 2 is not provable in ZF (if ZF is consistent).

D. Claim 2 is implied by the claim that every set has full conditional probabilities. For of course we only need to prove Claim 2 in the special case where the initial partial preorder is a subset relation (first identify $x$ and $y$ if $x\lesssim y$ and $y\lesssim x$; then replace each $x$ by $\{ y : y \lesssim x \}$). But then for sets $A$ and $B$ let $A\preceq B$ iff $P(A-B|A\Delta B)\le P(B-A|A\Delta B)$. It's easy to check that that's a partial preorder such that if $A$ is a proper subset of $B$ then $A\prec B$. In another question I asked if one could prove the existence of full conditional probabilities from Hahn-Banach (it's easy to prove from BPI). If so, then Claim 2 is weaker than Claim 1, since the Consequences site says there are models with Hahn-Banach (Form 52) but where it's not true that every set has a total order (Form 30).

share|cite|improve this question

Your Answer


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

Browse other questions tagged or ask your own question.