Twierdzenia i dowody

Każdy dowód dotyczy pewnego twierdzenia. Praktycznie zawsze składają się one z dwóch części: założenia i tezy. Założenie mówi jakich obiektów dotyczy dana reguła, a teza mówi jaką własność te obiekty mają spełniać. Przykłady twierdzeń są następujące (znakiem | pokazane jest miejsce podziału pomiędzy założeniem, a tezą):

• Każdy trójkąt prostokątny o przyprostokątnych długości a,b | ma przeciwprostokątną długości \(\sqrt{a^2+b^2}\).

• Jeśli liczba p jest pierwsza, a m jest dowolną liczbą całkowitą, | to liczba m^p − m jest podzielna przez p

• Dla każdego wielościanu wypukłego, o W wierzchołkach, S ścianach i K krawędziach, | zachodzi wzór W + S = K + 2.

Jeśli teza nie wynika z założeń, mówimy że twierdzenie jest fałszywe. Jeden z przykładów jest następujący:

Jeśli liczba a jest dodatnia, to jest równa 7.

Twierdzenie to jest fałszywe, bo na przykład liczba a = 5 jest dodatnia (czyli spełnia założenia), ale nie jest równa 7 (czyli nie spełnia tezy). Ten przykład jest bardzo prosty, ale często jest bardzo trudno określić, czy dane twierdzenie jest prawdziwe, czy fałszywe.

Jeśli twierdzenie jest fałszywe, nie można go w żaden sposób poprawnie udowodnić. Jeśli natomiast jest prawdziwe, wtedy różnych dowodów może być wiele. Taka sytuacja ma miejsce w przykładzie 2 poniżej.

Przykład 1

Udowodnimy w bardzo szczegółowy sposób następujące twierdzenie.

Dowód:

1. Rozważmy dowolne liczby rzeczywiste a,b.
2. Pokażemy, że \(a^2+b^2\geq 2ab\).
3. Zauważmy, że nierówność \(a^2+b^2\geq 2ab\) jest równoważna nierówności \(a^2+b^2-2ab\geq 0\), bo wiemy że od obu stron nierówności można odjąć tę samą liczbę i uzyskać nierówność równoważną.
4. Wobec tego wystarczy, że pokażemy, że \(a^2+b^2-2ab\geq 0\).
5. Ale lewa strona tej nierówności jest równa (a − b)², korzystając ze wzoru skróconego mnożenia.
6. Więc wystarczy pokazać, że \((a-b)^2\geq 0\).
7. Oznaczmy jako c wartość a − b.
8. Wobec tego, aby zakończyć dowód wystarczy pokazać, że \(c^2 \geq 0\).
9. Rozpatrzmy trzy przypadki:
   1. c > 0: wtedy \(c^2=c\cdot c> 0\), bo liczba dodatnia pomnożona przez liczbę dodatnią, daje liczbę dodatnią.
   2. c = 0: wtedy c² = 0, czyli w szczególności \(c^2\geq 0\).
   3. c < 0: wtedy \(c^2=c\cdot c\) jest iloczynem dwóch liczb ujemnych, więc jest liczbą dodatnią. Więc c² > 0.
10. Więc, niezależnie od tego czy c jest dodatnie, zero, czy ujemne, zawsze zachodzi \(c^2\geq 0\).
11. Więc wykazaliśmy to co trzeba było sprawdzić, by wiedzieć że \(a^2+b^2\geq 2ab\).

Omówienie

Najpierw zwróćmy uwagę na sformułowanie twierdzenia. Po pierwsze mówi ono dokładnie jakich liczb a,b dotyczy to twierdzenie (w tym przypadku wszystkich liczb rzeczywistych), czyli ma opisane założenia. Po drugie zostaje dobrze określona własność jaką dowodzimy (w tym przypadku jest to pewna nierówność), czyli teza. Tak sformułowane twierdzenie jest ścisłe i jednoznaczne. Dzięki temu, każdy kto wie czym są liczby i co oznacza nierówność, wie dokładnie co to twierdzenie mówi.

Teraz spójrzmy na dowód. Został on napisany w postaci kroków.

• Pierwszy krok mówi intuicyjnie jeśli twierdzenie ma być spełnione dla wszystkich liczb a,b to wystarczy jak rozważymy dowolne takie liczby i dla nich udowodnimy, że zachodzi teza. Jest to najbardziej bezpośrednia metoda dowodzenia twierdzeń, mówiąca: rozważmy obiekty o których wiemy tylko tyle ile mówią założenia, pokażmy dla nich, że zachodzi teza. Są też bardziej skomplikowane metody, ale o tym potem.

• Następnie, teza którą chcemy pokazać jest zmieniana na kolejne warunki równoważne. W trakcie tych zmian korzystamy z różnych praw (np. o odejmowaniu tej samej liczby od obu stron równości). Warto zawsze precyzyjnie określić z jakiego prawa korzystamy.

• W kroku 7 wprowadzamy pomocnicze oznaczenie, które uprości dalszą część rozumowania.

• Krok 9 pokazuje tzw. rozumowanie przez przypadki. Sprawdzamy wszystkie możliwości jakie mogą zachodzić (w tej sytuacji są trzy). Jeśli dla każdej z nich uda nam się pokazać, że zachodzi jakaś własność, to zachodzi ona zawsze.

• Krok 11 podsumowuje całe rozumowanie.

Przykład 2

Twierdzenie to jest udowodnione z użyciem indukcji matematycznej w dziale 1. Indukcja. Poniżej znajduje się inne, ale również poprawne rozumowanie.

