indukcja matematyczna

indukcja matematyczna,

metoda dowodzenia twierdzeń matematycznych;

pozwala w skończonej liczbie kroków wykazać, że dana własność W przysługuje każdemu elementowi (nieskończonego) zbioru liczb naturalnych ℕ. Jeśli wykaże się, że: (I) ma tę własność najmniejsza liczba naturalna 0 oraz (II) z tego, że ma ją (dowolna) liczba n (założenie indukcyjne) wynika, że własność W ma również liczba n + 1 (teza indukcyjna), to można wnioskować, że każda liczba naturalna ma własność W. Równoważnie — jeżeli (I) 0 ma własność W oraz (II) z tego, że każda liczba naturalna mniejsza od liczby n ma własność W wynika, że również n ma własność W, to każda liczba naturalna ma własność W. Dowód warunku (I) nazywa się pierwszym krokiem indukcyjnym, dowód warunku (II) — drugim krokiem indukcyjnym. Przykładowo, jeśli W oznacza własność: 0 + 1 + 2 + 3 + ... + n = n(n + 1)/2, to: (I) równość jest prawdziwa, gdy n = 0 (obie strony są wówczas równe 0) oraz (II) jeśli 0 + 1 + 2 + 3 + ... + n = n(n + 1)/2 dla pewnej (dowolnej) liczby naturalnej n, to 0 + 1 + 2 + 3 + ... + n + (n + 1) = n(n + 1)/2 + (n + 1) = (n + 1)((n + 1) + 1)/2, czyli równość jest prawdziwa także dla n + 1; zatem można stwierdzić, że każda liczba naturalna n ma własność W.

Indukcję matematyczną można uogólnić na dowolny zbiór dobrze uporządkowany (A, ≤_A) (indukcja matematyczna pozaskończona): (I) jeśli najmniejszy element zbioru (A, ≤_A) ma własność W oraz (II) jeśli z tego, że każdy element poprzedzający (w sensie relacji ≤_A) element x ma własność W wynika, że również x ma własność W, to każdy element zbioru A ma własność W. Istotą indukcji matematycznej jest następujący schemat wnioskowania: jeśli w zbiorze A (I) pewna własność W przysługuje elementom, które w zadanej strukturze na A można uznać za początkowe, oraz (II) z tego, że własność W mają pewne elementy zbioru A wynika, że mają ją także elementy, które w tej strukturze następują po nich, to każdy element zbioru A ma własność W. Ten schemat jest poprawny, jeśli każdy element zbioru A można osiągnąć (w sensie danej struktury) z elementów początkowych. Na przykład, w zbiorze A z rodziną operacji F (algebra (A, F)) indukcja matematyczna (algebraiczna) przybiera następującą postać: (I) jeśli każdy element pewnego zbioru generatorów G algebry (A, F) ma własność W oraz (II) dla dowolnej operacji f ∈ F (n-argumentowej) i dowolnych elementów g₁, g₂, ... , g_n ∈ G z tego, że g₁, g₂, ... , g_n mają własność W, wynika, że ma ją również element f(g₁, g₂, ... ,g_n), to każdy element zbioru A ma własność W.

Wiktor Bartol