Dowody polegające na dodawaniu liczb naturalnych

Podstawowe właściwości arytmetyczne (powiększenie w celu uzyskania dowodów indukcyjnych)

Ten artykuł zawiera matematyczne dowody niektórych właściwości dodawania liczb naturalnych : tożsamości addytywnej, przemienności i asocjatywności. Dowody te są wykorzystywane w artykule Dodawanie liczb naturalnych .

Definicje

W tym artykule użyjemy aksjomatów Peano do definicji liczb naturalnych. W przypadku tych aksjomatów dodawanie jest definiowane na podstawie stałej 0 i funkcji następczej S ( a ) za pomocą dwóch reguł

A1:	za + 0 = za
A2:	za + S( b ) = S ( za + b )

Dla dowodu przemienności przydatne jest nadanie następcy 0 nazwy „1”; to jest,

1 = S(0).

Dla każdej liczby naturalnej a , jeden ma

	S( a )
=	S( za + 0)	[przez A1]
=	a + S(0)	[przez A2]
=	+ 1	[przez Def. z 1]

Dowód asocjatywności

Udowodnimy łączność ustalając najpierw liczby naturalne aib i stosując indukcję po liczbie naturalnej c .

Dla przypadku podstawowego c = 0,

( za + b )+0 = za + b = za +( b +0)

Każde równanie wynika z definicji [A1]; pierwszy z a + b , drugi z b .

A teraz indukcja. Przyjmujemy hipotezę indukcyjną, czyli zakładamy, że dla pewnej liczby naturalnej c ,

( za + b )+ do = za +( b + do )

Potem następuje,

	( za + b ) + S ( do )
=	S (( za + b ) + do )	[przez A2]
=	S ( za + ( b + do ))	[przez hipotezę indukcyjną]
=	za + S ( b + do )	[przez A2]
=	za + ( b + S ( do ))	[przez A2]

Innymi słowy, hipoteza indukcyjna obowiązuje dla S ( c ). Dlatego indukcja po c jest zupełna.

Dowód tożsamości

Definicja [A1] mówi wprost, że 0 jest tożsamością właściwą . Udowodnimy, że 0 jest lewostronną tożsamością przez indukcję po liczbie naturalnej a .

Dla przypadku podstawowego a = 0, 0 + 0 = 0 z definicji [A1]. Przyjmijmy teraz hipotezę indukcyjną, że 0 + a = a . Następnie

	0 + S ( za )
=	S (0 + za )	[przez A2]
=	S ( za )	[przez hipotezę indukcyjną]

To kończy indukcję na .

Dowód przemienności

Udowodnimy przemienność ( a + b = b + a ) stosując indukcję po liczbie naturalnej b . Najpierw udowodnimy przypadki bazowe b = 0 i b = S (0) = 1 (tj. udowodnimy, że 0 i 1 dojeżdżają do pracy ze wszystkim).

Przypadek bazowy b = 0 wynika bezpośrednio z właściwości elementu tożsamości (0 jest tożsamością addytywną ), co zostało udowodnione powyżej: a + 0 = a = 0 + a .

Następnie udowodnimy przypadek bazowy b = 1, że 1 komutuje się ze wszystkim, tzn. dla wszystkich liczb naturalnych a mamy a + 1 = 1 + a . Udowodnimy to przez indukcję po a (dowód indukcyjny w dowodzie indukcyjnym). Udowodniliśmy, że 0 komutuje się ze wszystkim, a więc w szczególności 0 komutuje się z 1: dla a = 0 mamy 0 + 1 = 1 + 0. Załóżmy teraz, że a + 1 = 1 + a . Następnie

	S ( za ) + 1
=	S ( za ) + S (0)	[przez Def. z 1]
=	S ( S ( za ) + 0)	[przez A2]
=	S (( za + 1) + 0)	[jak pokazano powyżej ]
=	S ( a + 1)	[przez A1]
=	S (1 + za )	[przez hipotezę indukcyjną]
=	1 + S ( za )	[przez A2]

To kończy indukcję po a , więc udowodniliśmy przypadek bazowy b = 1. Załóżmy teraz, że dla wszystkich liczb naturalnych a mamy a + b = b + a . Musimy pokazać, że dla wszystkich liczb naturalnych a mamy a + S ( b ) = S ( b ) + a . Mamy

	za + S ( b )
=	za + ( b + 1)	[jak pokazano powyżej ]
=	( za + b ) + 1	[przez asocjatywność]
=	( b + za ) + 1	[przez hipotezę indukcyjną]
=	b + ( za + 1)	[przez asocjatywność]
=	b + (1 + za )	[w przypadku podstawowym b = 1]
=	( b + 1) + za	[przez asocjatywność]
=	S ( b ) + za	[jak pokazano powyżej ]

To kończy indukcję po b .

Zobacz też

Edmund Landau , Podstawy analizy, Chelsea Pub Co. ISBN 0-8218-2693-X .