Definition:Choice Function

From ProofWiki
Jump to navigation Jump to search

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 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 known as

A choice function is also known as a selection function.


Examples

Doubletons of Real Numbers

Let $\FF$ be a set of sets of the form $\set {a, b}$ where $a$ and $b$ are real numbers.

Then there exists a choice function on $\FF$.


Singletons

Let $\FF$ be a set of singletons.

Then there exists a choice function on $\FF$.


Also see

  • Results about choice functions can be found here.


Sources