Namespaces
Variants
Actions

Difference between revisions of "Axiom of choice"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (link)
 
(7 intermediate revisions by 2 users not shown)
Line 1: Line 1:
One of the axioms in set theory. It states that for any family <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014270/a0142701.png" /> of non-empty sets there exists a function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014270/a0142702.png" /> such that, for any set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014270/a0142703.png" /> from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014270/a0142704.png" />, one has <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014270/a0142705.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014270/a0142706.png" /> is called a choice function on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014270/a0142707.png" />). For finite families <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014270/a0142708.png" /> the axiom of choice can be deduced from the other axioms of set theory (e.g. in the system ZF).
+
{{MSC|03E25|03E35}}
 +
{{TEX|done}}
  
The axiom of choice was explicitly formulated by E. Zermelo (1904) and was objected to by many mathematicians. This is explained, first, by its purely existential character which makes it different from the remaining axioms of set theory and, secondly, by some of its implications which are  "unacceptable"  or even contradict intuitive  "common sense" . Thus, the axiom of choice implies: the existence of a Lebesgue non-measurable set of real numbers; the existence of three subdivisions of the sphere <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014270/a0142709.png" />
 
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014270/a01427010.png" /></td> </tr></table>
+
One of the axioms in set theory. It states that for any family $F$ of
 +
non-empty sets there exists a function $f$ such that, for any set $S$
 +
from $F$, one has $f(S)\in S$ ($f$ is called a choice function on $F$). For
 +
finite families $F$ the axiom of choice can be deduced from the other
 +
axioms of set theory (e.g. in the system ZF).
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014270/a01427011.png" /></td> </tr></table>
+
The axiom of choice was explicitly formulated by E. Zermelo (1904) and
 +
was objected to by many mathematicians. This is explained, first, by
 +
its purely existential character which makes it different from the
 +
remaining axioms of set theory and, secondly, by some of its
 +
implications which are "unacceptable" or even contradict intuitive
 +
"common sense" . Thus, the axiom of choice implies  the existence of a
 +
Lebesgue non-measurable set of real numbers; the [[Banach–Tarski paradox]]: the existence of three
 +
subdivisions of the sphere $B$
 +
$$B=U_1\cup\dots\cup U_n,$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014270/a01427012.png" /></td> </tr></table>
+
$$B=V_1\cup\dots\cup V_m,$$
  
such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014270/a01427013.png" /> is congruent with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014270/a01427014.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014270/a01427015.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014270/a01427016.png" /> is congruent with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014270/a01427017.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014270/a01427018.png" />. Thus, the sphere <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014270/a01427019.png" /> is divisible into a finite number of parts <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014270/a01427020.png" /> which can be moved in space to form two spheres identical to it.
+
$$B=X_1\cup\dots\cup X_{n+m},$$
 +
such that $U_i$ is congruent with $X_i$, $1\le i \le n$, and $V_j$ is congruent
 +
with $X_{n+j}$, $1\le j\le m$. Thus, the sphere $B$ is divisible into a finite number
 +
of parts $X_1,\dots,X_{n+m}$ which can be moved in space to form two spheres identical
 +
to it.
  
Many postulates equivalent to the axiom of choice were subsequently discovered. Among these are: 1) The well-ordering theorem: On any set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014270/a01427021.png" /> there exists a total order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014270/a01427022.png" /> such that any non-empty set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014270/a01427023.png" /> contains a least element in the sense of the relation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014270/a01427024.png" />; 2) the maximality principle (Zorn's lemma): If any totally ordered subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014270/a01427025.png" /> of a partially ordered set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014270/a01427026.png" /> is bounded from above, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014270/a01427027.png" /> contains a maximal element; 3) any non-trivial lattice with a unit element has a maximal ideal; 4) the product of compact topological spaces is compact; and 5) any set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014270/a01427028.png" /> has the same cardinality as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014270/a01427029.png" />.
+
Many postulates equivalent to the axiom of choice were subsequently
 +
discovered. Among these are: 1) The well-ordering theorem: On any set
 +
$X$ there exists a total order $R\subseteq X\times X$ such that any non-empty set $U\subset X$
 +
