Gödelovy věty o neúplnosti

V matematické logice jsou Gödelovy věty o neúplnosti dvě slavné věty, které v roce 1931 dokázal Kurt Gödel.

První věta o neúplnosti

Gödelova první věta o neúplnosti je asi nejslavnějším výsledkem v matematické logice. V podstatě říká, že:

„Teorie“ zde odkazuje na množinu tvrzení. (Teorie je obecně nekonečně velká množina.) Teorie je „konzistentní“, pokud neprokazuje žádné rozpory. Význam „je možné konstruovat“ je ten, že existuje nějaký mechanický postup, který při daném axiomu teorie vytváří další tvrzení. To, že toto tvrzení není v teorii prokazatelné, znamená, že nemůže být odvozeno z tvrzení teorie za použití standardních pravidel logiky prvního řádu. Tvrzení vytvořené postupem je pro tuto teorii často označováno jako „Gödelova věta“, i když ve skutečnosti existuje nekonečně mnoho tvrzení, která mají stejnou vlastnost (že jsou pravdivá, ale nejsou z teorie prokazatelná).

(Některé technické hypotézy zde byly vynechány; tou nejdůležitější je ustanovení, že teorie je výpočetně vyčíslitelná. To znamená, že aby byla Gödelova věta použitelná, musí být v zásadě možné napsat počítačový program, který, pokud by dovolil běžet věčně, by vytiskl všechny axiomy teorie a nic jiného.)

Zhruba lze vyjádřit Gödelův výrok G: „G nemůže být prokázána pravda“. Pokud by G byla prokázána pravda podle axiomů teorie, pak by teorie měla větu G, která by si protiřečila. Podobný rozpor by nastal, pokud by G mohla být prokázána nepravda. Jsme tedy nuceni dojít k závěru, že G nemůže být prokázána pravda nebo nepravda, ale je pravdivá právě kvůli tomuto faktu. Q.E.D.

Předložená ukázka je v běžné angličtině, a není tedy matematicky přesná. Pro dobře definovanou ukázku představuje Gödel výroky pomocí čísel; pak se teorie, která je již o číslech, také týká výroků, včetně svých vlastních. Otázky týkající se prokazatelnosti výroků jsou reprezentovány jako matematicky definovatelné otázky týkající se vlastností čísel, které by byly rozhodnutelné podle teorie, pokud by byla úplná. V těchto pojmech je Gödelova věta tvrzením, že neexistuje přirozené číslo s určitou vlastností. Číslo s touto vlastností by bylo důkazem nekonzistence teorie. Pokud by takové číslo existovalo, pak by teorie byla nekonzistentní, v rozporu s hypotézou. Takže takové číslo neexistuje a Gödelův výrok je pravdivý, ale teorie to nemůže dokázat.

Gödel prokázala neúplnost teorie aritmetika, ale je jasné, že demonstrace by mohla být uvedena pro každou teorii a jazyk na určitou expresivitu.

Gödel původně prokázal slabší větu, než je uvedeno výše. V větě prokázané Gödelem je předpoklad, že teorie je (nejen konzistentní, ale) omega-konzistentní. Omega-konzistence je technický pojem, který se vztahuje na teorii T, pokud pro žádný majetek P, T prokáže, že každé konkrétní přirozené číslo postrádá P, přesto T prokáže, že existuje nějaké přirozené číslo s P. Všimněte si, že omega-konzistence znamená konzistenci, ale konzistence neznamená omega-konzistenci. J. Barkley Rosser později posílil větu odstraněním požadavku, aby teorie byla omega-konzistentní. To je většinou technický zájem, protože všechny pravdivé formální teorie aritmetiky, tj. teorie, jejichž axiomy jsou pravdivá tvrzení o přirozených číslech, jsou omega-konzistentní a tudíž se na ně vztahuje původní Gödelova věta.

Druhá věta o neúplnosti

Gödelova druhá věta o neúplnosti může být uvedeno takto:

Je-li T nekonzistentní, pak lze dokázat cokoliv, včetně toho, že T je konzistentní.
(Důkaz části „pouze pokud“:) Je-li T konzistentní, pak T nezahrnuje tvrzení o své vlastní konzistenci. To vyplývá z první věty.

