Twierdzenia Gödla o niezupełności

Twierdzenia Gödla (1931)

I twierdzenie. W każdym niesprzecznym systemie formalnym, który jest efektywnie aksjomatyzowalny i zawiera arytmetykę liczb naturalnych, istnieje zdanie prawdziwe, ale niedowodliwe w tym systemie.

II twierdzenie. Taki system nie może udowodnić własnej niesprzeczności.

Co dokładnie mówią te twierdzenia

Zacznijmy od słownika, bo w tym twierdzeniu każde słowo jest istotne.

System formalny to zestaw aksjomatów i reguł wnioskowania - maszyna do produkowania dowodów. Zdanie jest dowodliwe, jeśli da się je z aksjomatów wyprowadzić skończonym ciągiem poprawnych kroków.

Do 1931 roku matematycy - z Davidem Hilbertem na czele - liczyli, że da się zbudować system, w którym każde prawdziwe zdanie arytmetyki będzie dowodliwe, a przy okazji da się udowodnić, że system nie prowadzi do sprzeczności. To był słynny program Hilberta.

Gödel pokazał, że taki system nie istnieje. Zawsze pozostaną zdania prawdziwe, których system nie udowodni - i dołożenie ich jako nowych aksjomatów nic nie da, bo w powiększonym systemie natychmiast pojawi się kolejne takie zdanie.

Założenia - i dlaczego każde jest konieczne

Twierdzenie nie dotyczy „każdej teorii”. System musi spełniać trzy warunki:

niesprzeczność - nie dowodzi jednocześnie zdania i jego zaprzeczenia (system sprzeczny dowodzi wszystkiego, więc jest zupełny, ale bezużyteczny);
efektywna aksjomatyzowalność - istnieje algorytm rozstrzygający, co jest aksjomatem. Gdyby aksjomatami były po prostu „wszystkie zdania prawdziwe”, system byłby zupełny - ale nie dałoby się go używać;
wystarczająca siła - system musi umieć wyrazić arytmetykę liczb naturalnych (dodawanie i mnożenie).

Ostatnie założenie jest zaskakująco istotne. Istnieją teorie zupełne i rozstrzygalne: arytmetyka Presburgera (liczby naturalne z samym dodawaniem, bez mnożenia) oraz geometria elementarna w ujęciu Tarskiego. Granicę przekracza dopiero dodanie mnożenia.

Dowód - szkic

Pokaż dowódUkryj dowód

Pełny dowód to kilkadziesiąt stron rachunków; jego pomysł da się jednak streścić w czterech krokach.

Krok 1. Numeracja Gödla - matematyka mówi o sobie. Każdemu symbolowi, zdaniu i całemu dowodowi przypisujemy liczbę naturalną (np. przez rozkład na czynniki pierwsze: $2^{k_1} \cdot 3^{k_2} \cdot 5^{k_3} \cdot \ldots$ ). Dzięki temu zdania o dowodach stają się zdaniami o liczbach - a o liczbach nasz system potrafi mówić z założenia.

Krok 2. Relacja dowodliwości jest arytmetyczna. Gödel pokazał, że da się napisać formułę arytmetyczną $\mathrm{Dow}(x, y)$ , prawdziwą dokładnie wtedy, gdy $x$ jest numerem dowodu zdania o numerze $y$ . Sprawdzenie poprawności dowodu jest mechaniczne, więc daje się zapisać rachunkiem na liczbach.

Krok 3. Zdanie samozwrotne. Za pomocą przekątniowej sztuczki (tej samej co u Cantora) buduje się zdanie $G$ , które mówi o sobie:

