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