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:
Zasada Minimum
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:
\( \begin{align*} 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 \end{align*} \)
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 = {\{ {n \in \mathbb{N} : 1 + 3 + 5 + \ldots + (2n-1) \neq n^2} \}\ } \)
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} \).
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 = {\{ {n\in\mathbb{N}: 0+1+2+\ldots+n=\frac{n(n+1)}{2}} \}\ }. \)
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) & = & [0+1+2+ \cdots + k] & + & (k+1) \\ [1,5ex] & = & [\frac{k(k+1)}{2}] & + & (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 & = & [0^2+1^2+2^2+ \cdots + k^2] & + & (k+1)^2 \\ [1,5ex] & = & [\frac{k(k+1)(2k+1)}{6}] & + & (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.
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}-{\{ {0,1,\ldots,k_0-1} \}\ } \).
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 \( 2n+1 < 2^n \) (dla zupełnie dowolnego \( n\geq 3 \))
- 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
\( \begin{align*}(1+a)^{k+1} & = & (1+a)^k(1+a) \\ & \geq & (1+ka)(1+a) \\ & = & 1+a+ka+ka^2 \\ & \geq & 1+(k+1)a. \end{align*} \)
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} = (2^{2^n})^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{\lfloor \lg{n}\rfloor+1}{2} \leq H_n \leq \lfloor \lg{n}\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 \).
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 \( {\{ {0,\ldots,k-1} \}\ } \) zawiera również kolejną liczbę \( k \), tzn. \( \forall k\in \mathbb{N} \) jeśli \( (\forall l < k \ \ l\in Z), \) 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.
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 \).
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?
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ę.
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 Indukcji Zupełnej,
- Zasada Indukcji Matematycznej,
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
- \( \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'={\{ {l\in\mathbb{N} : l < k_0} \}\ } \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{\{ {l\in\mathbb{N} : l < k_0} \}\ } \), 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={\{ {0} \}\ } \). 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'= \{n\in\mathbb{N}:n\leq s \) dla dowolnego \(s\in S . \)
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ść.