Matematyka dyskretna 1/Wykład 1: Indukcja

From Studia Informatyczne

Spis treści

1 Wprowadzenie
- 1.1 Notacja:
2 Indukcja matematyczna

Wprowadzenie

Matematyka dyskretna to zbiorcza nazwa działów matematyki, zajmujących się badaniem struktur nieciągłych, czyli skończonych lub co najwyżej przeliczalnych. Matematyka dyskretna stała się popularna w ostatnich latach dzięki zastosowaniom w informatyce, która w sposób naturalny zajmuje się jedynie strukturami skończonymi. Oto niektóre działy i tematy mające bardzo silny związek z matematyką dyskretną:

logika,

teoria mnogości,

algebra struktur skończonych,

algebra liniowa,

kombinatoryka,

teoria liczb,

algorytmika,

teoria informacji,

złożoność obliczeniowa,

rachunek prawdopodobieństwa,

teoria grafów,

teoria i częściowych porządków.

Wiele z powyższych zagadnień będzie omawiane w trakcie późniejszych kursów. Część już poznaliście w trakcie kursów:

Logika i teoria mnogości,

Algebra liniowa z geometrią analityczną,

do których będziemy się często odwoływać.

W trakcie kursu Matematyka dyskretna 1 i jego rozszerzenia Matematyka dyskretna 2 skoncentrujemy się natomiast na następujących zagadnieniach:

Matematyka dyskretna 1
- kombinatoryka,
- teoria grafów,
- teoria liczb.

Matematyka dyskretna 2:
- zaawansowana teoria grafów,
- teoria grup i ciał skończonych,
- elementy kryptografii.

[Edytuj]

Notacja:

Oznaczenia zbiorów:
- $\mathbb{N}$ - zbiór liczb naturalnych, czyli ${\left\{ {0,1,2,\ldots} \right\}\ }$ . Tak, tak $0$ jest liczbą naturalną!
- $\mathbb{Z}$ - zbiór liczb całkowitych,
- $\mathbb{Q}$ - zbiór liczb wymiernych,
- $\mathbb{R}$ - zbiór liczb rzeczywistych,
- $\mathbb{C}$ - zbiór liczb zespolonych.

Oznaczenia niektórych funkcji:
- $\log x$ - to logarytm z liczby $x$ przy podstawie $10$ ,
- $\lg x$ - to logarytm z liczby $x$ przy podstawie $2$ ,
- $\left\lfloor x\right\rfloor$ - to największa liczba całkowita nie większa od $x$ ,
- $\left\lceil x\right\rceil$ - to najmniejsza liczba całkowita nie mniejsza od $x$ .

$\array{|c|c|c|} \hline \textnormal{Podłoga}: & \mathbb{R} \ni x \mapsto \left\lfloor x\right\rfloor \in \mathbb{Z} & \left\lfloor x\right\rfloor \textnormal{to największa liczba całkowita mniejsza lub równa} \quad x\\ \hline \textnormal{Sufit}: & \mathbb{R} \ni x \mapsto \left\lceil x\right\rceil \in \mathbb{Z} & \left\lceil x\right\rceil \textnormal{to najmniejsza liczba całkowita większa lub równa} \quad x\\ \hline \endarray$

I tak na przykład:

$\array{|c|c|c|} \hline x & \left\lfloor x\rfloor & \left\lceil x\right\rceil\\ \hline 2 & 2 & 2\\ \hline -2 & -2 & -2\\ \hline 2.5 & 2 & 3\\ \hline -2.5 & -3 & -2\\ \hline \pi & 3 & 4\\ \hline \endarray$

Przykład

Funkcji $\left\lfloor x\right\rfloor$ w połączeniu z funkcją logarytmu można użyć do wyliczania liczby cyfr liczby naturalnej $k$ zapisanej w układzie dziesiętnym. Jest to mianowicie

