104309

Zatem Vn [(p(n) => <p(n + l)]_f a więc Vn <p(n). □

Zasada minimum

Niech W będzie dowolną własnością liczb naturalnych taką, że 3n W(n). Wówczas istnieje najmniejsza liczba naturalna n taka, że W(n).

3n W(n) => 3n (W(n) a Vk [k < n => ~ W(k)]}

Algorytm dowodu: Czy W(0)? Jeśli tak, to dowód zakończony. Jeśli nie, to pytamy, czy W(l)? Jeśli tak, to dowód zakończony. Jeśli nie, to pytamy, czy W(2)? (...) Dochodzimy do no takiego, że W(no). Dowód zakończony.

Twierdzenie. Każda liczba naturalna n > 1 dzieli się przez pewną liczbę pierwszą.

Dowód, n jest liczbą pierwszą lub n nie jest liczbą pierwszą. W pierwszym przypadku n dzieli się przez n, które jest liczbą pierwszą (teza zachodzi). Załóżmy wiec, że n nie jest liczbą pierwszą. Określamy W(m) m>lAm^lAm^n₁Am|iL 3m W(m). Stąd 3m (W(m) a Vk [k < m => ~ W(k)]}. Wybierzmy m takie, że W(m) oraz Vk [k < m => ~ W(k)]. Twierdzimy, że m jest liczbą pierwszą. Gdyby istniało k takie, że k * 1 i k * m i k | m, to wówczas k | n i k < m < n, czyli k * 1 i k * n. W(k) i k < m, co jest niemożliwe.

Do wyrażenia zasady minimum (istnienia elementu najmniejszego, a nie tylko minimalnego) potrzebne jest pojęcie (relacja) porządku liniowego.

Porządki liniowe, które spełniają zasadę minimum dla dowolnej własności W nazywamy dobrymi porządkami.

Zasada indukcji dla dobrych porządków (zasada indukcji porządkowej, zasada indukcji oparta na zasadzie minimum)

Niech W będzie własnością liczb naturalnych taką, że:

Vn {Vk [k < n => W(k)] => W(n)}

Wówczas Vn W(n).