Das Prinzip vom kleinsten Element
Als Nächstes betrachten wir, erneut in drei Formulierungen, ein auf den ersten Blick ganz andersartiges Prinzip.
Satz (Prinzip vom kleinsten Element)
Positive Form:
Gibt es eine natürliche Zahl, die eine Eigenschaft erfüllt, so gibt es eine kleinste natürliche Zahl, die diese Eigenschaft erfüllt.
Negative Form:
Gibt es in den natürlichen Zahlen ein Gegenbeispiel für eine Eigenschaft, so gibt es ein kleinstes Gegenbeispiel in den natürlichen Zahlen.
Satz (Prinzip vom kleinsten Element, formale Version)
Sei ℰ(n) eine Eigenschaft natürlicher Zahlen. Dann gilt:
positive Form:
∃n ℰ(n) → ∃n* (ℰ(n*) ∧ ∀k < n* ¬ℰ(k))
negative Form:
∃n ¬ℰ(n) → ∃n* (¬ℰ(n*) ∧ ∀k < n* ℰ(k))
Satz (Prinzip vom kleinsten Element, Version für Mengen)
Jede nichtleere Menge von natürlichen Zahlen besitzt ein kleinstes Element. Genauer formuliert: Sei A ⊆ ℕ. Dann gilt:
positive Form:
A ≠ ∅ → ∃n* n* = min(A)
negative Form:
A ≠ ℕ → ∃n* n* = min(ℕ − A)
Dabei ist der Ausdruck n* = min(B) (n* ist das Minimum von B) definiert durch
n* ∈ B ∧ ∀n ∈ B n* ≤ n.
Als Kontrast betrachte der Leser die ganzen und die rationalen Zahlen. Die Mengen
{ −1, −2, −3, … } ⊆ ℤ,
{ 1, 1/2, 1/3, 1/4, … } ⊆ ℚ
sind nichtleer, besitzen aber kein kleinstes Element. Die erste Menge ist unbeschränkt, die zweite dagegen beschränkt.
Exemplarisch diskutieren wir die Anwendung der negativen Form des Prinzips. Diese Form wird oft als „Prinzip vom kleinsten Gegenbeispiel“ oder „Prinzip vom kleinsten Verbrecher“ bezeichnet.
Verlauf eines Beweises mit Hilfe des Prinzips vom kleinsten Element
Um zu zeigen, dass jede natürliche Zahl n die Eigenschaft ℰ besitzt, können durch einen Widerspruchsbeweis so vorgehen:
Annahme nicht. Dann gibt es ein kleinstes Gegenbeispiel n* für diese Eigenschaft, sodass also ℰ(n*) nicht gilt, aber ℰ(n) für alle n < n* erfüllt ist. Nun erzeugen wir einen Widerspruch unter Verwendung dieser Verhältnisse. Typischerweise wird dabei eine Zahl m < n* gefunden, die die Eigenschaft ℰ nicht besitzt. Dies ist ein Widerspruch zur minimalen Wahl von n*.
Der Leser mag sich fragen, ob er, in Theorie und Anwendung, die einfache Induktion, die starke Induktion oder das Prinzip vom kleinsten Element einleuchtender oder einfacher findet. Mathematisch sind diese Prinzipien rein logisch äquivalent. Dass die einfache Induktion verwendet werden kann, um die starke Form zu beweisen, haben wir oben schon gesehen, und natürlich ergibt sich die einfache Induktion auch leicht aus der starken Version. Bemerkenswert ist, dass für die Äquivalenz der starken Induktion und des Prinzips vom kleinsten Element kein „eigentlicher Beweis“ geführt werden muss. Es genügt, das Kontrapositionsgesetz der Aussagenlogik und die Regeln für die Verneinung von Quantoren zu bemühen. Sind A und B Aussagen, so gilt:
A → B ↔ ¬ B → ¬ A.(Kontrapositionsgesetz)
Wenden wir dies auf die starke Induktion
∀n (∀k<nℰ(k) → ℰ(n)) → ∀n ℰ(n)
an, so erhalten wir die äquivalente Aussage
¬ ∀n ℰ(n) → ¬ ∀n (∀k<nℰ(k) → ℰ(n)).
Die Verneinungsregeln für Quantoren und die Tautologie ¬(C → D) ↔ C ∧ ¬D ergeben die äquivalente Aussage
∃n ¬ ℰ(n) → ∃n (∀k<nℰ(k) ∧ ¬ ℰ(n)).
Dies ist aber genau das Prinzip vom kleinsten Element in der negativen Form (dass auf der rechten Seite der Implikation n statt n* ist, ist vielleicht unschön aber logisch untadelig).
Das Prinzip vom kleinsten Element wird oft stillschweigend eingesetzt:
Beispiel: Existenz eines Primteilers
Wir betrachten die Aussage:
Sei n eine natürliche Zahl n ≥ 2. Dann besitzt n einen Primteiler.
Wenn wir dies nicht nur glauben, sondern beweisen möchten, betrachten wir die Menge A aller Teiler d von n mit d ≥ 2. Da n ein Teiler von sich selbst ist und n ≥ 2 gilt, ist A nichtleer. Also besitzt A ein kleinstes Element p. Da jeder Teiler k ≥ 2 von p auch ein Teiler von n ist, muss nach Minimalität von p jeder solche Teiler gleich p sein, d. h. p ist eine Primzahl.