1. Kapitola první: problém MU
    1. Formální systémy
    2. Teorémy, axiomy, pravidla

Kapitola první: problém MU

Formální systémy

Jedním z ústředních pojmů této knihy je formální systém. My se budeme zabývat typem formálního systému, který vytvořil americký logik Emil Post ve dvacátých letech 20. století a jemuž se často říká „Postův produkční systém“. V této kapitole se podíváme na jeho základní vlastnosti, aby to bylo zábavnější a abychom povzbudili čtenáře k vlastním pokusům s formálními systémy, začneme s hádankou, kterou nazveme „Problém MU“.

Zadání je prosté a lze ho shrnout jednou větou: „Lze vytvořit MU?“ Jako výchozí bod máme řetězec (tedy posloupnost písmen) — tímto řetězcem je MI.* Dále máme k dispozici pár pravidel, podle nichž lze z jednoho řetězce vytvořit jiný. Kdykoli lze jedno nebo více z těchto pravidel použít, můžeme to udělat — nic však nepředepisuje, které z nich použít, bude-li jich použitelných víc. Je to jen na nás, a právě tato vlastnost ovšem činí z podobné hry s formálním systémem předmět jistého umění. Hlavní je ale na to je snad zbytečné upozorňovat — že nesmíme učinit nic, co by nebylo v pravidlech. Takové omezení můžeme nazvat „požadavek formálnosti“. V této kapitole nebudeme mít s jeho dodržováním problém, v následujících kapitolách však budeme experimentovat s některými formálními systémy, které budou k porušování „požadavku formálnosti“ vysloveně svádět, a to zejména ty, kdo nemají v práci s formálními systémy dostatečné zkušenosti.

myšice v hrušce

Nejprve si o našem formálním systému MIU řekneme, že využívá jen tří písmen abecedy: M,I, U. To znamená, že do MIU-systému mohou patřit jedině ty řetězce, které používají výhradně tato tři písmena. Zde je několik řetězců, které by mohly do MIU patřit:MU UIM MUUMUU UIIUMIUUIMUIIUMIUUIMUIIU

*V této knize budeme ohledně řetězců užívat následující úmluvy. Je-li řetězec vysazen ze stejného písma jako text, pak bude ohraničen jednoduchými“ či „dvojitými“ uvozovkami. Interpunkce, jež je součástí textu, nikoli však řetězce, zůstane logicky vně uvozovek. Například první písmeno této věty je „N“, zatímco první písmeno „této věty“ je „t“.

Tyto řetězce jsou sice všechny v abecedě MIU-systému, zatím však v naší sbírce MIU- řetězců máme jen jeden jediný, a to MI. Naši soukromou sbírku můžeme rozšiřovat jen pomocí následujících pravidel. Zde je první z nich:

PRAVIDLO I: Máme-li řetězec, jehož poslední písmeno je I, můžeme na jeho konec přidat U.

Mimochodem, pokud by to nebylo všem zřejmé: součástí významu slova „řetězec“ je pevné pořadí jeho písmen. Například MI a IM jsou dva různé řetězce. Řetězec symbolů není jen nějaký košík, v němž pořadí nehraje roli. Zde je druhé pravidlo:

PRAVIDLO II: Předpokládejme, že máme Mx. Pak lze do naší sbírky přidat i Mxx. Několik následujících příkladů ukazuje, co tím máme na mysli:

Z MIU můžeme vytvořit MIUIU. Z MUM můžeme vytvořit MUMUM. Z MU můžeme vytvořit MUU.

Písmeno „x“ v pravidle II zastupuje libovolný řetězec; jakmile se však rozhodneme, který řetězec to je, musíme u své volby pro toto konkrétní použití pravidla setrvat (při dalším použití pravidla ovšem tuto volbu činíme znovu). Viz poslední příklad: jakmile máme MU, můžeme do své sbírky přidat i MUU; nejprve však musíme MU získat! Ještě poslední poznámku k písmenu „x“: není součástí daného formálního systému ve stejném smyslu jako písmena „M“, „I“ a „U“. Je totiž užitečné umět se vyjadřovat o řetězcích systému obecně, symbolicky — a to je právě role „x“, které zastupuje libovolný řetězec. Pokud bychom někdy přidali do své sbírky řetězec obsahující „x“, nebude to v pořádku, protože řetězce MIU-systému žádné „x“ nemohou obsahovat.

