Dowód przez sprzeczność

Dowód przez zaprzeczenie jest popularną techniką dowodzenia. Jeśli chcemy udowodnić, że jakieś twierdzenie jest prawdziwe, zakładamy, że jest ono prawdziwe, a następnie negujemy je i próbujemy dojść do sprzeczności. Celem jest udowodnienie, że wybrane przez nas założenie prowadzi do jakiegoś nonsensu.

Trywialny przykład

Rozważmy stwierdzenie "nie ma najmniejszej dodatniej liczby wymiernej". Możemy udowodnić to twierdzenie przez spór, najpierw negując stwierdzenie "istnieje najmniejsza dodatnia liczba" i oznaczając tę liczbę q. Jeśli q jest najmniejszą dodatnią liczbą wymierną, to nie jesteśmy w stanie znaleźć mniejszej dodatniej liczby wymiernej - ponieważ wtedy q nie byłaby najmniejsza.

Wykorzystamy to do znalezienia sprzeczności. Jeśli znajdziemy liczbę, która jest mniejsza niż q, którą możemy wybrać dowolnie, to osiągnęliśmy sprzeczność i pierwotne stwierdzenie nie jest ważne. Jeśli wybierzemy na przykład 0,1 jako najmniejszą liczbę, zobaczymy, że 0,01 jest mniejsze. Następnie 0,001 jest jeszcze mniejsze, 0,0001 jest jeszcze mniejsze itd. Wystarczy podzielić daną liczbę q przez dziesięć, aby otrzymać mniejszą liczbę. W rzeczywistości wystarczy podzielić ją przez dowolną liczbę większą niż jeden, na przykład dwa - połowa liczby q będzie z pewnością mniejsza niż cała liczba q.

Tak więc liczba q/2 jest z pewnością mniejsza niż q i jest również liczbą dodatnią. To prowadzi nas do konfliktu z zanegowanym stwierdzeniem, tj. zanegowane stwierdzenie jest nieważne, a zatem oryginalne niezanegowane stwierdzenie jest ważne.

Ciekawe liczby

Klasycznym zabawnym dowodem ilustrującym zasadę sprzeczności jest następujący przykład. Załóżmy, że istnieją liczby naturalne, które są w jakiś sposób interesujące. Na przykład, liczba 2 jest interesująca, ponieważ jest prawdą, że 2 · 2 = 2 + 2, jest to raczej nietypowa własność. Liczba 42 jest interesująca, ponieważ jest odpowiedzią na wszystko. I tak dalej. Pytanie brzmi - czy istnieje nieskończenie wiele interesujących liczb?

Załóżmy, że jest odwrotnie, tzn. że jest tylko nieskończenie wiele interesujących liczb, a niektóre liczby są nieinteresujące. Porządkujemy te nieciekawe liczby naturalne w zbiór liczb nieciekawych. Teraz wybieramy najmniejszą nieciekawą liczbę. Chwila, najmniejszą nieciekawą liczbę? To brzmi całkiem interesująco, prawda? :-)

To prowadzi nas do sprzeczności, ponieważ najmniejsza nieinteresująca liczba jest w rzeczywistości całkiem interesująca, więc nie może istnieć najmniejsza nieinteresująca liczba, a zatem zbiór nieinteresujących liczb musi być pusty.

Oczywiście to nonsens, nie mamy odpowiedniej definicji interesującej liczby, ale sama procedura dowodu jest w porządku.

Dowód na nieskończoność liczb pierwszych

W tym przykładzie pokażemy procedurę podobną do tej z poprzedniej sekcji, ale tym razem będzie ona poprawna pod każdym względem.

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

Rozkład na liczby pierwsze lub faktoryzacja to rozkład liczby naturalnej innej niż jeden na iloczyn liczb pierwszych. Jest to dość interesująca właściwość liczb naturalnych. Niezależnie od tego, jaką liczbę naturalną weźmiemy (z wyjątkiem jedynki), prawdą jest, że można ją rozłożyć na iloczyn kilku (nawet tych samych) 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 liczb pierwszych nazywane jest Podstawowym Twierdzeniem Arytmetyki. Twierdzenie to mówi nam między innymi, że taki rozkład jest unikalny, tj. nie możemy znaleźć dwóch różnych rozkładów pierwszej liczby naturalnej. Co więcej, tylko liczby pierwsze mają rozkład składający się tylko z jednej liczby - ich samych. Zatem rozkładem pierwszym liczby siedem byłaby liczba siedem. Wykorzystamy te fakty przy konstruowaniu dowodu poniższego twierdzenia.

