středa 27. dubna 2011

Interpretace formálních systémů


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

V minulém čísle jsme zavedli formální systém, který operoval s řetězci sestávajícími ze znaků M, I a U. Některé z těchto řetězců mají status teorému. Na počátku obsahovala množina teorémů jediný řetězec (který nazýváme axiomem), konkrétně MI. Množinu teorémů jsme ale mohli rozmnožovat tak, že jsme ze stávajících teorémů vyráběli nové pomocí specifikovaných odvozovacích pravidel. Množina teorémů se tak může rozrůstat donekonečna, a tedy teorémů je nekonečně mnoho (zda je výraz teorémem samozřejmě nezávisí na tom, jestli již jej někdo odvodil, ale pouze na tom, jestli jej odvodit lze).

Množina teorémů je nekonečně velká, ale v žádném případě není každý výraz teorémem. Asi každý čtenář minulého dílu si všimnul, že všechny teorémy začínají na M. Odvozovací pravidla nejsou schopna počáteční M „zabít“: první dvě pravidla vedou k přidávání znaků na konec výrazu a třetí ubírá trojice III. Pokud všechny axiomy mají M na počátku, jakože mají (tedy vlastně bych měl napsat „axiom má“, když je pouze jeden), tak všechny teorémy musí taktéž mít M na začátku. Podobně je patrné, že žádný teorém nebude mít M uprostřed nebo na konci. Můžeme tak s jistotou říct, že kupříkladu řetězce UUIU nebo MIM nejsou teorémy. Jak to ale je s řetězcem MU, na jehož status jsem se ptal v závěru minulého dílu? Ukazuje se, že ani MU není teorémem, i když uvidět to je o něco složitější, než v případech výrazů UUIU a MIM. Klíčové pozorování se týká počtu I uvnitř teorémů: odvození pravidlem I tento počet nechává beze změny, pravidlo II počet I zdvojnásobuje a pravidlo III jej snižuje o 3. Označme písmenem z zbytek po dělení počtu íček třemi. Pravidla I a III nechávají viditelně z beze změny. Jednoduchá úvaha prozradí, co se děje při odvozování za pomoci II. pravidla: je-li z = 0 pro původní teorém, je i z = 0 pro nově odvozený teorém; má-li původní teorém z = 1, nový má z = 2; a nakonec, má-li původní teorém z = 2, nový má z = 1. Jediný počáteční teorém má z = 1, a proto všechny teorémy budou mít buď z = 1 (pokud jejich odvození z počátečního axiomu zahrnuje sudý počet užití II. pravidla) nebo z = 2 (když odvození zahrnuje lichý počet užití tohoto pravidla). Výraz MU ale má z = 0, a tak nemůže být teorémem.

Předchozí úvahy mají jedno společné: dívají se na systém zvnějšku, s užitím dedukce, která není svázána třemi striktními pravidly systému MIU. Stroj, který by „dedukoval“ pouze v rámci systému MIU, by nikdy nezjistil, že MU není teorémem. Jediné, co tento stroj může dělat, chce-li zjistit, jestli MU je teorém, je aplikovat odvozovací pravidla na stále rostoucí množinu teorémů a doufat, narazí na MU. Pokud by se tak stalo (teď už víme, že k tomu dojít nemůže, ale připusťme to hypoteticky — nebo si představme na místě MU jiný řetězec, jehož teorémovost nám není známa), stroj by si „byl jist“, že výraz je teorémem. Při tomto postupu si ale nikdy nemůže být jist tím, že MU teorémem není, protože nikdy nemůže vyzkoušet všech nekonečně mnoho postupů odvozování a vyloučit tak, že žádný z nich nakonec nevyprodukuje MU.

K úvaze o rozdílné povaze teorémů a neteorémů se ještě vrátíme, ale předtím zavedu další Hofstadterův systém, který oproti systému MIU obsahuje dvě složky navíc: gramatiku a interpretaci.

Systém PR

Abeceda systému PR obsahuje tři znaky: P, R a -. Na rozdíl od předchozího systému, ve kterém jakýkoli řetězec byl přípustným výrazem, máme zde gramatické pravidlo: řežezec systému PR je dobře formovaný, obsahuje-li právě jedno P a právě jedno R, R leží vpravo od P, a nakonec ani P, ani R nestojí na kraji řetězce nebo těsně vedle sebe. Tudíž například -----P-R- nebo --P--R-- jsou dobře formované výrazy, zatímco R-P nebo -P-PP---R- nikoli. Dále máme k dispozici jediné odvozovací pravidlo:

  1. Je-li XPYRZ teorém, pak XPY-RZ- je také teorém.

Kupříkladu kdybychom věděli, že ----P-R- je teorém, pak bychom totéž mohli říct i o ----P--R--.

Skutečnost, že existuje pouze jedno odvozovací pravidlo, je svým způsobem vyvážena tím, že existuje nekonečně mnoho axiomů. Jinak řečeno, místo konečného systému axiomů máme k dispozici tzv. axiomové schéma, které zní takto: Každý dobře definovaný výraz tvaru XP-RX- je axiom. Podřetězec X zde může být libovolný (podmínka dobré definovanosti celého výrazu ve skutečnosti vede k tomu, že X stojí za úvahu jen pokud neobsahuje P ani R), a tak je axiomů nepřeberné množství. Nejjednodušším axiomem je zjevně -P-R--.

