Von der Rekursion zur Induktion

Autoren: Michèle Artigue und Ferdinando Arzarello.

Übersetzt von Eva Klein und Hans-Georg Weigand (Universität Würzburg)

Hat man ein quadratisches Gitterraster gegeben, so ist es leicht dort Quadrate einzuzeichnen, deren Ecken jeweils auf Schnittpunkten der Rasterlinien liegen. Aber ist dies auch für andere regelmäßige Polygone, z.B. ein Oktagon, möglich? Die Antwort lautet „Nein“ und kann für das Achteck wie folgt bewiesen werden (Payan, 1994):

Lassen wir das Gitterraster zunächst einmal außer Acht. Jedem regelmäßigen Achteck (also einem Achteck mit gleich langen Seiten und gleich großen Winkeln) ordnen wir wie in Abbildung 2 dargestellt ein anderes Achteck zu. Den Punkt $A'$ erhält man als Bildpunkt des Punktes $A$ durch eine 90°- Drehung gegen den Uhrzeigersinn mit Zentrum $B$ , $B'$ als Bildpunkt von durch eine 90°- Drehung gegen den Uhrzeigersinn mit Zentrum $C$ , usw. Auf diese Weise erhalten wir ein weiteres regelmäßiges Achteck, welches ähnlich zum Ausgangsachteck ist und dessen Zentrum ebenfalls $O$ ist. Seine Fläche ist jedoch echt kleiner als die des ersten Achtecks.

Kommen wir nun zu den regelmäßigen Polygonen zurück, deren Eckpunkte Rasterschnittpunkte sind. Jedem solchen Polygon weisen wir die Anzahl $S(P)$ der Schnittpunkte der Gitternetzlinien zu, die komplett innerhalb des Polygons liegen (d.h. solche, die innerhalb des Polygons liegen und nicht auf einer Seitenlinie). Ist z.B. $P$ das Pentagon aus Abbildung 3, dann gilt $S(P)= 26$ ( Zur Erinnerung: Diese Zahl steht durch den Satz von Pick in engem Zusammenhang mit der Fläche des Pentagons).

Abb.2: Konstruktion des zweiten Polygons

Abb. 3: Berechnung von S(P)

Angenommen, man könnte ein regelmäßiges Achteck konstruieren, dessen Eckpunkte Schnittpunkte von Gitternetzlinien sind. Durch den zuvor beschriebenen Prozess könnten wir aus diesem wiederum ein weiteres regelmäßiges Achteck konstruieren, dessen Eckpunkte ebenfalls Schnittpunkte der Gitterlinien sind, da diese Eigenschaft bei 90°- Drehungen erhalten bleibt, wenn das Drehzentrum ein Gitternetzpunkt ist. Außerdem wäre die natürliche Zahl $S(P_2)$ stets echt kleiner als $S(P_1)$ . Wiederholt man diesen Prozess, so endet er notwendigerweise in einem Widerspruch.

Wir haben also die Unmöglichkeit der Existenz eines solchen Achtecks unter Verwendung einer seit Fermats Zeitalter bekannten arithmetischen Methode bewiesen: Einen Beweis durch unendlichen Abstieg. Diese Methode beruht auf der Unmöglichkeit eine streng fallende unendliche Folge natürlicher Zahlen zu bilden und bezieht sich dabei auf eine besondere Eigenschaft der Ordnung innerhalb der Menge der natürlicher Zahlen: die Eigenschaft der Wohlordnung. Diese besagt, dass jede nichtleere Teilmenge ein kleinstes Element besitzt. Nehmen wir einmal an, man könne tatsächlich eine unendliche fallende Folge $(u_n)$ positiver natürlicher Zahlen bilden. Sei $S$ dann die Menge aller Terme der gegebenen Folge: $S=\{ u_0, u_1, ... , u_n ... \}$ .

