1. Liczby naturalne i zasada indukcji matematycznej

Liczby naturalne to liczby 1, 2, 3,…. , używane powszechnie do liczenia i ustalania kolejności. Liczb naturalnych jest nieskończenie wiele. Zbiór liczb naturalnych oznaczamy symbolem N. Zapis n ∈ N oznacza, że n jest liczbą naturalną.

Tu pojęciami pierwotnymi(tzn. takimi których nie definiujemy) są:

• liczba 1;

• następnik liczby (uwaga: następnikiem liczby n jest n + 1; następnikiem liczby 10 jest 10+1=11).

Przyjmujemy następujące aksjomaty:

• 1 jest liczbą naturalną

• Następnik każdej liczby naturalnej jest liczbą naturalną.

• 1 nie jest następnikiem żadnej liczby naturalnej.

• Dowolne dwie liczby naturalne mające równe następniki są równe.

• Jeśli X jest dowolnym podzbiorem N takim, że:

1. 1 ∈ X

2. dla każdego n ∈ N, jeśli n ∈ X, to następnik n+1 należy do X, wówczas X = N. (zasada indukcji matematycznej)

Równoważna forma zasady indukcji matematycznej:

Niech W(n) będzie własnością przysługującą liczbom naturalnym taką, że:

1. W(1) zachodzi

2. dla dowolnej liczby naturalnej n, jeśli W(n) zachodzi, to W(n + 1) również zachodzi.

Wówczas własność W(n) mają wszystkie liczby naturalne.

Przykład:
Wykazać metodą indukcji matematycznej, że dla każdej liczby naturalnej n liczba n³+5n jest podzielna przez 3.

1. Sprawdzamy poprawność wzoru dla n=1

1³+5*1=6 prawda ponieważ 6 dzieli się przez 3

1. Przypuśćmy że dla pewnego n naturalnego 3|(n³+5n).
   Wówczas: n³+5n=3k
   Należy pokazać że teza zachodzi dla n+1. Zatem mamy:
   (n+1)³+5(n+1) = n³+3n²+3n+1+5n+5= n³+5n+3n²+3n+6=3k+3n²+3n+6=
   =3(k+n²+n+2)

Liczba ta na pewno dzieli się przez 3 zatem na mocy aksjomatu indukcji matematycznej, teza jest prawdziwa dla każdego n ∈ N.