# Choice function

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Choice_function
> Markdown URL: https://mediated.wiki/source/Choice_function.md
> Source: https://en.wikipedia.org/wiki/Choice_function
> Source revision: 1274567144
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

{{Short description|Mathematical function}}
{{for|the combinatorial choice function C(n, k)|Combination|Binomial coefficient}}

Let ''X'' be a [set of sets](/source/set_of_sets) none of which are empty. Then a '''choice function''' ('''selector''', '''selection''') on ''X'' is a [mathematical function](/source/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 example ==
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 importance ==
[Ernst Zermelo](/source/Ernst_Zermelo) (1904) introduced choice functions as well as the [axiom of choice](/source/axiom_of_choice) (AC) and proved the [well-ordering theorem](/source/well-ordering_theorem),<ref name="Zermelo, 1904">{{cite journal| first=Ernst| last=Zermelo| year=1904| title=Beweis, dass jede Menge wohlgeordnet werden kann| journal=Mathematische Annalen| volume=59| issue=4| pages=514–16| doi=10.1007/BF01445300| url=http://gdz.sub.uni-goettingen.de/no_cache/en/dms/load/img/?IDDOC=28526}}</ref> which states that every set can be [well-ordered](/source/well_ordering). AC states that every set of nonempty sets has a choice function. A weaker form of AC, the [axiom of countable choice](/source/axiom_of_countable_choice) (AC<sub>ω</sub>) states that every [countable set](/source/countable_set) of nonempty sets has a choice function. However, in the absence of either AC or AC<sub>ω</sub>, some sets can still be shown to have a choice function.

*If <math>X</math> is a [finite](/source/finite_set) 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<sub>ω</sub> is needed.
*If every member of <math>X</math> is a nonempty set, and the [union](/source/union_(set_theory)) <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<sub>ω</sub> was needed. (This example shows that the well-ordering theorem implies AC. The [converse](/source/Converse_(logic)) is also true, but less trivial.)

== Choice function of a multivalued map ==
Given two sets <math>X</math> and <math>Y</math>, let <math>F</math> be a [multivalued map](/source/multivalued_function) 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](/source/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 inclusion](/source/differential_inclusion)s, [optimal control](/source/optimal_control), and [mathematical economics](/source/mathematical_economics).<ref>{{cite book
    | last = Border
    | first = Kim C.
    | title = Fixed Point Theorems with Applications to Economics and Game Theory
    | year = 1989
    | publisher = Cambridge University Press
    | isbn = 0-521-26564-9
  }}</ref> See [Selection theorem](/source/Selection_theorem).

==Bourbaki tau function==
[Nicolas Bourbaki](/source/Nicolas_Bourbaki) used [epsilon calculus](/source/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>{{cite book|last=Bourbaki|first=Nicolas|title=Elements of Mathematics: Theory of Sets|date=1968 |publisher=Hermann |isbn=0-201-00634-0}}</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](/source/axiom_of_global_choice).<ref>John Harrison, "The Bourbaki View" [http://www.rbjones.com/rbjpub/logic/jrh0105.htm 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 [http://ncatlab.org/nlab/show/choice+operator nCatLab].</ref>

==See also==
* [Axiom of countable choice](/source/Axiom_of_countable_choice)
* [Axiom of dependent choice](/source/Axiom_of_dependent_choice)
* [Hausdorff paradox](/source/Hausdorff_paradox)
* [Hemicontinuity](/source/Hemicontinuity)

==Notes==
{{Reflist}}

==References==
{{PlanetMath attribution|id=6419|title=Choice function}}

Category:Basic concepts in set theory
Category:Axiom of choice

---
Adapted from the Wikipedia article [Choice function](https://en.wikipedia.org/wiki/Choice_function) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Choice_function?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.