Pro názornost si teď můžete zkusit odvodit teorém --P---R-----; řešení je v poznámce [1].

Minule bylo řečeno, že interpretace formálního systému je návod, jak přiřadit symbolům či podřetězcům dobře definovaných výrazů vyjádření přirozeného jazyka, přičemž by mělo platit, že pravdivým výrokům přirozeného jazyka odpovídají teorémy formálního systému. Můžeme teď zkusit interpretovat systém PQ. Což tedy zkusit tuto interpretaci:

  1. Každou maximální nepřerušenou řadu pomlček nahradíme číslovkou označující její délku. To jest - překládáme jako „jedna“, -- překládáme jako „dvě“ atd. Přívlastkem maximální chci říct, že musíme vždy vzít nejdelší nepřerušený řetězec mezer: z výrazu ---P-R-- nelze sestrojit částečný překlad „jednadva“P„jedna“R„dva“, ale pouze „tři“P„jedna“R„dva“.
  2. Symbol P nahradíme řetězcem „ plus “.
  3. Symbol R nahradíme řetězcem „ rovná se “.

Teorému --P---R----- pak odpovídá interpretace „dva plus tři rovná se pět“, což je zcela jistě pravdivý výrok. Po vyzkoušení několika dalších teorémů se ukáže, že jejich interpretace jsou také pravdivé — nakonec jste si pravděpodobně všimnuli, že ve všech teorémech je počet pomlček vlevo od R stejný, jako počet pomlček vpravo od R, a odtud je jen krůček k poznání, že uvedená interpretace je skutečně správná. Zdá se tedy, že systém PR lze použít pro popis sčítání kladných celých čísel. Gramatika systému zde pomáhá k tomu, aby po interpretaci vznikl smysluplný výrok: interpretace všech dobře formovaných výrazů jsou korektní české věty. Pozor ovšem na to, že to nefunguje opačně, tj. ne všechny smysluplné české věty o sčítání lze zapsat jako výrazy systému PR. Například „dva plus tři se rovná jedna plus čtyři“ je smysluplná věta, dokonce pravdivá, ale řetězec --P---R-P---- není dobře formovaný výraz systému PR. To pochopitelně neznamená, že nemůžeme vhodným způsobem systém PR rozšířit, aby umožňoval i výrazy tohoto typu. Jakmile ale jednou stanovíme pravidla formálního systému, musíme se jich strinktně držet, i když nám interpretace napovídá možnost jejich obejití.

Již od časů Eukleida bylo formální odvozování ideálem matematického důkazu, a dnešní matematika je vystavěna jako formální systém. Pro důkazy běžných tvrzení není potřeba klesat až na úroveň manipulací s řetězci znaků, a pro formulaci matematických vět se tak užívá upravená verze normálního jazyka. Víme ale, že v případě potřeby lze matematická tvrzení redukovat na řetězce určitého formálního systému, a jejich důkazy na posloupnost přesně specifikovaných elementárních kroků. Dokazovat složitější tvrzení na úrovni formálních systémů by bylo stejně nepohodlné jako tvořit webové stránky v assembleru, obojí ale je v principu možné.

Systém PR není zrovna nejlepším nástrojem pro formální popis sčítání, ale to neznamená, že nefunguje. Mohli bychom jej proto použít pro důkazy jednoduchých aritmetických tvrzení typu „37+62=99“. Matematikové používají k formalizaci aritmetiky o něco složitější systémy, ale duch v nich prováděných odvození je podobný, čtenář si tak může již nyní učinit určitou představu o tom, oč vlastně šlo ve slavném Russellově a Whiteheadově důkazu tvrzení „1+1=2“ (bez jasné představy o povaze formálních systémů jsem míval značné potíže pochopit, co je na „1+1=2“ možné dokazovat).

S formálním dokazováním tvrzení přirozeného jazyka je spjat filosofický problém. Na začátku tvorby libovolného formálního systému, který později zamýšlíme interpretovat, se snažíme zformalizovat nějakou sadu pravdivých tvrzení a najít několik málo pravidel, pomocí kterých lze tuto sadu rozšiřovat. Ukáže-li se, že rozšířená sada obsahuje pouze pravdivé výroky, uznáme nakonec, že systém plní svou funkci. Jak si ale můžeme být jisti, že všechny teorémy systému mají pravdivou interpretaci? A pokud si tím nemůžeme být jisti, jak můžeme fakt, že nějaký výraz je teorémem zvoleného systému, považovat za důkaz toho, že jeho interpretace je pravdivý výrok? Co když odvodíme teorém, jehož interpretace se bude jevit intuitivně nepravdivou? Máme věřit intuici a odvrhnout systém, nebo naopak důvěřovat systému a ignorovat intuici? Věc je komplikována tím, že pravdivost převážné většiny formulovatelných výroků není nijak intuitivně zřejmá, a pro její posouzení se musíme obrátit k víceméně formálnímu odvozování. Zůstaneme-li u jednoduchých výrazů pro sčítání: abychom zjistili, zda výrok „3775489 + 254563 = 4030052“ je pravdivý, musíme na levou stranu rovnosti aplikovat naučený algoritmus zvaný sčítání, který se znaky řetězce operuje přesně daným způsobem (nebo tuto povinnost delegovat na kalkulačku). Zdá se, jakoby formální systém, zde vtělený do postupů, které se každý naučí ve druhé třídě, v podobných případech pravdivost výroku definoval. A přesto, můžeme si snadno vymyslet formální systémy generující nepravdivé výroku — ba dokonce by asi nebylo tak těžké zařídit, aby takový nepravdu generující systém měl axiomy a odvozovací pravidla, na kterých by na první pohled nebylo vidět nic závadného.

