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.
Ćwiczenie 3.2
Wykaż, że \( \sqrt{2} \) jest liczbą niewymierną.
Ścisłe uzasadnienie poprawności dowodów niewprost leży na gruncie logiki, której poświęcony jest następny wykład.