Editing Set (mathematics) (section)

=== 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.