Dowód nie wprost

Dowód nie wprost, nazywany też dowodem przez sprzeczność, to popularna technika dowodzenia. Jeśli chcemy udowodnić, że jakieś zdanie jest prawdziwe, tworzymy jego zaprzeczenie (negację), zakładamy, że to zaprzeczenie jest prawdziwe, i próbujemy dojść do jakiejś sprzeczności. Celem jest pokazać, że przyjęte przez nas założenie prowadzi do jakiegoś absurdu.

Prosty przykład

Weźmy twierdzenie „nie istnieje najmniejsza dodatnia liczba wymierna”. Udowodnimy je nie wprost w ten sposób, że najpierw zapiszemy jego zaprzeczenie: „istnieje najmniejsza dodatnia liczba wymierna” – oznaczmy ją q. Jeśli q jest najmniejszą dodatnią liczbą wymierną, to nie da się znaleźć mniejszej dodatniej liczby wymiernej – bo wtedy liczba q nie byłaby najmniejsza.

Wykorzystamy to przy szukaniu sprzeczności. Jeśli jednak znajdziemy liczbę mniejszą od q, przy czym tę rzekomo najmniejszą liczbę możemy wybrać dowolnie, dojdziemy do sprzeczności i zaprzeczone twierdzenie nie jest prawdziwe. Jeśli za najmniejszą liczbę wybierzemy na przykład 0,1, to widzimy, że liczba 0,01 jest mniejsza. Dalej 0,001 jest jeszcze mniejsza, 0,0001 znowu mniejsza i tak dalej. Wystarczy daną liczbę q podzielić przez dziesięć i dostaniemy liczbę mniejszą. W zasadzie wystarczy ją podzielić przez dowolną liczbę większą od jedynki, na przykład przez dwa – połowa liczby q będzie na pewno mniejsza niż cała liczba q.

Liczba q/2 jest więc na pewno mniejsza od q i jednocześnie jest dodatnią liczbą wymierną. Doszliśmy tym samym do sprzeczności z zaprzeczonym twierdzeniem, czyli zaprzeczone twierdzenie nie jest prawdziwe, a zatem prawdziwe jest wyjściowe twierdzenie.

Ciekawe liczby

Klasycznym żartobliwym dowodem, który ilustruje zasadę sprzeczności, jest następujący przykład. Załóżmy, że istnieją liczby naturalne, które są w jakiś sposób ciekawe. Na przykład liczba 2 jest ciekawa, bo zachodzi 2 · 2 = 2 + 2, a to dość nietypowa własność. Liczba 42 jest ciekawa, bo według „Autostopem przez Galaktykę” jest odpowiedzią na wszystko. I tak dalej. Pytanie brzmi – czy istnieje nieskończenie wiele ciekawych liczb?

Załóżmy, że jest odwrotnie, czyli że istnieje tylko skończenie wiele ciekawych liczb, a niektóre liczby są nieciekawe. Te nieciekawe liczby naturalne zbierzemy w zbiór liczb nieciekawych. Teraz wybierzemy najmniejszą nieciekawą liczbę. Chwileczkę, najmniejsza nieciekawa liczba? To brzmi całkiem ciekawie, prawda? :-)

Doszliśmy tym samym do sprzeczności, bo najmniejsza nieciekawa liczba jest w rzeczywistości całkiem ciekawa, więc nie może istnieć najmniejsza nieciekawa liczba, a co za tym idzie, zbiór liczb nieciekawych musi być pusty.

To oczywiście nonsens, bo nie zdefiniowaliśmy porządnie, czym jest ciekawa liczba, ale sam sposób dowodzenia jest w porządku.

Dowód, że liczb pierwszych jest nieskończenie wiele

W tym przykładzie pokażemy podobne rozumowanie jak w poprzednim rozdziale, ale tym razem będzie ono poprawne pod każdym względem.

Liczba pierwsza to liczba, która jest podzielna tylko przez dwie różne liczby – przez samą siebie i przez jedynkę. Zauważ, że jedynka tej definicji nie spełnia, a dwójka spełnia.

Rozkład na czynniki pierwsze, czyli faktoryzacja, to zapisanie liczby naturalnej (oprócz jedynki) jako iloczynu liczb pierwszych. To całkiem ciekawa własność liczb naturalnych. Jakąkolwiek liczbę naturalną weźmiesz (oprócz jedynki), da się ją rozłożyć na iloczyn kilku (także jednakowych) liczb pierwszych. Przykłady:

$$\begin{eqnarray} 8&=&2\cdot2\cdot2\\15&=&3\cdot5\\26&=&2\cdot13\\1800&=&2^3\cdot3^2\cdot5^2 \end{eqnarray}$$