Dowód:

1. Rozpatrzmy dwie możliwości:
   1. Powyższe twierdzenie zachodzi dla wszystkich liczb naturalnych \(n\geq 1\).
   2. Istnieje jakaś liczba \(n\geq 1\), dla której twierdzenie nie zachodzi.
2. Jeśli ma miejsce pierwsza możliwość, twierdzenie jest prawdziwe. Rozważmy, co by było gdyby zachodziła druga z nich.
3. Mielibyśmy wtedy pewną liczbę \(n\geq 1\) dla której odpowiednia równość nie zachodzi.
4. Załóżmy, że \(m\geq 1\), to najmniejsza ze wszystkich liczb większych równych 1, dla których twierdzenie nie zachodzi.
5. Są kolejne dwa przypadki:
   1. m = 1, ale wtedy wzór ma postać \(1=\frac{1(1+1)}{2}=1\), więc zachodzi. Więc ta sytuacja nie może mieć miejsca, więc m > 1.
   2. m > 1, ten przypadek pozostaje.
6. Czyli \(m-1\geq 1\) i dla m − 1 wzór zachodzi, bo m jest najmniejszą liczbą dla której nie zachodzi.
7. Czyli \(1+2+\ldots+(m-1)=\frac{(m-1)(m-1+1)}{2}=\frac{m(m-1)}{2}\).
8. Ale wtedy możemy do obu stron równości dodać m, otrzymując \(\left(1+2+\ldots+(m-1)\right)+m=\frac{m(m-1)}{2}+m\).
9. Czyli (wciągając m nad kreskę ułamka i rozpisując) dostajemy \(1+2+\ldots+m=\frac{m(m-1)}{2}+m=\frac{m(m-1)+2m}{2}=\frac{m^2-m+2m}{2}=\frac{m^2+m}{2}=\frac{m(m+1)}{2}\).
10. Ale to jest dokładnie wzór z twierdzenia, dla m.
11. Czyli twierdzenie zachodzi dla m.
12. Ale w przypadku który rozpatrujemy, założyliśmy że twierdzenie nie zachodzi dla m. Czyli mamy sprzeczność!
13. Skoro tak, to w takim razie rozpatrywany przypadek w ogóle nie może mieć miejsca - nie może istnieć żadna liczba dla której twierdzenie by nie zachodziło.
14. Czyli ma miejsce przypadek 1.1 i twierdzenie zachodzi dla wszystkich liczb.

Omówienie

Strategia dowodzenia tego twierdzenia różni się znacznie od poprzedniego. Zamiast wziąć liczbę \(n\geq 1\) podaną w założeniach twierdzenia i dla niej pokazać wzór, robimy coś zupełnie innego. W istocie korzystamy z zasad logiki i tworzymy tzw. rozumowanie przez sprowadzenie do absurdu (nazywane też dowodem nie wprost). Mianowicie dopuszczamy sytuację w której twierdzenie by nie zachodziło i poprzez kolejne kroki dochodzimy do sprzeczności. A skoro tak, to twierdzenie musi zawsze zachodzić.

• W pierwszym kroku robimy rozumowanie przez przypadki, przy czym rozpatrywane przypadki to prawdziwość (lub nieprawdziwość) twierdzenia.
• Przypadek twierdzenie jest prawdziwe oczywiście nas satysfakcjonuje. Wobec tego zakładamy na chwilę, że nie ma on miejsca.
• W kroku 4, w oparciu o założenie że twierdzenie jest fałszywe dla pewnego \(n\geq 1\), wybieramy najmniejsze możliwe takie n i oznaczamy je m.
• W kroku 5 rozpatrujemy kolejne dwa przypadki, czy m = 1, czy m > 1. Pierwsza możliwość nie może zachodzić, więc jeśli w ogóle takie m ma istnieć, to musi być m > 1.
• W kroku 6 korzystamy z tego jak powstała liczba m. Mianowicie jest ona NAJMNIEJSZĄ liczbą dla której twierdzenie nie zachodzi. Więc dla wszystkich mniejszych musi być ono prawdziwe. W szczególności dla liczby m − 1.
• W krokach 7-9 prowadzimy zwykłe rozumowanie wykorzystując różne prawa przekształcania równań.
• W kroku 10 okazuje się, że (ciągle przy założeniu, że twierdzenie nie zachodzi dla m) udało nam się pokazać, że twierdzenie zachodzi dla m. Czyli sprzeczność. Czyli przypadek, że dla jakiejś liczby twierdzenie nie zachodzi nie może mieć miejsca.
• Czyli jedyny przypadek jaki może zajść jest taki, że dla wszystkich liczb n, wzór z twierdzenia jest prawdziwy.
• Znaczy to dokładnie tyle, że twierdzenie jest prawdą.

Wnikliwy czytelnik dostrzeże analogie pomiędzy powyższym rozumowaniem, a rozumowaniem przez indukcję. Jednak tutaj, zamiast powołać się na zasadę indukcji matematycznej, prowadzimy zupełnie samodzielnie rozumowanie, opierając się tylko na prawach logiki. Uzyskany w ten sposób dowód ma wcale nie trywialną strukturę, w której pewne założenia są przyjmowane tylko tymczasowo, by ostatecznie pokazać, że są niedorzeczne. Bardzo wiele twierdzeń w tzw. matematyce wyższej ma podobnie, lub nawet bardziej skomplikowaną strukturę rozumowania. To właśnie logika matematyczna mówi, które struktury dowodów są poprawne i podaje różnorodne prawa z których można korzystać konstruując taki dowód.