6. Induktives Vorgehen PDF

Preview

Summary

Download 6. Induktives Vorgehen PDF

Description

6 INDUKTIVES VORGEHEN 6.1

volls tändige induktion

Wir gehen in dieser Vorlesung davon aus, dass die natürlichen Zahlen etwas sind, worunter sich alle (jedenfalls weitgehend) das Gleiche vorstellen. Wir meinen hier immer die Zahlen einschließlich der 0 und schreiben N0 = {0, 1, 2, 3, 4, . . . } Das ist ausreichend, solange man nicht Beweise führen möchte, bei denen man auf besondere Eigenschaften der natürlichen Zahlen zurückgreifen möchte. Genau das werden wir nun aber tun. Hätten wir eine Definition der natürlichen Zahlen angegeben, dann wäre das folgende Bestandteil der Definition. Mangels einer ordentlichen Definition müssen wir uns auf eine Mitteilung beschränken. Es gilt nämlich: Wenn eine Menge M nur Zahlen aus N0 enthält, • 0 ∈ M ist und

• für jedes n ∈ N0 aus n ∈ M folgt, dass auch n + 1 ∈ M ist,

dann ist M = N0 , enthält also tatsächlich alle natürlichen Zahlen. Das ist die Grundlage für das Beweisprinzip der vollständigen Induktion. Dabei hat man im einfachsten Fall ein „Aussageschema“ A, in dem eine Variable vorkommt, für die man jede natürliche Zahl einsetzen kann. Für jeden konkreten Wert n ∈ N0 ergibt sich eine Aussage An , die wahr oder falsch ist. Vollständige Induktion benutzt man, um zu beweisen, dass jede Aussage An wahr ist, gleich, welchen Wert n hat. Bezeichnet M = { n ∈ N0 | An ist wahr } , dann hat man also zu zeigen, dass M = N0 ist. Und das macht man gerade, indem man die oben genannte Eigenschaft der natürlichen Zahlen anwendet. Man hat also zu zeigen: • 0 ∈ M ist und • für jedes n ∈ N0 folgt aus n ∈ M, dass auch n + 1 ∈ M ist. Das bedeutet mit anderen Worten, dass man zeigen muss: • A0 ist wahr und • für jedes n ∈ N0 gilt: wenn An wahr ist, dann ist auch An+1 wahr.

49

vollständige Induktion

Induktionsanfang Induktionsschritt

In einem entsprechenden Beweis nennt man den ersten Punkt Induktionsanfang, den zweiten den Induktionsschritt. Man könnte einwenden, dass man durch diese Vorgehensweise nichts gewonnen hat, denn im Induktionsschritt muss man ja erneut beweisen, dass etwas für jedes n ∈ N0 gilt. Die gute Nachricht ist aber, dass in vielen Fällen der Nachweis, dass An → An+1 für jedes n ∈ N0 gilt, deutlich einfacher ist als der Nachweis, dass An für jedes n ∈ N0 gilt. Für ein Beispiel, an dem man das alles sehr schön sieht, kommen wir zurück auf Konkatenation und Potenzen von Wörtern. Es sei im Folgenden A ein beliebiges Alphabet. Wir erinnern daran, dass für jedes w1 und jedes w2 ∈ A ∗ gilt: | w1 w2 | = | w1 | + | w2 | (siehe Lemma 4.2). Außerdem hatten wir die Potenzen eines Wortes w ∈ A ∗ so definiert: w0 = ε für jedes k ∈ N0 : wk+1 = wk · w Wir wollen nun beweisen:

6.1 Lemma. Für jedes Alphabet A und jedes Wort w ∈ A ∗ gilt: Für jedes n ∈ N0 ist | wn | = n | w | . 6.2 Beweis. Dass die Aussage für jedes Alphabet A und jedes Wort w ∈ A ∗ gilt, beweisen wir, indem wir annehmen, dass ein beliebiges Alphabet A und ein beliebiges Wort w ∈ A ∗ gegeben seien, über die keine weiteren einschränkenden Annahmen getroffen werden. Damit müssen wir nun also zeigen: „Für jedes n ∈ N0 ist | wn | = n | w|.“ Die Aussagen An , die im obigen Schema der vollständigen Induktion benutzt wurden, sind also gerade diese: An ist | wn | = n | w| Induktionsanfang: Im Fall n = 0 ist zu zeigen, dass A0 wahr ist, dass also gilt: | w0 | = 0| w|. Das ist einfach:

| w0 | = | ε | = 0 = 0 · | w | . Im Induktionsschritt muss gezeigt werden, dass für jedes n ∈ N0 gilt: An → An+1 . Das tun wir, indem wir „irgendein beliebiges n ∈ N0 “ hernehmen (siehe auch die Bemerkung zu Beginn von Beweis 4.4) und zeigen, dass für dieses n gilt: An → An+1 . Wann ist die Implikation wahr? In Abschnitt 5.3 haben wir gesehen, dass das zum einen der Fall ist, wenn An falsch ist; dann müssen wir nichts tun. Wenn An wahr ist, dann muss auch An+1 wahr sein.

