"Naiwne" dowody niewprost | Informatyka MIMUW

Częstą metodą dowodzenia twierdzeń matematycznych jest dowodzenie niewprost. Dowód niewprost polega na założeniu zaprzeczenia twierdzenia, które chcemy udowodnić i doprowadzeniu do sprzeczności. Wykazujemy, że jeśli twierdzenie nasze jest nieprawdziwe, jesteśmy w stanie udowodnić jakąś tezę, która jest w sposób oczywisty fałszywa.
Jednym z najbardziej znanych dowodów niewprost jest dowód istnienia nieskończenie wielu liczb pierwszych. Dowód ten został zaproponowany przez Euklidesa z Aleksandrii, a my prezentujemy go w wersji podanej przez Ernsta Kummera. Twierdzenie 3.1
Istnieje nieskończenie wiele liczb pierwszych.
Dowód
Załóżmy, że istnieje jedynie skończenie wiele liczb pierwszych

$p_0,\dotsc,p_n$ . Zdefiniujmy liczbę

$k = p_0\cdot p_1\cdot\dotsb\cdot p_n$
i rozważmy

${k+1}$ . Liczba

${k+1}$ posiada dzielnik pierwszy, a ponieważ jedynymi pierwszymi liczbami są liczby

$p_0,\dotsc,p_n$ , wnioskujemy, że

${p_i}$ dzieli

${k+1}$ dla pewnego

$i$ . Liczba

${p_i}$ dzieli również

$k$ , a więc

${p_i}$ dzieli

$(k+1)-k=1$ co jest sprzecznością.
Ćwiczenie 3.1
Wykaż, że nie istnieje największa liczba naturalna.

Rozwiązanie

Załóżmy, niewprost, że istnieje największa liczba naturalna i oznaczmy ją przez

$\mathrm {n}$ . Niewątpliwie

${n+1}$ jest liczbą naturalną większą od

$\mathrm {n}$ , co jest sprzecznością z naszym założeniem.

Ćwiczenie 3.2
Wykaż, że $\sqrt{2}$ jest liczbą niewymierną.

Rozwiązanie

Załóżmy, niewprost, że

$\sqrt{2}$ jest liczbą wymierną, czyli, że istnieją dwie naturalne, względnie pierwsze liczby

$k$ i

$l$ takie, że

$\sqrt{2}=k/l$ . Przekształcając ostatnie wyrażenie otrzymujemy

$k^2=2l^2$ . Skoro 2 dzieli lewą stronę równości, dzieli też i prawą, a ponieważ dwa jest liczbą pierwszą, wnioskujemy, że 2 dzieli

$k$ . Jeśli 2 dzieli

$k$ , to 4 dzieli

$k^2$ i na podstawie równości 4 dzieli

$2l^2$ . Wnioskujemy stąd, że 2 dzieli

$l^2$ i, na podstawie pierwszości liczby 2, że 2 dzieli l. Udowodniliśmy, że 2 dzieli zarówno

$k$ jak i

$l$ , co jest sprzecznością z założeniem, że liczby te są względnie pierwsze.

Ścisłe uzasadnienie poprawności dowodów niewprost leży na gruncie logiki, której poświęcony jest następny wykład.