# Without appealing to choice, can we prove that if $X$ is well-orderable, then so too is $2^X$?

Without appealing to the axiom of choice, it can be shown that (Proposition:) if $X$ is well-orderable, then $2^X$ is totally-orderable.

Question: can we show the stronger result that if $X$ is well-orderable, then so too is $2^X$?

Proof of Proposition. Pick any well-ordering of $X$. Then the lexicographic order totally orders $2^X$.

More explicitly: for any two $f,g \in 2^X$, define $f < g$ iff

1. there exists $x \in X$ such that $f(x) \neq g(x)$, and
2. if $x \in X$ is minimal such that $f(x) \neq g(x)$, then $f(x)=0$ and $g(x)=1$.

It can be shown that $<$ totally-orders $2^X$.

-

No.

The axiom "If $X$ can be well-ordered then $2^X$ can be well-ordered" implies the axiom of choice in $\sf ZF$. In $\sf ZFA$ or $\sf ZF-Reg$ this is no longer true, though.

To see more details see the first part of Jech, The Axiom of Choice Chapter 9.

One very interesting observation about the fact that in $\sf ZFA$ this statement does not prove the axiom of choice, is that if $\psi(X)$ is a statement in which all the quantifiers are either bounded in $y$ or bounded in $\mathcal P(y)$ (where $y$ is a variable, of course), and in $\sf ZF$ we have that $\forall X\psi(X)$ implies $\sf AC$, then in $\sf ZFA$ we have that $\forall X\psi(X)$ implies that the power set of a well-ordered set is well-orderable. (This is the first problem in the aforementioned chapter 9.)

-
Or see Theorem 9 here. And one can go further: One cannot even prove in $\mathsf{ZF}$ that if $X$ is well-orderable, then $2^{2^X}$ is linearly orderable. – Andrés Caicedo Jul 1 '13 at 6:22
Wait, it doesn't hold in the Zionist Freedom Alliance? What is ZFA? – goblin Jul 1 '13 at 8:48
@user18921: I am not a big fond of political comments. $\sf ZFA$ is $\sf ZF$ with atoms. – Asaf Karagila Jul 1 '13 at 9:54
@AsafKaragila, ahh sorry man; I was just trying to be funny. If you had let me know immediately, I would have just deleted it. – goblin Jul 1 '13 at 10:19
@user18921: It's fine. Nothing that a few bottles of 20+ years old single malt won't cure... ;-) – Asaf Karagila Jul 1 '13 at 10:21

Actually there is a proof of this left as exercise in Kunen's Set Theory, 2011 ed., exercise I.12.17, which comes with a hint, and is done as follows:

In $\mathsf{ZF}$, including the axiom of regularity of course, suppose that for any cardinal $\aleph$, $2^{\aleph}$ is well-orderable, then this implies that for any ordinal $\delta$, $\mathcal P(\delta)$ is well-orderable; as in $\mathsf{ZF}$ ,$\delta\thickapprox \aleph$, where $\aleph$ is the greatest cardinal with $\aleph\leq \delta.$

Let us prove by transfinite induction on $\gamma$ that $R(\gamma)$, the class of all sets of rank $\gamma$; which is a set, is well-orderable for all ordinals $\gamma$. As we are assuming $V=WF$ this will imply $\mathsf {AC}$.

Suppose $\gamma\neq 0$ is such that the property holds for all $\alpha<\gamma$. If $\gamma=\alpha+1$ is successor, then as $R(\alpha)$ is well-orderable there is some ordinal $\delta$ such that $\delta\thickapprox R(\alpha)$, hence $R(\gamma)=\mathcal P(R(\gamma))\thickapprox \mathcal P(\delta)$, but as $\mathcal P(\delta)$ is well-orderable by hypothesis, $R(\gamma)$ is then well-orderable.

Now suppose $\gamma$ is limit. By Hartogs' Theorem; in $\mathsf{ZF}$, there is some cardinal $\kappa$ with $\kappa \npreceq R(\gamma)$. Fix a well-order $\sqsubset$ of $P(\kappa)$. Let us define by induction on $\alpha<\gamma$ an explicit well-order $\lhd_{\alpha}$ on $R(\alpha)$ for all $\alpha<\gamma$. Furthermore, let us construct each $\lhd_{\alpha}$ in such a manner that for any $\alpha<\beta<\gamma$ we have $\lhd_{\beta}\cap (R(\alpha)\times R(\alpha))\subseteq \lhd_{\alpha}$.

Let $\lhd_0$ be the canonical well-order of $R(0)$. Suppose we have defined $\lhd_{\alpha}$ for all $\alpha<\beta$ for some $\beta\leq \gamma$, meeting the conditions above. There are two cases:

Case $\beta=\alpha+1$. Since $\kappa\npreceq R(\alpha)$, we must have that $\bf{type}$$(R(\alpha),\lhd_{\alpha})<\kappa.$ Let $f_{\alpha}:(R(\alpha),\lhd_{\alpha})\rightarrow \kappa$ be the canonical embedding, the one that maps $(R(\alpha),\lhd_{\alpha})$ into an initial segment of $\kappa$. Then $f_{\alpha}[R(\alpha)]=\mu$ for some $\mu<\kappa$, so that $f^{-1}_{\alpha}[ \ ]:P(\mu)\rightarrow P(R(\alpha))$ is a bijection, but $P(\mu)\subseteq P(\kappa)$. Hence there is an explicit well-ordering of $P(R(\alpha))$ via $f^{-1}_{\alpha}[ \ ]$ and the well-order $\sqsubset$ on $P(\kappa)$. Let $\lhd_{\beta}$ be this well-order. Then clearly for any $\mu<\beta$ we have $\lhd_{\beta}\cap (R(\mu)\times R(\mu))=\emptyset$.

Suppose $\beta$ is limit. Since for any $\alpha<\mu<\beta$ we have $\lhd_{\mu}\cap R(\alpha)^2\subseteq \lhd_{\alpha}$, it follows that if we put $\lhd_{\beta}=\bigcup_{\alpha<\beta}\lhd_{\alpha}$, $\lhd_{\beta}$ is a well-order on $R(\beta)=\bigcup_{\alpha<\beta}R(\alpha)$, and also for any $\mu<\beta$, $\lhd_{\beta}\cap R(\mu)^2\subseteq \lhd_{\mu}.$

Hence by transfinite induction we obtained an explicit well-order $\lhd_{\gamma}$ of $R(\gamma)$. Hence $R(\gamma)$ is well-orderable for all ordinals $\gamma$, and therefore $\mathsf{AC}$ holds.

-

No, we can’t. It’s a result due to Herman Rubin in $1960$ that if $2^{\aleph}$ is well-orderable for every well-ordered cardinal $\aleph$, then the axiom of choice holds.

-
It was Herman Rubin, I believe it was in 1963 or so. – Asaf Karagila Jul 1 '13 at 6:24
@Asaf: I just checked: $\text{Rubin}^2$ came out in $1963$, but Felgner says that the result is actually from $1960$. – Brian M. Scott Jul 1 '13 at 6:30
The result first appeared in H. Rubin. Two propositions equivalent to the axiom of choice only under both the axioms of extensionality and regularity, Notices A.M.S., 7, 381 (Abstract). This is mentioned in Equivalents of the axiom of choice, II, in page 98. – Andrés Caicedo Jul 1 '13 at 6:48