úterý 31. května 2011

Pravda a dokazatelnost


Toto je třetí 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.

Ještě než se dostaneme k vlastním ideím Gödelova důkazu věty o tom, že dostatečně složité formální systémy jsou buď neúplné, nebo nekonsistentní (význam těchto slov jsem nastínil v minulém díle), ještě se zastavím u dvou aspektů vztahu formálních pravidel a interpretace. První poznámka se týká vztahu teorémů a neteorémů; toto téma jsem minule již nakousl, když jsem zjistil, že MU není teorémem systému MIU (definovaného v prvním díle), ale tento fakt není v konečném čase prokazatelný v rámci systému MIU. Pozorování tohoto typu samozřejmě neplatí pouze pro systém MIU, ale zcela obecně pro všechny formální systému; tedy aspoň pro ty, ve kterých existuje nekonečné množství legálních odvozovacích postupů. Při pohledu „zevnitř“ systému mají množina teorémů a množina neteorémů velmi odlišný charakter: o teorému se můžeme přesvědčit, že je teorémem, zatímco o neteorému si nikdy nemůžeme být jisti. Chceme-li si být jisti, musíme užít dedukci ležící mimo daný formální systém. Toto pozorování možná nepůsobí nijak převratným dojmem v případě systému MIU, ale zní lehce překvapivě, díváme-li se stejným způsobem na logiku.

V minulých dílech bylo taktéž řečeno, že teorémy logiky, v rámci její přirozené interpretace, odpovídají pravdivým tvrzením, zatímco neteorémy odpovídají nepravdivým tvrzením. V abecedě formální logiky máme mimo jiné znak ¬, který interpretujeme jako negaci. Jednou z triviálně chápaných vlastností negace je to, že pokud tvrzení je pravdivé, jeho negace je nepravdivá. Víme-li tedy, že nějaký výraz formální logiky je teorém, chtělo by se jeho negaci prohlásit za neteorém. Problém s tímto přístupem je v tom, že leží za hranicemi toho, co formální systémy umožňují. Formální systémy umožňují odvozovat teorémy, nikoli neteorémy. Teorém je definován pozitivně jako něco, co je možno v konečném počtu kroků odvodit z daných axiomů; neteorémy tvoří doplněk množiny teorémů, a nic nezaručuje, že je taktéž lze v konečném čase generovat.

Člověk není Turingův stroj a může si s pravidly svých formálních systémů hrát. Jedna z otázek, která se nabízí téměř automaticky, je tato: Nešlo by pojetí formálních systémů rozšířit tak, aby bylo možno v konečném čase generovat i neteorémy? Konečnou sadu neteorémů bychom povýšili na „neaxiomy“ a zavedli bychom „neodvozovací pravidla“, pomocí kterých bychom generovali neteorémy. Vraťme se na moment k dříve diskutovanému MIU. Roli „neaxiomu“ by tam mohl hrát třeba řetězec U a jedno z „neodvozovacích pravidel“ by znělo takto:

  1. Je-li X neteorém, pak XY je neteorém (X,Y libovolné výrazy).

Tato konstrukce generuje všechny možné řetězce začínající na U, o kterých z výše provedené analýzy víme, že skutečně nepatří mezi teorémy. Zároveň ale vidíme, že ne všechny neteorémy lze vygenerovat tímto pravidlem — například takto nedostaneme náš známý řetězec MU. Seznam pravidel a „neaxiomů“ generující všechny neteorémy systému MIU by musel zřejmě být větší. Není samozřejmě jisté, zda takový seznam vůbec lze sestrojit; i pokud ale takový systém sestrojit lze, abychom ověřili, že generuje všechny neteorémy a právě jen neteorémy, museli bychom užít dedukci přesahující rámec zvoleného systému. [*].

