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.

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.

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

Given two sets X {\displaystyle X} and Y {\displaystyle Y} , let F {\displaystyle F} be a multivalued map from X {\displaystyle X} to Y {\displaystyle Y} (equivalently, F : X → P ( Y ) {\displaystyle F:X\rightarrow {\mathcal {P}}(Y)} is a function from X {\displaystyle X} to the power set of Y {\displaystyle Y} ).

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

∀ x ∈ X ( f ( x ) ∈ F ( x ) ) . {\displaystyle \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.^[2] See Selection theorem.

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 P ( x ) {\displaystyle P(x)} is a predicate, then τ x ( P ) {\displaystyle \tau _{x}(P)} is one particular object that satisfies P {\displaystyle P} (if one exists, otherwise it returns an arbitrary object). Hence we may obtain quantifiers from the choice function, for example P ( τ x ( P ) ) {\displaystyle P(\tau _{x}(P))} was equivalent to ( ∃ x ) ( P ( x ) ) {\displaystyle (\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]

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

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