Lesson 6

Let us explain in which form the Axiom of Choice is used in the proof of the Well-Ordering Principle. Let \(A\) be a given set. We assume that there exists a function \(\varphi\), defined on all subsets of the set \(A\), except for \(A\) itself, which assigns to each such subset one of the elements outside of it, that is: \[X \subsetneq A \Rightarrow \varphi(X) \in A \setminus X.\] Once such a function is fixed, it is possible to construct a well-order on \(A\), and this construction involves no ambiguity. Here is how it is done.

We define the least element of the set \(A\) as \(a_{0} = \varphi(\varnothing)\). Next comes the element \(a_{1} = \varphi(\{a_{0}\})\); by construction, it differs from \(a_{0}\). Then follows the element \(a_{2} = \varphi(\{a_{0}, a_{1}\})\), and so on.

If the set \(A\) is infinite, this process may be continued indefinitely, yielding a sequence \(\{a_{0}, a_{1}, …\}\) of elements of the set \(A\). If, after this, there still remain unused elements of the set \(A\), we consider the element \(a_{\omega} = \varphi(\{a_{0}, a_{1}, a_{2}, …\})\), and we proceed in this manner as long as the set \(A\) is not exhausted. When it is exhausted, the selection process terminates and defines a well-order on \(A\).

Of course, the previous sentence requires clarification—what exactly does “proceed in this manner” mean? Nevertheless, this difficulty can be overcome. We proceed as follows: we examine all potential fragments of the future order and demonstrate that they can be consistently combined.

Let \((S, \leq_{S})\) be a certain subset of the set \(A\) together with an order defined on it. We shall say that \((S, \leq_{S})\) is a correct fragment if it constitutes a well-ordered set, and moreover satisfies \[s = \varphi([0, s))\] for every \(s \in S\). Here, \([0, s)\) denotes the initial segment of the set \(S\), consisting of all elements less than \(s\) with respect to the given order on \(S\).

For instance, the set \(\{\varphi(\varnothing)\}\) is a correct fragment (the order need not be specified in this case, as it contains only one element). The set \(\{\varphi(\varnothing), \varphi(\{\varphi(\varnothing)\})\}\) (the first of the listed elements is considered less than the second) is also a correct fragment. This construction can be extended further, but it is now necessary to discuss the “intersection” of infinitely many (and even uncountably many) such steps of the construction. Our plan is as follows: we will prove that any two correct fragments can be combined in a consistent manner, after which we will examine the union of all such fragments. The union of all correct fragments will itself be a correct fragment and will coincide with the entire set \(A\) (otherwise, one could extend it and obtain a correct fragment not included in the union).