Die Ordnung der natürlichen Zahlen

aus ZUM-Wiki, dem Wiki für Lehr- und Lerninhalte auf ZUM.de
Wechseln zu: Navigation, Suche

Die Ordnung der natürlichen Zahlen

Auf den natürlichen Zahlen wird eine Ordnung folgendermaßen rekursiv definiert:

  • (Kleiner1) \forall n:\mathbf{N_0}.\ \neg n < 0
  • (Kleiner2) \forall m,n:\mathbf{N_0}.\ m<\sigma(n)\Leftrightarrow m=n \vee m<n

Wenn man dies weiß, dann kann man sich behelfen, wenn natürliche Zahlen einmal durcheinander kommen (beispielsweise weil einem der Korb mit den natürlichen Zahlen auf den Boden gefallen ist).

Dieses Problem tritt beispielsweise auf, wenn man eine unsortierte Adressenliste im Computer hat und diese sortieren möchte. Computer repräsentieren Buchstaben als Zahlen, und für einen Computer ist das Sortieren einer Adressenliste gleichbedeutend mit dem Sortieren natürlicher Zahlen. (Man kann sich jetzt vermutlich darüber streiten, ob es nicht besser ordnen als sortieren heißen sollte. Man sortiert nämlich eher Socken gleicher Farbe. Aber das soll uns nicht stören.)

Damit Computer Zahlen sortieren können, muss man ihnen einen Algorithmus an die Hand geben. Ein Algorithmus ist eine aus endlichen Schritten bestehende eindeutige Handlungsvorschrift zur Lösung eines Problems oder einer Klasse von Problemen. Es gibt viele Sortieralgorithmen. Einer davon ist Bubblesort. Ein wichtiges Kriterium zur Beurteilung von Algorithmen ist die Einschätzung deren Effizienz. Wie viele Vergleichsoperationen benötigt man bei Bubblesort, wenn eine unsortierte Liste vorliegt? Wir betrachten den ungünstigsten Fall:

Bei n+1 unsortierten natürlichen Zahlen benötigt man 1+2+\ldots+n Vergleichsoperationen. Dies drückt man auch folgendermaßen aus: \sum_{i=1}^{n}i. Wir müssen also die Summe der ersten n natürlichen Zahlen bilden, um herauszufinden, wie viele Vergleichsschritte man bei einer Liste von n+1 natürlichen Zahlen benötigt. Mühsam, wenn es sich um 1000000 Zahlen handelt. Wie viele Vergleichsschritte braucht man da?

Gauß hat als kleiner Junge einen Trick gefunden. Es gilt: \sum_{i=1}^{n}i=\frac{n(n+1)}{2}

Neben jeder Menge präformaler Beweise können Formalisten das Ganze natürlich formal Beweisen - mit vollständiger Induktion. Wir verzichten jetzt übrigens mal auf die ganze Sigma-Geschichte. Genug ist genug.

Wir beweisen: \forall n:\mathbf{N}.\ \sum_{i=1}^{n}i=\frac{n(n+1)}{2}.

Induktionsanfang: (n=1)

\sum_{i=1}^{1}i=1=\frac{2}{2}=\frac{1(1+1)}{2}

Induktionsschritt:

Wir schließen nun von n=k auf n=k+1:

Induktionsannahme (n=k): \sum_{i=1}^{k}i=\frac{k(k+1)}{2}

Zu zeigen: \sum_{i=1}^{k+1}i=\frac{(k+1)(k+2)}{2}

\sum_{i=1}^{k+1}i=\sum_{i=1}^{k}i+(k+1)=\frac{k(k+1)}{2}+(k+1)=\frac{k(k+1)}{2}+\frac{2(k+1)}{2}=\frac{k(k+1)+2(k+1)}{2}=\frac{(k+2)(k+1)}{2}=\frac{(k+1)(k+2)}{2}

q.e.d.

Aufgabe: Begründen Sie jede einzelne Umformung in diesem Beweis!