Indukcja matematyczna - Mathematical induction

Indukcję matematyczną można nieformalnie zilustrować przez odniesienie do sekwencyjnego efektu spadających kostek domina .

Indukcja matematyczna jest techniką dowodu matematycznego . Zasadniczo służy do udowodnienia, że ​​zdanie P ( n ) zachodzi dla każdej liczby naturalnej n  = 0, 1, 2, 3, . . . ; to znaczy, że ogólne stwierdzenie jest ciągiem nieskończenie wielu przypadków P (0), P (1), P (2), P (3), . . . . Nieformalne metafory pomagają wyjaśnić tę technikę, na przykład spadające domino lub wspinanie się po drabinie:

Indukcja matematyczna udowadnia, że ​​po drabinie możemy wspinać się tak wysoko, jak nam się podoba, udowadniając, że możemy wspiąć się na najniższy szczebel ( podstawa ) i że z każdego szczebla możemy wspiąć się na kolejny ( stopień ).

—  Matematyka konkretna , strona 3 na marginesach.

Dowód przez indukcję składa się z dwóch przypadkach. Pierwszego, przypadek podstawy (albo podstawa ), dowodzi instrukcję dla n = 0, bez podjęcia jakiegokolwiek wiedzy innych przypadkach. Drugim przypadku, krok indukcyjny , dowodzi, że jeśli oświadczenie odnosi się do danego przypadku n = k , wówczas musi on również posiadać do następnego przypadku  n = k + 1. Te dwa kroki ustalenia, że oświadczenie zachodzi dla każdej liczby naturalnej n . Przypadek bazowy niekoniecznie zaczyna się od n = 0, ale często od n = 1 i prawdopodobnie od dowolnej ustalonej liczby naturalnej n = N , ustalając prawdziwość zdania dla wszystkich liczb naturalnych n ≥ N .

Metodę można rozszerzyć, aby udowodnić stwierdzenia dotyczące bardziej ogólnych, dobrze ugruntowanych struktur, takich jak drzewa ; to uogólnienie, znane jako indukcja strukturalna , jest stosowane w logice matematycznej i informatyce . Indukcja matematyczna w tym rozszerzonym sensie jest ściśle związana z rekurencją . Indukcja matematyczna jest regułą wnioskowania stosowaną w dowodach formalnych i jest podstawą większości dowodów poprawności programów komputerowych.

Chociaż jej nazwa może sugerować inaczej, indukcji matematycznej nie należy mylić z rozumowaniem indukcyjnym stosowanym w filozofii (patrz Problem indukcji ). Metoda matematyczna bada nieskończenie wiele przypadków, aby udowodnić ogólne stwierdzenie, ale robi to za pomocą skończonego łańcucha rozumowania dedukcyjnego obejmującego zmienną n , która może przyjmować nieskończenie wiele wartości.

Historia

W 370 BC Plato jest Parmenides mogły zawierać wczesny przykład niejawny dowodu indukcyjnego. Odwrotna, powtarzana technika, odliczanie w dół, a nie w górę, znajduje się w paradoksie sorytów , w którym argumentowano, że jeśli 1 000 000 ziaren piasku utworzy kupę, a usunięcie jednego ziarna z kupy pozostawi kupę, to pojedyncze ziarnko piasku (lub nawet bez ziaren) tworzy kupę.

W Indiach wcześnie ukryte dowody by indukcji matematycznej pojawiają się Bhaskara «„s metody cyklicznego », aw al-Fakhri napisany przez al-Karaji około 1000 roku, który zgłosił go do arytmetycznych sekwencji udowodnić dwumianowego twierdzenia i właściwości Trójkąt Pascala .

Żaden z tych starożytnych matematyków nie postawił jednak wprost hipotezy indukcyjnej. Innym podobnym przypadkiem (w przeciwieństwie do tego, co napisał Vacca, jak ostrożnie wykazał Freudenthal) był przypadek Francesco Maurolico w swoim duecie Arithmeticorum libri (1575), który użył tej techniki, aby udowodnić, że suma pierwszych n nieparzystych liczb całkowitych wynosi n 2 .

