Gödelovo číslování a formální aritmetika

Toto je šestý 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.

Z předchozích pěti dílů tohoto seriálu již známe prakticky všechny ingredience potřebné k porozumění tomu, proč není možné stvořit formální systém, který by byl schopen dokázat všechna pravdivá tvrzení matematiky. Bylo již řečeno, jak formální systémy fungují, a v minulém díle jsem nakousl, jak do řeči formálních systémů převést paradox lháře: Očíslujeme-li si jistým jednoznačným způsobem všechny výrazy, stane se dokazatelnost výroku tvrzením o přirozených číslech. Jestliže systém umožňuje formulovat výroky o přirozených číslech, automaticky nabízí i možnost formulovat i výroky o dokazatelnosti svých vlastních výrazů. Pak stačí zformulovat výraz, který tvrdí sám o sobě (prostřednictvím Gödelova číslování), že je nedokazatelný. Takový výrok je buď nedokazatelný a tudíž pravdivý nebo dokazatelný a zároveň nepravdivý. Idea je tedy jasná, ovšem podání bylo doposud poněkud vágní. Zbývá dořešit několik technických detailů a dovést tak konstrukci formální verze lhářova paradoxu do (téměř) explicitní podoby. Co je tedy ještě nutné prodiskutovat? Čeká nás

1. ilustrace Gödelova číslování na jednoduchém systému (kterou potřebujeme, aby vynikla souvislost mezi tvrzeními o dokazatelnosti výroků s tvrzeními o přirozených číslech)
   
2. naznačení toho, jak vypadá formální aritmetika aneb teorie čísel (se vším všudy jsem zatím popsal pouze výrokovou logiku, k dokazování aritmetických pravd je potřeba větší systém)
   
3. diskuse toho, jaká fakta o přirozených číslech musí formální aritmetika být schopna odvodit, nebo aspoň vyjádřit (což potřebujeme, protože konstrukce lhářova paradoxu nebude zcela explicitní — výrazy mluvící o dokazatelnosti výroků jsou příliš složité na to, aby zde byly vypsány; budeme se muset obejít s vírou v jejich existenci, a tato víra vyžaduje odůvodnění)
   
4. konstrukce autoreference pomocí „quinování“ (potřebujeme techniku, jak vtěsnat do výroku jeho vlastní Gödelovo číslo).
   

V tomto díle se dostanu k prvním dvěma bodům.

K prvnímu bodu si vypůjčím primitivní systém MIU zavedený již v prvním dílu. Pro osvěžení: abecedu systému tvořily tři písmena M, I a U. K tomu byl k dispozici axiom MI a tři odvozovací pravidla:

1. Končí-li teorém na I, můžeme na konec přidat U a získáme nový teorém. Tedy je-li XI teorém, pak XIU je teorém. (Například, z UII odvodíme UIIU.)
   
2. Máme-li teorém začínající na M, můžeme to, co následuje, zdvojit. Tedy je-li MX teorém, MXX je teorém. (Například, z MMUUI odvodíme MMUUIMUUI.)
   
3. Když v libovolném teorému nahradíme podřetězec III symbolem U, získáme nový teorém. Tedy je-li XIIIY teorém, je i XUY teorém. (Například, z UMUIIIU odvodíme UMUUU.)
   

Jak zavést Gödelovo číslování? Odpověď je, že prakticky jakkoli. Můžeme to provést například tak, že je nejprve rozdělíme do skupin podle délky; v každé takové skupině bude zjevně pouze konečný počet dobře formovaných výrazů. Ty pak seřadíme abecedně. Získáme tak jednoznačné řazení všech dobře formovaných výrazů a každému můžeme přiřadit číslo odpovídající jeho pořadí. Jiný způsob očíslování výroků je ještě jednodušší na provedení: každému znaku formální abecedy přiřadíme nějaké číslo, a číslo celého výrazu získáme slepením desítkového zápisu čísel znaků, ze kterých sestává. Jak konkrétně Gödelovo číslování provedeme je zcela jedno; záleží pouze na tom, aby každému dobře formovanému výrazu odpovídalo právě jedno přirozené číslo, a aby každému přirozenému číslu odpovídal nejvýše jeden výraz našeho formálního systému [*].

Musíme zvolit jedno konkrétní Gödelovo číslování, a učiňme to například takto: M nahradíme číslicí 3, I číslicí 1 a U číslicí 5. Gödelovo číslo (dále jen G.č.) výrazu UMUIIIU tak je prostě 5351115, jediný axiom MI má číslo 31 atd.

