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$).
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$.