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 E. Caicedo Jul 1 '13 at 6:22
• @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
• @AsafKaragila, ha ha fair enough. Sorry though. Btw, if you know of any good articles about ZFA, please link. I'm not even sure what the axioms would be - obviously we weaken extensionality, but what else needs modifying? – goblin Jul 1 '13 at 10:25

Asaf states in his answer that if for all well-orderable sets $X$ the power set $\mathcal P(X)$ is also well-orderable, then the axiom of choice must hold. 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.

• you define $R(\gamma)$ to be the class of sets of rank $\gamma$ and you seem to be using this fact in the successor-step of your induction. In the limit-step however you're taking $R(\beta)$ to be the class of sets with rank less than $\beta$. I think your proof should still work after some minor adaptations though... – Larry Nov 30 '17 at 6:54
• PS: you should maybe also make it a bit clearer that you are referring to Asaf's answer, not the question. – Larry Dec 14 '17 at 9:23

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 E. Caicedo Jul 1 '13 at 6:48

No. The stronger proposition already doesn't hold for $$\omega$$; it's consistent in absence of axiom of choice that $$2^{\omega}$$, or the cardinality of the continuum, cannot be well-ordered.

• The problem is that you need choice to show $|\mathbb{R}| = |2^\mathbb{N}|$. – goblin Mar 6 at 6:51
• @goblin: No, you don't. Cantor–Bernstein is choice free. – Asaf Karagila Mar 6 at 7:46
• @AsafKaragila, ah, you're right. Yet somehow I have lodged in my brain that $\mathfrak{c}$ and $\beth_1$ are fundamentally different. I wonder why? – goblin Mar 6 at 12:21
• @goblin: I don't know, I'm not your therapist! :) – Asaf Karagila Mar 6 at 12:58
• @AsafKaragila, no, beer is my therapist, and she's bloody good at it too :) – goblin Mar 6 at 13:02