Co to jest dowód

Dowody są kamieniem węgielnym całej matematyki; dzięki dowodom można zbudować całą piramidę z zaledwie kilku kamieni, i to do góry nogami.

Znaczenie dowodów

Dowody mają sens w matematyce z kilku powodów. Głównym powodem jest to, że bez pomocy dowodów nie jesteśmy w stanie potwierdzić żadnego pomysłu lub hipotezy, która przychodzi nam do głowy. Na przykład, możemy wierzyć, że istnieje skończona liczba liczb pierwszych, ale jeśli nie mamy dowodu, staje się to tylko bezmyślnym stwierdzeniem. Z drugiej strony, nawet nieudowodnione twierdzenia mają znaczenie w matematyce (i nie tylko). Krótka odpowiedź brzmi: jeśli założenie, że istnieje skończenie wiele liczb pierwszych jest prawdziwe, to... prawdziwa jest jakaś inna teoria.

Nie możemy się jednak dziwić, że z czasem ktoś udowodni, że liczb pierwszych jest nieskończenie wiele, co pokażemy poniżej, i cała nasza teoria runie jak domek z kart. Dzięki dowodom możemy więc budować domki z kart, które nigdy się nie zawalą.

Powodem, dla którego dowody są nauczane w szkołach, jest to, że ci, którzy rozumieją dowód, zrozumieją jego istotę. Zwykle trudno jest dokładnie zrozumieć daną substancję bez zrozumienia dowodów. Podkreśliłem słowo "zrozumieć" całkiem celowo, ponieważ jeśli zapamiętasz dowody dzień przed egzaminem i po prostu wyplujesz je na papier następnego dnia, nie oznacza to, że jesteś bliżej zrozumienia tematu.

Tak więc, podczas nauki przedmiotu, dowody odpowiadają na pytanie "dlaczego to działa w ten sposób?". Jeśli zrozumiesz, dlaczego dana rzecz działa, łatwiej ją zapamiętasz, a z czasem na pewno zrozumiesz jej istotę bardziej niż osoba, która nauczyła się jej w stylu "wylej to". Pytanie brzmi, czy to jest twój cel.

Czym jest dowód

To, czym jest dowód, jest formalnie zdefiniowane w logice matematycznej, na przykład przez pociągnięcie syntaktyczne, ale my zadowalamy się znacznie prostszą definicją.

Na początku każdego dowodu musimy mieć twierdzenie, które chcemy udowodnić. Twierdzenie to oznaczamy magicznym symbolem $\phi$. Jest to grecka litera, która brzmi "phi". Następnie będziemy potrzebować pewnego zbioru aksjomatów i założeń, oznaczonego przez Ax, za pomocą którego będziemy mogli udowodnić twierdzenie $\phi$. Zestaw aksjomatów to coś, co już wiemy, coś, co zakładamy, że jest prawdziwe. Mogą to być rzeczy takie jak "każda liczba parzysta jest jednocześnie podzielna przez dwa". Co więcej, zbiór ten może zawierać formuły modyfikujące wyrażenia, które są udowodnione gdzieś z boku i które już zakładamy, że są prawdziwe:

$$(a+b)^2=a^2+2ab+b^2;\qquad a,b\in\mathbb{R}$$

Teraz będziemy sukcesywnie modyfikować wyrażenia w zbiorze Ax, aż otrzymamy wyrażenie $\phi$. Wszystkie modyfikacje muszą być logicznie poprawne, muszą być zgodne z podstawową logiką zdań. Na przykład, jeśli chcielibyśmy udowodnić poprzednią formułę, postępowalibyśmy w taki sposób, że wyrażenie

$$(a+b)^2$$

będziemy wprowadzać równoważne modyfikacje, aż otrzymamy wyrażenie po prawej stronie. Demonstracja:

$$(a+b)^2=(a+b)\cdot(a+b)=a\cdot a+a\cdot b + b\cdot a + b\cdot b=$$

$$=a\cdot a+2ab+b\cdot b=a^2+2ab+b^2$$

W pierwszym kroku rozbiliśmy potęgę na iloczyn, w drugim pomnożyliśmy nawiasy, w trzecim dodaliśmy równe wyrażenia, a w ostatnim zapisaliśmy iloczyn jako potęgę. Każdy krok reprezentował elementarną korektę, na którą mogliśmy sobie pozwolić, i zakładamy, że każda z tych elementarnych korekt jest zawarta w zbiorze Ax.

