Beweis des Divisionssatzes mit starker Induktion

Meiner Meinung nach machst du dir zu viele Gedanken.

Induktion einschalten$a$.

Für$a=0$, die aussage stimmt:$0=b0+0$Und$0<b$.

Vermuten$a>0$und dass die Aussage für alle gilt$c<a$.

Wenn$a<b$, Dann$a=b0+a$Und$a<b$. Wenn$a\ge b$, Dann$a-b<a$, So$a-b=bq+r$mit$r<b$; seit$a=b(q+1)+r$, Wir sind fertig.

Sie können es durch starke Induktion beweisen$a$.

Für$a=0$, es ist trivial.

Betrachten Sie nun eine beliebige$a\in\mathbb N$und gehe davon aus, dass jeder$a'<a$kann geschrieben werden als$qb+r$, mit$r<b$. Nun, wenn$a<b$, Du kannst schreiben$a$als$0\times b+a$. Ansonsten überlegen$a-b$. Nach der Induktionsvoraussetzung kann es geschrieben werden als$bq+r$, mit$r<b$. Aber dann$a=(q+1)b+r$.

Die Idee ist, dass das Set$S$von ganzen Zahlen der Form$\, a - n b\,$ist unter Subtraktion durch abgeschlossen $b$so können wir kontinuierlich subtrahieren$b$aus$a$bis wir ein Element erreichen$< b.\,$Wenden Sie in der Tat Folgendes an.

Lemma $\ $Wenn nicht leer$S\subseteq \Bbb N\,$ist unter Subtraktion abgeschlossen$\!\ge 0\,$von$\,b,\,$dh$\,s\ge b\in S\Rightarrow\, s-b \in S\,$Dann$S$enthält ein natürliches$< b$

Nachweisen $\ $Am wenigsten $\,\ell\in S$befriedigen muss$\,\ell < b,\,$anders$\,\ell-b\in S$wäre ein kleineres Element von$S$.