Das Prinzip vom unendlichen Abstieg

Zum Abschluss der Diskussion besprechen wir noch eine (eher psychologische) Umformulierung des Prinzips vom kleinsten Element.

Satz (Prinzip vom unendlichen Abstieg)

Gibt es in den natürlichen Zahlen zu jedem Beispiel für eine Eigenschaft stets noch ein kleineres Beispiel, so gilt die Eigenschaft für keine natürliche Zahl.

Satz (Prinzip vom unendlichen Abstieg, Version für Eigenschaften)

Sei ℰ(n) eine Eigenschaft natürlicher Zahlen. Dann gilt:

∀n(ℰ(n) → ∃m < n ℰ(m)) → ∀n ¬ℰ(n)

Satz (Prinzip vom unendlichen Abstieg, Version für Mengen)

Sei A ⊆ ℕ. Dann gilt:

∀n(n  ∈  A → { 0, …, n − 1 } ∩ A ≠ ∅) → A = ∅

Der Beweis der Äquivalenz des Prinzips zu einem (und damit allen) der obigen Prinzipien sei dem Leser überlassen. Wir notieren noch:

Verlauf eines Beweises mit Hilfe des Prinzips vom unendlichen Abstieg

Um zu zeigen, dass jede natürliche Zahl n die Eigenschaft ℰ(n) besitzt, können wir so vorgehen:

Wir nehmen an, es gilt ¬ℰ(n) für eine natürliche Zahl n. Unter Verwendung dieser Annahme zeigen wir nun, dass ein m < n existiert mit ¬ℰ(m). Nach dem Prinzip vom unendlichen Abstieg (angewendet auf die Eigenschaft ¬ ℰ(n)) ist dann gezeigt, dass ℰ(n) für alle natürlichen Zahlen n gilt.

Schließlich können wir das Prinzip vom unendlichen Abstieg äquivalent auch in der Sprache der Folgen formulieren:

Satz (Prinzip monoton fallender Folgen)

(a)	Es gibt keine streng monoton fallende unendliche Folge in ℕ.

(b)	Jede monoton fallende unendliche Folge in ℕ ist schließlich konstant.

Satz (Prinzip monoton fallender Folgen, formale Version)

(a)	∀(n_k)_k ≥ 0 ∃k n_k + 1 ≥ n_k

(b)	∀(n_k)_k ≥ 0 (∀k n_k ≥ n_k + 1 → ∃k* ∀k ≥ k* n_k = n_k*)