Z zasady indukcji matematycznej wynika natychmiast następujące twierdzenie zwane "zasadą minimum".

Dowód.

Niech A ≠ ∅, A ⊆ N i przypuśćmy, że w A nie ma liczby najmniejszej (tzn. A nie ma elementu pierwszego). Oznacza to w szczególności, że 0 ∉ A. Rozważmy zbiór B takich liczb naturalnych n, że ani n ani żadna liczba mniejsza od n nie należy do A, B = {n : ( ∀ m ≤ n) m ∉ A}. Udowodnimy, że wobec przyjętych założeń, musi być B=N. Dowód tego faktu przeprowadzimy wykorzystując zasadę indukcji matematycznej.

(1) Ponieważ 0 nie należy do A, to z definicji zbioru B wynika, że 0 ∈ B.

(2) Załóżmy, że dla pewnego n, n ∈ B. Udowodnimy, że liczba n+1 należy do B.

Dowód (2)

Z założenia indukcyjnego wynika, że wszystkie liczby mniejsze od n oraz samo n nie należą do zbioru A. Gdyby więc (n+1) ∈ A, to byłby to element najmniejszy w A, co nie jest możliwe wobec przyjętego o A założenia. Zatem (n+1) ∉ A, a stąd (n+1) ∈ B.
Ponieważ wykazaliśmy, że oba założenia zasady indukcji są spełnione, to na mocy tejże zasady indukcji wszystkie liczby naturalne należą do B.

Skoro jednak udowodniliśmy, że N=B, to zbiór A musi być pusty, wbrew założeniu. Sprzeczność ta dowodzi, że nie można znaleźć takiego niepustego podzbioru A zbioru liczb naturalnych, który nie miałby elementu pierwszego, a to oznacza, że każdy niepusty podzbiór N ma element pierwszy. ♦

Przykład 9.2.1

Udowodnimy, że {n ∈ N : 3|(n³-n)} = N. W przedstawionym dowodzie "nie wprost" wykorzystamy zasadę minimum. Niech A= {n ∈ N : 3|(n³-n)}. Przypuśćmy, że A ≠ N. Wtedy na mocy zasady minimum, w zbiorze N\A istnieje element najmniejszy. Ponieważ 3|0, więc 0 ∈ A, a tym samym 0 nie jest elementem najmniejszym w N\A. Niech więc elementem najmniejszym w N\A będzie jakaś liczba k>0. Jako element zbioru N\A, k nie należy do A, zatem  3 nie jest dzielnikiem (k³-k). Rozważmy liczbę k-1. Mamy (k-1) ∈ N oraz

(k-1) ³ - (k-1) = k³-3k² + 3k -1 -k +1 = (k³-k) -3k(k-1) .

Ponieważ (k³-k) nie dzieli się całkowicie przez 3, a 3k(k-1) jest wielokrotnością 3, zatem liczba (k-1) ³ -(k-1) nie dzieli się przez 3. Wynika stąd, że (k-1) ∈ N\A, co przeczy założeniu, że k było liczbą najmniejszą w zbiorze N\A. W konsekwencji musi być A=N. ♦

Pytanie 9.2.1 Czy dla dowolnej liczby naturalnej n>1, nⁿ > n!