Twierdzenie o rozkładzie na czynniki pierwsze nazywa się zasadniczym twierdzeniem arytmetyki. Mówi nam między innymi, że taki rozkład jest jednoznaczny, czyli nie znajdziemy dwóch różnych rozkładów na czynniki pierwsze jednej liczby naturalnej. Ponadto tylko liczby pierwsze mają rozkład złożony z jednej jedynej liczby – z nich samych. Rozkładem siódemki byłaby więc liczba siedem. Z tych faktów skorzystamy, budując dowód następującego twierdzenia.

Teraz udowodnimy twierdzenie „liczb pierwszych jest nieskończenie wiele”. Znowu zapisujemy jego zaprzeczenie: „liczb pierwszych jest skończenie wiele”. Załóżmy, że ciąg liczb

$$a_1, a_2, a_3,,\ldots,a_n$$

zawiera wszystkie istniejące liczby pierwsze. Jeśli w tym ciągu są wszystkie liczby pierwsze, to na pewno nie da się już znaleźć liczby, która byłaby pierwsza i jednocześnie nie należała do tego ciągu. Wszystkie liczby pierwsze mamy w ciągu, poza ciągiem nie może już wystąpić żadna liczba pierwsza.

Jeśli chcemy dojść do sprzeczności, musimy więc skonstruować jakąś liczbę pierwszą, której w tym ciągu nie ma. Pomoże nam w tym liczba q. Zbudujemy ją tak, że pomnożymy wszystkie liczby pierwsze z ciągu i dodamy jedynkę:

$$q=a_1 \cdot a_2 \cdot a_3 \cdot \ldots \cdot a_n+1$$

Teraz musimy pokazać, że ta liczba albo jest liczbą pierwszą, albo w jakiś sposób daje nową liczbę pierwszą. Wiemy, że q jest liczbą naturalną i że każdą liczbę naturalną można zapisać jako iloczyn liczb pierwszych. Żadna liczba pierwsza a_i nie dzieli jednak liczby q bez reszty, zawsze zostaje reszta jeden. Gdybyśmy spróbowali podzielić liczbę q na przykład przez liczbę pierwszą a₂, wyszłoby nam tak:

$$\frac{a_1 \cdot a_2 \cdot a_3 \cdot \ldots \cdot a_n+1}{a_2}=\frac{a_1 \cdot a_2 \cdot a_3 \cdot \ldots \cdot a_n}{a_2}+\frac{1}{a_2}=$$

$$=a_1 \cdot a_3 \cdot a_4 \cdot \ldots \cdot a_n+\frac{1}{a_2}$$

Najpierw rozdzielamy ułamek na dwa. W pierwszym ułamku skracamy a₂ i zostaje nam jakiś iloczyn liczb pierwszych, czyli po prostu jakaś inna, nieistotna liczba całkowita. W drugim ułamku nie ma czego skracać, ten ułamek będzie zawsze liczbą niecałkowitą (bo mianownik nie może być równy jeden, jedynka nie jest liczbą pierwszą). W sumie dostaniemy więc liczbę, która nie jest całkowita, czyli liczba pierwsza a₂ nie dzieli liczby q.

Udowodniliśmy w ten sposób, że żadna z liczb pierwszych z ciągu a_n nie dzieli liczby q. (Uwaga: pokazaliśmy to wprawdzie tylko dla a₂, ale łatwo to uogólnić, jeśli zamienimy a₂ na ogólne a_i.) Ponieważ jednak każdą liczbę naturalną da się rozłożyć na iloczyn liczb pierwszych, muszą istnieć inne liczby pierwsze, których nie ma w ciągu a_n, ale które tworzą rozkład liczby q. Sama liczba q może przy tym spokojnie być liczbą pierwszą i wtedy jej rozkład będzie się składał tylko z liczby q. Jeszcze raz więc ostatni tok rozumowania:

1. Każdą liczbę naturalną można zapisać jako jakiś iloczyn liczb pierwszych.
2. Zgodnie z założeniem ciąg a_n zawiera wszystkie istniejące liczby pierwsze.
3. Przekształcamy pierwsze twierdzenie tak, że każdą liczbę naturalną można zapisać jako iloczyn wybranych wyrazów ciągu a_n, bo ten zawiera wszystkie liczby pierwsze.
4. Udowodniliśmy, że żadna liczba z ciągu a_n nie dzieli liczby q.
5. Powstała w ten sposób sprzeczność z założeniem $\rightarrow$ jeśli każdą liczbę naturalną musimy umieć rozłożyć na iloczyn liczb pierwszych, a ciąg a_n nie zawiera żadnej liczby, która dzieli q, to muszą istnieć inne liczby pierwsze, które dzielą q i tworzą rozkład liczby q na czynniki pierwsze.

W ten sposób doszliśmy do sprzeczności. Rozkład liczby q na czynniki pierwsze zawiera liczby pierwsze, których nie ma w ciągu, o którym zakładaliśmy, że zawiera wszystkie liczby pierwsze. Zaprzeczone twierdzenie jest więc fałszywe, a prawdziwe jest wyjściowe twierdzenie. Liczb pierwszych jest nieskończenie wiele.