Zde je třetí pravidlo: PRAVIDLO III: Pokud se v některém řetězci vyskytuje III, můžeme udělat nový řetězec s U místo III. Příklady: Z UMIIMU můžeme udělat UMUMU. Z MIlll můžeme udělat MIU (a také MUI). Z IIMIl pomocí tohoto pravidla nemůžeme udělat nic. (Tři | musejí následovat bezprostředně po sobě.) Z Mill můžeme udělat MU. V žádném případě neplatí, že toto pravidlo lze použít obráceně jako v následujícím příkladu: Z MU uděláme Mlll. <= To je špatně. Pravidla jsou totiž jednosměrná. A zde je poslední pravidlo:

PRAVIDLO IV: Pokud se uvnitř některého řetězce vyskytne UU, můžeme ho odstranit. Z UUU dostaneme U. Z MUUUJII dostaneme MUIII.

A to je vše. Teď můžeme začít s pokusy o vytvoření MU. Možná se to hned nepodaří, tím se však nenecháme odradit — důležité je získat trochu praxe v práci s MIU- systémem. Dobrou zábavu.

Teorémy, axiomy, pravidla

Řešení Problému MU si ukážeme později — v této fázi nebyl důležitý cíl, ale hledání cesty k němu. Při pokusech s MIU-systémem jsme vytvořili svou soukromou sbírku řetězců. Těmto řetězcům, které vznikly podle daných pravidel, budeme říkat teorémy. Zde je nutné podotknout, že termín „teorém“ v matematice znamená něco trochu jiného, než co jím budeme označovat v této kapitole my. V matematice je teorém řidčeji užívaným synonymem termínu věta a oba termíny zde označují nějaké tvrzení v běžném jazyce, jehož platnost byla dokázána argumentací podle přesných pravidel — viz třeba Zenonův teorém o „neexistenci“ pohybu, Eukleidova věta o nekonečném počtu prvočísel či Churchův teorém, o kterém budeme mluvit později. My se dopustíme určité svévole a v této knize si pojem „teorém“ vyhradíme pro použití ve formálních systémech, zatímco pro běžné užití budeme používat termínu „věta“. Tyto termíny budeme zaměňovat jen tam, kde je slovní spojení zažité a nehrozí riziko záměny. Náš MIU-systém je vzorovým příkladem formálního systému, jeho „teorémy“ nejsou žádná tvrzení (jsou to pouhé řetězce symbolů) a místo dokazování je budeme jen vytvářet jakoby strojem, podle jistých typografických pravidel. Raději si to zformulujme ještě jinak: „teorém“ je jen technické označení řetězce, jenž se dá vytvořit v nějakém formálním systému. V tomto smyslu Problém MU spočívá v otázce, zda je MU teorémem MIU-systému.

Do začátku jsme volně dostali jednu větu, totiž MI. Taková „volná“ věta se nazývá axiom — i to je jen technický termín zcela odlišný od obvyklého matematického významu (my ho budeme užívat v obou významech). Formální systém může mít libovolný počet axiomů: žádný, jeden, několik, ba i nekonečně mnoho. Se všemi z těchto možností se ještě v knize setkáme.

Každý formální systém má pravidla pro manipulaci se symboly, podobná oněm čtyřem pravidlům MIU-systému. Tato pravidla se nazývají produkční pravidla nebo odvozovací pravidla. Budeme používat oba termíny.

Na závěr zavedeme ještě jeden termín, a to odvození. Zde je příklad odvození teorému MUIIU:

(1) MI axiom (2) MII z (1) podle pravidla II (3) MIIII z (2) podle pravidla II (4) MIIIIU z (3) podle pravidla I (5) MUIU z (4) podle pravidla III (6) MUIUUIU z (5) podle pravidla II (7) MUIIU z (6) podle pravidla IV

Odvození věty je přesný návod, jak krok za krokem větu vytvořit podle pravidel formálního systému. Odvození je založeno na stejném principu jako důkaz, je však jen jeho chudým příbuzným. Tvrdit, že jste dokázali MUIIU, by znělo poněkud podivně, odvodit ho už zní mnohem lépe.