$\left\lfloor \log_{10}k \right\rfloor+1$

Podobnie

$\left\lfloor \log_{2}k \right\rfloor+1$

jest liczbą bitów potrzebnych do zapisania liczby naturalnej $k$ .

W dalszym ciągu przyjmujemy, że jeśli nie jest napisane jakie wartości może przyjmować zmienna, to przyjmuje ona wartości z $\mathbb{N}$ .

[Edytuj]

Indukcja matematyczna

Indukcja matematyczna będzie przez nas używana jako metoda dowodzenia twierdzeń. Zazwyczaj są to twierdzenia dotyczące liczb naturalnych, ale - jak się jeszcze wielokrotnie przekonamy - wiele różnych twierdzeń, pozornie nie dotyczących liczb naturalnych, można sformułować tak, by można było je poddać dowodowi indukcyjnemu.

Poprawność indukcji matematycznej wynika z dobrego uporządkowania liczb naturalnych, czyli z następującej zasady minimum:

[Edytuj]

Zasada Minimum

Francesco Maurolico (1494-1575)
Zobacz biografię

MD1-1.3.swf

Dowolny niepusty podzbiór $S \subseteq \mathbb{N}$ zbioru liczb naturalnych ma w sobie liczbę najmniejszą.

Założenie, że zbiór $S$ nie jest pusty jest oczywiście konieczne, gdyż w zbiorze pustym nie istnieje żadna liczba.

Przykład

Pierwszy, znany dowód używający indukcji przedstawił Francesco Maurolio

w 1575 roku. Udowodnił on, że suma początkowych $n$ liczb nieparzystych wynosi $n^2$ , tzn.:

$1 + 3 + 5 + \ldots + (2n-1) = n^2$

Istotnie, bardzo łatwo sprawdzić, że dla wybranej wartości $n$ jest to prawda. Na przykład:

$\aligned 1+3 &=& 4 = 2^2 \\ 1+3+5 &=& 9 = 3^2 \\ 1+3+5+7 &=& 16 = 4^2 \\ 1+3+5+7+9 &=& 25 = 5^2 \endaligned$

Ale jak pokazać, że jest to prawdą dla wszystkich liczb?

Z pomocą może nam tu przyjść Zasada Minimum. Gdyby rozważana równość nie zachodziła dla wszystkich liczb naturalnych, to zbiór

$S = {\left\{ {n \in \mathbb{N} : 1 + 3 + 5 + \ldots + (2n-1) \neq n^2} \right\}\ }$

byłby niepusty, i zgodnie z Zasadą Minimum miałby liczbę najmniejszą. Ten najmniejszy kontrprzykład dla równości Maurolio, tzn. najmniejszą liczbę w zbiorze $S$ , oznaczmy sobie przez $s$ . Wiemy już, że $s\neq 1,2,3,4,5$ , bo te liczby spełniają równości Maurolio, więc nie leżą w zbiorze $S$ . Również $s\neq 0$ no oczywiście suma zerowej liczby nieparzystych liczb wynosi $0=0^2$ , wiec $0 \not\in S$ . Oznacza to, że $s>5$ .

Z drugiej strony, skoro $s$ jest najmniejszym kontrprzykładem, to $s-1$ spełnia równość Maurolio więc:

$1 + 3 + 5 + \ldots + (2s-3) = (s-1)^2.$

Dodając teraz do obu stron równości kolejną liczbę nieparzystą, czyli $2s+1$ , dostajemy

$1 + 3 + 5 + \ldots + (2s-3) + (2s-1) = (s-1)^2 + (2s-1) = s^2 - 2s + 1 + 2s - 1 = s^2,$

co oczywiście oznacza, że $s\not\in S$ . Tym samym $s$ nie może być najmniejszą liczbą w zbiorze kontrprzykładów, a więc w ogóle taki kontrprzykład istnieć nie może, i wobec tego wszystkie liczby naturalne spełniają równość Maurolio.

