 | Axiom of choice: Encyclopedia II - Axiom of choice - Usage
Axiom of choice - Usage
Until the late 19th century, the axiom of choice was often used implicitly. For example, after having established that the set X contains only non-empty sets, a mathematician might have said "let F(s) be one of the members of s for all s in X." In general, it is impossible to prove that F exists without the axiom of choice, but this seems to have gone unnoticed until Zermelo.
Not every situation requires the axiom of choice. For finite sets X, the axiom of choice follows from the other axioms of set theory. In that case it is equivalent to saying that if we have several (a finite number of) boxes, each containing at least one item, then we can choose exactly one item from each box. Clearly we can do this: We start at the first box, choose an item; go to the second box, choose an item; and so on. There are only finitely many boxes, so eventually our choice procedure comes to an end. The result is an explicit choice function: a function that takes the first box to the first element we chose, the second box to the second element we chose, and so on. (A formal proof for all finite sets would use the principle of mathematical induction.)
For certain infinite sets X, it is also possible to avoid the axiom of choice. For example, suppose that the elements of X are sets of natural numbers. Every nonempty set of natural numbers has a least element, so to specify our choice function we can simply say that it takes each set to the least element of that set. This gives us a definite choice of an element from each set and we can write down an explicit expression that tells us what value our choice function takes. Any time it is possible to specify such an explicit choice, the axiom of choice is unnecessary.
The difficulty appears when there is no natural choice of elements from each set. If we cannot make explicit choices, how do we know that our set exists? For example, suppose that X is the set of all non-empty subsets of the real numbers. First we might try to proceed as if X were finite. If we try to choose an element from each set, then, because X is infinite, our choice procedure will never come to an end, and consequently, we will never be able to produce a choice function for all of X. So that won't work. Next we might try the trick of specifying the least element from each set. But some subsets of the real numbers don't have least elements. For example, the open interval (0,1) does not have a least element: If x is in (0,1), then so is x/2, and x/2 is always strictly smaller than x. So taking least elements doesn't work, either.
The reason that we are able to choose least elements from subsets of the natural numbers is the fact that the natural numbers are well-ordered: Every subset of the natural numbers has a unique least element. Perhaps if we were clever we might say, "Even though the usual ordering of the real numbers does not work, it may be possible to find a different ordering of the real numbers which is a well-ordering. Then our choice function can choose the least element of every set under our unusual ordering." The problem then becomes constructing such an ordering, and it turns out that every set can be well-ordered if and only if the axiom of choice is true.
A proof requiring the axiom of choice is always nonconstructive: even if the proof produces an object then it is impossible to say exactly what that object is. Consequently, while the axiom of choice asserts that there is a well-ordering of the real numbers, it does not give us an example of one. Yet the reason why we chose above to well-order the real numbers was so that for each set in X, we could explicitly choose an element of that set. If we cannot write down the well-ordering we are using, then our choice is not very explicit. This is one of the reasons why some mathematicians dislike the axiom of choice. For example, constructivists posit that all existence proofs should be totally explicit; it should be possible to construct anything that exists. They reject the axiom of choice because it asserts the existence of an object without telling what it is.
Other related archives1904, A. K. Dewdney, Algebra, April Fool's Day, Axiom of dependent choice, Baire category theorem, Banach-Alaoglu theorem, Banach–Tarski paradox, Bertrand Russell, Boolean prime ideal theorem, Ernst Zermelo, Functional analysis, General topology, Hahn-Banach theorem, Hausdorff paradox, Hilbert space, Kurt Gödel, Measure theory, Nielsen-Schreier theorem, Paul Cohen, Per Martin-Löf, Scientific American, Set theory, Set-builder notation, Stone's representation theorem for Boolean algebras, Stone-Cech compactification, Trichotomy, Tychonoff space, Tychonoff's theorem, Vitali theorem, Zermelo-Fraenkel set theory, Zorn's lemma, algebraic closure, axiom, axiom of countable choice, axiom of dependent choice, axiom of uniformization, basis, cardinality, category, choice function, choose, closed, closed graph theorem, closure, compact, compactness, complete, constructive logic, constructivists, countably many, determined, field, field extension, functional analysis, game, generalized continuum hypothesis, infinite, infinitely, injection, intuitionistic logic, intuitionistic type theory, law of excluded middle, linear functionals, logically independent, mathematical induction, mathematics, maximal ideal, measurable, metric spaces, model, natural numbers, negation, non-empty, non-measurable sets, nonconstructive, open, open mapping theorem, product, real analysis, real numbers, ring, set, set theory, skeleton, topological spaces, transcendence basis, ultrafilter lemma, uniform spaces, union, vector space, well-ordered, well-ordering principle, well-ordering theorem
 Adapted from the Wikipedia article "Usage", under the G.N U Free Docmentation License. Please also see http://en.wikipedia.org/wiki |
