youproof.orgDeep Math. Human Access.

Bizonyítás

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

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

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

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

Az indukciós feltétel miatt:

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

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

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

Végül a 11.6. Lemma miatt:

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

Vagyis azt kaptuk, hogy valóban a+s(n)⏟=b=s(n)⏟=b+aa + \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.7. Lemma alapján az állítás igaz b=0b=0-ra.

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

∎