Natürliche Zahlen/Ordnungsrelation/Total/Fakt/Beweis

Beweis

Wir verwenden die Charakterisierung mit der Addition. Wegen ${}n=n+0$ ist ${}n\geq n$. Wenn ${}k\geq \ell$ und ${}\ell \geq m$ ist, so bedeutet dies, dass es natürliche Zahlen ${}a,b$ mit ${}k=\ell +a$ und ${}\ell =m+b$ gibt. Dann gilt insgesamt

${}k=\ell +a=(m+b)+a=m+(b+a)\,$

und somit ist auch ${}k\geq m$. Aus ${}k\geq \ell$ und ${}\ell \geq k$ ergibt sich ${}k=\ell +a$ und ${}\ell =k+b$ und somit ${}k=k+(a+b)$. Dies ist nach der Abziehregel nur bei ${}a+b=0$ möglich, und dies ist wiederum, da ${}0$ kein Nachfolger ist, nur bei ${}a=b=0$ möglich. Die Aussage ${}a\geq b$ oder ${}b\geq a$ beweisen wir durch Induktion über ${}a$ (für jedes feste ${}b$), wobei der Induktionsanfang wegen ${}b\geq 0$ klar ist. Die Aussage gelte also für ein bestimmtes ${}a$. Wenn die erste Möglichkeit gilt, also ${}a\geq b$, so gilt wegen

${}a+1>a\geq b\,$

erst recht ${}a+1\geq b$. Wenn die zweite Möglichkeit gilt, also ${}a\leq b$, so gibt es zwei Möglichkeiten. Bei ${}a=b$ ist ${}a+1\geq b$ und die Gesamtaussage gilt für ${}a+1$. Andernfalls ist ${}a<b$ und somit ist nach Fakt  (3) ${}a+1\leq b$ und die Gesamtaussage gilt erneut.

Zur bewiesenen Aussage