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 \bigcup \mathbb S$ satisfying:

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

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


The domain of $f$ is $\mathbb 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".


In some situations, AoC is not needed to get a choice function:


Principle of Finite Choice

Let $I$ be a non-empty finite indexing set.

Let $\family {S_i}_{i \mathop \in I}$ be an $I$-indexed family of non-empty sets.


Then there exists an $I$-indexed family $\family {x_i}_{i \mathop \in I}$ such that:

$\forall i \in I: x_i \in S_i$


That is, there exists a mapping:

$\ds f: I \to \bigcup_{i \mathop \in I} S_i$

such that:

$\forall i \in I: \map f i \in S_i$


A Choice Function Exists for Set of Well-Ordered Sets

If every member of $\mathbb S$ is a well-ordered, then we can define a choice function $f$ by:

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


Every member of $\mathbb S$ is a well-ordered set.

Thus, for $S \in \mathbb S$, there is a minimal element $s$ for $S$ (with respect to the ordering of $S$).

By Well-Ordering Minimal Elements are Unique, $s$ is unique.

Therefore, we can define $f$ by:

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

$\blacksquare$


This has to be rewritten. In particular:
The following paragraph needs to be rewritten clearly or deleted, and any relevant points to the page in which they are immediately relevant, for example Choice Function Exists for Set of Well-Ordered Sets if so be the case.
You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by doing so. (discuss)

Note that this only applies if we are given a well-ordering for each $S \in \mathbb S$.

More formally, this means: if there is a mapping that maps $S \in \mathbb S$ to a well-ordering of $S$.

If we just know that each $S \in \mathbb S$ is well-orderable, we generally do need AoC to get a choice function (to apply the proof above, we have to pick a well-order for each $S\in \mathbb S$, which requires AoC. This is related to the fact that generally we need AoC to show that, for example, the countable union of countable sets is countable.)


A Choice Function Exists for Well-Orderable Union of Sets

If the union $\bigcup \mathbb S$ is well-orderable, we can create a choice function for $\bigcup \mathbb S$.


Suppose $T = \bigcup \mathbb S$ is well-orderable.

Then we can create a well-ordering $\preceq$ on $T$ so as to make $\struct {T, \preceq}$ a well-ordered set.

From the definition of well-ordered set, every subset of $T$ is itself well-ordered.

From Subset of Union: General Result we have that $\forall S \in \mathbb S: S \subseteq T$.

So every $S \in \mathbb S$ is well-ordered and Choice Function Exists for Set of Well-Ordered Sets applies.

$\blacksquare$


Also see


Sources

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