Axiom of choice

From Free net encyclopedia

(Redirected from Axiom of Choice)
For other uses, see Axiom of choice (disambiguation).

In mathematics, the axiom of choice, or AC, is an axiom of set theory. It was formulated in 1904 by Ernst Zermelo.<ref name="Zermelo, 1904">Template:Cite journal</ref> While it was originally controversial, it is now used without reservation by most mathematicians. However, there are still schools of mathematical thought, primarily within set theory, that either reject the axiom of choice or investigate consequences of axioms inconsistent with AC.

Intuitively speaking, AC says that given a collection of bins, each containing at least one object, then exactly one object from each bin can be picked and gathered in another bin - even if there are infinitely many bins, and there is no "rule" for which object to pick from each.

Contents

[edit]

Statement

The axiom of choice states:

Let X be a set of non-empty sets. Then we can choose a member from each set in X.

Stated more formally:

Let X be a set of non-empty sets. Then there exists a choice function f defined on X. In other words, there exists a function f defined on X, such that for each set s in X, <math>f(s) \in s</math>.

Another formulation of the axiom of choice states:

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

Or alternatively:

An arbitrary Cartesian product of non-empty sets is non-empty.
[edit]

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.

[edit]

Independence of AC

By work of Kurt Gödel and Paul Cohen, the axiom of choice is logically independent of the other axioms of Zermelo-Fraenkel set theory (ZF). This means that neither it nor its negation can be proven to be true in ZF. Consequently, assuming the axiom of choice, or its negation, will never lead to a contradiction that could not be obtained without that assumption.

So the decision whether or not it is appropriate to make use of the axiom of choice in a proof cannot be made by appeal to other axioms of set theory. The decision must be made on other grounds.

One argument given in favor of using the axiom of choice is that it is convenient to use it: using it cannot hurt (cannot result in contradiction) and makes it possible to prove some propositions that otherwise could not be proved.

The axiom of choice is not the only significant statement which is independent of ZF. For example, the generalized continuum hypothesis (GCH) is not only independent of ZF, but also independent of ZF plus the axiom of choice (ZFC). However, ZF plus GCH implies AC, making GCH a strictly stronger claim than AC, even though they are both independent of ZF.

One reason that some mathematicians dislike the axiom of choice is that it implies the existence of some bizarre counter-intuitive objects. An example of this is the Banach–Tarski paradox which says in effect that it is possible to "carve up" the 3-dimensional solid unit ball into finitely many pieces and, using only rotation and translation, reassemble the pieces into two balls each with the same volume as the original. Note that the proof, like all proofs involving the axiom of choice, is an existence proof only: it does not tell us how to carve up the unit sphere to make this happen, it simply tells us that it can be done.

On the other hand, the negation of the axiom of choice is also bizarre. For example, the statement that for any two sets S and T, the cardinality of S is less than or equal to the cardinality of T or the cardinality of T is less than or equal to the cardinality of S is equivalent to the axiom of choice. Put differently, if the axiom of choice is false, then there are sets S and T of incomparable size: neither can be mapped in a one-to-one fashion onto a subset of the other.

A third possibility is to prove theorems using neither the axiom of choice nor its negation, a tactic preferred in constructive mathematics. Such statements will be true in any model of Zermelo–Fraenkel set theory, regardless of the truth or falsity of the axiom of choice in that particular model. This renders any claim that relies on either the axiom of choice or its negation undecidable. For example, under such an assumption, the Banach–Tarski paradox is neither true nor false: It is impossible to construct a decomposition of the unit ball which can be reassembled into two unit balls, and it is also impossible to prove that it can't be done. However, the Banach–Tarski paradox can be rephrased as a statement about models of ZF by saying, "In any model of ZF in which AC is true, the Banach–Tarski paradox is true." Similarly, all the statements listed below under Results requiring AC are undecidable in ZF, but since each is provable in any model of ZFC, there are models of ZF in which each statement is true.

[edit]

Weaker forms of AC and strengthened forms of ¬AC

There are several weaker statements which are not equivalent to the axiom of choice, but which are closely related. A simple one is the axiom of countable choice (ACω or CC), which states that a choice function exists for any countable set X. This usually suffices when trying to make statements about the real numbers, for example, because the rational numbers, which are countable, form a dense subset of the reals. See also the Boolean prime ideal theorem, the ultrafilter lemma, the axiom of dependent choice (DC), and the axiom of uniformization.

One also considers stronger forms of the negation of AC. For example, if we abbreviate by BP the claim that every set of real numbers has the property of Baire, then BP is stronger than ¬AC, which asserts the existence of possibly only one choice function on one set. Note that strengthed negations may be compatible with weakened forms of AC. For example, ZF + DC + BP is consistent if ZF is.

It is also consistent with ZF+DC that every set of reals is Lebesgue measurable; however, this consistency result, due to Robert M. Solovay, cannot be proved in ZFC itself, but requires a mild large cardinal assumption (the existence of an inaccessible cardinal). The much stronger axiom of determinacy, or AD, implies that every set of reals is Lebesgue measurable, has the property of Baire, and has the perfect set property (all three of these results are refuted by AC itself). ZF+DC+AD is consistent provided that a sufficiently strong large cardinal axiom is consistent (the existence of infinitely many Woodin cardinals).

[edit]

Results requiring AC (or weaker forms)

