choice functionChoiceFunction2004-10-25 14:46:022005-12-01 12:57:47Definitionchoice\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}
\def\emptyset{\varnothing}\PMlinkescapeword{between}
\PMlinkescapeword{domain}
\PMlinkescapeword{order}
\PMlinkescapeword{states}
A \emph{choice function} on a set $S$ is a function $f$ with domain $S$ such that $f(x)\in x$ for all $x\in S$.
A choice function on $S$ simply picks one element from each member of $S$. So in order for $S$ to have a choice function, every member of $S$ must be a nonempty set. The \PMlinkname{Axiom of Choice}{AxiomOfChoice} (AC) states that every set of nonempty sets does have a choice function.
Without AC the situation is more complicated, but we can still show that some sets have a choice function. Here are some examples:
\begin{itemize}
\item If $S$ is a finite set of nonempty sets, then we can construct a choice function on $S$ by picking one element from each member of $S$. This requires only finitely many choices, so we don't need to use AC.
\item If every member of $S$ is a well-ordered nonempty set, then we can pick the least element of each member of $S$. In this case we may be making infinitely many choices, but we have a rule for making the choices, so AC is not needed. The distinction between ``well-ordered'' and ``well-orderable'' is important here: if the members of $S$ were merely well-orderable, we would first have to choose a well-ordering of each member, and this might require infinitely many arbitrary choices, and therefore AC.
\item If every member of $S$ is a nonempty set, and the union $\cup S$ is well-orderable, then we can choose a well-ordering for this union, and this induces a well-ordering on every member of $S$, so we can now proceed as in the previous example. In this case we were able to well-order every member of $S$ by making just one choice, so AC wasn't needed. (This example shows that the Well-Ordering Principle, which states that every set is well-orderable, implies AC. The converse is also true, but less trivial --- \PMlinkname{see the proof}{ProofOfZermelosWellOrderingTheorem}.)
\end{itemize}