W 1931 roku austriacki logik Kurt Gödel dokonał prawdopodobnie jednego z najbardziej zdumiewających osiągnięć intelektualnych w historii.
Matematycy tamtych czasów poszukiwali solidnego fundamentu dla matematyki: zestawu podstawowych faktów matematycznych lub aksjomatów, który byłby zarówno spójny – nigdy nie prowadził do sprzeczności – jak i kompletny, służąc jako budulec wszystkich prawd matematycznych.
Ale szokujące twierdzenia o niezupełności Gödla, opublikowane w wieku zaledwie 25 lat, zmiażdżyły to marzenie. Udowodnił on, że każdy zestaw aksjomatów, który można by przyjąć jako możliwą podstawę matematyki, będzie nieuchronnie niekompletny; zawsze będą istniały prawdziwe fakty dotyczące liczb, których nie da się udowodnić za pomocą tych aksjomatów. Pokazał również, że żaden kandydujący zestaw aksjomatów nigdy nie będzie w stanie udowodnić swojej własnej spójności.
Jego twierdzenia o niezupełności oznaczają, że nie może istnieć matematyczna teoria wszystkiego, żadne ujednolicenie tego, co jest możliwe do udowodnienia i tego, co jest prawdziwe. To, co matematycy mogą udowodnić, zależy od ich założeń wyjściowych, a nie od jakiejś fundamentalnej prawdy, z której wynikają wszystkie odpowiedzi.
W ciągu 89 lat od odkrycia Gödla matematycy natknęli się na takie właśnie rodzaje pytań bez odpowiedzi, jakie zapowiadały jego twierdzenia. Na przykład Gödel sam przyczynił się do ustalenia, że hipoteza continuum, dotycząca rozmiarów nieskończoności, jest nierozstrzygalna, podobnie jak problem haltingu, który pyta, czy program komputerowy zasilany losowymi danymi będzie działał wiecznie, czy też w końcu się zatrzyma. Nierozstrzygalne pytania pojawiły się nawet w fizyce, co sugeruje, że gödelowska niezupełność dotyka nie tylko matematyki, ale – w jakiś niezrozumiały sposób – rzeczywistości.
Oto uproszczony, nieformalny przegląd tego, jak Gödel udowadniał swoje twierdzenia.
Liczenie Gödla
Głównym manewrem Gödla było odwzorowanie twierdzeń o systemie aksjomatów na twierdzenia wewnątrz systemu – czyli na twierdzenia o liczbach. To odwzorowanie pozwala systemowi aksjomatów mówić logicznie o sobie.
Pierwszym krokiem w tym procesie jest odwzorowanie każdego możliwego twierdzenia matematycznego, lub serii twierdzeń, na unikalną liczbę zwaną liczbą Gödla.
Nieco zmodyfikowana wersja schematu Gödla przedstawiona przez Ernesta Nagela i Jamesa Newmana w ich książce z 1958 roku, Dowód Gödla, zaczyna się od 12 elementarnych symboli, które służą jako słownik do wyrażenia zestawu podstawowych aksjomatów. Na przykład, stwierdzenie, że coś istnieje, można wyrazić symbolem ∃, a dodawanie – symbolem +. Co ważne, symbol s, oznaczający „następnik”, daje możliwość określenia liczb; na przykład ss0 oznacza 2.
Tym dwunastu symbolom przypisuje się następnie liczby Gödla od 1 do 12.
| Znak stały | Liczba Gödla | Usual Meaning |
| ~ | 1 | nie |
| ∨ | 2 | or |
| ⊃ | 3 | if…then… |
| ∃ | 4 | there is an… |
| = | 5 | equals |
| 0 | 6 | zero |
| s | 7 | następca |
| ( | 8 | znak interpunkcyjny |
| ) | 9 | znak interpunkcyjny |
| , | 10 | znak interpunkcyjny |
| + | 11 | plus |
| × | 12 | times |
Następnie, litery reprezentujące zmienne, począwszy od x, y i z, odwzorowujemy na liczby pierwsze większe od 12 (czyli 13, 17, 19, …).
Wtedy każda kombinacja tych symboli i zmiennych – to znaczy każda formuła arytmetyczna lub ciąg formuł, które można skonstruować – otrzymuje swoją własną liczbę Gödla.
Na przykład, rozważmy 0 = 0. Trzy symbole formuły odpowiadają liczbom Gödla 6, 5 i 6. Gödel musi zmienić tę sekwencję trzech liczb w pojedynczą, unikalną liczbę – liczbę, której nie wygeneruje żadna inna sekwencja symboli. Aby to zrobić, bierze trzy pierwsze liczby (2, 3 i 5), podnosi każdą z nich do liczby Gödla odpowiadającej symbolowi znajdującemu się na tej samej pozycji w sekwencji i mnoży je razem. W ten sposób 0 = 0 staje się 26 × 35 × 56, czyli 243 000 000.
Odwzorowanie działa, ponieważ żadne dwie formuły nigdy nie skończą z tą samą liczbą Gödla. Liczby Gödla są liczbami całkowitymi, a liczby całkowite dzielą się na pierwiastki tylko w jeden sposób. Tak więc jedyną faktoryzacją liczb pierwszych 243 000 000 jest 26 × 35 × 56, co oznacza, że istnieje tylko jeden możliwy sposób rozszyfrowania liczby Gödla: formuła 0 = 0.
Gödel poszedł o krok dalej. Dowód matematyczny składa się z sekwencji formuł. Gödel nadał więc każdej sekwencji formuł unikalną liczbę Gödla. W tym przypadku zaczyna od listy liczb pierwszych, tak jak poprzednio – 2, 3, 5 i tak dalej. Następnie podnosi każdą liczbę pierwszą do numeru Gödla formuły na tej samej pozycji w sekwencji (2243 000 000 × …, jeśli na przykład 0 = 0 jest pierwsze) i mnoży wszystko razem.
Arytmetyzacja metamatematyki
Prawdziwym dobrodziejstwem jest to, że nawet twierdzenia o formułach arytmetycznych, zwane twierdzeniami metamatematycznymi, mogą same być tłumaczone na formuły z własnymi liczbami Gödla.
Pierw rozważmy formułę ~(0 = 0), oznaczającą „zero nie równa się zero”. Formuła ta jest w oczywisty sposób fałszywa. Mimo to posiada liczbę Gödla: 2 podniesione do potęgi 1 (liczba Gödla symbolu ~), pomnożone przez 3 podniesione do potęgi 8 (liczba Gödla symbolu „nawiasu otwartego”), i tak dalej, dając 2¹ × 38 × 56 × 75 × 116 × 139.
Ponieważ możemy wygenerować liczby Gödla dla wszystkich formuł, nawet fałszywych, możemy sensownie mówić o tych formułach, mówiąc o ich liczbach Gödla.
Rozważmy stwierdzenie: „Pierwszym symbolem formuły ~(0 = 0) jest tylda.” To (prawdziwe) metamatematyczne stwierdzenie o ~(0 = 0) przekłada się na stwierdzenie o liczbie Gödla tej formuły – mianowicie, że jej pierwszym wykładnikiem jest 1, liczba Gödla dla tyldy. Innymi słowy, nasze twierdzenie mówi, że 2¹ × 38 × 56 × 75 × 116 × 139 ma tylko jeden czynnik 2. Gdyby ~(0 = 0) zaczynało się od jakiegokolwiek symbolu innego niż tylda, jego liczba Gödla miałaby co najmniej dwa czynniki 2. Dokładniej więc, 2 jest czynnikiem 2¹ × 38 × 56 × 75 × 116 × 139, ale 22 nie jest czynnikiem.
Ostatnie zdanie możemy przekształcić w precyzyjną formułę arytmetyczną, którą możemy zapisać* za pomocą elementarnych symboli. Formuła ta ma oczywiście liczbę Gödla, którą możemy obliczyć, odwzorowując jej symbole na potęgi liczb pierwszych.
Przykład ten, jak piszą Nagel i Newman, „jest przykładem bardzo ogólnego i głębokiego spostrzeżenia, które leży u podstaw odkrycia Gödla: o własnościach typograficznych długich łańcuchów symboli można mówić w sposób pośredni, ale doskonale dokładny, mówiąc zamiast tego o własnościach faktoryzacji liczb pierwszych dużych liczb całkowitych.”
Konwersja na symbole jest również możliwa dla metamatematycznego stwierdzenia „Istnieje pewien ciąg formuł o liczbie Gödla x, który dowodzi formuły o liczbie Gödla k” – lub, w skrócie, „Formułę o liczbie Gödla k można udowodnić.” Zdolność do „arytmetyzacji” tego rodzaju stwierdzeń ustawiła scenę dla zamachu stanu.
G Itself
Dodatkowym spostrzeżeniem Gödla było to, że mógł on zastąpić własną liczbę Gödla formuły w samej formule, co prowadziło do niekończących się kłopotów.
Aby zobaczyć, jak działa substytucja, rozważmy formułę (∃x)(x = sy). (Brzmi ona: „Istnieje pewna zmienna x, która jest następnikiem y” lub, w skrócie, „y ma następnik”). Jak wszystkie formuły, ma ona liczbę Gödla – pewną dużą liczbę całkowitą, którą nazwiemy po prostu m.
Następnie wprowadźmy m do formuły w miejsce symbolu y. Tworzy to nową formułę, (∃x)(x = sm), co oznacza, że „m ma następnik”. Jak nazwiemy liczbę Gödla tej formuły? Są trzy informacje do przekazania: Zaczęliśmy od formuły, która ma liczbę Gödla m. Zastąpiliśmy w niej m symbolem y. A zgodnie z wprowadzonym wcześniej schematem odwzorowań, symbol y ma liczbę Gödla 17. Oznaczmy więc nową formułę liczbą Gödla sub(m, m, 17).
Zastąpienie stanowi sedno dowodu Gödla.
Rozważał on metamatematyczne stwierdzenie w rodzaju „Formuła z liczbą Gödla sub(y, y, 17) nie może być udowodniona.” Przywołując notację, której właśnie się nauczyliśmy, formuła z liczbą Gödla sub(y, y, 17) to formuła otrzymana przez wzięcie formuły z liczbą Gödla y (jakiejś nieznanej zmiennej) i podstawienie tej zmiennej y wszędzie tam, gdzie istnieje symbol, którego liczba Gödla wynosi 17 (czyli wszędzie tam, gdzie istnieje y).
Rzeczy zaczynają się robić dziwne, ale mimo to, nasze metamatematyczne stwierdzenie – „Formuła o liczbie Gödla sub(y, y, 17) nie może być udowodniona” – na pewno przekłada się na formułę o unikalnej liczbie Gödla. Nazwijmy ją n.
Teraz ostatnia runda podstawiania: Gödel tworzy nową formułę przez podstawienie liczby n wszędzie tam, gdzie w poprzedniej formule jest y. Jego nowa formuła brzmi: „Formuła z liczbą Gödla sub(n, n, 17) nie może być udowodniona.” Nazwijmy tę nową formułę G.
Naturalnie, G ma liczbę Gödla. Jaka jest jej wartość? Oto ona: musi być sub(n, n, 17). Z definicji, sub(n, n, 17) jest liczbą Gödla formuły, która wynika z wzięcia formuły z liczbą Gödla n i podstawienia n wszędzie tam, gdzie jest symbol z liczbą Gödla 17. A G jest dokładnie taką formułą! Ze względu na unikalność faktoryzacji pierwszorzędnej widzimy teraz, że formuła, o której mówi G, to nikt inny jak samo G.
G twierdzi samo przez się, że nie da się jej udowodnić.
Ale czy G da się udowodnić? Jeśli tak, to oznaczałoby to, że istnieje pewien ciąg formuł, który dowodzi formuły o liczbie Gödla sub(n, n, 17). Ale to jest przeciwieństwo G, które mówi, że taki dowód nie istnieje. Przeciwne twierdzenia, G i ~G, nie mogą być prawdziwe w spójnym systemie aksjomatycznym. Prawda G musi więc być niedekonstruowalna.
Jednakże, choć G jest niedekonstruowalne, jest wyraźnie prawdziwe. G mówi: „Formuła z liczbą Gödla sub(n, n, 17) nie może być udowodniona”, i to jest dokładnie to, co odkryliśmy, że tak jest! Ponieważ G jest prawdziwe, ale nierozstrzygalne w systemie aksjomatycznym użytym do jego skonstruowania, system ten jest niekompletny.
Można by pomyśleć, że można po prostu wprowadzić jakiś dodatkowy aksjomat, użyć go do udowodnienia G i rozwiązać paradoks. Ale nie można. Gödel pokazał, że rozszerzony system aksjomatyczny pozwoli na skonstruowanie nowej, prawdziwej formuły Gʹ (według podobnego schematu jak poprzednio), której nie da się udowodnić w ramach nowego, rozszerzonego systemu. W dążeniu do pełnego systemu matematycznego nigdy nie można złapać własnego ogona.
Brak dowodu spójności
Uczyliśmy się, że jeśli zbiór aksjomatów jest spójny, to jest niezupełny. To jest pierwsze twierdzenie niezupełności Gödla. Drugie – że żaden zbiór aksjomatów nie może dowieść własnej spójności – łatwo z niego wynika.
Co by znaczyło, gdyby zbiór aksjomatów mógł dowieść, że nigdy nie da sprzeczności? Znaczyłoby to, że istnieje ciąg formuł zbudowanych z tych aksjomatów, który dowodzi formuły oznaczającej, metamatematycznie, „Ten zbiór aksjomatów jest spójny”. Zgodnie z pierwszym twierdzeniem, ten zestaw aksjomatów byłby wtedy z konieczności niezupełny.
Ale „Zestaw aksjomatów jest niezupełny” to to samo, co powiedzenie: „Istnieje prawdziwa formuła, której nie da się udowodnić”. To stwierdzenie jest równoważne naszej formule G. A wiemy, że aksjomaty nie mogą dowieść G.
Więc Gödel stworzył dowód przez sprzeczność: Gdyby zbiór aksjomatów mógł udowodnić swoją własną spójność, wtedy moglibyśmy udowodnić G. Ale nie możemy. Dlatego żaden zbiór aksjomatów nie może udowodnić własnej spójności.
Dowód Gödla zabił poszukiwania spójnego, kompletnego systemu matematycznego. Znaczenie niezupełności „nie zostało w pełni zgłębione”, pisali Nagel i Newman w 1958 roku. Pozostaje to prawdą do dziś.
*Dla ciekawskich, stwierdzenie to brzmi: „Istnieje pewna liczba całkowita x taka, że x pomnożone przez 2 jest równe 2¹ × 38 × 56 × 75 × 116 × 139, i nie istnieje żadna liczba całkowita x taka, że x pomnożone przez 4 jest równe 2¹ × 38 × 56 × 75 × 116 × 139”. Odpowiedni wzór to:
(∃x)(x × ss0 = sss … sss0) ⋅ ~(∃x)(x × ssss0 = sss … sss0)
gdzie sss … sss0 oznacza 2¹ × 38 × 56 × 75 × 116 × 139 egzemplarzy symbolu następnika s. Symbol ⋅ oznacza „i” i jest skrótem od dłuższego wyrażenia w słowniku podstawowym: p ⋅ q oznacza ~(~p ∨ ~q).
Ten artykuł został przedrukowany w serwisie Wired.com.