Choice function

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 ${\displaystyle X}$ is a finite set of nonempty sets, then one can construct a choice function for ${\displaystyle X}$ by picking one element from each member of ${\displaystyle X.}$ This requires only finitely many choices, so neither AC or AC_ω is needed.
• If every member of ${\displaystyle X}$ is a nonempty set, and the union ${\displaystyle \bigcup X}$ is well-ordered, then one may choose the least element of each member of ${\displaystyle X}$. In this case, it was possible to simultaneously well-order every member of ${\displaystyle 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 ${\displaystyle X}$ and ${\displaystyle Y}$, let ${\displaystyle F}$ be a multivalued map from ${\displaystyle X}$ to ${\displaystyle Y}$ (equivalently, ${\displaystyle F:X\to \mathcal{P}(Y)}$ is a function from ${\displaystyle X}$ to the power set of ${\displaystyle Y}$).

A function ${\displaystyle f:X\to Y}$ is said to be a selection of ${\displaystyle F}$, if:

$${\displaystyle \mathrm{\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.

A survey of selectors was published by Claude Ambrose Rogers and John E. Jayne in 2002.

Bourbaki tau function

Nicolas Bourbaki used epsilon calculus for their foundations that had a ${\displaystyle \tau }$ symbol that could be interpreted as choosing an object (if one existed) that satisfies a given proposition. So if ${\displaystyle P(x)}$ is a predicate, then ${\displaystyle {\tau }_x(P)}$ is one particular object that satisfies ${\displaystyle P}$ (if one exists, otherwise it returns an arbitrary object). Hence we may obtain quantifiers from the choice function, for example ${\displaystyle P({\tau }_x(P))}$ was equivalent to ${\displaystyle (\mathrm{\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.