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

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)

share|improve this question
    
What about considering elements of $A$ as one-element subsets? –  darij grinberg Jan 22 '11 at 14:37
    
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... –  mathahada Jan 22 '11 at 15:03
1  
Ah, you want a well ordering. Should learn to read. –  darij grinberg Jan 22 '11 at 17:09
add comment

1 Answer

up vote 4 down vote accepted

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.

share|improve this answer
4  
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. –  Andreas Blass Jan 22 '11 at 17:57
    
See also this related MO question: mathoverflow.net/questions/37272/are-all-sets-totally-ordered –  Joel David Hamkins Jan 22 '11 at 18:31
add comment

Your Answer

 
discard

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.