Dowód matematyczny — jak wygrać spór

🎯 Po co Ci to?

Doszliśmy do serca całego działu. W matematyce nie wystarczy powiedzieć „sprawdziłem kilka przypadków i działa". Fizyk tak może; matematyk: nie. Jego walutą jest dowód: rozumowanie, które daje pewność raz na zawsze, dla nieskończenie wielu przypadków. To dzięki niemu twierdzenie sprzed 2000 lat wciąż jest prawdą. Ta jednostka pokazuje trzy podstawowe sposoby, jak taki dowód poprowadzić, i jak jednym ruchem obalić fałszywe „zawsze".

✅ Czego się nauczysz

Po tej jednostce potrafisz:

  • obalić zdanie „dla każdego" jednym kontrprzykładem;
  • przeprowadzić prosty dowód wprost (łańcuch implikacji od założenia do tezy);
  • zrozumieć ideę dowodu nie wprost (przez sprowadzenie do sprzeczności) i odtworzyć klasyczny dowód, że liczb pierwszych jest nieskończenie wiele.

📘 Wyjaśnienie

Kontrprzykład: najtańsza broń. Zacznijmy od burzenia, bo jest łatwiejsze niż budowanie. Aby obalić zdanie „dla każdego $x$ zachodzi $p(x)$", wystarczy wskazać jeden obiekt, dla którego nie zachodzi. To wprost: zaprzeczeniem zdania „dla każdego" jest zdanie „istnieje taki, dla którego nie".

💭 Pomyśl: Ktoś twierdzi: „Każda liczba pierwsza jest nieparzysta." Czy masz jak to obalić jednym ruchem?

Sprawdź odpowiedź

Tak: kontrprzykładem jest 2: liczba pierwsza, a jednak parzysta. Jeden świadek wystarcza, żeby zburzyć „każda". Nie musisz analizować wszystkich liczb pierwszych; wystarczy pokazać jedną wystającą z szeregu.

Zapamiętaj tę asymetrię: jeden kontrprzykład obala „zawsze", ale żaden zbiór przykładów nie dowodzi „zawsze". Budowanie prawdy wymaga cięższego narzędzia.

Dowód wprost: łańcuch od założenia do tezy. Twierdzenia mają zwykle postać implikacji: „jeśli założenie, to teza". Dowód wprost to po prostu przejście po łańcuchu implikacji od jednego do drugiego, tak by każdy krok był oczywisty lub już udowodniony.

Twierdzenie. Suma dwóch liczb parzystych jest parzysta.

Dowód. Załóżmy, że $a$ i $b$ są parzyste. To znaczy (z definicji parzystości) że dają się zapisać jako $a = 2k$ i $b = 2m$ dla pewnych liczb całkowitych $k, m$. Wtedy $$a + b = 2k + 2m = 2(k + m).$$ Skoro $k + m$ jest liczbą całkowitą, to $a+b$ jest podwojeniem liczby całkowitej, czyli jest parzyste. To właśnie chcieliśmy pokazać. ∎

Zwróć uwagę: nie sprawdziliśmy żadnego konkretnego przypadku. Rozumowanie objęło wszystkie pary liczb parzystych naraz, bo $k$ i $m$ były dowolne. To jest różnica między „sprawdziłem $4+6=10$" a „dowiodłem". Symbol ∎ (albo „c.k.d.", czyli „co kończy dowód") to tradycyjna kropka na końcu dowodu.

Dowód nie wprost: spryt przez sprzeczność. Czasem droga wprost jest ciernista, ale istnieje sprytniejsze wejście. Zakładamy, że teza jest fałszywa, i pokazujemy, że prowadzi to do jawnej sprzeczności, do zdania, które musiałoby być i prawdą, i fałszem naraz. Skoro fałszywe założenie zawaliło logikę, to musiało być błędne, więc teza jest prawdziwa.

To jak w śledztwie: „załóżmy, że to nie podejrzany zabił. Ale wtedy o 21:00 był w dwóch miejscach naraz; niemożliwe. Więc jednak on." Podważasz alternatywę do absurdu, żeby została jedyna możliwość.

Najsłynniejszy dowód nie wprost w historii matematyki pokazuje, że $\sqrt{2}$ nie da się zapisać jako ułamek: zakłada się, że da się, i doprowadza to do sprzeczności. Poprowadzimy go krok po kroku już w Dziale 2, gdy liczby zaczną się rozrastać; tam ten dowód będzie kulminacją, nie ćwiczeniem. Teraz najważniejsze, żebyś rozpoznał sam manewr: „przypuśćmy, że jest inaczej… (sprzeczność!) więc jednak tak". Oto on w akcji, w dowodzie równie starym:

Twierdzenie (Euklides). Liczb pierwszych jest nieskończenie wiele.

Dowód nie wprost. Przypuśćmy, że jest ich skończenie wiele: $p_1, p_2, \dots, p_k$. Rozważmy liczbę $N = p_1 \cdot p_2 \cdot \ldots \cdot p_k + 1$. Jest większa od $1$, więc ma dzielnik pierwszy $p$ (najmniejszy dzielnik $N$ większy od $1$ musi być pierwszy: gdyby był złożony, miałby jeszcze mniejszy dzielnik). Z założenia $p$ jest którąś z liczb $p_1, \dots, p_k$. Ale każda z nich dzieli iloczyn $p_1 \cdot \ldots \cdot p_k$, więc $N$ daje przy dzieleniu przez nią resztę $1$. Sprzeczność: $p$ jednocześnie dzieli $N$ i nie dzieli. Zatem liczb pierwszych jest nieskończenie wiele. ∎

