|
A choice function is a mathematical function f whose domain X is a collection of nonempty sets such that for every S in X, f(S) is in S. In other words f chooses exactly one element from each set in X. In mathematics, a function is a relation, such that each element of a set (the domain) is associated with a unique element of another (possibly the same) set (the codomain, not to be confused with the range). ...
In mathematics, the domain of a function is the set of all input values to the function. ...
The axiom of choice (AC) states that every set of nonempty sets has a choice function. A weaker form of axiom of Choice, the axiom of countable choice (CC) states that every countable set of nonempty sets has a choice function. However, in the absence of either AC or CC, some sets can still be shown to have a choice function. In mathematics, the axiom of choice, or AC, is an axiom of set theory. ...
The axiom of countable choice or axiom of denumerable choice is an axiom of set theory similar to the axiom of choice. ...
In mathematics the term countable set is used to describe the size of a set, e. ...
- If S is a finite set of nonempty sets, then one can construct a choice function for S by picking one element from each member of S. This requires only finitely many choices, so neither AC or CC is needed.
- If every member of S is a well-ordered nonempty set, then it is possible to pick the least element of each member of S. In this case infinitely many choices may be required, but there is a rule for making the choices, so again neither AC or CC is needed. The distinction between "well-ordered" and "well-orderable" is important here: if the members of S 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 CC, if S were countably infinite).
- If every member of S 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 S, so a choice function will exist as in the previous example. In this case it was possible to well-order every member of S by making just one choice, so neither AC nor CC wasn't 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.)
In mathematics, a set is called finite if and only if there is a bijection between the set and some set of the form {1, 2, ..., n} where is a natural number. ...
In mathematics, a well-order (or well-ordering) on a set S is a total order on S with the property that every non-empty subset of S has a least element in this ordering. ...
In mathematics, especially in order theory, a maximal element of a subset S of some partially ordered set is an element of S that is not smaller than any other element in S. The term minimal element is defined dually. ...
In mathematics, a well-order (or well-ordering) on a set S is a total order on S with the property that every non-empty subset of S has a least element in this ordering. ...
In set theory and other branches of mathematics, the union of a collection of sets is the set that contains everything that belongs to any of the sets, but nothing else. ...
The well-ordering theorem (not to be confused with the well-ordering axiom) states that every set can be well-ordered. ...
See also
This article incorporates material from Choice function on PlanetMath, which is licensed under the GFDL. In mathematics, the axiom of choice, or AC, is an axiom of set theory. ...
The axiom of countable choice or axiom of denumerable choice is an axiom of set theory similar to the axiom of choice. ...
In mathematics, the Hausdorff paradox, named after Felix Hausdorff, states that if you remove some countable subset of the sphere S2, the remainder can be divided into three subsets A, B and C such that A, B, C and B ∪C are all congruent. ...
PlanetMath is a free, collaborative, online mathematics encyclopedia. ...
|
Feeds |
Contact