Selection Function
   HOME

TheInfoList



OR:

A choice function (selector, selection) is a mathematical function ''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 In mathematics, one can often define a direct product of objects already known, giving a new one. This generalizes the Cartesian product of the underlying sets, together with a suitably defined structure on the product set. More abstractly, one ta ...
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 Ernst Friedrich Ferdinand Zermelo (, ; 27 July 187121 May 1953) was a German logician and mathematician, whose work has major implications for the foundations of mathematics. He is known for his role in developing Zermelo–Fraenkel axiomatic se ...
(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 collectio ...
(AC) and proved the well-ordering theorem, 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 In mathematics, a set is countable if either it is finite or it can be made in one to one correspondence with the set of natural numbers. Equivalently, a set is ''countable'' if there exists an injective function from it into the natural numbers; ...
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 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 ...
\bigcup X is well-ordered, then one may choose the least element of each member of X. In this case, it was possible to simultaneously well-order every member of X 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 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, F:X\rightarrow\mathcal(Y)is a function from ''X'' to the power set of ''Y''). A function f: X \rightarrow Y is said to be a selection of ''F'', if: \forall x \in X \, ( f(x) \in F(x) ) \,. The existence of more regular choice functions, namely continuous or measurable selections is important in the theory of
differential inclusion In mathematics, differential inclusions are a generalization of the concept of ordinary differential equation of the form :\frac(t)\in F(t,x(t)), where ''F'' is a multivalued map, i.e. ''F''(''t'', ''x'') is a ''set'' rather than a single point ...
s,
optimal control Optimal control theory is a branch of mathematical optimization that deals with finding a control for a dynamical system over a period of time such that an objective function is optimized. It has numerous applications in science, engineering and ...
, and
mathematical economics Mathematical economics is the application of mathematical methods to represent theories and analyze problems in economics. Often, these applied methods are beyond simple geometry, and may include differential and integral calculus, difference an ...
. See Selection theorem.


Bourbaki tau function

Nicolas Bourbaki Nicolas Bourbaki () is the collective pseudonym of a group of mathematicians, predominantly French alumni of the École normale supérieure (Paris), École normale supérieure - PSL (ENS). Founded in 1934–1935, the Bourbaki group originally in ...
used epsilon calculus for their foundations that had a \tau symbol that could be interpreted as choosing an object (if one existed) that satisfies a given proposition. So if P(x) is a predicate, then \tau_(P) is one particular object that satisfies P (if one exists, otherwise it returns an arbitrary object). Hence we may obtain quantifiers from the choice function, for example P( \tau_(P)) was equivalent to (\exists x)(P(x)). However, Bourbaki's choice operator is stronger than usual: it's a ''global'' choice operator. That is, it implies the axiom of global choice. 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: A(a)\to A(\varepsilon(A)), where \varepsilon 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 * Hausdorff paradox *
Hemicontinuity In mathematics, the notion of the continuity of functions is not immediately extensible to multivalued mappings or correspondences between two sets ''A'' and ''B''. The dual concepts of upper hemicontinuity and lower hemicontinuity facilitate s ...


Notes


References

{{PlanetMath attribution, id=6419, title=Choice function Basic concepts in set theory Axiom of choice