Indukcja matematyczna

W matematyce, termin indukcja matematyczna używany jest na określenie szczególnej metody dowodzenia twierdzeń (w najbardziej typowych przypadkach o liczbach naturalnych), ale także jest on używany na oznaczenie konstrukcji pewnych obiektów.

Wbrew nazwie, argumenty oparte na indukcji matematycznej nie są rozumowaniami indukcyjnymi, lecz dedukcyjnymi. Najstarszy znany dowód indukcyjny był podany przez Francesco Maurolico w pracy Arithmeticorum libri fuo w 1575. Maurolico udowodnił przez indukcję, że suma pierwszych n nieparzystych liczb naturalnych wynosi $n^2$.

Intuicje

Efekt domina

Zarówno definicje indukcyjne jak i twierdzenie o indukcji matematycznej można porównać do rozumowań krok po kroku, gdzie kroki są ponumerowane liczbami naturalnymi. Sedno dowodów indukcyjnych leży w uzasadnieniu, że w pierwszym kroku dane stwierdzenie jest prawdziwe, oraz że dla każdego $n\in {\mathbb N}$ z prawdziwości twierdzenia dla kroku n wynika prawdziwość twierdzenia dla kroku n+1.

Często używaną ilustracją dla tego typu argumentacji jest efekt domina. Wyobraźmy sobie że ustawiliśmy szereg kamieni używanych do gry w domino tak, że stoją one jeden za drugim na krótszym boku. Musimy się upewnić, że popchnięcie jednego kamienia spowoduje jego przewrócenie, oraz zakładamy że dowolna ilość kamieni ustawiona jeden za drugim przewróci się po popchnięciu pierwszego z nich. Możemy teraz udowodnić dowodząc krok indukcyjny, że szereg powiększony o jedną kostkę dostawioną na końcu także się przewróci.

Twierdzenia o indukcji matematycznej

Następujące twierdzenia są natychmiastową konsekwencją bardzo intuicyjnej własności liczb naturalnych, stwierdzającej że w każdym niepustym zbiorze liczb naturalnych jest liczba najmniejsza.

Wersja podstawowa

Przypuśćmy, że $P(n)$ jest pewnym wyrażeniem (czyli formułą w jakimś języku) w którym jedyną zmienną wolną jest $n$ i dziedzina tej zmiennej zawiera wszystkie liczby naturalne. Załóżmy, że

(a) $P(1)$ jest zdaniem prawdziwym oraz

(b) dla każdego $n\in \mathbb N$ zachodzi implikacja

$P(n)\quad \implies \quad P(n+1)$.

Wówczas $P(n)$ jest prawdziwe dla każdej liczby naturalnej $n\in \mathbb N$.

Wariant zwany indukcją zupełną

Przypuśćmy, że $P(n)$ jest pewnym wyrażeniem, w którym jedyną zmienną wolną jest $n$ i dziedzina tej zmiennej zawiera wszystkie liczby naturalne. Załóżmy, że

(c) dla każdej liczby naturalnej $n\in \mathbb N$ zachodzi implikacja

$(\forall m<n)(P(m))\quad \implies \quad P(n)$.

Wówczas $P(n)$ jest prawdziwe dla każdego $n\in \mathbb N$.

Aksjomat czy twierdzenie?

Powyżej używaliśmy określenia Twierdzenie o Indukcji, ale w wielu źródłach można spotkać określenie Aksjomat Indukcji. Jaki jest więc rzeczywisty status indukcji: jest to twierdzenie czy też aksjomat? Odpowiedź na to pytanie zależy od kontekstu w którym jest ono stawiane.

W matematyce elementarnej, zastosowaniach matematyki czy też w matematyce dyskretnej dominuje tendencja do mówienia o Twierdzeniu o Indukcji Matematycznej, także z tego powodu, że w tych rozważaniach unika się przesadnej formalizacji. Często wprowadzając indukcję matematyczną podaje się wówczas dowód twierdzenia o indukcji przy założeniu dobrego uporządkowania liczb naturalnych (tzn zakładając, że każdy niepusty podzbiór zbioru liczb naturalnych zawiera element najmniejszy).

W logice, natomiast, (szczególnie gdy liczby naturalne są wprowadzane w oparciu o aksjomatykę Peano), traktujemy indukcję jako aksjomat (jeden z aksjomatów arytmetyki Peano). Zwykle chcemy aby rozwijana teoria była sformalizowana w logice pierwszego rzędu - w tym wypadku mamy do czynienia nie z jednym aksjomatem, ale z nieskończoną listą aksjomatów (indeksowanych formułami). Tak więc dla każdej formuły $\Phi$ wprowadzamy następujący aksjomat:

$\Big(\Phi(0)\ \wedge\ \big(\forall x\big)\big(\Phi(x)\ \Rightarrow\ \Phi(S(x))\big)\Big)\ \Rightarrow\ (\forall x)(\Phi(x))$

(gdzie $S$ jest jedno argumentowym symbolem funkcyjnym, oznaczającym funkcję "następnika"). Należy zwrócić uwagę, że ta nieskończona lista aksjomatów jest wciąż znacznie słabsza od często formułowanej zasady indukcji w której kwantyfikuje się po wszystkich predykatach:

jeśli 0 jest elementem zbioru $X\subseteq {\mathbb N}$ oraz zbiór ten spełnia warunek $(\forall n)(n\in X\ \Rightarrow n+1\in X)$, to $X={\mathbb N}$.

Twierdzenie o definiowaniu indukcyjnym

Ważną konsekwencją zasady indukcji jest następujące twierdzenie uzasadniające poprawność definiowania rekurencyjnego:

Niech $A$ będzie niepustym zbiorem i niech $U$ będzie zbiorem wszystkich ciągów skończonych o wyrazach w $A$. Przypuśćmy, że dana jest funkcja $f:U\longrightarrow A$. Wówczas istnieje jedyna funkcja $g:{\mathbb N}\longrightarrow A$ taka, że dla każdej liczby naturalnej $n\in {\mathbb N}$ mamy

$g(n)=f\big(g\upharpoonright\big\{m\in {\mathbb N}:m<n\big\}\big)$.

Przypomnijmy, że symbol $\upharpoonright$ oznacza obcięcie funkcji, a więc $g\upharpoonright\big\{m\in {\mathbb N}:m<n\big\}$ jest zawężeniem funkcji g do pierwszych n liczb naturalnych (czyli jest to ciąg skończony długości n).

Jak stosujemy indukcję

Jeśli $T(n)$ oznacza pewne twierdzenie mówiące o liczbach naturalnych $n$, to aby udowodnić, że twierdzenie to jest prawdziwe dla każdej liczby naturalnej $n$ nie mniejszej od $n_0$ (samo $n_0$ może być równe $1$ albo być inną ustaloną liczbą naturalną), wystarczy:

• dowieść, że jest ono prawdziwe dla liczby $n_0$, to znaczy sprawdzić, że zachodzi $T(n_0)$.
• dla każdej liczby naturalnej $n$ nie mniejszej od $n_0$, wychodząc z założenia, że twierdzenie to jest prawdziwe dla liczby $n$, wyprowadzić, że jest ono prawdziwe dla $n+1$, chodzi bowiem o to, aby wykazać, że dla każdej liczby naturalnej $n$ nie mniejszej od $n_0$ prawdziwa jest implikacja: $T(n) \implies T(n+1)$