Problemy, dowody i granice matematycznej wiedzy - ciekawostki, fakty, historie

Ciąg Goodsteina potrafi rosnąć niewyobrażalnie długo, zawsze spada do zera — ale arytmetyka Peana nie potrafi udowodnić tego ogólnego faktu

W ciągu Goodsteina liczbę zapisuje się w dziedzicznej postaci potęgowej w pewnej podstawie, zwiększa podstawę o 1, a następnie odejmuje 1. Początkowo wartości mogą eksplodować do gigantycznych rozmiarów. Mimo to twierdzenie Goodsteina mówi, że każdy taki ciąg ostatecznie osiąga zero. Kirby i Paris wykazali, że tego uniwersalnego stwierdzenia nie można udowodnić w arytmetyce Peana, jeśli PA jest spójna. Twierdzenie jest jednak dowodliwe w silniejszych systemach, wykorzystując porządek liczb porządkowych poniżej ε₀.

Dostatecznie silny spójny system nie może własnymi metodami udowodnić własnej spójności

Drugie twierdzenie Gödla o niezupełności idzie krok dalej niż pierwsze. Dla odpowiednio silnego, efektywnie aksjomatyzowanego i spójnego systemu arytmetycznego F naturalne zdanie wyrażające „F jest spójny” nie może być udowodnione w samym F. Nie oznacza to, że spójności takiego systemu nie da się nigdy uzasadnić. Można użyć silniejszej teorii lub argumentów zakładających więcej. Granica polega na tym, że system nie może, przy spełnieniu warunków twierdzenia, zamknąć w sobie własnego certyfikatu spójności.

Dowód hipotezy Keplera został po latach przepisany tak, aby mógł sprawdzić go asystent dowodów

Hipoteza Keplera z 1611 roku mówi, że najgęstsze możliwe upakowanie jednakowych kul w przestrzeni nie jest gęstsze od układu znanego z warstw kul ułożonych jak pomarańcze. Thomas Hales ogłosił komputerowo wspomagany dowód w 1998 roku, ale jego rozmiar i zależność od obliczeń sprawiły, że proces recenzji był wyjątkowo trudny. Hales uruchomił więc projekt Flyspeck: zamiast tylko przekonywać ludzi, postanowiono przełożyć cały argument na formalny język sprawdzany przez systemy HOL Light i Isabelle. Projekt zakończono w 2014 roku, a formalny dowód opublikowano w 2015.

Dwie bryły mogą mieć tę samą objętość, a mimo to nie dać się pociąć na skończone kawałki i przełożyć jedna w drugą

W płaszczyźnie każde dwa wielokąty o równym polu można pociąć na skończoną liczbę wielokątnych kawałków i złożyć jeden z drugiego. Hilbert zapytał, czy to samo zachodzi dla wielościanów o równej objętości. Max Dehn już około 1900 roku wykazał, że nie. Zbudował dodatkowy niezmiennik zależny od długości krawędzi i kątów dwuściennych. Sześcian i odpowiednio przeskalowany regularny czworościan mogą mieć równe objętości, ale różne niezmienniki Dehna, więc żadne skończone cięcie na wielościenne części nie pozwoli złożyć jednego w drugi.

Gauss odkrył, że regularny siedemnastokąt da się skonstruować metodą znaną od starożytności

Przez około dwa tysiące lat po Euklidesie nie znaleziono zasadniczo nowego regularnego wielokąta konstruowalnego wyłącznie cyrklem i linijką. W 1796 roku dziewiętnastoletni Carl Friedrich Gauss wykazał, że regularny 17-kąt można zbudować dokładnie tymi narzędziami. Wynik wynika z głębokiego związku między wielokątami, pierwiastkami z jedności i szczególnymi liczbami pierwszymi Fermata. Odkrycie było nie tylko nową konstrukcją geometryczną: zapowiadało algebraiczny język, który później pozwolił dokładnie sklasyfikować możliwe i niemożliwe konstrukcje.

Hipoteza Bircha i Swinnertona-Dyera próbuje odczytać liczbę rozwiązań równania z zachowania zupełnie innej funkcji

Krzywa eliptyczna ma postać równania sześciennego, na przykład y²=x³+ax+b, a jednym z podstawowych pytań jest liczba jej punktów o współrzędnych wymiernych. Hipoteza Bircha i Swinnertona-Dyera przewiduje niezwykły związek: rangę grupy punktów wymiernych ma kodować rząd zera odpowiedniej funkcji L w punkcie s=1. Innymi słowy, informacja arytmetyczna o rozwiązaniach równania ma być zapisana w zachowaniu funkcji analitycznej. Hipoteza jest wsparta wieloma wynikami i obliczeniami, ale w pełnej ogólności pozostaje nierozwiązanym Problemem Milenijnym.

