Template:Short description Template:For
Let X be a set of sets none of which are empty. Then a choice function (selector, selection) on X is a mathematical function f that is defined on X such that f is a mapping that assigns each element of X to one of its elements.
An exampleEdit
Let X = { {1,4,7}, {9}, {2,7} }. Then the function f defined by f({1, 4, 7}) = 7, f({9}) = 9 and f({2, 7}) = 2 is a choice function on X.
History and importanceEdit
Ernst Zermelo (1904) introduced choice functions as well as the axiom of choice (AC) and proved the well-ordering theorem,<ref name="Zermelo, 1904">Template:Cite journal</ref> 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 <math>X</math> is a finite set of nonempty sets, then one can construct a choice function for <math>X</math> by picking one element from each member of <math>X.</math> This requires only finitely many choices, so neither AC or ACω is needed.
- If every member of <math>X</math> is a nonempty set, and the union <math>\bigcup X</math> is well-ordered, then one may choose the least element of each member of <math>X</math>. In this case, it was possible to simultaneously well-order every member of <math>X</math> 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 mapEdit
Given two sets <math>X</math> and <math>Y</math>, let <math>F</math> be a multivalued map from <math>X</math> to <math>Y</math> (equivalently, <math>F:X\rightarrow\mathcal{P}(Y)</math> is a function from <math>X</math> to the power set of <math>Y</math>).
A function <math>f: X \rightarrow Y</math> is said to be a selection of <math>F</math>, if:
<math display="block">\forall x \in X \, ( f(x) \in F(x) ) \,.</math>
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.<ref>Template:Cite book</ref> See Selection theorem.
Bourbaki tau functionEdit
Nicolas Bourbaki used epsilon calculus for their foundations that had a <math> \tau </math> symbol that could be interpreted as choosing an object (if one existed) that satisfies a given proposition. So if <math> P(x) </math> is a predicate, then <math>\tau_{x}(P)</math> is one particular object that satisfies <math>P</math> (if one exists, otherwise it returns an arbitrary object). Hence we may obtain quantifiers from the choice function, for example <math> P( \tau_{x}(P))</math> was equivalent to <math> (\exists x)(P(x))</math>.<ref>Template:Cite book</ref>
However, Bourbaki's choice operator is stronger than usual: it's a global choice operator. That is, it implies the axiom of global choice.<ref>John Harrison, "The Bourbaki View" eprint.</ref> Hilbert realized this when introducing epsilon calculus.<ref>"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: <math>A(a)\to A(\varepsilon(A))</math>, where <math>\varepsilon</math> is the transfinite logical choice function." Hilbert (1925), “On the Infinite”, excerpted in Jean van Heijenoort, From Frege to Gödel, p. 382. From nCatLab.</ref>
See alsoEdit
NotesEdit
ReferencesEdit
{{#if: | This article incorporates material from the following PlanetMath articles, which are licensed under the Creative Commons Attribution/Share-Alike License: {{#if: | Choice function | {{#if: 6419 | Choice function | [{{{sourceurl}}} Choice function] }} }}, {{#if: | {{{title2}}} | {{#if: | {{{title2}}} | [{{{sourceurl2}}} {{{title2}}}] }} }}{{#if: | , {{#if: | {{{title3}}} | {{#if: | {{{title3}}} | [{{{sourceurl3}}} {{{title3}}}] }} }} }}{{#if: | , {{#if: | {{{title4}}} | {{#if: | {{{title4}}} | [{{{sourceurl4}}} {{{title4}}}] }} }} }}{{#if: | , {{#if: | {{{title5}}} | {{#if: | {{{title5}}} | [{{{sourceurl5}}} {{{title5}}}] }} }} }}{{#if: | , {{#if: | {{{title6}}} | {{#if: | {{{title6}}} | [{{{sourceurl6}}} {{{title6}}}] }} }} }}{{#if: | , {{#if: | {{{title7}}} | {{#if: | {{{title7}}} | [{{{sourceurl7}}} {{{title7}}}] }} }} }}{{#if: | , {{#if: | {{{title8}}} | {{#if: | {{{title8}}} | [{{{sourceurl8}}} {{{title8}}}] }} }} }}{{#if: | , {{#if: | {{{title9}}} | {{#if: | {{{title9}}} | [{{{sourceurl9}}} {{{title9}}}] }} }} }}. | This article incorporates material from {{#if: | Choice function | Choice function}} on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License. }}