Dann hat $S$ ein kleinstes Element $\alpha$ . Dies ist ein Element der Folge, also existiert ein $k$ , so dass $\alpha =u_k$ gilt. Aber dann ist $u_{k+1} < u_k$ und $u_{k+1}$ liegt in $S$ , ein Widerspruch zur Definition von $\alpha$ .

Mathematische Induktion und die Wohlordnung von natürlichen Zahlen

Mathematische Induktion, wie sie normalerweise in der Oberstufe eingeführt wird, ist in der Tat eine Konsequenz der Wohlordnung der natürlichen Zahlen. Sie ist das dritte von Peanos Axiomen der Arithmetik (1908) und wird wie folgt formuliert:

„Wenn $S$ eine Menge ist die $0$ enthält und wenn für jedes Element $a$ in $S$ der Nachfolger von $a$ ebenfalls in $S$ enthalten ist, dann enthält $S$ jede natürliche Zahl .“

Wir umschreiben dies normalerweise wie folgt: Wenn eine Eigenschaft $P$ von natürlichen Zahlen sowohl von $0$ als auch jedem Nachfolger $n+1$ einer jeden natürlichen Zahl angenommen wird, die diese Eigenschaft besitzt, so wird $P$ von allen natürlichen Zahlen angenommen.

Nimmt man an, dass die Ordnung natürlicher Zahlen eine wohlgeordnete Relation ist, dann ist die mathematische Induktion eine direkte Konsequenz daraus. Denn angenommen, die Eigenschaft $P$ würde nicht von allen natürlichen Zahlen angenommen, und $S$ sei die Menge der natürlichen Zahlen, die diese Eigenschaft nicht annehmen. Dann ist $S$ nicht leer, da sie ein kleinstes Element $n_0$ enthält und $n_0$ ist ungleich $0$ , da $0$ die Eigenschaft $P$ besitzt. Damit hat $n_0$ einen Vorgänger $n_0 -1$ , der nicht in $S$ enthalten ist. Aber dann nimmt $n_0 -1$ und damit auch $n_0$ $P$ an, im Widerspruch zur Definition von $n_0$ .

Mathematische Induktion kann auch zur Definition von Funktionen genutzt werden. Man nutzt dies zum Beispiel, wenn man eine Folge durch Induktion definiert, indem man eine Relation $u_{n+1}=f(u_n)$ aufstellt, wobei $f$ eine auf $\mathbb{N}$ definierte Funktion ist und als ersten Term $u_0$ hat. Man nennt dies auch eine Definition durch Induktion.

Rekursion und Induktion: Erste Verallgemeinerung

Allgemeiner gesehen kann man bei jeder wohlgeordneten Menge eine induktive Denkweise verwenden. Betrachtet man zum Beispiel die Menge $\{0,1\} \times \mathbb{N}$ mit lexikographischer Ordnung $(a,b) \leqslant (c,d)$ , falls $a < c$ oder $a=c$ und $b \leqslant d$ gilt. Diese Ordnung ist eine wohlgeordnete Relation. Sei $S$ eine nichtleere Teilmenge von $\{0,1\} \times \mathbb{N}$ , so erhalten wir zwei Fälle:

Fall 1: Alle Elemente von $S$ haben die Form $(1,b)$ . Dann ist $\{ b \mid (1,b) \in S \}$ eine nichtleere Teilmenge von $\mathbb{N}$ und besitzt ein kleinstes Element $b_0$ . $(1,b_0)$ ist damit das kleinste Element von $S$ .
Fall 2: Es gibt ein Element von $S$ von der Form $(0,b)$ . Um zu zeigen, dass $S$ ein kleinstes Element besitzt, muss man beweisen dass $\{ b \mid (0,b) \in S \}$ ein kleinstes Element besitzt, was jedoch offensichtlich der Fall ist.