Udowodnimy teraz twierdzenie, że "istnieje nieskończenie wiele liczb pierwszych". Ponownie unieważnimy twierdzenie: "istnieje skończona liczba liczb pierwszych". Załóżmy, że ciąg liczb

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

reprezentuje wszystkie istniejące liczby pierwsze. Jeśli wszystkie liczby pierwsze znajdują się w tym ciągu, to z pewnością nie będziemy w stanie znaleźć liczby, która jest jednocześnie liczbą pierwszą i nie znajduje się w tym ciągu. Mamy wszystkie liczby pierwsze w ciągu, żadna liczba pierwsza nie może znajdować się poza ciągiem.

Jeśli więc chcemy dojść do sprzeczności, musimy skonstruować liczbę pierwszą, która nie znajduje się w ciągu. Pomoże nam w tym liczba q. Tworzymy ją mnożąc wszystkie liczby pierwsze w ciągu i dodając jedną:

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

Teraz musimy pokazać, że ta liczba jest liczbą pierwszą lub w jakiś sposób generuje liczbę pierwszą. Wiemy, że q jest liczbą naturalną i że każda liczba naturalna może być wyrażona jako iloczyn liczb pierwszych. Jednak żadna liczba pierwsza a_i nie dzieli liczby q bez reszty, zawsze pozostawiając jedynkę po dzieleniu. Jeśli spróbowalibyśmy podzielić liczbę q przez, na przykład, liczbę pierwszą a₂, otrzymalibyśmy następujący wynik:

$$\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 dzielimy ułamek na dwa. W pierwszym ułamku obcinamy a₂ i otrzymujemy iloczyn liczb pierwszych, który jest po prostu jakąś inną nieistotną liczbą całkowitą. W drugim ułamku nie ma nic do obcinania, ten ułamek zawsze będzie jakąś liczbą niecałkowitą (ponieważ mianownik nie może być jedynką, jedynka nie jest liczbą pierwszą). W sumie otrzymujemy więc liczbę, która nie jest liczbą całkowitą, tzn. liczba pierwsza a₂ nie dzieli liczby q.

Dowodzi to, że żaden z liczb pierwszych w ciągu a_n nie dzieli liczby q. (Uwaga: pokazaliśmy to tylko dla a₂, ale można to łatwo uogólnić, jeśli zastąpimy a₂ ogólnym a_i) Ale ponieważ każdą liczbę naturalną można rozłożyć na iloczyn liczb pierwszych, muszą istnieć inne liczby pierwsze, które nie są w ciągu a_n, ale są faktoryzacjami q. Jednak sama liczba q może być liczbą pierwszą, a rozkład na liczby pierwsze będzie dotyczył tylko liczby q. Ostatni ciąg myślowy:

1. Każda liczba naturalna może być wyrażona jako iloczyn liczb pierwszych.
2. Z założenia ciąg a_n zawiera wszystkie istniejące liczby pierwsze.
3. Zmodyfikujmy pierwsze stwierdzenie, aby powiedzieć, że każda liczba naturalna może być wyrażona jako iloczyn wybranych elementów ciągu a_n, ponieważ zawiera on wszystkie liczby pierwsze.
4. Udowodniliśmy, że żadna liczba z ciągu a_n nie dzieli liczby q.
5. To wywołało spór z założeniem $\rightarrow$. Jeśli musimy być w stanie rozłożyć każdą liczbę naturalną 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 są pierwszymi rozkładami liczby q.

To prowadzi nas do sprzeczności. Rozkład liczby pierwszej q zawiera liczby pierwsze, które nie są zawarte w sekwencji, o której zakładaliśmy, że zawiera wszystkie liczby pierwsze. Zatem zanegowane twierdzenie nie jest prawdziwe, a zanegowane oryginalne twierdzenie jest prawdziwe. Istnieje nieskończenie wiele liczb pierwszych.