Existuje mnoho způsobů, jak to udělat, a ne všechny vedou ke stejnému výsledku. Zejména různé formalizace tvrzení, že T je konzistentní, mohou být v T neequivalentní, a některé mohou být dokonce prokazatelné. Například aritmetika prvního řádu (Peanova aritmetika nebo zkráceně PA) může dokázat, že největší konzistentní podmnožina PA je konzistentní. Ale protože PA je konzistentní, největší konzistentní podmnožina PA je právě PA, takže v tomto smyslu PA „dokazuje, že je konzistentní“. Co PA nedokazuje, je, že největší konzistentní podmnožina PA je ve skutečnosti celá PA. (Termín „největší konzistentní podmnožina PA“ je dosti vágní, ale to, co je zde míněno, je největší konzistentní počáteční segment axiomů PA uspořádaný podle některých kritérií, např. podle „Gödelových čísel“, čísel kódujících axiomy podle schématu používaného Gödelem zmíněným výše).

V případě Peanovy aritmetiky nebo jakékoli známé explicitně axiomatizované teorie T je možné definovat konzistenci „Con(T)“ T z hlediska neexistence čísla s určitou vlastností následovně: „neexistuje celé číslo kódující posloupnost vět, takže každá věta je buď jedním z (kanonických) axiomů T, logickým axiomem, nebo bezprostředním důsledkem předcházejících vět podle pravidel odvození logiky prvního řádu, a to tak, že poslední věta je rozpor“. Nicméně pro libovolné T neexistuje žádná kanonická volba pro Con(T).

Formalizace Con(T) závisí na dvou faktorech: formalizaci pojmu věta je odvozitelná z množiny vět a formalizaci pojmu být axiomem T. Formalizaci derivovatelnosti lze provést kanonicky, takže vzhledem k aritmetickému vzorci A(x) definujícímu množinu axiomů můžeme kanonicky vytvořit predikát ProvA(P), který vyjadřuje, že P je prokazatelné ze množiny axiomů definovaných A(x). Pomocí tohoto predikátu můžeme vyjádřit Con(T) jako „ne ProvA(‚P a ne-P‘)“. Solomon Feferman ukázal, že Gödelova druhá věta o neúplnosti prochází, když je vzorec A(x) zvolen tak, že má tvar „existuje číslo n splňující rozhodnitelný predikát P“ pro nějaké P. Kromě toho ProvA(P) musí splňovat tzv. Hilbertovy-Bernaysovy podmínky prokazatelnosti:

1. Pokud T dokazuje P, pak T dokazuje ProvA(P)

2. T dokazuje 1., tj. T dokazuje, že pokud T dokazuje P, pak T dokazuje ProvA(P)

3. T dokazuje, že pokud T dokazuje, že (P znamená Q), pak T dokazuje, že prokazatelnost P znamená prokazatelnost Q

Gödelova druhá věta o neúplnosti také znamená, že teorie T1 splňující výše uvedené technické podmínky nemůže dokázat konzistenci žádné teorie T2, která dokazuje konzistenci T1. Je to proto, že pak T1 může dokázat, že pokud T2 dokazuje konzistenci T1, pak je T1 ve skutečnosti konzistentní. Tvrzení, že T1 je konzistentní, má totiž formu „pro všechna čísla n, n má rozhodující vlastnost, že není kódem pro důkaz rozpornosti v T1“. Pokud by T1 byla ve skutečnosti nekonzistentní, pak by T2 dokázalo pro některé n, že n je kódem rozpornosti v T1. Ale pokud by T2 také dokázalo, že T1 je konzistentní, tj. žádné takové n neexistuje, bylo by to samo nekonzistentní. Tuto úvahu můžeme provést v T1 a dojít k závěru, že pokud je T2 konzistentní, pak je T1 konzistentní. Protože druhou větou o neúplnosti T1 neprokazuje svou konzistenci, nemůže dokázat ani konzistenci T2.

