Przejdź do zawartości

Indukcja matematyczna

Z Wikipedii, wolnej encyklopedii

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[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]
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[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ż: liczby trójkątne.
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ż: 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
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ż: indukcja wsteczna.
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]
 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, 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]
 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 | edytuj kod]
  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. 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.
  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

[edytuj | edytuj kod]
  1. a b indukcja matematyczna, [w:] Encyklopedia PWN [online], Wydawnictwo Naukowe PWN [dostęp 2024-03-19].
  2. Michał Tarnowski, Reguła znaków Kartezjusza, „Delta”, czerwiec 2023, ISSN 0137-3005 [dostęp 2024-03-19].
  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

[edytuj | edytuj kod]