Choice function

Let X be a set of sets none of which are empty. Then a choice function (selector, selection) on X is a 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 (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.

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→𝒫(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:

∀x∈X(f(x)∈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 τ 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 τ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(τx(P)) was equivalent to (∃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.

See also