Definition:Choice Function/Power Set

From ProofWiki
Jump to navigation Jump to search

Definition

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$


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$.


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

  • Results about choice functions can be found here.


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Definition:Choice_Function/Power_Set&oldid=579388"