Choice function
From Wikipedia, the free encyclopedia
|
A choice function is a mathematical function Failed to parse (Missing texvc executable; please see math/README to configure.): f whose domain Failed to parse (Missing texvc executable; please see math/README to configure.): X is a collection of nonempty sets such that for every Failed to parse (Missing texvc executable; please see math/README to configure.): S in Failed to parse (Missing texvc executable; please see math/README to configure.): X , Failed to parse (Missing texvc executable; please see math/README to configure.): f(S) is an element of Failed to parse (Missing texvc executable; please see math/README to configure.): S . In other words Failed to parse (Missing texvc executable; please see math/README to configure.): f chooses exactly one element from each set in Failed to parse (Missing texvc executable; please see math/README to configure.): X . 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]. 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.
is a finite set of nonempty sets, then one can construct a choice function for Failed to parse (Missing texvc executable; please see math/README to configure.): X by picking one element from each member of Failed to parse (Missing texvc executable; please see math/README to configure.): X. This requires only finitely many choices, so neither AC or ACω is needed.
is a well-ordered nonempty set, then it is possible to pick the least element of each member of Failed to parse (Missing texvc executable; please see math/README to configure.): 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 Failed to parse (Missing texvc executable; please see math/README to configure.): 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 Failed to parse (Missing texvc executable; please see math/README to configure.): X were countably infinite).
is a nonempty set, and the union Failed to parse (Missing texvc executable; please see math/README to configure.): \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 Failed to parse (Missing texvc executable; please see math/README to configure.): X , so a choice function will exist as in the previous example. In this case it was possible to well-order every member of Failed to parse (Missing texvc executable; please see math/README to configure.): X by making just one choice, so neither AC nor ACω was needed. (This example shows that the well-ordering theorem, which states that every set can be well-ordered, implies AC. The converse is also true, but less trivial.) See alsoNotes
This article incorporates material from Choice function on PlanetMath, which is licensed under the GFDL. |
