Dowody i obalenia
W podręcznikach historia twierdzenia jest zwykle bardzo krótka: najpierw pojawia się precyzyjne sformułowanie, a zaraz po nim poprawny dowód. Można odnieść wrażenie, że twierdzenia od początku mają swoją ostateczną postać, a jedynym zadaniem matematyka jest znalezienie argumentu, który tę postać uzasadni.
Lakatos (1976) proponuje zupełnie inny obraz matematyki.
Od przykładów do hipotezy
Zacznijmy od kilku dobrze znanych brył. Oznaczmy przez \(V\) liczbę wierzchołków, przez \(E\) liczbę krawędzi, a przez \(F\) liczbę ścian.
| Wielościan | V | E | F |
|---|---|---|---|
| czworościan | 4 | 6 | 4 |
| sześcian | 8 | 12 | 6 |
| ośmiościan | 6 | 12 | 8 |
| dwunastościan | 20 | 30 | 12 |
| dwudziestościan | 12 | 30 | 20 |
Widzimy, że punkty \((V,E,F)\) leżą na jednej płaszczyźnie. Matematycznie oznacza to, że istnieją liczby \(a, b, c, d\), takie że dla dowolnego wielościanu \[\begin{equation*} aV+bE+cF =d. \end{equation*}\]
Dla czworościanu otrzymujemy \[\begin{equation*} 4a + 6b +4c=d. \end{equation*}\] Dla sześcianu jest to \[\begin{equation*} 8a+ 12b+ 6c=d. \end{equation*}\] Rozważając kolejne bryły, możemy podać wiele różnych równań, które spełniają liczby \(a,b,c,d\). Układ takich równań możemy następnie rozwiązać i otrzymać \(a=c=1\), \(b=-1\) i \(d=2\). Nasuwa to przypuszczenie, że dla każdego wielościanu \[ V-E+F=2. \]
Hipoteza 1 Dla każdego wielościanu liczba wierzchołków minus liczba krawędzi plus liczba ścian jest równa \(2\).
Dowód, który wygląda przekonująco
Wyobraźmy sobie, że powierzchnia wielościanu jest wykonana z cienkiej gumy. Usuwamy jedną ścianę, a pozostałą powierzchnię rozciągamy na płaszczyźnie. Obraz rozciągniętego wielościanu na płaszczyźnie nazywamy mapą.
Usunięcie ściany zmniejsza \(F\) o jeden, powinniśmy więc otrzymać płaską mapę spełniającą \[ V-E+F=1. \] Następnie dzielimy wszystkie ściany tej mapy na trójkąty. Za każdym razem, gdy rysujemy nową przekątną, liczba krawędzi i liczba ścian zwiększają się o jeden. Wartość \(V-E+F\) się zatem nie zmienia.
Na koniec usuwamy trójkąty jeden po drugim. Przy każdym kroku znika albo
- jedna ściana i jedna krawędź,
- jedna ściana, dwie krawędzie i jeden wierzchołek.
Również te operacje nie zmieniają wartości \(V-E+F\). Ostatecznie pozostaje pojedynczy trójkąt, dla którego \[ V-E+F=3-3+1=1. \] Przed usunięciem pierwszej ściany wartość musiała więc wynosić \(2\).
Analiza argumentu
Nie traktujmy powyższego dowodu jak niepodzielnego bloku. Należy rozłożyć go na ukryte w nim twierdzenia pomocnicze. Są to co najmniej trzy lematy.
Lemat 1 Po usunięciu jednej ściany powierzchnię każdego wielościanu można bez rozrywania rozciągnąć na płaszczyźnie.
Lemat 2 Każdą ścianę otrzymanej siatki można podzielić przekątnymi na trójkąty, nie zmieniając wartości \(V-E+F\).
Lemat 3 Trójkąty można usuwać w dowolnej kolejności. Przy każdym usunięciu znika albo jedna ściana i jedna krawędź, albo jedna ściana, dwie krawędzie i jeden wierzchołek. Wartość \(V-E+F\) pozostaje więc niezmieniona aż do pozostawienia pojedynczego trójkąta.
Jeżeli wszystkie trzy lematy są prawdziwe, dowód działa. Każdy z nich jest jednak osobnym przypuszczeniem, które możemy próbować obalić. Z jednej strony dołożyliśmy sobie więcej pracy, bo zamiast sprawdzać poprawność naszej hipotezy musimy sprawdzić poprawność trzech lematów. Zauważmy jednak, że wszystkie są koncepcyjnie prostsze i dotyczą bardzo konkretnych własności, przez co powinny być łatwiejsze do rozstrzygnięcia. To ważna zmiana perspektywy. Dowód nie tylko prowadzi od założeń do wniosku. Dowód rozkłada duże twierdzenie na mniejsze zobowiązania. Pokazuje, co dokładnie musiałoby być prawdą, aby wniosek rzeczywiście wynikał z naszego pomysłu.
Pierwszy kontrprzykład: trójkąt ze środka
Wróćmy do triangulacji sześcianu. Co się stanie, jeśli jako pierwszy usuniemy trójkąt leżący całkowicie wewnątrz siatki? Nie znika wtedy żadna krawędź ani żaden wierzchołek. Znika tylko jedna ściana. Wartość \(V-E+F\) zmniejsza się o \(1\). Trzeci krok dowodu w swojej najprostszej wersji jest więc fałszywy.
Można w tym momencie stwierdzić, że to koniec dowodu. Czy to również koniec naszej hipotezy? Nie. Pokazaliśmy, że konkretny argument nie działa; nie znaleźliśmy jeszcze wielościanu naruszającego wzór. Pokazaliśmy jedynie, że nie wolno usuwać trójkątów w zupełnie dowolnej kolejności.
Wprowadzimy teraz rozróżnienie pochodzące z Lakatos (1976).
Definicja 1 Kontrprzykład lokalny obala jeden z lematów użytych w dowodzie, ale nie musi obalać głównego przypuszczenia.
Sześcian z niefortunnie wybranym trójkątem jest kontrprzykładem lokalnym. Pokazuje, że dowód jest wadliwy, nie pokazuje jednak, że Hipoteza 1 jest fałszywa.
Hotfix
Spróbujmy poprawić dowód. Nie usuwajmy dowolnych trójkątów. Usuwajmy jedynie trójkąty leżące na brzegu aktualnej siatki.
Trzeci lemat został więc zastąpiony ostrożniejszą wersją:
Trójkąty brzegowe można usuwać w dowolnej kolejności, a każdy taki ruch ma jedną z dwóch bezpiecznych postaci.
Ta poprawka rozwiązuje poprzedni problem, ale tworzy następny. Nawet trójkąty brzegowe można usuwać w złej kolejności. W triangulacji sześcianu da się usunąć osiem trójkątów tak, że na końcu zostaną dwa rozłączne trójkąty. Podczas jednego z ostatnich ruchów usuwamy ścianę i dwie krawędzie, ale nie usuwamy wierzchołka. Wartość \(V-E+F\) znowu się zmienia.
W takim razie powinniśmy usuwać tylko takie trójkąty brzegowe, których usunięcie nie rozspójnia pozostałej siatki. Problem polega na tym, że to nie jest jeszcze instrukcja. Skąd wiadomo, że taki trójkąt zawsze istnieje? I skąd wiadomo, że po jego usunięciu następny również będzie istniał?
Istnienie tej kolejności jest teraz nowym twierdzeniem. Nie wolno umieszczać go w dowodzie pod postacią polecenia: „wybieramy dobrą kolejność”. Zdanie
usuwamy trójkąty w takiej kolejności, aby wszystko działało
nie jest argumentem. Jest jedynie innym sposobem zapisania tego, co należało udowodnić.
Potrzebujemy zatem trzeciej wersji lematu:
Trójkąty triangulowanej mapy można tak ponumerować, aby usuwanie ich w tej kolejności zachowywało wartość \(V-E+F\) aż do ostatniego trójkąta.
Zatrzymamy się na chwilę i spróbujemy uzupełnić tę lukę. Poniższa wersja wykorzystuje indukcyjny argument opisany również przez Eppstein (b.d.) .
Nazwijmy trójkąt dobrym, jeśli leży na brzegu siatki i po jego usunięciu pozostałe trójkąty nadal tworzą jeden spójny kawałek w kształcie dysku.
Potrzebujemy następującego faktu.
Lemat 4 Jeżeli triangulowana mapa składa się z więcej niż jednego trójkąta, to zawiera co najmniej dwa dobre trójkąty brzegowe.
Dowód tego lematu odłożymy na sam koniec.
Lemat dostarcza brakującej instrukcji. Wybieramy dobry trójkąt i usuwamy go. Pozostaje mniejsza triangulowana mapa, więc lemat można zastosować ponownie. Ponieważ trójkątów jest skończenie wiele, po pewnej liczbie kroków zostanie jeden z nich.
Na naszym rysunku sześcianu można najpierw usunąć cztery trójkąty przylegające do czterech boków zewnętrznego kwadratu. Następnie usuwamy cztery odsłonięte „uszy”, a na końcu jeden z dwóch środkowych trójkątów. W każdym kroku zmiany liczb \((V,E,F)\) mają jedną z dwóch bezpiecznych postaci opisanych wcześniej.
Współczesnym językiem taka dobra kolejność ścian nazywa się shellingiem. Samo podanie nazwy niczego jednak nie dowodzi. Matematyczna treść tkwi w argumencie pokazującym, że odpowiednią kolejność rzeczywiście można znaleźć.
Czy hipoteza została już udowodniona?
Naprawiliśmy trzeci krok argumentu. Nie oznacza to jeszcze, że dowód działa dla każdego obiektu, który moglibyśmy nazwać wielościanem. Nadal korzystamy z dwóch wcześniejszych założeń:
- po usunięciu ściany powierzchnię można rozłożyć na jeden płaski dysk;
- każda ściana jest zwykłym wielokątem, który można podzielić przekątnymi na trójkąty.
Dotychczas założenia te wyglądały niewinnie, ponieważ wszystkie rozważane bryły były wypukłe i przypominały zdeformowaną sferę. Poszukajmy obiektów, które wystawią te założenia na próbę.
Sześcienna skorupa
Wyobraźmy sobie duży sześcian, z którego wnętrza wycięto mniejszy sześcian, nie przebijając się na zewnątrz. Powierzchnia otrzymanej bryły ma dwie części: zewnętrzną powierzchnię dużego sześcianu oraz wewnętrzną powierzchnię otaczającą pustą komorę.
Każda z tych powierzchni ma osiem wierzchołków, dwanaście krawędzi i sześć ścian. Łącznie otrzymujemy \[\begin{equation*} V-E+F=16-24+12=4. \end{equation*}\] Jest wielościanem, dla którego \(V-E+F\neq2\).
Definicja 2 Kontrprzykład globalny obala główne przypuszczenie.
To nie jest już wyłącznie krytyka dowodu. Otrzymaliśmy obiekt, dla którego główne przypuszczenie zawodzi. Jest to kontrprzykład globalny.
- Odrzucić hipotezę.
- Uznać, że sześcienna skorupa nie jest prawdziwym wielościanem.
- Zachować hipotezę, ale jawnie wykluczyć bryły z wewnętrznymi komorami.
- Wrócić do dowodu i sprawdzić, który jego krok nie działa dla skorupy.
Każda z tych odpowiedzi reprezentuje inną strategię metodologiczną.
Kapitulacja
Możemy powiedzieć: „Hipoteza była fałszywa, więc ją odrzucamy”. Jest to logicznie bez zarzutu, ale matematycznie mało owocne. Tracimy razem z fałszywą hipotezą fakt, że wzór działał dla wszystkich dotychczasowych zwykłych brył. Kontrprzykład powinien skłonić nas do pytania, co odróżnia skorupę od czworościanu czy sześcianu.
Wykluczenie potwora
Możemy także oznajmić, że skorupa nie jest wielościanem. Zmieniamy granice pojęcia w taki sposób, aby kłopotliwy obiekt znalazł się na zewnątrz.
Taka decyzja nie zawsze jest błędna. Definicje muszą gdzieś wyznaczać granice. Problem pojawia się wtedy, gdy jedynym uzasadnieniem zmiany jest chęć uratowania ulubionego twierdzenia. Jeśli przed zobaczeniem kontrprzykładu nazwalibyśmy skorupę wielościanem, a po jego zobaczeniu przestajemy to robić, powinniśmy wyjaśnić, dlaczego nowa definicja jest matematycznie użyteczna.
Wykluczenie wyjątku
Możemy osłabić hipotezę i powiedzieć na przykład:
Każdy wypukły wielościan spełnia \(V-E+F=2\).
To prawdziwe i ważne twierdzenie. Zwróćmy uwagę, że takie strategiczne wycofanie się do bezpiecznej klasy może przesłonić informację zawartą w dowodzie. Wypukłość jest warunkiem wystarczającym, ale wygląda na znacznie silniejszy, niż naprawdę potrzebujemy. Wiele niewypukłych wielościanów również spełnia wzór.
Włączenie lematu
Najbardziej pouczająca reakcja polega na powrocie do dowodu. Dla sześciennej skorupy zawodzi pierwszy krok. Po usunięciu jednej ściany zewnętrzna część powierzchni może zostać otwarta, ale powierzchnia wewnętrznej komory nadal pozostaje zamkniętym, oddzielnym składnikiem.
Dowód ujawnia więc ukryte założenie: powierzchnia nie może mieć zamkniętej komory odłączonej od powierzchni zewnętrznej. Zamiast arbitralnie odrzucać kontrprzykład, dołączamy wykryty warunek do twierdzenia.
Drugi potwór: rama z tunelem
Rozważmy teraz bryłę w kształcie grubej prostokątnej ramy. Można przełożyć przez nią rękę; jej powierzchnia ma jeden tunel.
Przy naturalnym podziale powierzchni na czworokąty otrzymujemy \[\begin{equation*} V-E+F=0. \end{equation*}\] Również tutaj nie działa pierwszy krok dowodu. Usunięcie jednej ściany nie pozwala rozciągnąć bryły na płaszczyźnie. Pozostaje obszar z otworem.
Twierdzenie wygenerowane przez dowód
Pierwotna hipoteza brzmiała:
Dla każdego wielościanu V-E+F=2.
Była to naiwna hipoteza: powstała z przykładów, zanim wiedzieliśmy, jakie własności obiektów będą istotne. Analiza dowodu i kontrprzykładów prowadzi do precyzyjniejszego stwierdzenia.
Twierdzenie 1 Niech wielościan składa się ze skończenie wielu zwykłych wielokątnych ścian. Załóżmy, że po usunięciu jednej ściany pozostałą powierzchnię można — wyginając i rozciągając, ale bez rozcinania ani sklejania — zamienić w jeden płaski obszar bez dziur. Wtedy \[\begin{equation*} V-E+F=2. \end{equation*}\]
Epilog
Historia nie musi kończyć się na wykluczeniu skorupy i ramy. Ich wyniki układają się w nowy wzór.
Jeżeli wielościan ma w sobie \(g\) tunelów, to zachodzi \[\begin{equation*}
V-E+F=2-2g.
\end{equation*}\] To znacznie bogatszy rezultat niż początkowe \(V-E+F=2\). Fałszywa naiwna hipoteza nie została po prostu wyrzucona. Została zastąpiona twierdzeniem, które wyjaśnia zarówno wcześniejsze przykłady, jak i kontrprzykłady.
Dowód brakującego lematu
Dowód. Zastosujemy indukcję względem liczby trójkątów. Dla dysku złożonego z dwóch trójkątów teza jest bezpośrednia: można bezpiecznie usunąć każdy z nich. Załóżmy teraz, że lemat jest prawdziwy dla wszystkich dysków złożonych z mniejszej liczby trójkątów.
Jeżeli każdy trójkąt brzegowy jest dobry, wynik jest oczywisty. Trójkątów brzegowych musi być co najmniej dwa: gdyby wszystkie krawędzie brzegu należały do jednego trójkąta, cała figura składałaby się tylko z niego.
Załóżmy więc, że istnieje zły trójkąt brzegowy \(T\), czyli taki, którego usunięcie rozcina pozostałą figurę na dwa mniejsze kawałki \(P_1\) i \(P_2\).
Rozważmy \(P_1\). Jeżeli składa się z jednego trójkąta, trójkąt ten można bezpiecznie usunąć z całej figury. Jeżeli zawiera więcej trójkątów, to z założenia indukcyjnego ma dwa dobre trójkąty brzegowe. Co najwyżej jeden z nich leży w miejscu, w którym \(P_1\) był połączony z \(T\). Drugi jest dobry także w całej wyjściowej figurze.
Tak samo postępujemy z \(P_2\). Otrzymujemy po jednym dobrym trójkącie z każdej strony \(T\), a więc co najmniej dwa dobre trójkąty w całej figurze.
Zadania
ToDo