Matematyka dyskretna 1/Wykład 1: Indukcja
From Studia Informatyczne
Spis treści |
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:
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.
Notacja:
- Oznaczenia zbiorów:
-
- zbiór liczb naturalnych, czyli
. Tak, tak
jest liczbą naturalną!
-
- zbiór liczb całkowitych,
-
- zbiór liczb wymiernych,
-
- zbiór liczb rzeczywistych,
-
- zbiór liczb zespolonych.
-
- Oznaczenia niektórych funkcji:
-
- to logarytm z liczby
przy podstawie
,
-
- to logarytm z liczby
przy podstawie
,
-
- to największa liczba całkowita nie większa od
,
-
- to najmniejsza liczba całkowita nie mniejsza od
.
-

I tak na przykład:

Przykład
Funkcji w połączeniu z funkcją logarytmu można użyć do wyliczania liczby cyfr liczby naturalnej
zapisanej w układzie dziesiętnym. Jest to mianowicie

Podobnie

jest liczbą bitów potrzebnych do zapisania liczby naturalnej .
W dalszym ciągu przyjmujemy, że jeśli nie jest napisane jakie wartości może przyjmować zmienna, to przyjmuje ona wartości z .
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:
Zasada Minimum
Dowolny niepusty podzbiór zbioru liczb naturalnych ma w sobie liczbę najmniejszą.
Założenie, że zbiór 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 liczb nieparzystych wynosi
, tzn.:

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

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

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 , oznaczmy sobie przez
. Wiemy już, że
, bo te liczby spełniają równości Maurolio, więc nie leżą w zbiorze
. Również
no oczywiście suma zerowej liczby nieparzystych liczb wynosi
, wiec
. Oznacza to, że
.
Z drugiej strony, skoro jest najmniejszym kontrprzykładem, to
spełnia równość Maurolio więc:

Dodając teraz do obu stron równości kolejną liczbę nieparzystą, czyli , dostajemy

co oczywiście oznacza, że . Tym samym
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 jest jakimś zbiorem liczb naturalnych,
- w którym jest zero, tzn.
,
- oraz
wraz z każdą liczbą naturalną
zawiera również kolejną liczbę
, tzn.
,
to wtedy musi już zawierać wszystkie liczby naturalne, tzn.
.
Przykład
Pokażemy, że dla dowolnej liczby naturalnej zachodzi:


Podobnie jak poprzednio łatwo udowodnić, iż jest to prawda dla wybranych, konkretnych . W szczególności:
- dla
mamy
oraz
,
- dla
mamy
oraz
,
- dla
mamy
oraz
.
Jednak te wszystkie równości nie dowodzą, iż jest to prawda dla dowolnego . Ż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

Wtedy
-
, bo
,
- nadto, gdy
, tzn.

to, badając, czy 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}](/images/math/2/1/3/2133ff6da63f227e53afb95dd697038a.png)
co świadczy o tym, że .
A stąd już możemy wnosić, podobnie jak w przypadku równości Maurolio, że .
Przykład
Niech

Jeśli pokażemy, że , to dostaniemy ważny wzór na sumę kolejnych kwadratów.
Oczywiście .
Nadto, gdy , to aby stwierdzić czy
jest w
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}](/images/math/2/3/4/23408cc5929eccb21040d5adc242efd6.png)
co świadczy o tym, że .
Przykład
Można zauważyć, że funkcja rośnie wolniej niż
. Co prawda dla początkowych wartości mamy

i zachowanie tych dwu funkcji nie jest zdecydowane, ale już dla większych wartości , liczba
znacznie dominuje
.
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 jest jakimś zbiorem liczb naturalnych,
- w którym jest
, tzn.
,
- oraz
wraz z każdą liczbą naturalną
zawiera również kolejną liczbę
, tzn.
,
to wtedy zbiór zawiera wszystkie liczby naturalne
,
tzn. .
Pierwszy warunek nazywamy bazą indukcji. W drugim warunku najpierw dokonujemy założenia indukcyjnego (o tym, że ), aby wykonać krok indukcyjny dowodząc, że
.
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


przeprowadźmy dowód indukcyjny:
- Pokażemy najpierw, że
(dla zupełnie dowolnego
)
- oczywiście
- oraz
- oczywiście
- a następnie
- zauważamy, że
- oraz, że
.
- zauważamy, że
Kolejne dowody indukcyjne będziemy już przeprowadzać mniej opisowo, pomijając na przykład definicje zbioru , o którym później dowodzimy, że zawiera (prawie) wszystkie liczby naturalne.
Przykład [nierówność Bernoulliego]
Udowodnimy, że dla dowolnej liczby rzeczywistej oraz dowolnego
zachodzi

- baza:
,
- z założenia indukcyjnego
, poprzez wymnożenie stronami przez nieujemną liczbę rzeczywistą
, dostajemy