Tento snadný důsledek druhé věty o neúplnosti ukazuje, že není žádná naděje na prokázání např. konzistence aritmetiky prvního řádu pomocí finitistických prostředků za předpokladu, že uznáme, že finitistické prostředky jsou správně formalizovány v teorii, jejíž konzistence je prokazatelná v PA. Všeobecně se uznává, že teorie primitivní rekurzivní aritmetiky (PRA) je přesnou formalizací finitistické matematiky a PRA je prokazatelně konzistentní v PA. Tudíž PRA nemůže prokázat konzistenci PA. Obecně se má za to, že Hilbertův program validace použití „ideálních“ matematických principů k prokázání „reálných“ (finitistických) matematických výroků prokázáním, že „ideální“ principy jsou konzistentní pomocí finitisticky přijatelných principů, nemůže být proveden.

Tento důsledek je vlastně tím, co činí druhou větu o neúplnosti epistemologicky relevantní. Jak poznamenal Georg Kreisel, ve skutečnosti by neposkytovala žádnou zajímavou informaci, pokud by teorie T prokázala svou konzistenci. Je to proto, že nekonzistentní teorie dokazují vše, včetně jejich konzistence. Důkaz konzistence T v T by nám tedy neposkytl žádné vodítko k tomu, zda je T skutečně konzistentní; žádné pochybnosti o konzistenci T by byly vyřešeny takovým důkazem konzistence. Zájem o důkazy konzistence spočívá v možnosti prokázat konzistenci teorie T v nějaké teorii T‘, která je v jistém smyslu méně pochybná než samotný T, např. slabší než T. Pro většinu přirozeně se vyskytujících T a T‘, jako je T = Zermelo-Fraenkelova teorie množin a T‘ = primitivní rekurzivní aritmetika, je konzistence T‘ prokazatelná v T, a tudíž T‘ nemůže prokázat konzistenci T výše uvedeným důsledkem druhé věty o neúplnosti.

Konzistence aritmetiky prvního řádu byla prokázána za předpokladu, že určitá ordinála nazývaná ε0 je dobře založena. Viz Gentzenův důkaz konzistence.

Význam Gödelových vět

Gödelovy věty jsou věty v logice prvního řádu a musí být nakonec chápány v tomto kontextu. Ve formální logice jsou matematická tvrzení i důkazy psány v symbolickém jazyce, kde můžeme mechanicky ověřit platnost důkazů, aby nemohlo být pochyb, že věta vyplývá z našeho výchozího seznamu axiomů. Teoreticky může být takový důkaz ověřen počítačem a ve skutečnosti existují počítačové programy, které ověří platnost důkazů. (Automatické ověřování důkazů úzce souvisí s automatickým dokazováním vět, i když dokazování a kontrola důkazů jsou obvykle odlišné úkoly.)

Abychom mohli tento proces provést, musíme vědět, jaké jsou naše axiomy. Mohli bychom začít s konečnou množinou axiomů, například v euklidovské geometrii, nebo obecněji bychom mohli povolit nekonečný seznam axiomů s požadavkem, že můžeme mechanicky ověřit, zda se jedná o axiom z dané množiny, nebo ne (axiomové schéma). V informatice se tomu říká rekurzivní množina axiomů. I když nekonečný seznam axiomů může znít divně, je to přesně to, co se používá v obvyklých axiomech pro přirozená čísla, Peanův axiom: induktivní axiom je ve skutečnosti axiomové schéma – uvádí, že pokud nula má nějakou vlastnost a kdykoli nějaké přirozené číslo má tuto vlastnost, její nástupce má také tuto vlastnost, pak všechna přirozená čísla mají tuto vlastnost – nespecifikuje, která vlastnost a jediný způsob, jak v logice prvního řádu říci, že to platí pro všechny vlastnosti, je mít nekonečný počet příkazů.

Gödelova první věta o neúplnosti ukazuje, že každý takový systém, který umožňuje definovat přirozená čísla, je nutně neúplný: obsahuje tvrzení, která nejsou prokazatelně pravdivá ani prokazatelně nepravdivá.

Existence neúplného systému není sama o sobě nijak překvapivá. Například vezmete-li euklidovskou geometrii a upustíte od paralelního postulátu, dostanete neúplný systém (v tom smyslu, že systém neobsahuje všechna pravdivá tvrzení o euklidovském prostoru). Systém může být neúplný jednoduše proto, že jste neobjevili všechny potřebné axiomy.

