Choice function explained

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 of X.

An example

Let X = . Then the function f defined by f = 7, f = 9 and f = 2 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 c up 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 to Y (equivalently,

F:X → l{P}(Y) is a function from X to the power set of Y).

A function

f: X → Y is said to be a selection of F, if:

$$\backslash forall\; x\; \backslash in\; X\; \backslash ,\; (f(x)\; \backslash in\; F(x))\; \backslash ,.$$

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.^[2] See Selection theorem.

Bourbaki tau function

Nicolas Bourbaki 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 _{x} (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 _{x} (P)) was equivalent to (\exists x)(P(x)) .^[3]

However, Bourbaki's choice operator is stronger than usual: it's a global choice operator. That is, it implies the axiom of global choice.^[4] Hilbert realized this when introducing epsilon calculus.^[5]

See also

• Axiom of countable choice
• Axiom of dependent choice
• Hausdorff paradox
• Hemicontinuity

Notes and References

1. Ernst. Zermelo. 1904. Beweis, dass jede Menge wohlgeordnet werden kann. Mathematische Annalen. 59. 4. 514–16. 10.1007/BF01445300.
2. Book: Border , Kim C. . Fixed Point Theorems with Applications to Economics and Game Theory . 1989 . Cambridge University Press . 0-521-26564-9 .
3. Book: Bourbaki, Nicolas. Elements of Mathematics: Theory of Sets. 0-201-00634-0.
4. John Harrison, "The Bourbaki View" eprint.
5. "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. From nCatLab.