Najwcześniej rygorystycznie stosował indukcję Gersonides (1288-1344). Pierwsze wyraźne sformułowanie zasady indukcji zostało podane przez Pascala w jego Traité du triangle aithmétique (1665). Inny Francuz, Fermat , wykorzystał pokrewną zasadę: dowód pośredni przez nieskończone pochodzenie .

Hipoteza indukcyjna została również zastosowana przez Szwajcara Jakoba Bernoulliego i od tego czasu stała się dobrze znana. Nowoczesne formalne potraktowanie tej zasady pojawiło się dopiero w XIX wieku za sprawą George'a Boole'a , Augustusa de Morgana , Charlesa Sandersa Peirce'a , Giuseppe Peano i Richarda Dedekinda .

Opis

Najprostsza i najpowszechniejsza forma indukcji matematycznej zakłada, że ​​zdanie zawierające liczbę naturalną n (czyli liczbę całkowitą n ≥ 0 lub 1) obowiązuje dla wszystkich wartości n . Dowód składa się z dwóch kroków:

  1. Początkowy lub baza sprawa : udowodnić, że oświadczenie odnosi się do 0 lub 1.
  2. Krok indukcyjny , krok indukcyjny , czy krok przypadek : udowodnić, że dla każdego n , jeżeli oświadczenie odnosi się do n , a następnie przechowuje to dla n + 1 . Innymi słowy, załóżmy, że zdanie jest prawdziwe dla pewnej dowolnej liczby naturalnej n i udowodnij, że to zdanie jest prawdziwe dla n + 1 .

Hipoteza w kroku indukcyjnym, którą zdanie obowiązuje dla określonego n , nazywa się hipotezą indukcyjną lub hipotezą indukcyjną . Aby udowodnić krok indukcyjny, zakłada się hipotezę indukcyjną dla n, a następnie wykorzystuje to założenie, aby udowodnić, że zdanie jest prawdziwe dla n + 1 .

Autorzy, którzy wolą definiować liczby naturalne, aby zaczynały się od 0, używają tej wartości w przypadku podstawowym; ci, którzy definiują liczby naturalne na początku od 1, używają tej wartości.

Przykłady

Suma kolejnych liczb naturalnych

Indukcję matematyczną można wykorzystać do udowodnienia następującego zdania P ( n ) dla wszystkich liczb naturalnych n .

Stanowi to ogólny wzór na sumę liczb naturalnych mniejszych lub równych danej liczbie; w rzeczywistości nieskończony ciąg stwierdzeń: , , , itd.

Propozycja. Dla każdego,

Dowód. Niech P ( n ) będzie stwierdzeniem Dajemy dowód przez indukcję na n .

Przypadek bazowy : pokaż, że instrukcja obowiązuje dla najmniejszej liczby naturalnej n = 0.

P (0) jest oczywiście prawdziwe:

Krok indukcyjny : Pokaż, że dla dowolnego k ≥ 0, jeśli P ( k ) jestspełniony, wtedy P ( k +1) również jestspełniony.

Przyjmuje się hipotezy, że dla indukcji określonego K , w przypadku pojedynczego n = K posiada, co oznacza P ( k ) jest spełniony:

Wynika, że:

Algebraicznie prawa strona upraszcza się jako:

Porównując skrajnie lewą i prawą stronę, wnioskujemy, że:

Oznacza to, że zdanie P ( k + 1) również jest prawdziwe, ustanawiając krok indukcyjny.

Wniosek : Ponieważ zarówno przypadek bazowy, jak i krok indukcyjny zostały udowodnione jako prawdziwe, dzięki indukcji matematycznej zdanie P ( n ) obowiązuje dla każdej liczby naturalnej n .

Nierówność trygonometryczna

Indukcję często stosuje się do udowodnienia nierówności. Jako przykład dowodzimy, że dla dowolnej liczby rzeczywistej i naturalnej .

Na pierwszy rzut oka może się wydawać, że bardziej ogólną wersję, dla dowolnych liczb rzeczywistych , można by udowodnić bez indukcji; ale przypadek pokazuje, że może to być fałsz dla wartości niecałkowitych . Sugeruje to, że zbadamy to stwierdzenie specjalnie pod kątem naturalnych wartości , a indukcja jest najłatwiejszym narzędziem.

