Indukcja matematyczna – metoda:

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.

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[uwaga 1]; podał go Francesco Maurolico w pracy Arithmeticorum libri duo (Dwie księgi o arytmetyce) z 1575 roku[3].

Wprowadzenie

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 ale nie jest to dowodem[uwaga 2]. 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

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ą [uwaga 3]. 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

Suma początkowych liczb naturalnych
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
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
Stąd

Indukcja zupełna

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ą [uwaga 3]. Zakładając, że
  • jest prawdziwe,
  • dla wszystkich jeśli są prawdziwe, to jest prawdziwe,
otrzymuje się prawdziwość dla wszystkich [uwaga 4].

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ą [uwaga 3]. Można dowieść stwierdzenia
dla każdego jest
zapewniając, że
  • jest prawdziwe,
  • dla wszystkich jeśli są prawdziwe, to jest prawdziwe.

Inne warianty

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[uwaga 5].

Istnieje również podobna modyfikacja zasady indukcji zupełnej.

Indukcja wsteczna
Niech oznacza pewne stwierdzenie dotyczące liczby naturalnej [uwaga 3]. 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?

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

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ż

Uwagi

  1. Równość jest prawdziwa dla wszystkich (zob. liczby kwadratowe).
  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. 1 2 3 4 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

Przypisy

  1. 1 2 indukcja matematyczna, [w:] Encyklopedia PWN [dostęp 2024-03-19].
  2. Michał Tarnowski, Reguła znaków Kartezjusza, [w:] pismo „Delta”, deltami.edu.pl, czerwiec 2023, ISSN 0137-3005 [dostęp 2024-03-19] (pol.).
  3. publikacja w otwartym dostępie – możesz ją przeczytać Biografia Maurolico, Francesco, Wydział Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego, wazniak.mimuw.edu.pl [dostęp 2024-03-19].

Linki zewnętrzne

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.