choice function
A choice function on a set S is a function f with domain S such that f(x)∈x for all x∈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 ∪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 |