Natürliche Zahlen/Addition mit n/Nachfolgerzählen/Hilfseigenschaften/Fakt/Beweis

Beweis

1. Die Gleichungen links und rechts sind unmittelbar klar, da der ${}n$-te Nachfolger der ${}0$ gleich ${}n$ ist.
2. Die Ausdrücke besagen prozesstheoretisch das gleiche: Links geht man von der Zahl ${}n$ aus und nimmt einmal öfters als ${}k$-mal den Nachfolger. In der Mitte bestimmt man ${}k$-fach den Nachfolger von ${}n$ und nimmt von diesem Ergebnis den Nachfolger. Rechts nimmt man von ${}n$ den Nachfolger und davon dann ${}k$-fach den Nachfolger.
3. Es ist

   ${}n+k=k+n\,$

   für alle ${}k,n$ zu zeigen. Diese Gleichungen zeigen wir durch Induktion über ${}k$ für alle ${}n$. Bei ${}k=0$ steht beidseitig ${}n$ nach Teil (1). Es sei die Gleichheit nun für ein ${}k$ (und alle ${}n$) schon bewiesen. Dann ist unter Verwendung der Induktionsvoraussetzung und Teil (2)

   ${}n+k^{\prime }=(n+k)^{\prime }=(k+n)^{\prime }=k^{\prime }+n\,,$

   die Gleichung gilt also auch für ${}k^{\prime }$.

4. Wir beweisen die Assoziativität, also die Gleichheit

   ${}(m+n)+k=m+(n+k)\,,$

   durch Induktion über ${}k$ (für alle ${}m,n$ gleichzeitig). Mit der Regel aus (2) und der Induktionsvoraussetzung ergibt sich direkt

   ${}(m+n)+k^{\prime }=(m+n)^{\prime }+k=(m+n^{\prime })+k=m+(n^{\prime }+k)=m+(n+k^{\prime })\,.$

5. Die Abziehregel beweisen wir ebenfalls durch Induktion über ${}k$. Der Fall

   ${}k=0\,$

   ist klar. Es sei also die Aussage für ein ${}k$ schon bewiesen und sei eine Gleichung der Form

   ${}m+k^{\prime }=n+k^{\prime }\,$

   gegeben. Dann ist nach der Umlegungsregel auch

   ${}m^{\prime }+k=n^{\prime }+k\,.$

   Nach der Induktionsvoraussetzung ist somit

   ${}m^{\prime }=n^{\prime }\,.$

   Da die Nachfolgerabbildung injektiv ist, ergibt sich

   ${}m=n\,.$

Zur bewiesenen Aussage