Matematyka.pl

Witam! Jeśli ktoś mógłby mi to wytłumaczyć to chcę tylko znać różnicę między słabą a mocną zasadą indukcji matematycznej. Wiem, jak się z nich oblicza, ale jak określić w słowach co je różni.
Z góry dzięki.

A co rozumiesz przez mocną i słabą zasadę indukcji?

JK

No słaba zasada indukcji matematycznej to wnioskując z moich notatek z wykładów to po prostu zależność gdzie funkcja zdaniowa jest prawdziwa dla \(\displaystyle{ f(n_0)}\) i następnie dla każdego \(\displaystyle{ n}\) należącego do naturalnych większego lub równego \(\displaystyle{ n_0}\) zdanie jest prawdziwe, poprzez sprawdzenie implikacji \(\displaystyle{ f(n) \Rightarrow f(n+1)}\)

W zasadzie mocnej indukcji matematycznej wszystko jest tak samo, ponadto z tego co rozumiem implikuje ona słabą zasadę - każdy przykład zrobiony mocną zasadą, wyjdzie też w słabej. Jednak Mocna zasada różni się tą linijką

\(\displaystyle{ f(n_0)}\) jest prawdziwe
\(\displaystyle{ \forall_k\in \NN, k > n_0 \left[ (\forall_k\in \NN, n_0 < 1 < k \ f(l)) \Rightarrow f(k)\right]}\)
to \(\displaystyle{ \forall_n\in \NN, n \ge n_0 \left[ f(n)]\right]}\)

Niestety nie za bardzo rozumiem co to może oznaczać, a jeśli wie Pan z doświadczenia co to Panu przypomina i gdzie ewentualnie to źle napisałem to chętnie się dowiem.

Zapis taki sobie, ale wiadomo, o co chodzi.

Te dwie zasady indukcji są sobie równoważne. W słabej w kroku indukcyjnym zakładasz prawdziwość \(\displaystyle{ f(n)}\) i to wystarcza do pokazania prawdziwości \(\displaystyle{ f(n+1)}\). W mocnej w kroku indukcyjnym do pokazania, że prawdziwe jest \(\displaystyle{ f(n+1)}\) potrzebujesz założenia, że prawdziwe są wszystkie poprzednie \(\displaystyle{ f(k)}\) dla \(\displaystyle{ k\le n}\). Jeżeli jednak rozumie się, na czym polega indukcja, to intuicyjnie równoważność tych dwóch zasad jest dość oczywista.

JK

Dziękuję, zdaje się że zrozumiałem. Te dwie zasady muszą być sobie równoważne, ponieważ gdyby "słaba" zasada nie spełniała warunku\(\displaystyle{ f(k) < n}\) k - prawda to wtedy dana zależność byłaby prawdziwa tylko dla pierwszego wyrazu i dla jednego konkretnego n które założymy i n+1. Można nawet powiedzieć, że ta funkcja by była prawdziwa tylko w 3 punktach, i gdyby słaba nie równoważyła się mocnej zasadzie, to prawdziwość tylko tych 3 punktów udowadniałaby prawdziwość innych, co prowadziłoby do sprzeczności, ponieważ wszystkie oprócz n0, n i n+ mogłyby być fałszywe.
Więc intuicyjnie, słaba musi zawierać ten dodatkowy aksjomat mocnej, żeby zachodziła, ale ponieważ nie jest on zapisany to stąd wynika różnica.
O to mniej więcej chodzi? Staram się to też zrozumieć, a nie tylko wykuć i zapomnieć po (jutrzejszym xd) kolokwium.
Pozdrawiam.

Szczerze mówiąc nie jest łatwo śledzić Twój tok rozumowania (zwłaszcza o tej porze...), bo wyrażasz się dość nieprecyzyjnie.

JK

Jan Kraszewski pisze:Zapis taki sobie, ale wiadomo, o co chodzi.

Te dwie zasady indukcji są sobie równoważne. W słabej w kroku indukcyjnym zakładasz prawdziwość \(\displaystyle{ f(n)}\) i to wystarcza do pokazania prawdziwości \(\displaystyle{ f(n+1)}\). W mocnej w kroku indukcyjnym do pokazania, że prawdziwe jest \(\displaystyle{ f(n+1)}\) potrzebujesz założenia, że prawdziwe są wszystkie poprzednie \(\displaystyle{ f(k)}\) dla \(\displaystyle{ k\le n}\). Jeżeli jednak rozumie się, na czym polega indukcja, to intuicyjnie równoważność tych dwóch zasad jest dość oczywista.

JK

Jak pokazać, że z mocnej wynika słaba? Może to trywiał, ale jakoś nie widzę…-- 21 marca 2017, 23:52 --Doprecyzuję pytanie. Zasada indukcji porządkowej jest równoważna zasadzie minimum. Z zasady minimum łatwo zaś wyprowadzić zwykłą zasadę indukcji. Zastanawiam się jednak nad dowodem bezpośrednim. Tak jak: https://www.matematyka.pl/404872.htm#p5419400. Tutaj udało się udowodnić bezpośrednio wynikanie w drugą stronę.