Rozumowanie przeprowadzone na przykładzie równości Maurolio wskazuje, że jeśli tylko $Z \subseteq \mathbb{N}$ jest jakimś zbiorem liczb naturalnych,

w którym jest zero, tzn. $0 \in Z$ ,

oraz $Z$ wraz z każdą liczbą naturalną $k$ zawiera również kolejną liczbę $k+1$ , tzn. $\forall k\in Z \ \ k+1 \in Z$ ,

to wtedy $Z$ musi już zawierać wszystkie liczby naturalne, tzn. $Z=\mathbb{N}$ .

Md-1.1

Przykład

Pokażemy, że dla dowolnej liczby naturalnej $n$ zachodzi:

$0+1+2+\ldots+n=\frac{n(n+1)}{2}\qquad$ dla $n \geq 0$

Podobnie jak poprzednio łatwo udowodnić, iż jest to prawda dla wybranych, konkretnych $n$ . W szczególności:

dla $n=2$ mamy $1+2=3$ oraz $\frac{2\cdot(2+1)}{2}=3$ ,

dla $n=5$ mamy $1+2+3+4+5=15$ oraz $\frac{5\cdot(5+1)}{2}=15$ ,

dla $n=14$ mamy $1+2+\ldots+14=105$ oraz $\frac{14\cdot(14+1)}{2}=105$ .

Jednak te wszystkie równości nie dowodzą, iż jest to prawda dla dowolnego $n\in\mathbb{N}$ . Żadnym skończonym ciągiem sprawdzeń nie jesteśmy w stanie uzasadnić tej równości dla wszystkich liczb naturalnych z osobna, gdyż jest ich zbyt wiele. Z pomocą przychodzi jednak schemat rozumowania indukcyjnego zaproponowany powyżej:

Niech

$Z = {\left\{ {n\in\mathbb{N}: 0+1+2+\ldots+n=\frac{n(n+1)}{2}} \right\}\ }.$

Wtedy

$0\in Z$ , bo $0=\frac{0\cdot(0+1)}{2}$ ,

nadto, gdy $k\in Z$ , tzn.

$0+1+2+ \cdots + (k-1) +k = \frac{k(k+1)}{2},$

to, badając, czy $k+1 \in Z$ rozważamy sumę

$\begin{array} {rcccl} 0+1+2+ \cdots + k + (k+1) &=& \left[0+1+2+ \cdots + k\right] &+& (k+1) \\[1,5ex] &=& \left[\frac{k(k+1)}{2}\right] &+& (k+1) \\[1,5ex]&=&\frac{k(k+1)+2(k+1)}{2}&& \\[1,5ex] &=&\frac{(k+1)(k+2)}{2}&& \\[1,5ex] &=&\frac{(k+1)((k+1)+1)}{2}&& \end{array}$

co świadczy o tym, że $k+1 \in Z$ .

A stąd już możemy wnosić, podobnie jak w przypadku równości Maurolio, że $Z=\mathbb{N}$ .

Przykład

Niech

$Z={\left\{ {n\in\mathbb{N} : 0^2+1^2+2^2+3^2+ \cdots + (n-1)^2 +n^2 = \frac{n(n+1)(2n+1)}{6} } \right\}\}.$

Jeśli pokażemy, że $Z=\mathbb{N}$ , to dostaniemy ważny wzór na sumę kolejnych kwadratów.

Oczywiście $0 \in Z$ .

Nadto, gdy $k\in Z$ , to aby stwierdzić czy $k+1$ jest w $Z$ rozważamy sumę

