2
$\begingroup$

To show that Axiom of Choice $\Leftrightarrow$ Well-ordering Theorem, Hrbacek and Jech in their book prove the following theorem first:

$X$ can be well-ordered if and only if $\mathcal{P}(X)$ has a choice function.

However, I fell I'm missing something. Sure, assuming the aforementioned theorem it's easy to prove that the axiom of choice implies the well-ordering theorem (let $X$ be a set, if every set has a choice function, so does $\mathcal{P}(X)$, thus, $X$ can be well-ordered).

However, how to deduce the converse using the theorem?

Assume that every set can be well-ordered. Let $X$ be a set. To use the theorem, we need to consider $X$ as a power set for some other set $A$? However, I'm not sure that every set is a power set of some other set. In fact, a nonempty set need to contain $\varnothing$ in order to be a power set.

$\endgroup$
3
$\begingroup$

Given a set $X$, let $Y=\bigcup X$. Then $X\subseteq\mathcal{P}(Y)$, so a choice function on $\mathcal{P}(Y)$ can be restricted to give a choice function on $X$.

(Incidentally, as I would define it, you can only have a choice function on a set of nonempty sets, since you can't choose an element from the empty set. So really we should speak of choice functions on $\mathcal{P}(X)\setminus\{\emptyset\}$, not on $\mathcal{P}(X)$.)

$\endgroup$
  • $\begingroup$ Thank you. I thought it has to do something with $\bigcup X$, but wasn't able to guess about the restriction. $\endgroup$ – Jxt921 Jun 24 '17 at 5:00
  • $\begingroup$ Concerning the definition of a choice function, it is true that one of choices (no pun intended) for it it to consider only sets of nonempty sets, but another way is to define it the way that only the images of nonempty $x$ belong to $x$, and there are no restrictions to what $f( \varnothing )$ might be. $\endgroup$ – Jxt921 Jun 24 '17 at 5:03
1
$\begingroup$

I presume when they say $P(X)$ has a choice function, they mean that there is $F:P(X)\setminus\{\emptyset\}\to X$ with $F(A)\in A$ for all nonempty $A\subseteq X$? If there is such a choice function, transfinite induction gives a well-ordering of $X$.

The existence of such a choice function for all $X$ is clearly equivalent to AC.

$\endgroup$

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.