Gödel ukázal, že ve většině případů, například v teorii čísel nebo reálné analýze, nikdy nemůžete vytvořit úplný a konzistentní konečný seznam axiomů, nebo dokonce nekonečný seznam, který může být vytvořen počítačovým programem. Pokaždé, když přidáte výrok jako axiom, vždy se objeví další pravdivé výroky, které stále nemohou být prokázány jako pravdivé, dokonce ani s novým axiomem. Navíc, pokud systém může dokázat, že je konzistentní, pak je nekonzistentní.

Je možné mít úplný a konzistentní seznam axiomů, které nemohou být vytvořeny počítačovým programem (to znamená, že seznam není výpočetně vyčíslitelný). Například by se daly všechny pravdivé výroky o přirozených číslech považovat za axiomy (a žádné nepravdivé výroky). Ale pak neexistuje žádný mechanický způsob, jak rozhodnout, vzhledem k výroku o přirozených číslech, zda je to axiom nebo ne.

Gödelova věta má další výklad v jazyce počítačové vědy. V logice prvního řádu jsou věty vypočitatelné: můžete napsat počítačový program, který nakonec vygeneruje jakýkoliv platný důkaz. Můžete se zeptat, zda mají silnější vlastnost rekurzivity: můžete napsat počítačový program, který definitivně určí, zda je výrok pravdivý nebo nepravdivý? Gödelova věta říká, že obecně to nejde.

Mnozí logici se domnívají, že Gödelovy věty o neúplnosti zasadily smrtelnou ránu programu Davida Hilberta směřujícímu k univerzálnímu matematickému formalismu, který byl založen na Principia Mathematica. Všeobecně se shodneme na postoji, že druhá věta je to, co konkrétně tuto ránu zasadilo. Nicméně někteří se domnívají, že to byla první, a jiní se domnívají, že ani jedna.

Příklady nerozhodnutelných výroků

Je třeba poznamenat, že existují dva odlišné smysly slova „nerozhodnutelný“ v použití. První z nich je smysl používaný ve vztahu ke Gödelovým větám, tj. že tvrzení není ani prokazatelné, ani vyvratitelné, v nějakém specifikovaném deduktivním systému. Druhý smysl se používá ve vztahu k teorii rekurze a nevztahuje se na tvrzení, ale na rozhodovací problémy, což jsou nespočetně nekonečné množiny otázek, z nichž každá vyžaduje odpověď ano/ne. Takový problém je prý nerozhodnutelný, pokud neexistuje rekurzivní funkce, která by správně zodpověděla každou otázku v množině problémů. Spojení mezi těmito dvěma je, že pokud je rozhodovací problém nerozhodnutelný (v rekurzivním teoretickém smyslu), pak neexistuje konzistentní formální systém, který by dokazoval pro každou otázku A v problému buď „odpověď na otázku A je ano“, nebo „odpověď na otázku A je ne“.

(Z tohoto důvodu se často dává přednost výrazu „nezávislý“ před výrazem „nerozhodnutelný“, pro smysl „ani prokazatelný, ani vyvratitelný“. Nicméně „nezávislý“ je také nejednoznačný; někteří ho používají tak, že znamená jen „neprokazatelný“, a nechávají otevřené, zda by nezávislé tvrzení mohlo být vyvráceno.)

Je třeba poznamenat, že nerozhodnutelnost výroku v konkrétním deduktivním systému neřeší
sama o sobě otázku, zda je pravdivostní hodnota výroku dobře definována, nebo zda ji lze znát. Říká pouze, že konkrétní uvažovaný deduktivní systém o této otázce nerozhoduje. Zda existují takzvané „absolutně nerozhodnutelné“ výroky, jejichž pravdivostní hodnota nemůže být nikdy známa nebo je špatně specifikována, je kontroverzním bodem mezi různými filozofickými školami.

Následná kombinovaná práce Gödela a Paula Cohena dala konkrétní příklady nerozhodnutelných tvrzení (tvrzení, která v nějakém specifikovaném deduktivním systému nemohou být ani prokázána, ani vyvrácena): Hypotéza kontinua nemůže být ani prokázána, ani vyvrácena v ZFC (standardní axiomatizace teorie množin) a axiom volby nemůže být ani prokázán, ani vyvrácen v ZF (což jsou všechny axiomy ZFC kromě axiomu volby). Tyto výsledky nevyžadují větu o neúplnosti.