Poučení z předchozího odstavce je, že, kdyby nic jiného, je jednodušší a bezpečnější mluvit o teorémech a neteorémech, než o pravdách a nepravdách. Pro teorémy ale nemusí platit všechna omezení, která očekáváme u pravdivého výroku. Zejména, obsahuje-li náš systém znak ¬ interpretovaný jako negace, ze skutečnosti, že ¬X je teorém ještě neplyne, že X teorém není, a naopak též ne. Může se stát, že nějaký dobře formovaný výraz X z počátečních axiomů nelze vyvodit, a zároveň ani nelze vyvodit ¬X. Výraz X je potom v rámci tohoto systému nerozhodnutelný, a systém obsahující nerozhodnutelné dobře formované výrazy se nazývá neúplným. Nebo se může stát i to, že naopak odvodíme jak X, tak ¬X. Jestliže k tomu dojde, říkáme, že daný systém je nekonsistentní. Nekonsistence ovšem neznamená, že náš systém nelze užívat jako formální systém; z formální stránky je vše v pořádku, nekonsistence je problematická pouze kvůli zvolené interpretaci. (Na druhou stranu, aspoň pro standardní verze logiky má nekonsistence destruktivní následky, protože umožňuje snadno odvodit každý výraz jako teorém, a systém, ve kterém je každý dobře formovaný výraz teorémem, zjevně nenaskýtá velký praktický užitek.)

Jak neúplnost, tak i nekonsistence se zdají být vadou na kráse formálních systémů. Dlouholetý ideál matematiků byl vytvořit teorii, ve které by každý matematický výrok byl dokazatelně buď pravdivý nebo nepravdivý; přeloženo do formálnějšího jazyka, kde by pro každé dobře formované X bylo buď X samotné, nebo jeho negace ¬X, teorémem. Gödel ukázal, že tohoto cíle nelze dosáhnout. V dalších dílech se na tuto nemožnost podíváme detailněji.


Poznámky:
1. Jediný možný postup:

  1. --P-Q--- (axiom, vyhovuje schématu XP-RX-)
  2. --P--Q---- (z 1. pomocí pravidla I.)
  3. --P---Q----- (z 2. pomocí pravidla I.)

pátek 22. dubna 2011

Formální systémy


Toto je první 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říští díl.

Pod logikou si obvykle představujeme disciplínu zkoumající zásady, kterými se musí řídit myšlení, má-li si nárokovat spolehlivost. V historii existovaly různé přístupy k logice. Po dlouhou dobu byly populární aristotelské sylogismy, které stanovovaly, jaké operace je možno provádět s některými množinovými výroky. Kanonický příklad sylogismu je toto odvození:

  1. Všichni savci jsou zvířata.
  2. Všechny krávy jsou savci.
  3. Některé krávy jsou zvířata.

V každém sylogismu třetí výrok plyne z prvních dvou. Sylogismus uvedený výše je platný [*]. Jiný příklad sylogismu, tentokráte neplatného:

  1. Všichni savci jsou zvířata.
  2. Všechny krávy jsou zvířata.
  3. Některé krávy jsou savci.

Sylogismus je neplatný navzdory tomu, že všechny tři výroky jsou pravdivé. Neplatnost znamená, že nahradíme-li krávy, zvířata a savce jinými kategoriemi, může se stát, že první dva výroky budou pravdivé, zatímco třetí nikoli. Platnost sylogismu je vlastností jeho struktury, nikoli věcí, o kterých sylogismus mluví. Z tohoto důvodu je vhodné použít abstraktnější symbolickou notaci, která dá lépe vyniknout logické struktuře. Dnes by člověk první sylogismus zapsal třeba takto:

  1. ∃x:K(x)
  2. ∀x:S(x)⇒Z(x)
  3. ∀x:K(x)⇒S(x)
  4. ∃x:K(x)∧Z(x)

Symbol S(x) reprezentuje výrok „x je savec“, nicméně platnost sylogismu nezávisí na této interpretaci. Nultý výrok je doplnění nevyjádřeného předpokladu, že existuje aspoň jedna kráva.

Středověký způsob nakládání se sylogismy byl v jistých ohledech velmi těžkopádný. Existuje 256 typů různých sylogismů (které dostaneme z našeho prvního různým prohazováním pozic krav, savců a zvířat a záměnami slov „některé“, „všechny“ a „žádné“) z nichž pouze 24 je platných, a středověký logik jednoduše memorizoval těchto 24 variant, obvykle s užitím určitých mnemotechnických pomůcek (detaily viz článek na anglické Wikipedii). Z dnešního pohledu se takový přístup zdá absurdní. Místo memorizace čtyřiadvaceti schémat platných sylogismů si pamatujeme, jaké operace je možné činit s logickými symboly. Například víme, že implikace je transitivní, což znamená, že platí-li A⇒B a zároveň platí B⇒C, pak platí i A⇒C, díky čemuž z 1. a 2. odvodíme ∀x:K(x)⇒Z(x). Pomocí jiných povolených operací pak z tohoto mezivýsledku a nulté premisy ∃x:K(x) lze odvodit hledaný čtvrtý výrok.

