To tylko jedna z 2 stron tej notatki. Zaloguj się aby zobaczyć ten dokument.
Zobacz
całą notatkę
Indukcja matematyczna jako specyficzna metoda dowodzenia
1. Indukcja w wersji starożytnej (Euklides), przez wyczerpywanie.
p jest liczbą naturalną ⇒ (p jest liczbą pierwszą ⇔ {p ≠ 1 ∧ ∀x [x | p ⇒ (x = 1 ∨ x = p)]})
Twierdzenie. Każda liczba naturalna n 1 dzieli się przez pewną liczbę pierwszą.
Dowód. Niech n będzie liczbą naturalną n 1. Jeśli n jest liczbą pierwszą, to teza zachodzi. W przeciwnym przypadku określamy n1 takie, że n1 | n, n1 ≠ 1 i n1 ≠ n. Jeśli liczba n1 jest pierwsza, to teza zachodzi. W przeciwnym przypadku określamy n2 takie, że n2 | n1, n2 ≠ 1 i n2 ≠ n1. Wiemy, że ∀x ∀y [(x 0 ∧ y 0 ∧ x | y) ⇒ x ≤ y]. Gdyby n nie miało dzielnika pierwszego, to otrzymalibyśmy nieskończony malejący ciąg liczb naturalnych (n, n1, n2, ...), co jest niemożliwe. □
2. Zasada indukcji (Dedekind)
Niech W będzie dowolna własnością liczb naturalnych taką, że:
1° W(0)
2° ∀n [W(n) ⇒ W(n + 1)]
Wówczas ∀n W(n).
Gdy wiemy, że zachodzi 1° i 2°, to dla dowolnego k możemy udowodnić, że W(k) w następujący sposób:
1. W(0) (z 1°)
2. W(0) ⇒ W(1) (z 2°)
3. W(1) (MP 1, 2)
4. W(1) ⇒ W(2) (z 2°)
5. W(2) (MP 3, 4)
...
2k - 1. W(k - 1) (MP 2k - 3, 2k - 2)
2k. W(k - 1) ⇒ W(k) (z 2°)
2k + 1. W(k) (MP 2k - 1, 2k) □
Dla dowolnego k mamy dowód w 2k + 1 krokach, że W(k).
Dowód indukcyjny
Ogólny schemat dowodu indukcyjnego
[φ(x1) ∧ ∀k φ(xk) ⇒ φ(xk+1)] ⇒ ∀n φ(xn)
∀n φ(xn) - twierdzenie o liczbach naturalnych
1. Krok wstępny (bazowy) dowodu - pokazujemy, że φ(x1)
2. Krok indukcyjny dowodu:
a) założenie indukcyjne - zakładamy, że φ(xk),
b) teza indukcyjna - wykorzystując założenie indukcyjne dowodzimy, że φ(xk+1).
Wniosek: ∀k φ(xk) ⇒ φ(xk+1)
Zatem ∀n φ(xn). □
Poprawność dowodu indukcyjnego opiera się na indukcyjnej definicji zbioru liczb naturalnych (arytmetyka Peano).
Schemat dowodu przez indukcję
Teza: ∀n φ(n)
Dowód (przez indukcję po n).
1. krok bazowy: zachodzi φ(0), ponieważ ... .
2. krok indukcyjny: weźmy n takie, że φ(n) (założenie indukcyjne). (...) Zatem φ(n + 1) (teza indukcyjna).
Zatem ∀n [φ(n) ⇒ φ(n + 1)], a więc ∀n φ(n). □
Zasada minimum
Niech W będzie dowolną własnością liczb naturalnych taką, że ∃n W(n). Wówczas istnieje najmniejsza liczba naturalna n taka, że W(n).
∃n W(n) ⇒ ∃n {W(n) ∧ ∀k [k
(…)
… 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:
∀n {∀k [k < n ⇒ W(k)] ⇒ W(n)}
Wówczas ∀n W(n).
…
... zobacz całą notatkę
Komentarze użytkowników (0)