Peano-Halbring/Division mit Rest/Fakt/Beweis

Beweis

Wir betrachten zum Nachweis der Existenz die erststufige Aussage

$\mathrm{\forall }d(d\ge 1\to \mathrm{\exists }q\mathrm{\exists }r(m=dq+r\wedge r\le d\wedge \mathrm{\neg }r=d)),$

die $m$ als einzige freie Variable besitzt. Für  $m=0$  ist die Aussage mit  $q=0$  und

$r=0$

richtig. Zum Beweis des Induktionsschritts sei

$m=dq+r$

mit den angegebenen Eigenschaften. Daher ist

$m+1=dq+r+1.$

Wenn  $r^{\prime }=r+1$  kleiner als $d$ ist, so erfüllen $q,r^{\prime }$ die geforderten Eigenschaften. Bei  $r+1\ge d$  muss  $r+1=d$  nach Aufgabe gelten. Dann ist

$m+1=dq+r+1=dq+d=d(q+1),$

sodass $q+1$ und $0$ das Geforderte leisten. Für die Eindeutigkeit siehe Aufgabe.

Zur bewiesenen Aussage