Jedną z najważniejszych teorii matematycznych jest arytmetyka liczb naturalnych. W tym wykładzie, jak zauważył już może Czytelnik, liczby naturalne to 0, 1, 2, 3 itd., a ich zbiór to N. Elementarna arytmetyka liczb naturalnych używa języka, w którym oprócz stałej 0 występuje jednoargumentowa funkcja suc, nazywana następnikiem, i relacja równości. Aksjomaty tej teorii, a więc podstawowe prawa rządzące liczbami naturalnymi, sformułował Peano.

Ax1. Zero jest liczbą naturalną.

Ax2. Dla każdej liczby naturalnej n istnieje dokładnie jedna liczba naturalna suc(n), która jest następnikiem n.

Ax3. Zero nie jest następnikiem żadnej liczby naturalnej.

Ax4. Jeżeli k jest następnikiem liczby n, k = suc(n), i k jest następnikiem liczby m, k = suc(m), to n = m.

Ax5. Zasada indukcji matematycznej: Jeżeli A jest podzbiorem zbioru liczb naturalnych N takim, że spełnione są warunki (1), (2):

to A = N.

Pierwszy z aksjomatów stwierdza tylko, że 0 ∈ N. Drugi aksjomat definiuje funkcję jednoargumentową suc, określoną dla wszystkich liczb naturalnych i zwaną funkcją następnika. Aksjomat czwarty zapewnia, że funkcja suc jest różnowartościowa, tzn. różnym liczbom naturalnym są przyporządkowane różne następniki. Aksjomat trzeci wyróżnia 0 jako taki element zbioru liczb naturalnych, który nie jest wartością funkcji suc. Wreszcie aksjomat piąty mówi jak można zbudować zbiór liczb naturalnych z zera przez sukcesywne zastosowanie funkcji następnika: każda liczba naturalna n jest otrzymana z zera przez n-krotne wykonanie operacji następnika,

1=^df suc(0), 2 = ^df suc(suc(0)), 3 = ^df suc(suc(suc(0))), itd.

Fakt ten wielokrotnie, i często nieświadomie, wykorzystuje się w programowaniu z użyciem pętli "while" stwierdzając, że program {x:= 0; while x < y do x := x+1 od } nie zapętla się dla wszystkich wartości naturalnych zmiennej y.

Aby zilustrować użycie zasady indukcji w dowodach twierdzeń matematycznych, rozważmy następujący przykład 9.1.1. Inne przykłady podamy w następnym punkcie wykładu.

Przykład 9.1.1

Każda liczba postaci n⁵-n dla n ∈ N jest podzielna przez 5?

Dowód .

Niech A={n ∈ N: (n⁵ - n) mod 5 = 0}. Udowodnimy, że N=A.

1. 0 ∈ A, ponieważ 0⁵ - 0 = 0.
2. Weźmy jakąś ustaloną liczbę n należącą do A. Wynika stąd oczywiście, że dla pewnego naturalnego k, mamy n⁵ - n = 5k. Wtedy jednak (n+1)⁵ - (n+1) jest też podzielne przez 5, bo

(n+1)⁵-(n+1) = n⁵+5n⁴+10n³ +10n²+5n +1- n -1 = n⁵ - n + 5(n⁴ +2n³ +2n² +n) = 5(k+n⁴ +2n³ +2n² +n) .

Stąd n+1 ∈ A.

Ponieważ oba założenia zasady indukcji matematycznej zostały spełnione, zatem możemy wywnioskować, że A=N. Oznacza to, że dla dowolnej liczby naturalnej n, liczba n⁵-n jest podzielna przez 5. ♦

Pytanie 9.1.1: Jaka jest ostatnia cyfra rozwinięcia dziesiętnego liczby 37 ⁵⁰⁰ - 37 ¹⁰⁰ ?