Indukcja matematyczna
Liczby 1, 2, 3, 4, 5, ... nazywamy liczbami naturalnymi.
Zbiór wszystkich liczb naturalnych oznaczamy symbolicznie N.
Liczby naturalne można wprowadzić w sposób aksjomatyczny:
- 1 jest liczbą naturalną, czyli 1 ∈ N,
- 1 nie jest następnikiem żadnej liczby naturalnej,
- dla każdej liczby naturalnej n istnieje dokładnie jedna liczba
naturalna m, taka że m jest następnikiem n
Zasada indukcji zupełnej
Jeżeli A jest podzbiorem zbioru liczb naturalnych N, takim że 1 ∈ A, oraz dla każdej liczby naturalnej n: jeżeli n ∈ A i m jest następnikiem n, to m ∈ A, to każda liczba naturalna należy do A, czyli A = N.
Zasadę indukcji zupełnej stosuje się w dowodach twierdzeń matematycznych. Natomiast za pomocą pojęć pierwotnych można wprowadzić dodawanie i mnożenie liczb naturalnych. Każda liczba naturalna n ma swój następnik, którego można oznaczyć przez n'. Dodawanie liczb naturalnych można wówczas zdefiniować następująco:
n + m' = (n + m)'
Mnożenie liczb naturalnych można zdefiniować poprzez:
n · m' = (n · m) + n
Relację mniejszości dla liczb naturalnych można zdefiniować za pomocą dodawania w następujący sposób: n < m wtedy i tylko wtedy, gdy istnieje liczba naturalna k, taka że n + k = m. Za pomocą dodawania, mnożenie i relacji mniejszości można zdefiniować kolejne pojęcia, którymi operuje się w arytmetyce liczb naturalnych.
Korzystając z zasady indukcji zupełnej można udowodnić bardzo ważne twierdzenie, które nazywane jest zasadą minimum.
W każdym niepustym zbiorze liczb naturalnych istnieje liczba najmniejsza, czyli mniejsza lub równa, od każdej liczby należącej do tego zbioru.