youproof.orgDeep Math. Human Access.

Bizonyítás

A teljes indukciót a bb-re fogjuk alkalmazni. Első lépésként feltesszük, hogy az állítás már igaz valamilyen b=nb=n természetes számra, azaz a+s(n)=s(a)+na+s(n)=s(a)+n. Ez lesz tehát az indukciós feltételünk. Ezek után az indukciós lépés megtételéhez azt kell bizonyítanunk, hogy ebben az esetben b=s(n)b=s(n)-re is igaz lesz, azaz:

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

Most nézzük meg, hogy a baloldali kifejezésből milyen lépéseken keresztül tudunk eljutni a jobboldali kifejezéshez. Először is a 11.4. Definíció 2. pontja miatt:

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

Az indukciós feltétel miatt:

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

Végül szintén a 11.4. Definíció 2. pontja miatt:

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

Vagyis azt kaptuk, hogy valóban

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

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. De mit sem érnénk ezzel a ténnyel, ha nem borítanánk fel az első dominót. Ezért most azt igazoljuk, hogy az állítás igaz b=0b=0-ra, azaz:

a+s(0)=s(a)+0a+s(0) = s(a) + 0

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

a+s(0)=s(a+0)=…a + s(0) = s(a+0) = \ldots

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

…=s(a)=…\ldots = s(a) = \ldots

És ismét a 11.4. Definíció 1. pontja miatt:

…=s(a)+0\ldots = s(a) + 0

Vagyis azt kaptuk, hogy valóban a+s(0)=s(a)+0a+s(0) = s(a) + 0, borul tehát az első dominó, és vele együtt a teljes dominósor.

Ha ugyanis az állítás igaz b=0b=0-ra, akkor igaz lesz b=1b=1. De ha igaz b=1b=1-re, akkor igaz lesz b=2b=2-re is. És így tovább, mivel láttuk, hogy ha igaz b=nb=n-re, akkor igaz lesz b=s(n)b=s(n)-re is, ezért ez az igazság a rákövetkezésen keresztül tovább öröklődik egészen a végtelenségig.

∎