Mělo by být zřejmé, co z toho plyne pro nápad zavést do formální logiky „pravidlo“, že negace teorému je neteorém. Ačkoli každý, kdo užívá logiku, věří, že tomu tak je, úvahami v rámci příslušné verze logiky není možné ukázat, že neexistuje výraz, který sám, a zároveň i jeho negace, jsou teorémy. Je možné si představit nějaký obecnější systém uvažování, který by tento fakt byl schopen ukázat, ale to pouze odsouvá problém o úroveň výše: obecnější systém, má-li strukturu formálního systému (což není až zas tak silný předpoklad), se střetává se stejnou asymterií mezi pozitivně vymezenou množinou teorémů a jejím doplňkem. Z nejobecnějšího sestrojitelného systému, takového, který by plně popisoval idealizovanou strukturu lidského myšlení, nemáme šanci vystoupit o úroveň výš. Bez onoho vystoupení výš nemůžeme ukázat, že nějaký konkrétní výraz není teorémem; v konkrétnějším případě pak nemůžeme ukázat, že pokud výraz X je teorém, pak ¬X není teorém. Musíme tak být spokojeni s tím, že množina neteorémů je definována pouze negativně. Poněkud se to příčí intuici: kdybychom chtěli být echt přesní, mohli bychom vlastně rozlišovat význam napohled identických vět

  1. dva plus tři není rovno čtyřem, a
  2. není pravda, že dva plus tři je rovno čtyřem.

První z nich říká [*], že ¬(2+3=4) je teorém, zatímco druhá říká, že 2+3=4 není teorém (v rámci nějakého rozumné formální aritmetiky; ta samozřejmě obsahuje logiku jako podsystém). Důvěra v identičnost obou vět je podmíněna důvěrou v konsistenci aritmetiky, předpoklad, který se pochopitelně v běžné debatě o aritmetice nenamáháme zdůrazňovat. Jak jsem již minule napsal, věci budou vypadat méně podivně, když místo „je pravda“ budeme říkat „je dokazatelné“, ale stále je dobré mít na paměti, že dokazatelnost non-X není totéž, co nedokazatelnost X: z dokazatelnosti non-X plyne nedokazatelnost X za předpokladu konsistence a z nedokazatelnosti X plyne dokazatelnost non-X za předpokladu úplnosti; nikdy ale nemáme oba předpoklady splněny najednou. Výhoda slova „dokazatelnost“ je ta, že nemá ty absolutní konotace, které jsou vlastní „pravdě“: cítíme, že pravda je jen jedna, zatímco dokazatelnost přirozeně může záviset na volbě axiomů. Chceme-li mluvit o pravdivosti výroků, musíme se ptát na pravdivost axiomů. Ale jak můžeme mluvit o pravdivosti něčeho, co závisí jen na naší libovůli?

S jediností pravdy souvisí ještě jedna otázka, a to: existuje jen jedna logika? Je logika univerzální, v tom smyslu, že jakákoli myslící entita musí používat stejnou logiku, jako my? Člověk bývá silně puzen ke kladné odpovědi; nakonec i teologové v debatách o všemohoucím Bohu zpravidla tak nějak předpokládají, že věmohoucnost je omezena logikou. Pohled na logiku jako formální systém naproti tomu navádí k většímu skepticismu. Abeceda, gramatika a odvozovací pravidla logiky nejsou — jak nakonec explicitně uvidíme v některém z dalších dílů —, zrovna příkladem nejjednoduššího či nejelegantnějšího formálního systému. Pravidla logiky nám připadají přirozená a, chtělo by se říct, logická; vypovídá to ale více o výjimečnosti logiky mezi formálními systémy, nebo spíš o architektuře lidského mozku a způsobu našeho uvažování? Koneckonců, neexistuje jediná Logika s velkým L: máme logiku výrokovou, predikátovou prvního řádu (ta má oproti výrokové logice navíc kvantifikátory), druhého řádu (umožňuje kvantifikovat výroky), třetího i vyšších řádů nebo modální. Druhy logiky se liší svou abecedou, gramatikou či odvozovacími pravidly. Proč tedy předpokládat, že mimozemšťané, vyvinuvší se v jiném prostředí, automaticky budou myslet způsobem isomorfním tomu našemu?

