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

• 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 — see the proof (http://planetmath.org/ProofOfZermelosWellOrderingTheorem).)

Title	choice function
Canonical name	ChoiceFunction
Date of creation	2013-03-22 14:46:26
Last modified on	2013-03-22 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