Co ważne, każda korekta musi być poprawna, musi opierać się na czymś, co już wiemy. Dowód matematyczny jest czymś w rodzaju ewolucji - poprzez kolejne drobne modyfikacje uzyskujemy jedno wyrażenie wyrażające inne.

Trywialne dowody

Trywialny dowód (lub też oczywisty dowód) to terminus technicus dla dowodu, który nie mieści się na tablicy, więc jest pomijany, a uczeń uczy się go ze skryptu do pracy domowej. :-) A tak na poważnie - trywialne dowody to takie, które zazwyczaj wynikają z jakiejś definicji w jednym trywialnym kroku.

Spróbujmy to zilustrować przykładem: rozważmy zbiór liczb naturalnych, czyli zbiór liczb ℕ = {1, 2, 3, …}. Możemy teraz powiedzieć, że każdy ułamek postaci:

$$\frac{q}{p}; \qquad q,p\in\mathbb{N}$$

jest ułamkiem poprawnym, tzn. nie znajdziemy pary liczb q, p, dla których dany ułamek jest bezsensowny. Jak moglibyśmy to udowodnić? Najpierw musimy ustalić, kiedy ułamek nie ma sensu. Ułamek jest bezsensowny, gdy w mianowniku jest zero (nie możemy dzielić przez zero). Musimy więc udowodnić, że p≠0 dla wszystkich możliwych p. Wiemy jednak, że p pochodzi z liczb naturalnych, które zdefiniowaliśmy jako ℕ = {1, 2, 3, …}. Zbiór liczb naturalnych nie zawiera zera, więc liczba p zawsze będzie różna od zera.

$$\forall p\in\mathbb{N}: p\ne 0$$

I przeprowadziliśmy dowód. Wiemy, że jeśli zarówno licznik, jak i mianownik ułamka są liczbami naturalnymi, to ułamek będzie poprawny.

Trywialne dowody są zwykle naprawdę trywialne, ale tylko wtedy, gdy znasz otaczający kontekst. Na przykład, jeśli nie rozumiesz pojęcia zbioru lub nie wiesz, co to znaczy, że p jest elementem zbioru ℕ, to ten dowód również nie był dla ciebie trywialny. Trywialne dowody charakteryzują się nie tyle prostotą, co krótkością i wynikają po prostu z pewnego (dowolnie trudnego) kontekstu.

Kontrprzykład

Kontrprzykład jest prawdopodobnie najprostszą formą udowodnienia, że dane wyrażenie nie jest prawdziwe. Ważną rzeczą jest słowo nie jest. Kontrprzykład może faktycznie wskazywać na przypadek, w którym dane stwierdzenie nie jest prawdziwe, ale generalnie nawet wiele przykładów nie wystarczy, gdy w grze jest nieskończenie wiele elementów do przetestowania.

Przykład: "każda liczba naturalna jest większa od dziesięciu". Jak udowodnić, że to stwierdzenie nie jest prawdziwe? Kontrprzykładem dla naszego stwierdzenia jest na przykład liczba pięć. Liczba pięć jest liczbą naturalną i nie jest większa od dziesięciu. Nie możemy udowodnić tego stwierdzenia, wymieniając kilka liczb naturalnych, które są większe od dziesięciu. Nie można powiedzieć, że "liczby naturalne 11, 12, 13, 123 i 5345 są większe od 10, więc twierdzenie jest prawdziwe". Nie można. Wybraliśmy tylko kilka przykładów, dla których nasze stwierdzenie jest prawdziwe, ale to nie mówi nic o innych liczbach, których w ogóle nie wymieniliśmy.

Drugi przykład: każdy mężczyzna powyżej sześciu stóp wzrostu ma brązowe lub niebieskie oczy. Przypuszczam, że niewiele osób jest w stanie znaleźć kontrprzykład. Co to mówi nam o stwierdzeniu, o którym mowa? Cóż, zupełnie nic. Jeśli nie możemy znaleźć kontrprzykładu, nie musi to oznaczać, że dane stwierdzenie jest prawdziwe. Kontrprzykład może gdzieś istnieć, po prostu nie jesteśmy w stanie go teraz znaleźć. Brak możliwości znalezienia kontrprzykładu nie dowodzi, że twierdzenie jest prawdziwe.

