Epimenidův paradox

Toto je pátý díl seriálu o logice, který volně sleduje myšlenky D.Hofstadtera sepsané v jeho knize Gödel, Escher, Bach. Navigace: úvodní článek - předchozí díl - příští díl.

Paradox lháře neboli Epimenidův paradox patří k nejstarším logickým paradoxům. Bez zajímavosti není ani jeho historie — v původní formě byl připisován Epimenidovi, který, byť sám Kréťan, označil všechny Kréťany za lháře. Epimenidés sám tímto výrokem nechtěl nastolit téma logických paradoxů, spíš mu šlo o kritiku svých krajanů, kteří trvali na pro Epimenida nepřijatelné herezi, že Zeus je smrtelný. Pozdějším Epimenida znalým autorům už paradoxnost výroku neušla. Jak můžeme Epimenidovi věřit, že všichni Kréťané jsou lháři, když on sám je Kréťan, a tudíž, v důsledku svého vlastního tvrzení, lhář?

Klasicky formulovaný Epimenidův „paradox“ je nanejvýš řečnickou chybou, stěží však může aspirovat na roli opravdového logického paradoxu. Možná Epimenidés mluví pravdu; nic nebrání lhářům čas od času říkat pravdu. Nebo možná lže: existuje pár pravdomluvných Kréťanů (Epimenidés k nim nepatří), takže není pravda, že všichni jsou lháři. Není ovšem těžké Epimenidův výrok upravit tak, aby se stal skutečným paradoxem. Kdyby Epimenidés řekl „teď lžu“, postrádalo by jeho tvrzení svou morálně přesvědčovací sílu, ale zato by bylo skutečným oříškem pro logiku. A kdyby byl Epimenidés zběhlejší v novodobé logice, asi by místo toho pověděl „tento výrok je nepravdivý“, což je asi nejběžnější moderní formulace paradoxu lháře. Je snadné nahlédnout, že takovýto o sobě mluvící výrok nemůže být ani pravdivý, ani nepravdivý — a věta, která není ani pravdivá, ani nepravdivá, si zaslouží pojmenování paradox.

Paradoxu lháře v průběhu času vyrostla spousta příbuzných. Jedním z nich je Russelův paradox, který není ničím jiným, než paradoxem lháře převlečeným do jazyka teorie množin. Množinu x nadefinujeme jako množinu všech množin, které neobsahují sama sebe. x je zřejmě docela velká množina obsahující řadu prvků; prázdnou množinu, množinu {1,2,5}, množinu všech reálných čísel nebo množinu všech jednookých Vietnamců, například. Obsahuje ale x sama sebe? Pokud ne, pak se dostáváme do sporu s definicí, protože x má obsahovat všechny množiny neobsahující sama sebe, a přitom x je množina neobsahující sama sebe, jež není prvkem x. Tedy x obsahuje sama sebe. Jenže to je také spor s definicí, protože ta volá po tom, aby x obsahovala pouze množiny, které sebe neobsahují.

Trochu jiný, po mém soudu subtilnější, je Curryho paradox: „Je-li tato věta pravdivá, pak Brno leží v Asii.“ Je to pravdivá věta? Označme ji V, a když už jsme u toho označování, zaveďme též symbol B pro větu „Brno leží v Asii“. Máme tak V = (V ⇒ B). Zkusme předpokládat, že V je pravda. Je-li tomu tak, pak V ⇒ B je pravdivý výrok (nu pochopitelně, vždyť je to V samo), ale pokud V a zároveň V ⇒ B jsou pravdivé, pak B je pravda (vzpomínáte na modus ponens?) a Brno leží v Asii. Brno ale podle všeho neleží v Asii, takže V nemůže být pravdivé. Předpokládejme tudíž, že V je nepravda. Jakýkoli výrok X ⇒ Y, kde X je nepravdivý výrok, je podle zásad logiky pravdivý. Tudíž V ⇒ B je pravdivý výrok, leč hle, tento výrok je roven samotnému V, které je dle předpokladu nepravdivé! Což je spor, a V tak nemůže být ani nepravdivé.

Pocit paradoxnosti obvykle vyplývá z narušení některého intuitivně přijímaného předpokladu, v tomto případě pak jde o předpoklad, že každý výrok musí být buď pravdivý nebo nepravdivý. Uvedené příklady výroků ukazují, že zcela obecně něco takového předpokládat nemůžeme. V zásadě by to nemusela být velká potíž: od každého předpokladu se můžeme oprostit, ukáže-li se jeho nevhodnost, a v tomto případě prostě uznáme, že ne každý výrok má dobře definovanou pravdivostní hodnotu. Nebo, ekvivalentně, můžeme věty s nejasnou pravdivostní hodnotou vyloučit z kategorie „výroků“. Není tedy a priori zřejmé, že lhářův paradox představuje skutečný problém pro formalizovanou logiku. Mohlo by se zdát, že paradox pouze odráží nějakou nedokonalost neformálního jazyka a při dostatečně pečlivé analýze zmizí, nebo se ukáže triviálním. Zkusme se tedy vydat touto cestou a zjistit, jak daleko je možno dojít.