gbi:skript:6

50

© worsch&wacker 2008–2021

Benutzen wir also die Induktionsvoraussetzung: | wn | = n | w|. Gezeigt werden muss, dass dann auch gilt: | wn+1 | = ( n + 1)| w|. Dafür kann man natürlich die Definition von wn nutzen:

| wn + 1 | = | wn · w |

= | wn | + | w |

= n | w| + | w| = ( n + 1)| w|

nach Induktionsvoraussetzung

Damit sind wir fertig.

6.2

varianten volls tändiger induktion

Manchmal ist es erzwungen oder hilfreich, Varianten des eben vorgestellten Schemas zu benutzen. Die drei folgenden Fälle werden auch in dieser Vorlesung noch vorkommen: 1. Induktionsanfang an „anderer“ Stelle, wenn zum Beispiel nur für jedes n ∈ N+ Aussagen An definiert sind. 2. im Induktionsschritt Benutzung nicht nur von An , sondern von „mehreren früheren“ Aussagen Ai mit i ≤ n. 3. „mehrere Induktionsanfänge“, wenn man z. B. explizit zeigt, dass A0 , A1 und A2 wahr sind. Der erste Fall ist ganz einfach zu behandeln. Es sei k ∈ N+ und stellen Sie sich vor, dass man nur für jedes n ∈ N0 mit n ≥ k eine Aussage An definiert hat oder dass man nur für jedes n ≥ k beweisen will oder kann, dass An wahr ist. Dann kann man im Induktionsanfang beweisen, dass Ak wahr ist, und im Induktionsschritt, dass für jedes n ∈ N0 mit n ≥ k die Implikation An → An+1 gilt. Zur Begründung überlege man einfach, dass die Menge M = {i ∈ N0 | Ai+k ist wahr} genau dann gleich N0 ist, wenn die Aussagen An für jedes n ≥ k wahr sind. Von der zweiten oben genannten Variante wollen wir den allgemeinsten Fall betrachten. Dazu sei für jedes n ∈ N0 eine Aussage Bn definiert. Wir behaupten, dass man für den Nachweis, dass jede Aussage Bn wahr ist, so vorgehen darf, dass im Induktionsschritt für den Beweis von Bn+1 als „Induktionsvoraussetzungen“ immer nicht nur Bn benutzt wird, sondern jede der Aussagen Bi mit i ≤ n.

gbi:skript:6

51

© worsch&wacker 2008–2021

Um nachzuweisen, dass man dabei keinen Fehler begeht, führen wir diese Vorgehensweise auf die strikte zurück, die wir im ersten Abschnitt kennengelernt haben. Dazu wird für n ∈ N0 eine neue Aussage An definiert als „Für jedes i ∈ N0 mit i ≤ n ist Bi wahr.“ Insbesondere ist also für ein n ∈ N0 eine Aussage Bn wahr, sobald die Aussage An wahr ist. Um zu beweisen, dass jede Aussage Bn wahr ist, ist es also hinreichend, zu beweisen, dass jede Aussage An wahr ist. Was bedeutet ein Beweis der Aussagen An durch vollständige Induktion? • Im Induktionsanfang muss man A0 beweisen. Das ist aber äquivalent zur Aussage B0 . • Im Induktionsschritt muss man für n ∈ N0 beweisen: An → An+1 . An+1 ist die Aussage „Für jedes i ∈ N0 mit i ≤ n + 1 ist Bi wahr.“ An+1 kann man aber auch so ausdrücken: „Für jedes i ∈ N0 mit i ≤ n gilt Bi und es gilt Bn+1 .“ Also ist An+1 äquivalent zu der Aussage „An und Bn+1 “. Damit das gilt, müssen zwei Dinge bewiesen werden: – An : das ist aber banal, denn das ist ja gerade die Induktionsvoraussetzung

Fibonacci-Zahlen

– Bn+1 : Dafür muss im Allgemeinen etwas geleistet werden, aber man darf auch hier die Induktionsvoraussetzung benutzen, die besagt: „Für jedes i ∈ N0 mit i ≤ n gilt Bi .“ Man darf also für den Beweis von Bn+1 nicht nur auf Bn , sondern auch auf alle „früheren“ Aussagen Bn−1 , . . . , B0 zurückgreifen. Der dritte zu Beginn dieses Abschnittes genannte Fall, dass man unter Umständen „mehrere Induktionsanfänge“ betrachtet, tritt häufig im Zusammenhang mit entsprechenden induktiven Definitionen auf. Ein typisches Beispiel sind die sogenannten Fibonacci-Zahlen. Diese Folge von Zahlen f i ist nach dem italienischen Mathematiker Leonardo Fibonacci benannt, der ungefähr von 1170 bis nach 1240 gelebt hat, und wie folgt festgelegt1 : f0 = 0 f1 = 1 für jedes n ∈ N+ f n+1 = f n + f n−1 Wie man sieht, legt die dritte Zeile nur Werte f i für i ≥ 2 fest, und es werden zwei Werte mit kleineren Indizes benötigt. Und deswegen muss man auch die Fibonacci1 Machmal fängt man mit den Werten 1 und 1 an. Das ändert von der dann am Anfang fehlenden 0 abgesehen nichts an der sich ergebenden Folge der Zahlen.