$\begin{array} {rcccl} 0^2+1^2+2^2+ \cdots + k^2 + (k+1)^2 &=& \left[0^2+1^2+2^2+ \cdots + k^2\right] &+& (k+1)^2 \\[1,5ex] &=& \left[\frac{k(k+1)(2k+1)}{6}\right] &+& (k+1)^2 \\[1,5ex]&=&\frac{k(k+1)(2k+1)+6(k+1)^2}{6} \\[1,5ex] &=&\frac{(k+1)[k(2k+1)+6(k+1)]}{6} \\[1,5ex] &=&\frac{(k+1)[2k^2+7k+6]}{6} \\[1,5ex] &=&\frac{(k+1)[(k+2)(2k+3)]}{6} \\[1,5ex] &=&\frac{(k+1)((k+1)+1)(2(k+1)+1)}{6}&& \end{array}$

co świadczy o tym, że $k+1 \in Z$ .

Przykład

Można zauważyć, że funkcja $n\mapsto n^2$ rośnie wolniej niż $n \mapsto 2^n$ . Co prawda dla początkowych wartości mamy

$\begin{array} {|c|c|c|c|c|c|c|c|c|c|c} \hline n&0&1&2&3&4&5&6&7&8&...\\ \hline \hline n^2&0&1&4&9&16&25&36&49&64&...\\ \hline 2^n&1&2&4&8&16&32&64&128&256&...\\ \hline \end{array}$

i zachowanie tych dwu funkcji nie jest zdecydowane, ale już dla większych wartości $n$ , liczba $2^n$ znacznie dominuje $n^2$ .

Często, tak jak w powyższym przykładzie, pewna własność nie dotyczy wszystkich liczb naturalnych, ale prawie wszystkich, tzn. wszystkich poza być może pewną skończoną liczba wartości początkowych. Wtedy z pomocą przychodzi już następujące sformułowanie Zasady Indukcji Matematycznej.

[Edytuj]

Zasada Indukcji Matematycznej

Jeśli $Z \subseteq \mathbb{N}$ jest jakimś zbiorem liczb naturalnych,

w którym jest $k_0$ , tzn. $k_0 \in Z$ ,
oraz $Z$ wraz z każdą liczbą naturalną $k \ge k_0$ zawiera również kolejną liczbę $k+1$ , tzn. $\forall k\geq k_0 \ \ k \in Z \Rightarrow \ k+1 \in Z$ ,

to wtedy zbiór $Z$ zawiera wszystkie liczby naturalne $n \ge k_0$ ,
tzn. $Z\supseteq\mathbb{N}-{\left\{ {0,1,\ldots,k_0-1} \right\}\ }$ .

Pierwszy warunek nazywamy bazą indukcji. W drugim warunku najpierw dokonujemy założenia indukcyjnego (o tym, że $k\in Z$ ), aby wykonać krok indukcyjny dowodząc, że $k+1\in Z$ .

Często używaną ilustracją indukcji matematycznej jest efekt domina. Załóżmy, że ułożyliśmy bardzo dużo kostek domina, jedna za drugą. Upewniliśmy się też, że jeśli przewróci się dowolna z nich (założenie indukcyjne) to przewróci się też następna (krok indukcyjny). Wtedy, jeśli ktoś nam powie, że przewrócił czwartą kostkę (baza indukcji) to wiemy, iż wszystkie następne (poza być może pierwszymi trzema) też się przewróciły. W indukcji matematycznej liczby naturalne są niejako kostkami domina ułożonymi dostatecznie blisko siebie.

Przykład

Aby się przekonać, że w istocie

$n^2 <2^n$ dla $n\geq 5$

przeprowadźmy dowód indukcyjny:

Pokażemy najpierw, że (dla zupełnie dowolnego )
- oczywiście $2 \cdot 3 + 1 = 7 < 8 =2^3$
- oraz $2(n+1)+ 1 = 2n+3 <2^n+4 = 2^n+2^2 \leq 2^n + 2^n = 2\cdot 2^n = 2^{n+1}$

a następnie
- zauważamy, że $5^2=25<32=2^5$
- oraz, że $(n+1)^2 = n^2 + (2n+ 1) < 2^n +2^n = 2\cdot 2^n = 2^{n+1}$ .