V roce 1936 Alan Turing dokázal, že problém haltingu – otázka, zda Turingův stroj zastaví na daném programu či nikoliv – je nerozhodnutelný, v druhém smyslu tohoto pojmu. Tento výsledek byl později zobecněn v oblasti rekurzivních funkcí na Riceovu větu, která ukazuje, že všechny netriviální vlastnosti rekurzivních funkcí jsou nerozhodnutelné, tj. neexistuje rekurzivní funkce, která vrací 1, když je dán popis rekurzivní funkce mající tuto vlastnost a vrací 0 jinak. V tomto kontextu netriviální vlastnost je taková, která platí pro některé, ale ne pro všechny rekurzivní funkce.

V roce 1973 se ukázalo, že Whiteheadův problém v teorii grup je nerozhodnutelný v prvním smyslu termínu ve standardní teorii množin.
V roce 1977 Paris a Harrington dokázali, že Paris-Harringtonův princip, verze Ramseyho věty, je nerozhodnutelný v axiomatizaci aritmetiky dané Peanovými axiomy, ale může být prokázáno, že je pravdivý ve větším systému aritmetiky druhého řádu.
Kruskalova věta o stromech, která má uplatnění v informatice, je také nerozhodnutelná z Peanových axiomů, ale prokazatelná v teorii množin. Ve skutečnosti je Kruskalova věta o stromech (nebo její konečná podoba) nerozhodnutelná v mnohem silnějším systému kodifikujícím principy přijatelné na základě filozofie matematiky zvané predikativismus.
Goodsteinova věta je relativně jednoduché tvrzení o přirozených číslech, které Kirby a Paris ukázali jako nerozhodnutelné v Peanově aritmetice.

Gregory Chaitin produkoval nerozhodnutelné výroky v algoritmické teorii informace a ve skutečnosti prokázal svou vlastní větu o neúplnosti v tomto nastavení.

Jedním z prvních problémů podezřelých být nerozhodnutelný, ve druhém smyslu tohoto pojmu, byl slovní problém pro skupiny, první představuje Max Dehn v roce 1911, který se ptá, zda existuje konečně představil skupiny, pro které neexistuje algoritmus určit, zda dvě slova jsou rovnocenné. To bylo prokázáno, že případ v roce 1952.

Mylné představy o Gödelových větách

Vzhledem k tomu, že Gödelova první věta o neúplnosti je tak slavná, dala vzniknout mnoha mylným představám. Jsou zde vyvráceny:

Diskuse a důsledky

Výsledky neúplnosti ovlivňují filozofii matematiky, zejména hlediska jako formalismus, který k definování svých principů používá formální logiku.
První větu lze parafrázovat slovy, že „nikdy nemůžeme najít všeobjímající axiomatický systém, který je schopen dokázat všechny matematické pravdy, ale žádné nepravdy“.

Na druhou stranu, z přísně formalistického pohledu by tato parafráze byla považována za nesmyslnou, protože předpokládá, že matematická „pravda“ a „lež“ jsou dobře definovány v absolutním smyslu, spíše než ve vztahu ke každému formálnímu systému.

Proto, aby bylo možné stanovit konzistenci systému S, je třeba použít nějaký jiný výkonnější systém T, ale důkaz v T není zcela přesvědčivý, pokud T konzistence již byla stanovena bez použití S.

Konzistence Peanových axiomů pro přirozená čísla může být například prokázána v teorii množin, ale ne pouze v teorii přirozených čísel.
To poskytuje negativní odpověď na problém číslo 2 na slavném seznamu důležitých otevřených otázek v matematice Davida Hilberta (tzv. Hilbertovy problémy).

Gödelovy věty v zásadě stále ponechávají jistou naději: mohlo by být možné vytvořit obecný algoritmus, který pro dané tvrzení určuje, zda je nerozhodnutelné, či nikoli, a tak by matematici mohli nerozhodnutelná tvrzení úplně obejít. Záporná odpověď na Entscheidungsproblem však ukazuje, že žádný takový algoritmus neexistuje.

