Matematyka dyskretna 1/Wykład 1: Indukcja

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

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

Francesco Maurolico (1494-1575)
Zobacz biografię

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:

dla

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ę



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ę



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. .

Domino md.jpg

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


dla


przeprowadźmy dowód indukcyjny:

  • Pokażemy najpierw, że (dla zupełnie dowolnego )
    • oczywiście
    • oraz
  • a następnie
    • zauważamy, że
    • oraz, ż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 .

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

Przykład

{{{3}}}

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


dla dowolnego


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ść.

End of proof.gif