Kolejne dowody indukcyjne będziemy już przeprowadzać mniej opisowo, pomijając na przykład definicje zbioru $Z$ , o którym później dowodzimy, że zawiera (prawie) wszystkie liczby naturalne.

Przykład [nierówność Bernoulliego]

Udowodnimy, że dla dowolnej liczby rzeczywistej $a\geq -1$ oraz dowolnego $n\in\mathbb{N}$ zachodzi

$(1+a)^n \geq 1+na.$

baza: $(1+a)^0=1=1+0\cdot a$ ,

z założenia indukcyjnego $(1+a)^k\geq 1+ka$ , poprzez wymnożenie stronami przez nieujemną liczbę rzeczywistą $1+a$ , dostajemy

$\aligned(1+a)^{k+1}&=&(1+a)^k(1+a)\\ &\geqslant&(1+ka)(1+a)\\ &=&1+a+ka+ka^2\\ &\geqslant&1+(k+1)a. \endaligned$

Przykład

Pokażemy, że o ile tylko $n\geq 2$ , to liczba postaci $2^{2^n}$ ma na końcu w zapisie dziesiętnym cyfrę $6$ . Oznacza to, że $2^{2^n}= 10x+6$ dla pewnej liczby naturalnej $x$ .

Dla $n=2$ mamy $2^{2^2}=16 =10\cdot 1 +6$ ,

Nadto, gdy $2^{2^n}=10x+6$ , to

$2^{2^{n+1}} = 2^{2^n\cdot 2} = \left(2^{2^n}\right)^2 = (10x+6)^2 = 100x^2+120x+36 =$ $10(10x^2+12x+3)+6.$

Przykład [ $n$ -ta liczba harmoniczna]

$n$ -ta liczba harmoniczna to

$H_n=\frac{1}{1}+\frac{1}{2}+\ldots+\frac{1}{n}.$

Przyjmuje się, że $H_0=0$ . Nazwa ta wzięła się stąd, że możliwe do uzyskania na strunie długości fali stojącej są proporcjonalne kolejno do $1,\frac{1}{2},\frac{1}{3},\frac{1}{4}\ldots$ . Oto wartości kilku pierwszych liczb harmonicznych:

$\begin{array} {|c|c|c|c|c|c|c|c|c|c} \hline n&0&1&2&3&4&5&6&7&8 \\ \hline H_n&0&1&\frac{3}{2}&\frac{11}{6}&\frac{25}{12}&\frac{137}{60}&\frac{49}{20}&\frac{363}{140}&\frac{761}{280} \\ \hline \end{array}$

Pokażemy, że liczby harmoniczne osiągają dowolnie duże wartości, choć rosną dość wolno.

Dla $n\ge 1$ mamy mianowicie:

$\frac{\left\lfloor \lg{n}\right\rfloor+1}{2} \leq H_n \leq \left\lfloor \lg{n}\right\rfloor+1.$

Powyższe oszacowania wynikają natychmiastowo z nierówności:

$\frac{n+1}{2} \leq H_{2^n} \leq n+1,$

które udowodnimy indukcyjnie ze względu na $n$ :

dla $n=0$ mamy $\frac{0+1}{2} \leq H_1 \leq 0+1$ ,

zakładając teraz indukcyjnie, że $\frac{k+1}{2} \leq H_{2^k} \leq k+1$ ,

mamy

$\begin{array} {rcl} H_{2^{k+1}}&=&H_{2^k}+\frac{1}{2^k+1}+\frac{1}{2^k+2}+\ldots+\frac{1}{2^{k+1}} \leq k+1+2^k\frac{1}{2^k}\\ &=&k+2. \end{array}$

oraz