Neúplný, nekonsistentní, nebo nedůvěryhodný?

Aby lhářův paradox přestavoval problém pro nějaký formální systém, musíme především být schopni jej v onom formálním systému formulovat; to jest vytvořit dobře formovaný výraz, jehož interpretace by zněla „tento výrok je nepravdivý“. Abychom dali celé věcii přesný technický smysl, pak je lépe užít interpretace „tento výraz je nedokazatelný“, či ještě přesněji „negace tohoto výrazu je teorémem systému S“ [*], kde S je systém, ve kterém výrok formulujeme a případně dokazujeme. Podaří-li se takový výraz sestrojit, pak máme problém. Pokud totiž takový výraz je teorémem, pak, věříme-li interpretaci našeho systému, i jeho negace je teorémem, a systém je nekonsistentní. Jestliže výraz není teorémem, pak jeho interpretace je pravdivá, a tudíž jeho negace (znovu, věříme-li interpretaci) nemůže být teorémem, a systém je neúplný.

Máme tedy na výběr tři možnosti. Buď je systém neúplný, nebo je nekonsistentní, nebo se nedá bezvýhradně důvěřovat interpretacím jeho teorémů. Poslední možnost není moc lákavá: kdybychom připustili, že občas teorémy mohou lhát, mohl by být systém klidně úplný i konsistentní zároveň — jenže připustit něco takového prakticky znamená vyhodit důvěryhodnost systému oknem. Kdyby formální důkazy občas lhaly, možná by matematikové před formálním dokazováním dali přednost návštěvě u kartářky; to je zpravidla rychlejší a pohodlnější metoda, jak se dobrat odpovědi. Možnost, že systém je nekonsistentní, je taktéž velmi nepříjemná kvůli minule diskutovanému principu exploze. Zbývá tak poslední možnost, a to neúplnost. Znamená to, že existují pravdivé výroky, které je možné v systému zformulovat, ale které nejsou teorémy, a tudíž je není možné dokázat. S tím se sice dá žít, ale i tak je to velmi závažný fakt pro samotné základy matematiky. Za své bere naděje generací matematiků, že každé pravdivé tvrzení o matematických objektech je možné dokázat vycházeje z určité sady axiomů, stejně jako to šlo v eukleidovské geometrii.

Ale to už trochu předbíháme — pořád nám zbývá ta nejtěžší, a pravděpodobně i nejzajímavější část celého problému: povinnost lhářův paradox v našem formálním systému zformulovat. Kdyby systém takovou formulaci neumožňoval, vyhnuli bychom se nepřílemnému trilematu předchozího odstavce a mohli bychom šťastně věřit na dokazatelnost všech matematických pravd. Před Gödelem a rokem 1931 bylo něco takového vnímáno jako jeden ze základních cílů matematiky. Konkrétně, věřilo se, že existuje formální systém, jenž umožňuje zformulovat mimo jiné všechna tvrzení aritmetiky (a dokázat ta pravdivá), a jenž je zároveň imunní vůči paradoxu lháře.

Jazyk a metajazyk

Věc, kterou mají všechny verze paradoxu lháře společnou, je autoreference. Autoreference neznamená nic jiného, než že výroky mluví samy o sobě. Konkrétně je autoreference v našem paradoxu zastoupena frází „tento výraz“, ale může být i skrytá. Uvažte například dvojici výroků:

1. „Následující výrok je nepravdivý.“
   
2. „Předchozí výrok je pravdivý.“
   

Ačkoli ani jeden z obou výroků v sobě neodkazuje sám na sebe, dohromady fungují úplně stejně, jako lhářův paradox. Chceme-li se tedy vyhnout problémům s autoreferencí, nestačí se vyvarovat přímých autoreferenčních odkazů. Jedna možnost je „zakázat“ jakékoli odkazy na výroky; věta „výrok P je pravdivý“ by se tak vymykala formalizaci. Podíváme-li se na na výrokovou logiku jako nejjednodušší prototyp systému, ve kterém má cenu mluvit o úplnosti a konsistenci, vidíme, že to tak může fungovat. Výroková logika obsahuje různé symboly: závorky, logické operátory a písmena. Každé písmeno je možno interpretovat jako nějaký konkrétní výrok přirozeného jazyka, třeba „Brno leží v Asii“ nebo „železo má atomové číslo 26“. Je v principu jedno, jakou interpretaci vybereme, pouze si musíme dávat pozor na dvě věci. Jednak každý výskyt jednoho písmene musí být v rámci jedné formule interpretován týmž výrokem (a tedy (P∨¬P) můžeme interpretovat jako „buď Brno leží v Asii, nebo Brno neleží v Asii“, ale ne „buď Brno leží v Asii, nebo železo nemá atomové číslo 26“), a jednak interpretace musí být konkrétní na kontextu nezávislý výrok, který neobsahuje žádné volné proměnné nebo odkazy. Druhým požadavkem vylučujeme výroky typu „číslo n je sudé“ nebo „výrok P je pravdivý“. Význam fráze „tento výraz“ samozřejmě na kontextu velmi závisí a požadavky tak nesplňuje. Výroková logika je díky tomu odolná vůči paradoxu lháře: řetězec s interpretací „negace tohoto výrazu je teorém“ v jejím rámci nestvoříme.