Hipoteza Hodge’a pyta, które fragmenty topologii skomplikowanego kształtu naprawdę pochodzą z równań algebraicznych

Zbiory rozwiązań wielomianów mogą tworzyć bardzo skomplikowane przestrzenie geometryczne. Topologia pozwala badać ich globalny kształt za pomocą klas homologii i kohomologii, a geometria algebraiczna wyróżnia podzbiory opisane dodatkowymi równaniami algebraicznymi. Hipoteza Hodge’a przewiduje, że określona klasa topologicznych obiektów — racjonalne klasy Hodge’a — powinna być kombinacją klas pochodzących z cykli algebraicznych. W pewnych niskich wymiarach wynik jest znany, ale w ogólności pozostaje otwartym Problemem Milenijnym.

Hipoteza Poincarégo czekała prawie sto lat, a jej rozwiązanie udowodniło coś znacznie większego

Hipoteza Poincarégo z 1904 roku pytała, czy każda zamknięta, po prostu spójna trójwymiarowa rozmaitość jest w istocie trójwymiarową sferą. Grigorij Perelman rozwiązał problem w preprintach z lat 2002–2003, rozwijając program przepływu Ricciego Richarda Hamiltona. Co ważne, jego praca nie ograniczała się do samej hipotezy Poincarégo: dostarczyła kluczowych elementów dowodu znacznie szerszej hipotezy geometryzacji Thurstona, opisującej strukturę trójwymiarowych rozmaitości. Rozwiązanie jednego słynnego problemu okazało się więc częścią większej teorii klasyfikacji przestrzeni.

Hipoteza Riemanna nie przewiduje, gdzie są liczby pierwsze — kontroluje, jak bardzo ich rozmieszczenie może odchylać się od średniej

Hipoteza Riemanna, sformułowana w 1859 roku, mówi że wszystkie nietrywialne zera funkcji dzeta Riemanna mają część rzeczywistą równą 1/2. Na pierwszy rzut oka brzmi to jak problem z analizy zespolonej, ale zera funkcji dzeta są głęboko powiązane z rozmieszczeniem liczb pierwszych. Twierdzenie o liczbach pierwszych opisuje ich średnią gęstość; hipoteza Riemanna dawałaby bardzo silną kontrolę nad błędem tego przybliżenia. Według Clay Mathematics Institute problem pozostaje nierozwiązany, mimo sprawdzenia ogromnej liczby pierwszych zer numerycznie.

Kwadratura koła została rozwiązana przez dowód, że wymaganej konstrukcji nie da się wykonać

Przez ponad dwa tysiące lat próbowano skonstruować wyłącznie cyrklem i linijką kwadrat o takim samym polu jak dany okrąg. Dla okręgu o promieniu 1 bok takiego kwadratu musiałby mieć długość √π. Klasyczne konstrukcje mogą tworzyć tylko liczby należące do określonej klasy algebraicznej. Gdy Ferdinand von Lindemann udowodnił w 1882 roku, że π jest liczbą transcendentalną, wynik automatycznie wykluczył konstrukcję √π tymi narzędziami. Ostatecznym rozwiązaniem zadania nie był więc rysunek, lecz dowód, że żaden taki rysunek zgodny z regułami nie może istnieć.

Marzenie o jednej mechanicznej procedurze rozstrzygającej całą logikę pierwszego rzędu zostało matematycznie obalone

Entscheidungsproblem, sformułowany przez Hilberta i Ackermanna, pytał o algorytm, który dla dowolnej formuły logiki pierwszego rzędu zawsze rozstrzygnie, czy jest ona logicznie prawdziwa we wszystkich strukturach. W 1936 roku Alonzo Church i Alan Turing, używając różnych formalizmów obliczalności, wykazali że taka ogólna procedura nie istnieje. Wynik nie oznacza, że żadnych fragmentów logiki nie da się automatycznie rozstrzygać — wiele szczególnych teorii ma procedury decyzyjne. Upadł pomysł jednego uniwersalnego mechanizmu dla całej logiki pierwszego rzędu.

Miliony sprawdzonych przypadków hipotezy Goldbacha nie zastępują jednego dowodu dla wszystkich liczb