Pro postmodernistu, který čte tyto řádky s hřejivým pocitem vítězství („já to říkal celou dobu, logika je sociální konstrukt“): Předešlý odstavec není obhajobou epistemického relativismu ani Feyerabendova anything goes. Od tvrzení, že formální logika je model lidského uvažování (a tedy ne univerzální model jakéhokoli myšlení) je velmi daleko k závěru, že všechny modely myšlení jsou si rovnocenné. Klíčová je zde existence smysluplné interpretace, to jest korespondence mezi řetězci formálního systému a pozorovaným světem. Až Derrida, Lacan a spol. nabídnou alternativní formalizaci myšlení, která bude mít smysluplnou interpretaci, můžeme diskutovat o privilegovaném postavení klasické logiky a sociálně determinované epistemologii. Nečekám však, že by se dekonstruktivisté, poststrukturalisté a kontinentální filosofové vůbec k něčemu takovému odhodlali.

Lepším příkladem, než různé varianty logiky (které jsou spíš různými rozšířeními téhož, než alternativami navzájem) zde nakonec může být stará známá geometrie [*]. Nejstarší formalizovanou geometrií je ta Eukleidova; zde je původních pět postulátů, na kterých je postavena [*]:

  1. Mezi každými dvěma body lze jednoznačně narýsovat úsečku.
  2. Každou úsečku lze jednoznačně prodloužit na přímku.
  3. Ke každé úsečce existuje jedna kružnice, která má střed v jednom jejím konci a prochází druhým jejím koncem.
  4. Všechny pravé úhly jsou si rovny.
  5. K dané přímce a bodu, který na ní neleží, lze sestrojit právě jednu rovnoběžku, která prochází daným bodem.

Generace geometrů nebyly spokojeny s existencí pátého postulátu. Jeden z důvodů byl, že původní formulace pátého postulátu byla velmi neelegantní a nesamozřejmá: Jestliže přímka protíná dvě další přímky tak, že součet vnitřních úhlů na jedné straně první přímky je menší než dva pravé úhly, pak se dvě další přímky navzájem protínají právě na této straně. Zdálo se, že pátý postulát bude možné dokázat z prvních čtyřech. Koneckonců sám Eukleidés použil pátého postulátu v první knize svých Základů až při důkazu 29. tvrzení (z celkem 48). Pokusy dokázat pátý postulát ale byly všechny neúspěšné, a postulát si tak zachoval status axiomu. Neuspokojivý stav trval až do přelomu dvacátých a třicátých let devatenáctého století, kdy Nikolaj Lobačevskij a János Bolyai nezávisle „objevili“ neeuklidovskou geometrii. Slovo „objevili“ píši do uvozovek proto, že přinejmenším sférická geometrie musela být v tu dobu prakticky dobře známa přinejmenším mezi geografy — a bylo tomu tak již od dob antických. Zásluha Lobačevského a Bolyaiho spočívala v tom, že rozpoznali možnost formalizovat neplanární geometrii pomocí prvních čtyřech Eukleidových axiomů.

Po mnoho staletí tak lidé věřili, že existuje jedna automaticky správná formální geometrie, a tato víra se ukázala falešnou. Znamená to ale, že eukleidovská geometrie je pouhý sociální konstrukt? Zajisté ne. Existují i geometrie jiné, neeukleidovské, ale volba mezi užitím konkrétní geometrie není pouhá sociální konvence. Naopak, tato volba je dána praktickou potřebou: používat hyperbolickou geometrii při stavbě domu je pošetilé, stejně jako je pošetilé používat eukleidovskou geometrii při námořní navigaci na velké vzdálenosti.