contains a least element in the sense of the relation $R$; 2) the
 +
maximality principle ([[Zorn lemma|Zorn's lemma]]): If any totally ordered subset $U$
 +
of a partially ordered set $X$ is bounded from above, $X$ contains a
 +
maximal element; 3) any non-trivial lattice with a unit element has a
 +
maximal ideal; 4) [[Tikhonov theorem|Tikhonov's theorem]]: the product of compact topological spaces is
 +
compact; and 5) any infinite set $X$ has the same cardinality as $X\times X$.
  
The axiom of choice does not contradict the other axioms of set theory (e.g. the system ZF) and cannot be logically deduced from them if they are non-contradictory. The axiom of choice is extensively employed in classical mathematics. Thus, it is used in the following theorems. 1) Each subgroup of a free group is free; 2) the algebraic closure of an algebraic field exists and is unique up to an isomorphism; and 3) each vector space has a basis. It is also used in: 4) the equivalence of the two definitions of continuity of a function at a point (the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014270/a01427030.png" />-definition and the definition by limits of sequences) and in proving 5) the countable additivity of the Lebesgue measure. The last two theorems follow from the countable axiom of choice (the formulation of the axiom includes the condition of countability of the family <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014270/a01427031.png" />). It was proved that the theorems 1) to 5) are not deducible in the system ZF if ZF is non-contradictory.
+
The axiom of choice does not contradict the other axioms of set theory
 +
(e.g. the system ZF) and cannot be logically deduced from them if they
 +
are non-contradictory. The axiom of choice is extensively employed in
 +
classical mathematics. Thus, it is used in the following theorems. 1)
 +
Each subgroup of a free group is free; 2) the algebraic closure of an
 +
algebraic field exists and is unique up to an isomorphism; and 3) each
 +
vector space has a basis. It is also used in: 4) the equivalence of
 +
the two definitions of continuity of a function at a point (the
 +
$\epsilon - \delta$-definition and the definition by limits of sequences) and in
 +
proving 5) the countable additivity of the Lebesgue measure. The last
 +
two theorems follow from the countable axiom of choice (the
 +
formulation of the axiom includes the condition of countability of the
 +
family $F$). It was proved that the theorems 1) to 5) are not
 +
deducible in the system ZF if ZF is non-contradictory.
  
A model of set theory has been constructed which meets the countable axiom of choice and in which each set of numbers is Lebesgue-measurable. This model was constructed on the assumption that the system ZF does not contradict the axiom of the existence of an inaccessible cardinal number.
+
A model of set theory has been constructed which meets the countable
 +
axiom of choice and in which each set of numbers is
 +
Lebesgue-measurable. This model was constructed on the assumption that
 +
the system ZF does not contradict the axiom of the existence of an
 +
[[inaccessible cardinal]] number.
  
 
====References====
 
====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  A. Levy,  "Foundations of set theory" , North-Holland  (1973)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top"T.J. Jech,   "Lectures in set theory: with particular emphasis on the method of forcing" , ''Lect. notes in math.'' , '''217''' , Springer (1971)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top"T.J. Jech,   "The axiom of choice" , North-Holland (1973)</TD></TR></table>
+
{|
 
+
|-
 
+
|valign="top"|{{Ref|Je}}||valign="top"| T.J. Jech, "Lectures in set theory: with particular emphasis on the method of forcing", ''Lect. notes in math.'', '''217''', Springer (1971) {{MR|0321738}} {{ZBL|0236.02048}}
 
+
|-
====Comments====
+
|valign="top"|{{Ref|Je2}}||valign="top"| T.J. Jech, "The axiom of choice", North-Holland (1973) {{MR|0396271}} {{ZBL|0259.02051}}
 
+
|-
 
+
|valign="top"|{{Ref|Je3}}||valign="top"| T.J. Jech, "Set theory", Acad. Press (1978) (Translated from German) {{MR|0506523}} {{ZBL|0419.03028}}
====References====
+
|-
<table><TR><TD valign="top">[a1]</TD> <TD valign="top"T.J. Jech,   "Set theory" , Acad. Press (1978) (Translated from German)</TD></TR></table>
+
|valign="top"|{{Ref|FrBaLe}}||valign="top"| A.A. Fraenkel, Y. Bar-Hillel, A. Levy, "Foundations of set theory", North-Holland (1973) {{MR|0345816}} {{ZBL|0248.02071}}
 +
|-
 +
|}

