Definition:Choice Function
in the process of being refactored, or:
has been identified as a candidate for refactoring.
Until this has been finished, please leave {{refactor}} in the code.
Contents |
Definition
Let $\mathbb S$ be a set of sets such that:
- $\forall S \in \mathbb S: S \ne \varnothing$
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: f \left({S}\right) \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".
The above needs to be rewritten more tersely. Examples of its use should be moved either to the aoc page itself or onto the specific pages where the statements themselves are used.
Note that the recent amendment to this page which added a considerable quantity of material was made by an anonymous editor and therefore we can not enter into a discussion with him/her.
You can help Proof Wiki by completing it.
To discuss it in more detail, feel free to use the talk page.
When this has been done, {{WIP}} should be removed from the code.
If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page (see the proofread template for usage).
In some situations, AoC is not needed to get a choice function:
A Choice Function Exists for All Finite Sets
Let $\mathbb S$ be a set of sets such that:
- $\forall S \in \mathbb S: S \ne \varnothing$
that is, none of the sets in $\mathbb S$ may be empty.
Let $\mathbb S$ be finite.
Then there exists a choice function $f: \mathbb S \to \bigcup \mathbb S$ defined as:
- $\forall S \in \mathbb S: \exists x \in S: f \left({S}\right) = x$
Thus, if $\mathbb S$ is finite, we can construct a choice function on $\mathbb S$ by picking one element from each member of $\mathbb S$.
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: f \left({S}\right) = \inf \left({S}\right)$
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: f \left({S}\right) = s$
$\blacksquare$
Note that this only applies if we are given a well order for each $S \in \mathbb S$, more formally, if there is a function that maps $S \in \mathbb S$ to a well-order 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.)
The above 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 Proof Wiki by completing it.
To discuss it in more detail, feel free to use the talk page.
When this has been done, {{WIP}} should be removed from the code.
If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page (see the proofread template for usage).
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 $\left({T, \preceq}\right)$ 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
- The Well-Ordering Theorem is Equivalent to the Axiom of Choice, which demonstrates the truth of the converse of the Well-Ordering Theorem.
Axiom of Choice
This theorem depends on the Axiom of Choice.
Because of some of its bewilderingly paradoxical implications, the Axiom of Choice is considered to be controversial.
Most mathematicians are convinced of its truth and insist that it should nowadays be generally accepted.
However, others consider its implications so counter-intuitive and nonsensical that they adopt the philosophical position that it cannot be true.
Sources
- Paul R. Halmos: Naive Set Theory (1960)... (previous)... (next): $\S 15$: The Axiom of Choice