$\begin{array} {rccl} H_{2^{k+1}}&=&H_{2^k}+\frac{1}{2^k+1}+\frac{1}{2^k+2}+\ldots+\frac{1}{2^{k+1}}\geq \frac{k+1}{2}+2^k\frac{1}{2^{k+1}}\\ &=&\frac{k+2}{2}. \end{array}$

Często wygodniej jest zamiast Indukcji Matematycznej stosować z pozoru mocniejszą Zasadę Indukcji Zupełnej. Tym razem, po to, by wywnioskować, iż $k\in Z$ będziemy mogli skorzystać nie tylko z faktu, że $k-1\in Z$ , ale ze znacznie mocniejszego założenia, że wszystkie liczby mniejsze niż $k$ , tzn. $0,\ldots,k-1$ , są w $Z$ .

[Edytuj]

Zasada Indukcji Zupełnej

Jeśli $Z \subseteq \mathbb{N}$ jest jakimś zbiorem liczb naturalnych,

który wraz z każdym początkowym fragmentem zbioru $\mathbb{N}$ postaci ${\left\{ {0,\ldots,k-1} \right\}\ }$ zawiera również kolejną liczbę $k$ , tzn. $\forall k\in \mathbb{N}$ jeśli $\left(\forall l<k \ \ l\in Z\right),$ to $k+1 \in Z$

to wtedy $Z$ zawiera wszystkie liczby naturalne, tzn. $Z=\mathbb{N}$ .

Zasada Indukcji Zupełnej pozwala skorzystać w dowodzie kroku indukcyjnego( $k\in Z$ ) ze znacznie szerszego założenia indukcyjnego, że $l\in Z$ dla wszystkich $l<k$ (a nie tylko dla $k-1$ jak w indukcji matematycznej).

Zwróćmy uwagę, że w Zasadzie Indukcji Zupełnej nie ma wyróżnionego kroku bazowego. Jest on ukryty w warunku dla $k=0$ : poprzednik implikacji jest trywialnie spełniony (dowolne naturalne $l<0$ spełnia wszystkie możliwe warunki, gdyż po prostu nie istnieje). Zazwyczaj w dowodach przez indukcję zupełną dowód tego brzegowego warunku (bazowego) jest odrębny.

MD1-Rys1.4.swf

Przykład

Mamy prostokątną czekoladę złożona z $N=a\cdot b$ ( $a,b>0$ ) kwadratowych kawałków. Przez wykonanie cięcia (ułamanie czekolady) rozumiemy rozcięcie jej jakiejkolwiek spójnej części wzdłuż którejś z linii pomiędzy kawałkami, tak by dostać dwa znów prostokątne kawałki. Ile razy trzeba ułamać czekoladę aby rozdzielić jej wszystkie kwadraciki?

Stosując indukcję zupełną względem liczby $N$ (kwadracików w czekoladzie), że niezależnie od kolejności wykonywanych cięć potrzeba i wystarcza dokładnie $N-1$ cięć.

Jeśli czekolada ma tylko $1$ kawałek, to nie trzeba niczego dzielić, więc $0$ cięć wystarcza,

Gdy czekolada ma $k$ kawałków, to pierwsze jej cięcie podzieli ją na dwa prostokąty o odpowiednio $k_0$ i $k_1$ kawałkach, przy czym $k_0+k_1=k$ i $k_0,k_1<k$ . Korzystając teraz z założenia indukcyjnego wiemy, że aby połamać te mniejsze kawałki potrzeba i wystarcza odpowiednio $k_0-1$ i $k_1-1$ cięć. W sumie wykonaliśmy więc $1+(k_0-1)+(k_1-1)=(k-1)$ cięć, co było do udowodnienia.

Zauważmy, że w tym rozumowaniu istotnie skorzystaliśmy z możliwości indukcji zupełnej używając w dowodzie założenia indukcyjnego dla dowolnego $1\leq l<k$ .

George Pólya (1887-1985)
Zobacz biografię

Przykład

