# Axiom of Choice implies the Well-Ordering Principle

I am trying to understand the proof of this implication we were taught in my set theory module. I cannot seem to tie it together with the final line of the argument... We used this lemma:

Given $F\colon \mathcal{P}(X)\to X$, there exists a unique well-ordered set $(W,<)$ such that

• $W\subseteq X$;
• for all $x\in W$, we have $F(\{y\in W:y<x\})=x$; and
• $F(W)\in W$.

The proof given is:

Let $\sigma\colon\mathcal{P}(X)\to X$ be a choice function (technically defined on $\mathcal{P}(X)-\{\emptyset\}$ but we may let $\sigma(\emptyset)$ be any member of $X$). Take $F\colon\mathcal{P}(X)\to X$ defined as $F(A)=\sigma(X-A)$ and apply the lemma.

How does the lemma yield the well ordering principle? I assume that we want $W$ to be $X$ since WO states that the well-ordering relation is on the set $X$ (for all $X$).

## 1 Answer

Yes, the point is that $W=X$.

The key to that is the last part of the conclusion of the lemma: $F(W)\in W$, which is the same as $\sigma(X\setminus W)\in W$. If $X\setminus W$ is nonempty, then this contradicts $\sigma$ being a choice function, so the only way we can have $\sigma(X\setminus W)\in W$ is if $X\setminus W=\varnothing$, in which case $\sigma(\varnothing)$ is just some member of $X$.

Since $W\subseteq X$ and $X\setminus W=\varnothing$, it must be that $W=X$.