Czym jest dowód

Dowody są kamieniami węgielnymi całej matematyki – dzięki dowodom możesz z kilku małych kamyczków zbudować całą piramidę, i to jeszcze do góry nogami.

Sens dowodów

Dowody mają w matematyce sens z kilku powodów. Najważniejszy jest ten, że bez dowodów nie jesteśmy w stanie potwierdzić żadnej myśli ani hipotezy, która przyjdzie nam do głowy. Moglibyśmy na przykład wierzyć, że liczb pierwszych jest skończenie wiele, ale jeśli nie mamy dowodu, jest to tylko puste stwierdzenie. Z drugiej strony także nieudowodnione twierdzenia mają w matematyce (i nie tylko) sens. Mówi się po prostu, że jeśli jest prawdziwe założenie, że liczb pierwszych jest skończenie wiele, to zachodzi… jakaś inna teoria.

Nie możemy się jednak potem dziwić, że ktoś po jakimś czasie udowodni, że liczb pierwszych jest nieskończenie wiele, jak pokażemy dalej, i cała nasza teoria rozsypie się jak domek z kart. Dzięki dowodom możemy więc budować domki z kart, które nie rozsypią się nigdy.

Dowodów uczy się w szkołach dlatego, że kto zrozumie dowód, zrozumie też dany materiał. Zwykle trudno jest dogłębnie rozumieć materiał, jeśli nie rozumie się dowodów. Słowo „rozumie się” zaznaczam całkowicie celowo: jeśli wykujesz dowody na pamięć dzień przed egzaminem, a następnego dnia tylko wyrzucisz je z siebie na kartkę, to wcale nie jesteś bliżej zrozumienia tematu.

Dowody odpowiadają więc przy nauce jakiegoś materiału na pytanie „dlaczego to tak działa?”. Jeśli zrozumiesz, dlaczego dana rzecz działa, łatwiej ją zapamiętasz i po czasie będziesz ją rozumieć zdecydowanie lepiej niż ktoś, kto uczył się według zasady „zakuć, zdać, zapomnieć”. Pytanie tylko, czy taki jest twój cel.

Czym jest dowód

Czym jest dowód, definiuje się formalnie w logice matematycznej, na przykład za pomocą wynikania syntaktycznego, ale nam wystarczy dużo prostsza definicja.

Na początku każdego dowodu musimy mieć twierdzenie, które chcemy udowodnić. Oznaczymy je magicznym symbolem $\phi$. To grecka litera, którą czytamy „fi”. Dalej będziemy potrzebować jakiegoś zbioru aksjomatów i założeń, oznaczymy go Ax, za pomocą których udowodnimy twierdzenie $\phi$. Zbiór aksjomatów to coś, co już wiemy, o czym zakładamy, że jest prawdziwe. Mogą to być rzeczy takie jak na przykład „każda liczba parzysta jest podzielna przez dwa”. Zbiór ten może też zawierać na przykład wzory na przekształcanie wyrażeń, które zostały udowodnione gdzieś obok i o których już zakładamy, że są prawdziwe, na przykład:

$$(a+b)^2=a^2+2ab+b^2;\qquad a,b\in\mathbb{R}$$

Teraz będziemy stopniowo przekształcać twierdzenia ze zbioru Ax tak długo, aż otrzymamy twierdzenie $\phi$. Wszystkie przekształcenia muszą być logicznie poprawne, muszą być zgodne z podstawami rachunku zdań. Na przykład gdybyśmy chcieli udowodnić poprzedni wzór, postąpimy tak, że wyrażenie

$$(a+b)^2$$

będziemy przekształcać przekształceniami równoważnymi, aż otrzymamy wyrażenie z prawej strony. Pokażę to:

$$(a+b)^2=(a+b)\cdot(a+b)=a\cdot a+a\cdot b + b\cdot a + b\cdot b=$$

$$=a\cdot a+2ab+b\cdot b=a^2+2ab+b^2$$

W pierwszym kroku rozpisaliśmy potęgę jako iloczyn, w drugim kroku wymnożyliśmy nawiasy, w trzecim kroku dodaliśmy jednakowe wyrazy, a w ostatnim kroku zapisaliśmy iloczyn jako potęgę. Każdy krok był jakimś elementarnym przekształceniem, na które mogliśmy sobie pozwolić, przy czym zakładamy, że każde z tych elementarnych przekształceń należy do zbioru Ax.

