Episode I

Alice és Bob

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

Ismételten teljes indukciót alkalmazunk, ám ezúttal a 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+n=n+a. Azt kell bizonyítanunk, hogy ebben az esetben b=s(n)-re is igaz lesz, azaz:

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

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

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

Az indukciós feltétel miatt:

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

Ismételten a 11.4. Definíció 2. pontja miatt:

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

Végül a korábban már bizonyított 11.5. Lemma miatt:

\ldots = s(n) + a

Vagyis azt kaptuk, hogy valóban a + \underbrace{s(n)}_{=b} = \underbrace{s(n)}_{=b} + 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íttottuk, ugyanis a 11.6. 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+b=b+a.