Formální systémy

K sepsání seznamu povolených operací v predikátové logice se ještě dostanu v některém z příštích dílů; v tuto chvíli je to nepříliš podstatné. Podstatná je ale idea, že logická dedukce má strukturu operací s řetězci znaků, které (ty řetězce) sice je možno interpretovat jako tvrzení přirozeného jazyka, ale které (ty operace) nezávisí na této interpretaci. Logika je příklad formálního systému. Základem formálního systému je jeho abeceda, což je množina symbolů, z kterých postupně budeme sestavovat řetězce. Ve výše uvedených příkladech jsme konstruovali řetězce predikátové logiky s užitím symbolů , , , , :, (, ), x, K, S a Z. Tyto symboly jsou součástí abecedy predikátové logiky (ta obsahuje i další symboly, které se v příkladech výše nevyskytují). Symboly abeced formálních systémů budu vždy psát tučně. Řetězce těchto symbolů pak tvoří výrazy formálního jazyka.

Lze si představit formální systém, který připouští jakékoli řetězce (a zanedlouho jeden takový zavedeme), ale většina formálních systémů podrobuje své řetězce určitým omezením, která tvoří gramatiku formálního jazyka. Ve výrokové logice například nemůže znak stát na začátku výroku, počet závorek ( musí být roven počtu ) atd. Řetězec ⇒)Kx::Z gramatice nevyhovuje, jinak řečeno, není dobře formovaným výrazem. Některé dobře formované výrazy mají status teorému. Má-li formální systém vhodnou interpretaci, dobře formované výrazy odpovídají smysluplným tvrzením přirozeného jazyka, zatímco teorémy by měly odpovídat pravdivým tvrzením. Tak tomu samozřejmě je v logice: příkladem teorému je výraz A⇒A (s interpretací „jestliže platí A, pak platí A“; tato interpretace je pouze částečná, protože jsem nechal neinterpretovaný symbol A, nicméně pravdivost je zřejmá i tak), zatímco příkladem dobře formovaného výrazu, který není teorémem, je A∧¬A („platí A a zároveň neplatí A“). Formální systémy se ale obejdou i bez interpretace, a v tom případě teorémy jsou prostě určitou podmnožinou dobře formovaných výrazů. K definitivnímu určení formálního systému je tudíž potřeba určit způsob, jak odlišit teorémy od neteorémů.

Hledanými posledními přísadami do formálního systému jsou axiomy a odvozovací pravidla. Axiomy jsou výrazy, které získávají čest být teorémem zdarma, v rámci definice formálního systému. Odvozovací pravidla jsou potom přísně specifikované postupy, jak z teorémů vytvářet další teorémy. Jeden z axiomů výrokové logiky je A⇒(B⇒A). Příkladem odvozovacího pravidla je modus ponens, formulovaný následovně: pokud X je teorém a zároveň XY je teorém, pak Y je teorém. (Všimněte si, že X a Y zde nejsou jednotlivé symboly z abecedy výrokové logiky, ale libovolné řetězce; proto je nepíšu tučně, ale kurzívou.) Kdybychom měli ještě jeden axiom, konkrétně A, mohli bychom modus ponens užít k odvození teorému (B⇒A).

Ačkoli různé verze a nadstavby logiky jsou nejdůležitějšími příklady formálních systémů (a vlastně i důvodem, proč nás vlastně formální systémy zajímají), pro ilustraci základních ideí se příliš nehodí. Jedním důvodem je jejich relativní složitost, a druhým je existence interpretace. Logiku užíváme dnes a denně pro řešení bežných problémů života, a máme k tomu vyvinuté efektivní intuitivní myšlení. To ale svádí k různým zkratkovitým manipulacím a posuzování výrazů formální logiky na základě jejich interpretace. Pro běžné aplikace (kam spadá vše od úvah typu „soused je katolík, každý katolík je křesťan, tudíž soused je křesťan“ až po dokazování Banachovy věty o pevném bodě) je to naprosto dostatečné. Chceme-li ale zkoumat logiku samotnou, musíme se držet striktně formálních postupů, a to vyžaduje určitý tréning. Z toho důvodu Hofstadter v úvodu své knihy zavádí poměrně jednoduchý formální systém, který nemá žádnou očividnou interpretaci.

Systém MIU
Abeceda systému MIU sestává, jak by se nakonec podle názvu dalo čekat, ze tří symbolů: M, I a U. Jak jsem již avizoval o tři odstavce výše, tento systém nemá žádná gramatická pravidla: libovolný řetězec sestávající ze znaků M, I a U, například M nebo třeba UUIMUUMU, je dobře formulovaným výrazem. Odvozovací pravidla jsou tři:

  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.)

No a konečně, zbývá zadat axiomy. Lépe řečeno axiom, protože je pouze jeden: MI

