Editing Set (mathematics) (section)

==Axiom of choice==
{{main|Axiom of choice}}

Informally, the axiom of choice says that, given any family of nonempty sets, one can choose simultaneously an element in each of them.{{efn|Gödel{{sfn|Gödel|1938}} and Cohen{{sfn|Cohen|1963b}} showed that the axiom of choice cannot be proved or disproved from the remaining set theory axioms, respectively.}} Formulated this way, acceptability of this axiom sets a foundational logical question, because of the difficulty of conceiving an infinite instantaneous action. However, there are several equivalent formulations that are much less controversial and have strong consequences in many areas of mathematics. In the present days, the axiom of choice is thus commonly accepted in mainstream mathematics.

A more formal statement of the axiom of choice is: ''the Cartesian product of every indexed family of nonempty sets is non empty''.

Other equivalent forms are described in the following subsections.

=== Zorn's lemma ===
{{main|Zorn's lemma}}

Zorn's lemma is an assertion that is equivalent to the axiom of choice under the other axioms of set theory, and is easier to use in usual mathematics. 

Let {{tmath|S}} be a partial ordered set. A [[chain (order theory)|chain]] in {{tmath|S}} is a subset that is [[total order|totally ordered]] under the induced order. Zorn's lemma states that, if every chain in {{tmath|S}} has an [[upper bound]] in {{tmath|S}}, then {{tmath|S}} has (at least) a [[maximal element]], that is, an element that is not smaller than another element of {{tmath|S}}.

In most uses of Zorn's lemma, {{tmath|S}} is a set of sets, the order is set inclusion, and the upperbound of a chain is taken as the union of its members.

An example of use of Zorn's lemma, is the proof that every [[vector space]] has a [[Hamel basis|basis]]. Here the elements of {{tmath|S}} are [[linearly independent]] subsets of the vector space. The union of a chain of elements of {{tmath|S}} is linearly independent, since an infinite set is linearly independent if and only if each finite subset is, and every finite subset of the union of a chain must be included in a member of the chain. So, there exist a maximal linearly independent set. This linearly independant set must span the vector space because of maximality, and is therefore a basis.

Another classical use of Zorn's lemma is the proof that every proper [[ideal (ring theory)|ideal]]{{mdash}}that is, an ideal that is not the whole ring{{mdash}}of a [[ring (mathematics)|ring]] is contained in a [[maximal ideal]]. Here, {{tmath|S}} is the set of the proper ideals containing the given ideal. The union of chain of ideals is an ideal, since the axioms of an ideal involve a finite number of elements. The union of a chain of proper ideals is a proper ideal, since otherwise {{tmath|1}} would belong to the union, and this implies that it would belong to a member of the chain.

=== Transfinite induction  ===
{{main|Well-order|Transfinite induction}}

The axiom of choice is equivalent with the fact that a well-order can be defined on every set, where a well-order is a [[total order]] such that every nonempty subset has a least element.

Simple examples of well-ordered sets are the natural numbers (with the natural order), and, for every {{mvar|n}}, the set of the {{mvar|n}}-[[tuples]] of natural numbers, with the [[lexicographic order]].

Well-orders allow a generalization of [[mathematical induction]], which is called ''transfinite induction''. Given a property ([[predicate (mathematical logic)|predicate]]) {{tmath|P(n)}} depending on a natural number, mathematical induction is the fact that for proving that {{tmath|P(n)}} is always true, it suffice to prove that for every {{tmath|n}},
:<math>(m<n \implies P(m)) \implies P(n).</math>
Transfinite induction is the same, replacing natural numbers by the elements of a well-ordered set.

Often, a proof by transfinite induction easier if three cases are proved separately, the two first cases being the same as for usual induction:
*<math>P(0)</math> is true, where {{tmath|0}} denotes the least element of the well-ordered set
*<math>P(x) \implies P(S(x)),\quad</math> where {{tmath|S(x)}} denotes the ''successor'' of {{tmath|x}}, that is the least element that is greater than {{tmath|x}}
*<math>(\forall y;\; y<x \implies P(y)) \implies P(x) ,\quad</math> when {{tmath|x}} is not a successor.

Transfinite induction is fundamental for defining [[ordinal number]]s and [[cardinal number]]s.