Silna hipoteza Goldbacha mówi, że każda parzysta liczba całkowita większa od 2 jest sumą dwóch liczb pierwszych. Komputery potwierdziły ją dla ogromnych zakresów, a teoria liczb zna bardzo mocne wyniki częściowe, lecz ogólny dowód nadal nie jest znany. Co ciekawe, słabszy wariant — że każda nieparzysta liczba większa od 5 jest sumą trzech liczb pierwszych — został udowodniony przez Haralda Helfgotta. To świetny przykład różnicy między „sprawdziliśmy niewyobrażalnie dużo przykładów”, „udowodniliśmy bliski wariant” i „mamy pełny dowód pierwotnego twierdzenia”.

Nie da się cyrklem i linijką podzielić każdego kąta na trzy równe części

Trysekcja kąta jest często opowiadana tak, jakby matematycy przez wieki po prostu nie znaleźli wystarczająco sprytnej konstrukcji. W 1837 roku Pierre Wantzel udowodnił coś znacznie mocniejszego: ogólna trysekcja nie jest możliwa przy użyciu wyłącznie klasycznego cyrkla i nieoznaczonej linijki. Niektóre kąty — na przykład 90° — oczywiście można podzielić na trzy części, a dowolny kąt można trisektować przy użyciu dodatkowych narzędzi lub krzywych. Niemożliwość dotyczy dokładnie uniwersalnej konstrukcji w określonym modelu geometrycznym.

Nie istnieje odpowiednik wzoru kwadratowego dla wszystkich równań piątego stopnia

Po znalezieniu wzorów rozwiązujących ogólne równania trzeciego i czwartego stopnia matematycy przez stulecia szukali analogicznej formuły dla równania stopnia piątego. Ostatecznie Ruffini i przede wszystkim Niels Henrik Abel wykazali, że ogólnego równania piątego stopnia nie da się rozwiązać przez skończoną kombinację dodawania, odejmowania, mnożenia, dzielenia i wyciągania pierwiastków z współczynników. Nie oznacza to, że równania piątego stopnia nie mają pierwiastków ani że żadne konkretne równanie nie jest rozwiązywalne przez pierwiastniki. Niemożliwa jest uniwersalna formuła tego określonego typu.

Niedowodliwość w arytmetyce Peana pojawia się nawet w skończonej kombinatoryce, bez zdań mówiących o własnej dowodliwości

Twierdzenie Parisa–Harringtona jest pozornie niewielkim wzmocnieniem skończonego twierdzenia Ramseya. Dodaje warunek, że znaleziony jednorodny zbiór ma być „duży” także w relacji do swojego najmniejszego elementu. Paris i Harrington wykazali w 1977 roku, że to zdanie jest prawdziwe, ale nie jest dowodliwe w arytmetyce Peana, jeśli PA jest spójna. Był to przełom, ponieważ pokazał naturalną matematyczną niezależność bez kodowania zdania w stylu Gödla o samym systemie dowodowym. Kluczowe jest przy tym odróżnienie ścisłego wyniku matematycznego od popularnego skrótu: twierdzenie mówi dokładnie o określonych założeniach i nie daje automatycznie szerszych wniosków.

Nierozstrzygalność ukrywa się nawet w zwykłej algebrze: istnieją skończenie opisane grupy bez algorytmu rozwiązywania problemu słowa

Grupę można opisać przez skończony zestaw generatorów i relacji. Problem słowa pyta wtedy, czy dany ciąg generatorów reprezentuje element neutralny — równoważnie, czy dwa różne zapisy oznaczają ten sam element grupy. Dla wielu grup istnieją proste algorytmy. Jednak P. S. Novikov i William Boone wykazali w latach 50., że istnieją skończenie prezentowane grupy, dla których żaden algorytm nie rozstrzyga problemu słowa dla wszystkich wejść. Granica obliczalności pojawia się więc wewnątrz klasycznej algebry, nie tylko w teorii maszyn Turinga.

Podwojenie sześcianu wymaga liczby, której klasyczny cyrkiel i linijka nie potrafią skonstruować

Jeśli sześcian ma bok długości 1, jego objętość wynosi 1. Sześcian o dwukrotnie większej objętości musi mieć bok długości ∛2. Starożytni znaleźli liczne rozwiązania problemu przy użyciu dodatkowych krzywych i urządzeń, ale przez ponad dwa tysiące lat nie było wiadomo, czy istnieje konstrukcja wyłącznie cyrklem i linijką. W 1837 roku Wantzel udowodnił, że nie: ∛2 ma stopień algebraiczny 3, podczas gdy liczby możliwe do skonstruowania klasycznymi narzędziami powstają przez rozszerzenia stopnia będącego potęgą 2.

Regularny siedmiokąt wygląda niewinnie, ale dokładnie nie da się go skonstruować klasycznym cyrklem i linijką

