2
$\begingroup$

Given a well ordering of a set $A$ we can define a total order $A^A$ in an obvious way (for $f \neq g$ find the least $i$ such that $f(i) \neq g(i)$ and define $f < g$ if $f(i) < g(i)$)

Does the inverse direction work? Does a total order on the powerset of $A$ give rise to a well ordering of $A$? (without choice, of course, for otherwise the result is obvious)

Improve this question
$\endgroup$
3
  • $\begingroup$ What about considering elements of $A$ as one-element subsets? $\endgroup$
    – darij grinberg
    Jan 22, 2011 at 14:37
  • $\begingroup$ This does necessarily work. You can fix a bijection from 2^Q to R such that {q} is mapped to q, and the usual ordering of R is total, but Q is not well ordered... $\endgroup$
    – mathahada
    Jan 22, 2011 at 15:03
  • 1
    $\begingroup$ Ah, you want a well ordering. Should learn to read. $\endgroup$
    – darij grinberg
    Jan 22, 2011 at 17:09

1 Answer 1

Reset to default
4
$\begingroup$

No. If this were true, then ZF would prove that "every set can be totally ordered" implies "every set can be well-ordered", which (assuming ZF is consistent) it doesn't. I can't find the original citation for this nonimplication, but it's in Howard and Rubin's "Consequences of the Axiom of Choice" for example.

Improve this answer
$\endgroup$
2
  • 4
    $\begingroup$ The first model of set theory that satisfies the ordering principle ("every set can be totally ordered") but not the axiom of choice was a permutation model (of set theory with atoms) constructed by Mostowski in the late 1930's. For models of ZF (thus without atoms), Cohen's original model will work. That follows from the theorem of Halpern and Levy (in the late 1960's) that this model satisfies the Boolean prime ideal theorem, which implies the ordering principle. $\endgroup$
    – Andreas Blass
    Jan 22, 2011 at 17:57
  • $\begingroup$ See also this related MO question: mathoverflow.net/questions/37272/are-all-sets-totally-ordered $\endgroup$
    – Joel David Hamkins
    Jan 22, 2011 at 18:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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