Náznak důkazu věty o neúplnosti Kurta Gödela

Důkaz toho, že existuje pravdivá a nedokazatelná věta, lze nejlépe udělat nalezením této věty. Stačilo by umět zformulovat větu: „Tato věta je nedokazatelná.“ Tomu, že takovouto větu v příslušném systému axiómů zformulovat lze, se právě mj. věnuje Gödelův článek „O nerozhodnutelných větách v díle Principia Mathematica a příbuzných systémech I“. To, co tu nyní uvedu, není důkaz samotný, ale je to jen náznak důkazu. Chce-li někdo zpopularizovat důkaz věty o neúplnosti, má jednoduchou práci, protože pěkný náznak důkazu před tím, než uvedl důkaz samotný, napsal Kurt Gödel sám. Cituji tedy z jeho článku „O nerozhodnutelných větách v díle Principia Mathematica a příbuzných systémech I“ z roku 1931:

Vývoj matematiky směřující k stále větší přesnosti vedl - jak známo - k formalizaci rozsáhlých oblastí tohoto oboru tak, že v nich lze důkazy provézt pomocí několika mechanických pravidel. Nejúplnější formální systém, jenž byl doposud vytvořen, je systém popsaný v díle Principia Mathematica (PM) na jedné straně a Zermelo-Fraenkelova axiomatická teorie množin (později rozšířená J. von Neumannem) na straně druhé. Tyto dva systémy jsou vytvořeny tak, že v nich lze formalizovat všechny dnes v matematice užívané způsoby důkazů, tj. tyto mohou být sestaveny použitím pouze několika axiómů a vyvozovacích pravidel. Proto se zdá hodným víry domnění, že pomocí těchto axiómů a vyvozovacích pravidel lze úspěšně odpovědět na všechny matematické otázky vyjádřené v jazyce těchto dvou systémů. Bude však níže ukázáno, že je to omyl, a že naopak existují poměrné jednoduché problémy teorie běžných celých čísel, které nemohou být pomocí axiómů rozhodnuty. Toto přitom není důsledek zvláštní povahy jen těchto dvou výše zmíněných systémů, ale platí to pro širokou skupinu formálních systémů vzniklých přidáním konečného počtu axiómů k axiómům výše zmíněných dvou systémů a podmínky, že z přidaných axiomů nelze odvodit nepravdivé tvrzení (...).

Dříve než zajdeme do podrobností, načrtneme nejdříve bez nároku na absolutní přesnost hlavní myšlenku důkazu. Na formuli nějakého formálního systému (omezíme se zatím jen na PM) se můžeme z hlediska vnější formy dívat jako na konečné posloupnosti základních symbolů (proměnné, logické konstanty a závorky nebo oddělující znaky), a je snadné zcela přesně definovat, které posloupnosti základních symbolů jsou syntakticky správné formule a které nejsou. Podobně z formálního hlediska nejsou důkazy ničím jiným, než konečné posloupnosti formulí (ovšemže s určitými zvláštními vlastnostmi). V metamatematických úvahách je zajisté zcela lhostejné, který znak je použit pro který základní symbol a proto jako základní symboly budeme používat přirozená čísla. Formule je tím pádem konečný řetězec přirozených čísel a důkaz je konečný řetězec konečných řetězců přirozených čísel. Metamatematické zápisy (tvrzení) se tímto stávají zápisy (tvrzeními) vypovídajícími o přirozených číslech, resp. o řetězcích těchto čísel, což je činí (přinejmenším z části) vyjádřitelné v symbolech systému PM samém. Hlavně může být ukázáno, že pojmy "formule", "důkaz", "dokazatelná formule" jsou cele vyjádřitelné v systému PM, tj., že např. může být vyjádřena nějaká F(v) v PM, která má jednu volnou proměnnou v (jejímž typem je řetězec čísel), přičemž smysl F(v) lze interpretovat takto: v je dokazatelná formule. Nyní zkonstruujeme nerozhodnutelné tvrzení v systému PM, tj. tvrzení A takové, že ani A ani non-A není dokazatelné, a to následovně:

Budeme o formuli v PM s právě jednou volnou proměnnou typu odpovídajícímu celým číslům (třídám tříd) mluvit jako o příznaku třídy. Budeme předpokládat, že příznaky třídy jsou nějakým způsobem seřazeny do řetezce, značíce n-tý příznak třídy jako R(n), a poznamenejme, že pojem "příznak třídy" a relace uspořádání R jsou obě definovatelné v systému PM. Nechť α je libovolný příznak třídy; zápis [α; n] značí formuli, ve které je volná proměnná formule α nahrazena za přirozené číslo n. Trojmístná relace x = [y; z] je rovněž vyjádřitelná v PM. Nyní definujeme třídu přirozených čísel K následujícím způsobem:

(1)  K = {n ∈ N | ¬Bew [R(n); n] }

(kde Bew x značí: x je dokazatelná formule). Jelikož jsou všechny pojmy užité v této definici definovatelné v PM, lze je tudíž definovatelný i pojem K sestavený z oněch pojmů, tj. existuje příznak třídy S takový, že obsahem formule [S; n] je ta skutečnost, že přirozené číslo n náleží K. S je jakožto příznak třídy identický s nějakým určitým R(q), tj. platí

S = R(q)

pro nějaké určité přirozené číslo q. Nyní dokážeme, že tvrzení [R(q); q] je nerozhodnutelné v PM. Pokud bychom předpokládali, že tvrzení [R(q); q] je dokazatelné, pak je jistě také pravdivé, a tedy by podle (1) mělo být pravdivé i non Bew [R(q); q], což vede ke sporu s předokladem. Na druhou stranu, pokud by byla negace [R(q); q] dokazatelná, pak n nenáleží K, a tedy by platilo i Bew [R(q); q]. Z toho ale plyne, že [R(q); q] i jeho negace by byly dokazatelné, což je opět spor.

Kurt Gödel – O nerozhodnutelných větách v díle Principia Mathematica a příbuzných systémech I