Odvozovací pravidla byla formulována tak, aby se s výrazy pohodlně manipulovalo jako s řetězci znaků. Samozřejmě můžeme pravidla „přeložit“ z jazyka řetězců do jazyka Gödelových čísel, maje tak

1. končí-li G.č. teorému na 1, můžeme na konec přidat 5 a získáme G.č. nového teorému.
   

Spíš než o překlad se jedná o otrockou transliteraci — místo se symboly M, I a U tu šíbujeme se symboly 1, 3 a 5. Cílem ale není nahrazovat symboly, nýbrž přejít od symbolických manipulací s textovými řetězci k aritmetickým operacím s čísly. Dostáváme se tak ke skutečnému překladu do jazyka aritmetiky.

1. Je-li g G.č. teorému a je-li zbytek po dělení g deseti roven jedné, potom i g' = 10g + 5 je G.č. teorému.
   
2. Je-li g G.č. teorému a existuje-li přirozené číslo n takové, že 3.10ⁿ < g < 4.10ⁿ, potom g' = 3.10²ⁿ + 10ⁿ g + g je G.č. teorému.
   
3. Je-li g G.č. teorému a existují-li přirozená čísla k, m a n takové, že m < 10ⁿ a zároveň g = 10ⁿ⁺³ k + 111.10ⁿ + m, potom g' = 10ⁿ⁺¹ k + 5.10ⁿ + m je G.č. teorému.
   

V těchto řádcích lze s trochou námahy poznat výše sepsaná pravidla systému MIU, tentokráte však převlečená do hávu aritmetických operací. Pravidla nevypadají zrovna jednoduše, ale na tom příliš nezáleží.

Prozatím máme pravidla pro manipulaci s přirozenými čísly; podívejme se ale na některé výroky o číslech. Vezměme kupříkladu tuto trivialitu: „315 = 10.31 + 5 a zároveň zbytek po dělení 31/10 je 1“. Jedná se o konjunkci dvou prostých tvrzení týkající se čísel 5, 10, 31 a 315 — za ní se ovšem, ve světle Gödelova číslování, skrývá tvrzení o systému MIU. Konkrétně, „MIU je korektně odvozeno aplikací I. pravidla z MI“. Můžeme postoupit ještě o krok dále, když nahradíme konkrétní čísla volnými proměnnými. Výrok „n = 10.31“ vlastně znamená „n je G.č. teorému systému MIU odvozeného pomocí I. pravidla z axiomu MI“.

Můžeme analogicky, jako tvrzení o přirozených číslech, vyjádřit výrok „X je teorémem systému MIU“? (Pokud se nám podaří aritmetickým jazykem mluvit o systému MIU, dle stejného návodu budeme moct mluvit i o jiných systémech.) Jistě, jakmile nahradíme výrazy jakéhokoli systému jejich Gödelovými čísly, tvrzení o výrazech se stávají tvrzeními o přirozených číslech. Přísně vzato ale potřebujeme víc: nestačí nám tvrzení o přirozených číslech, potřebujeme tvrzení, které se dá formulovat v rámci formální aritmetiky. Zatím jsem se vyhýbal přesnému popisu toho, jak má tato formální aritmetika vypadat, a tak tu zůstává určitá volnost ve výběru toho, jak aritmetiku formalizujeme. Jistě se nespokojíme s něčím tak primitivním, jako byl systém PR popsaný v druhém díle této série. Systém PR byl schopen vyjádřit pouze výroky o sčítání, zatímco naše ambice je najít systém, který bude formalizovanou verzí běžné aritmetiky. Aby této ambici dostál, musí zvolený systém být schopen vyjádřit a dokázat všechny pravdy o přirozených číslech, ke kterým jsme schopni dojít neformálním myšlením. Musí tedy být schopen vyjádřit například

• 17 je liché číslo
  
• pokud je n mocnina dvou, potom n není mocnina tří
  
• existuje nekonečné množství prvočísel
  
• neexistují kladná a, b, c a n > 2 takové, že aⁿ + bⁿ = cⁿ
  

a tak dále.

Asi nejběžnější formalizace aritmetiky vychází z axiomů, které poprvé zformuloval italský matematik Giuseppe Peano. Nebudu zde ovšem diskutovat Peanovy axiomy a příslušná gramatická a odvozovací pravidla [*], poněvadž jejich konkrétní tvar není extrémně důležitý. Pro utvoření hrubé představy pouze řeknu, s jakými symboly se můžeme setkat a uvedu formální verze některých jednoduchých tvrzení.