Propozycja . Dla każdego, .

Dowód. Ustal dowolną liczbę rzeczywistą i niech będzie stwierdzeniem . Wprowadzamy na .

Przypadek podstawowy: Obliczenieweryfikuje.

Krok indukcyjny: pokazujemy implikacjedla dowolnej liczby naturalnej. Załóżmy hipotezę indukcyjną: dla danej wartościpojedynczy przypadekjest prawdziwy. Korzystając ze wzoru dodawania kątów i nierówności trójkąta , wyprowadzamy:

Nierówność między skrajnymi wielkościami lewej i prawej strony pokazuje, że to prawda, co kończy krok indukcyjny.

Wniosek : To twierdzenie obowiązujedla wszystkich liczb naturalnych. ∎

Warianty

W praktyce dowody indukcyjne często mają różną strukturę, w zależności od dokładnego charakteru właściwości, która ma być udowodniona. Wszystkie warianty indukcji są szczególnymi przypadkami indukcji pozaskończonej; patrz poniżej .

Podstawa indukcji inna niż 0 lub 1

Jeśli chce się udowodnić twierdzenie nie dla wszystkich liczb naturalnych, ale tylko dla wszystkich liczb n większych lub równych pewnej liczbie b , to dowód przez indukcję składa się z:

  1. Pokazanie, że instrukcja jest aktualna, gdy n = b .
  2. Pokazanie, że jeśli zdanie obowiązuje dla dowolnej liczby nb , to to samo zdanie obowiązuje również dla n + 1 .

Można to wykorzystać na przykład do wykazania, że 2 nn + 5 dla n ≥ 3 .

W ten sposób można udowodnić, że pewne zdanie P ( n ) obowiązuje dla wszystkich n ≥ 1 , a nawet dla wszystkich n ≥ −5 . Ta forma indukcji matematycznej jest w rzeczywistości szczególnym przypadkiem poprzedniej formy, ponieważ jeśli twierdzeniem, które ma być udowodnione jest P ( n ), to udowodnienie tego za pomocą tych dwóch reguł jest równoważne udowodnieniu P ( n + b ) dla wszystkich liczb naturalnych n z obudowa indukcyjna 0 .

Przykład: tworzenie kwot w dolarach za pomocą monet

Załóż nieskończoną ilość monet o wartości 4 i 5 dolarów. Indukcję można wykorzystać do udowodnienia, że ​​dowolna suma dolarów większa lub równa 12 może zostać utworzona przez połączenie takich monet. Niech S ( k ) oznacza zdanie „ k dolarów może powstać z kombinacji monet 4- i 5-dolarowych ”. Dowód, że S ( k ) jest prawdziwy dla wszystkich k ≥ 12 można wtedy uzyskać przez indukcję na k w następujący sposób:

Przypadek podstawowy : Pokazanie, że S ( k ) utrzymuje się dla k = 12 jest proste: weź trzy 4-dolarowe monety.

Krok indukcji : Zakładając, że S ( k ) zachodzi dla pewnej wartości k ≥ 12 ( hipoteza indukcyjna ), udowodnij, że S ( k + 1) również zachodzi:

Załóżmy, że S ( k ) jest prawdziwe dla pewnego dowolnego k ≥12 . Jeśli istnieje rozwiązanie dla k dolarów, które zawiera co najmniej jedną monetę 4 dolarową, zastąp ją monetą 5 dolarową, aby uzyskać k + 1 dolar. W przeciwnym razie, jeśli używane są tylko monety 5-dolarowe, k musi być wielokrotnością 5, a więc co najmniej 15; ale wtedy możemy zastąpić trzy monety 5-dolarowe czterema monetami 4-dolarowymi, aby uzyskać k + 1 dolar. W każdym przypadku S ( k + 1) jest prawdziwe.

Zatem, zgodnie z zasadą indukcji, S ( k ) obowiązuje dla wszystkich k ≥ 12 , a dowód jest kompletny.

