Choice function: Difference between revisions
Appearance
Content deleted Content added
Paul August (talk | contribs) m Rm "wikification" tag |
added some historical context and reference/link to Zermelo's 1904 paper. |
||
Line 1: | Line 1: | ||
A '''choice function''' is a [[mathematical function]] <math>f</math> whose [[Domain (mathematics)|domain]] <math>X</math> is a collection of nonempty [[Set|sets]] such that for every <math>S</math> in <math>X</math>, <math>f(S)</math> is an element of <math>S</math>. In other words <math>f</math> chooses exactly one element from each set in <math>X</math>. |
A '''choice function''' is a [[mathematical function]] <math>f</math> whose [[Domain (mathematics)|domain]] <math>X</math> is a collection of nonempty [[Set|sets]] such that for every <math>S</math> in <math>X</math>, <math>f(S)</math> is an element of <math>S</math>. In other words <math>f</math> chooses exactly one element from each set in <math>X</math>. |
||
[[Ernst Zermelo]] introduced choice functions along with the [[axiom of choice]] (AC) in a 1904 paper that gave a proof of the [[well-ordering theorem]]<ref name="Zermelo, 1904">{{cite journal| first=Ernst| last=Zermelo| year=1904| title=[http://gdz.sub.uni-goettingen.de/no_cache/en/dms/load/img/?IDDOC=28526 Beweis, dass jede Menge wohlgeordnet werden kann]| journal=Mathematische Annalen| volume=59| pages=514-16}}</ref>. AC states that every set of nonempty sets has a choice function. A weaker form of AC, the [[axiom of countable choice]] (AC<sub>ω</sub>) states that every [[countable set]] of nonempty sets has a choice function. However, in the absence of either AC or AC<sub>ω</sub>, some sets can still be shown to have a choice function. |
|||
*If <math>X</math> is a [[finite set|finite]] set of nonempty sets, then one can construct a choice function for <math>X</math> by picking one element from each member of <math>X.</math> This requires only finitely many choices, so neither AC or AC<sub>ω</sub> is needed. |
*If <math>X</math> is a [[finite set|finite]] set of nonempty sets, then one can construct a choice function for <math>X</math> by picking one element from each member of <math>X.</math> This requires only finitely many choices, so neither AC or AC<sub>ω</sub> is needed. |
||
Line 10: | Line 10: | ||
==See also== |
==See also== |
||
* [[Axiom of choice]] |
* [[Axiom of choice]] |
||
* [[Axiom of countable choice]] |
* [[Axiom of countable choice]] |
||
* [[Hausdorff paradox]] |
* [[Hausdorff paradox]] |
||
==Notes== |
|||
{{reflist|1}} |
|||
---- |
---- |
Revision as of 19:09, 6 March 2008
A choice function is a mathematical function whose domain is a collection of nonempty sets such that for every in , is an element of . In other words chooses exactly one element from each set in .
Ernst Zermelo introduced choice functions along with the axiom of choice (AC) in a 1904 paper that gave a proof of the well-ordering theorem[1]. AC states that every set of nonempty sets has a choice function. A weaker form of AC, the axiom of countable choice (ACω) states that every countable set of nonempty sets has a choice function. However, in the absence of either AC or ACω, some sets can still be shown to have a choice function.
- If is a finite set of nonempty sets, then one can construct a choice function for by picking one element from each member of This requires only finitely many choices, so neither AC or ACω is needed.
- If every member of is a well-ordered nonempty set, then it is possible to pick the least element of each member of In this case infinitely many choices may be required, but there is a rule for making the choices, so again neither AC or ACω is needed. The distinction between "well-ordered" and "well-orderable" is important here: if the members of were merely well-orderable, it would be necessary to choose a well-ordering of each member, and this might require infinitely many arbitrary choices, and therefore AC (or ACω, if were countably infinite).
- If every member of is a nonempty set, and the union is well-orderable, then it is possible to choose a well-ordering for this union, and this induces a well-ordering on every member of , so a choice function will exist as in the previous example. In this case it was possible to well-order every member of by making just one choice, so neither AC nor ACω was needed. (This example shows that the well-ordering theorem, which states that every set can be well-ordered, implies AC. The converse is also true, but less trivial.)
See also
Notes
- ^ Zermelo, Ernst (1904). "Beweis, dass jede Menge wohlgeordnet werden kann". Mathematische Annalen. 59: 514–16.
{{cite journal}}
: External link in
(help)|title=