Strasznie nie lubię dowodów nie wprost,
bo polegają one na tym,
że człowiek opowiada cały czas jakieś bzdury,
aż dojdzie do takiej bzdury,
że wszyscy już się zgadzają,
że tak dalej być nie może.
(Niezidentyfikowany matematyk
wedle miesięcznika ,,Delta”)
Uwagi wstępne
Jak wiadomo, podstawową umiejętnością matematyka jest dowodzenie twierdzeń. Dowodzenie polega na wyprowadzaniu jednych prawd matematycznych z innych prawd, czy ogólniej − wyprowadzaniu jednych zdań z innych zdań.
Za dowód matematyczny uznaje się ciąg rozumowań, w którym przesłankami są jakieś zdania uznane za prawdziwe: aksjomaty czy wcześniej udowodnione twierdzenia, a jedynymi dopuszczalnymi regułami wnioskowania są reguły logiczne. Czasem jednak problem polega na wyprowadzaniu wniosków z przyjętej hipotezy czy aksjomatu, którego prawdziwość jest dyskusyjna1. Wówczas oczywiście taką hipotezę czy aksjomat bierze się za przesłankę dowodu.
Szczególnym rodzajem dowodu jest dowód nie wprost, zwany niekiedy w tradycyjnej logice dowodem apagogicznym. Polega on na tym, ogólnie rzecz biorąc, że zakłada się, iż dowodzone twierdzenie iest fałszywe i pokazuje, ze założenie to prowadzi do sprzeczności. Takie ujęcie spotyka się w elementarnych podręcznikach logiki i metodologii nauk oraz w encyklopediach. Poza ogólnikami i trywialnymi przykładami nie napotkałem tam jednak na żadne sensowne przykłady matematycznych dowodów nie wprost. Warto być może przyjrzeć się bliżej temu pojęciu i zadać pytanie, co to znaczy, że ,,założenie, iż twierdzenie jest fałszywe prowadzi do sprzeczności”, a w szczególności zobaczyć, jak pojęcie to fukcjonuje w praktyce matematycznej. Warto też odpowiedzieć na pytanie, jak wygląda rozumowanie, podstawie którego dochodzi się do wniosku, że skoro założenie o fałszywości twierdzenia prowadzi do sprzeczności, to twierdzenie musi być prawdziwe.
Poniżej przedstawię kilka uwag na ten temat.
Dlaczego wykazanie sprzeczności kończy dowód?
Wszyscy godzą się z tym, że dowód nie wprost dla danego twierdzenia kończymy, gdy napotka się na parę zdań sprzecznych, to jest takich, z których jedno jest negacją drugiego. Poniżej pokażemy na przykładzie prostych dowodów matematycznych, dlaczego dowód taki można w tym momencie uznać za zakończony.
Istnieją przynajmniej trzy rodzaje dowodów nie wprost.
Pierwszy rodzaj polega na doprowadzeniu do sprzeczności ze zdaniem, będącym założeniem dowodu nie wprost, głoszącym że dowodzone twierdzenie jest fałszywe.
Twierdzenie 1 (Twierdzenie Euklidesa). Liczb pierwszych jest nieskończenie wiele.
Dowód. Załóżmy (jest to założenie dowodu nie wprost), że istnieje taka liczba naturalna \(n\), że liczb pierwszych jest tylko \(n\). Niech więc \(p_1, p_2, \ldots p_n\) będą wszystkimi liczbami pierwszymi. Rozważmy liczbę \(m = p_1\cdot p_2\cdot \ldots \cdot p_n + 1\). Jest ona większa od wszystkich liczb \(p_1, p_2, \ldots p_n\). Dalej, nie jest podzielna przez żadną z tych liczb, bo gdyby była podzielna np. przez \(p_n\), to liczba \(1 = m – p_1\cdot p_2\cdot \ldots \cdot p_n\) też byłaby podzielna przez \(p_n\). Stąd \(m\) jest liczbą pierwszą, różną od wszystkich liczb \(p_1, p_2, \ldots p_n\). Zatem nieprawda, że liczb pierwszych jest tylko \(n\).
W dowodzie tym założeniem dowodu nie wprost jest, że istnieje taka liczba naturalna \(n\), że liczb pierwszych jest \(n\). Z tego wyprowadzamy wniosek, że nieprawda, iż istnieje tylko \(n\) liczb pierwszych. Tezę twierdzenia, że nie istnieje taka liczba naturalna \(n\), iż liczb pierwszych jest \(n\) (tzn. liczb pierwszych jest nieskończenie wiele) dostajemy za pomocą twierdzenia Claviusa:
\[
(\phi \rightarrow \neg \phi) \rightarrow \neg \phi
\]
i reguły odrywania.
Drugi rodzaj polega na doprowadzeniu do sprzeczności zdania będącego założeniem dowodu nie wprost z jakimś znanym już twierdzeniem matematycznym.
Najprostszym przykładem takiego dowodu będzie dowód następującego twierdzenia.
Twierdzenie 2. Jeśli kwadrat liczby naturalnej \(n\) jest podzielny przez liczbę pierwszą \(p\), to \(n\) jest też podzielna przez \(p\).
Dowód. Wprowadzając skrót \(k|l\) dla zwrotu ,,\(k\) dzieli \(l\)” można tezę twierdzenia zapisać formalnie w postaci: \(p |n^2 \Rightarrow p|n\).
Załóżmy (jest to założenie dowodu nie wprost), że istnieją liczby \(n_{0}\) i \(p_{0}\) takie, że co prawda \(p_{0} | n_{0}^{2}\), ale fałszem jest, że \(p_{0}|n_{0}\), tzn. że implikacja: \(p_{0} | (n_{0}\cdot n_{0}) \Rightarrow p_{0}|n_{0}\) jest fałszywa.
Z teorii liczb wiadomo jednak, ze jeśli liczba pierwsza \(q\) dzieli iloczyn dwóch liczb, to dzieli przynajmniej jedną z tych dwu liczb. Wobec tego zgodnie z tym twierdzeniem, dla liczb \(p_{0}\) i \(n_{0}\) zachodzi implikacja: \(p_{0}|(n_{0}\cdot n_{0}) \Rightarrow p_0 |n_{0}\). Doszliśmy zatem do sprzeczności z pewnym twierdzeniem teorii liczb.
Rozumowanie więc wygląda tak: gdyby fałszem było, iż \(p |n^2 \Rightarrow p|n\), to by fałszem było \(p_{0}|(n_{0}\cdot n_{0}) \Rightarrow p_0 |n_{0}\). Ponieważ jednak prawdą jest, że \(p_{0}|(n_{0}\cdot n_{0}) \Rightarrow p_0 |n_{0}\), więc prawdą będzie, \(p |n^2 \Rightarrow p|n\).
Tezę twierdzenia, że \(p |n^2 \Rightarrow p|n\) dostajemy za pomocą prawa
\[
[(\neg \phi \rightarrow \neg \psi) \wedge \psi ] \rightarrow \phi
\]
oraz reguły odrywania: za \(\phi\) bierzemy \(p |n^2 \,\Rightarrow \, p|n\), a za \(\psi\) − \(p_{0}|(n_{0}\cdot n_{0}) \Rightarrow p_0 |n_{0}\).
Trzeci rodzaj dowodu polega na wyprowadzeniu z założenia dowodu nie wprost dwóch wniosków (różnych od dowodzonego twierdzenia i jego negacji), z których każdy jest negacją drugiego.
Najkrótszym przykładem takiego dowodu będzie rozumowanie B. Russella, użyte przezeń do pokazania tzw. paradoksu Russella. Był to faktycznie dowód dla następującego twierdzenia.
Twierdzenie 3. Nie każda własność, wyrażona w języku teorii mnogości definiuje jakiś zbiór.
Dowód. Załóżmy, że każda własność, wyrażalna w języku teorii mnogości, definiuje jakiś zbiór. Wobec tego własność bycia zbiorem normalnym, to jest zbiorem nie będącym własnym elementem, definiuje jakiś zbiór. Oznaczmy więc przez \(\mathfrak{N}\) zbiór zborów normalnych i zdefiniujmy go warunkiem
\[
X \in \mathfrak{N}\quad \iff\quad X \not \in X
\]
Spytajmy teraz, czy zbiór zbiorów normalnych jest zbiorem normalnym, czy mianowicie \(\mathfrak{N} \in \mathfrak{N}\). Wstawiając \(\mathfrak{N}\) na miejsce \(X\) w powyższej równoważności dostajemy równoważność
\[
\mathfrak{N} \in \mathfrak{N}\quad \iff\quad \mathfrak{N} \not \in \mathfrak{N}.
\]
Aby naprawdę zakończyć dowód, trzeba skorzystać z praw
\[
(\phi \leftrightarrow \neg \phi) \rightarrow \phi
\]
oraz
\[
(\phi \leftrightarrow \neg \phi) \rightarrow \neg \phi
\]
aby dostać parę zdań sprzecznych, wynikających z założenia, że każda własność, wyrażalna w języku teorii mnogości definiuje jakiś zbiór.
Tezę twierdzenia dostajemy tym razem korzystając z tautologii
\[
[(\phi \rightarrow \psi) \wedge (\phi \rightarrow \neg \psi)] \rightarrow \neg \phi.
\]
Tautologia ta jest zwane ,,prawem redukcji do absurdu”.
Tak więc w każdym z tych trzech przypadków tezę twierdzenia uzyskuje się na podstawie innej tautologii, bo inne jest tam rozumowanie matematyczne.
Przykłady dowodów nie wprost
Praktyka matematyczna dowodzenia nie wprost jest jednak o wiele bogatsza, niż przedstawiona na tych trzech prostych przykładach. Te trzy typy rozumowań charakterystycznych dla dowodów nie wprost mogą z kolei być zagnieżdżone w bardziej złożonych dowodach nie wprost, a takze w dowodach wprost (tu się zresztą nasuwa pytanie, czy dowód wprost, w którym występuje fragment, będący dowodem nie wprost, jat naprawdę dowodem wprost).
Odnotujmy następne przykłady.
Twierdzenie 4 (Twierdzenie Cantora). Niech \(X\) będzie zbiorem i niech \({\cal P}(X)\) będzie zbiorem wszystkich podzbiorów zbioru \(X\). Wówczas
\[
card(X) < card({\cal P}(X)).
\]
Dowód. Zauważmy najpierw, że \(card(X) \leq card({\cal P}(X))\). Weźmy bowiem zbiór \({\cal P}_{1}(X)\) wszystkich podzbiorów jednoelementowych zbioru \(X\); moce zbiorów \(X\) i \({\cal P}_{1}(X)\) są równe, a \({\cal P}_{1}(X) \subseteq {\cal P}(X)\). Wystarczy więc pokazać, że \(card(X) \neq card({\cal P}(X))\).
Załóżmy (i to jest nasze założenie dowodu nie wprost), że \(card(X) = card({\cal P}(X))\). Wobec tego istnieje różnowartościowa funkcja \(f\), przekształcająca zbiór \({\cal P}(X)\) na zbiór \(X\).
Oznaczmy przez \(x_{A}\) element przyporządkowany zbiorowi \(A\) przez funkcję \(f\), tzn. niech \(x_{A} = f(A)\). Jasne, że albo \(x_{A}\) jest elementem zbioru \(A\), albo nie jest. Podzielmy wobec tego zbiór \(X\) na dwa podzbiory: Podzbiór \(A_{1}\) takich elementów, dla których \(x_{A} \not \in A\) i podzbiór takich, które spełniają warunek \(x_{A} \in A\). Formalnie:
\[
x \in A_{1} \quad \iff \quad x_{A} \not \in A,
\]
oraz
\[
x \in A_{2}\quad \iff \quad x_{A} \in A.
\]
Oczywiście zbiory \(A_{1}\) i \(A_{2}\) są rozłączne, a w sumie dają zbiór \(X\).
Rozważmy zbiór \(A_{1}\). Jasne, że zbiorowi \(A_{1}\) funkcja \(f\) przyporządkowuje jakiś element \(x_{A_{1}}\). Załóżmy, że \(x_{A_{1}}\) należy do zbioru \(A_{1}\). Wprost z definicji zbioru \(A_{1}\) dostajemy równoważność
\[
x_{A_{1}} \in A_{1} \quad \iff \quad x_{A_{1}} \not \in A_{1}.
\]
Dalej można rozumować, jak w dowodzie twierdzenia Russella: z tej równoważności wynika, że \(x_{A_{1}} \in A_{1}\) oraz że \(x_{A_{1}} \not \in A_{1}\). Ponieważ jest to konsekwencja założenia, że zbiory \(X\) i \({\cal P}(X)\) są równoliczne, więc − rozumując jak w dowodzie twierdzenia Russella − nie mogą być równoliczne.
Można jednak, jeśli ktoś woli, wydedukować z ostatniej równoważności tylko, że \(x_{A_{1}} \not \in A_{1}\) i kontynuować dowód inaczej.
Ponieważ zbiory \(A_{1}\) i \(A_{2}\) są rozłączne i wyczerpują zbiór \(X\), a \(x_{A_{1}} \not \in A_{1}\), więc \(x_{A_{1}} \in A_{2}\). A wtedy mamy następującą równoważność, biorącą się definicji zbioru \(A_{2}\):
\[
x_{A_{1}} \in A_{2}\quad \iff \quad x_{A_{1}} \in A_{1},
\]
a to przeczy założeniu o rozłączności zbiorów \(A_{1}\) i \(A_{2}\).
Dowód więc uznamy za skończony: uzyskaliśmy dwa zdania sprzeczne.
Czytelnik zechce się zastanowić dokładniej nad rozumowaniem w drugim wariancie dowodu: z czym właściwie dochodzi się tu do sprzeczności? Okazuje się, że z jedną z konsekwencji założenia dowodu nie wprost.
Zastanówmy się, czy ten dowód jest dowodem nie wprost. Nie wprost udowodniliśmy tylko, że zbiory \(X\) i \({\cal P}(X)\) nie są równoliczne. Słabą nierówność: \(card(X) \leq card({\cal P}(X))\) udowodniliśmy jednak wprost. Gdyby nawet przyjąć, że dowód nie wprost to taki, w którym ,,zasadnicza część” jest przeprowadzona nie wprost, to trzeba wyjaśnić, która część dowodu jest ,,zasadnicza”, a która nie.
A oto następny przykład.
Twierdzenie 5. Niech \(a\) będzie dodatnią liczbą całkowitą, a \(n\) niezerową liczbą naturalną. Wówczas jeśli \(\sqrt[n]{a}\) jest liczbą wymierną, to \(\sqrt[n]{a}\) jest liczbą całkowitą.
Dowód. Niech \(\sqrt[n]{a}\) będzie liczbą wymierną, więc niech \(\sqrt[n]{a} = \frac{k}{m}\) dla liczb niezerowych liczb naturalnych \(k\) i \(m\); załóżmy, że są one względnie pierwsze. Wówczas \(m^{n}a = k^n\). Jeśli \(m \neq 1\), to istnieje liczba pierwsza \(p\), dzieląca \(m\). Skoro jednak \(p\) dzieli \(m\), to to \(p\) dzieli \(k^n\), zatem dzieli też \(k\) (por. Twierdzenie 2), a to oznacza, że liczby \(m\) i \(k\) nie są względnie pierwsze, bo obie są podzielne przez \(p\). Doszliśmy więc do sprzeczności z założeniem, że \(m \neq 1\), toteż \(m = 1\). Wobec tego \(\frac{k}{m}\) jest liczbą całkowitą.
Osobliwością tego dowodu jest to, że zaczyna się tak, jak dowód wprost, ale fragment tego dowodu, zresztą najistotniejszy dla całego dowodu, jest dowodem nie wprost. Dalej, ten fragment dowodu korzysta z prawa wyłączonego środka: dowiedliśmy, że fałszem jest, iż \(m \neq 1\), a z tego wnosimy, że \(m = 1\). %Dowód ten nie jest więc dowodem intuicjonistycznym.
Czy więc jest to dowód wprost, czy nie wprost?
Konsekwencją tego twierdzenia jest następujące twierdzenie.
Twierdzenie 6. Jeśli \(p\) jest liczbą pierwszą, a \(n\leq 2\), to liczba \(\sqrt[n]{p}\) jest niewymierna.
Dowód. Podamy dowód nie wprost. Niech liczna \(\sqrt[n]{p}\) będzie wymierna. Wobec poprzedniego twierdzenia musi być całkowita; niech np. \(\sqrt[n]{p} = a\). Zatem \(p = a^n\), toteż liczba \(p\) nie może być pierwsza.
Warto zauważyć, że twierdzenie to ma dwa założenia, ale doszliśmy do sprzeczności z jednym z nich.
Nawiasem mówiąc, jak i w poprzednich przypadkach, stosując prawa de Morgana dla kwantyfikatorów − negując tezę twierdzenia, by dowieść je wprost, w zasadzie używaliśmy tych samych symboli dla zmiennych i dla stałych nazwowych. Powinniśmy używać egzemplifikacji typu \(p_0\) czy \(n_0\), by odróżnić stałe od zmiennych. Czytelnik (zwłaszcza purysta) zechce to wybaczyć; dzięki temu rozważania stały się nieco przejrzystsze.
A oto ostatni przykład, oparty na dwu poprzednich twierdzeniach.
Twierdzenie 7. Jeśli \(n\) jest liczbą naturalną taką, że \(n> 1\), to liczba \(\sqrt[n]{n}\) jest liczbą niewymierną.
Dowód. Załóżmy, że \(n>1\) i że \(\sqrt[n]{n}\) jest liczbą wymierną. Z twierdzenia 5 wynika, że jeśli \(\sqrt[n]{n} = a\) jest liczbą wymierną, to \(a\) jest liczbą całkowitą, wobec tego \(a^n = n\). Gdyby teraz \(a = 1\), to \(n =1\) wbrew założeniu, że \(n > 1\). Wobec tego \(2 \leq a\), a w konsekwencji \(2^n \leq a^n\). Wiadomo jednak, że dla każdej liczby naturalnej \(n\) prawdą jest, ze \(2^n > n\), wobec czego (ponieważ, jak widzieliśmy, \(a \geq 2\) pociąga, że \(a^n \geq 2^n\)), \(a^n > n\). Wobec tego równość \(a^n = n\) nie może, i to kończy dowód.
Interesujące jest w tym dowodzie to po pierwsze, że jest on dowodem nie wprost, zawierającym dodatkowy dowód nie wprost: ,,gdyby \(a= 1\), to \(n = 1\) wbrew założeniu, że \(n>1\), toteż \(a>1\)”.
Po drugie, sprzeczność z równością \(a^n = n\), uzyskaliśmy z założenia dowodu nie wprost i Twierdzenia 5.
Wnioski
- Widzieliśmy, że pojęcie dowodu nie wprost to materia raczej delikatna: przykłady wskazują, że część dowodu wprost może zawierać poddowód nie wprost i odwrotnie. Z drugiej strony panuje przeświadczenie, że są jednak dwa rodzaje dowodów. Co więc jest dowodem nie wprost? Rozgraniczenie nie jest klarowne. Wobec tego najbardziej sensowne będzie przyjęcie konwencji: dowodem nie wprost jest dowód twierdzenia, polegający na tym, że zaczyna się on od zanegowania dowodzonego twierdzenia.
I starczy.
- Jasne jest, jak się okazuje, że prawdziwe dowody matematyczne (nawet proste) miewają skomplikowana strukturę: niektóre fragmenty są, jak zauważyliśmy wyżej, wprost, inne są nie wprost. Opinie na ten temat – teoretycznie rzecz biorąc – mogą być dwie.
- Nie ma takiego zagadnienia, którego by się nie dało skomplikować. Można więc skomplikować problem: co to jest dowód nie wprost?. Ale po co komplikować?
- Z faktami gentlemani nie dyskutują. A fakty wskazują na nader złożoną naturę argumentacji matematycznej, zwłaszcza dowodów, które nie są zupełnie elementarne. Nie tylko więc materia jest skomplikowana, ale i sposób badania tej materii jest intelektualnie wyrafinowany. Nie ma co tego kryć: jest to dodatkowy argument za tym, że matematyka, którą uprawiamy, jest dziedziną wyrafinowaną, a innym pozostawmy już tylko przyjęcie do wiadomości tego faktu.