Příklad různých geometrií je ilustrativní i jinak. Ukazuje, jakou sílu interpretace má při posuzování pravdivosti výroků. Jeden ze způsobů, jak bylo možné dokázat pátý Eukleidův postulát byl důkaz sporem: zkusme vzít jeho negaci za axiom a ukažme, že výsledný systém je nekonsistentní. Nekonsistenci se sice nedařilo nalézt, ale lidé po staletí věřili, že když se budou snažit dostatečně, jednou na nějakou narazí. Až v okamžiku, kdy se podařilo najít interpretaci geometrie obsahující negaci pátého axiomu, bylo rázem zřejmé, že nekonsistence neexistuje. Ač to nebylo formálně dokázáno — není zas tak jednoduché dokázat, že Lobačevského geometrie je konsistentní — bylo to zřejmé. Od systému se smysluplnou interpretací nekonsistenci prostě nečekáme.

Pátý postulát tedy není dokazatelný pomocí prvních čtyřech. Je ale pravdivý? Po tom, co bylo řečeno, je evidentní marnost takto položené otázky. Bez bližší specifikace významu pravdivosti není možno jednoznačně odpovědět. Pravdivost závisí na interpretaci, a interpretace geometrických pojmů „rovnoběžka“, „úhel“ či „bod“ se v různých geometriích liší. U abstraktních matematických výroků můžeme snadno mluvit o dokazatelnosti; pravdivost je mnohem subtilnější a nejasnější vlastnost.

pondělí 30. května 2011

Pondělní šifra XXXI.

Následující obrázek v sobě skrývá zašifrovanou tajenku, kterou může být slovo, výraz nebo věta dávající v češtině dobrý význam (může to být i vlastní jméno nebo cizí slovo, pokud je v češtině dostatečně často používáno). Způsob šifrování není předem specifikován, ale měl by být odhalitelný na základě relativně jednoduchých pozorování. V některých případech může být k rozluštění potřeba znalost Morseovy abecedy nebo Braillova písma.



pátek 27. května 2011

Jak spolehlivě zmást cestujícího


Představte si, že přijdete na zastávku trolejbusu, a místo jízdního řádu na místě visí pouze tabulka s informací, že linka 8 jede s intervalem 27 minut, zatímco linka 49 má interval 19 minut, o víkendu 23 minut. Pro jistotu vedle toho visí stejná tabulka, podle které v místě linka 49 vůbec nejede a osmička jezdí s intervalem 23 minut. Očekávali byste, že dopravce při umísťování nového seznamu linek aspoň sundá starou neplatnou tabulku? Zapomeňte na to a vítejte v Rusku.

Navzdory nekontrolovanému rozmachu automobilismu v Rusku existuje ne úplně špatný systém veřejné dopravy. Od cestujícího se ovšem čeká, že bude vědět, kudy, kam a jak chce jet. Informace se zpravidla nezveřejňují. Nejenže neexistuje (aspoň co já vím) nějaká analogie našeho Idosu [upřesnění - viz diskuse], kde by bylo možno z pohodlí domova automaticky dohledat nejrychlejší trasu. Informace nebývají ani na zastávkách: označník zastávky je malá tabulka visící na nejbližším vhodném drátě nebo sloupu a obsahující v lepším případě seznam linek a jejich intervaly. U tramvají navíc chybí nástupní ostrůvky, což z vystupování vprostřed čtyřproudé vozovky činí adrenalinový zážitek. Schéma sítě? Zpravidla až ve vozidle, jenže tam je většinou na volbu trasy už pozdě.

Příznivým faktem je to, že stanice a zastávky mají zpravidla svá jména. Nepříznivé jsou ale zvyklosti, které Rusové v pojmenovávání svých stanic mají. Přesvědčení, že jméno stanice by mělo být pro cestujícího co nejvíce informativní, je v Rusku zjevně exotickou výjimkou. Jeden z projevů této nepříjemné skutečnosti jsou názvy přestupních stanic metra [*]. Ve většině případů platí, že přestupní stanice má tolik jmen, kolik tras metra jí prochází. Jeden z důležitých přestupních uzlů v centru Moskvy se tak nazývá Borovickaja, jedete-li linkou 9, Arbatskaja (na lince 3), Aleksandrovskij sad (na lince 4) a Biblioteka imeni Lenina pro cestující linky 1. Paradoxně navíc existuje i stanice Arbatskaja na lince 4, z které ale není možný přestup do stejnojmenné stanice na lince 3.

