Search the FAQ Archives

3 - A - B - C - D - E - F - G - H - I - J - K - L - M
N - O - P - Q - R - S - T - U - V - W - X - Y - Z
faqs.org - Internet FAQ Archives

sci.math FAQ: The Axiom of Choice


[ Usenet FAQs | Web FAQs | Documents | RFC Index | Business Photos and Profiles ]

See reader questions & answers on this topic! - Help others by sharing your knowledge
Archive-name: sci-math-faq/axiomchoice
Last-modified: February 20, 1998
Version: 7.5

     _________________________________________________________________
   
                              The Axiom of Choice
                                       
   There are several equivalent formulations:
   
     * The Cartesian product of nonempty sets is nonempty, even if the
       product is of an infinite family of sets.
     * Given any set S of mutually disjoint nonempty sets, there is a set
       C containing a single member from each element of S. C can thus be
       thought of as the result of ``choosing" a representative from each
       set in S. Hence the name.
       
Relevance of the Axiom of Choice

   THE AXIOM OF CHOICE
   
   There are many equivalent statements of the Axiom of Choice. The
   following version gave rise to its name:
   
     For any set X there is a function f, with domain X\(0), so that
     f(x) is a member of x for every nonempty x in X.
     
   Such an f is called a ``choice function" on X. [Note that X (0) means
   X with the empty set removed. Also note that in Zermelo-Fraenkel set
   theory all mathematical objects are sets so each member of X is itself
   a set.]
   
   The Axiom of Choice (AC) is one of the most discussed axioms of
   mathematics, perhaps second only to Euclid's parallel postulate. The
   axioms of set theory provide a foundation for modern mathematics in
   the same way that Euclid's five postulates provided a foundation for
   Euclidean geometry, and the questions surrounding AC are the same as
   the questions that surrounded Euclid's Parallel Postulate:
    1. Can it be derived from the other axioms?
    2. Is it consistent with the other axioms?
    3. Should we accept it as an axiom?
       
   For many sets, including any finite set, the first six axioms of set
   theory (abbreviated ZF) are enough to guarantee the existence of a
   choice function but there do exist sets for which AC is required to
   show the existence of a choice function. The existence of such sets
   was proved in 1963 by Paul Cohen. This means that AC cannot be derived
   from the other six axioms; in other words ``AC is independent of ZF."
   This answers question [1] posed above.
   
   The question of whether AC is consistent with the other axioms
   (question [2] above) was answered by Goedel in 1938. Goedel showed
   that if the other axioms are consistent then AC is consistent with
   them. This is a ``relative consistency" proof which is the best we can
   hope for because of Goedel's Second Incompleteness Theorem.
   
   The third question, ``Should we accept it as an axiom?", moves us into
   the realm of philosophy. Today there are three major schools of
   thought concerning the use of AC:
    1. Accept it as an axiom and use it without hesitation.
    2. Accept it as an axiom but use it only when you cannot find a proof
       without it.
    3. AC is unacceptable.
       
   Most mathematicians today belong to school A. Mathematicians who are
   in school B are usually there because of a belief in Occam's Razor
   (use as few assumptions as possible when explaining something) or an
   interest in metamathematics. There are a growing number of people
   moving to school C, especially computer scientists who work on
   automated reasoning using constructive type theories.
   
   Underlying the schools of thought about the use of AC are views about
   truth and the nature of mathematical objects. Three major views are
   platonism, constructivism, and formalism.
   
      Platonism
      
   A platonist believes that mathematical objects exist independent of
   the human mind, and a mathematical statement, such as AC, is
   objectively either true or false. A platonist accepts AC only if it is
   objectively true, and probably falls into school A or C depending on
   her belief. If she isn't sure about AC's truth then she may be in
   school B so that once she finds out the truth about AC she will know
   which theorems are true.
   
      Constructivism
      
   A constructivist believes that the only acceptable mathematical
   objects are ones that can be constructed by the human mind, and the
   only acceptable proofs are constructive proofs. Since AC gives no
   method for constructing a choice set constructivists belong to school
   C.
   
      Formalism
      
   A formalist believes that mathematics is strictly symbol manipulation
   and any consistent theory is reasonable to study. For a formalist the
   notion of truth is confined to the context of mathematical models,
   e.g., a formalist would say "The parallel postulate is false in
   Riemannian geometry." but she wouldn't say "The parallel postulate is
   false." A formalist will probably not allign herself with any school.
   She will comfortably switch between A, B, and C depending on her
   current interests.
   
   So: Should you accept the Axiom of Choice? Here are some arguments for
   and against it.
   
      Against
      
     * It's not as simple, aesthetically pleasing, and intuitive as the
       other axioms.
     * It is equivalent to many statements which are not intuitive such
       as "Every set can be well ordered." How, for example, would you
       well order the reals?
     * With it you can derive non-intuitive results, such as the
       existence of a discontinuous additive function, the existence of a
       non-measurable set of reals, and the Banach-Tarski Paradox (see
       the next section of the sci.math FAQ).
     * It is nonconstructive - it conjures up a set without providing any
       sort of procedure for its construction.
       
      For
      
   The acceptance of AC is based on the belief that our intuition about
   finite sets can be extended to infinite sets. The main argument for
   accepting it is that it is useful. Many important, intuitively
   plausible theorems are equivalent to it or depend on it. For example
   these statements are equivalent to AC:
     * Every vector space has a basis.
     * Trichotomy of Cardinals: For any cardinals k and l, either k<l or
       k=l or k>l.
     * Tychonoff's Theorem: The product of compact spaces is compact in
       the product topology.
     * Zorn's Lemma: Every nonempty partially ordered set P in which each
       chain has an upper bound in P has a maximal element.
       
   And these statements depend on AC (i.e., they cannot be proved in ZF
   without AC):
     * The union of countably many countable sets is countable.
     * Every infinite set has a denumerable subset.
     * The Loewenheim-Skolem Theorem: Any first-order theory which has a
       model has a denumerable model.
     * The Baire Category Theorem: The reals are not the union of
       countably many nowhere dense sets (i.e., the reals are not
       meager).
     * The Ultrafilter Theorem: Every Boolean algebra has an ultrafilter
       on it.
       
      Alternatives to AC
      
     * Accept only a weak form of AC such as the Denumerable Axiom of
       Choice (every denumerable set has a choice function) or the Axiom
       of Dependent Choice.
     * Accept an axiom that implies AC such as the Axiom of
       Constructibility (V=L) or the Generalized Continuum Hypothesis
       (GCH).
     * Adopt AC as a logical axiom (Hilbert suggested this with his
       epsilon axiom). If set theory is done in such a logical formal
       system the Axiom of Choice will be a theorem.
     * Accept a contradictory axiom such as the Axiom of Determinacy.
     * Use a completely different framework for mathematics such as
       Category Theory. Note that within the framework of Category Theory
       Tychonoff's Theorem can be proved without AC (Johnstone, 1981).
       
      Test Yourself: When is AC necessary?
      
   If you are working in Zermelo-Fraenkel set theory without the Axiom of
   Choice, can you choose an element from...
    1. a finite set?
    2. an infinite set?
    3. each member of an infinite set of singletons (i.e., one-element
       sets)?
    4. each member of an infinite set of pairs of shoes?
    5. each member of inifinite set of pairs of socks?
    6. each member of a finite set of sets if each of the members is
       infinite?
    7. each member of an infinite set of sets if each of the members is
       infinite?
    8. each member of a denumerable set of sets if each of the members is
       infinite?
    9. each member of an infinite set of sets of rationals?
   10. each member of a denumerable set of sets if each of the members is
       denumberable?
   11. each member of an infinite set of sets if each of the members is
       finite?
   12. each member of an infinite set of finite sets of reals?
   13. each member of an infinite set of sets of reals?
   14. each member of an infinite set of two-element sets whose members
       are sets of reals?
       
   The answers to these questions with explanations are accessible
   through http://www.jazzie.com/ii/math/index.html
   
      References
      
   Benacerraf, Paul and Putnam, Hilary. "Philosophy of Mathematics:
   Selected Readings, 2nd edition." Cambridge University Press, 1983.
   
   Dauben, Joseph Warren. "Georg Cantor: His Mathematics and Philosophy
   of the Infinite." Princeton University Press, 1979.
   
   A. Fraenkel, Y. Bar-Hillel, and A. Levy with van Dalen, Dirk.
   "Foundations of Set Theory, Second Revised Edition." North-Holland,
   1973.
   
   Johnstone, Peter T. "Tychonoff's Theorem without the Axiom of Choice."
   Fundamenta Mathematica 113: 21-35, 1981.
   
   Leisenring, Albert C. "Mathematical Logic and Hilbert's
   Epsilon-Symbol." Gordon and Breach, 1969.
   
   Maddy, "Believing the Axioms, I", J. Symb. Logic, v. 53, no. 2, June
   1988, pp. 490-500, and "Believing the Axioms II" in v.53, no. 3.
   
   Moore, Gregory H. "Zermelo's Axiom of Choice: Its Origins,
   Development, and Influence." Springer-Verlag, 1982.
   
   Rubin, Herman and Rubin, Jean E. "Equivalents of the Axiom of Choice
   II." North-Holland, 1985.
   
   This section of the FAQ is Copyright (c) 1994 Nancy McGough. Send
   comments and or corrections relating to this part to nancym@ii.com.
   The most up to date version of this section of the sci.math FAQ is
   accesible through http://www.jazzie.com/ii/math/index.html
-- 
Alex Lopez-Ortiz                                         alopez-o@unb.ca
http://www.cs.unb.ca/~alopez-o                       Assistant Professor	
Faculty of Computer Science                  University of New Brunswick

User Contributions:

Comment about this article, ask questions, or add new information about this topic:

CAPTCHA


[ Usenet FAQs | Web FAQs | Documents | RFC Index ]

Send corrections/additions to the FAQ Maintainer:
alopez-o@neumann.uwaterloo.ca





Last Update March 27 2014 @ 02:12 PM