In ähnlicher Weise lässt sich zeigen, dass die lexikographische Ordnung von $\mathbb{N}^p$ eine Wohlordnung ist. Die Anwendung des vorherigen Beweises wird in diesem Fall der Leserin oder dem Leser überlassen. Demzufolge kann es keine unendliche strengmonotonfallende Folge in diesen Mengen geben, selbst wenn für jedes Element der Form $(a_1, a_2, ... , a_p)$ mit $a_1 \neq 0$ unendlich viele kleinere Elemente der Form $(b_1, b_2, ..., b_p)$ mit $b_1 < a_1$ existieren.

Das Prinzip des unendlichen Abstiegs aus dem ersten Beispiel kann auch in $\mathbb{N}^p$ angewendet werden. Außerdem kann man in $\mathbb{N}^p$ ebenfalls Funktionen durch Induktion definieren. Dies ist zum Beispiel der Fall für die von Ackermann 1932 definierte Funktion von $\mathbb{N}^2$ nach $\mathbb{N}$ , die später noch näher erläutert wird.

Induktion und Ordinalzahlen

In der Mengentheorie drückt sich das für mathematische Beweise essentielle Konzept der Wohlordnung im Konzept der Ordinalzahlen aus und beschreibt nicht nur die bereits oben dargestellten Wohlordnungsrelationen. Ordinalzahlen, und damit auch natürliche Zahlen als endliche Ordinalzahlen, sind als wohlgeordnete Mengen durch Zugehörigkeit und Transitivität definiert (eine Menge $X$ ist transitiv, wenn alle Elemente $z$ eines Elements $y$ von $X$ auch ein Element der Menge $X$ sind). In diesem Artikel wird jedoch nur ein intuitiver Zugang zu transfiniten Ordinalzahlen betrachtet, die Ende des 19. Jahrhunderts von Cantor eingeführt wurden. Die kleinste unendliche Ordinalzahl wird als $\omega$ bezeichnet und ist die Vereinigung aller endlichen Ordinalzahlen. Sie repräsentiert die Ordnung auf den natürlichen Zahlen. Sie besitzt einen Nachfolger $\omega +1$ , der wiederum einen Nachfolger $\omega +2$ besitzt, usw. Die kleinste Ordinalzahl, die größer als jedes $\omega +n$ ist, ist $\omega +\omega$ oder $\omega . 2$ . Die kleinste Ordinalzahl, die größer ist als jedes $\omega . n$ , ist $\omega^2$ usw.

$0, 1, 2... n... \omega, \omega+1, \omega+2… \omega+n... \omega.2, \omega.2+1, \omega.2+2... \omega.2+n... \omega.3... \omega.n ... \omega^2 ... \omega^3... \omega^\omega ...$

Es gibt in der Tat zwei verschiedene Arten von Ordinalzahlen: Diejenigen, die Nachfolger einer gegebenen Ordinalzahl sind, wie z.B. $\omega +n$ , $\omega ^\omega +n$ , für $n \neq 0$ , und diejenigen, die keinen Vorgänger besitzen, sondern Vereinigungen aller kleineren Ordinalzahlen sind, wie z.B. $\omega$ , $\omega ^n$ , $\omega^\omega, ...$ in der vorherigen Liste. Man stellt fest, dass die lexikographische Ordnung von $\{0,1\} \times \mathbb{N}$ dieser Menge eine Ordnung zuweist, die der Ordnung der Ordinalzahl $\omega+\omega$ entspricht. Die Verallgemeinerung der lexikographischen Ordnung von $\mathbb{N} \times \mathbb{N}$ entspricht der von $\omega^2$ , … Aber es gibt viele andere Ordinalzahlen außer den hier benannten, und jede davon ist abzählbar. Durch die Mengentheorie kann unter Verwendung des Auswahlaxioms bewiesen werden, dass jede Menge wohlgeordnet sein kann.

