home *** CD-ROM | disk | FTP | other *** search
/ ftp.pasteur.org/FAQ/ / ftp-pasteur-org-FAQ.zip / FAQ / sci-math-faq / AC / relevance < prev   
Encoding:
Text File  |  1995-11-18  |  10.7 KB  |  276 lines
  1. Newsgroups: sci.math,sci.answers,news.answers
  2. Path: senator-bedfellow.mit.edu!bloom-beacon.mit.edu!spool.mu.edu!torn!watserv3.uwaterloo.ca!undergrad.math.uwaterloo.ca!neumann.uwaterloo.ca!alopez-o
  3. From: alopez-o@neumann.uwaterloo.ca (Alex Lopez-Ortiz)
  4. Subject: sci.math FAQ: Relevance of AC
  5. Summary: Part 26 of many, New version,
  6. Originator: alopez-o@neumann.uwaterloo.ca
  7. Message-ID: <DI76MH.ACs@undergrad.math.uwaterloo.ca>
  8. Sender: news@undergrad.math.uwaterloo.ca (news spool owner)
  9. Approved: news-answers-request@MIT.Edu
  10. Date: Fri, 17 Nov 1995 17:15:53 GMT
  11. Expires: Fri, 8 Dec 1995 09:55:55 GMT
  12. Reply-To: nancym@ii.com
  13. Nntp-Posting-Host: neumann.uwaterloo.ca
  14. Organization: University of Waterloo
  15. Followup-To: sci.math
  16. Lines: 257
  17. Xref: senator-bedfellow.mit.edu sci.math:124400 sci.answers:3434 news.answers:57835
  18.  
  19.  
  20. Archive-Name: sci-math-faq/AC/relevance
  21. Last-modified: December 8, 1994
  22. Version: 6.2
  23.  
  24.  
  25.  
  26.  
  27.                              THE AXIOM OF CHOICE
  28.  
  29.  
  30.  
  31.    There are several equivalent formulations:
  32.  
  33.      * The Cartesian product of nonempty sets is nonempty, even if the
  34.        product is of an infinite family of sets.
  35.  
  36.      * Given any set S of mutually disjoint nonempty sets, there is a set
  37.        C containing a single member from each element of S . C can thus
  38.        be thought of as the result of ``choosing" a representative from
  39.        each set in S . Hence the name.
  40.  
  41.  
  42.  
  43.  
  44. Relevance of the Axiom of Choice
  45.  
  46.  
  47.  
  48.    THE AXIOM OF CHOICE
  49.  
  50.    There are many equivalent statements of the Axiom of Choice. The
  51.    following version gave rise to its name:
  52.  
  53.      For any set X there is a function f , with domain X\(0) , so that
  54.      f(x) is a member of x for every nonempty x in X .
  55.  
  56.    Such an f is called a ``choice function" on X . [Note that X\ (0)
  57.    means X with the empty set removed. Also note that in Zermelo-Fraenkel
  58.    set theory all mathematical objects are sets so each member of X is
  59.    itself a set.]
  60.  
  61.    The Axiom of Choice (AC) is one of the most discussed axioms of
  62.    mathematics, perhaps second only to Euclid's parallel postulate. The
  63.    axioms of set theory provide a foundation for modern mathematics in
  64.    the same way that Euclid's five postulates provided a foundation for
  65.    Euclidean geometry, and the questions surrounding AC are the same as
  66.    the questions that surrounded Euclid's Parallel Postulate:
  67.     1. Can it be derived from the other axioms?
  68.     2. Is it consistent with the other axioms?
  69.     3. Should we accept it as an axiom?
  70.  
  71.    For many sets, including any finite set, the first six axioms of set
  72.    theory (abbreviated ZF) are enough to guarantee the existence of a
  73.    choice function but there do exist sets for which AC is required to
  74.    show the existence of a choice function. The existence of such sets
  75.    was proved in 1963 by Paul Cohen. This means that AC cannot be derived
  76.    from the other six axioms; in other words ``AC is independent of ZF."
  77.    This answers question [1] posed above.
  78.  
  79.    The question of whether AC is consistent with the other axioms
  80.    (question [2] above) was answered by Goedel in 1938. Goedel showed
  81.    that if the other axioms are consistent then AC is consistent with
  82.    them. This is a ``relative consistency" proof which is the best we can
  83.    hope for because of Goedel's Second Incompleteness Theorem.
  84.  
  85.    The third question, ``Should we accept it as an axiom?", moves us into
  86.    the realm of philosophy. Today there are three major schools of
  87.    thought concerning the use of AC:
  88.     1. Accept it as an axiom and use it without hesitation.
  89.     2. Accept it as an axiom but use it only when you cannot find a proof
  90.        without it.
  91.     3. AC is unacceptable.
  92.  
  93.    Most mathematicians today belong to school A. Mathematicians who are
  94.    in school B are usually there because of a belief in Occam's Razor
  95.    (use as few assumptions as possible when explaining something) or an
  96.    interest in metamathematics. There are a growing number of people
  97.    moving to school C, especially computer scientists who work on
  98.    automated reasoning using constructive type theories.
  99.  
  100.    Underlying the schools of thought about the use of AC are views about
  101.    truth and the nature of mathematical objects. Three major views are
  102.    platonism, constructivism, and formalism.
  103.  
  104.    Platonism
  105.  
  106.    A platonist believes that mathematical objects exist independent of
  107.    the human mind, and a mathematical statement, such as AC, is
  108.    objectively either true or false. A platonist accepts AC only if it is
  109.    objectively true, and probably falls into school A or C depending on
  110.    her belief. If she isn't sure about AC's truth then she may be in
  111.    school B so that once she finds out the truth about AC she will know
  112.    which theorems are true.
  113.  
  114.  
  115.  
  116.    Constructivism
  117.  
  118.    A constructivist believes that the only acceptable mathematical
  119.    objects are ones that can be constructed by the human mind, and the
  120.    only acceptable proofs are constructive proofs. Since AC gives no
  121.    method for constructing a choice set constructivists belong to school
  122.    C.
  123.  
  124.  
  125.  
  126.    Formalism
  127.  
  128.    A formalist believes that mathematics is strictly symbol manipulation
  129.    and any consistent theory is reasonable to study. For a formalist the
  130.    notion of truth is confined to the context of mathematical models,
  131.    e.g., a formalist would say "The parallel postulate is false in
  132.    Riemannian geometry." but she wouldn't say "The parallel postulate is
  133.    false." A formalist will probably not allign herself with any school.
  134.    She will comfortably switch between A, B, and C depending on her
  135.    current interests.
  136.  
  137.    So: Should you accept the Axiom of Choice? Here are some arguments for
  138.    and against it.
  139.  
  140.  
  141.  
  142.    Against
  143.  
  144.      * It's not as simple, aesthetically pleasing, and intuitive as the
  145.        other axioms.
  146.      * It is equivalent to many statements which are not intuitive such
  147.        as "Every set can be well ordered." How, for example, would you
  148.        well order the reals?
  149.      * With it you can derive non-intuitive results, such as the
  150.        existence of a discontinuous additive function, the existence of a
  151.        non-measurable set of reals, and the Banach-Tarski Paradox (see
  152.        the next section of the sci.math FAQ).
  153.      * It is nonconstructive - it conjures up a set without providing any
  154.        sort of procedure for its construction.
  155.  
  156.  
  157.  
  158.    For
  159.  
  160.    The acceptance of AC is based on the belief that our intuition about
  161.    finite sets can be extended to infinite sets. The main argument for
  162.    accepting it is that it is useful. Many important, intuitively
  163.    plausible theorems are equivalent to it or depend on it. For example
  164.    these statements are equivalent to AC:
  165.      * Every vector space has a basis.
  166.      * Trichotomy of Cardinals: For any cardinals k and l , either k < l
  167.        or k = l or k > l .
  168.      * Tychonoff's Theorem: The product of compact spaces is compact in
  169.        the product topology.
  170.      * Zorn's Lemma: Every nonempty partially ordered set P in which each
  171.        chain has an upper bound in P has a maximal element.
  172.  
  173.    And these statements depend on AC (i.e., they cannot be proved in ZF
  174.    without AC):
  175.      * The union of countably many countable sets is countable.
  176.      * Every infinite set has a denumerable subset.
  177.      * The Loewenheim-Skolem Theorem: Any first-order theory which has a
  178.        model has a denumerable model.
  179.      * The Baire Category Theorem: The reals are not the union of
  180.        countably many nowhere dense sets (i.e., the reals are not
  181.        meager).
  182.      * The Ultrafilter Theorem: Every Boolean algebra has an ultrafilter
  183.        on it.
  184.  
  185.  
  186.  
  187.    Alternatives to AC
  188.  
  189.      * Accept only a weak form of AC such as the Denumerable Axiom of
  190.        Choice (every denumerable set has a choice function) or the Axiom
  191.        of Dependent Choice.
  192.      * Accept an axiom that implies AC such as the Axiom of
  193.        Constructibility ( V = L ) or the Generalized Continuum Hypothesis
  194.        (GCH).
  195.      * Adopt AC as a logical axiom (Hilbert suggested this with his
  196.        epsilon axiom). If set theory is done in such a logical formal
  197.        system the Axiom of Choice will be a theorem.
  198.      * Accept a contradictory axiom such as the Axiom of Determinacy.
  199.      * Use a completely different framework for mathematics such as
  200.        Category Theory. Note that within the framework of Category Theory
  201.        Tychonoff's Theorem can be proved without AC (Johnstone, 1981).
  202.  
  203.  
  204.  
  205.    Test Yourself: When is AC necessary?
  206.  
  207.    If you are working in Zermelo-Fraenkel set theory without the Axiom of
  208.    Choice, can you choose an element from...
  209.     1. a finite set?
  210.     2. an infinite set?
  211.     3. each member of an infinite set of singletons (i.e., one-element
  212.        sets)?
  213.     4. each member of an infinite set of pairs of shoes?
  214.     5. each member of inifinite set of pairs of socks?
  215.     6. each member of a finite set of sets if each of the members is
  216.        infinite?
  217.     7. each member of an infinite set of sets if each of the members is
  218.        infinite?
  219.     8. each member of a denumerable set of sets if each of the members is
  220.        infinite?
  221.     9. each member of an infinite set of sets of rationals?
  222.    10. each member of a denumerable set of sets if each of the members is
  223.        denumberable?
  224.    11. each member of an infinite set of sets if each of the members is
  225.        finite?
  226.    12. each member of an infinite set of finite sets of reals?
  227.    13. each member of an infinite set of sets of reals?
  228.    14. each member of an infinite set of two-element sets whose members
  229.        are sets of reals?
  230.  
  231.    The answers to these questions with explanations are accessible
  232.    through http://www.jazzie.com/ii/math/index.html
  233.  
  234.  
  235.  
  236.    References
  237.  
  238.    Benacerraf, Paul and Putnam, Hilary. "Philosophy of Mathematics:
  239.    Selected Readings, 2nd edition." Cambridge University Press, 1983.
  240.  
  241.    Dauben, Joseph Warren. "Georg Cantor: His Mathematics and Philosophy
  242.    of the Infinite." Princeton University Press, 1979.
  243.  
  244.    A. Fraenkel, Y. Bar-Hillel, and A. Levy with van Dalen, Dirk.
  245.    "Foundations of Set Theory, Second Revised Edition." North-Holland,
  246.    1973.
  247.  
  248.    Johnstone, Peter T. "Tychonoff's Theorem without the Axiom of Choice."
  249.    Fundamenta Mathematica 113: 21-35, 1981.
  250.  
  251.    Leisenring, Albert C. "Mathematical Logic and Hilbert's
  252.    Epsilon-Symbol." Gordon and Breach, 1969.
  253.  
  254.    Maddy, "Believing the Axioms, I", J. Symb. Logic, v. 53, no. 2, June
  255.    1988, pp. 490-500, and "Believing the Axioms II" in v.53, no. 3.
  256.  
  257.    Moore, Gregory H. "Zermelo's Axiom of Choice: Its Origins,
  258.    Development, and Influence." Springer-Verlag, 1982.
  259.  
  260.    Rubin, Herman and Rubin, Jean E. "Equivalents of the Axiom of Choice
  261.    II." North-Holland, 1985.
  262.  
  263.    This section of the FAQ is Copyright (c) 1994 Nancy McGough. Send
  264.    comments and or corrections relating to this part to nancym@ii.com.
  265.    The most up to date version of this section of the sci.math FAQ is
  266.    accesible through http://www.jazzie.com/ii/math/index.html
  267.  
  268.  
  269.      _________________________________________________________________
  270.  
  271.  
  272.    
  273.    
  274.  
  275.  
  276.