Jsou tací, kteří zastávají názor, že tvrzení, které je v rámci deduktivního systému neprokazatelné, může být v metalanguage zcela prokazatelné. A co nelze v této metalanguage prokázat, může být v zásadě prokázáno v meta-metalanguage, rekurzivně, ad infinitum. Odvoláním se na jakousi superteorii typů s axiomem redukovatelnosti – která induktivním předpokladem platí pro celou zásobu jazyků – lze pro všechny praktické účely překonat překážku neúplnosti.

Všimněte si, že Gödelovy věty platí pouze pro dostatečně silné
axiomatické systémy. „Dostatečně silné“ znamená, že teorie obsahuje dostatek aritmetiky k provedení kódovacích konstrukcí potřebných pro důkaz první věty o neúplnosti. V podstatě vše, co je požadováno, jsou některá základní fakta o sčítání a násobení, jak je formalizováno, např. v Robinsonově aritmetice Q.
Existují ještě slabší axiomatické systémy, které jsou konzistentní a úplné, například Presburgerova aritmetika, která dokazuje každé pravdivé tvrzení prvního řádu zahrnující pouze sčítání.

Axiomatický systém se může skládat z nekonečně mnoha axiomů (jak to dělá Peanova aritmetika prvního řádu), ale aby se Gödelova věta uplatnila, musí existovat účinný algoritmus, který je schopen kontrolovat korektnost důkazů. Například by se dala vzít množina všech vět prvního řádu, které jsou pravdivé ve standardním modelu přirozených čísel. Tento systém je úplný; Gödelova věta se neuplatní, protože neexistuje účinný postup, který by rozhodoval, zda je daná věta axiomem. Ve skutečnosti je to důsledek Gödelovy první věty o neúplnosti.

Jiný příklad specifikace teorie, na kterou se Gödelova první věta nevztahuje, lze zkonstruovat následovně: seřaďte všechny možné výroky o přirozených číslech nejprve podle délky a poté lexikograficky, začněte axiomatickým systémem, který se zpočátku rovná Peanovým axiomům, projděte si seznam výroků jeden po druhém, a pokud současný výrok nelze prokázat ani vyvrátit ze současného axiomového systému, přidejte ho do tohoto systému.
Tím vznikne systém, který je úplný, konzistentní a dostatečně výkonný, ale není výpočetně vyčíslitelný.

Gödel sám prokázal pouze technicky mírně slabší verzi výše uvedených vět; první důkaz pro výše uvedené verze byl uveden J. Barkley Rosser v roce 1936.

V podstatě, důkaz o první věta spočívá v konstrukci prohlášení p v rámci formálního axiomatický systém, který může být uveden meta-matematický výklad:

Jako takový může být považován za moderní variantu Lhářského paradoxu, i když na rozdíl od klasických paradoxů ve skutečnosti paradoxní není.

Pokud je axiomatický systém (omega-)konzistentní, Gödelův důkaz ukazuje, že p (a jeho negace) nelze v systému prokázat.
Proto p je pravdivé (p tvrdí, že není prokazatelné, a není prokazatelné), přesto nemůže být v systému formálně prokázáno.
Všimněte si, že přidáním p k axiomům systému by se problém nevyřešil: pro rozšířenou teorii by existovala další Gödelova věta.

Mnoho učenců debatovalo o tom, co Gödelova věta o neúplnosti implikuje o lidské inteligenci. Velká část debat se soustředí na to, zda je lidská mysl rovnocenná Turingovu stroji, nebo podle Church-Turingovy teze jakémukoli konečnému stroji vůbec. Pokud je, a pokud je stroj konzistentní, pak by se na něj vztahovaly Gödelovy věty o neúplnosti.

Jeden z prvních pokusů použít neúplnost k rozumu o lidské inteligenci byl samotným Gödelem v jeho Gibbsově přednášce z roku 1951 nazvané „Některé základní věty o základech matematiky a jejich filozofických důsledcích“. V této přednášce Gödel používá větu o neúplnosti, aby dospěl k následujícímu rozuzlení: (a) lidská mysl není konzistentní konečný stroj, nebo (b) existují Diophantinovy rovnice, pro které nemůže rozhodnout, zda existují řešení. Gödel shledává (b) nevěrohodným, a tak se zdá, že věřil, že lidská mysl není rovnocenná konečnému stroji, tj. její síla převyšuje sílu jakéhokoli konečného stroje. Nicméně si uvědomil, že to byla pouze domněnka, protože nemohl vyvrátit (b).

