Axiom of Choice implies Well-Ordering Principle.

My textbook only presents the construction of function $F$ and does not provide details on how to define such well-ordering. I try to fill in the remaining blanks in my attempt. Does it look fine or contain logical flaws/gaps?

Thank you for your help!

My attempt:

Let $A$ be a set. By Axiom of Choice, there is a choice function $f:\mathcal{P}(A) \setminus \{\emptyset\} \to A$ such that $f(X) \in X$ for all $X \in \mathcal{P}(A) \setminus \{\emptyset\}$. Let $V$ be the class of all sets. We define a function $G:V \to V$ as follows: $$G(x)=\begin{cases} f(A \setminus {\rm ran} (x))&\text{if }x\text{ is a function and }A \setminus {\rm ran} (x) \neq \emptyset\\A&\text{otherwise}\end{cases}$$

By Transfinite Recursion Theorem, there is a function $F: {\rm Ord} \to V$ such that $F(\alpha)=G(F \restriction \alpha)$ for all $\alpha \in {\rm Ord}$.

  1. There do not exist $\alpha_1<\alpha_2 \in {\rm Ord}$ such that $F(\alpha_1)=F(\alpha_2)=a$ for some $a\in A$

If not, $F(\alpha_1)=F(\alpha_2)=a$ for some $a\in A$. We have $F(\alpha_2)=G(F \restriction \alpha_2)$. There are only two cases.

  • $F(\alpha_2)=A \neq a =F (\alpha_1)$

  • $F(\alpha_2)=f(A \setminus {\rm ran} (F \restriction \alpha_2))$

$f(A \setminus {\rm ran} (F \restriction \alpha_2)) \in A \setminus {\rm ran} (F \restriction \alpha_2) \implies f(A \setminus {\rm ran} (F \restriction \alpha_2)) \notin {\rm ran} (F \restriction \alpha_2) \implies$ $F(\alpha_2) \notin {\rm ran} (F \restriction \alpha_2) \implies F(\alpha_2) \neq F(\alpha_1) \in {\rm ran} (F \restriction \alpha_2)$.

Both cases lead to a contradiction.

  1. $A=F(\lambda)$ for some $\lambda < h(A)$ where $h(A)$ is the Hartogs number of $A$

If not, $A \neq F(\lambda)$ for all $\lambda < h(A)$ and consequently $F(\lambda) \in A$ for all $\lambda < h(A)$. Then $F \restriction h(A)$ is an injection from $h(A)$ to $A$ and thus $|h(A)| \le |A|$. This contradicts the definition of $h(A)$.

  1. $A={\rm ran} (F \restriction \beta)$ for some $\beta \in {\rm Ord}$

Let $\beta = \min \{\lambda \in {\rm Ord} \mid A=F(\lambda)\}$. Then $F(\alpha) \in A$ for all $\alpha<\beta$. If not, $F(\alpha) = A$ for some $\alpha<\beta$. This contradicts the minimality of $\beta$. It follows that ${\rm ran} (F \restriction \beta) \subseteq A$. Moreover, $F(\beta)=A \implies G(F \restriction \beta)=A \implies A \setminus {\rm ran} (F \restriction \beta) =\emptyset \implies A \subseteq {\rm ran} (F \restriction \beta)$.

To sum up, ${\rm ran} (F \restriction \beta) = A$. Hence $F \restriction \beta$ is a bijection from $\beta$ to $A$. We define an ordering $\prec$ on $A$ by $a\prec b \iff F^{-1}(a) < F^{-1}(b)$ for all $a,b\in A$. Since $F \restriction \beta$ is a bijection from $\beta$ to $A$, $F \restriction \beta$ is an isomorphism between $(\beta,<)$ and $(A,\prec)$.

