Praktische Informatik 1

1.2 Induktive Definitionen und Beweise

Für fast alle in der Informatik wichtigen Datentypen besteht ein direkter Zusammenhang zwischen ihrer rekursiven Definition (ihrem rekursiven Aufbau) und induktiven Beweisen von Eigenschaften dieser Daten. Wir wollen uns diese Dualität am Beispiel der natürlichen Zahlen betrachten.

Die natürlichen Zahlen lassen sich durch die folgenden so genannten Peano-Axiome definieren:

• 
  1 ist eine natürliche Zahl.
  
• 
  Für jede natürliche Zahl gibt es genau eine natürliche Zahl als Nachfolger.
  
• 
  Verschiedene natürliche Zahlen haben auch verschiedene Nachfolger.
  
• 
  1 ist nicht der Nachfolger irgendeiner natürlichen Zahl.
  
• 
  Sei P eine Menge natürlicher Zahlen mit folgenden Eigenschaften:
  
  • 
    1 ist in P
    
  • 
    Für jede Zahl in P ist auch ihr Nachfolger in P.
    

Dann enthält P alle natürlichen Zahlen.

Das letzte dieser Axiome ist das so genannte Induktionsaxiom. Es wird oft in der Form gebraucht, dass P eine Eigenschaft natürlicher Zahlen ist:

• 
  Sei P eine Eigenschaft natürlicher Zahlen, so dass P(1) gilt und aus P(i) folgt P(i+1). Dann gilt P für alle natürlichen Zahlen.
  

Der erste Mathematiker, der einen formalen Beweis durch vollständige Induktion angab, war der italienische Geistliche Franciscus Maurolicus (1494 -1575). In seinem 1575 veröffentlichten Buch „Arithmetik“ benutzte Maurolicus die vollständige Induktion unter anderem dazu, zu zeigen, dass alle Quadratzahlen sich als Summe der ungeraden Zahlen bis zum doppelten ihrer Wurzel ergeben:

1 + 3 + 5 + ... + (2n-1)=n*n

Beweis: Sei P die Menge natürlicher Zahlen, die diese Gleichung erfüllen. Um zu beweisen, dass P alle natürlichen Zahlen enthält, müssen wir zeigen

• 
  1=1*1
  
• 
  Wenn 1 + 3 + 5 + ... + (2n-1)=n*n,
  dann 1 + 3 + 5 + ... + (2n-1)+(2(n+1)-1)=(n+1)*(n+1)
  

Die Wahrheit dieser Aussagen ergibt sich durch einfaches Ausrechnen.

Hier ist ein geringfügig komplizierteres Beispiel zum selber machen: Die Summe der Kubikzahlen bis n ist das Quadrat der Summe der Zahlen bis n.

Ein wichtiger Gesichtspunkt beim Induktionsaxiom ist, dass die natürlichen Zahlen als „induktiv aufgebaut“ dargestellt werden gemäß den folgenden Regeln:

• 
  1N.
  
• 
  Wenn iN, dann auch i+1N.
  
• 
  Außer den so erzeugten Objekten enthält N keine weiteren Zahlen.
  

Mit anderen Worten, jede Zahl wird erzeugt durch die endlich-oft-malige Anwendung der Operation (+1) auf die Zahl 1.

Das Induktionsaxiom erlaubt es, Funktionen über den natürlichen Zahlen rekursiv zu definieren. Eine rekursive Definition nimmt dabei auf sich selbst Bezug. Solche Definitionen können leicht schief gehen („das Gehalt berechnet sich immer aus dem Gehalt des letzten Jahres plus 3%“ oder „Freiheit ist immer die Freiheit der Andersdenkenden“ oder „GNU is short for »GNU is Not Unix«“). Ein Begriff, der durch solch eine zirkuläre Definition erklärt wird, ist nicht wohldefiniert. Eine Funktion ist nur dann wohldefiniert, wenn sich der Funktionswert eindeutig aus den Argumenten ergibt. Das Prinzip der vollständigen Induktion erlaubt es nun, eine Funktion über den natürlichen Zahlen dadurch zu deklarieren, dass man den Funktionswert für n=1 angibt, und indem man zeigt, wie sich der Funktionswert für (n+1) aus dem Funktionswert für n berechnen lässt. Wenn man nämlich für P die Aussage „der Funktionswert ist eindeutig bestimmt“ einsetzt, so besagt dass Induktionsprinzip, dass dann der Funktionswert für alle natürlichen Zahlen eindeutig bestimmt ist. Zum Beispiel lässt sich die Fakultätsfunktion n!=1*2*…*n ohne „Pünktchen“ dadurch definieren, dass wir festlegen