Durch die Induktion nach Ordinalzahlen kann man Funktionen definieren. Um eine Funktion durch Induktion nach einer Ordinalzahl $\alpha$ zu definieren, muss man ihren Wert an der Stelle $0$ angeben und weiterhin wie man den Wert von $f(\alpha)$ aus den Funktionswerten vorheriger Ordinalzahlen erhält. Man beachte, dass es hilfreich ist, zwei Fälle für die Definition von $f(\alpha)$ zu betrachten: $\alpha$ als Grenzwert oder als Nachfolger. Über den Ordinalzahlen kann man das Prinzip des unendlichen Abstiegs anwenden – die Goodstein Vignette liefert ein gutes Beispiel für einen solchen Beweis.

Über die Ackermannfunktion und das Diagonalargument

Ein Beispiel für eine Funktion, die durch Induktion definiert wird, ist die schon zuvor erwähnte Ackermannfunktion. Diese wird mit $A$ bezeichnet und ist wie folgt definiert:

Für jede positive natürliche Zahl $y$ , $A(0,y) = y+1$
Für jede positive natürliche Zahl $x$ , $A(x+1,0) = A(x,1)$
Für jedes Paar positiver natürlicher Zahlen $(x,y)$ , $A(x+1,y+1) = A(x, A(x+1,y))$ .

Ihr Wert an der Stelle $(x,y)$ ist dann genau gegeben, wenn $x$ gleich $0$ ist. Wenn $x \neq 0$ gilt, so verwendet man für die Berechnung von $A(x,y)$ die Werte der Funktion an gewissen Punkten $(c,d)$ , sodass $(c,d) < (x,y)$ für die lexikographische Ordnung gilt. Diese Berechnung benötigt eine strengmonotonfallende Folge solcher Punkte, die zwangsläufig endlich ist, da die lexikologische Ordnung eine wohlgeordnete Relation ist. Diese Folge kann jedoch sehr lang sein. Wie viele Terme sind notwendig um $A(3,2)$ zu bestimmen?

Wir beginnen mit dem einfacheren Beispiel: $A(2,2), und verwenden die folgende Tabelle. <img src="https://blog.kleinproject.org/wp-content/ql-cache/quicklatex.com-35c1a59096fad23f50cff9d2974fc662_l3.png" height="159" width="212" class="ql-manual-mode " alt="Rendered by QuickLaTeX.com" title="Rendered by QuickLaTeX.com"/> Mit Hilfe der ersten Bedingung können wir die erste Spalte füllen. Daraufhin erhält man sukzessive:$ A(1,0) = A(0,1) = 2 $;$ A(1,1) = A(0,A(1,0)) = A(0, 2) = 3 $;$ A(1,2) = A(0,A(1,1))= A(0,3) = 4

$und allgemein erhält man: <span class="ql-right-eqno"> </span><span class="ql-left-eqno"> </span><img src="https://blog.kleinproject.org/wp-content/ql-cache/quicklatex.com-13c820bdd14a5098eca9ee79bd5b6595_l3.png" height="18" width="385" class="ql-img-displayed-equation " alt="\[A(1,n+1)=A(0, A(1,n))=A(0,n+1)=n+2.\]" title="Rendered by QuickLaTeX.com"/> Wir ergänzen anschließend:$