Uwaga na częstą pomyłkę: sama liczba $N$ nie musi być pierwsza. $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1 = 30031 = 59 \cdot 509$. Dowód twierdzi tylko, że $N$ ma dzielnik pierwszy, którego nie ma na liście.

📐 DEFINICJA, trzy techniki: Kontrprzykład: obala zdanie „dla każdego" jednym wyjątkiem. Dowód wprost: łańcuch implikacji od założenia do tezy. Dowód nie wprost: zakładamy, że teza fałszywa, i wyprowadzamy sprzeczność.

⚠️ Uwaga, pułapka

„Sprawdziłem i wychodzi" to nie dowód, tylko poszlaka, i bywa myląca. Zdanie „liczba $n^2 + n + 41$ jest pierwsza" jest prawdziwe dla $n = 0, 1, 2, \dots$ aż do $39$ (czterdzieści trafień z rzędu!) a mimo to fałszywe: dla $n = 40$ wychodzi $41^2$, liczba złożona. Gdyby matematyka ufała próbkom, uwierzyłaby w fałsz. Dlatego istnieją dowody.

🛠️ Teraz Ty

Obal kontrprzykładem albo uzasadnij:

  1. „Każda liczba podzielna przez 4 jest podzielna przez 8."
  2. „Suma dwóch liczb nieparzystych jest parzysta." (spróbuj dowodu wprost, wzorując się na przykładzie powyżej)
Sprawdź
  1. Fałsz. Kontrprzykład: $4$ dzieli się przez 4, ale nie przez 8. (Albo $12$, albo $20$; jeden wystarczy.)
  2. Prawda. Dowód wprost: liczba nieparzysta to $2k+1$. Weźmy $a = 2k+1$, $b = 2m+1$. Wtedy $a + b = 2k+1+2m+1 = 2k+2m+2 = 2(k+m+1)$; podwojenie liczby całkowitej, czyli parzysta. ∎

🕰️ Skąd to się wzięło

Pomysł, że twierdzenie trzeba udowodnić, a nie tylko sprawdzić na przykładach, to wynalazek starożytnych Greków, utrwalony w Elementach Euklidesa (ok. 300 p.n.e.): książce, która przez dwa tysiące lat była najczęściej wydawanym dziełem matematycznym w historii. Grecki jest i sam dowód nie wprost: legenda głosi, że gdy pitagorejczyk Hippasos dowiódł nim, że $\sqrt{2}$ nie jest ułamkiem (dokładnie tą metodą, którą poznasz w Dziale 2), roztrzaskał świętą wiarę szkoły, że „wszystko jest liczbą", i podobno przypłacił to życiem. Dowód potrafi być groźny.

📌 Najważniejsze w pigułce

  • Kontrprzykład: jeden wyjątek obala „dla każdego". Zbiór przykładów niczego nie dowodzi.
  • Dowód wprost: od założenia do tezy łańcuchem implikacji, dla dowolnego (nie konkretnego) obiektu.
  • Dowód nie wprost: zakładamy negację tezy → sprzeczność → więc teza prawdziwa.
  • Euklides: gdyby liczb pierwszych było skończenie wiele, iloczyn wszystkich plus $1$ nie dzieliłby się przez żadną z nich; sprzeczność.
  • Precyzyjny język matematyki istnieje po to, by móc dowodzić.

🎒 Zadania

  1. Obal lub uzasadnij: „Każda liczba naturalna większa od 1 jest sumą dwóch liczb pierwszych."
  2. Udowodnij wprost: „Kwadrat liczby parzystej jest parzysty."
  3. Wyjaśnij własnymi słowami, dlaczego jeden przykład wystarcza, by obalić „dla każdego", ale nie wystarcza, by je udowodnić. (odwołaj się do zdań mówiących „dla każdego")
Rozwiązanie krok po kroku

1. Zdanie jest fałszywe: obalamy kontrprzykładem. Najprościej liczbą nieparzystą: $11$ nie jest sumą dwóch liczb pierwszych ($11=2+9$, a $9$ nie jest pierwsza; innych rozkładów na dwie pierwsze brak). Jeden kontrprzykład wystarcza. (Uwaga: dla liczb parzystych większych od 2 to słynna hipoteza Goldbacha, do dziś nierozstrzygnięta; my obalamy zdanie o „każdej" liczbie.)

2. Dowód wprost. Liczba parzysta to $2k$. Jej kwadrat: $(2k)^2 = 4k^2 = 2\cdot(2k^2)$. Skoro $2k^2$ jest całkowite, kwadrat jest dwójką razy coś całkowitego, czyli parzysty. Objęliśmy wszystkie liczby parzyste naraz ($k$ dowolne). ∎

3. „Dla każdego" znaczy „bez wyjątku". Jeden kontrprzykład to jeden wyjątek, a wyjątek burzy „bez wyjątku". Ale jeden (czy sto) przykładów potwierdzających NIE gwarantuje, że gdzieś dalej nie czai się wyjątek, dlatego do udowodnienia „dla każdego" potrzeba dowodu obejmującego wszystkie przypadki naraz (np. na literze), nie próbek.

🔍 Sprawdź, czy umiesz

  • obalić fałszywe „zawsze" kontrprzykładem;
  • przeprowadzić prosty dowód wprost i opisać ideę dowodu nie wprost;
  • odtworzyć dowód, że liczb pierwszych jest nieskończenie wiele.

Ucz się tej jednostki z asystentem