Dowód bezpośredni

Podstawowym rodzajem dowodu jest dowód bezpośredni. Podążamy sucho za definicją i modyfikujemy początkowe stwierdzenie, aż otrzymamy stwierdzenie, które chcemy uzyskać. Zazwyczaj chcemy udowodnić twierdzenie, które ma postać implikacji $A\Rightarrow B$, gdzie A to jakiś punkt wyjścia, założenie, a B to twierdzenie, które chcemy wyprowadzić, udowodnić. Jeśli twierdzenie A jest prawdziwe, to twierdzenie B jest prawdziwe. Często otrzymujemy tylko twierdzenie B, tj. to, co chcemy udowodnić, i musimy odpowiednio wybrać twierdzenie A.

Poniższa procedura wykorzystuje implikację do wyprowadzenia kolejnych twierdzeń, a ostatnim twierdzeniem jest twierdzenie B. Schematycznie można to zapisać następująco:

$$A\Rightarrow A_1\Rightarrow A_2\Rightarrow A_3\Rightarrow\ldots \Rightarrow A_n \Rightarrow B$$

Jako przykład udowodnimy, że twierdzenie

$$a>1\Rightarrow a^2>1$$

Teraz w krokach:

1. Skoro a>1, to na pewno a>0 też zachodzi i tak samo a≠0 (w rzeczywistości tylko osłabiamy warunek).

• Ponieważ a nie jest równe zero i jest dodatnie, możemy bezpiecznie pomnożyć zmienną a przez całą nierówność. Gdyby a było zerem, nie moglibyśmy w ogóle mnożyć; gdyby było ujemne, musielibyśmy odwrócić nierówność. Po pomnożeniu przez zmienną a otrzymujemy wyrażenie a²>a.
• W tym momencie wiemy, że a>1 i wiemy również, że a²>a. Jeśli złożymy te dwa wyrażenia razem, otrzymamy: a²>a>1.
• Z tego miejsca usuwamy środkowe wyrażenie i otrzymujemy wyrażenie a²>1. Możemy sobie na to pozwolić, ponieważ a jest większe niż jeden, a a² jest większe niż a. Jeśli a² jest większe niż a, a a jest również większe niż jeden, to z pewnością a² jest większe niż jeden.

Symbolicznie moglibyśmy zapisać to w ten sposób:

$$a>1\Rightarrow a>0 \Rightarrow a^2>a \Rightarrow a^2>a>1 \Rightarrow a^2>1.$$

Dowód pośredni

Dowód pośredni w większym stopniu wykorzystuje właściwości implikacji. Jeśli musimy udowodnić twierdzenie o postaci $A\Rightarrow B$, możemy użyć odwróconej implikacji i udowodnić, że

$$\neg B \Rightarrow \neg A.$$

Takie podejście może być czasami wygodniejsze niż, powiedzmy, dowód bezpośredni. Dowód przez zaprzeczenie wykorzystuje podobną procedurę, do której można odwzorować dowolny dowód pośredni. Spróbujmy pośrednio udowodnić twierdzenie

$$a-b=0\Rightarrow a=b.$$

Dokonamy teraz odwrócenia implikacji:

$$\begin{eqnarray} \neg(a=b)&\Rightarrow&\neg(a-b=0)\\ a\ne b&\Rightarrow&a-b\ne0 \end{eqnarray}$$

Jeśli a≠ b, to możemy rozłożyć b na sumę b = a + x, gdzie x reprezentuje odległość b od a. Wyrażenie zmienia się następująco:

$$a\ne (a+x)\Rightarrow a-(a+x)\ne0;\quad x\ne0$$

Odejmij te zmienne a, co możemy:

$$0\ne x\Rightarrow x\ne 0; \quad x\ne0$$

Widzimy, że wszędzie tam, gdzie mamy, że x jest różne od zera, twierdzenie jest udowodnione, a zatem oryginalne twierdzenie jest prawdziwe

$$a-b=0\Rightarrow a=b.$$

Inne techniki dowodzenia to na przykład wspomniany już dowód przez spór lub dowód przez indukcję.

Inne źródła

• Dowód matematyczny w Wikipedii