gbi:skript:6

52

© worsch&wacker 2008–2021

Zahlen mit den zwei kleinsten Indizes explizit festlegen. Man kann beweisen, dass für jedes n ∈ N0 gilt: 1 fn = √ 5

√ !n 1+ 5 − 2

√ !n ! 1− 5 2

Wenn man das mit vollständiger Induktion macht, dann benötigt man • „zwei Induktionsanfänge“ für f 0 und f 1 und • im Induktionsschritt natürlich den Rückgriff auf „zwei Induktionsvoraussetzungen“ für f n und f n−1 .

6.3

induktive definitionen

In den ersten Kapiteln dieser Vorlesung haben wir schon an der ein oder anderen Stelle induktive Definitionen genutzt. Im Folgenden soll es um die Frage gehen, warum so etwas überhaupt sinnvoll ist. Das ist nicht immer so klar wie z. B. zu Beginn von Abschnitt 4.4.4 bei der Definition der iterierten Konkatenation. Die sogenannte Ackermann-Funktion A : N0 × N0 → N0 ist in vielerlei Hinsicht etwas ungewöhnlich. Von den leicht unterschiedlichen Versionen geben wir hier die Definition von Rósza Péter an:

für jedes y ∈ N0 :

für jedes x ∈ N0 :

für jedes x ∈ N0 , y ∈ N0 :

A (0, y) = y + 1 A ( x + 1, 0) = A ( x, 1) A ( x + 1, y + 1) = A ( x, A ( x + 1, y))

Als erstes sei eine Warnung ausgesprochen: Erwarten Sie nicht, dass die Funktionswerte (von Ausnahmen abgesehen) in einem „übersichtlichen Bereich“ liegen, und etwa von Hand oder einem Computer in überschaubarer Zeit bestimmt werden können. Schon die Berechnung von A (3, 3) dauert überraschend lange und für A (4, 4) reicht sozusagen weder die Zeit seit dem Urknall zur Berechnung noch das Weltall zum Aufschreiben des Funktionswertes. Was uns hier interessiert ist die Frage, ob die obigen Formeln überhaupt eine vernünftige Definition sind. Eine Tabelle mit allen Funktionswerten könnte man z. B. so aufbauen:

gbi:skript:6

53

© worsch&wacker 2008–2021

Ackermann-Funktion

x=0 x=1 x=2 .. .

y=0 A (0, 0) A (1, 0) A (2, 0) ...

y=1 A (0, 1) A (1, 1) A (2, 1) .. .

y=2 A (0, 2) A (1, 2) A (2, 2) .. .

y=3 A (0, 3) A (1, 3) A (2, 3) .. .

y=4 A (0, 4) A (1, 4) A (2, 4) .. .

··· ··· ···

Man sieht schnell, dass verschiedene Zeilen der Definition auch disjunkte Teile der Tabelle festlegen: die erste Zeile, die erste Spalte ohne den ersten Wert, und den ganzen Rest. Es bleibt also die Frage, ob überhaupt jedes A ( x, y) wohldefiniert ist. Überlegen Sie kurz . . . Eine Möglichkeit ist, zeilenweise vorzugehen, also zu beweisen: „Für jedes x ∈ N0 ist in Zeile x alles definiert.“ Das kann man tatsächlich per vollständiger Induktion beweisen. • Beim Induktionsanfang für x = 0 muss man dann zeigen: „Für jedes y ∈ N0 ist A (0, y) definiert.“ Das ist klar. • Für den Induktionsschritt von x nach x + 1 ist die Induktionsvoraussetzung „Für jedes y ∈ N0 ist A ( x, y) definiert.“ und man muss beweisen „Für jedes y ∈ N0 ist A ( x + 1, y) definiert.“ Dafür kann man noch einmal vollständige Induktion bemühen.

zusammenfas s ung und aus b lick Beweise durch vollständige Induktion werden immer wieder an vielen Stellen auftauchen. Es ist wichtig, solche Beweise zu verstehen und führen zu können. Das hängt auch damit zusammen, dass induktive Definitionen in der Informatik von großer Bedeutung sind, weil sie eine Möglichkeit bieten, mittels einer endlichen Beschreibung präzise eine unendliche Menge von Objekten festzulegen.

gbi:skript:6

54

© worsch&wacker 2008–2021...