W tym przykładzie, chociaż S ( k ) również obowiązuje dla , powyższego dowodu nie można zmodyfikować, aby zastąpić minimalną kwotę 12 dolarów jakąkolwiek niższą wartością m . Dla m = 11 przypadek podstawowy jest w rzeczywistości fałszywy; dla m = 10 , drugi przypadek w kroku indukcji (zastąpienie trzech monet 5- przez cztery 4-dolarowe) nie zadziała; nie mówiąc już o jeszcze niższych m .

Indukcja na więcej niż jednym blacie

Czasami pożądane jest udowodnienie twierdzenia obejmującego dwie liczby naturalne, n i m , poprzez iterację procesu indukcji. Oznacza to, że jeden dowodzi przypadku bazowego i kroku indukcyjnego dla n , aw każdym z nich dowodzi przypadku bazowego i kroku indukcyjnego dla m . Zobacz na przykład dowód przemienności towarzyszący dodawaniu liczb naturalnych . Możliwe są również bardziej skomplikowane argumenty obejmujące trzy lub więcej liczników.

Nieskończone zejście

Metoda nieskończonego schodzenia jest odmianą indukcji matematycznej, którą zastosował Pierre de Fermat . Służy do wykazania, że ​​pewne zdanie Q ( n ) jest fałszywe dla wszystkich liczb naturalnych n . Jej tradycyjna forma polega na wykazaniu, że jeśli Q ( n ) jest prawdziwe dla pewnej liczby naturalnej n , to obowiązuje również dla pewnej ściśle mniejszej liczby naturalnej m . Ponieważ nie ma nieskończenie malejących ciągów liczb naturalnych, taka sytuacja byłaby niemożliwa, pokazując w ten sposób (przez sprzeczność), że Q ( n ) nie może być prawdziwe dla żadnego n .

Ważność tej metody można zweryfikować na podstawie zwykłej zasady indukcji matematycznej. Stosując indukcję matematyczną na zdaniu P ( n ) zdefiniowanym jako „ Q ( m ) jest fałszywe dla wszystkich liczb naturalnych m mniejszych lub równych n ”, wynika z tego, że P ( n ) zachodzi dla wszystkich n , co oznacza, że Q ( n ) jest fałszywe dla każdej liczby naturalnej n .

Indukcja przedrostka

Najpopularniejsza forma dowodu za pomocą indukcji matematycznej wymaga udowodnienia na etapie indukcyjnym, że

po czym zasada indukcji "automatyzuje" n zastosowań tego kroku w przechodzeniu od P (0) do P ( n ). Można to nazwać „indukcją poprzednika”, ponieważ każdy krok dowodzi czegoś o liczbie od czegoś o poprzedniku tej liczby.

Wariantem zainteresowania złożonością obliczeniową jest „indukcja przedrostkowa”, w której w kroku indukcyjnym udowadnia się następujące stwierdzenie:

lub równoważnie

Zasada indukcji następnie „automatyzuje” logowanie n zastosowań tego wnioskowania przy uzyskiwaniu od P (0) do P ( n ). W rzeczywistości nazywa się to „indukcją przedrostka”, ponieważ każdy krok dowodzi czegoś o liczbie z czegoś o „przedrostku” tej liczby — utworzonej przez obcięcie młodszego bitu jej reprezentacji binarnej. Można to również postrzegać jako zastosowanie tradycyjnej indukcji na długości tej reprezentacji binarnej.

Jeśli tradycyjna indukcja poprzedników jest interpretowana obliczeniowo jako pętla n- krokowa, to indukcja przedrostkowa odpowiadałaby pętli log- n- krokowej. Z tego powodu dowody wykorzystujące indukcję przedrostkową są „bardziej wykonalne konstruktywne” niż dowody wykorzystujące indukcję poprzedników.

Indukcja poprzednika może w trywialny sposób symulować indukcję przedrostka na tym samym zdaniu. Indukcja przedrostków może symulować indukcję poprzedników, ale tylko kosztem uczynienia zdania bardziej złożonym składniowo (dodanie ograniczonego uniwersalnego kwantyfikatora ), więc interesujące wyniki dotyczące indukcji przedrostków z obliczeniami w czasie wielomianowym zależą od całkowitego wykluczenia kwantyfikatorów nieograniczonych i ograniczenia alternatywy ograniczonych kwantyfikatorów uniwersalnych i egzystencjalnych dozwolonych w stwierdzeniu.

