Systemy dowodzenia

Są dwa, dość naturalne pytania, jakie można sobie jeszcze zadać:

1. Czy jeśli \(\Phi\models\phi\), to też \(\Phi\vdash \phi\)? Czyli ilekroć coś jest prawdą, to czy można to udowodnić. Własność taką nazywamy pełnością używanego sposobu dowodzenia.
2. Ustalmy Φ jako aksjomatykę liczb naturalnych z dodawaniem i mnożeniem. Czy wtedy, dla każdego zdania φ, zachodzi \(\Phi\models\phi\), lub \(\Phi\models\lnot\phi\)? Czyli dane zdanie zawsze albo jest prawdziwe, albo jest nieprawdziwe? Własność taką nazywamy zupełnością aksjomatyki liczb naturalnych.

Na oba pytania odpowiedzi znalazł Kurt Goedel na początku XX wieku:

1. Pierwszy wynik jest pozytywny: wiele używanych systemów dowodzenia ma pierwszą z własności. Czyli jeśli coś w ogóle jest konsekwencją semantyczną (prawdą), to można tego bezpośrednio dowieść. Dzięki temu, matematycy nie muszą rozważać klas wszystkich modeli, tylko poszukiwać dowodów. Twierdzenia tego typu nazywane są twierdzeniami o pełności.
2. Drugi wynik, to twierdzenie Goedla o niezupełności. Pokazuje ono, że musi istnieć zdanie φ dotyczące liczb naturalnych, które nie może zostać ani udowodnione, ani obalone. Korzystając z twierdzenia o pełności, można wywnioskować że muszą istnieć przynajmniej dwa różne modele liczb naturalnych N,N' i w jednym z nich φ jest prawdą, a w drugim nie.

Konsekwencja drugiego z twierdzeń jest taka, że dla niektórych zdań φ, pytanie czy to zdanie jest prawdą, nie ma ani pozytywnej, ani negatywnej odpowiedzi. Zdania takie nazywamy niezależnymi od odpowiedniej aksjomatyki.

Przykład takiego zdania, to słynna Hipoteza Continuum, zaproponowana na przełomie XIX i XX wieku przez Georga Cantora. Podaje ona pewną zależność dotyczącą liczności nieskończonych podzbiorów zbioru liczb rzeczywistych. Sam Cantor, jak też wielu innych matematyków, przez wiele lat próbowali udowodnić lub obalić tę własność. Dopiero w 1963 roku logik Paul Cohen pokazał, że hipotezy continuum nie daje się ani udowodnić, ani obalić w oparciu o aksjomaty teorii mnogości. W późniejszych latach, używając podobnych technik co Cohen, udowodniono że wiele innych hipotez matematyki ma tę własność. Wniosek z tego jest taki, że muszą istnieć różne modele aksjomatyki teorii mnogości, w niektórych z nich hipoteza continuum zachodzi, a w innych nie.

Więcej o twierdzeniu o niezupełności

Poniżej opisany jest w dużym skrócie sposób, w jaki można udowodnić twierdzenie Goedla o niezupełności. Najpierw ściślejsze sformułowanie:

Istnieje zdanie nad sygnaturą arytmetyki 0, + , * , którego nie można ani udowodnić, ani obalić w oparciu o aksjomaty liczb naturalnych.

Sposób postępowania jest taki:

1. Załóżmy, że jednak każde zdanie można albo udowodnić, albo obalić - rozumowanie przez sprzeczność.
2. Definiujemy metodę, pozwalającą kodować formuły logiki z użyciem liczb. Robimy to tak, by każdej formule odpowiadała jakaś liczba i odwrotnie, każdej liczbie odpowiadała formuła. Dzięki temu możemy napisać na przykład zdanie \(\varphi(n,a,b)\), mówiące że liczba n koduje formułę postaci \(\psi_1\wedge\psi_2\), gdzie liczba a koduje ψ₁, a liczba b koduje ψ₂.
3. Można wtedy napisać formułę P(n,m), mówiącą że liczba n koduje jakieś zdanie ψ i można udowodnić, że prawdą jest ψ(m).
4. Wtedy można stworzyć nową formułę \(R(k)\equiv\lnot P(k,k)\), czyli mówiącą że nie zachodzi P(k,k), czyli prawdziwości zdania o numerze k na k udowodnić się nie da.
5. Formuła R ma swój kod, oznaczmy ten kod \(r\in\mathbb N\)
6. Rozważmy czy można udowodnić że prawdą jest R(r)?
   1. Jeśli tak, to znaczy że nie jest prawdą P(r,r), ale to znaczy że nie można udowodnić formuły kodowanej przez r dla argumentu r. Czyli wtedy nie można udowodnić R(r). Sprzeczność, bo rozpatrujemy przypadek gdy można udowodnić R(r).
   2. Jeśli nie, to znaczy że można udowodnić \(\lnot R(r)\equiv P(r,r)\), czyli można udowodnić R(r). Znowu sprzeczność.
7. Więc R(r) nie może być ani udowodnione, ani obalone. Wbrew założeniu z punktu 1.

W powyższym rozumowaniu można dostrzec następujący schemat (używając słowa prawda w sensie istnienia dowodu):

• W punkcie 3 konstruujemy formułę P(n,m), która może mówić coś o dowodzeniu formuł - czyli między innymi sama o sobie. Mówi ona ,formuła kodowana przez n jest prawdą na m'.
• W punkcie 4 konstruujemy formułę R(k) mówiącą ,formuła kodowana przez k nie jest prawdą na k'.
• W punkcie 5 rozpatrujemy R(r), czyli zdanie mówiące ,jestem zdaniem nieprawdziwym'.
• Otrzymujemy klasyczny paradoks kłamcy - zdanie mówiące ,jestem fałszem' nie może być ani prawdą, ani fałszem.