One of the most interesting aspects of the axiom of choice is the large number of places in mathematics that it shows up. There are also a remarkable number of important statements that, assuming the axioms of ZF but neither AC nor ¬AC, are equivalent to the axiom of choice. The most important among them are Zorn's lemma and the well-ordering theorem: every set can be well-ordered. In fact, Zermelo initially introduced the axiom of choice in order to formalize his proof of the well-ordering principle. Here are some statements that require the axiom of choice in the sense that they are not provable from ZF but are provable from ZFC (ZF plus AC). Equivalently, these statements are true in all models of ZFC but false in some models of ZF.

  • Set theory
    • Any union of countably many countable sets is itself countable.
    • If the set A is infinite, then there exists an injection from the natural numbers N to A (see Dedekind infinite).
    • If the set A is infinite, then A and A×A have the same cardinality. (This statement is equivalent to AC (over ZF))
    • Trichotomy: If two sets are given, then they either have the same cardinality, or one has a smaller cardinality than the other. (This statement is equivalent to AC (over ZF))
    • The product of any nonempty family of nonempty sets is nonempty. (This statement is equivalent to AC (over ZF))
    • Every infinite game <math>G(T,X)</math> where <math>X</math> is either open or closed is determined.
    • König's theorem: The sum of a sequence of cardinals is strictly less than the product of a sequence of larger cardinals. (This statement is equivalent to AC (over ZF))
[edit]

Results requiring ¬AC

There are models of Zermelo-Fraenkel set theory in which the axiom of choice is false. We will abbreviate "Zermelo-Fraenkel set theory plus the negation of the axiom of choice" by ZF¬C. For certain models of ZF¬C, it is possible to prove the negation of some standard facts. Note that any model of ZF¬C is also a model of ZF, so for each of the following statements, there exists a model of ZF in which that statement is true.

  • There exists a model of ZF¬C in which there is a function f from the real numbers to the real numbers such that f is not continuous at a, but for any sequence {xn} converging to a, limn f(xn)=f(a).
  • There exists a model of ZF¬C in which real numbers are a countable union of countable sets.
  • There exists a model of ZF¬C in which there is a field with no algebraic closure.
  • In all models of ZF¬C there is a vector space with no basis.
  • There exists a model of ZF¬C in which there is a vector space with two bases of different cardinalities.

For proofs, see Thomas Jech, The Axiom of Choice, American Elsevier Pub. Co., New York, 1973.

[edit]

Results requiring choice in intuitionistic logic, though not classically

Interestingly, in various varieties of constructive logic (in particular, intuitionistic logic) in which the law of excluded middle is not assumed, the assumption of the axiom of choice is sufficient to obtain the law of excluded middle as a theorem. To see this, for any proposition <math>P\,,</math> let <math>U\,</math> be the set <math>\{x \in \{0, 1\} : (x = 0) \vee P\}</math> and let <math>V\,</math> be the set <math>\{x \in \{0, 1\} : (x = 1) \vee P\}</math> (see Set-builder notation). By the axiom of choice, there will exist a choice function <math>f\,</math> for the set <math>\{U, V\}\,</math> (note that, although the axiom of choice isn't classically required in order to obtain choice functions for finite sets, it is necessary here in intuitionistic logic). Since <math>f(U) \in U</math> and <math>f(V) \in V</math>, this implies <math>[(f(U) = 0) \vee P] \wedge [(f(V) = 1) \vee P]</math>, which implies <math>f(U) \neq f(V) \vee P</math>. Since <math>P\,</math> implies <math>U = V = \{0, 1\}\,</math>, it must be that <math>P\,</math> implies <math>f(U) = f(V)\,</math>, so <math>f(U) \neq f(V) \vee P</math> would imply <math>\neg P \vee P</math>. As this could be done for any proposition <math>P\,</math>, this completes the proof that the axiom of choice implies the law of the excluded middle.

The above proof is not valid in all intuitionistic deductive systems. For example, in the intuitionistic type theory of Per Martin-Löf, the axiom of choice is a theorem, yet excluded middle is not.

[edit]

Quotes

The Axiom of Choice is obviously true, the well-ordering principle obviously false, and who can tell about Zorn's lemma?
— Jerry Bona
This is a joke that although the axiom of choice, the well-ordering principle, and Zorn's lemma are mathematically equivalent, most mathematicians find the axiom of choice to be intuitive, the well-ordering principle to be counterintuitive, and Zorn's lemma to be too complex for any intuition.
The Axiom of Choice is necessary to select a set from an infinite number of socks, but not an infinite number of shoes.
— Bertrand Russell
The observation here is that one can define a function to select from an infinite number of pairs of shoes by stating for example, to choose the left shoe. Without the axiom of choice, one cannot assert that such a function exists for pairs of socks, because left and right socks are (presumably) identical to each other.
The axiom gets its name not because mathematicians prefer it to other axioms.
— A. K. Dewdney
From the famous April Fool's Day article in the computer recreations column of the Scientific American, April 1989.
[edit]

External links

  • There are many people still doing work on the axiom of choice and its consequences. If you are interested in more, look up Paul Howard at EMU.
[edit]

References

<references/>

  • ------, 1908, "Untersuchungen über die Grundlagen der Mengenlehre I," Mathematische Annalen 65: 261-81.

Translations:

  • Jean van Heijenoort, 1967. From Frege to Godel: A Source Book in Mathematical Logic, 1879-1931. Harvard Univ. Press.
    • 1904. "Proof that every set can be well-ordered," 139-41.
    • 1908. "Investigations in the foundations of set theory I," 199-215.cs:Axiom výběru

da:Udvalgsaksiomet de:Auswahlaxiom fr:Axiome du choix ko:선택공리 it:Assioma della scelta he:אקסיומת הבחירה hu:Kiválasztási axióma nl:Keuzeaxioma ja:選択公理 pl:Aksjomat wyboru pt:axioma da escolha ru:Аксиома выбора sv:Urvalsaxiomet zh:选择公理

Retrieved from "http://www.netipedia.com/index.php/Axiom_of_choice"