• 
  1! = 1
  
• 
  Wenn n!=x, dann ist (n+1)!=(n+1)*x
  

Eine andere Schreibweise der zweiten Zeile ist

• 
  (n+1)!=(n+1)*n!
  

Da in dieser Formel „n“ nur ein Stellvertreter für eine beliebige Zahl ist, können wir auch schreiben

• 
  Wenn n>1, dann ist n!=n*(n-1)!
  

Diese Schreibweise ist sehr nahe an der Schreibweise in Programmiersprachen, beispielsweise (in Groovy):

• 
  def fac(n){ if (n==1) return(1) else return(n*fac(n-1)) }
  
• 
  def fac(n){ (n==1)? 1 : n*fac(n-1) }
  

In der vorgestellten Fassung erlaubt es das Induktionsprinzip nur, bei der Definition von f(n) auf den jeweils vorherigen Wert f(n-1) zurückzugreifen. Eine etwas allgemeinere Fassung ist das Prinzip der transfiniten Induktion:

• 
  Sei P eine Eigenschaft natürlicher Zahlen, so dass für alle xN gilt:
  Falls P(y) für alle yx). Dann gilt P für alle natürlichen Zahlen.
  

Dieses Prinzip gilt nicht nur für die natürlichen Zahlen, sondern für beliebige fundierte Ordnungen (in denen es keine unendlich langen absteigenden Ketten gibt). Der Induktionsanfang ergibt sich dadurch, dass es keine kleinere natürliche Zahl als 1 gibt und für die 1 daher nichts vorausgesetzt werden kann. Im Induktionsschritt erlaubt uns dieses Prinzip, auf beliebige vorher behandelte kleinere Zahlen zurückzugreifen. Das Standardbeispiel sind hier die Fibonacci-Zahlen (nach Leonardo di Pisa, filius Bonacci, 1175-1250, der das Dezimalsystem in Europa einführte)

oder, in der programmiersprachlichen Fassung (in Groovy),

def fib(n){ (n<=2)? 1 : fib(n-1) + fib(n-2) }
Die Werte dieser Funktion sind, der Reihe nach, 1,1,2,3,5,8,13,21,… und sollen das Bevölkerungswachstum von Kaninchenpaaren nachbilden. Als Beispiel für einen Beweis, der auf mehrere Vorgänger zurückgreift, zeigen wir die Formel von Binet:

.

Als Lemma benötigen wir, dass für gilt , und ebenso für . Das sieht man durch einfaches Ausrechnen, ebenso die Gültigkeit der Aussage für n=1,2. Damit können wir als Induktionsannahme voraussetzen, dass und . Mit ergibt sich , d.h., , was zu zeigen war.

Die Berechnung der Fibonacci-Zahlen mit der Formel von Binet geht erheblich schneller als mittels der rekursiven Definition:

def binet(n){

((((1 + Math.sqrt(5))/2)**n - ((1-Math.sqrt(5))/2)**n)/Math.sqrt(5))}

binet(50) ergibt sofort 1.258626902500002E10
Im Allgemeinen ist es nicht immer möglich, solch eine geschlossene (nichtrekursive) Formel für eine rekursiv definierte Funktion zu finden.
Wir haben das Induktionsprinzip für natürliche Zahlen und der fundierten Ordnungsrelation < angewendet. Dies ist nur ein Spezialfall des folgenden allgemeinen Prinzips für induktiv erzeugte Mengen.

Das sind Mengen, die definiert werden durch

• 
  die explizite Angabe gewisser Elemente der Menge,
  
• 
  Regeln zur Erzeugung weiterer Elemente aus schon vorhandenen Elementen der Menge
  

sowie der expliziten oder impliziten Annahme, dass die Menge nur die so erzeugten Elemente enthält.

Für induktiv erzeugte Mengen gilt folgendes allgemeine Induktionsprinzip:

Sei P eine Eigenschaft, die Elemente der Menge haben können oder nicht, so dass

• 
  P für alle explizit angegebenen Elemente der Menge gilt, und
  
• 
  P für alle gemäß den Bildungsregeln erzeugten Elemente gilt, falls es für die bei der Erzeugung verwendeten Elemente gilt.
  

Dann gilt P für alle Elemente der Menge.

Beispiele für dieses Erzeugungsprinzip werden später betrachtet.