Transfinite induction

Transfinite induction is a proof technique in mathematics, which generalizes the well-known induction of the natural numbers in any well-ordered classes, for example, to sets of ordinals or cardinals, or even on the real class of all ordinals. Accordingly, the transfinite recursion is a definition principle, which generalizes the recursion in natural numbers. The first transfinite recursion introduced by Georg Cantor in 1897. Felix Hausdorff she rose to the general definition of principle and also led the transfinite induction as a proof principle.

Definition

As transfinite induction the following applies for a well-ordered class explained proof scheme:

The fact that this statement actually proven induction is sufficient to be seen as a: Be, that is the class of all elements of, is not the case for the. Assumed is not empty, then there would be because of the well-ordering a smallest element (which without loss of generality also the element that proves the statement for smaller elements ), and it would apply to each with also, by definition of words. But Then by the induction statement also proved. On the other hand, it follows, however, from now on. Because of this contradiction was the assumption is not empty, false, so that in fact for all elements of the case.

Application

If the class of ordinals is decomposed to the evidence often into three proof steps:

• Is true.
• Is an ordinal, it follows from well.
• If a limit number and applies for each ordinal, so also applies.

The first two steps are consistent with the mathematical induction for natural numbers. Because the set of natural numbers is the reaching to the first boundary section number of the class of ordinals.

Transfinite recursion

As transfinite recursion the following applies definition process in a well-ordered class:

This recursion will be formalized for ordinals.

Rekursionssatz: is the class of ordinals, the class of all sets and a term as recursion. Then there exists a transfinite sequence so that the statement is true for all ordinals.

Idea of ​​proof: It "united" all recursively defined ordinal sequences with the same recursion to transfinite sequence. The recursion for ordinal records the following as designated statement:

So these figures fulfill the same recursion, but are not defined in each case on the whole class of ordinals. From the uniqueness, there is, however, that these functions are continuations of each other and can be combined into a single transfinite sequence. The validity of all ordinals you show by transfinite induction, namely as above noted in three statements ( it is worth remembering that for ordinals is equivalent and that ):

Thus, the statement holds for all ordinals. One can now define, by setting for any. This is well-defined (ie independent of the choice of ) so that you simply can also choose.

Application

As with the transfinite induction one can work with three even with the transfinite recursion instead of a recursion: with an initial value function, a rule for successor figures (often in the simpler form ) and a rule for limiting numbers. The first two recursions coincide with the usual recursion for natural numbers.

Examples

• ,
• As well as
• If limit number.