Proponujemy teraz przeanalizować przykład błędnego rozumowania indukcyjnego. Ćwiczenie to zaproponował George Polya

wybitny węgierski matematyk. Udowodnimy zatem, że wszystkie konie są jednej maści!

Posłużymy się indukcją względem liczby koni.

Dowolny zbiór złożony z jednego konia jest zbiorem koni o jednej maści.

Rozpatrzmy dowolny $(k+1)$ -elementowy zbiór koni. Wybierzmy dowolnego konia z tego zbioru i usuńmy go na chwilę. Na mocy założenia indukcyjnego $k$ -elementowy zbiór pozostałych koni jest zbiorem koni o tej samej maści. Dodajmy z powrotem usuniętego konia i usuńmy dowolnego innego. Znów mamy $k$ -elementowy zbiór koni, a więc są to konie tej samej maści. Ponadto usunięty koń był tej samej maści co większość koni w obecnym zbiorze. To oznacza, że wszystkie rozpatrywane $k+1$ konie są jednej maści.

Gdzie jest błąd?

Wskazówka:

Sprawdź rozumowanie kroku indukcyjnego dla małych wartości $k$ .

Rozwiązanie:

Krok indukcyjny jest błędny dla $k=1$ ( $k+1=2$ ). Rzeczywiście,

rozważamy dowolne dwa konie A i B,

usuwając konia A pozostały koń B stanowi oczywiście zbiór koni jednej maści,

dodając z powrotem konia A i usuwając konia B znów mamy jednoelementowy zbiór koni tej samej maści,

jednak powyższe zdania nie implikują, że A i B mają tę samą maść.

Zwróćmy uwagę, że dla dowolnego $k\geq 2$ rozumowanie jest poprawne. Rzeczywiście, gdyby dowolne dwa konie były tej samej maści to wszystkie byłyby tej samej maści.

W przedstawionych przykładach użyliśmy różnych modyfikacji zasady indukcji. Powiedzieliśmy, że są one konsekwencją zasady minimum, czyli dobrego uporządkowania zbioru $\mathbb{N}$ . Nie udowodniliśmy jednak poprawności samej zasady indukcji. Zanim to uczynimy wprowadzimy jeszcze jedną, bardzo silnie powiązaną zasadę.

[Edytuj]

Zasada Maksimum

Dowolny niepusty i ograniczony od góry podzbiór $S \subseteq \mathbb{N}$ zbioru liczb naturalnych ma w sobie liczbę największą.

Obserwacja 1.1

Następujące zasady są równoważne:

Zasada Minimum,

Zasada Indukcji Zupełnej,

Zasada Indukcji Matematycznej,

Zasada Maksimum.

Dowód

Pokażemy najpierw, że Zasada Minimum implikuje Zasadę Indukcji Zupełnej. Dla dowodu niewprost załóżmy, że istnieje pewien podzbiór $Z\subseteq N$ taki, że $k\in Z$ , jeśli tylko $Z$ zawiera wszystkie liczby naturalne $l<k$ , ale wbrew Zasadzie Indukcji Zupełnej $Z\neq N$ . Wtedy oczywiście zbiór $S=\mathbb{N}-Z$ jest niepusty na podstawie Zasady Minimum ma element najmniejszy, powiedzmy $s_0$ . Z minimalności $s_0$ wiemy, że żadna z liczb $l<s_0$ nie może być w $S$ zatem wszystkie one są w $Z$ . Wtedy jednak, nasze założenie o zbiorze $Z$ gwarantuje, że również $s_0 \in Z$ , wbrew przypuszczeniu, że $s_0 \in S =\mathbb{N}-Z$ .

Teraz z Zasady Indukcji Zupełnej wyprowadzimy Zasadę Indukcji Matematycznej. Niech więc jakiś podzbiór $Z\subseteq\mathbb{N}$ spełnia

$k_0 \in Z$ ,

