Transfinite induction

Transfinite induction is a proof technique in mathematics that generalizes the induction known from natural numbers to any well-ordered classes, for example to sets of ordinals or cardinal numbers , or even to the real class of all ordinals. Accordingly, the transfinite recursion is a definition principle that generalizes the recursion for natural numbers. Georg Cantor carried out the first transfinite recursion in 1897. Felix Hausdorff raised it to the general principle of definition and also introduced transfinite induction as a principle of proof.

definition

The following proof scheme for a well-ordered class applies as transfinite induction : ${\displaystyle (A,<)}$

If one wants to prove that the statement holds for all , then it suffices to prove the following induction statement : ${\displaystyle a\in A}$ ${\displaystyle P(a)}$

When and for all with the statement is true, then applies . ${\displaystyle a\in A}$ ${\displaystyle b\in A}$ ${\displaystyle b<a}$ ${\displaystyle P(b)}$ ${\displaystyle P(a)}$

That this proven induction statement is actually sufficient can be seen as follows: Be , that is the class of all elements of for which does not apply. Suppose is not empty, then there would be because of the well-ordering a smallest element (which o. B. d. A. also the element that the statement of smaller elements proves), and it would apply to each with also , by definition of so . Then, according to the proven induction statement, it also holds . On the other hand, it also follows immediately . Because of this contradiction, the assumption that is not empty was wrong, so that in fact holds true for all elements of . ${\displaystyle B=\{x\in A|\neg P(x)\}}$ ${\displaystyle A}$ ${\displaystyle P}$ ${\displaystyle B}$ ${\displaystyle a\in B}$ ${\displaystyle b<a}$ ${\displaystyle b}$ ${\displaystyle b<a}$ ${\displaystyle b\notin B}$ ${\displaystyle B}$ ${\displaystyle P(b)}$ ${\displaystyle P(a)}$ ${\displaystyle a\in B}$ ${\displaystyle \neg P(a)}$ ${\displaystyle B}$ ${\displaystyle P}$ ${\displaystyle A}$

application

If the class is ordinal numbers, the proof is often broken down into the following three proof steps: ${\displaystyle A}$

• ${\displaystyle P(0)}$ is true.
• Is an ordinal, it follows from well . ${\displaystyle a}$ ${\displaystyle P(a)}$ ${\displaystyle P(a+1)}$
• If is a limit number and applies to every ordinal number , then also applies . ${\displaystyle a}$ ${\displaystyle P(b)}$ ${\displaystyle b<a}$ ${\displaystyle P(a)}$

The first two steps coincide with the complete induction for natural numbers, because the set of natural numbers is the section of the class of ordinal numbers that extends to the first limit number.

Transfinite recursion

The following definition procedure applies as transfinite recursion in a well-ordered class : ${\displaystyle (A,<)}$

If it can only be defined by the values at points , this is already completely defined. ${\displaystyle f(a)}$ ${\displaystyle f(b)}$ ${\displaystyle b<a}$ ${\displaystyle f}$ ${\displaystyle A}$

This recursion principle is now formalized for ordinal numbers.

Recursion theorem: let the class of ordinal numbers, the class of all sets and a term as recursion rule . Then there is exactly one transfinite sequence , so that the statement applies to all ordinal numbers . ${\displaystyle \mathrm {On} }$ ${\displaystyle V}$ ${\displaystyle R(x)}$ ${\displaystyle F\colon \mathrm {On} \to V}$ ${\displaystyle a}$ ${\displaystyle F(a)=R(F|_{a})}$

Proof idea: One “combines” all recursively defined ordinal sequences with the same recursion rule to form a transfinite sequence. The recursion for an ordinal number captures the following statement: ${\displaystyle b}$ ${\displaystyle P(b)}$

There is exactly one figure , so the statement applies to all of them . ${\displaystyle F_{b}\colon b\to V}$ ${\displaystyle a<b}$ ${\displaystyle F_{b}(a)=R(F_{b}|_{a})}$

These mappings therefore fulfill the same recursion rule, but are not defined for the entire class of ordinal numbers. From the uniqueness, however, it follows that these functions are continuations of one another and can be combined into a single transfinite sequence. The validity of for all ordinal numbers is shown by transfinite induction, as noted above in three sub-statements (it should be remembered that for ordinal numbers is synonymous with and that ): ${\displaystyle F_{b}}$ ${\displaystyle P(b)}$ ${\displaystyle b}$ ${\displaystyle a<b}$ ${\displaystyle a\in b}$ ${\displaystyle b+1=b\cup \{b\}}$

