Peano-Halbring/Division mit Rest/Fakt/Beweis

Beweis

Wir betrachten zum Nachweis der Existenz die erststufige Aussage

$\forall d{\left(d\geq 1\rightarrow \exists q\exists r{\left(m=dq+r\wedge r\leq d\wedge \neg r=d\right)}\right)},$

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'=r+1$ kleiner als ${}d$ ist, so erfüllen ${}q,r'$ die geforderten Eigenschaften. Bei ${}r+1\geq d$ muss ${}r+1=d$ gelten. Dann ist

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

so dass ${}q+1,0$ das Geforderte leisten. Für die Eindeutigkeit siehe Aufgabe.

Zur bewiesenen Aussage