Można pójść o krok dalej: trzeba udowodnić

po czym zasada indukcji "automatyzuje" log log n zastosowania tego wnioskowania w uzyskiwaniu od P (0) do P ( n ). Ta forma indukcji została wykorzystana analogicznie do badania obliczeń równoległych w czasie logarytmicznym.

Pełna (silna) indukcja

Inny wariant, zwany indukcji zupełnej , przebieg wartości indukcji lub silnej indukcji (w przeciwieństwie do którego podstawową formą indukcji jest czasami znany jako słabą indukcję ), sprawia, że krok indukcyjny łatwiej udowodnić za pomocą silniejszego hipotezy: jedna dowodzi oświadczenie pod założenie, które obowiązuje dla wszystkich liczb naturalnych mniejszych niż ; natomiast podstawowa forma zakłada jedynie . Nazwa „silna indukcja” nie oznacza, że ​​metoda ta może dowieść czegoś więcej niż „słaba indukcja”, a jedynie odnosi się do silniejszej hipotezy zastosowanej w etapie indukcyjnym.

W rzeczywistości można wykazać, że te dwie metody są w rzeczywistości równoważne, jak wyjaśniono poniżej. W tej formie pełnej indukcji nadal trzeba udowodnić przypadek bazowy , a nawet może być konieczne udowodnienie przypadków ekstra-bazowych, tak jak przed zastosowaniem ogólnego argumentu, jak w poniższym przykładzie liczby Fibonacciego .

Chociaż opisana właśnie forma wymaga udowodnienia przypadku bazowego, nie jest to konieczne, jeśli można udowodnić (zakładając dla wszystkich niższe ) dla wszystkich . Jest to szczególny przypadek indukcji pozaskończonej, jak opisano poniżej, chociaż nie jest już równoważny ze zwykłą indukcją. W tej formie przypadek bazowy jest podciągnięty przez przypadek , gdzie jest udowodniony bez innych założonych; ten przypadek może wymagać oddzielnego potraktowania, ale czasami ten sam argument dotyczy i , dzięki czemu dowód jest prostszy i bardziej elegancki. W metodzie tej należy jednak zadbać o to, aby dowód nie zakładał w sposób dorozumiany, że , np. mówiąc „wybierz dowolny ” lub zakładając, że zbiór m elementów ma element.

Indukcja zupełna jest równoważna ze zwykłą indukcją matematyczną, jak opisano powyżej, w tym sensie, że dowód za pomocą jednej metody może zostać przekształcony w dowód za pomocą drugiej. Załóżmy, że istnieje dowód przez całkowitą indukcję. Niech oznacza „ dotyczy wszystkich takich, które ”. Wtedy obowiązuje dla wszystkich wtedy i tylko wtedy, gdy obowiązuje dla wszystkich , a nasz dowód jest łatwo przekształcany w dowód przez (zwykłą) indukcję. Gdyby natomiast udowodnił zwykłą indukcję, dowód byłby już skutecznie jednym przez indukcję zupełną: jest udowodniony w przypadku bazowym, bez żadnych założeń, i jest udowodniony w kroku indukcyjnym, w którym można założyć wszystkie wcześniejszych przypadkach, ale wystarczy użyć przypadku .

Przykład: liczby Fibonacciego

Pełna indukcja jest najbardziej użyteczna, gdy dla każdego kroku indukcyjnego wymaganych jest kilka wystąpień hipotezy indukcyjnej. Na przykład pełna indukcja może być użyta do wykazania, że

gdzie jest n p liczbę Fibonacciego , (The złotego ) i są pierwiastkami wielomianu . Korzystając z faktu, że dla każdego , powyższa tożsamość może być zweryfikowana przez bezpośrednie obliczenie, jeśli założymy, że już obowiązuje dla obu i . W celu uzupełnienia dowodu tożsamość musi zostać zweryfikowana w dwóch przypadkach podstawowych: i .

Przykład: rozkład na czynniki pierwsze