Použitím prvního a druhého pravidla můžeme z axiomu odvodit okamžitě dva teorémy: MIU a MII. Možnosti odvozování tím ale samozřejmě nekončí, můžeme postupovat ve více krocích a konstruovat libovolně dlouhé teorémy. Kupříkladu můžeme odvodit teorém MIUUIUU, a to třeba takto:

  1. MI (axiom)
  2. MII (z 1. s užitím pravidla II)
  3. MIIII (z 2. s užitím pravidla II)
  4. MIIIIU (z 3. s užitím pravidla I)
  5. MIUU (z 4. s užitím pravidla III)
  6. MIUUIUU (z 5. s užitím pravidla II)

Všechny řetězce získané v mezikrocích jsou samozřejmě také teorémy.

Samozřejmě můžeme strojově aplikovat zadaná odvozovací pravidla v libovolném pořadí a vršit nekonečný seznam teorémů; půvabu v této činnosti moc není. O poznání zajímavější se věc stane v momentě, kdy si začneme klást otázky typu: „je MIUUIUU teorém?“ Pro MIUUIUU odpověď známe, ale zkuste to na moment zapomenout. Jak byste postupovali? Evidentně můžete zkoušet odvozovat různé teorémy a doufat, že narazíte na MIUUIUU. Takovou činnost lze aplikovat systematicky: nejdřív vyzkoušíte všechna jednokroková odvození, pak dvoukroková, tříkroková a tak dále, a mezi pětikrokovými nakonec narazíte na výše uvedené a vyprodukujete hledaný řetězec. Takový postup by byl ovšem velmi zdlouhavý, protože počet n-krokových odvození roste geometricky s n. A co hůře, na začátku nevíte, že nejkratší [*] odvození MIUUIUU má pět kroků. Mohlo by jich mít sedmdesát, nebo třeba milion.

Stejně jako matematikové při dokazování matematických vět slepě systematicky neprohledávají všechna možná odvozování a stejně jako šachisté při hledání nejlepší hry strojově neprocházejí všechny varianty tahů povolených v pravidlech, i pro odvozování v systému MIU si lze vypěstovat cit. Mělo by to být výrazně jednodušší, než vypěstovat si cit pro šachy nebo matematiku, protože MIU je výrazně jednodušší než šachy a matematika. Svůj cit pro systém MIU si můžete vyzkoušet při řešení problému, který Hofstadter předkládá svým čtenářům: Je MU teorém? K odpovědi se dostanu v dalším díle — jestli si chcete zkusit problém vyřešit samostatně, máte na to dost času.

úterý 19. dubna 2011

Смоленск, вторая часть

Pár kilometrů západně od Smolenska leží katyňský památník, připomínající masakr více než čtyř tisíc polských důstojníků a poddůstojníků zajatých sovětskou armádou po obsazení východní části Polska v roce 1939. Památník, jehož hlavní částí je vojenský hřbitov, vznikl v roce 2000 a je hojně navštěvován především Poláky. Součástí areálu jsou ale i hroby sovětských občanů zabitých NKVD v témže místě v průběhu stalinských čistek.









K Polsku je Smolensk vázán nejen vzpomínkou na katyňský masakr. Ke starší historii patří události sedmnáctého století, kdy Poláci Smolensk dobyli po dvouletém obléhání (v roce 1611), a udrželi ho i přes ruský pokus o znovudobytí ztraceného území v tzv. Smolenské válce v roce 1632. Město se vrátilo do ruských rukou až roku 1654.





A nakonec pár žánrových obrázků, které nemají nic společného s Polskem.







pondělí 18. dubna 2011

Смоленск, первая часть

Po umístění myši nad fotografii se zjeví příslušný popisek.


Smolensk je třísettisícové město nedaleko běloruských hranic, a jedno z nejstarších a historicky nejvýznamějších měst Ruska. Strategická poloha města předurčila jeho historii plnou bitev. O Smolensk se bojovalo v mnohých válkách polsko-ruských, během Napoleonova tažení i dvakrát za druhé světové války. Vojenská historie ovlivnila i architekturu města: jednak zachovaným barokním opevněním, které je svým rozsahem v rámci Ruska jedinečným, a jednak architekturou centra, které bylo nově vystavěno po zničení v průběhu napoleonských bitev. Město bylo znovu prakticky zničeno v Druhé světové válce, poválečná obnova ale zachovala historický charakter centra.





Klasicistní architektura centra přechází plynně do typicky ruského neladu předměstských čtvrtí plného neudržovaných domů a nezastavěných proluk. Dále od centra se dostanéme do panelákových džunglí nebo vesnické zástavby. Pozitivním rysem je spousta zeleně. Přesto, na městě je vidět, že nepatří mezi nejvíce prosperující ruské regiony. Ekonomické problémy byly spojeny mimo jiné s úpadkem leteckého průmyslu v devadesátých letech; rozsáhlý areál leteckých závodů na severu města je dnes využíván pouze částečně. Minulost leteckého strojírenství připomínají dva památníky, které jsem bohužel nestihl vyfotit, proto jen externí odkazy: Tu-16 na ulici Bagrationa, Jak-42 na křižovatce ulic Kutuzova a Frunze.





Jako ve většině ruských měst, i ve Smolensku stojí bezpočet pomníků, památníků, pamětních desek i jiných objektů připomínajících historii. Místní historie obsahuje mnoho momentů hodných připomenutí, a nejpopulárnější je zřejmě Napoleonovo tažení. K jižnímu opevnění přiléhá skver Pamjati gerojev s bustami ruských generálů Vlastenecké války roku 1812.