Ważne jest, że każde przekształcenie musi być poprawne, musi wynikać z czegoś, co już znamy. Dowód matematyczny jest trochę jak ewolucja – stopniowymi małymi zmianami dochodzimy od jednego wyrażenia do innego.

Dowody trywialne

Dowód trywialny (albo dowód oczywisty) to terminus technicus na dowód, który nie zmieścił się na tablicy, więc się go pomija, a student uczy się go ze skryptu w ramach pracy domowej. :-) A teraz poważnie – dowody trywialne to takie dowody, które zwykle wynikają z jakiejś definicji w jednym trywialnym kroku.

Pokażmy to na przykładzie: weźmy zbiór liczb naturalnych, czyli zbiór liczb ℕ = {1, 2, 3, …} (w tym artykule bez zera – w polskiej szkole zalicza się do nich często także 0). Możemy teraz powiedzieć, że każdy ułamek postaci:

$$\frac{q}{p}; \qquad q,p\in\mathbb{N}$$

jest poprawnym ułamkiem, czyli nie znajdziemy żadnej pary liczb q, p, dla której ten ułamek nie miałby sensu. Jak byśmy to udowodnili? Najpierw musimy ustalić, kiedy ułamek nie ma sensu. Ułamek nie ma sensu, gdy w mianowniku jest zero (nie można dzielić przez zero). Musimy więc udowodnić, że p≠0 dla wszystkich możliwych p. Wiemy jednak, że p bierzemy z liczb naturalnych, które zdefiniowaliśmy jako ℕ = {1, 2, 3, …}. Zbiór liczb naturalnych nie zawiera zera, więc liczba p będzie zawsze różna od zera.

$$\forall p\in\mathbb{N}: p\ne 0$$

I dowód mamy za sobą. Wiemy, że jeśli licznik i mianownik ułamka będą liczbami naturalnymi, ułamek będzie poprawny.

Dowody trywialne zwykle rzeczywiście są trywialne, ale tylko wtedy, gdy znasz otaczający je kontekst. Na przykład jeśli nie rozumiesz pojęcia zbioru albo nie wiesz, co to znaczy, że p jest elementem zbioru ℕ, to nawet ten dowód nie był dla ciebie trywialny. Dowody trywialne wyróżniają się więc nie tyle tym, że są proste, ile raczej tym, że są krótkie i wynikają w prosty sposób z jakiegoś (dowolnie trudnego) kontekstu.

Kontrprzykład

Kontrprzykład to chyba najprostszy sposób na wykazanie, że dane twierdzenie nie jest prawdziwe. Ważne jest to słowo „nie”. Kontrprzykład może wskazać przypadek, w którym podane zdanie nie zachodzi, ale ogólnie żadna liczba przykładów nie wystarczy, gdy w grę wchodzi nieskończenie wiele elementów, które możemy sprawdzać.

Przykład: „każda liczba naturalna jest większa od dziesięciu”. W jaki sposób wykażemy, że to nieprawda? Kontrprzykładem do naszego twierdzenia jest na przykład liczba pięć. Pięć jest liczbą naturalną i nie jest większa od dziesięciu. Twierdzenia nie możemy natomiast udowodnić, wymieniając kilka liczb naturalnych większych od dziesięciu. Nie możesz powiedzieć „liczby naturalne 11, 12, 13, 123 i 5345 są większe od 10, więc to zdanie jest prawdziwe”. Tak się nie da. Wybraliśmy tylko kilka przykładów, dla których nasze twierdzenie zachodzi, ale to nic nie mówi o pozostałych liczbach, o których w ogóle nie wspomnieliśmy.

Drugi przykład: każdy mężczyzna wyższy niż dwa metry ma brązowe albo niebieskie oczy. Zakładam, że mało kto potrafi znaleźć kontrprzykład. Co nam to mówi o tym zdaniu? Cóż, zupełnie nic. Jeśli nie potrafimy znaleźć kontrprzykładu, nie musi to oznaczać, że zdanie jest prawdziwe. Kontrprzykład może gdzieś istnieć, tylko akurat nie potrafimy go znaleźć. Nieumiejętność znalezienia kontrprzykładu nie dowodzi, że dane twierdzenie jest prawdziwe.

