Choice function

A choice function (selector, selection) is a mathematical function f that is defined on some collection X of nonempty sets and assigns to each set S in that collection some element f(S) 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 = { {1,4,7}, {9}, {2,7} }. Then the function that assigns 7 to the set {1,4,7}, 9 to {9}, and 2 to {2,7} is a choice function on X.

History and Importance

Ernst Zermelo (1904) introduced choice functions as well as the axiom of choice (AC) and proved the well-ordering theorem,^[1] 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 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 $\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.)

Refinement of the notion of choice function

A function $f: A \rarr B$ is said to be a selection of a multivalued map φ:A → B ( that is, a function $\varphi:A\rarr\mathcal{P}(B)$ from A to the power set $\mathcal{P}(B)$), if

$\forall a \in A \, ( f(a) \in \varphi(a) ) \,.$

The existence of more regular choice functions, namely continuous or measurable selections (see: ^[2] ) is important in the theory of differential inclusions, optimal control, and mathematical economics.

Bourbaki tau function

Nicholas Bourbaki used a formalism for set theory that had a τ symbol which could be interpreted as choosing a set (if one existed) which satisfies a given proposition. So if P(x) is a proposition P(τ(x)(P(x))) was equivalent to $(\exists x)(P(x))$.^[3]

See also

• Axiom of countable choice
• Hausdorff paradox
• Hemicontinuity

Notes

1. ^ Zermelo, Ernst (1904). "Beweis, dass jede Menge wohlgeordnet werden kann". Mathematische Annalen 59 (4): 514–16. doi:10.1007/BF01445300. http://gdz.sub.uni-goettingen.de/no_cache/en/dms/load/img/?IDDOC=28526. 
2. ^ Border, Kim C. (1989). Fixed Point Theorems with Applications to Economics and Game Theory. Cambridge University Press. ISBN 0521265649. 
3. ^ Bourbaki, Nicolas. Elements of Mathematics: Theory of Sets. ISBN 0201006340. 

References

This article incorporates material from Choice function on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.