Zasada indukcji zupełnej

Zbiór wzorów, definicji i najczęściej poruszanych problemów z Podstaw matematyki
Awatar użytkownika
bolo
Użytkownik
Użytkownik
Posty: 2470
Rejestracja: 2 lis 2004, o 08:28
Płeć: Mężczyzna
Lokalizacja: BW
Podziękował: 8 razy
Pomógł: 191 razy

Zasada indukcji zupełnej

Post autor: bolo »

Niech każdej liczbie naturalnej \(\displaystyle{ n}\) przyporządkowane jest zdanie \(\displaystyle{ p(n)}\).

Jeżeli:
  1. \(\displaystyle{ p(1)}\) jest prawdziwe,
  2. jeżeli \(\displaystyle{ p(n)}\) jest prawdziwe, to jest prawdziwe \(\displaystyle{ p(n+1)}\),
to zdanie \(\displaystyle{ p(n)}\) jest prawdziwe dla każdego \(\displaystyle{ n=1,2,3,...}\)

Dowód: Skorzystamy z następujących własności liczb naturalnych. W każdym niepustym podzbiorze zbioru liczb naturalnych istnieje najmniejsza liczba naturalna. Przypuśćmy, że są spełnione założenia a), b), oraz że istnieje liczba naturalna \(\displaystyle{ n}\), dla której zdanie \(\displaystyle{ p(n)}\) jest fałszywe. Oznaczmy przez \(\displaystyle{ A}\) zbiór tych \(\displaystyle{ n\in\mathbb{N}}\), dla których \(\displaystyle{ p(n)}\) jest zdaniem fałszywym. Z zaprzeczenia tezy wynika, że \(\displaystyle{ A\neq\O}\), a więc \(\displaystyle{ A}\) zawiera liczbę najmniejszą. Oznaczmy ją przez \(\displaystyle{ n_{0}}\). Z założenia a) wynika, że \(\displaystyle{ p(1)}\) jest zdaniem prawdziwym, czyli \(\displaystyle{ 1\notin A}\), a więc \(\displaystyle{ n_{0}\neq 1}\). Stąd \(\displaystyle{ n_{0}-1}\) jest liczbą naturalną. Ponieważ \(\displaystyle{ n_{0}}\) jest najmniejszą liczbą naturalną w zbiorze \(\displaystyle{ A}\), a więc \(\displaystyle{ n_{0}-1\notin A}\), czyli zdanie \(\displaystyle{ p(n_{0}-1)}\) jest prawdziwe. Z założenia b) wynika, że zdanie \(\displaystyle{ p(n_{0})}\) jest prawdziwe. Jest to sprzeczne z definicją liczby \(\displaystyle{ n_{0}\in A}\). Ponieważ przypuszczenie, że istnieje liczby naturalne \(\displaystyle{ n}\), takie że zdanie \(\displaystyle{ p(n)}\) jest fałszywe doprowadziło do sprzeczności, więc zdanie \(\displaystyle{ p(n)}\) jest prawdziwe dla każdego \(\displaystyle{ n=1,2,3,...}\).

Wniosek:
Jeżeli:
  1. zdanie \(\displaystyle{ p(n)}\) jest prawdziwe dla liczby naturalnej \(\displaystyle{ n_{0}}\),
  2. z prawdziwości \(\displaystyle{ p(n)}\) dla liczby naturalnej \(\displaystyle{ k}\) wynika prawdziwość \(\displaystyle{ p(n)}\) dla liczby \(\displaystyle{ k+1}\), gdzie \(\displaystyle{ k\geqslant n_{0}}\),
to zdanie \(\displaystyle{ p(n)}\) jest prawdziwe dla wszystkich liczb naturalnych \(\displaystyle{ n\geqslant n_{0}}\).
Zablokowany