$\forall k\geq k_0 \ \ k \in Z \Rightarrow \ k+1 \in Z$ .

Aby dowieść, że $k \in Z$ ilekroć $k\geq k_0$ , wystarczy pokazać, że zbiór $Z'={\left\{ {l\in\mathbb{N} : l<k_0} \right\}\ } \cup Z$ jest równy $\mathbb{N}$ . To z kolei uzyskamy, pokazując, że $Z'$ spełnia założenia Zasady Indukcji Zupełnej. Istotnie, niech $k$ będzie dowolną liczbą naturalna, taką że $Z'$ zawiera wszystkie liczby naturalne $l<k$ . Chcemy pokazać, że wtedy $k\in Z'$ . Z samej definicji zbioru $Z'$ jest to oczywiste ilekroć $k<k_0$ . Z założenia o zbiorze $Z$ jest to również oczywiste dla $k=k_0$ . Gdy natomiast $k>k_0$ to $k-1\geq k_0$ . Ponadto, $k$ jako liczba mniejsza od $k$ , należy do $Z'$ (bo $Z'$ zawiera wszystkie liczby naturalne $l<k$ ). Ale $k-1 \notin{\left\{ {l\in\mathbb{N} : l<k_0} \right\}\ }$ , więc $k\in Z$ . Teraz wystarczy zastosować drugie założenie o zbiorze $Z$ , by wnosić, że $k =(k-1)+1 \in Z \subseteq Z'$ .

Kolejnym krokiem będzie wyprowadzenie Zasady Maksimum z Zasady Indukcji Matematycznej. Niech więc $S\subseteq \mathbb{N}$ będzie zbiorem niepustym, ale ograniczonym od góry. Używając indukcji z uwagi na wielkość liczby $M$ ograniczającej od góry zbiór $S$ , pokażemy, że $S$ ma element największy.

Jeśli $M=0$ , to ponieważ $S\neq\emptyset$ , wiemy, że $S={\left\{ {0} \right\}\ }$ . Wobec tego $0$ jest elementem największym w $S$ .

Pracujemy przy założeniu indukcyjnym, mówiącym że każdy niepusty podzbiór zbioru $\mathbb{N}$ ograniczony przez $M$ ma element największy. Chcemy dowieść, że jeśli $\emptyset \neq S \subseteq\mathbb{N}$ jest ograniczony przez $M+1$ , to $S$ ma element największy. Jeśli $M+1\in S$ , to $M+1$ jest elementem największym w $S$ , bo ogranicza $S$ . Jeśli zaś $M+1\notin S$ to $S$ jest także ograniczony przez $M$ , a więc na mocy założenia indukcyjnego ma element największy.

Na koniec pokażmy, że Zasada Maksimum implikuje Zasadę Minimum. Rozważmy zatem dowolny, niepusty $S\subseteq\mathbb{N}$ . Jeśli $0\in S$ to $0$ jest elementem najmniejszym w $S$ . Załóżmy zatem, że $0\notin S$ . Wtedy niech

$S'={\left\{ {n\in\mathbb{N}:n\leq s$ dla dowolnego $s\in S} \right\}\ }.$

Ponieważ $0\in S'$ to $S'$ jest niepusty. Ponieważ $S$ jest niepusty to $S'$ jest ograniczony. Zatem z Zasady Maksimum zbiór $S'$ ma element największy, powiedzmy $s_0$ . Pokażemy, że $s_0$ należy do $S$ i jest najmniejszy w $S$ . Gdyby $s_0 \not\in S$ wtedy $s_0+1$ należałoby do $S'$ , a to stoi w sprzeczności z maksymalnością $s_0$ w $S'$ . Gdyby zaś $s_0$ nie było najmniejsze w $S$ , to $s_1<s_0$ dla jakiegoś $s_1\in S$ . Wtedy jednak $s_0$ nie mogłoby być w $S'$ . Sprzeczność.