Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose, with the negation of Axiom of Choice, we have a non-well-orderable set $A$, and its power set $P(A)$, let $P'(A)$ be $\{x \in P(A): x \text{ is well orderable}\}$

Is there an injection from $P'(A)$ into $A$?

What can we say about the cardinality of $P'(A)$?

share|improve this question
1  
You mean well-orderable, right? –  Asaf Karagila Jan 27 '13 at 15:44
    
Are you understanding the set $A$ to be linearly ordered? Or maybe partially ordered? Or what? –  Michael Hardy Jan 27 '13 at 15:46
    
If $A$ is partially ordered in such a way that every pair of its members is incomparable, then the only subsets well ordered by that partial ordering (i.e. by its restriction) are singletons. In that case there is an injection such as you seek. –  Michael Hardy Jan 27 '13 at 15:48
    
@AsafKaragila: Thank your for pointing that out. –  Metta World Peace Jan 27 '13 at 15:50
    
The question is much clearer, and very different, after the latest edits. –  Michael Hardy Jan 27 '13 at 15:51
show 5 more comments

1 Answer

up vote 4 down vote accepted

Let me denote this set as $\mathcal W(A)$, which is a notation I recall seeing before (although not where, at the moment).

Clearly if $A$ can be well-ordered then $\mathcal W(A)=\mathcal P(A)$ and therefore we cannot prove that $\mathcal W(A)<\mathcal P(A)$, or that $|A|=|\mathcal W(A)|$. But it is also clear that if $A$ cannot be well-ordered then $\mathcal W(A)\neq\mathcal P(A)$.

  • It is consistent that $|\mathcal W(A)|<|\mathcal P(A)|$:

    Suppose that $A$ is [infinite and] amorphous (cannot be written as a disjoint union of two infinite sets) then every well-orderable subset is finite. However $\mathcal P(A)$ is Dedekind-finite, so the cardinality of all finite subsets of $A$ is strictly smaller than that of $\mathcal P(A)$ (in fact it is exactly half!), and so it is consistent that the inequality is sharp.

  • It is provable that $|A|<|\mathcal W(A)|$:

    1. Tarski, A. On well-ordered subsets of any set. Fundamenta Mathematicae 32, pp. 176–183 (1939);
    2. Truss, J. K. The well-ordered and well-orderable subsets of a set. Mathematical Logic Quarterly 19, pp. 211–214 (1973).

    You could also find a paragraph in L. Halbeisen's Combinatorial Set Theory, Chapter 5, Related Results no. 33.

share|improve this answer
2  
Zermelo gave a proof that $|A|<|\mathcal P(A)|$ that is essentially different from Cantor in that it avoids diagonalization. You can see it here: math.stackexchange.com/questions/284812/… That proof only uses $\mathcal W(A)$, so in fact Zermelo's argument gives the inequality $|A|<|\mathcal W(A)|$. –  Andres Caicedo Jan 27 '13 at 16:13
1  
Stevo Todorcevic developed a nice theory of partition calculus of partially ordered sets in "Partition relations for partially ordered sets", Acta Math. 155 (1-2), (1985), 1–25. At the beginning of the paper, Stevo reproves $|A|<|\mathcal W(A)|$ as a consequence of very general results in his partition calculus setting. –  Andres Caicedo Jan 27 '13 at 16:16
    
Andres, thank you for the addition! –  Asaf Karagila Jan 27 '13 at 16:23
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.