Episode I

Alice és Bob

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

Az a-ra vonatkozó teljes indukciót alkalmazunk, azaz feltesszük, hogy az állítás már igaz valamilyen a=n természetes számra. Indukciós feltevésünk szerint tehát s(b)\cdot n=(b\cdot n) + n. Azt kell bizonyítanunk, hogy ekkor az állítás a=s(n)-re is teljesül, azaz:

s(b)\cdot s(n) = (b\cdot s(n)) + s(n)

A Peano-szorzás 12.1. Definíciójának 2. pontja miatt:

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

Az indukciós feltétel miatt a zárójel átírható:

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

Tekintve, hogy az összeadás asszociatív (lásd: 11.8. Tétel), ezért ezt a kifejezést átzárójelezhetjük:

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

A Peano-összeadás 11.4. Definíciójának 2. pontja miatt a zárójel átírható:

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

Tekintve, hogy az összeadás kommutatív (lásd: 11.7. Tétel), ezért a jobboldali tagban szereplő s függvény paramétere átírható:

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

Ismételten a Peano-összeadás 11.4. Definíciójának 2. pontját alkalmazva:

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

Az összeadás asszociativitása miatt ez a kifejezés ismételten átzárójelezhető:

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

Végül a Peano-szorzás 12.1. Definíciójának 2. pontja miatt a zárójelben lévő kifejezés átírható:

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

Vagyis azt kaptuk, hogy valóban s(b)\cdot \underbrace{s(n)}_{=a} = (b\cdot \underbrace{s(n)}_{=a}) + \underbrace{s(n)}_{=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. Ezért most felborítjuk az első dominót, azaz igazoljuk, hogy az állítás igaz a=0-ra, azaz:

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

Ez viszont nyilvánvalóan teljesül, hiszen a Peano-szorzás 12.1. Definíciójának 1. pontja miatt:

s(b)\cdot 0 = 0 = \ldots

Szintén ugyanezen ok miatt:

\ldots = b\cdot 0 = \ldots

Végül a Peano-összeadás 11.4. Definíciójának 1. pontja miatt:

\ldots = (b\cdot 0) + 0

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