V následujících letech se v intelektuální atmosféře zřejmě vznášely přímější anti-mechanistické linie uvažování. V roce 1960 Hilary Putnam publikoval práci s názvem „Myšlenky a stroje“, ve které poukazuje na nedostatky typického anti-mechanistického argumentu. Neformálně se jedná o argument, že (údajný) rozdíl mezi „tím, co lze mechanicky dokázat“ a „tím, co lze lidmi považovat za pravdivé“ ukazuje, že lidská inteligence není mechanické povahy. Nebo, jak to Putnam formuloval:

Nechť T je Turingův stroj, který mě „reprezentuje“ v tom smyslu, že T může dokázat právě matematická tvrzení, která dokazuji. Pak pomocí Gödelovy techniky mohu objevit tvrzení, které T nemůže dokázat, a navíc mohu dokázat toto tvrzení. To vyvrací předpoklad, že T mě „reprezentuje“, tudíž nejsem Turingův stroj.

Putnam namítá, že tento argument ignoruje otázku konzistence. Gödelovu techniku lze aplikovat pouze na konzistentní systémy. Je možné, argumentuje Putnam, že lidská mysl je nekonzistentní. Má-li někdo použít Gödelovu techniku, aby dokázal, že tvrzení, že T nelze dokázat, musí nejprve dokázat (matematické tvrzení představující) konzistenci T, což je nelehký a možná nemožný úkol. Není tedy nutné, aby byl člověk schopen dokázat něco, co T nemůže.

Lucas v knize Myšlenky, stroje a Gödel (1963) a později ve své knize Svoboda vůle (1970) předkládá protimechanistický argument, který úzce navazuje na ten, který popsal Putnam, včetně důvodů, proč lze lidskou mysl považovat za konzistentní. Lucas připouští, že Gödelovou druhou větou nemůže lidská mysl formálně dokázat svou vlastní konzistenci, a dokonce říká (možná žertem), že ženy a politici jsou nekonzistentní. Nicméně předkládá argumenty, proč lze mužskou nepolitickou mysl považovat za konzistentní. Tyto argumenty jsou filozofické povahy a jsou předmětem mnoha debat; Lucas poskytuje odkazy na odpovědi na svých vlastních webových stránkách.

Další významnou práci odvedl Judson Webb ve své práci z roku 1968 „Metamathematics and the Philosophy of Mind“. Webb tvrdí, že předchozí pokusy glosovaly, zda lze skutečně vidět, že Gödelův výrok p vztahující se k sobě samému je pravdivý. Použitím jiné formulace Gödelových vět, totiž vět Raymonda Smullyana a Emila Posta, Webb ukazuje, že lze pro sebe odvodit přesvědčivé argumenty jak o pravdě, tak o nepravdivosti p. Dále tvrdí, že všechny argumenty o filozofických důsledcích Gödelových vět jsou ve skutečnosti argumenty o tom, zda je pravdivá Church-Turingova teze.

Později do boje vstoupil Roger Penrose, který ve svých knihách The Emperor’s New Mind (1989) [ENM] a Shadows of the Mind (1994) [SM] poskytl poněkud neotřelé anti-mechanistické argumenty. Tyto knihy se ukázaly jako vysoce kontroverzní. Martin Davis reagoval na ENM ve své práci „Is Mathematical Insight Algorithmic?“ (ps), kde tvrdí, že Penrose ignoruje otázku konzistence. Solomon Feferman dává kritické zkoumání SM ve své práci „Penrose’s Gödelian argument“ (pdf).

Důkazní skica pro první větu

Hlavní problém při konkretizaci výše uvedené důkazní myšlenky je následující: aby bylo možné sestavit tvrzení p, které je ekvivalentní „p
nelze dokázat“, p by muselo nějakým způsobem obsahovat odkaz na p, což by mohlo snadno vyvolat nekonečnou regresi. Gödelův důmyslný trik, který později použil Alan Turing, aby ukázal, že Entscheidungsproblem je neřešitelný,
bude popsán níže.