Kuriózní situace vznikaly během vlny přejmenovávání v devadesátých letech. Zatímco některá místa ztratila svůj ideologický název z dřívějška, ne vždy se změna jména dotkla příslušné stanice. Pokud jste třeba chtěli dojet do Nižného Novgorodu, až do loňska byste museli hledat vlak, jehož cílová stanice se zove Gorkij, což byl název města v letech 1932-1990. (Dnes už se stanice jmenuje logicky Nižnyj Novgorod - Moskovskij vokzal.) Ne vždy lze podobné kuriozity vysvětlit změnou režimu, často jsou oba názvy (vesnice i nádraží) politicky napohled neutrální, a přesto různé. Poblíž Volgogradu je to téměř normou:

název sídla název stanice
Samofalovka Kotlubaň
Šurupovskij Kalinino
Frolovo Arčeda
Suchov Rakovka
Michajlovka Sebrjakovo
Troickij Kumylga
Novoanninskij Filonovo
Čerkesovskij Budarino
Novonikolajevskij Alexikovo


a tak dále [*]. Jinde pomáhají cestujícím v orientaci informativní názvy stanic typu „platforma 75. kilometr“, případně očíslovaná nádraží ve větších městech („Volgograd-II“).

Že vlaky z Moskvy do Petrohradu stále odjíždějí z Leningradského nádraží asi zmate málokoho. Zřejmě proto — aby se cestující nenudili — je na příslušné jízdence jako stanice odjezdu uvedeno МОСКВА ОКТ., zřejmě zkratka za jméno Okťjabrskij nebo Okťjabrskaja. Taková stanice ale v Moskvě není — tedy vlastně je, ale jezdí tam pouze metro, a navíc je to na druhé straně města. Stanice metra u Leningradského nádraží se jmenuje Komsomolskaja. Takové věci by ale přinejmenším Pražany překvapovat neměly: vždyť i my jsme měli stanici metra Moskevská (jak stylové) umístěnou pět kilometrů od stejnojmenné ulice.

Nejen bloudění je souzeno cestujícím. Další opatření, které má za účel zpříjemnit cestování, je nepřestupný tarif. Jedno, zda chcete jet jednu stanici nebo dvacet, cena je tatáž. Cesta na vzdálenost 1 km s přestupem stojí dvakrát tolik, co cesta na vzdálenost 20 km bez přestupu. Samozřejmě, i tohle u nás bylo, ale aspoň s jedním typem lístku na všechny druhy dopravy. Ne tak v Moskvě. I když jízdenky na tramvaj i metro stojí stejně, 28 rublů, není možné použít tramvajovou jízdenku v metru, ani naopak. Jistě, metro je provozováno jinou společností (Moskovskij metropoliten) než povrchová doprava (Mosgortrans), ale absurdita jde tak daleko, že jízdenky na metro nelze použít ani na moskevský monorail, i když oba systémy patří stejné společnosti a jízdenka stojí stejně a vypadá (téměř) stejně.