Problém s takovým přístupem je jeho přílišná svazujícnost. Výroková logika je velmi slabý systém, jehož dokazovací schopnost se omezuje na tautologie. Stojí za to zkoumat systémy s větší formulační silou; je-li naše ambice dokázat všechna tvrzení matematiky, s výrokovou logikou si určitě nevystačíme. Být naprosto neschopen formulovat výroky o výrocích taktéž není vlastnost z nejžádanějších. Existuje spousta výroků o výrocích, jejichž pravdivost není nijak pochybná ani paradoxní, a jsme-li schopni se na jejich pravdivosti shodnout užívajíce neformálního myšlení, měli bychom být schopni naše úvahy zformalizovat.

Nadějně vypadající cesta spočívá v rozdělení našeho jazyka do jakési nekonečné kastovní hierarchie. Na jejím dně spočívají výroky neobsahující žádný odkaz na jiné výroky. Tyto výroky tvoří dohromady jazyk nulté úrovně, kterým jsme schopni popsat prakticky všechno, kromě výroků o jazyce samém. Mluvit o jazyce, respektive o výrocích tohoto jazyka, přitom není zakázáno. Mluva tohoto typu ale náleží do jiného jazyka, metajazyka první úrovně. V něm jsme schopni formulovat vše, co je formulovatelné v jazyce nulté úrovně, a k tomu navíc i výroky hovořící o větách jazyka nulté úrovně. Metajazyk první úrovně ovšem neumožňuje hovořit o těch výrocích metajazyka první úrovně, které zároveň nespadají do základního jazyka úrovně nulté. K tomu potřebujeme metajazyk druhé úrovně, a tak dále, ad infinitum. V tomto systému každý výrok stojí na nějakém konkrétním stupni hierarchie jazyků, přičemž výroky metajazyka n-té úrovně mohou mluvit o výrocích všech (meta)jazyků nižších úrovní. Žádný výrok ale nemůže mluvit sám o sobě, a stejně tak není možná cyklická autoreference: náleží-li „následující výrok je nepravdivý“ do úrovně n, pak následující výrok náleží nanejvýš úrovni n – 1, a není tedy oprávněn mluvit o předchozím výroku.

Stejná myšlenka aplikovaná na teorii množin vede k teorii typů, která byla populární na počátku dvacátého století.

Nevyhnutelnost autoreferencí

I když hierarchizace výroků je svým způsobem neelegantní (přinejmenším v normální komunikaci nerozlišujeme různé úrovně jazyka), zdálo by se, že problém s paradoxem lháře řeší docela dobře. Zdání ale klame: autoreference, které jsme vyhodili dveřmi, se u dostatečně složitého systému skrytě vrací oknem. Dostatečnou složitostí se zde míní schopnost systému vyjadřovat všechna tvrzení aritmetiky, a trik, kterým se autoreferenci podaří přežít všechny pokusy o své vymýcení, spočívá v tzv. Gödelově číslování. Gödelovo číslování není nic složitějšího, než jednoznačné přiřazení přirozeného čísla každému dobře formovanému výrazu. Poněvadž Gödelovo číslo věrně reprezentuje jemu odpovídající výraz, můžeme místo s výrazy operovat s čísly. Odvozování se stane aritmetickou operací a dokazatelnost výroku specifickou vlastností přirozených čísel. Stále ale předpokládáme, že náš systém je schopen vyjádřit jakékoli tvrzení o vlastnostech přirozených čísel. Musí tedy být možné v tomto systému zapsat výrok tvrdící, že g je Gödelovým číslem nějakého teorému! Gödelovo číslování tak umožňuje systému mluvit o dokazatelnosti výrazů, aniž by na to byl vybaven speciálním symbolem přímo interpretovaným jako „je dokazatelný“.

To ještě automaticky neumožňuje vyjádřit lhářův paradox. Potřebujeme zkonstruovat výraz, který říká „g není Gödelovým číslem teorému“, přičemž zároveň g musí být Gödelovým číslem formální verze výrazu „g není Gödelovým číslem teorému“. Strčit do specifického výrazu jeho vlastní Gödelovo číslo není úplně triviální úloha. Protože tento díl je již dostatečně dlouhý, podrobnější debatu o Gödelově číslování, aritmetické reprezentaci dokazatelnosti a obsažení Gödelova čísla výroku v něm samém ponechám na příště.