# Choice function

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 = { {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, 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.)

## 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 {P}}(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 inclusions, optimal control, and mathematical economics. 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))$ .

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.