A choice function (selector, selection) is a
mathematical function
In mathematics, a function from a set to a set assigns to each element of exactly one element of .; the words map, mapping, transformation, correspondence, and operator are often used synonymously. The set is called the domain of the functi ...
''f'' that is defined on some collection ''X'' of nonempty
sets and assigns some element of each set ''S'' in that collection to ''S'' by ''f''(''S''); ''f''(''S'') maps ''S'' to some element of ''S''. In other words, ''f'' is a choice function for ''X'' if and only if it belongs to the
direct product of ''X''.
An example
Let ''X'' = . Then the function that assigns 7 to the set , 9 to , and 2 to is a choice function on ''X''.
History and importance
Ernst Zermelo (1904) introduced choice functions as well as the
axiom of choice
In mathematics, the axiom of choice, or AC, is an axiom of set theory equivalent to the statement that ''a Cartesian product of a collection of non-empty sets is non-empty''. Informally put, the axiom of choice says that given any collection ...
(AC) and proved the
well-ordering theorem
In mathematics, the well-ordering theorem, also known as Zermelo's theorem, states that every set can be well-ordered. A set ''X'' is ''well-ordered'' by a strict total order if every non-empty subset of ''X'' has a least element under the orde ...
,
which states that every set can be
well-ordered
In mathematics, a well-order (or well-ordering or well-order relation) on a set ''S'' is a total order on ''S'' with the property that every non-empty subset of ''S'' has a least element in this ordering. The set ''S'' together with the well-or ...
. AC states that every set of nonempty sets has a choice function. A weaker form of AC, the
axiom of countable choice
The axiom of countable choice or axiom of denumerable choice, denoted ACω, is an axiom of set theory that states that every countable collection of non-empty sets must have a choice function. That is, given a function ''A'' with domain N (where ...
(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
is a
finite
Finite is the opposite of infinite. It may refer to:
* Finite number (disambiguation)
* Finite set, a set whose cardinality (number of elements) is some natural number
* Finite verb, a verb form that has a subject, usually being inflected or marke ...
set of nonempty sets, then one can construct a choice function for
by picking one element from each member of
This requires only finitely many choices, so neither AC or AC
ω is needed.
*If every member of
is a nonempty set, and the
union
Union commonly refers to:
* Trade union, an organization of workers
* Union (set theory), in mathematics, a fundamental operation on sets
Union may also refer to:
Arts and entertainment
Music
* Union (band), an American rock group
** ''Un ...
is well-ordered, then one may choose the least element of each member of
. In this case, it was possible to simultaneously well-order every member of
by making just one choice of a well-order of the union, so neither AC nor AC
ω was needed. (This example shows that the well-ordering theorem implies AC. The
converse
Converse may refer to:
Mathematics and logic
* Converse (logic), the result of reversing the two parts of a definite or implicational statement
** Converse implication, the converse of a material implication
** Converse nonimplication, a logical c ...
is also true, but less trivial.)
Choice function of a multivalued map
Given two sets ''X'' and ''Y'', let ''F'' be a
multivalued map from ''X'' and ''Y'' (equivalently,
is a function from ''X'' to the
power set
In mathematics, the power set (or powerset) of a set is the set of all subsets of , including the empty set and itself. In axiomatic set theory (as developed, for example, in the ZFC axioms), the existence of the power set of any set is post ...
of ''Y'').
A function
is said to be a selection of ''F'', if:
The existence of more regular choice functions, namely continuous or measurable selections is important in the theory of
differential inclusions,
optimal control, and
mathematical economics. See
Selection theorem In functional analysis, a branch of mathematics, a selection theorem is a theorem that guarantees the existence of a single-valued selection function from a given set-valued map. There are various selection theorems, and they are important in the ...
.
Bourbaki tau function
Nicolas Bourbaki used
epsilon calculus Hilbert's epsilon calculus is an extension of a formal language by the epsilon operator, where the epsilon operator substitutes for quantifiers in that language as a method leading to a proof of consistency for the extended formal language. The ' ...
for their foundations that had a
symbol that could be interpreted as choosing an object (if one existed) that satisfies a given proposition. So if
is a predicate, then
is one particular object that satisfies
(if one exists, otherwise it returns an arbitrary object). Hence we may obtain quantifiers from the choice function, for example
was equivalent to
.
However, Bourbaki's choice operator is stronger than usual: it's a ''global'' choice operator. That is, it implies the
axiom of global choice In mathematics, specifically in class theories, the axiom of global choice is a stronger variant of the axiom of choice that applies to proper classes of sets as well as sets of sets. Informally it states that one can simultaneously choose an ele ...
. Hilbert realized this when introducing epsilon calculus.
["Here, moreover, we come upon a very remarkable circumstance, namely, that all of these transfinite axioms are derivable from a single axiom, one that also contains the core of one of the most attacked axioms in the literature of mathematics, namely, the axiom of choice: , where is the transfinite logical choice function." Hilbert (1925), “On the Infinite”, excerpted in Jean van Heijenoort, ''From Frege to Gödel'', p. 382. Fro]
nCatLab
See also
*
Axiom of countable choice
The axiom of countable choice or axiom of denumerable choice, denoted ACω, is an axiom of set theory that states that every countable collection of non-empty sets must have a choice function. That is, given a function ''A'' with domain N (where ...
*
Hausdorff paradox The Hausdorff paradox is a paradox in mathematics named after Felix Hausdorff. It involves the sphere (a 3-dimensional sphere in ). It states that if a certain countable subset is removed from , then the remainder can be divided into three disjoin ...
*
Hemicontinuity
Notes
References
{{PlanetMath attribution, id=6419, title=Choice function
Basic concepts in set theory
Axiom of choice