Latest revision as of 18:30, 4 December 2017

2020 Mathematics Subject Classification: Primary: 03E25 Secondary: 03E35 [MSN][ZBL]


One of the axioms in set theory. It states that for any family $F$ of non-empty sets there exists a function $f$ such that, for any set $S$ from $F$, one has $f(S)\in S$ ($f$ is called a choice function on $F$). For finite families $F$ the axiom of choice can be deduced from the other axioms of set theory (e.g. in the system ZF).

The axiom of choice was explicitly formulated by E. Zermelo (1904) and was objected to by many mathematicians. This is explained, first, by its purely existential character which makes it different from the remaining axioms of set theory and, secondly, by some of its implications which are "unacceptable" or even contradict intuitive "common sense" . Thus, the axiom of choice implies the existence of a Lebesgue non-measurable set of real numbers; the Banach–Tarski paradox: the existence of three subdivisions of the sphere $B$ $$B=U_1\cup\dots\cup U_n,$$

$$B=V_1\cup\dots\cup V_m,$$

$$B=X_1\cup\dots\cup X_{n+m},$$ such that $U_i$ is congruent with $X_i$, $1\le i \le n$, and $V_j$ is congruent with $X_{n+j}$, $1\le j\le m$. Thus, the sphere $B$ is divisible into a finite number of parts $X_1,\dots,X_{n+m}$ which can be moved in space to form two spheres identical to it.

Many postulates equivalent to the axiom of choice were subsequently discovered. Among these are: 1) The well-ordering theorem: On any set $X$ there exists a total order $R\subseteq X\times X$ such that any non-empty set $U\subset X$ contains a least element in the sense of the relation $R$; 2) the maximality principle (Zorn's lemma): If any totally ordered subset $U$ of a partially ordered set $X$ is bounded from above, $X$ contains a maximal element; 3) any non-trivial lattice with a unit element has a maximal ideal; 4) Tikhonov's theorem: the product of compact topological spaces is compact; and 5) any infinite set $X$ has the same cardinality as $X\times X$.

The axiom of choice does not contradict the other axioms of set theory (e.g. the system ZF) and cannot be logically deduced from them if they are non-contradictory. The axiom of choice is extensively employed in classical mathematics. Thus, it is used in the following theorems. 1) Each subgroup of a free group is free; 2) the algebraic closure of an algebraic field exists and is unique up to an isomorphism; and 3) each vector space has a basis. It is also used in: 4) the equivalence of the two definitions of continuity of a function at a point (the $\epsilon - \delta$-definition and the definition by limits of sequences) and in proving 5) the countable additivity of the Lebesgue measure. The last two theorems follow from the countable axiom of choice (the formulation of the axiom includes the condition of countability of the family $F$). It was proved that the theorems 1) to 5) are not deducible in the system ZF if ZF is non-contradictory.

A model of set theory has been constructed which meets the countable axiom of choice and in which each set of numbers is Lebesgue-measurable. This model was constructed on the assumption that the system ZF does not contradict the axiom of the existence of an inaccessible cardinal number.

References

[Je] T.J. Jech, "Lectures in set theory: with particular emphasis on the method of forcing", Lect. notes in math., 217, Springer (1971) MR0321738 Zbl 0236.02048
[Je2] T.J. Jech, "The axiom of choice", North-Holland (1973) MR0396271 Zbl 0259.02051
[Je3] T.J. Jech, "Set theory", Acad. Press (1978) (Translated from German) MR0506523 Zbl 0419.03028
[FrBaLe] A.A. Fraenkel, Y. Bar-Hillel, A. Levy, "Foundations of set theory", North-Holland (1973) MR0345816 Zbl 0248.02071
How to Cite This Entry:
Axiom of choice. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Axiom_of_choice&oldid=19296
This article was adapted from an original article by V.N. Grishin (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article