$G \equiv \text{„nie istnieje dowód zdania o numerze } \ulcorner G \urcorner \text{"}.$

Czyli: „nie jestem dowodliwe”.

Krok 4. Analiza obu możliwości.

Gdyby $G$ było dowodliwe, to system dowodziłby zdania, które twierdzi, że dowodu nie ma - a jednocześnie umiałby ten dowód wskazać. System dowodziłby więc zdania i jego zaprzeczenia, czyli byłby sprzeczny.
Skoro system jest niesprzeczny, $G$ nie jest dowodliwe. Ale to dokładnie to, co $G$ mówi - a więc $G$ jest prawdziwe.

Mamy zdanie prawdziwe i niedowodliwe. $\blacksquare$

Skąd bierze się drugie twierdzenie. Powyższe rozumowanie („jeśli system jest niesprzeczny, to $G$ jest niedowodliwe”) samo daje się zapisać w systemie. Gdyby system potrafił udowodnić własną niesprzeczność, mógłby stąd wyprowadzić $G$ - a przecież $G$ jest niedowodliwe. Zatem dowodu własnej niesprzeczności nie ma.

Czego te twierdzenia NIE mówią

Trudno o twierdzenie częściej nadużywane. Warto więc jasno:

Nie mówią, że „nic nie da się udowodnić”. Przytłaczająca większość twierdzeń matematyki ma się świetnie; Gödel mówi o istnieniu wyjątków, nie o regule.
Nie mówią, że matematyka jest sprzeczna. Wręcz przeciwnie - drugie twierdzenie zakłada niesprzeczność i dotyczy tylko tego, że system nie może jej sam udowodnić.
Nie mówią, że prawda jest względna. Zdanie $G$ jest prawdziwe - to nie kwestia opinii, lecz wniosek z dowodu.
Nie dowodzą, że umysł ludzki przewyższa komputer. Taka interpretacja (Lucas, Penrose) jest filozoficzną hipotezą, a nie treścią twierdzenia - człowiek również nie wie, czy jego własne „aksjomaty” są niesprzeczne.
Nie stosują się do dowolnych systemów. Poza matematyką - w prawie, ekonomii, teologii - nie ma numeracji Gödla ani formalnych dowodów, więc cytowanie tych twierdzeń jest tam zwykłą metaforą.

Konkretne przykłady zdań niedowodliwych

Zdanie $G$ jest sztuczne. Znamy jednak naturalne twierdzenia matematyczne, które są niedowodliwe w standardowej arytmetyce:

twierdzenie Goodsteina o ciągach liczb naturalnych - prawdziwe, ale niedowodliwe w arytmetyce Peana (Kirby i Paris, 1982);
wzmocnione twierdzenie Ramseya z tego samego artykułu;
hipoteza continuum - niezależna od aksjomatów teorii mnogości (Gödel 1940, Cohen 1963).

Podobny los spotkał informatykę: problem stopu (czy dany program się zatrzyma) jest nierozstrzygalny - Alan Turing udowodnił to w 1936 roku metodą bardzo bliską argumentowi Gödla.

Kto i kiedy

Kurt Gödel ogłosił oba twierdzenia w 1931 roku, mając $25$ lat; był wtedy członkiem Koła Wiedeńskiego. Wynik zakończył program Hilberta w jego pierwotnej postaci i uchodzi za najważniejsze twierdzenie logiki XX wieku.

Gödel wyemigrował w 1940 roku do Princeton, gdzie przyjaźnił się z Albertem Einsteinem. Anegdota z jego egzaminu na obywatelstwo USA mówi, że znalazł w konstytucji lukę logiczną pozwalającą legalnie ustanowić dyktaturę - Einstein z trudem powstrzymał go przed wykładaniem tego komisji.

Najczęstsze pytania

Czy twierdzenie Gödla oznacza, że matematyka jest niepełna i zawodna? Nie. Oznacza, że żaden pojedynczy system formalny nie wyczerpie całej prawdy arytmetycznej. Matematyka działa dalej - po prostu nie jest sprowadzalna do jednej mechanicznej procedury.

Czy da się „naprawić” system, dokładając zdanie $G$ jako aksjomat? Można, ale nic to nie da. Powiększony system znowu spełnia założenia twierdzenia, więc pojawia się w nim nowe zdanie prawdziwe i niedowodliwe - i tak w nieskończoność.

Co to znaczy, że zdanie jest „prawdziwe, ale niedowodliwe”? Prawdziwe w standardowym modelu liczb naturalnych, czyli w tym, co rozumiemy przez zwykłe liczby. Niedowodliwe - bo nie da się go wyprowadzić z aksjomatów danego systemu.

Jaki jest związek z problemem stopu Turinga? Bardzo bliski. Oba dowody używają samoodniesienia i przekątniowania; nierozstrzygalność problemu stopu pociąga za sobą niezupełność arytmetyki.

Czy istnieją systemy, do których twierdzenie się nie stosuje? Tak - te za słabe, by wyrazić mnożenie liczb naturalnych. Arytmetyka Presburgera i geometria elementarna Tarskiego są zupełne i rozstrzygalne.

Podsumowanie

I twierdzenie: w każdym niesprzecznym, efektywnie aksjomatyzowalnym systemie zawierającym arytmetykę istnieje zdanie prawdziwe, ale niedowodliwe.
II twierdzenie: taki system nie udowodni własnej niesprzeczności.
Dowód opiera się na numeracji Gödla (zdania o dowodach stają się zdaniami o liczbach) i zdaniu samozwrotnym „nie jestem dowodliwe”.
Twierdzenia nie oznaczają, że matematyka jest sprzeczna, że prawda jest względna ani że umysł przewyższa maszynę - to najczęstsze nadużycia.
Naturalne przykłady zdań niedowodliwych: twierdzenie Goodsteina, hipoteza continuum; informatyczny odpowiednik to nierozstrzygalny problem stopu.