Dowód wprost

Podstawowym rodzajem dowodu jest dowód wprost. Postępujemy po prostu zgodnie z definicjami i przekształcamy wyjściowe zdanie, aż otrzymamy zdanie, które chcemy otrzymać. Zwykle chcemy udowodnić zdanie w postaci implikacji $A\Rightarrow B$, gdzie A jest jakimś punktem wyjścia, założeniem, a B jest zdaniem, które chcemy wyprowadzić, udowodnić. Jeśli prawdziwe jest zdanie A, to prawdziwe jest zdanie B. Często mamy dane tylko zdanie B, czyli to, co chcemy udowodnić, a zdanie A musimy sami odpowiednio wybrać.

Następnie za pomocą implikacji wyprowadzamy kolejne zdania, a ostatnim z nich jest zdanie B. Schematycznie można to zapisać tak:

$$A\Rightarrow A_1\Rightarrow A_2\Rightarrow A_3\Rightarrow\ldots \Rightarrow A_n \Rightarrow B$$

Jako przykład udowodnimy, że prawdziwe jest zdanie

$$a>1\Rightarrow a^2>1$$

Teraz krok po kroku:

1. Ponieważ a>1, to na pewno również a>0 i również a≠0 (właściwie tylko osłabiamy warunek).
2. Ponieważ a nie jest równe zeru i jest dodatnie, możemy bez obaw pomnożyć całą nierówność przez a. Gdyby a było równe zeru, nierówność ostra by się nie zachowała (otrzymalibyśmy 0>0), a gdyby było ujemne, musielibyśmy odwrócić znak nierówności. Po pomnożeniu przez a otrzymujemy wyrażenie a²>a.
3. W tej chwili wiemy, że a>1, i jednocześnie wiemy, że a²>a. Jeśli połączymy te dwa wyrażenia, otrzymamy: a²>a>1.
4. Teraz wystarczy usunąć środkowe wyrażenie i mamy a²>1. Mogliśmy sobie na to pozwolić, bo a jest większe od jedynki, a a² jest większe od a. Jeśli a² jest większe od a, a a jest jednocześnie większe od jedynki, to a² jest na pewno większe od jedynki.

Symbolicznie moglibyśmy to zapisać tak:

$$a>1\Rightarrow a>0 \Rightarrow a^2>a \Rightarrow a^2>a>1 \Rightarrow a^2>1.$$

Dowód przez kontrapozycję

Dowód przez kontrapozycję w większym stopniu korzysta z własności implikacji. Jeśli mamy udowodnić twierdzenie w postaci $A\Rightarrow B$, możemy skorzystać z implikacji przeciwstawnej (kontrapozycji) i udowodnić

$$\neg B \Rightarrow \neg A.$$

Takie postępowanie bywa czasem wygodniejsze niż na przykład dowód wprost. Podobny sposób wykorzystuje dowód nie wprost (przez sprzeczność), do którego można sprowadzić każdy dowód przez kontrapozycję. W polskich podręcznikach dowód przez kontrapozycję często zalicza się zresztą także do dowodów nie wprost. Spróbujmy przez kontrapozycję udowodnić twierdzenie

$$a-b=0\Rightarrow a=b.$$

Teraz utworzymy implikację przeciwstawną:

$$\begin{eqnarray} \neg(a=b)&\Rightarrow&\neg(a-b=0)\\ a\ne b&\Rightarrow&a-b\ne0 \end{eqnarray}$$

Jeśli a≠ b, możemy rozłożyć b na sumę b = a + x, gdzie x oznacza odległość liczby b od liczby a. Wyrażenie zmieni się tak:

$$a\ne (a+x)\Rightarrow a-(a+x)\ne0;\quad x\ne0$$

Odejmiemy te zmienne a, które się da:

$$0\ne x\Rightarrow -x\ne 0; \quad x\ne0$$

Ponieważ x≠0, jest też −x≠0, więc implikacja jest prawdziwa. Twierdzenie jest udowodnione, a tym samym prawdziwe jest też wyjściowe zdanie

$$a-b=0\Rightarrow a=b.$$

Innymi technikami dowodzenia są na przykład wspomniany już dowód nie wprost albo dowód indukcyjny.