Když už je řeč o magnetických kartách: jelikož u tramvají а busů není možné instalovat turnikety na zastávku, prozíravě jsou umístěny uvnitř vozidel. Což znamená, že všichni musejí nastupovat předními dveřmi. Automaty na jízdenky prakticky neexistují (pár stanic metra má automaty, ale z těch lezou pouze jízdenky na metro), v trafikách se jízdenky neprodávají a kiosky s jízdenkami jsou vzácné. Náhodní cestující bez předplatních jízdenek jsou tak nuceni kupovat jízdenky u řidiče, a v kombinaci s povinným nástupem všech cestujících předními dveřmi to předvídatelným způsobem zpomaluje odbavení. (Mimo Moskvu jsou v tramvajích a autobusech průvodčí a tato komplikace tak odpadá.) Podobně efektivní systém funguje u dálkových vlaků: v každém vagónu jsou otevřeny pouze jedny dveře, u kterých číhá průvodčí a kontroluje jízdenky při nástupu. Člověk tak může nastoupit pouze do svého vagónu (dálkové vlaky jsou povinně místenkové). V expresu Moskva-Dubna, tvořeném jednotkou ED-4, se zpravidla otvírají troje dveře z dvanácti. Stalo se mi, že jsem měl jízdenku do pátého vozu, a protože dveře pátého vozu byly zavřené a před šestým byla fronta, zkusil jsem nastoupit přes čtvrtý vůz. Průvodčí mě ovšem odkázala do příslušných mezí: ačkoli je vlak vevnitř plně průchozí, s jízdenkou do pátého vozu lze nastupovat výhradně přes šestý vůz.

Užívání veřejné dopravy v Rusku tak člověka udělá otrlým vůči banálním komplikacím typu předběžně vyvěšených výlukových jízdních řádů, které nás matou v českých městech.

pondělí 9. května 2011

Pondělní šifra XXX.

Následující obrázek v sobě skrývá zašifrovanou tajenku, kterou může být slovo, výraz nebo věta dávající v češtině dobrý význam (může to být i vlastní jméno nebo cizí slovo, pokud je v češtině dostatečně často používáno). Způsob šifrování není předem specifikován, ale měl by být odhalitelný na základě relativně jednoduchých pozorování. V některých případech může být k rozluštění potřeba znalost Morseovy abecedy nebo Braillova písma.



čtvrtek 5. května 2011

Achillova noční můra


Tak trochu v rámci série článků o logice a formálních systémech, tak trochu mimo něj, bych se rád zastavil u dvou esejů, jejichž vznik od sebe dělí téměř sto let, a které přitom mají mnoho společného. Autorem prvního z nich je Lewis Carroll, matematik, který je spíše znám jako spisovatel (díky Bertrandu Russellovi, nositeli Nobelovy ceny za literaturu, není v této kategorii osamocen). Esej Co řekla Želva Achillovi je sice velmi známá, přesto se mi nepodařilo na internetu najít český překlad. Proto jsem vytvořil překlad svůj, který můžete nalézt [ZDE]; dáváte-li přednost originálnímu znění, text je k nalezení např. [TADY].

Carroll lehce nevážnou formou využívá běžného nedorozumění k vytvoření zdání paradoxu. Nedorozumění spočívá v nerozlišování mezi implikací jakožto logickým operátorem na jedné straně a odvozovacími pravidly logiky na straně druhé. Všichni víme, že přijímáme-li výroky A a A⇒B za pravdivé, musíme za pravdivý přijmout i výrok B. Toto pravidlo se zove modus ponens a občas celou sekvenci zapisujeme symbolicky, třebas takto:

A⇒B, AB.


Problém nastane v okamžiku, kdy se nám zachce nahradit nezvyklý symbol ⊢ obyčejnou implikací. Člověk pak napíše (A∧(A⇒B))⇒B, a platnost B odůvodní platností tohoto výroku. Ale proč vlastně platí (A∧(A⇒B))⇒B? Na tom Carroll staví zápletku své nedlouhé povídky.

Druhý esej pochází z pera logika Raymonda Smullyana a jmenuje se Epistemologická noční můra. Ačkoli značně novější, s překládáním jsem se namáhat nemusel; česká verze [ODKAZ] totiž vyšla v Pokrocích matematiky, fyziky a astronomie „již“ sedm let po svém vzniku, a to v roce 1989. Originál např. [ZDE]. Epistemologická noční můra je, podobně jako výše zmíněný Carrollův esej, napsaná formou rozhovoru. Po přečtení textu, jehož paradoxní efekt je vystavěn na důmyslné hře s autoreferenčními výroky a nekonečnými řetězci výroků, člověk ztratí značnou část důvěry v neprůstřelnou pevnost logiky.