Since $<$ is a well-ordering on $\beta$, so is $\prec$ on $A$.

  • 1
    $\begingroup$ I think the first proof was done by Zermelo, the original paper is not too long... you could probably just read it and see if your construction matches his. $\endgroup$ – Christopher Rose Dec 21 '18 at 2:26
  • 1
    $\begingroup$ Hi @AndrésE.Caicedo, please have a closer look! I wrote "... for some $a\in A$" $\endgroup$ – LAD Dec 21 '18 at 14:26
  • 1
    $\begingroup$ @PhilipWhite I don't think Zermelo's original proof used ordinals or transfinite recursion, so it won't match the OP's proof. $\endgroup$ – Andreas Blass Dec 22 '18 at 0:29
  • $\begingroup$ @AndreasBlass Was under the same impression, since it was years before replacement and (von Neumann) ordinals, but was surprised today looking through Sierpinski's old textbook to see him claim that Zermelo's original 1904 proof was 'based, similarly to ours, on the theory of ordinals', in contrast to the more careful/ difficult 1908 proof. (Sierpinski's proof is the usual.) Looking at Moore's account, the 1904 proof is as modern as one could reasonably expect, although it gets muddled at the end where we would usually invoke Hartogs. (Apparently Cantorians thought this was the fatal flaw.) $\endgroup$ – spaceisdarkgreen Dec 29 '18 at 19:15
  • $\begingroup$ @AndreasBlass (Which is not to say that the original proof 'uses ordinals and transfinite recursion' in the modern way that OP's attempt does, and that OP should expect an exact match. Just thought it was interesting.) $\endgroup$ – spaceisdarkgreen Dec 29 '18 at 19:22

Here's the usual approach. Define $G$ on ordinals, rather than arbitrary sets, by transfinite recursion. Explicitly $$G(\alpha):=f(\{x\in A|\forall\beta\in\alpha (G(\beta)\ne x)\}).$$Obviously, $G$ never takes the same value twice.

If $G(\alpha)$ exists for every ordinal $\alpha$, all ordinals can be injected into $A$, contradicting replacement and the Burali-Forti paradox.

Therefore $G(\alpha)$ is undefined for some minimal ordinal $\alpha$, and then $\{x\in A|\forall\beta\in\alpha (G(\beta)\ne x)\}=\emptyset$ (because $f(B)$ exists for any non-empty subset of $A$), i.e. $A=\{G(\beta)|\beta\in\alpha\}$. This provides a well-ordering of $A$ isomorphic to the $\in$ ordering of $\alpha$.

Incidentally, the well-ordering principle also implies the axiom of choice. To invent a choice function $f$ on some set $X$ with $\emptyset\not\in X$, well-order $Y:=\bigcup X$. Any $y\in X$ is a non-empty subset of $Y$. Then define $f(y)$ as the minimum element of $y$.

| cite | improve this answer | |
  • 1
    $\begingroup$ Could you please verify my proof? $\endgroup$ – LAD Dec 21 '18 at 13:38

Let $V$ be the class of all sets. We define a function $G: V\rightarrow V$ as follows: [...]

Nope, that's not valid in Zermelo-Fraenkel (ZFC), because ZFC has no proper classes at all. So you can't have a "class of all sets," much less use it as the domain and codomain of a function! If you want to use something other than ZFC, you have to say so explicitly, but your proof doesn't say anything of the sort.

(Good ideas for "something other than ZFC" include NBG and NF(U), depending on what you are trying to achieve.)

Your argument can be interpreted as a metatheoretical "proof that there is a proof" of the Well-Ordering Theorem. But WOT is a straightforward theorem of ZFC. It should not require the use of metatheory to prove. Contrast for example Goodstein's theorem, which cannot be proven from within Peano Arithmetic and therefore does require the use of metatheory.

| cite | improve this answer | |
  • 2
    $\begingroup$ Two things (the first somewhat more minor than the second). 1. The proof is in ZF, not ZFC. It is pointless to prove two provable things are equivalent... it only makes sense to prove equivalences in a base theory where the statements aren't (known to be) provable. 2. Just because a proof mentions classes doesn't mean it's in a class-enabled theory. Statements about classes, when formalized in ZF/C are statements in the metatheory about formulas. It is routine to use classes in arguments in ZF/C. (That said, there's no harm formalizing this in a theory with classes.) $\endgroup$ – spaceisdarkgreen Dec 21 '18 at 18:34
  • $\begingroup$ Actually right after I write it, I take back the first point, since this is not actually a proof of equivalence. It makes sense to view the direction AC => WOP as simply a proof of WOP in ZFC. $\endgroup$ – spaceisdarkgreen Dec 21 '18 at 18:36
  • $\begingroup$ @spaceisdarkgreen: "Statements about classes, when formalized in ZF/C are statements in the metatheory about formulas. It is routine to use classes in arguments in ZF/C." - 1. In the metatheory, you may not have all the same machinery as in the theory. 2. A proof in the metatheory that AC entails WOP is not a proof in ZFC that AC entails WOP. ZFC doesn't know or care about the metatheory, so you can't use a proof in the metatheory to make ZFC believe that AC entails WOP. $\endgroup$ – Kevin Dec 21 '18 at 19:17
  • $\begingroup$ You show in the metatheory that there is a proof of WOT from ZF + the choice function version of AC. You use the idea of classes as abbreviations for formulas in this argument. If you are claiming that results like transfinite recursion that are metatheorems about classes are somehow not applicable to studying ZFC, that is simply wrong: they can be found in any textbook on the subject. $\endgroup$ – spaceisdarkgreen Dec 21 '18 at 19:32
  • $\begingroup$ @spaceisdarkgreen: A metatheoretical existence proof is quite different from a theoretical direct proof, because the former may be nonconstructive (and in this case, it is necessarily nonconstructive because of the use of AC). Therefore, you cannot necessarily transform the former into the latter without a great deal of care which OP has not demonstrated. $\endgroup$ – Kevin Dec 21 '18 at 20:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.