Začneme tím, že každý vzorec nebo výrok, který lze zformulovat v našem systému, dostane unikátní číslo, nazvané jeho Gödelovo číslo.
To se provádí takovým způsobem, že je snadné mechanicky převádět tam a zpět mezi vzorci a Gödelovými čísly. Protože náš systém je dostatečně silný na to, aby dokázal o číslech uvažovat, je nyní možné uvažovat i o vzorcích.

Vzorec F(x), který obsahuje právě jednu volnou proměnnou x
se nazývá formulář výpisu.
Jakmile je x nahrazeno určitým číslem, formulář výpisu se změní na výpis v dobré víře a pak je buď prokazatelný v systému, nebo ne.
Formuláře výpisu samy o sobě nejsou výpisy, a proto je nelze prokázat ani vyvrátit.
Ale každý formulář výpisu F(x) má Gödelovo číslo, které označíme G(F).
Volba volné proměnné použité ve formuláři F(x) není pro přiřazení Gödelova čísla G(F) relevantní.

Pečlivou analýzou axiomů a pravidel systému pak lze zapsat příkaz ve tvaru P(x), který ztělesňuje myšlenku, že x je Gödelovo číslo výroku, který lze v našem systému dokázat.
Formálně: P(x) lze dokázat, pokud x je Gödelovo číslo prokazatelného výroku, a jeho negaci ~P(x) lze dokázat, pokud tomu tak není.
(I když je to pro tento průkazný náčrt dost dobré, technicky to není úplně přesné.
Viz Gödelův papír pro problém a Rosserův papír pro řešení.
Klíčovým slovem je „omega-konzistence“.)

Nyní nastává trik: výrokový formulář F(x) se nazývá samoneprokazatelný, pokud formulář F, aplikovaný na vlastní Gödelovo číslo, není prokazatelný.
Tento pojem lze definovat formálně a můžeme sestrojit výrokový formulář SU(z), jehož interpretace je taková, že z je Gödelovo číslo samostatně neprokazatelného výrokového formuláře. Formálně je SU(z) definováno jako: z = G(F) pro nějakou konkrétní formu F(x) a y je Gödelovo číslo příkazu F(G(F)) a ~P(y). Nyní požadovaný výrok p, který byl zmíněn výše, lze definovat jako:

Nyní budeme předpokládat, že náš axiomatický systém je konzistentní.

Pokud by p bylo prokazatelné, pak SU(G(SU)) by bylo pravdivé a podle
definice SU, z = G(SU) by bylo Gödelovo číslo samostatně neprokazatelné výpovědní formy.
Tudíž SU by bylo samostatně neprokazatelné, což podle definice samostatně neprokazatelné znamená, že SU(G(SU)) není prokazatelné, ale to bylo naše p: p není prokazatelné.
Tento rozpor ukazuje, že p nemůže být prokazatelné.

Pokud by negace p= SU(G(SU)) byla prokazatelná, pak by to podle definice SU znamenalo, že z = G(SU) není Gödelovo číslo samostatně neprokazatelné formy, což znamená, že SU není samostatně neprokazatelné.
Podle definice samostatně neprokazatelné dojdeme k závěru, že SU(G(SU)) je prokazatelné, tudíž p je prokazatelné. Opět rozpor.
Tento ukazuje, že negace p také nemůže být prokazatelná.

Takže tvrzení p nemůže být v rámci našeho systému dokázáno ani vyvráceno.

Důkazní skica pro druhou větu

Nechť p znamená výše zkonstruovanou nerozhodnutou větu a předpokládejme, že konzistenci systému lze prokázat zevnitř samotného systému.
Výše jsme viděli, že pokud je systém konzistentní, pak p není prokazatelné.
Důkaz této implikace lze formalizovat v samotném systému, a proto lze v systému prokázat tvrzení „p není prokazatelné“ nebo „není P(p)“.

Ale toto poslední tvrzení je ekvivalentní samotnému p (a tato ekvivalence může být v systému prokázána), takže p může být v systému prokázáno.
Tento rozpor ukazuje, že systém musí být nekonzistentní.