Natürliche Zahlen/Nichtleere Teilmengen/Hat Minimum/Fakt/Beweis

Beweis

Wir betrachten die Aussage

${}A(n)$ = Alle Teilmengen von ${}\mathbb {N}$, die ${}n$ enthalten, besitzen ein Minimum.

Da jede nichtleere Teilmenge mindestens ein ${}n\in \mathbb {N}$ besitzt, ist die Aussage des Satzes äquivalent zur Gültigkeit von ${}A(n)$ für alle ${}n$. Diese Aussage können wir durch Induktion beweisen. Die Aussage ${}A(0)$ besagt, dass jede Teilmenge ${}M\subseteq \mathbb {N}$, die die ${}0$ enthält, auch ein Minimum enthält. Dies ist aber klar, da dann eben ${}0$ das Minimum ist. Es sei die Aussage ${}A(k)$ nun für alle ${}k\leq n$ schon bewiesen. Wir müssen ${}A(n+1)$ beweisen. Es sei also ${}M\subseteq \mathbb {N}$ eine Teilmenge, die ${}n+1$ enthält. Wenn ${}M$ auch eine Zahl ${}k<n+1$ besitzt, so besitzt ${}M$ nach der Induktionsvoraussetzung ein Minimum. Andernfalls besitzt ${}M$ keine Zahl, die kleiner als ${}n+1$ ist. Dann ist aber ${}n+1$ das Minimum von ${}M$.

Zur bewiesenen Aussage