Otwórz menu główne

Spis treści

Indukcja matematyczna – metoda dowodzenia twierdzeń o prawdziwości nieskończonej liczby stwierdzeń oraz definiowania rekurencyjnego (zob. osobna sekcja). W najbardziej typowych przypadkach dotyczą one liczb naturalnych.

Dowody wykorzystujące metodę indukcji nazywa się dowodami indukcyjnymi, choć wbrew sugestywnej nazwie argumenty oparte na indukcji matematycznej nie są rozumowaniami indukcyjnymi, lecz dedukcyjnymi (podobnie jak cała matematyka). Najstarszy znany dowód indukcyjny, dotyczący sumy początkowych liczb nieparzystych[a], podał Francesco Maurolico (1494–1575) w pracy Arithmeticorum libri duo („Dwie księgi o arytmetyce”) z 1575 roku.

WprowadzenieEdytuj

 
Efekt domina

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   i czuć się przekonanym o prawdziwości tego stwierdzenia, ale daleko takiemu postępowaniu do dowodu[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łnaEdytuj

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ładyEdytuj

Suma początkowych liczb naturalnych
Zobacz też: liczba trójkątna.
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   Stąd
 
Suma początkowych potęg dwójki
Zobacz też: potęga dwójki.
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
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   Na mocy zasady indukcji matematycznej   dla wszystkich   (dla  ).

Indukcja zupełnaEdytuj

Czasami wygodnie jest użyć zasady indukcji w nieco innej postaci. Zakłada się w niej prawdziwość (nie tylko  ), a każdego z   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 wariantyEdytuj

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 modyfikcja zasady indukcji zupełnej.

Aksjomat czy twierdzenie?Edytuj

Osobny artykuł: aksjomat indukcji.

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, wyrażenie „aksjomat indukcji” oznacza w istocie schemat aksjomatu: nieskończoną listę aksjomatów, osobnych dla każdej formuły.

DefiniowanieEdytuj

Osobne artykuły: definicjarekurencja.

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

UwagiEdytuj

  1. Równość   jest prawdziwa dla wszystkich  
  2. 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  
  3. a b c Dokładniej: formułą w pewnym języku, w którym jedyną zmienną wolną jest   a dziedzina tej zmiennej zawiera wszystkie liczby naturalne.
  4. Dowód zgodnie z zasadą indukcji matematycznej (niezupełnej). Niech
     
    wtedy
    •   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.
    Zatem dla każdego   jeśli   jest prawdziwe, to   jest prawdziwe. Z zasady indukcji matematycznej (niezupełnej)   jest prawdziwe dla wszystkich   Dlatego
      i   i … i   są prawdziwe dla wszystkich  
    co kończy dowód.
  5. Można się o tym łatwo przekonać podstawiając   dla   i korzystając z zasady indukcji matematycznej (niezupełnej) dla   w miejsce