Difference between revisions of "Axiom of Choice"

From Conservapedia
Jump to: navigation, search
(fixed quote)
m (→‎Usage: HTTP --> HTTPS [#1], replaced: http://books.google.com → https://books.google.com)
 
(35 intermediate revisions by 14 users not shown)
Line 1: Line 1:
−
The '''Axiom of Choice''' ('''AC''')<ref>There are numerous equivalent [[mathematical formula]]e which capture the idea of the Axiom of Choice. Here are two:
+
The '''Axiom of Choice''' ('''AC''') in [[set theory]] states that "for every set made of [[nonempty set]]s there is a function that chooses an element from each set". This function is called a ''choice function''.
−
::<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>
+
  
−
and
+
This axiom is powerful because by assuming the existence of such a function, one can then manipulate the function to prove otherwise unprovable theorems.  This axiom is controversial because it assumes the existence of a function without giving any hint on how it could be constructed. This axiom has been used to prove many apparently absurd results, as in the [[Banach-Tarski Paradox]] discussed below.
−
::<math>\forall x\neq\varnothing\;\exists S\;(\forall z\in x\;\exists_1w\in z\cap S).</math></ref> is a powerful [[axiom]] of [[Zermelo-Fraenkel]] set theory that is useful for proving otherwise unprovable problems, but which has also been used to prove statements that appear absurd.<ref>See, e.g., the [[Banach-Tarski Paradox]] discussed below.</ref>  The '''Axiom of Choice''' holds that:<ref name="willard">Stephen Willard, "General Topology" 1.17, p. 9 (Dover 2004)</ref>
+
  
−
::given any collection of sets, however large, we can pick one element from each set in the collection.
+
To better understand the Axiom of Choice, consider alternative descriptions of it:
  
−
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."  More precisely, the Axiom of Choice states that:
+
The Axiom of Choice holds that:<ref name="willard">Stephen Willard, "General Topology" 1.17, p. 9 (Dover 2004)</ref>
 +
 
 +
::given any collection of [[set]]s, however large, we can pick one element from each set in the collection.
 +
 
 +
More precisely, the Axiom of Choice states that:
  
 
::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.
 
::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.
  
−
Mathworld explains the Axiom of Choice as follows:<ref>http://mathworld.wolfram.com/AxiomofChoice.html</ref>
+
Mathworld explains the Axiom of Choice as follows:<ref name="mathworld">http://mathworld.wolfram.com/AxiomofChoice.html</ref>
  
−
::Given any set of mutually disjoint nonempty sets, there exists at least one set that contains exactly one element in common with each of the nonempty sets.
+
::Given any set of mutually [[disjoint]] nonempty sets, there exists at least one set that contains exactly one element in common with each of the nonempty sets.
 +
 
 +
Therefore, "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." 
  
 
Yet another helpful explanation of the Axiom of Choice is this:<ref name="kuro5hin">http://www.kuro5hin.org/story/2003/5/23/134430/275</ref>
 
Yet another helpful explanation of the Axiom of Choice is this:<ref name="kuro5hin">http://www.kuro5hin.org/story/2003/5/23/134430/275</ref>
Line 19: Line 23:
 
::If you have a collection of sets C (which may potentially contain an uncountably large number of sets), then there exists a set H, called the choice set, which contains precisely one element from each (non-empty) set in C. H is called the "choice set" because you are essentially going through each set in C and choosing one element from it. One feature of the Axiom of Choice is that H is simply assumed to exist; there is no algorithm given which might tell you how to construct an example of H.
 
::If you have a collection of sets C (which may potentially contain an uncountably large number of sets), then there exists a set H, called the choice set, which contains precisely one element from each (non-empty) set in C. H is called the "choice set" because you are essentially going through each set in C and choosing one element from it. One feature of the Axiom of Choice is that H is simply assumed to exist; there is no algorithm given which might tell you how to construct an example of H.
  
−
It has been shown that the Axiom of Choice is consistent with and independent of the other axioms of set theory. Thus assuming the Axiom of Choice and assuming its negation each result in consistent set theories, differing from each other.
+
Here is another description of the Axiom of Choice:<ref>http://www.math.vanderbilt.edu/~schectex/ccc/choice.html</ref>
 +
 
 +
::Let C be a collection of nonempty sets. Then we can choose a member from each set in that collection. In other words, there exists a function f defined on C with the property that, for each set S in the collection, f(S) is a member of S.  The function f is then called a choice function.
 +
 
 +
It has been shown that neither the Axiom of Choice nor its negation will contradict the other axioms of set theory. Thus assuming the Axiom of Choice and assuming its negation will each result in differing, consistent set theories. It is the choice of the mathematician whether to believe the axiom or believe its negation; many people choose to not take a position on this issue at all because the majority of mathematics can be proven without invoking the axiom altogether.
  
 
== Use of the Axiom of Choice ==
 
== Use of the Axiom of Choice ==
  
−
The Axiom of Choice has many equivalent statements, such as the [[Tychonoff theorem]], the [[Well-Ordering Theorem]], the existence of [[cardinal number]]s, 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]]. In [[algebra]] it is common to use [[Zorn's Lemma]] (also equivalent to the Axiom of Choice) to study [[ideal]]s in infinite [[Noetherian ring]]s.
+
The Axiom of Choice has many equivalent statements, such as the [[Tychonoff theorem]], the Well-Ordering Theorem,<ref name="mathworld" /> the existence of [[cardinal number]]s and the existence of a basis for every vector space.<ref>http://marauder.millersville.edu/~bikenaga/linearalgebra/basis/basis.html</ref> In [[algebra]] it is common to use Zorn's Lemma (also equivalent to the Axiom of Choice<ref>http://mathworld.wolfram.com/ZornsLemma.html</ref>) to study [[ideal]]s in infinite [[Noetherian ring]]s.
  
−
Use of the Axiom of Choice has led to some seemingly absurd results.  In the [[Banach-Tarski Paradox]], the Axiom of Choice is used to prove that a solid sphere of infinitely divisible parts may be chopped up and reconstructed as two new spheres of identical size, thereby creating 2 out of only 1.  This paradox is proven only through use of the Axiom of Choice, and the authors of this proof did so to criticize this Axiom.  One attempt to resolve this apparent contradiction is to show that physical spheres are not [[Lebesgue measurable]].<ref name="kuro5hin" />
+
Use of the Axiom of Choice leads to some seemingly absurd results.  In the [[Banach-Tarski Paradox]], the Axiom of Choice is used to prove that a solid sphere of infinitely divisible parts may be chopped up and reconstructed as two new spheres of identical size, thereby creating 2 out of only 1.  This paradox is proven only through use of the Axiom of Choice, and the authors of this proof did so to criticize this Axiom.  One attempt to resolve this apparent contradiction is observe that the "pieces" constructed in the course of the paradox are not Lebesgue measure, so there is no way that this process could ever be carried out with a physical object.
  
−
The highly publicized proof of [[Fermat's Last Theorem]] relies on the Axiom of Choice, which was one of the points of criticism by [[Marilyn vos Savant]] in her column and book.<ref>Ask Marilyn ® by Marilyn vos Savant, Parade Magazine. November 21, 1993</ref><ref>''The World's Most Famous Math Problem: The Proof of Fermat's Last Theorem and Other Mathematical Mysteries'', Marilyn vos Savant. St. Martin's Griffin, 1993</ref>
+
The Axiom of Choice can also be used to prove the apparently absurd existence of subsets of the real line which do not have a well-defined Lebesgue measure.<ref>However, it is also possible to construct such a subset without using the Axiom of Choice. See [http://matwbn.icm.edu.pl/ksiazki/fm/fm138/fm13812.pdf "The Hahn-Banach theorem implies the existence of a non-Lebesgue measurable set"]</ref>
  
−
== Controversy ==
 
  
−
Despite its usefulness, many mathematicians reject the Axiom of Choice. Stephen Willard, author of the textbook "General Topolog"y, wrote the following after describing the axiom of choice:
+
== Usage ==
 +
Despite its usefulness, many mathematicians prefer to avoid the Axiom of Choice when possible. Stephen Willard, author of the textbook ''General Topology'', wrote the following after describing the Axiom of Choice:
  
−
<blockquote>It is left to the reader to decide that these two statements both say the same thing. What they say is: given any collection of sets, however large, we can pick one element from each set in the collection. It bothers some people because it asserts the existence of a set (...)  without giving enough information to determine that set uniquely (by applying a finite number of rules), and it is the ''only'' formal set-theoretic axiom which does this.  For this reason it is customary to mention the axiom of choice whenever it is used.  It need not be used if the number of sets is finite.<ref>[http://books.google.com/books?id=-o8xJQ7Ag2cC&printsec=frontcover#PPA9,M1 Page 9 of "General Topology"]</ref></blockquote>
+
<blockquote>It is left to the reader to decide that these two statements both say the same thing. What they say is: given any collection of sets, however large, we can pick one element from each set in the collection. It bothers some people because it asserts the existence of a set (...)  without giving enough information to determine that set uniquely (by applying a finite number of rules), and it is the ''only'' formal set-theoretic axiom which does this.  For this reason it is customary to mention the axiom of choice whenever it is used.  It need not be used if the number of sets is finite.<ref>[https://books.google.com/books?id=-o8xJQ7Ag2cC&printsec=frontcover#PPA9,M1 Page 9 of "General Topology"]</ref></blockquote>
  
−
The rejection of the Axiom of Choice reflects a preference for constructive [[Proof|mathematical proofs]]. 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. Since the Axiom of Choice is independent of the other axioms, assuming this axiom results in a more constrained system than otherwise.  Thus results provable with it might not be provable or might not even be true, without it.
+
The avoidance of the Axiom of Choice reflects a preference for [[constructive proof]]s. 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. Since the Axiom of Choice is independent of the other axioms, assuming this axiom results in a more constrained system than otherwise.  Thus results provable with it might not be provable or might not even be true, without it.
 +
 
 +
The general situation is this: some results (for example, Tychonoff's theorem) simply can't be proved without assuming the axiom of choice.  When proving theorems, mathematicians prefer to proceed using as few axioms as possible, and it is now understood that there are some theorems which can be proved without the axiom of choice, and some that can not.  It is well-understood which theorems fall into which category.  In some branches of mathematics, for example functional analysis, the use of the axiom of choice is ubiquitous because of reliance on things like the Hahn-Banach theorem (though this theorem can be proved using a strictly weaker axiom).
  
 
The formulation of a constructive Axiom of Choice is one of three major problems which challenge 21st century logicians.<ref>Edna Ernestine Kramer, "The Nature and Growth of Modern Mathematics", Princeton University
 
The formulation of a constructive Axiom of Choice is one of three major problems which challenge 21st century logicians.<ref>Edna Ernestine Kramer, "The Nature and Growth of Modern Mathematics", Princeton University
 
Press, 1982. p. 595.</ref>
 
Press, 1982. p. 595.</ref>
 +
 +
== Instruction ==
 +
 +
In many undergraduate mathematics curricula, the Axiom of Choice is introduced early as a tool for solving problems. It often goes under one of its other guises, such as [[Zorn's Lemma]] or the [[Well-Ordering Theorem]]. Students are taught it as a proof method, but often with little mention of the questionable nature of the axiom. Often, a full discussion of the [[paradox]]es that accompany the axiom is left to a higher (graduate) level special topics course in [[logic]], despite the fact that mathematicians in numerous fields may be tempted to use it and thus should be aware of its controversy. Undergraduate courses also neglect to adequately mention when the axiom is being invoked, giving a false sense that use of the axiom is incidental, rather than documenting its widespread nature in recent mathematical proofs.
  
 
== Sources ==
 
== Sources ==
  
 
*http://www.math.vanderbilt.edu/~schectex/ccc/choice.html
 
*http://www.math.vanderbilt.edu/~schectex/ccc/choice.html
 +
 +
== See also ==
 +
 +
*[[Zermelo-Fraenkel]] [[set theory]].
  
 
== References ==
 
== References ==
Line 48: Line 66:
 
<references/>
 
<references/>
  
−
[[category:set theory]]
+
[[Category:Set Theory]]
−
[[category:mathematics]]
+
[[Category:Advanced Mathematics]]

Latest revision as of 13:40, September 26, 2018

The Axiom of Choice (AC) in set theory states that "for every set made of nonempty sets there is a function that chooses an element from each set". This function is called a choice function.

This axiom is powerful because by assuming the existence of such a function, one can then manipulate the function to prove otherwise unprovable theorems. This axiom is controversial because it assumes the existence of a function without giving any hint on how it could be constructed. This axiom has been used to prove many apparently absurd results, as in the Banach-Tarski Paradox discussed below.

To better understand the Axiom of Choice, consider alternative descriptions of it:

The Axiom of Choice holds that:[1]

given any collection of sets, however large, we can pick one element from each set in the collection.

More precisely, the Axiom of Choice states that:

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.

Mathworld explains the Axiom of Choice as follows:[2]

Given any set of mutually disjoint nonempty sets, there exists at least one set that contains exactly one element in common with each of the nonempty sets.

Therefore, "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."

Yet another helpful explanation of the Axiom of Choice is this:[3]

If you have a collection of sets C (which may potentially contain an uncountably large number of sets), then there exists a set H, called the choice set, which contains precisely one element from each (non-empty) set in C. H is called the "choice set" because you are essentially going through each set in C and choosing one element from it. One feature of the Axiom of Choice is that H is simply assumed to exist; there is no algorithm given which might tell you how to construct an example of H.

Here is another description of the Axiom of Choice:[4]

Let C be a collection of nonempty sets. Then we can choose a member from each set in that collection. In other words, there exists a function f defined on C with the property that, for each set S in the collection, f(S) is a member of S. The function f is then called a choice function.

It has been shown that neither the Axiom of Choice nor its negation will contradict the other axioms of set theory. Thus assuming the Axiom of Choice and assuming its negation will each result in differing, consistent set theories. It is the choice of the mathematician whether to believe the axiom or believe its negation; many people choose to not take a position on this issue at all because the majority of mathematics can be proven without invoking the axiom altogether.

Use of the Axiom of Choice

The Axiom of Choice has many equivalent statements, such as the Tychonoff theorem, the Well-Ordering Theorem,[2] the existence of cardinal numbers and the existence of a basis for every vector space.[5] In algebra it is common to use Zorn's Lemma (also equivalent to the Axiom of Choice[6]) to study ideals in infinite Noetherian rings.

Use of the Axiom of Choice leads to some seemingly absurd results. In the Banach-Tarski Paradox, the Axiom of Choice is used to prove that a solid sphere of infinitely divisible parts may be chopped up and reconstructed as two new spheres of identical size, thereby creating 2 out of only 1. This paradox is proven only through use of the Axiom of Choice, and the authors of this proof did so to criticize this Axiom. One attempt to resolve this apparent contradiction is observe that the "pieces" constructed in the course of the paradox are not Lebesgue measure, so there is no way that this process could ever be carried out with a physical object.

The Axiom of Choice can also be used to prove the apparently absurd existence of subsets of the real line which do not have a well-defined Lebesgue measure.[7]


Usage

Despite its usefulness, many mathematicians prefer to avoid the Axiom of Choice when possible. Stephen Willard, author of the textbook General Topology, wrote the following after describing the Axiom of Choice:

It is left to the reader to decide that these two statements both say the same thing. What they say is: given any collection of sets, however large, we can pick one element from each set in the collection. It bothers some people because it asserts the existence of a set (...) without giving enough information to determine that set uniquely (by applying a finite number of rules), and it is the only formal set-theoretic axiom which does this. For this reason it is customary to mention the axiom of choice whenever it is used. It need not be used if the number of sets is finite.[8]

The avoidance of the Axiom of Choice reflects a preference for constructive proofs. 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. Since the Axiom of Choice is independent of the other axioms, assuming this axiom results in a more constrained system than otherwise. Thus results provable with it might not be provable or might not even be true, without it.

The general situation is this: some results (for example, Tychonoff's theorem) simply can't be proved without assuming the axiom of choice. When proving theorems, mathematicians prefer to proceed using as few axioms as possible, and it is now understood that there are some theorems which can be proved without the axiom of choice, and some that can not. It is well-understood which theorems fall into which category. In some branches of mathematics, for example functional analysis, the use of the axiom of choice is ubiquitous because of reliance on things like the Hahn-Banach theorem (though this theorem can be proved using a strictly weaker axiom).

The formulation of a constructive Axiom of Choice is one of three major problems which challenge 21st century logicians.[9]

Instruction

In many undergraduate mathematics curricula, the Axiom of Choice is introduced early as a tool for solving problems. It often goes under one of its other guises, such as Zorn's Lemma or the Well-Ordering Theorem. Students are taught it as a proof method, but often with little mention of the questionable nature of the axiom. Often, a full discussion of the paradoxes that accompany the axiom is left to a higher (graduate) level special topics course in logic, despite the fact that mathematicians in numerous fields may be tempted to use it and thus should be aware of its controversy. Undergraduate courses also neglect to adequately mention when the axiom is being invoked, giving a false sense that use of the axiom is incidental, rather than documenting its widespread nature in recent mathematical proofs.

Sources

See also

References

  1. ↑ Stephen Willard, "General Topology" 1.17, p. 9 (Dover 2004)
  2. ↑ 2.0 2.1 http://mathworld.wolfram.com/AxiomofChoice.html
  3. ↑ http://www.kuro5hin.org/story/2003/5/23/134430/275
  4. ↑ http://www.math.vanderbilt.edu/~schectex/ccc/choice.html
  5. ↑ http://marauder.millersville.edu/~bikenaga/linearalgebra/basis/basis.html
  6. ↑ http://mathworld.wolfram.com/ZornsLemma.html
  7. ↑ However, it is also possible to construct such a subset without using the Axiom of Choice. See "The Hahn-Banach theorem implies the existence of a non-Lebesgue measurable set"
  8. ↑ Page 9 of "General Topology"
  9. ↑ Edna Ernestine Kramer, "The Nature and Growth of Modern Mathematics", Princeton University Press, 1982. p. 595.
Retrieved from "https://conservapedia.com/index.php?title=Axiom_of_Choice&oldid=1451556"