Inny dowód, oparty na całkowitej indukcji, wykorzystuje hipotezę, że zdanie dotyczy wszystkich mniejszych dokładniej. Rozważmy stwierdzenie, że „każda liczba naturalna większa niż 1 jest iloczynem (jednej lub więcej) liczb pierwszych ”, co jest częścią „ istnieniapodstawowego twierdzenia arytmetyki . Aby udowodnić krok indukcyjny, hipoteza indukcyjna jest taka, że ​​dla danego stwierdzenia obowiązuje dla wszystkich mniejszych . Jeśli jest liczbą pierwszą, to z pewnością jest iloczynem liczb pierwszych, a jeśli nie, to z definicji jest iloczynem: , gdzie żaden z czynników nie jest równy 1; stąd żaden nie jest równy , a więc oba są większe niż 1 i mniejsze niż . Hipoteza indukcyjna ma teraz zastosowanie do i , więc każda z nich jest iloczynem liczb pierwszych. Jest to więc iloczyn iloczynów liczb pierwszych, a zatem sam iloczyn liczb pierwszych.

Przykład: ponowne sprawdzenie kwot w dolarach

Postaramy się udowodnić ten sam przykład co powyżej , tym razem z silną indukcją . Oświadczenie pozostaje takie samo:

Pojawią się jednak niewielkie różnice w konstrukcji i założeniach dowodu, zaczynając od rozszerzonego przypadku bazowego:

Przypadek podstawowy : Pokaż, że obowiązuje dla .

Sprawa podstawowa trzyma.

Hipoteza indukcyjna : Biorąc pod uwagę niektóre , załóżmy, że obowiązuje dla wszystkich z .

Krok indukcyjny : udowodnij, że się trzyma.

Wybór i obserwowanie tego pokazuje, że jest to zgodne z hipotezą indukcyjną. Oznacza to, że suma może być utworzona przez pewną kombinację monet i monet dolarowych. Następnie dodanie monety dolara do tej kombinacji daje sumę . To znaczy trzyma. CO BYŁO DO OKAZANIA

Indukcja przód-tył

Czasami wygodniej jest wydedukować wstecz, udowadniając twierdzenie dla , biorąc pod uwagę jego ważność dla . Jednak udowodnienie słuszności twierdzenia dla żadnej liczby nie wystarczy do ustalenia przypadku bazowego; zamiast tego trzeba udowodnić twierdzenie dla nieskończonego podzbioru liczb naturalnych. Na przykład Augustin Louis Cauchy najpierw zastosował indukcję postępującą (zwykłą), aby udowodnić nierówność średnich arytmetycznych i geometrycznych dla wszystkich potęg 2, a następnie użył indukcji wstecznej, aby pokazać ją dla wszystkich liczb naturalnych.

Przykład błędu w kroku indukcyjnym

Krok indukcyjny musi być udowodniony dla wszystkich wartości n . Aby to zilustrować, Joel E. Cohen zaproponował następujący argument, który ma dowodzić za pomocą indukcji matematycznej, że wszystkie konie są tego samego koloru :

  • Przypadek podstawowy: W zestawie tylko jednego konia występuje tylko jeden kolor.
  • Krok indukcyjny: załóż jako hipotezę indukcyjną, że w dowolnym zestawie koni występuje tylko jeden kolor. Teraz spójrz na dowolny zestaw koni. Ponumeruj je: . Rozważ zestawy i . Każdy to zestaw samych koni, dlatego w każdym jest tylko jeden kolor. Ale te dwa zestawy zachodzą na siebie, więc wśród wszystkich koni musi być tylko jeden kolor .

Przypadek podstawowy jest trywialny (ponieważ każdy koń ma taki sam kolor jak on sam), a krok indukcyjny jest poprawny we wszystkich przypadkach . Jednak logika kroku indukcyjnego jest nieprawidłowa dla , ponieważ stwierdzenie, że „dwa zestawy nakładają się” jest fałszywe (są tylko konie przed usunięciem i po usunięciu, zestawy po jednym koniu nie nakładają się).

Formalizowanie

W logice drugiego rzęduaksjomat indukcji” można zapisać następująco:

,

gdzie P (.) jest zmienną dla predykatów zawierających jedną liczbę naturalną, a k i n są zmiennymi dla liczb naturalnych .

