Choice function

Contents

Classic definition

A choice function (selector, selection) is a mathematical function f whose domain X is a collection of nonempty sets such that for every S in X, f(S) is an element of S. In other words f chooses exactly one element from each set in X.

History and importance

Ernst Zermelo introduced choice functions along with the axiom of choice (AC) in a 1904 paper that gave a proof of the well-ordering theorem,[1] which states that every set can be well-ordered. AC states that every set of nonempty sets has a choice function. A weaker form of AC, the axiom of countable choice (ACω) states that every countable set of nonempty sets has a choice function. However, in the absence of either AC or ACω, some sets can still be shown to have a choice function.

  • If X is a finite set of nonempty sets, then one can construct a choice function for X by picking one element from each member of X. This requires only finitely many choices, so neither AC or ACω is needed.
  • If every member of X is a well-ordered nonempty set, then it is possible to pick the least element of each member of X. In this case infinitely many choices may be required, but there is a rule for making the choices, so again neither AC or ACω is needed. The distinction between "well-ordered" and "well-orderable" is important here: if the members of X were merely well-orderable, it would be necessary to choose a well-ordering of each member, and this might require infinitely many arbitrary choices, and therefore AC (or ACω, if X were countably infinite).
  • If every member of X is a nonempty set, and the union \bigcup X is well-orderable, then it is possible to choose a well-ordering for this union, and this induces a well-ordering on every member of X, so a choice function will exist as in the previous example. In this case it was possible to well-order every member of X by making just one choice, so neither AC nor ACω was needed. (This example shows that the well-ordering theorem implies AC. The converse is also true, but less trivial.)

Refinement of the notion of choice function

By selection of a multivalued map φ : A → B, i.e. a map \varphi : A \rarr \mathcal{P}(B) from set A to power set \mathcal{P}(B) of subsets of B, we understand such a function f : A → B that f(a) \in \varphi(a) \, \forall a \in A.

The existence of more regular choice functions, namely continuous or measurable selections (see: [2] ) is important in the theory of differential inclusions, optimal control and mathematical economics.

References

  1. ^ Zermelo, Ernst (1904). "Beweis, dass jede Menge wohlgeordnet werden kann". Mathematische Annalen 59: 514–16. doi:10.1007/BF01445300. 
  2. ^ Border, Kim C. (1989). Fixed Point Theorems with Applications to Economics and Game Theory. Cambridge University Press. 

See also

Notes

This article incorporates material from Choice function on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.

Open source encyclopedia content modification information:

This page was last modified on 22 November 2008 at 18:22.

Authorship and Review

Open source encyclopedia content provided here is not reviewed directly by MedLibrary.org. Content is sourced directly from Wikipedia and is authored by an open community of volunteers. It is not produced by or in any way affiliated with MedLibrary.org.

Usage Guidelines

This article is licensed under the GNU Free Documentation License. It uses material from the Wikipedia article on "Choice function", which is available in its original form here:

http://en.wikipedia.org/w/index.php?title=Choice_function

All material adapted used from Wikipedia is available under the terms of the GNU Free Documentation License. Wikipedia® itself is a registered trademark of the Wikimedia Foundation, Inc.