O pomníky není nouze obecně, následuje několik vybraných:









Ve Smolensku jsou v provozu čtyři tramvajové linky na nepříliš kvalitních tratích. Historie tramvajové dopravy čítá přes sto let. Původní systém na metrovém rozchodu byl po Druhé světové válce přestavěn na standardních ruských 1524 mm. V devadesátých letech přišel, podobně jako v dalších městech v Rusku, úpadek tramvajové dopravy způsobený nedostatkem údržby vozidel a oprav tratí; obojí je v mizerném stavu, což nepřispívá ani k rychlosti, ani k pohodlí. V roce 2000 byla zrušena trať na Sovětské ulici a loni na podzim skončil provoz na prospektu Gagarina. Místní podnik sice v posledních letech nakoupil několik nových vozů KTM-23, budoucnost tramvají ale zůstává nejistá.








čtvrtek 14. dubna 2011

Etymologický zpravodaj - L


Dnešní nabídka etymologií bude poněkud bohatší, než obvykle. Na řadě jsou slova líh, louh, lék, lektvar, lord, lady a lyceum.

I když jsou to docela odlišné substance, líh i louh za svůj název vděčí německému Lauge (ve významu "louh"), jež má společný původ s latinským lavare = mýt. Koneckonců louh hraje významnou roli při výrobě mýdla a líh se také dá používat pro čištění, ačkoli pochybuji o tom, že tato souvislost se dá využít pro vysvětlení příbuznosti slov. Společný původ názvů pro líh a louh je specifický pro češtinu a dává vzniknout nepříjemné představě o povaze staročeských lihovin [1].

Pokud po přečtení předchozího odstavce očekáváte, že i slova lék a lektvar mají stejný původ, mýlíte se. Lektvar není české slovo odvozené z lék a var (případně tvar), jak by se mohlo zdát, ale pochází z latinského electuarium = výběr (myslí se výběr léčivých substancí), odvozeného z electus = vybraný, ze slovesa legere = sbírat (ale taky číst). Příbuzná slova jsou selekce nebo elita. Oproti tomu slovo lék je z germánských jazyků, kde se ovšem dodnes nedochovalo, a původně asi od Keltů: irsky lia (ve starém pravopise liaigh) = lékař.

Slovo lord není sice úplně typicky české slovo, nicméně v etymologickém slovníku má svoje heslo. Zaujalo mě proto, že jeho původ zdaleka nenaznačuje jakoukoli vznešenost. Lord je zkrácenina středoanglického hlaford (čti s [-v-] uprostřed), což je ze staroanglického hlāfweard = hospodář, doslova ale strážce chleba. Hlāf (dnes loaf = bochník) je celkem průhledně příbuzné s českým chléb, weard má dnes podoby ward či guard, přičemž druhá vznikla zpětným přejetím z francouzštiny, která přejala původní germánský výraz [2]. Obdobně jako lord, i ženský protějšek lady pochází od chleba, původní podoba je hlāfdīge nebo hlāfdæge. Druhá část znamenala služka, ještě dříve zadělávačka těsta a souvisí s angl. dough = těsto, doughnut = kobliha a také s českým díže.

Lyceum, respektive v řecké podobě Λυκειον, bylo původně názvem místa, ve kterém učil Aristoteles. Název pocházel od nedalekého chrámu Appolóna Lýkeia, kde přízvisko Lýkeios pochází zřejmě od lýkos = vlk. Je pravděpodobné, že řecké λυκος a české vlk sdílejí společný původ, spolu s německým Wolf a latinskými lupus a vulpes (druhé ovšem znamená liška).