Regularny trójkąt, kwadrat, pięciokąt i sześciokąt mają klasyczne konstrukcje. Naturalne byłoby oczekiwanie, że po prostu potrzeba sprytniejszego rysunku dla siedmiokąta. Tymczasem regularny 7-kąt nie jest konstrukcyjny w klasycznym sensie. Pełne kryterium Gaussa–Wantzela mówi, że liczba boków musi być iloczynem potęgi 2 i różnych pierwszych liczb Fermata. Liczba 7 nie ma tej postaci. Można więc konstruować bardzo dobre przybliżenia, używać oznaczonej linijki albo origami, ale nie istnieje dokładna klasyczna konstrukcja.

Reguła Collatza jest łatwiejsza do wykonania niż do zrozumienia

Weź dodatnią liczbę całkowitą. Jeśli jest parzysta, podziel ją przez 2; jeśli nieparzysta, pomnóż przez 3 i dodaj 1. Powtarzaj. Hipoteza Collatza mówi, że każda liczba w końcu trafia do 1. Regułę może wykonać dziecko, ale nikt nie zna pełnego dowodu. Ogromne obliczenia potwierdzają zachowanie dla wielkich zakresów, a Terence Tao udowodnił bardzo mocny wynik mówiący, że „prawie wszystkie” orbity schodzą poniżej dowolnej funkcji rosnącej do nieskończoności. To jednak nadal nie wyklucza pojedynczej wyjątkowej orbity.

Twierdzenie Gödla nie mówi, że „niczego nie da się udowodnić” — mówi, że każdy dostatecznie silny system ma własne nierozstrzygalne zdania

Pierwsze twierdzenie Gödla o niezupełności dotyczy formalnych, efektywnie aksjomatyzowanych i spójnych systemów zdolnych wyrazić dostatecznie dużo arytmetyki. W takim systemie istnieją zdania, których nie można w nim ani udowodnić, ani obalić. To nie jest twierdzenie o ludzkiej niewiedzy, względności prawdy ani o tym, że „wszystko jest niedowodliwe”. Granica jest zawsze względna wobec konkretnego systemu formalnego. Można przejść do silniejszego systemu i dowieść wcześniej nierozstrzygalnego zdania — lecz nowy system, jeśli spełnia warunki twierdzenia, będzie miał własne nierozstrzygalne zdania.

Twierdzenie o czterech barwach zmieniło dyskusję o tym, czym jest akceptowalny dowód

Twierdzenie o czterech barwach mówi, że regiony każdej mapy na płaszczyźnie można pokolorować najwyżej czterema kolorami tak, aby regiony mające wspólny odcinek granicy otrzymały różne kolory. W 1976 roku Kenneth Appel i Wolfgang Haken uzyskali pierwszy powszechnie przyjęty dowód, ale jego zasadnicza część wymagała komputerowego sprawdzenia dużej liczby konfiguracji. Nie dało się po prostu przeczytać całego dowodu linijka po linijce jak klasycznego tekstu. Później Georges Gonthier sformalizował twierdzenie w systemie Coq, dzięki czemu komputer sprawdzał już nie tylko przypadki, lecz także formalną poprawność całej konstrukcji.

Umiemy udowodnić, że nieskończenie często liczby pierwsze są blisko siebie — ale nie, że zawsze wystarczy odstęp 2

Hipoteza bliźniaczych liczb pierwszych mówi, że istnieje nieskończenie wiele par liczb pierwszych różniących się o 2, takich jak 11 i 13. W 2013 roku Yitang Zhang dokonał przełomu, udowadniając po raz pierwszy bezwarunkowo, że istnieje jakaś stała B, dla której nieskończenie wiele kolejnych liczb pierwszych ma odstęp nie większy niż B. Kolejne prace Maynarda i projektu Polymath dramatycznie zmniejszyły tę granicę; znany bezwarunkowy limit wynosi 246. To ogromny krok od „odstępy czasem są ograniczone”, ale nadal nie 2.

Wielkie twierdzenie Fermata rozwiązano po ponad 350 latach — za pomocą matematyki, której Fermat nie znał

Wielkie twierdzenie Fermata mówi, że równanie x^n + y^n = z^n nie ma niezerowych rozwiązań całkowitych dla n>2. Sformułowanie jest elementarne, ale droga do dowodu okazała się niezwykle głęboka. Andrew Wiles nie znalazł prostego argumentu ukrytego w marginesie książki Fermata; udowodnił wystarczający przypadek związku między krzywymi eliptycznymi i formami modularnymi, z którego twierdzenie Fermata wynikało. Co więcej, ogłoszony w 1993 roku dowód zawierał lukę. Wiles i Richard Taylor naprawili ją w 1994 roku inną metodą, a prace ukazały się w 1995 roku.