Explain what is meant by a well-ordering of a set.

Without assuming Zorn's Lemma, show that the power-set of any well-ordered set can be given a total (linear) ordering.

By a selection function for a set $A$, we mean a function $f: P A \rightarrow P A$ such that $f(B) \subset B$ for all $B \subset A, f(B) \neq \emptyset$ for all $B \neq \emptyset$, and $f(B) \neq B$ if $B$ has more than one element. Suppose given a selection function $f$. Given a mapping $g: \alpha \rightarrow[0,1]$ for some ordinal $\alpha$, we define a subset $B(f, g) \subset A$ recursively as follows:

$$\begin{aligned} &B(f, g)=A \quad \text { if } \alpha=0, \\ &B(f, g)=f\left(B\left(f,\left.g\right|_{\beta}\right)\right) \quad \text { if } \alpha=\beta^{+} \text {and } g(\beta)=1 \\ &B(f, g)=B\left(f,\left.g\right|_{\beta}\right) \backslash f\left(B\left(f,\left.g\right|_{\beta}\right)\right) \quad \text { if } \alpha=\beta^{+} \text {and } g(\beta)=0 \\ &B(f, g)=\bigcap\left\{B\left(f,\left.g\right|_{\beta}\right) \mid \beta<\alpha\right\} \quad \text { if } \alpha \text { is a limit ordinal. } \end{aligned}$$

Show that, for any $x \in A$ and any ordinal $\alpha$, there exists a function $g$ with domain $\alpha$ such that $x \in B(f, g)$.

[It may help to observe that $g$ is uniquely determined by $x$ and $\alpha$, though you need not show this explicitly.]

Show also that there exists $\alpha$ such that, for every $g$ with domain $\alpha, B(f, g)$ is either empty or a singleton.

Deduce that the assertion 'Every set has a selection function' implies that every set can be totally ordered.

[Hartogs' Lemma may be assumed, provided you state it precisely.]