In diesem Beitrag geht es um das aus der Zahlentheorie bekannte Prinzip des kleinsten Elements.
Endliche Teilmengen der natürlichen Zahlen
Eine Teilmenge M der natürlichen Zahlen nennt man endlich, wenn es eine natürliche Zahl k gibt, sodass für jedes Element m aus M gilt: m ≤ k.
Kleinstes Element einer Menge natürlicher Zahlen
Ein Element a aus einer Teilmenge M der natürlichen Zahlen heißt kleinstes Element von M, wenn für jedes Element m aus M gilt: a ≤ m.
Jede nicht-leere und endliche Teilmenge M der natürlichen Zahlen besitzt ein kleinstes Element.
Beweis: Es seien m1, … , mp die p verschiedenen Elemente aus M. Wir setzen m0 := m1. Nun durchlaufen wir die übrigen p-1 Elemente m2, … , mp. Finden wir dabei ein Element mj, dass kleiner als m0 ist, so setzen wir m0 := mj. Das Verfahren endet nach endlich vielen Schritten und m0 ist nach Definition das kleinste Element aus M.
Prinzip des kleinsten Elements
Jede nicht-leere Teilmenge M der natürlichen Zahlen besitzt ein kleinstes Element.
Beweis: Wir wählen ein m aus der Menge M und bilden zwei Mengen M1 und M2 durch
M1 := {n ∈ M | n ≤ m} und M2 := {n ∈ M | m < n}.
Die Menge M1 ist endlich und besitzt nach dem Satz von oben ein kleinstes Element m0. Dieses ist nach Definition auch noch kleiner als alle Elemente aus M2. Wegen M = M1 U M2 ist also m0 ein kleinstes Element von M.