Encyclopedia > Transfinite induction

  Article Content

Transfinite induction

Transfinite induction is the proof technique of mathematical induction when applied to (large) well-ordered sets, for instance to sets of ordinals or cardinals, or even to the class of all ordinals. It may be regarded as one of three forms of mathematical induction.

If you are trying to prove that a property P holds for all ordinals then you can apply transfinite induction:

  • Prove that P(0) holds true; and
  • For any ordinal b, if P(a) is true for all ordinals a < b then P(b) is true as well.

The latter step is often broken down into two cases: the case for non-limit ordinals (ordinals which have an immediate predecessor), where the usual inductive approach can be applied (show that P(b) implies P(b+1)), and the case for limit ordinals[?], which have no predecessor, and thus cannot be handled by such an argument.

Typically, the case for limit ordinals is approached by noting that a limit ordinal b is (by definition) the union of all ordinals a < b and using this fact to prove P(b) assuming that P(a) holds true for all a < b.

The first step above is actually redundant. If P(b) follows from the truth of P(a) for all a < b, then it is simply a special case to say that P(0) is true, since it is vacuously true that P(b) holds for all b < 0.

An example here would be nice

[I agree that some examples should be added, but it's been a long time since I've looked at this material.]

All Wikipedia text is available under the terms of the GNU Free Documentation License

  Search Encyclopedia

Search over one million articles, find something about almost anything!
  Featured Article

... ready in 1990 but the unveiling was delayed until the anniversary date of September 15, 1991. The car had a quad turbo V12 3500cc engine of 611bhp, powering all four ...

This page was created in 33 ms