Nejdříve symboly. Formální aritmetika bude především obsahovat vše, co obsahovala výroková logika, ovšem kromě symbolů A, B, C atd., označujících abstraktní výroky. Důvod je samozřejmě ten, že aritmetiku nezajímají neurčené abstraktní výroky, nýbrž zcela konkrétní výroky o číslech. Musíme tedy přidat symboly pro čísla a relace mezi nimi. Obejdeme se se symboly 0, S, +, ., =, ∀, ∃ a nakonec symboly pro proměnné: a, b, c atd.

Symboly 0, +, . a = mají přesně ty významy, které od nich každý očekává; tedy označují nulu [*], sčítání, násobení a rovnost. Kvantifikátory ∀ a ∃ jsou taktéž známé. Symboly proměnných slouží, nepříliš překvapivě, k zápisu proměnných. Jediný nestandardní symbol je S. Napíšeme-li S před jiný číselný výraz, získáme tak číslo o jedna vyšší (písmeno S je z latinského successor = „následník“). Symbolu S užíváme především k zápisu všech čísel kromě nuly: S0 je jednička, SS0 dvojka a tak dále. Lze jej ale psát i před jiné výrazy, například můžeme mít Sa, S(S0+b) nebo SS(a.Sb).

Abeceda formální aritmetiky umožňuje zapsat řadu výroků o přirozených číslech relativně přímo. Výrok „jedna plus jedna se rovná dvěma“ má formální protějšek ((S0+S0)=SS0) [*], výrok „číslo a je rovno pěti“ přejde na (a=SSSSS0). Takhle snadné je to vždy, když výrok obsahuje pouze „primitivní“ operace a vztahy, jako sčítání nebo rovnost. Primitivními operacemi přitom myslíme ty, které mají ve formální abecedě své vyhrazené symboly. Ne všechny operace a vztahy ale mohou být primitivní. Kdybychom chtěli mít speciální symbol pro každý matematický koncept, potřebovali bychom obludně velkou abecedu. I v neformálním přístupu k matematice běžně definujeme složitější pojmy pomocí jednodušších, a situace není nijak odlišná zde. Třeba pro zápis výroku „pět je větší než dva“ nám chybí symbol pro „je větší“ a musíme jej nahradit nepřímo. Řešením je přeformulovat výrok s užitím pouze primitivních konceptů. Jedna přípustná náhrada zní: „neexistuje číslo n takové, že n není nula a zároveň n + 5 = 3“, symbolicky ¬∃n:(¬(n=0)∧((n+SSSSS0)=SSS0)) [*]. Formulaci lze ještě vylepšit: v řetězci ¬∃n:((Sn+SSSSS0)=SSS0)) jsme se elegantně zbavili konjunkce díky tomu, že Sn zde stojí jako symbol pro libovolné nenulové přirozené číslo (nula není následníkem žádného jiného přirozeného čísla).

Uvedený příklad ilustruje, že překlad neformálních výroků do řetězců formálního systému není vždy přímočarý. Formalizace složitějších výroků dá zpravidla velkou práci a vyžaduje i jistou praxi. Jako relativně jednoduché cvičení si můžete například zkusit zformalizovat „n je mocnina dvou“ (řešení viz [1]). Nabízí se tedy otázka: je skutečně pomocí uvedených symbolů zaručeně možné formalizovat jakýkoli výrok o přirozených číslech? Odpověď je, ne zcela. Existuje ovšem široká třída funkcí, které formalizovat lze, a existence formalizovaných verzí těchto funkcí je pro naše účely dostačující. Jedná se o primitivně rekurzivní funkce, kterým se bude věnovat příští díl.

Poznámky:
1. Formální verze výroku „n je mocnina dvou“ může být např. ¬∃a:(∃b:((SSSa.b)=n)∧¬∃c:∃d:(a=(SSc.SSd))). Tedy doslova: „neexistuje a, pro které existuje b takové, že (a + 3)b = n, a zároveň pro které není pravda, že existují c a d takové, že (c + 2)(d + 2) = a“. Méně doslovně a srozumitelněji (označme e = a + 3): „neexistuje e > 2, které je dělitelem n, a které zároveň nemá dělitele většího než 2“. Ještě více polopaticky: „Neexistuje prvočíselný dělitel n vyšší než dvojka“.