I'm trying to do the following exercise:

Exercise. Assume ZF. Then AC is equivalent to the statement that $P(\delta)$ can be well-ordered for all $\delta\in{\bf On}$.

I'm struggling with the limit case in the induction proof of the "$\Leftarrow$" direction; i.e. Foundation implies ${\bf V}={\bf WF}$, so I'm showing that $R(\alpha)$ (also sometimes called $V_\alpha$) is well-ordered for all $\alpha\in{\bf On}$. The hint tells me to fix some limit ordinal $\gamma$, find an ordinal $\kappa\npreceq R(\gamma)$ by Hartogs' lemma and fix a well-order $\sqsubset$ on $P(\kappa)$, which is possible by assumption. Now I have to find a way to recursively define a well-order $\vartriangleleft_\alpha$ on each $R(\alpha)$, from $\sqsubset$.

What I've tried and accomplished so far:

  • If $x\in R(\alpha)$ then $\forall\gamma\geq\alpha: x\in R(\gamma)$.
  • Since the ordinal $\kappa$ is found via Hartog's lemma, it satisfies being $(R(\gamma))^+$, and thus a cardinal.
  • Since $\kappa$ is a cardinal, it is true that $\forall \alpha\leq\gamma: R(\alpha)\preceq\kappa$, but since $\kappa\npreceq R(\gamma)$, we have instead that $\forall\alpha\leq\gamma: R(\alpha)\prec\kappa$.
  • Since $\forall\alpha\leq\gamma: R(\alpha)\prec\kappa$, we know there exist a surjection $f_\alpha:\kappa\to R(\alpha)$ for each $\alpha\leq\gamma$, but not a corresponding injection (since that requires AC).
  • We cannot do anything with the mostowski collapse $\pi:R(\alpha)\cong\beta$ ($\beta\in{\bf On}$) of the $R(\alpha)$'s, since that requires a fixed well-ordering on the $R(\alpha)$'s, which requires AC (to choose the well-orderings).
  • $\forall\alpha\in{\bf On}: \alpha\in R(\alpha+1)$.
  • We can't define $x\vartriangleleft_\alpha y$ iff $x\vartriangleleft_{\alpha+1}y$, since this requires the $\sqsubset$ ordering as the "last" $\vartriangleleft$, but to be able to do this, I'd suppose we need an injection, which is not possible (requires AC, as mentioned above as well).

Am I heading in the right direction? Because it seems like I've hit one dead end after each other. I'd love to find $\vartriangleleft_\alpha$'s that "coincide" with $\sqsubset$ somehow, but this seems near impossible, when we're not allowed to use injections. Is there just something blatantly obvious that I'm missing completely?


marked as duplicate by Asaf Karagila axiom-of-choice May 21 '14 at 0:32

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.