Mówiąc słownie, przypadek bazowy P (0) i krok indukcyjny (czyli hipoteza indukcyjna P ( k ) implikuje P ( k + 1) ) razem implikują, że P ( n ) dla dowolnej liczby naturalnej n . Aksjomat indukcji potwierdza słuszność wnioskowania, że P ( n ) zachodzi dla dowolnej liczby naturalnej n z przypadku bazowego i kroku indukcyjnego.

Pierwszy kwantyfikator w aksjomatach obejmuje predykaty, a nie pojedyncze liczby. Jest to kwantyfikator drugiego rzędu, co oznacza, że ​​ten aksjomat jest sformułowany w logice drugiego rzędu . Aksjomatyzacja indukcji arytmetycznej w logice pierwszego rzędu wymaga schematu aksjomatu zawierającego oddzielny aksjomat dla każdego możliwego predykatu. Artykuł Aksjomaty Peano zawiera dalsze omówienie tego zagadnienia.

Aksjomat indukcji strukturalnej dla liczb naturalnych został po raz pierwszy sformułowany przez Peano, który użył go do określenia liczb naturalnych wraz z następującymi czterema innymi aksjomatami:

  1. 0 to liczba naturalna.
  2. Funkcja następnika s każdej liczby naturalnej daje liczbę naturalną ( s ( x ) = x + 1 ) .
  3. Funkcja następnika jest iniektywna.
  4. 0 nie jest w zakresie od s .

W teorii mnogości ZFC pierwszego rzędu kwantyfikacja po predykatach nie jest dozwolona, ​​ale nadal można wyrazić indukcję przez kwantyfikację po zbiorach:

A może być odczytywane jako zbiór reprezentujący zdanie i zawierający liczby naturalne, dla których zdanie to obowiązuje. Nie jest to aksjomat, ale twierdzenie, biorąc pod uwagę, że liczby naturalne są definiowane w języku teorii mnogości ZFC za pomocą aksjomatów, analogicznych do aksjomatów Peano.

Indukcja nieskończona

Jedna odmiana zasady całkowitej indukcji może być uogólniona dla stwierdzeń o elementach dowolnego dobrze ugruntowanego zbioru , to znaczy zbioru z niezwrotną relacją < , który nie zawiera nieskończonych łańcuchów malejących . Każdy zbiór reprezentujący liczbę porządkową jest dobrze ugruntowany, jednym z nich jest zbiór liczb naturalnych.

W przypadku dobrze ugruntowanego zbioru indukcję pozaskończoną można sformułować jako jednoetapową. Aby udowodnić, że dla każdej liczby porządkowej obowiązuje zdanie P ( n ) :

  1. Pokaż, dla każdej liczby porządkowej n , że jeśli P ( m ) zachodzi dla wszystkich m < n , to P ( n ) również obowiązuje.

Ta forma indukcji, po zastosowaniu do zbioru liczb porządkowych (które tworzą dobrze uporządkowaną, a zatem dobrze ugruntowaną klasę), nazywa się indukcją pozaskończoną . Jest to ważna technika dowodowa w teorii mnogości , topologii i innych dziedzinach.

Dowody przez indukcję pozaskończoną zazwyczaj wyróżniają trzy przypadki:

  1. gdy n jest elementem minimalnym, tzn. nie ma elementu mniejszego niż n ;
  2. gdy n ma bezpośredniego poprzednika, tzn. zbiór elementów mniejszych od n ma element największy;
  3. gdy n nie ma bezpośredniego poprzednika, tj. n jest tak zwaną liczbą porządkową graniczną .

Ściśle mówiąc, w indukcji nieskończonej nie jest konieczne dowodzenie przypadku podstawowego, ponieważ jest to bezsensowny przypadek szczególny twierdzenia, że ​​jeśli P jest prawdziwe dla wszystkich n < m , to P jest prawdziwe dla m . Jest to bezsensownie prawdziwe właśnie dlatego, że nie ma wartości n < m, które mogłyby służyć jako kontrprzykłady. Tak więc przypadki specjalne są szczególnymi przypadkami przypadku ogólnego.

Związek z zasadą dobrego uporządkowania