A(2,0) = A(1,1) = 3 $;$ A(2,1) = A(1,A(2,0)) = A(1,3) = 5 $und schließlich$ A(2,2) = A(1, A(2,1)) = A(1,5) = 7 $. Um$ A(2,2) $zu bestimmen, muss man alle Werte der Funktion für die Paare der ersten Zeile bis hin zu$ (0,6) $berechnen, die der zweiten Zeile bis zu$ (1,5) $, und die der dritten Zeile bis zu$ (2,2) $, d.h. man muss insgesamt 15 Werte verwenden. Wie bestimmt man$ A(3,2) $und welchen Wert für$ A(3,2) $erhält man letztendlich? Diese Berechnung wird der Leserin oder dem Leser überlassen. Wenn man eine der zwei Variablen der Ackermannfunktion fest wählt, erhält man was im Allgemeinen als arithmetische Funktion bekannt ist. Wir benennen mit$ A_n $jene Funktion, die man erhält, indem man$ n $als erste Variable festlegt. Wir haben bereits gesehen, dass$ A_0(y)=A(0,y)=y+1 $und damit$ A_0 $die Nachfolgerfunktion ist und es gilt$ A_1(y) = y + 2 $. Man kann zeigen, dass$ A_2(y) = 2y+3 $und$ A_3(y)=2^{y+3}-3 $gilt. Danach werden die Ausdrücke durch Iteration der Exponenten schnell sehr kompliziert und die Werte von$ A(x,y) $werden in wenigen Schritten ziemlich groß.$ A(5,0)=65533 $, zum Beispiel, und$ A(4,2) $ist bereits eine Zahl mit 19729 Stellen. In der Tat kann man zeigen, dass für die Funktion$ g $, definiert durch$ g(x)=A(x,x) $, für alle primitiv-rekursiven Funktionen, also jede Funktion die durch Komposition und Induktion mit Hilfe ihrer Nachfolgerfunktion und Projektionsfunktionen von$ \mathbb{N}^p $zu$ \mathbb{N} $definiert werden kann, eine positive natürliche Zahl$ N $existiert, sodass$ g(x) > f(x) $für jedes$ x $größer als$ N $gilt. So kann man beweisen, dass es berechenbare Funktionen gibt, die nicht primitiv-rekursiv sind. Die Ackermannfunktion ist ein Beispiel für eine solche Funktion. Gewöhnliche Funktionen auf den ganzen Zahlen, wie z.B. solche Funktionen, die man am Gymnasium verwendet, sind jedoch allesamt primitiv-rekursiv. Die Funktionen, welche zwei natürlichen Zahlen ihre Summe oder ihr Produkt zuweisen, sind primitiv-rekursiv. Tatsächlich kann man diese durch Induktion wie folgt definieren: Für alle$ x, x+0 = x $, und$ x.0=0 $und für alle$ y, x+(y+1) = (x+y)+1 $und$ x(y+1) = xy+x $. Die Folgerung, dass die Funktion, die jedem Paar von natürlichen Zahlen$ (x,y) $den Wert$ x^y $zuweist und auch jede Iteration dieser Funktion ebenfalls primitiv-rekursiv ist, wird der Leserin oder dem Leser überlassen. Allgemein betrachtet, ist jede Funktion primitiv-rekursiv, die durch primitiv-rekursive Funktionen mit Hilfe eines Algorithmus definiert werden kann, der Schleifen der Form „für$ k $von$ 1 $bis$ n $`` verwendet. Für den Beweis benötigt man das Diagonalargument. Dieses Argument wurde 1874 von Georg Cantor eingeführt um zu beweisen, dass die Menge der reellen Zahlen nicht abzählbar ist, d.h. dass keine Bijektion zwischen$ \mathbb{R} $und$ \mathbb{N} $existiert. 1891 hat er diese Methode abermals angewendet, um zu beweisen, dass die Potenzmenge einer beliebigen Menge$ X $(d.h. die Menge aller Teilmengen von$ X $) eine Kardinalzahl besitzt, die echt kleiner ist als die Kardinalzahl von$ X $. Die Einführung des Diagonalarguments war ein wichtiger Schritt in der Entwicklung der Mathematik. Insbesondere ist es der Anfangspunkt der Beweise vieler Resultate, einschließlich des Gödelschen Unvollständigkeitssatzes, und von vielen Sätzen der Berechenbarkeitstheorie. Russells Paradoxon basiert ebenfalls auf dieser Idee. Schon im Gymnasium kann man den Schülerinnen und Schülern einen kleinen Vorgeschmack auf diese Denkweise geben, indem man beweist, dass das Intervall$ [0,1) $nicht abzählbar ist. Hierfür verwendet man, dass jede natürliche Zahl eine eindeutige Dezimaldarstellung besitzt (wobei man hier nur normalisierte Repräsentationen betrachtet, also keine uneigentlichen Dezimaldarstellungen, die in unendlich vielen Neunen enden). Nehmen wir an, es gäbe eine Bijektion zwischen dem Intervall$ [0,1) $und$ \mathbb{N} $, und betrachten deshalb eine Folge$ (\alpha_n) $dieser reellen Zahlen. Die genaue Dezimaldarstellung der reellen Zahl$ \alpha_n $hat die Form$ 0 $,$ a_1^n a_2^n … $, und kann in unendlich vielen Nullen enden. Betrachten wir die reelle Zahl$ \alpha $, deren Dezimaldarstellung$ 0,b_1^n b_2^n … $ist, mit$ b_k=a_k ^k -1 $falls$ a_k ^k \neq 0 $und$ b_k=a_k ^k +1 $falls$ a_k ^k = 0 $, so ist es klar, dass$ 0,b_1 ^n b_2 ^n … $die Dezimaldarstellung einer reellen Zahl$ \beta $im Intervall$ [0,1) $sein muss und dass$ \beta $ungleich zu jedem Element der Folge$ (a_n) $ist. Folglich ist das Intervall$ [0,1)$ nicht abzählbar und die Menge der reellen Zahlen auch nicht.

