*** Welcome to piglix ***

Transfinite recursion


Transfinite induction is an extension of mathematical induction to well-ordered sets, for example to sets of ordinal numbers or cardinal numbers.

Let P(α) be a property defined for all ordinals α. Suppose that whenever P(β) is true for all β < α, then P(α) is also true. Then transfinite induction tells us that P is true for all ordinals.

Usually the proof is broken down into three cases:

All three cases are identical except for the type of ordinal considered. They do not formally need to be considered separately, but in practice the proofs are typically so different as to require separate presentations. Zero is sometimes considered a limit ordinal and then may sometimes be treated in proofs in the same case as limit ordinals.

Transfinite recursion is similar to transfinite induction; however, instead of proving that something holds for all ordinal numbers, we construct a sequence of objects, one for each ordinal.

As an example, a basis for a (possibly infinite-dimensional) vector space can be created by choosing a vector and for each ordinal α choosing a vector that is not in the span of the vectors . This process stops when no vector can be chosen.


...
Wikipedia

...