1. The statement is immediate because there are no ordinal numbers at all and the recursion rule applies trivially and because there is only one mapping anyway . ${\displaystyle P(0)}$ ${\displaystyle a<0}$ ${\displaystyle 0\to V}$
2. If so , then it also applies : The existence of results from by putting if , as well as (necessarily) . If a function is according to the same conditions, then it follows first from the uniqueness statement in and then from the recursion rule as well , i.e. in total . ${\displaystyle P(b)}$ ${\displaystyle P(b+1)}$ ${\displaystyle F_{b+1}\colon b+1\to V}$ ${\displaystyle F_{b}\colon b\to V}$ ${\displaystyle F_{b+1}(a)=F_{b}(a)}$ ${\displaystyle a<b}$ ${\displaystyle F_{b+1}(b)=R(F_{b})}$ ${\displaystyle G_{b+1}\colon b+1\to V}$ ${\displaystyle G_{b+1}|_{b}=F_{b+1}|_{b}}$ ${\displaystyle P(b)}$ ${\displaystyle G_{b+1}(b)=R(F_{b})=F_{b+1}(b)}$ ${\displaystyle G_{b+1}=F_{b+1}}$
3. Is bound number and valid for all , then applies : If so, there are with . You bet . This is well-defined, since it certainly applies to with because of the predictable statements . This also results in the uniqueness. ${\displaystyle b}$ ${\displaystyle P(a)}$ ${\displaystyle a<b}$ ${\displaystyle P(b)}$ ${\displaystyle a<b}$ ${\displaystyle c}$ ${\displaystyle a<c<b}$ ${\displaystyle F_{b}(a)=F_{c}(a)}$ ${\displaystyle c'}$ ${\displaystyle a<c'<b}$ ${\displaystyle P(a),P(c),P(c')}$ ${\displaystyle F_{c'}(a)=R(F_{c'}|_{a})=R(F_{a})=R(F_{c}|_{a})=F_{c}(a)}$

Thus the statement applies to all ordinal numbers . You can now define by betting for anything. This is well-defined (i.e. independent of the choice of ), so that one can simply choose. ${\displaystyle P(b)}$ ${\displaystyle b}$ ${\displaystyle F\colon \mathrm {On} \to V}$ ${\displaystyle F(b)=F_{c}(b)}$ ${\displaystyle c>b}$ ${\displaystyle c}$ ${\displaystyle c=b+1}$

application

As with transfinite induction, with transfinite recursion you can work with three instead of one recursion rule : with an initial function value , a rule for successor numbers (often in the simpler form ) and a rule for limit numbers. The first two recursion steps coincide with the usual recursion for natural numbers. ${\displaystyle F(0)=R_{1}}$ ${\displaystyle F(b+1)=R_{2}(F|_{b+1})}$ ${\displaystyle F(b+1)=R_{2}(F(b))}$ ${\displaystyle F(b)=R_{3}(F|_{b})}$

Examples

1. Let a fixed ordinal number and the recursion rule be chosen as follows: If the graph is a function, let the smallest ordinal number not appear in (and otherwise arbitrary). The function defined recursively (depending on ) always delivers an ordinal number (follows by transfinite induction) and it applies , etc. One writes for and thus defines the addition of ordinal numbers. ${\displaystyle c}$ ${\displaystyle G}$ ${\displaystyle f}$ ${\displaystyle R(f)}$ ${\displaystyle c\cup \operatorname {Bild} (f)}$ ${\displaystyle c}$ ${\displaystyle F}$ ${\displaystyle F(0)=c}$ ${\displaystyle F(1)=c+1}$ ${\displaystyle c+a}$ ${\displaystyle F(a)}$
2. The addition can also - more easily understood - be defined by three recursion steps:
   • ${\displaystyle c+0:=c}$,
   • ${\displaystyle c+(b+1):=(c+b)+1}$ such as
   • ${\displaystyle c+b:=\sup\{c+a|a<b\}}$if is limit number. ${\displaystyle b}$
3. With transfinite recursion it can be shown: Every well-ordered set is order isomorphic to an ordinal number. Proof idea: One tries to define by means of the recursion rule . This would be automatically injective, but this cannot be because there is no real class. For the smallest ordinal number at which the recursion fails, an order isomorphism results with . ${\displaystyle (A,<)}$ ${\displaystyle F\colon \mathrm {On} \to A}$ ${\displaystyle R(f)=\min(A\setminus \operatorname {Bild} f)}$ ${\displaystyle F}$ ${\displaystyle A}$ ${\displaystyle (A,<)}$
4. Transfinite recursion also defines the cumulative hierarchy of sets.

Individual evidence

1. ↑ transfinite recursion for the definition of the power of ordinals, in: Cantor: Contributions to the foundation of transfinite set theory 2. , in: Mathematische Annalen 49 (1897), §18, 231f.
2. ↑ Felix Hausdorff , Egbert Brieskorn : Basics of set theory . 1st edition. Springer, Berlin, 2002, ISBN 3-540-42224-2 , pp. 112 f . ( limited preview in Google Book search).