Definition:Choice Function

Definition

Let $\mathbb S$ be a set of sets such that:

$\forall S \in \mathbb S: S \ne \O$

that is, none of the sets in $\mathbb S$ may be empty.

A choice function on $\mathbb S$ is a mapping $f: \mathbb S \to \ds \bigcup \mathbb S$ satisfying:

$\forall S \in \mathbb S: \map f S \in S$

That is, for a given set in $\mathbb S$, a choice function selects an element from that set.

The domain of $f$ is $\mathbb S$.

Power Set

The concept of the choice function is often seen in the context of the power set of a given set $S$:

Let $S$ be a set.

Let $\mathbb S = \powerset S \setminus \set \O$ be the power set of $S$ excluding the empty set $\O$.

A choice function for $S$ is a mapping $f: \mathbb S \to S$ satisfying:

$\forall x \in \mathbb S: \map f x \in x$

Chosen Element

Let $f: \mathbb S \to \ds \bigcup \mathbb S$ be a choice function on $\mathbb S$.

For a given $S \in \mathbb S$, the image $\map f S$ of $S$ is referred to as the $f$-chosen element of $S$.

Use of Axiom of Choice

The Axiom of Choice (abbreviated AoC or AC) is the following statement:

All $\mathbb S$ as above have a choice function.

It can be shown that the AoC it does not follow from the other usual axioms of set theory, and that it is relative consistent to these axioms (i.e., that AoC does not make the axiom system inconsistent, provided it was consistent without AoC).

Note that for any given set $S \in \mathbb S$, one can select an element from it (without using AoC). AoC guarantees that there is a choice function, i.e., a function that "simultaneously" picks elements of all $S \in \mathbb S$.

AoC is needed to prove statements such as "all countable unions of finite sets are countable" (for many specific such unions this can be shown without AoC), and AoC is equivalent to many other mathematical statements such as "every vector space has a basis".

Also see

• Zermelo's Well-Ordering Theorem

• Zermelo's Well-Ordering Theorem is Equivalent to Axiom of Choice

• In some situations, AoC is not needed to get a choice function:
  • Principle of Finite Choice
  • Choice Function Exists for Set of Well-Ordered Sets
  • Choice Function Exists for Well-Orderable Union of Sets

• Results about choice functions can be found here.

Sources

• 1964: Steven A. Gaal: Point Set Topology ... (previous) ... (next): Introduction to Set Theory: $3$. The Axiom of Choice and Its Equivalents
• 1973: Thomas J. Jech: The Axiom of Choice ... (previous) ... (next): $1.1$ The Axiom of Choice