youproof.orgDeep Math. Human Access.

Bizonyítás

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

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

A 12.1. Definíció 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

A 11.10. Tétel miatt az összeadás asszociatív, ezért ezt a kifejezést átzárójelezhetjük:

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

A 11.4. Definíció 2. pontja miatt a zárójel átírható:

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

A 11.8. Tétel miatt az összeadás kommutatív, 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 11.4. Definíció 2. pontja miatt:

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

A 11.10. Tétel miatt az összeadás asszociatív, ezért ez a kifejezés ismételten átzárójelezhető:

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

Végül ismét a 12.1. Definíció 2. pontja miatt 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 12.1. Definíció 1. pontja miatt:

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

Szintén ugyanezen ok miatt:

\ldots = b\cdot 0 = \ldots

Végül a 11.4. Definíció 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 természetes számra igaz, hogy s(b)\cdot a = (b\cdot a) + a.

∎