Editing Mathematical induction (section)

== Transfinite induction ==
{{main|Transfinite induction}}
One variation of the principle of complete induction can be generalized for statements about elements of any [[well-founded set]], that is, a set with an [[reflexive relation|irreflexive relation]] < that contains no [[infinite descending chain]]s. Every set representing an [[ordinal number]] is well-founded, the set of natural numbers is one of them.

Applied to a well-founded set, transfinite induction can be formulated as a single step. To prove that a statement {{math|''P''(''n'')}} holds for each ordinal number:
# Show, for each ordinal number {{mvar|n}}, that if {{math|''P''(''m'')}} holds for all {{math|''m'' < ''n''}}, then {{math|''P''(''n'')}} also holds.

This form of induction, when applied to a set of ordinal numbers (which form a [[well-order]]ed and hence well-founded [[class (set theory)|class]]), is called ''[[transfinite induction]]''. It is an important proof technique in [[set theory]], [[topology]] and other fields.

Proofs by transfinite induction typically distinguish three cases:
# when {{mvar|n}} is a minimal element, i.e. there is no element smaller than {{mvar|n}};
# when {{mvar|n}} has a direct predecessor, i.e. the set of elements which are smaller than {{mvar|n}} has a largest element;
# when {{mvar|n}} has no direct predecessor, i.e. {{mvar|n}} is a so-called [[limit ordinal]].

Strictly speaking, it is not necessary in transfinite induction to prove a base case, because it is a [[vacuous truth|vacuous]] special case of the proposition that if {{math|''P''}} is true of all {{math|''n'' < ''m''}}, then {{math|''P''}} is true of {{mvar|m}}. It is vacuously true precisely because there are no values of {{math|''n'' < ''m''}} that could serve as counterexamples. So the special cases are special cases of the general case.