Axiom of Choice

The Axiom of Choice is an axiom of Zermelo-Fraenkel set theory that states:

<math>\forall x\;(\forall y\;y\in x\Rightarrow\exists z\; z\in y)\;\exists S\;(\forall z\;z\in x\Rightarrow\exists w\;w\in z\;\wedge\;w\in S)\;\wedge\;(\forall v\;v\in z\;\wedge\;v\in S\Rightarrow v=w)</math>

Or more compactly:

<math>\forall x\neq\varnothing\;\exists S\;(\forall z\in x\;\exists_1w\in z\cap S).</math>

In layman's terms, the Axiom of Choice is "For every nonempty set there is a choice function." Or, "We can choose one element from every element of a nonempty set of disjoint sets and this process by which we choose these sets will set up a new set." A more precise layman explanation is this:

For every collection of nonempty sets S, there exists a function f such that f(S) is a member of S for every possible S.

The Axiom of Choice has many equivalent statements, such as the Tychonoff theorem, the Well-Ordering Theorem, the existence of cardinal numbers, the existence of a basis for every vector space, and the existence of subsets of the real line which do not have a well-defined Lebesgue measure.

Despite its usefulness, many mathematicians reject the axiom of choice. This rejection is based on the belief that all mathematical proofs should be constructive. AC, by its very nature, is nonconstructive, since it merely asserts that a choice function exists, but does not give an explicit method for its construction. Suppose we consider a set consisting of many pairs of shoes. The axiom of choice says that we can create a new set by selecting just the left shoe from each pair. It is obvious that we can do this for shoes, since left and right shoes are distinguishable. What if the pairs of objects in question are not distinguishable and it is not acceptable to say 'just pick any one of them'?

Put another way, it is objectionable to insist that a function exists based on the axiom of choice, and then to derive results based on the existence of that function, when in fact there is no known example of such function and no algorithm for identifying it. This objection to use of the axiom of choice is analogous to the objection to the use of non-falsifiable claims in science. It strains logic to insist that something is true when it cannot be verified, and if it were false no one would even know.

The formulation of constructive axiom of choice is one of three major problems which challenge 21st century logicians.

The axiom of choice is not related to the liberal term pro-choice, which is the term used for themselves by proponents of abortion.