Przykład
Pokażemy, że o ile tylko , to liczba postaci
ma na końcu w zapisie dziesiętnym cyfrę
. Oznacza to, że
dla pewnej liczby naturalnej
.
- Dla
mamy
,
- Nadto, gdy
, to


Przykład [-ta liczba harmoniczna]
-ta liczba harmoniczna to

Przyjmuje się, że . Nazwa ta wzięła się stąd, że możliwe do uzyskania na strunie długości fali stojącej są proporcjonalne kolejno do
. Oto wartości kilku pierwszych liczb harmonicznych:

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

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

które udowodnimy indukcyjnie ze względu na :
- dla
mamy
,
- zakładając teraz indukcyjnie, że
,
mamy

oraz

Często wygodniej jest zamiast Indukcji Matematycznej stosować z pozoru mocniejszą Zasadę Indukcji Zupełnej. Tym razem, po to, by wywnioskować, iż będziemy mogli skorzystać nie tylko z faktu, że
, ale ze znacznie mocniejszego założenia, że wszystkie liczby mniejsze niż
, tzn.
, są w
.
Zasada Indukcji Zupełnej
Jeśli jest jakimś zbiorem liczb naturalnych,
- który wraz z każdym początkowym fragmentem zbioru
postaci
zawiera również kolejną liczbę
, tzn.
jeśli
to
to wtedy zawiera wszystkie liczby naturalne, tzn.
.
Zasada Indukcji Zupełnej pozwala skorzystać w dowodzie kroku indukcyjnego() ze znacznie szerszego założenia indukcyjnego, że
dla wszystkich
(a nie tylko dla
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 : poprzednik implikacji jest trywialnie spełniony (dowolne naturalne
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 (
) 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 (kwadracików w czekoladzie), że niezależnie od kolejności wykonywanych cięć potrzeba i wystarcza dokładnie
cięć.
- Jeśli czekolada ma tylko
kawałek, to nie trzeba niczego dzielić, więc
cięć wystarcza,
- Gdy czekolada ma
kawałków, to pierwsze jej cięcie podzieli ją na dwa prostokąty o odpowiednio
i
kawałkach, przy czym
i
. Korzystając teraz z założenia indukcyjnego wiemy, że aby połamać te mniejsze kawałki potrzeba i wystarcza odpowiednio
i
cięć. W sumie wykonaliśmy więc
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 .
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
-elementowy zbiór koni. Wybierzmy dowolnego konia z tego zbioru i usuńmy go na chwilę. Na mocy założenia indukcyjnego
-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
-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
konie są jednej maści.
Gdzie jest błąd?
Wskazówka:

Rozwiązanie:


- 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 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 . 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 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 taki, że
, jeśli tylko
zawiera wszystkie liczby naturalne
, ale wbrew Zasadzie Indukcji Zupełnej
. Wtedy oczywiście zbiór
jest niepusty na podstawie Zasady Minimum ma element najmniejszy, powiedzmy
. Z minimalności
wiemy, że żadna z liczb
nie może być w
zatem wszystkie one są w
. Wtedy jednak, nasze założenie o zbiorze
gwarantuje, że również
, wbrew przypuszczeniu, że
.
Teraz z Zasady Indukcji Zupełnej wyprowadzimy Zasadę Indukcji Matematycznej.
Niech więc jakiś podzbiór spełnia
-
,
-
.
Aby dowieść, że ilekroć
, wystarczy pokazać, że zbiór
jest równy
. To z kolei uzyskamy, pokazując, że
spełnia założenia Zasady Indukcji Zupełnej. Istotnie, niech
będzie dowolną liczbą naturalna, taką że
zawiera wszystkie liczby naturalne
. Chcemy pokazać, że wtedy
. Z samej definicji zbioru
jest to oczywiste ilekroć
. Z założenia o zbiorze
jest to również oczywiste dla
. Gdy natomiast
to
. Ponadto,
jako liczba mniejsza od
, należy do
(bo
zawiera wszystkie liczby naturalne
). Ale
, więc
. Teraz wystarczy zastosować drugie założenie o zbiorze
, by wnosić, że
.
Kolejnym krokiem będzie wyprowadzenie Zasady Maksimum z Zasady Indukcji Matematycznej. Niech więc będzie zbiorem niepustym, ale ograniczonym od góry. Używając indukcji z uwagi na wielkość liczby
ograniczającej od góry zbiór
, pokażemy, że
ma element największy.
- Jeśli
, to ponieważ
, wiemy, że
. Wobec tego
jest elementem największym w
.
- Pracujemy przy założeniu indukcyjnym, mówiącym że każdy niepusty podzbiór zbioru
ograniczony przez
ma element największy. Chcemy dowieść, że jeśli
jest ograniczony przez
, to
ma element największy. Jeśli
, to
jest elementem największym w
, bo ogranicza
. Jeśli zaś
to
jest także ograniczony przez
, 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 . Jeśli
to
jest elementem najmniejszym w
. Załóżmy zatem, że
. Wtedy niech


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