Natürliche Zahlen/Ordnungsrelation/Verträglichkeit/Fakt/Beweis2
Beweis
- Wir beweisen die Aussage durch Induktion über . Bei
ist die Aussage klar. Für den Induktionsschritt müssen wir lediglich zeigen, dass die Aussage für
gilt. Bei
ist die Aussage klar, da der Nachfolger wohldefiniert ist. Bei
ist
nach Fakt (3)
und somit
Dies zeigt zugleich, dass aus auch folgt. Da die Ordnung total ist, folgt somit auch aus die Beziehung .
- Zweifache Anwendung von Teil (1) liefert
sodass die Transitivität den Schluss ergibt.
- Wir führen Induktion nach , die Fälle
sind klar. Es sei die Aussage für bewiesen. Dann ist mit dem Distributivgesetz, der Induktionsvoraussetzung und Teil (2)
- Aus den Voraussetzungen und Teil (3) ergibt sich
- Sei
.
Wir beweisen die Kontraposition, dass aus der Größerbeziehung
die Größerbeziehung
folgt. Sei also
.
Dann ist
und somit ist nach Teil (3) und Teil (2)
also .