Fazit

Das Prinzip der mathematischen Induktion ist nun schon seit dem Altertum in Gebrauch. Beispielsweise wird es in Euklids Elementen verwendet, um zu zeigen, dass es unendlich viele Primzahlen gibt. Auch das Prinzip des unendlichen Abstiegs wird seit Hunderten von Jahren genutzt und wird oft mit Fermat in Verbindung gebracht, der es wiederholt in seinem Werk zur Zahlentheorie verwendete. Auf die Äquivalenz dieser beiden Prinzipien wird jedoch erst seit Kurzem hingewiesen, eine Tatsache, die auf der Entwicklung der mathematischen Logik beruht. Das Hauptwerkzeug hierfür ist das Konzept der Wohlordnung, in welchem Georg Cantor ein fundamentales „Werkzeug des Denkens“ sah. Es erlaubt uns die Äquivalenz zwischen mathematischer Induktion und unendlichem Abstieg zu erkennen, aber auch mit anderen Mengen außer den natürliche Zahlen zu arbeiten und insbesondere zu verstehen, wie Induktion mit mehr als einer Induktionsvariable funktioniert (wie Z.B. in der Ackermannfunktion).

Das Beispiel vom Beginn dieses „Klein-Artikels“ zeigt, dass mathematische Induktion ein allgemeines Werkzeug der Mathematik ist und kein alleiniges Werkzeug der Zahlentheorie. Besonders in der diskreten Mathematik spielt sie eine große Rolle.

Dieser „Klein-Artikel“ bot außerdem Anlass, viele wichtige Fragen zusätzlich zu – aber nicht unabhängig von – der Induktion zu nennen, wie z.B. die der Berechenbarkeit. Die Mathematisierung des intuitiven Konzepts der Berechenbarkeit, welche die Encodierung von verschiedenen Typen von diskreten Objekten und die Verwendung von Diagonalargumenten erfordert, hat dabei geholfen, viele wichtige Resultate in verschiedensten Feldern zu erzielen. Sie ist außerdem entscheidend für Verbindungen zwischen Mathematik und Informatik.

Von der Rekursion zur Induktion

Related

Laisser un commentaire Annuler la réponse

Receive notice of every new vignette.

Search

Meta

Von der Rekursion zur Induktion

Partager :

Related

Laisser un commentaire Annuler la réponse

Receive notice of every new vignette.

Search

Meta