Episode I

Alice és Bob

. rész: Peano-szorzás kommutativitásának bizonyítása

Teljes indukciót alkalmazunk b-re vonatkozóan. Tegyük fel, hogy az állítás igaz valamilyen b=n természetes számra. Az tehát az indukciós feltétel, hogy a \cdot n=n \cdot a. Azt kell bizonyítanunk, hogy ebben az esetben b=s(n)-re is igaz lesz, azaz:

a \cdot \underbrace{s(n)}_{=b} = \underbrace{s(n)}_{=b} \cdot a

A 12.1. Definíció 2. pontja miatt:

a\cdot s(n) = (a\cdot n) + a = \ldots

Az indukciós feltétel miatt:

\ldots =(n\cdot a) + a= \ldots

Végül az imént bizonyított 12.3. Lemma miatt:

\ldots = s(n) \cdot a

Vagyis azt kaptuk, hogy valóban a \cdot \underbrace{s(n)}_{=b} = \underbrace{s(n)}_{=b} \cdot a.

Felállítottuk tehát a dominósort, és beláttuk, hogy bármely dominó felborítása esetén a soron következő dominó is fel fog borulni. Az első dominót pedig már fel is borítottuk, ugyanis a 12.2. Lemma alapján az állítás igaz b=0-ra.

Borul tehát az első dominó, és vele együtt a teljes dominósor, azaz minden a és b számra igaz, hogy a\cdot b=b\cdot a.