Zasada indukcji matematycznej jest zwykle określana jako aksjomat liczb naturalnych; zobacz aksjomaty Peano . Jest ściśle silniejsza niż zasada dobrego uporządkowania w kontekście innych aksjomatów Peano. Załóżmy, że:

  • Trychotomia Aksjomat: Dla każdej liczby naturalne n i m , n jest mniejszy niż lub równy m , wtedy i tylko wtedy, gdy m jest nie mniejsza niż n .
  • Dla każdej liczby naturalne n , n + 1 jest większe niż n .
  • Dla dowolnej liczby naturalnej n , żadna liczba naturalna nie mieści się w przedziale od n do n + 1 .
  • Żadna liczba naturalna nie jest mniejsza od zera.

Można wtedy dowieść, że indukcja, biorąc pod uwagę wyżej wymienione aksjomaty, implikuje zasadę dobrego uporządkowania. Poniższy dowód używa pełnej indukcji oraz aksjomatów pierwszego i czwartego.

Dowód. Załóżmy, że istnieje niepusty zbiór S liczb naturalnych, który nie ma najmniejszego elementu. Niech P ( n ) jest stwierdzenie, że n nie jest S . Wtedy P (0) jest prawdziwe, bo gdyby było fałszywe, to 0 jest najmniejszym elementem S . Co więcej, niech n będzie liczbą naturalną i załóżmy, że P ( m ) jest prawdziwe dla wszystkich liczb naturalnych m mniejszych niż n + 1 . Wtedy, jeśli P ( n + 1) jest fałszywe, n + 1 jest w S , a zatem jest minimalnym elementem w S , sprzeczność. Zatem P ( n + 1) jest prawdziwe. Zatem, zgodnie z zasadą całkowitej indukcji, P ( n ) obowiązuje dla wszystkich liczb naturalnych n ; więc S jest puste, sprzeczność. CO BYŁO DO OKAZANIA

" Ilość linii " dla zestawu {(0, n ) n ∈ ℕ}{(1 n ) n ∈ ℕ} . Liczby odnoszą się do drugiego składnika par; pierwszy można uzyskać z koloru lub lokalizacji.

Z drugiej strony zbiór {(0, n ): n ∈ ℕ} ∪ {(1, n ): n ∈ ℕ} , pokazany na rysunku, jest uporządkowany według porządku leksykograficznego . Ponadto, z wyjątkiem aksjomatu indukcyjnego, spełnia on wszystkie aksjomaty Peano, gdzie stała Peano 0 jest interpretowana jako para (0,0), a funkcja następcy Peano jest zdefiniowana na parach przez succ ( x , n ) = ( x , n + 1) dla wszystkich x {0,1} i n ∈ℕ. Jako przykład naruszenia aksjomatowi indukcji określenie źródłowe P ( x , n ) jako ( x , n ) = (0, 0) i ( x , n ) = ( succ ( Y , m )) przez pewien y ∈{0,1} i m ∈ℕ. Wtedy przypadek bazowy P (0,0) jest trywialnie prawdziwy, podobnie jak przypadek krokowy: jeśli P ( x , n ) , to P ( succ ( x , n ) ) . Jednak P nie jest prawdziwe dla wszystkich par w zestawie.

Aksjomaty Peano z zasadą indukcji w unikalny sposób modelują liczby naturalne. Zastąpienie zasady indukcji zasadą dobrego uporządkowania pozwala na bardziej egzotyczne modele, które spełniają wszystkie aksjomaty.

W kilku książkach i źródłach błędnie wydrukowano, że zasada dobrego uporządkowania jest równoważna aksjomatowi indukcji. W kontekście innych aksjomatów Peano tak nie jest, ale w kontekście innych aksjomatów są one równoważne; w szczególności zasada dobrego uporządkowania implikuje aksjomat indukcji w kontekście pierwszych dwóch wymienionych powyżej aksjomatów i

  • Każda liczba naturalna to albo 0 albo n + 1 dla jakiejś liczby naturalnej n .

Częstym błędem w wielu błędnych dowodach jest założenie, że n − 1 jest unikalną i dobrze zdefiniowaną liczbą naturalną, właściwością, która nie jest implikowana przez inne aksjomaty Peano.

Zobacz też

Uwagi

Bibliografia

Wstęp

Historia