# Cardinality of set of well-orderable subsets of a non-well-orderable set

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)$?

-
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

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.

-
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
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