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

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.

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.