choice function
A 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 Axiom of Choice^{} (http://planetmath.org/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:

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

•
If every member of $S$ is a wellordered 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 “wellordered” and “wellorderable” is important here: if the members of $S$ were merely wellorderable, we would first have to choose a wellordering of each member, and this might require infinitely many arbitrary choices, and therefore AC.

•
If every member of $S$ is a nonempty set, and the union $\cup S$ is wellorderable, then we can choose a wellordering for this union, and this induces a wellordering on every member of $S$, so we can now proceed as in the previous example. In this case we were able to wellorder every member of $S$ by making just one choice, so AC wasn’t needed. (This example shows that the WellOrdering Principle, which states that every set is wellorderable, implies AC. The converse^{} is also true, but less trivial — see the proof (http://planetmath.org/ProofOfZermelosWellOrderingTheorem).)
Title  choice function 

Canonical name  ChoiceFunction 
Date of creation  20130322 14:46:26 
Last modified on  20130322 14:46:26 
Owner  yark (2760) 
Last modified by  yark (2760) 
Numerical id  11 
Author  yark (2760) 
Entry type  Definition 
Classification  msc 03E25 
Related topic  AxiomOfChoice 
Related topic  AxiomOfCountableChoice 
Related topic  HausdorffParadox 
Related topic  ProofOfHausdorffParadox 
Related topic  OneToOneFunctionFromOntoFunction 