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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.