# Well-ordering theorem through repetitive use of the Axiom of Choice

Theorem: If $$X$$ is a set, then there exists a relation $$R$$ such that $$(X, R)$$ is a well-ordered set.

Proof: Let $$X$$ be a set, $$f_1$$ be its choice function (first use of A.C), and $$c_1$$ be the chosen element from $$X$$. Now, consider the set $$X-\{c_1\}$$. The chosen element $$c_2$$ under $$f_2$$ must be different than $$c_1$$. Therefore, we can invoke the Axiom of Choice again and again in transfinite recursion fashion to build a sequence of sets $$X_\alpha = X - \{c_\beta \mid \beta < \alpha\}$$, each time with a different choice of element $$c_\alpha$$, such that $$\bigcup^\limits{\lambda} c_\alpha = X$$. The last ordinal $$\lambda$$ exists since $$X$$ is a set and the collection of all ordinals is not, which, in turn, implies that the sequence stops.

Thus, we could order $$c_\alpha$$ by the natural Well-ordering of the ordinals; i.e., $$i \leq j \Rightarrow c_i \leq c_j$$.

Are there any flaws with this argument?

• I did not know how to name the ordinal for which the process stops. I know limit ordinal means another thing in the usual sense, and I will edit the question. – Alek Fröhlich Jun 19 '20 at 14:21
• @Jneven: There is no need for a [zfc] tag. In the future, please avoid creating new tags without discussing it on meta beforehand. – Asaf Karagila Jul 4 '20 at 7:58

Your proof is not using the axiom of choice correctly. You're seemingly using the choice function to choose one element and then you discard it and take a different choice function to choose the next element.

The idea is that you fix one choice function, whose domain is not $$\{X\}$$, but $$\mathcal P(X)\setminus\{\varnothing\}$$. Then you can repeatedly use that choice function. What you are doing is just using a choice function to utilise existential instantiation, which is the act of choosing one element from one set. The use of AC in the general proof is not there. It is in the ability to coalesce these choices together in a coherent way.

So your argument will need to argue that you have somehow chosen choice functions "correctly". Otherwise your appeal to recursion is not going to work: recursion needs a function to guide its "next step" construction, and this is why the use of a single choice function is important.

The gist of repeatedly using the choice function is correct. You're just not really "repeatedly using the axiom of choice". You're using it once, and repeatedly use the choice function you've picked.

If you insist on changing the choice functions, you will have to fix, in advance a choice function on sets of choice functions, and then at each step of the recursion process defer the question of which choice function to use to the function choosing choice functions. But that will still only be a single use of the axiom of choice (okay, a double use, if you really insist on being picky: once arguing that all those families do admit choice functions, and then that there is a choice function choosing a choice function for each family).

• Sorry for being slow, but I'd like to be sure I correctly understand the issue: the A.C formalizes the idea of choosing (possibly) infinitely many elements from (possibly) infinitely many sets, not from choosing an element from an infinite set. Thus, existential instantiation is not in need for an axiom as it is given to us by first order logic. Now, what is the problem with repetitive use (possibly infinite, I must add) of such instantiation? Wouldn't such thing be equivalent to the A.C in some sense? – Alek Fröhlich Jun 19 '20 at 14:40
• The problem is that proofs are finite. So you can't use EI infinitely many times. – Asaf Karagila Jun 19 '20 at 14:41
• ahh, I forgot about it. Thanks! – Alek Fröhlich Jun 19 '20 at 14:43