Poznámky:
1. Ani louh není zcela bez využití v potravinářství, specielně ve Skandinávii, kde se s jeho pomocí připravuje specialita zvaná lutefisk (doslova "louhová ryba").
2. Podobná dvojice podobných anglických slov je warranty / guarantee = záruka. Hláska w se ale vyskytovala jako varianta ke g i v severofrancouzských dialektech, takže i anglická slova s w mohou mít ryze francouzský (respektive normanský) původ (např. wardrobe = šatní skříň souvisí se slovem garderoba.

středa 6. dubna 2011

Gödel, Escher, Bach a výuka matematiky


Nikdy jsem neměl rád učebnice matematiky. Mluvím teď hlavně o učebnicích vysokoškolských, protože ty středoškolské si už moc jasně nevybavuji a základoškolské vypadly z paměti téměř dokonale. Nepamatuji si ale ani na to, že bych v té době byl jejich obsahem nějak nadšen, takže moje úvodní tvrzení pravděpodobně platí obecně.

Matematika je exaktní disciplína. Síla matematiky spočívá z poloviny ve formálním a přesném dokazování a z poloviny v úsporné symbolice. Výrok o matematických objektech je buď pravdivý nebo nepravdivý; ať už platí první nebo druhé, fakt je to absolutní a pevný jako papežova víra a (na rozdíl od papežovy víry) se k němu dá dojít sekvencí dobře definovaných kroků, které často můžeme reprezentovat manipulacemi s přesně definovanými symboly. Řekneme třeba, že „v separabilním prostoru je každá kompaktní množina omezená a uzavřená“. Pokud je to pravda, pak existuje postup, jak z definic klíčových pojmů (např. „separabilní prostor“, „kompaktní množina“) a sady axiomů či předem dokázaných tvrzení jednoznačně ukázat, že tomu tak je. Jestliže to tak není, můžeme zpravidla najít stejně jednoznačný protipříklad.

Tato síla matematiky jakoby určovala strukturu matematických textů. Běžná učebnice matematiky je strukturována stylem definice — věta — důkaz. Monotónní sekvence vět a důkazů jsou občas přerušeny příkladem, krátkým komentářem nebo odkazem na další literaturu; některé jednodušší důkazy jsou „ponechány jako cvičení pro čtenáře“ (jak já tohle nenávidím). Postupně se tak z několika málo prvotních axiomů deduktivně odvodí celá rozsáhlá teorie. Má se za to, že struktura matematiky mluví sama za sebe, a delší sekvence textu, vysvětlování či ilustrace jsou nehodné matematikova času. Jak říkal jeden z přednášejících na MFF: „Nejlepší obrázek je rovnice“.

Přesná a úsporná dedukce je jistě hlavní předností matematiky — ba možná její jedinou předností. Je jistě fascinující, jak z devíti jednoduchých axiomů Peanovy aritmetiky lze odvodit každý fakt o přirozených číslech, a z pěti Euklidových axiomů plyne každá, byť sebesložitější, věta v planimetrii. Problém je, že ve většině případů je deduktivní výstavba matematické teorie dost mizerným způsobem, jak matematiku učit.

Vezměme třeba Fourierovu analýzu. Když budu chtít celou teorii popsat v co nejkratším čase, pravděpodobně začnu s definicí Fourierovy transformace [*]



a poté začnu odvozovat, jaké vlastnosti tato operace má. Zbyde-li po dokázání třiceti vět a sedmnácti lemmat nějaký čas, zmíním praktické aplikace.

Prakticky každému, kdo se s takovým postupem setká poprvé, vytane na mysli otázka: proč? Proč je Fourierova transformace definována zrovna tak? Na což přednášející zpravidla odpoví „protože se to časem ukáže užitečným“ a autor knihy neodpoví nijak, poněvadž knize nelze zadávat dotazy... Koneckonců definice nemůže být nepravdivá a nelze ji tudíž dokázat ani vyvrátit. S čímž je tuto otázku možné zapudit z mysli. Potíž je, že s otázkou je obvykle zapuzena i značná část zájmu o příslušnou matematickou teorii [1].

Neříkám ani tak moc to, že výklad má začít defilé praktických aplikací. Výklad má spíš probíhat tak, aby každý další krok se zdál být přirozeným; aby při nové definici člověk neprožíval pocit naprostého překvapení. Praktické aplikace nebývají zdaleka tak efektivní, jako koncepčně jednoduchý abstraktní důvod. „Je potřeba umět odmocňovat záporná čísla“ mi na střední škole připadalo být mnohem přesvědčivější motivací pro zavedení komplexních čísel než „elektroinženýři je používají pro počítání se střídavým proudem“. Definici Fourierovy transformace tak má předcházet výklad diferenciálních rovnic a lineární algebry, analogie s rozkladem vektoru do bází a podobně. Netvrdím pochopitelně, že učebnice Fourierovy analýzy tyto aspekty vždy ignorují. Přesto jsem při čtení matematických textů zpravidla míval pocit, že intuitivním argumentům a skutečnému vysvětlování je věnováno příliš málo prostoru, že poměr textu a vzorců v matematických textech je příliš silně vychýlen ve prospěch vzorců. Může to být proto, že psát dlouhé vysvětlení znamená práci navíc pro autora a papír navíc pro vydavatele; lze se na to dívat tak, že dlouhé pasáže textu nepřidávají novou informaci a dokonce negují výhody stručné matematické notace. Nebo je to proto, že mnoho intuitivně přesvědčivých argumentů není přísně vzato pravdivých (respektive jsou nepřesné, a jejich zpřesnění by šlo na úkor intuitivní přesvědčivosti) a matematik má zábrany takové argumenty použít.

Uvědomuji si samozřejmě, že moje preference pro zdlouhavá vysvětlování nemusí být zcela univerzální, a že pravděpodobně existují lidé, kteří preferují matematické knihy, v nichž nejdelší sekvence psané přirozeným jazykem jsou „z čehož plyne“ a „což jsme měli dokázat“. Dokonce předpokládám, že mé představy o ideálním stylu výkladu jsou anomální, usuzuje z toho, že již píši osmý odstavec, aniž bych se stále dostal k hlavnímu tématu článku, který má být recenzí na knihu.

Gödel, Escher, Bach je kniha o matematice a její autor, Douglas Hofstadter, je matematik. Přesto nemá prakticky nic společného s učebnicemi matematiky tak, jak je známe. Vlastně nemá moc společného s jakoukoli jinou knihou, kterou jsem kdy měl možnost vidět (pravda, nemluvím zde z pozice příliš sečtělého člověka). Je obtížné GEB, jak se název zpravidla zkracuje, klasifikovat do ustálených škatulek literárních žánrů — jak jsem již napsal, není to učebnice, nejsme-li ochotni totálně změnit vnímání významu toho slova, není to beletrie, nezapadá ale ani do kategorie literatury faktu, kam by se dala zařadit většina populárně vědeckých publikací. Snad se dá říct, že GEB je próza, i když si umím představit argument i proti této klasifikaci. Aby toho nebylo málo, Hofstadter popírá, že GEB je primárně o matematice...

Ze tří osob jmenovaných v názvu je nejdůležitějším protagonistou Kurt Gödel, či lépe řečeno jeho nejznámější idea o nedokazatelnosti určitých výroků obsahujících autoreferenci. (Čtenář si dosytosti užije i paradoxních grafik M.C.Eschera a debat o Bachově hudbě; to poslední jsem já, jako muzikálně naivní čtenář, nebyl schopen plně ocenit.) První zhruba polovina GEBu postupně vysvětluje obsah slavné první Gödelovy věty o neúplnosti, a to způsobem, který nepředpokládá žádné předběžné matematické znalosti (možná se hodí umět sčítat přirozená čísla). Zbytek se pak věnuje tak různým věcem, jako jsou genetika a fungování DNA, původ vědomí, rekurzivní algoritmy nebo interpretace jazyka. Přes tak značnou šíři záběru nepůsobí kupodivu GEB ani trochu dojmem neuspořádané hromady vzájemně nesouvisejících ideí.

Ačkoli spekulace o podstatě vědomí jsou nepochybně zajímavé, píšu tuto recenzi především s ohledem na část vysvětlující Gödelovu větu. V tomto ohledu představuje GEB z mého úhlu pohledu jistý ideál — ideál prezentace matematických myšlenek. Hofstadter dokázal skloubit několik napohled protichůdných požadavků: zejména čitelnost, přesnost, přístupnost a provokativnost. (Poslední vlastností zde samozřejmě myslím schopnost provokovat nové nápady, spíš než rozhořčení a násilné reakce.) Autor každý svůj krok vysvětluje na příkladech a analogiích. Dokáže se ovšem vyhnout typické zhoubě populárně vědeckých publikací, která často bývá spojena s použitím analogií, speciálně v diskusích o obtížných tématech: vágnímu jazyku. V podstatných momentech je Hofstadter přesný a interpretace jeho textu je jednoznačná. Přesnosti přitom dosahuje bez toho, aby svůj text degradoval na soupis podmínek, definic, výjimek a formálních důkazů, zkrátka bez nahrazení přirozeného jazyka technickým žargonem, jaký bývá zpravidla k nalezení v matematických (a právnických) textech, kde na přesnosti záleží. Neznamená to, že GEB je plně prostá definic, důkazů a technického žargonu; pouze tolik, že tyto věci jsou užity v míře nutné tam, kde přispívají ke srozumitelnosti. Srozumitelnost, nikoli přesnost, je hlavním cílem.

Vše má samozřejmě svou cenu, a cenou za čtivost a srozumitelnost textu je zde jeho délka. GEB má několik set stran (a několik zde neznamená dvě nebo tři) a někdy byl text i na mě příliš zdlouhavý. To se týká speciálně alegorických dialogů stavěných podle vzoru eseje Co řekla želva Achillovi Lewise Carrolla, které se nacházejí mezi každými dvěma kapitolami. Gödelovu větu je jistě možné vysvětlit na desetině místa, které k tomu potřeboval Hofstadter, navíc s přidanou matematickou rigorózností. Podstatnější, než počet stran, je ale doba strávená nad knihou, a jak znám své tempo čtení hustě psaných matematických textů (doprovázeného často frustrací nad hodinu trvající neschopností posunout se o odstavec dál), nejsem si jistý, zda autorova ochota vést čtenáře pomalu a důkladně přes všechny podstatné kroky ve skutečnosti čas ve skutečnosti nešetří.

GEB jistě není kniha pro každého. Těm, kdo nenávidí cokoli související s matematikou a logikou z celé své duše, asi mnoho zábavy nenabídne. Pro obzvlášť matematicky nadané čtenáře možná může být naopak přespříliš zdlouhavá. Bohužel, není zatím ani pro čtenáře, kteří čtou pouze česky, protože český překlad dosud neexistuje. Zabýval jsem se nějakou dobu ideou knihu přeložit, ale kromě standardní lenosti tomu překáží i způsob, jakým je GEB psán. Kniha je plná slovních hříček a zašifrovaných sdělení, z nichž mnohé jsou nepřeložitelné. Přítomnost těchto věcí sice není pro obsah knihy klíčová, přesto ale mám pocit, že každý překlad GEBu je tak nějak neúplný. Jestli nějakou knihu je dobré číst v originále, pak tuto. [*]

I když se mi tedy nechce překládat, mám alternativní, skromnější plán. V sérii několika následujících [*] příspěvků se pokusím reprodukovat podstatné části Hofstadterova vysvětlení Gödelovy věty a vyrobit tak návod pro ty, kteří by chtěli pochopit, co vlastně znamená neúplnost logických systémů, ale zároveň nemají dost motivace k serióznímu studiu logiky.


Poznámky:
1. Že lidský mozek není stavěn jako procesor na matematickou logiku platí univerzálně, i pro matematiky. Příkladem par excellence byl geniální Ind Srínivása Rámánudžan, který vymýšlel podivuhodně složité identity, aniž by je v tu chvíli uměl formálně dokázat (a proto se čas od času, i když zřídkakdy, zmýlil).