Indukcja matematyczna
Indukcja matematyczna – metoda:
- dowodzenia twierdzeń o prawdziwości nieskończonej liczby zdań (tez);
- definiowania rekurencyjnego, zob. osobna sekcja.
W najbardziej typowych przypadkach dotyczą one liczb naturalnych[1], choć metodę indukcji stosuje się też do innych zbiorów dobrze uporządkowanych – ten typ indukcji matematycznej jest znany jako indukcja pozaskończona[1]. Dowody indukcyjne to wbrew nazwie rozumowania nie indukcyjne, lecz dedukcyjne, podobnie jak cała matematyka[potrzebny przypis].
Indukcję wykorzystuje się w dowodach między innymi tożsamości, nierówności oraz innych twierdzeń jak reguła znaków Kartezjusza[2]. Najstarsza znana argumentacja tego typu dotyczy sumy początkowych liczb nieparzystych[a]; podał go Francesco Maurolico w pracy Arithmeticorum libri duo (Dwie księgi o arytmetyce) z 1575 roku[3].
Wprowadzenie
[edytuj | edytuj kod]Jak dowieść prawdziwości poniższych stwierdzeń?
Każde z nich zawiera zmienną przebiegającą zbiór nieskończony Każde z tych stwierdzeń jest w istocie zbiorem nieskończenie wielu stwierdzeń. Można zbadać skończoną ich liczbę, gdzie przyjmuje pewne konkretne wartości, przykładowo sprawdzić dla ale nie jest to dowodem[b]. Z drugiej strony nie sposób sprawdzić prawdziwości nieskończenie wielu stwierdzeń w skończonym czasie. Pozostaje więc uciec się do innych metod. Mając na celu dowodzenie stwierdzeń o wszystkich liczbach naturalnych wprowadza się aksjomat – jest to w istocie piąty z aksjomatów Giuseppe Peana (1858–1932) liczb naturalnych – tzw. aksjomat indukcji matematycznej (zob. szczegóły).
Często używaną ilustracją jest efekt domina: ustawiając szereg kamieni domina jeden za drugim można być pewnym przewrócenia wszystkich kamieni (nawet ich nieskończonej liczby), jeśli tylko przewrócono pierwszy kamień, a każdy kamień (z wyjątkiem ostatniego, o ile taki istnieje) przewraca kolejny.
Indukcja niezupełna
[edytuj | edytuj kod]- Aksjomat indukcji matematycznej
- Jeśli jest podzbiorem który spełnia
- dla wszystkich jeśli to
- to stanowi całość tzn.
Aksjomat ten można wykorzystać do dowodzenia stwierdzeń postaci „ dla każdego ” jak następuje. Niech będzie zbiorem wszystkich liczb naturalnych, dla których jest prawdziwe. W pierwszym kroku, tzw. bazie indukcji, sprawdza się, czy czyli prawdziwość Następnie zakłada się, że czyli prawdziwość i przy tym założeniu, nazywanym hipotezą indukcyjną, dowodzi się prawdziwości W ten sposób pokazuje się, że pociąga Z aksjomatu indukcji matematycznej wynika a więc jest prawdziwe dla wszystkich
Powyższy aksjomat można więc sformułować w postaci następującej procedury:
- Zasada indukcji matematycznej
- Niech będzie stwierdzeniem zawierającym liczbę naturalną [c]. Można dowieść stwierdzenia
- dla każdego jest
- zapewniając, że
- jest prawdziwe,
- dla wszystkich jeśli jest prawdziwe, to jest prawdziwe.
Dowody korzystające z zasady indukcji matematycznej składają się z dwóch kroków. Pierwszym jest dowód prawdziwości w praktyce jest to zwykle dość proste, ale nie wolno zaniedbywać tego kroku. W drugim kroku zakłada się prawdziwość założenie to jest hipotezą indukcyjną, i pod tym założeniem dowodzi prawdziwości Dowód przez indukcję nie będzie pełny (ani poprawny), jeśli przeprowadzi się tylko pierwszy krok, a pominie drugi bądź wykona drugi z kroków, a opuści pierwszy. Kontrastując z opisanym dalej wariantem powyższą zasadę nazywa się też indukcją niezupełną.
Przykłady
[edytuj | edytuj kod]- Suma początkowych liczb naturalnych
- Zobacz też:
- Należy dowieść
- W tym celu wykorzystana zostanie zasada indukcji matematycznej:
- a więc wzór jest prawdziwy dla
- Czyniąc założenie (hipotezę indukcyjną) należy upewnić się, że
- Otóż
- a więc wzór jest prawdziwy dla o ile tylko jest prawdziwy dla
- Na mocy zasady indukcji matematycznej
- Suma początkowych potęg dwójki
- Zobacz też:
- Należy dowieść
- Jest co dowodzi prawdziwości stwierdzenia dla
- Zakładając należy dowieść
- Ponieważ
- to wzór jest prawdziwy dla jeśli tylko jest prawdziwy dla
- Zatem
- Nierówność Bernoulliego
- Zobacz też:
- Niech będzie ustaloną liczbą rzeczywistą. Należy udowodnić, że dla wszystkich
- Skoro to nierówność jest prawdziwa dla
- Przyjmując wykazana zostanie
- Zachodzi
- więc nierówność jest prawdziwa dla o ile jest prawdziwa dla
- Stąd
Indukcja zupełna
[edytuj | edytuj kod]Czasami wygodnie jest użyć zasady indukcji w nieco innej postaci. Zakłada się w niej prawdziwość nie tylko ale każdego ze zdań i wnosi o prawdziwości Zapewnia to o prawdziwości dla wszystkich o czym mówi poniższy
- Lemat
- Niech będzie stwierdzeniem zawierającym liczbę naturalną [c]. Zakładając, że
- jest prawdziwe,
- dla wszystkich jeśli są prawdziwe, to jest prawdziwe,
- otrzymuje się prawdziwość dla wszystkich [d].
Dzięki niemu zasada indukcji matematycznej może zyskać nową, czasem bardziej użyteczną postać, tzw. indukcji zupełnej.
- Zasada indukcji matematycznej
- Niech będzie stwierdzeniem zawierającym liczbę naturalną [c]. Można dowieść stwierdzenia
- dla każdego jest
- zapewniając, że
- jest prawdziwe,
- dla wszystkich jeśli są prawdziwe, to jest prawdziwe.
Inne warianty
[edytuj | edytuj kod]- Indukcja z dowolną bazą
- Stwierdzenie „” nie jest prawdziwe dla wszystkich liczb naturalnych zachodzi jednak dla wszystkich liczb naturalnych Do dowiedzenia tego i podobnych mu stwierdzeń również można wykorzystać zasadę indukcji matematycznej. Niech będzie ustaloną liczbą całkowitą (dodatnią, ujemną, zerem) i niech będzie stwierdzeniem dotyczącym liczby całkowitej Udowodnienie prawdziwości dla polega na wykazaniu, że
- jest prawdziwe,
- dla wszystkich jeśli jest prawdziwe, to jest prawdziwe[e].
Istnieje również podobna modyfikacja zasady indukcji zupełnej.
- Indukcja wsteczna
- Zobacz też:
- Niech oznacza pewne stwierdzenie dotyczące liczby naturalnej [c]. Jeżeli
- istnieje ściśle rosnący ciąg liczb naturalnych dla którego jest prawdziwe dla wszystkich
- dla wszystkich jeśli jest prawdziwe, to jest prawdziwe,
- to jest prawdziwe dla wszystkich
Aksjomat czy twierdzenie?
[edytuj | edytuj kod]W wielu źródłach można zamiast „aksjomatu indukcji” spotkać nazwę „twierdzenie o indukcji”; odpowiedź na pytanie tytułowe zależy od kontekstu, w którym jest ono stawiane.
W zastosowaniach matematyki, matematyce elementarnej, czy matematyce dyskretnej dominuje tendencja do mówienia o „twierdzeniu o indukcji matematycznej”, również dlatego, by uniknąć przesadnej formalizacji. Wprowadzając indukcję matematyczną podaje się często dowód twierdzenia o indukcji korzystając z dość intuicyjnej zasady dobrego uporządkowania liczb naturalnych, tzn. założenia, że każdy niepusty zbiór liczb naturalnych zawiera element najmniejszy.
Natomiast w logice, szczególnie gdy liczby naturalne wprowadzane są za pomocą aksjomatów Peana, indukcja traktowana jest jako aksjomat. Z powodu kwantyfikowania po zbiorach w gruncie rzeczy jest to aksjomat logiki drugiego rzędu; w przypadku, gdy rozwijana teoria jest formalizowana w logice pierwszego rzędu, słowo „aksjomat” w wyrażeniu „aksjomat indukcji” należy rozumieć w istocie jako schemat aksjomatu: nieskończoną listę aksjomatów, osobnych dla każdej formuły.
Definiowanie
[edytuj | edytuj kod]Ważną konsekwencją zasady indukcji matematycznej jest następujące twierdzenie uzasadniające poprawność definiowania rekurencyjnego:
- Niech będzie zbiorem wszystkich ciągów skończonych o wyrazach z niepustego zbioru a oznacza zbiór liczb naturalnych mniejszych od wybranej liczby Dla danej funkcji istnieje jedna i tylko jedna funkcja która dla każdej liczby naturalnej spełnia
- gdzie oznacza zawężenie funkcji.
Zobacz też
[edytuj | edytuj kod]- indukcja strukturalna
- paradoks koni – przykład błędnego użycia indukcji matematycznej
- zbiór induktywny
Uwagi
[edytuj | edytuj kod]- ↑ Równość jest prawdziwa dla wszystkich (zob. liczby kwadratowe).
- ↑ Twierdzenie to dotyczące liczb kardynalnych (tzn. „liczności” zbiorów) nosi nazwę twierdzenia Cantora: wszystkich podzbiorów danego zbioru jest niemniej niż elementów tego zbioru, dla dowolnej liczby kardynalnej
- ↑ a b c d Dokładniej: formułą w pewnym języku, w którym jedyną zmienną wolną jest a dziedzina tej zmiennej zawiera wszystkie liczby naturalne.
- ↑ Dowód zgodnie z zasadą indukcji matematycznej (niezupełnej). Niech
- jest prawdziwe (z założenia o bazie indukcyjnej (i)),
- przyjmując hipotezę indukcyjną, że jest prawdziwe; wówczas:
- i i … i jest prawdziwe (z definicji ),
- wszystkie są prawdziwe (z własności koniunkcji),
- jest prawdziwe (z założenia o hipotezie indukcyjnej (ii)),
- wszystkie są prawdziwe,
- i i … i i jest prawdziwe,
- jest prawdziwe.
- i i … i są prawdziwe dla wszystkich
- ↑ Można się o tym łatwo przekonać podstawiając dla i korzystając z zasady indukcji matematycznej (niezupełnej) dla w miejsce
Przypisy
[edytuj | edytuj kod]- ↑ a b indukcja matematyczna, [w:] Encyklopedia PWN [online], Wydawnictwo Naukowe PWN [dostęp 2024-03-19] .
- ↑ Michał Tarnowski , Reguła znaków Kartezjusza, „Delta”, czerwiec 2023, ISSN 0137-3005 [dostęp 2024-03-19] .
- ↑ Biografia Maurolico, Francesco, Wydział Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego, wazniak.mimuw.edu.pl [dostęp 2024-03-19].
Linki zewnętrzne
[edytuj | edytuj kod]- Indukcja matematyczna, Zintegrowana Platforma Edukacyjna, zpe.gov.pl [dostęp 2024-03-19].
- Indukcja – wprowadzenie, portal ucze-sie.pl, Wydział Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego, smurf.mimuw.edu.pl [dostęp 2024-03-19].
- Michał Miśkiewicz , Mały krok dla człowieka, wielki skok dla indukcji, „Delta”, wrzesień 2023, ISSN 0137-3005 [dostęp 2023-12-10] .
- Mathematical induction (ang.), Encyclopedia of Mathematics, encyclopediaofmath.org [dostęp 2024-03-19].