Editing Axiom of choice (section)

==Statement==
A [[choice function]] (also called selector or selection) is a function <math>f</math>, defined on a collection <math>X</math> of nonempty sets, such that for every set <math>A</math> in <math>X</math>, <math>f(A)</math> is an element of <math>A</math>. With this concept, the axiom can be stated:
{{math theorem|For any set <math>X</math> of nonempty sets, there exists a choice function ''f'' that is defined on <math>X</math> and maps each set of <math>X</math> to an element of that set.
| name = Axiom
}}

Formally, this may be expressed as follows:

:<math>\forall X \left[ \varnothing \notin X \implies \exists f \colon X \rightarrow \bigcup_{A\in X} A \quad \forall A \in X \, ( f(A) \in A ) \right] \,.</math>

Thus, the [[negation]] of the axiom may be expressed as the existence of a collection of nonempty sets which has no choice function. Formally, this may be derived making use of the logical equivalence of

:<math>
\neg \forall X \left[ P(X)\to Q(X) \right] \quad \iff \quad \exists X \left[ P(X)\land \neg Q(X) \right].
</math>

Each choice function on a collection <math>X</math> of nonempty sets is an element of the [[Cartesian product#Infinite products|Cartesian product]] of the sets in <math>X</math>. This is not the most general situation of a Cartesian product of a [[indexed family|family]] of sets, where a given set can occur more than once as a factor; however, one can focus on elements of such a product that select the same element every time a given set appears as factor, and such elements correspond to an element of the Cartesian product of all ''distinct'' sets in the family. The axiom of choice asserts the existence of such elements; it is therefore equivalent to the statement:

:''There exists a non-empty [[Cartesian product]] of a collection of non-empty sets''

===Nomenclature===

In this article and other discussions of the Axiom of Choice the following abbreviations are common:
*AC – the Axiom of Choice. More rarely, AoC is used.{{sfn|Rosenberg|2021}}
*ZF – [[Zermelo–Fraenkel set theory]] omitting the Axiom of Choice.
*ZFC – Zermelo–Fraenkel set theory, extended to include the Axiom of Choice.

===Variants===

There are many other equivalent statements of the axiom of choice. These are equivalent in the sense that, in the presence of other basic axioms of set theory, they imply the axiom of choice and are implied by it.

One variation avoids the use of choice functions by, in effect, replacing each choice function with its range:

:Given any set <math>X</math>, if the empty set is not an element of <math>X</math> and the elements of <math>X</math> are [[pairwise disjoint]], then there exists a set <math>C</math> such that its intersection with any of the elements of <math>X</math> contains exactly one element.<ref>{{harvnb|Herrlich|2006|p=9}}. According to {{harvnb|Suppes|1972|p=243}}, this was the formulation of the axiom of choice which was originally given by {{harvnb|Zermelo|1904}}. See also {{harvnb|Halmos|1960|p=60}} for this formulation.</ref>

This can be formalized in first-order logic as:

<math>
\begin{align}
\forall x (& \\
&\exists e (e \in x \and \lnot\exists y (y \in e)) \or \\
&\exists a \, \exists b \, \exists c \, (a \in x \and b \in x \and c \in a \and c \in b \and \lnot(a = b)) \or \\
&\exists c \, \forall e \, (e \in x \implies \exists a \, (a \in e \and a \in c \and \forall b \, ((b \in e \and b \in c) \implies a = b))))
\end{align}
</math>

Note that <math>P \or Q \or R</math> is logically equivalent to <math>(\lnot P \and \lnot Q) \implies R</math>.<br>
In English, this first-order sentence reads:

:Given any set <math>X</math>,
:<math>X</math> contains the empty set as an element or
:the elements of <math>X</math> are not pairwise disjoint or
:there exists a set <math>X</math> such that its intersection with any of the elements of <math>X</math> contains exactly one element.

This guarantees for any [[partition of a set]] <math>X</math> the existence of a subset <math>C</math> of <math>X</math> containing exactly one element from each part of the partition.

Another equivalent axiom only considers collections <math>X</math> that are essentially powersets of other sets:
:For any set <math>A</math>, the [[power set]] of <math>A</math> (with the empty set removed) has a choice function.
Authors who use this formulation often speak of the ''choice function on <math>A</math>'', but this is a slightly different notion of choice function.  Its domain is the power set of <math>A</math> (with the empty set removed), and so makes sense for any set <math>A</math>, whereas with the definition used elsewhere in this article, the domain of a choice function on a ''collection of sets'' is that collection, and so only makes sense for sets of sets.  With this alternate notion of choice function, the axiom of choice can be compactly stated as

:Every set has a choice function.{{sfn|Suppes|1972|p=240}}

which is equivalent to

:For any set <math>A</math> there is a function <math>f:\mathcal P(A)\setminus\{ \emptyset \} \to A </math> such that for any non-empty subset <math>B</math> of <math>A</math>, <math>f(B)</math> lies in <math>B</math>.

The negation of the axiom can thus be expressed as:

:There is a set <math>A</math> such that for all functions <math>f</math> (on the set of non-empty subsets of <math>A</math>), there is a subset <math>B</math> such that <math>f(B)</math> does not lie in <math>B</math>.

===Restriction to finite sets===

The usual statement of the axiom of choice does not specify whether the collection of nonempty sets is finite or infinite, and thus implies that every [[finite set|finite collection]] of nonempty sets has a choice function. However, that particular case is a theorem of the Zermelo–Fraenkel set theory without the axiom of choice (ZF); it is easily proved by the [[mathematical induction|principle of finite induction]].{{sfn|Tourlakis|2003|pp=209–210, 215–216}} In the even simpler case of a collection of ''one'' set, a choice function just corresponds to an element, so this instance of the axiom of choice says that every nonempty set has an element; this holds trivially. The axiom of choice can be seen as asserting the generalization of this property, already evident for finite collections, to arbitrary collections.