1 Přírodovědecká fakulta TEORIE MNOŽIN pro učitele Eduard FUCHS MASARYKOVA UNIVERZITA Brno, 2000 Obsah předmluva 4 1 Formální výstavba matematiky 6 1 Axiomatická teorie a její model.......................... 6 2 Jazyk matematických teorií............................ 8 3 Výrokový kalkul ................................. 13 4 Predikátový kalkul................................ 28 5 Axiomatická teorie................................ 37 6 Axiomatická teorie množin............................ 42 2 Základní množinové pojmy 52 1 Základní operace na systémech množin ..................... 52 2 Dobře uspořádané množiny............................ 56 3 Aritmetika uspořádaných množin......................... 60 4 Axióm výběru a věty s ním ekvivalentní..................... 66 3 Kardinální a ordinální čísla 73 1 Kardinální číslo. Spočetné množiny....................... 73 2 Nerovnost mezi kardinálními čísly........................ 78 3 Aritmetika kardinálních čísel........................... 84 4 Mohutnost kontinua................................ 90 5 Ordinální typy a ordinální čísla.......................... 93 6 Třída všech ordinálních čísel. Alefy....................... 99 4 Historický vývoj teorie množin 108 1 Vývoj pojmu nekonečno..............................108 2 Georg Cantor a jeho dílo.............................120 3 Antinomie teorie množin. Třetí krize matematiky................133 4 Východiska z krize................................137 2 3 5 Godelovy výsledky................................143 Dodatek 148 Literatura 154 Rejstřík 155 předmluva Množinově-logický jazyk matematiky je dnes již zcela běžný od 1. třídy základní školy. Proto musí být pro budoucí učitele matematiky jeho dokonalé zvládnutí — včetně nezbytného nadhledu — naprostou samozřejmostí. Cíle tohoto textu lze shrnout následovně: 1. vysvětlit nutnost formalizace matematických teorií a nastínit základní metody této formalizace; 2. vyložit základní pojmy teorie množin, především pak popsat základní vlastnosti kardinálních a ordinálních čísel; 3. popsat vývoj teorie množin a vliv této teorie na matematiku 20. století. K pochopení probírané látky není potřeba žádných hlubších předběžných znalostí. (Stručný přehled nejpotřebnějších elementárně-množinových pojmů je uveden v dodatku na konci této části CD). Rada těchto pojmů je dnes již součástí středoškolské matematiky a všechny jsou podrobně probírány v základních matematických přednáškách. Jejich dokonalé zvládnutí — a to v rozsahu výrazně převyšujícím zmíněný dodatek —je proto možno považovat za samozřejmé. Teorie množin sehrála ve vývoji matematiky roli zcela zásadní. Proto je historii teorie množin a důsledkům této teorie pro matematiku 20. století věnována celá 4. kapitola. V této kapitole jsou rovněž uvedeny autentické ukázky z klíčových textů B. Bolzana a G. Cantora. Zvláštní pozornost si zaslouží ta část 4. kapitoly, která je věnována dílu K. Gôdela. Význam jeho „věty o neúplnosti" dnes již přesahuje rámec matematiky samotné. Přesné odvození této věty a charakterizace jejích důsledků přitom není součástí učitelského studia matematiky, neboť k tomu nemají vybudován dostatečný logický aparát. Forma zpracování této problematiky ve 4. kapitole by však měla čtenářům umožnit alespoň pochopení základních idejí Gôdelova důkazu. 4 5 Symbolika užívaná v textu je běžná a význam všech symbolů je v textu (respektive v připojeném dodatku) definován. Upozorněme pouze, že — na rozdíl od středoškolské praxe — rozlišujeme inkluzi Cac. Symbol A c B tak značí, že A je vlastní podmnožinou množiny B. Běžné množiny čísel označujeme následovně: N... množina všech přirozených čísel Z ... množina všech celých čísel Q... množina všech racionálních čísel R... množina všech reálných čísel. Kapitola 1 Formální výstavba matematiky 1 Axiomatická teorie a její model Cítíte-li se skvěle, buďte bez, obav. To přejde. BOLINGŮV POSTULÁT. S rychlým rozvojem matematiky — zejména pak matematické analýzy — vznikla v 19. století naléhavá potřeba řádné výstavby základů matematických teorií. Vhodnou základnou se stala teorie množin, kterou počal v 70. letech minulého století systematicky budovat německý matematik Georg Cantor. (Podrobně historii vzniku teorie množin popíšeme ve 4. kapitole.) Základní množinové pojmy jsou natolik jednoduché, názorné a pro matematiku potřebné, že dnes už pronikly i do školské matematiky na té nejzákladnější úrovni. I malé děti snadno chápou „množiny" jako označení toho, co se v běžné řeči nazývá „soubor", „souhrn" a podobně a bez problémů zvládají základní množinovou algebru. Na první pohled jistě není zřejmé, že by se v takto budované teorii mohly objevit těžkosti zásadního rázu. Velmi snadno však lze ukázat, že nelze beztrestně předpokládat, že každý souhrn nějakých objektů vytváří množinu. Stačí připustit, že existuje množina všech množin, které nejsou svým vlastním prvkem, tj. množina A = {X; X je množina, X £ X}. Z definice množiny A okamžitě vyplývá, že nemůže platit ani vztah A £ A (podle definice množiny A odtud totiž plyne A £ A), ani vztah A £ A (odtud zase naopak plyne A £ A, neboť právě z takových množin jsme množinu A vytvořili). V tomto okamžiku jsme se však ocitli v neřešitelné situaci, neboť z intuitivní představy množiny je okamžitě zřejmé, že pro 6 1. Axiomatická teorie a její model 7 každý objekt x a každou množinu A nutně platí právě jeden ze vztahů x e A, respektive x A. (I když samozřejmě nemusíme vždy vědět, která z těchto situací v daném případě nastává.) Právě jsme zformulovali nejznámější z tzv. antinomií teorie množin, antinomii Russellovu. Antinomií, tj. tvrzení vedoucích ke sporu, se na přelomu 19. a 20. století objevila celá řada; podrobně o nich budeme hovořit v kapitole IV, §3. Jejich důsledky pro moderní matematiku byly dalekosáhlé, neboť přesvědčivě prokázaly, že celou matematiku je nutno budovat jinými metodami, když dosavadní postupy totálně selhaly. V teorii množin samotné pak antinomie ukázaly, že je neudržitelné Cantorovo původní stanovisko, že totiž množina je souhrn jakýchkoliv objektů, chápaných jakožto jeden celek. (Takto pojímané teorii se dnes říká naivní nebo intuitivní teorie množin.) Nalezení východisek z této situace nebylo vůbec jednoduché a jak uvidíme, nebylo všeobecně přijaté řešení vlastně nalezeno dodnes. Nejobvyklejším způsobem výstavby matematických teorií je dnes axiomatická metoda. Čtenář jistě dobře ví, v čem tato metoda spočívá. Každou matematickou teorii lze chápat jako systém nějakých tvrzení o objektech z určité oblasti. Například aritmetika je v tomto smyslu množinou výroků o číslech, geometrie množinou výroků o „vhodných" podmnožinách daného prostoru a podobně. Je zřejmé, že při deduktivní výstavbě (a matematika je ve své podstatě nesporně deduktivní vědou) není možné každé tvrzení odvodit z tvrzení jednodušších a každý pojem definovat pomocí jednodušších pojmů. Proto je nutné o některých nedefinovaných pojmech, tzv. primitivních pojmech dané teorie, vyslovit tvrzení — axiómy, považované za pravdivé bez důkazu. Podle předem stanovených odvozovacích pravidel se pak z těchto tvrzení odvozují další. V této kapitole se budeme zabývat formální stránkou takto budovaných matematických teorií. V závěru tohoto paragrafu si však vyjasněme ještě jednu věc. Uvedli jsme, že Cantorova intuitivní teorie množin je ve světle antinomií neudržitelná. Přitom však i dnes učíme děti ve školách, že množina je totéž jako souhrn, systém, soubor a podobně. Znamená to tedy, že na školách vědomě učíme „špatnou" teorii? Uvedli jsme, že při axiomatické výstavbě se o jistých nedefinovaných objektech (například v eukleidovské geometrii jsou to pojmy „bod", „přímka" atd.) vysloví nedokazovaná tvrzení (v eukleidovské geometrii je to 5 známých postulátů). Podle předem dohodnutých pravidel se pak na tomto základě deduktivně buduje celá teorie. Takto budovanou teorii (například geometrii) může chápat a rozumět jí každý, kdo užívá stejná odvozovací pravidla jako tvůrce dané teorie, i když si nedefinované pojmy může představovat zcela jinak (nebo šije eventuálně nepředstavuje vůbec). (Axiomatickou geometrii tedy může zvládnout i ten, kdo si vůbec nic konkrétního nedovede představit pod pojmy „bod", „přímka" apod.) Jakmile si takovou představu vytvoříme, jakmile si nedefinované pojmy nějak interpretujeme, vytváříme tím tzv. model 8 I. FORMÁLNÍ VÝSTAVBA MATEMATIKY dané axiomatické teorie. I když je zřejmé, že tento model si nelze vytvořit zcela libovolně, je snad jasné, že obecně lze k dané teorii vytvořit modelů více. V tomto smyslu se například učíme na školách pouze jeden z možných modelů eukleidovské geometrie. Je to ovšem model vytvořený tisíciletou zkušeností lidstva, model, který nejvěrněji odráží náš makrosvet. (Čtenář se však jistě setkal i s jinými modely, které jsou zvlášť výhodné při výkladu neeukleidovské geometrie.) A jak je to tedy s teorií množin? Standardní model axiomatické teorie množin obdržíme tak, že si primitivní, tj. nedefinovaný pojem „množina" interpretujeme jakožto synonymum slova soubor. Intuitivní teorie množin — lépe řečeno její jistá modifikace — se tak stává modelem axiomatické teorie množin. (Později uvidíme, že ve školách učíme model tzv. teorie Zermelo-Fraenkelovy). V modelu dané teorie lze ovšem, na rozdíl od intuitivní teorie, provádět jen ty konstrukce a zavádět jen ty pojmy, které jsou odrazem konstrukcí a pojmů přípustných v axiomatické teorii. Proto například nemůže být množinou jakýkoliv souhrn nějakých objektů (například souhrn všech množin) a proto nemůžeme dospět k antinomiím, které se objevily v Cantorově teorii. 2 Jazyk matematických teorií Všechno lz,e udělat snáz,. ILESŮV ZÁKON Při popisu matematických jazyků záhy vypozorujeme řadu analogií s jazyky přirozenými (hovorovými). I s nematematiky se jistě shodneme na následujících skutečnostech: (a) K popisu každého jazyka (češtiny, ruštiny, angličtiny apod.) se užívá jistých znaků, jejichž souhrn nazvěme abecedou. (b) Z prvků této abecedy se tvoří větší celky, nazývané slova, respektive věty. Přitom jen některá formálně utvořená „slova" z daných znaků jsou slovy daného jazyka. Tak například slovo „vhpaimple" je sice utvořena ze znaků české abecedy, zcela jistě to však není české slovo, „window" sice není české slovo, ale je to slovo anglického jazyka a podobně. (c) Jen některé v předcházejícím smyslu „správně" vytvořené věty mají smysl, respektive jsou pravdivé. Například „věta" „Jan a slunce včera prší" je gramaticky správně utvořena, jistě se však shodneme, že je to naprostý nesmysl. Věta „Molekula každého prvku je složena z pěti atomů" je utvořena gramaticky správně, je smysluplná, avšak každý, kdo má alespoň minimální znalosti chemie ví, že je nepravdivá. Slova daného jazyka (ať přirozeného nebo matematického) můžeme posuzovat ze dvou hledisek. Studujeme-li jazyk, aniž přihlížíme k tomu, co jednotlivé znaky, slova atd. znamenají, studujeme-li tedy pouze zákonitost sdružování znaků, závislosti tvaru slov apod. na tvaru jejich 2. Jazyk matematických teorií 9 částí a podobně, říkáme, že jazyk studujeme z hlediska syntaktického. Jestliže nám jde o to, jaký je význam jednotlivých znaků, slov atd., studujeme jazyk z hlediska sémantického. V této kapitole nám půjde téměř výhradně o studium matematických jazyků z hlediska syntaktického. Konečně si ujasněme poslední věc, než budeme hovořit o matematických jazycích podrobněji. Zadáváme-li určitý jazyk S, užíváme při tvoření tohoto jazyka nějaký jiný jazyk, odlišný od S. Tento jazyk nazýváme metajazykem1 jazyka S. Prvky abecedy tohoto metajazyka nazýváme metaznaky, tuto abecedu nazýváme metaabecedou a podobně. Konečně zdůrazněme, že hlavním cílem této kapitoly je popsat formalizaci matematických teorií, vyjasnit základní principy této formalizace a na některých příkladech ji ilustrovat, nikoliv provedení formální výstavby jako takové. ★ ★ ★ Symboly, které již nedělíme na symboly jednodušší, nazvěme znaky. Za znaky obvykle volíme písmena (latinská, řecká), číslice, závorky, čárky, ale často i jiné symboly, jako například U, n, v, A, +, V, 3 a podobně. Přitom předpokládáme, že poznáme, kdy jsou dva znaky totožné (kdy je například na dvou místech napsán stejný znak). Neobsahuje-li abeceda žádný znak, nazývá se prázdná. My však v dalším, kdykoliv řekneme abeceda, budeme mít na mysli abecedu neprázdnou. Skupinám znaků napsaným zleva doprava budeme říkat slova (vytvořená v dané abecedě). Je-li například dána abeceda a b * A + jsou slova například nápisy *ab A A nebo * * + *b A a nikoliv však nápis a * v b A Ac (symbol v nepatří do naší abecedy). Účelné je definovat tzv. prázdné slovo, které není tvořeno žádným znakem. Prázdné slovo je zřejmě slovem v každé abecedě. Za slovo považujeme také jednotlivé znaky. Nyní je rovněž zřejmé, co rozumíme posloupností slov. Doplníme-li zvolenou abecedu o nový znak, který nazveme oddělujícím znakem, nazýváme každé slovo v této rozšířené abecedě posloupností slov v abecedě původní. Často oddělující znak nepíšeme a místo něho uděláme mezi slovy mezeru. Abychom si nyní usnadnili popis studovaného jazyka, zvolíme si nějaké znaky, kterými budeme označovat slova vytvořená v naší abecedě. Čtenáři je jistě zřejmé, že to nemohou být 1Meta (z řečtiny), v složených slovech první část s významem „za", „po". Například metateorie je teorie zkoumající jinou teorii. Podrobně je studována zejména metamatematika. 10 I. FORMÁLNÍ VÝSTAVBA MATEMATIKY znaky naší abecedy, ale že to budou metaznaky. Dohodněme se, že za metaznaky označující slova, zvolíme malá písmena řecké abecedy (eventuálně s indexy; tyto indexy však nepovažujeme za samostatný znak). Označují-li a, p totéž slovo, napíšeme a ~ ji. Je-li například cp znak označující slovo *ba+, píšeme cp ~ *ba+. Prázdné slovo označíme symbolem co. Jsou-li a, p dvě slova a napíšeme-li je bez oddělovacího znaku těsně za sebou, dostaneme opět slovo, které nazýváme slovem složeným ze slov a,p a značíme je or/J. V dalším budeme běžně užívat řady zřejmých tvrzení následujícího typu, z nichž některá ani nebudeme výslovně formulovat. 2.1. Věta. (a) Pro libovolné slovo cp platí cocp ~ £]. Zcela analogický smysl má označení [«i -> £i, ■ ■ ■, oí„ -> P„]. Rozumíme jím substituci slov za znaky a,-, i = 1, ..., n (viz následující příklady). 2.10. Příklad. Zvolme abecedu jako v příkladu 2.6. Nechť / je substituce: (a) [1 -> 04] (b) [1 -> 2, 2 -> 3, + -> «] (c) [+ -> 1, 0 -> 2, 9 -> +]. Pak / přiřazuje slovu „21 + 4890" slovo: (a) 204 + 4890 (b) 324890 (c) 21148+ 2. 3. Výrokový kalkul 13 Prozatím jsme popisovali víceméně mechanicky práci se znaky. Dobře však víme, že v matematickém jazyce — stejně jako v jazycích přirozených — nepovažujeme za slovo každé seskupení znaků ze zvolené abecedy a slova neskládáme do posloupností zcela nahodile. Víme, že například při sčítání čísel uvažujeme slova typu „48 + 290" a nikoliv slova „+ + +01" nebo „28 + 42+" a podobně. Při odvozování nějakého vzorce nepíšeme za sebou slova namátkou, ale podle jistých předem stanovených pravidel. Souhrnu pravidel, kterými se matematik řídí ve své činnosti, říkáme kalkul. Pojem kalkulu zde však nebudeme definovat. Je snad ale jasné, že kalkulů je celá řada; každá matematická teorie má svůj specifický kalkul. Prakticky všechny kalkuly však mají „něco" společného. V následujících dvou paragrafech budeme precizovat výrokový kalkul, který v intuitivním smyslu běžně užíváme. 3 Výrokový kalkul Dobrý úsudek si vytvoříme díky špatné zkušenosti. Zkušenost nabudeme díky špatnému úsudku. HlGDONŮV ZÁKON 3.1. Definice. Abeceda výrokového kalkulu je tvořena následujícími znaky: 1. Velkými písmeny latinské abecedy A, B, ..., X,Y, Z případně opatřenými indexy. Tyto znaky nazýváme výrokovými proměnnými (nebo též proměnnými pro výroky). 2. Znaky -■, v, A, =>•, <£> nazývanými logické spojky. 3. Znaky ( a ) (levá a pravá závorka). 3.2. Poznámka. Označíme-li proměnnou pro výroky symbolem A\, P3, Z10 a podobně, neznamená to, že naši abecedu de facto rozšiřujeme o znaky označující přirozená čísla. Na uvedené znaky, jednoduše řečeno, pohlížíme jako na jediný symbol. Při počítání s výroky samozřejmě nebereme v úvahu všechna slova, která lze v dané abecedě vytvořit. Za správně utvořené slovo jistě nepovažujeme slovo A—> v B nebo (A)->(Z?) v (C-1). Na první pohled ovšem není jasné, jak popsat ta slova, která ve výrokovém kalkulu budeme považovat za správně utvořená. Správná slova, která popíšeme následující definicí, budeme nazývat výrokové formule nebo stručně jen formule, pokud nebude moci dojít k nedorozumění. (Ve shodě s §2 budeme k označování formulí a obecně slov v abecedě výrokového kalkulu užívat metaznaků a, fi, y, ..., eventuálně s indexy.) 14 I. FORMÁLNÍ VÝSTAVBA MATEMATIKY 3.3. Definice. (1) Každá výroková proměnná je výrokovou formulí. (2) Jsou-li (• (ý), (p) <^> (xfr) výrokovou formulí. (3) Žádné slovo, které nelze získat pomocí (1) a (2) není výrokovou formulí. 3.4. Poznámka. Definice 3.3 samozřejmě není a nemůže být výčtem všech výrokových formulí, neboť těch je evidentně nekonečně mnoho. Definice je pouze rekurentním návodem ke tvorbě výrokových formulí. Ukažme alespoň na několika příkladech, jak lze podle definice 3.3 konstruovat komplikovanější formule a jak poznáme, zda zadané slovo je nebo není výrokovou formulí. Jsou-li například A, B, C, D výrokové proměnné, jsou podle (2) slova (A)^(B), (C)v(-(D)) výrokovými formulemi. Opět podle (2) jsou pak výrokovými formulemi i slova (-((A) =» (5))) 4» (D), (A) A ((C) v (-(£>))), takže je výrokovou formulí i slovo ((-((A) =» (5))) 4» (£>)) =» ((A) A ((C) v (-(£>)))) (*) atd. Je vidět, že definice 3.3 nám umožňuje vytvářet dostatečně komplikované formule. Zcela analogicky postupujeme, když chceme zjistit, zdaje dané slovo výrokovou formulí. Nechť například je

) v (-(A)))). Zjišťujeme, zda

AvB, respektive A A B nejsou podle definice 3.3 formule, i když je nám naprosto zřejmé, jaký smysl těmto slovům přikládáme. Proto uzavřeme následující dohodu, která nám umožní zjednodušení zápisů výrokových formulí. 3.5. Úmluva. Zápisy výrokových formulí lze zjednodušit pomocí následujících tří pravidel. Jejich dodržování však nebudeme striktně vyžadovat, budeme se řídit tím, jaký z povolených zápisů bude v dané situaci nejúčelnější. 1. Je-li podslovem slova

•, Závorky, které nám zajišťují realizaci uvedených předností, při psaní formulí vynecháme. 3. Při kumulaci většího počtu závorek užijeme i závorek hranatých [, ], resp. složených {,}, které však nezmění význam formule. 3.6. Příklad. (a) Slovo ((A) v (B)) =>• (C) lze podle (1) zapsat ve tvaru (A v B) =>• C. Podle (2) lze toto slovo ještě zjednodušit na tvar AvB=^C. (b) Slovo HA))v^(-((C)a(D)))J lze podle (1) a (2) zjednodušit takto: -A v (C A D). 16 I. FORMÁLNÍ VÝSTAVBA MATEMATIKY Podle (4) však můžeme totéž slovo napsat také například takto: -■A v-.(-.(cad)) -(-(cad))]. nebo (-A) v (c) Formuli (★) v poznámce 3.4 lze přepsat takto: [(-A 4B)^/)]4[Aa(Cv -.d)]. Při konstrukci výrokových formulí lze s výhodou často využívat následujícího tvrzení, které vyplývá bezprostředně z definice výrokové formule. 3.7. Věta. Buďte a, p výrokové formule, £ libovolná výroková proménná. Buď f substituce [£ -> /?]. Pak je f (a) výroková formule. (Tz,n., ž,e když, ve výrokové formuli nahradíme proměnnou formulí, dostaneme opět formuli). 3.8. Příklad. Buď / substituce [A -> -(5 v c) D a c] a í>~A=).(Sa -c) v (-.A a 5). Pak je (p zřejmě formule a podle 3.7 je výrokovou formulí slovo (-(5 v c) =^ D a c) =^ j (5 a -.c) v -(-(5 v c) =^ d a c) a B Ve výrokovém kalkulu nám ovšem nejde o to, psát výrokové formule nebo zjišťovat, zda dané slovo je výrokovou formulí. Dobře víme, co rozumíme výrokem; smyslem námi popisovaných výrokových formulí je to, že pokud výrokové proměnné chápeme jako označení pro výroky, pak jsou výrokové formule rovněž zápisy (složených) výroků. Víme také, že charakteristickou vlastností výroků je jejich pravdivost, respektive nepravdivost. Hlavním cílem výrokového kalkulu je právě studium toho, jak pravdivost či nepravdivost složeného výroku závisí na pravdivosti či nepravdivosti výroků, z nichž byl tento výrok pomocí logických spojek utvořen3. 3 V této chvíli je čtenáři jistě zcela zřejmý rozdíl mezi sémantickým přístupem k výstavbě výrokového kalkulu, jak ho zná například ze střední školy, a syntaktickým přístupem, který demonstrujeme nyní. Při středoškolské výuce se nejdříve zavede, či — lépe řečeno — vysvětlí pojem výrok jako označení pro tvrzení, o němž má smysl prohlásit, že je pravdivé, respektive nepravdivé a pak se intuitivně budují další potřebné pojmy. Při syntaktické výstavbě se pojem výrok vůbec nedefinuje, je to primitivní pojem. Zato jsme však přesně popsali, jak vypadají formule, což při sémantické výstavbě pouze mimochodem vyplývá z toho, jak zavádíme formální označení. Při sémantické výstavbě je tedy pravdivost či nepravdivost výroku zabudována přímo v jeho „definici", my však tímto atributem musíme výrokový kalkul teprve opatřit. 3. Výrokový kalkul 17 Výrokový kalkul nám neumožní zjistit, zda jednoduché tvrzení nějaké teorie je pravdivé či nikoli; to jsme nuceni zjišťovat jiným způsobem. (Pomocí výrokového kalkulu například nejsme schopni zjistit, zda je pravdivé tvrzení „213 — 1 je prvočíslo"; že je toto tvrzení pravdivé, je možno dokázat v teorii čísel.) Výrokový kalkul nám jen upřesní, jak správně tvořit z výroků jednodušších výroky složitější a jak pravdivost těchto složitějších výroků závisí na pravdivosti příslušných výroků jednodušších. (Z výrokového kalkulu lze například zjistit, kdy je pravdivé tvrzení: „Je-li 213 — 1 prvočíslo, je také 217 — 1 prvočíslo".) Výrokový kalkul je tedy natolik obecný, že nepostačuje k vytvoření speciálních matematických teorií. Na druhé straně je ovšem natolik univerzální, že je součástí prakticky každého matematického jazyka. Proto věnujeme výrokovému kalkulu takovou pozornost. 3.9. Definice. Rozšiřme abecedu výrokového kalkulu o znaky 0, 1. Buď p funkce na slovech utvořených v této rozšířené abecedě taková, že platí: (1) není-li slovo

• ý), p(

■ f) p(

~ [(--A =» B) D] =» [A A (C v ->D)] z příkladu 3.6(c). Označme pro jednoduchost a ~ —'A =^ 5, ~ cc Z), y ~ C v —•D, S ~ A A y. Pak je (p ~ y6 =3- S. Hodnoty p(=>. e)^-(pa-e). (Viz tabulku 1.2) p(p) p(Q) p(-Q) p(PA^Q) a-g)) pop =» Ô) p((p a - =>. p) =>. p (p =>. -,/>) =>. ^p (p a p) 4» p; (p v p) 4» p [(p g) a (g =» i?)] ^ (p ^ i?) [(p 4» g) a (g 4» i?)] ^(p^r) (p a-p) =» e (p a Q) =» p -(p a g) 4» (-p v-j3) -(p v g) 4» (-p a-j3) (zákon vyloučeného třetího) (zákon totožnosti) (zákon dvojí negace) (zákon Claviův, též, reductio ad absurdum ) (6) (7) (8) (9) (10) (H) (12) (13) (14) (15) (zákon hypotetického sylogismu) (zákon Dunse Scota) (de Morganovo pravidlo) (de Morganovo pravidlo) (Peirceův zákon) V poznámce 3.10(d) jsme uvedli, že pro libovolnou výrokovou formuli lze mechanicky sestrojit tabulku pravdivostních hodnot této formule, tj. tabulku, která udává závislost hodnoty p((p) na hodnotách p (a) výrokových proměnných, které se ve formuli

A, v případě (b) formuli (p ~ A, v případě (c) formuli

A. V každém z těchto čtyř případů však bez obtíží lze zkonstruovat i jiné výrokové formule se stejnou pravdivostní tabulkou, například takto: 3. Výrokový kalkul 21 A

(A A ->A) (b) cp ~ -i-i A (c) cp ~ A =3- ->A (d) cp ~ -.(-.--A 4» A). Dokázali jsme tak, že v případě w = 1 je odpověď na problém 3.16 (1) kladná, na problém 3.16(2) záporná. 3.18. Příklad. Buďra = 2. Pak lze tabulku podle 3.16 sestavit celkem 16 způsoby, které jsou souhrnně uvedeny v tabulce 1.4. Porovnáním s tabulkou v definici 3.9 je okamžitě vidět, které sloupce v tabulce 1.4 odpovídají tabulkám logických spojek. Zřejmě lze volit c/?2 ~ A v B, c/34 ~ A =3- B, cpg ~ A <£> B, (P12 ~ A A B. Evidentní je však skutečnost, že lze velmi jednoduše zkonstruovat výrokovou formuli s požadovanou vlastností v každém ze zbývajících dvanácti případů. Za A A B) p(A A C) P(r) 1 1 1 0 1 1 1 1 0 0 0 0 1 0 1 0 1 1 0 1 1 1 0 1 1 0 0 0 0 0 0 1 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 Tabulka 1.5: Z tabulky 1.5 je ihned vidět, že platí následující tvrzení. Lemma. Je-li p (A) ~ 1, je p{x) ~ p(C), je-li p (A) ~ 0, je p{x) ~ p{B). Předpokládejme nyní, že pro přirozené n je věta 3.19 dokázána. Dokážeme, že tvrzení platí i pro n + 1. Nechť tedy je zadána tabulka o 2"+1 řádcích a n + 2 sloupcích. Rozdělme nyní tuto tabulku na dvě části následovně: vyškrtněme z tabulky předposlední sloupec (odpovídající pravdivostním hodnotám p(An+\)) a do první části zařaďme ty řádky, v nichž je ve vyškrtnutém sloupci 0, do druhé části zařaďme zbývající řádky. Každá část je nyní tabulkou pravdivostních hodnot nějaké výrokové formule, v níž se vyskytují pouze výrokové proměnné A\, ..., A„. Podle předpokladu však dovedeme zkonstruovat výrokové formule A„+1 A (pi) V (An+Í A A„+1, B -> (pi,C -> (pi]- Z lemmatu však nyní plyne: Je-li p(A„+1) ~ 0,je p((p) ~ p(íOi), je-li p(a„+1) ~ l,je /?(A, (p2 ~ A. Podle důkazu věty 3.19 je nyní •, <£> nám umožňují zkonstruovat libovolně komplikované výrokové formule. Nevyřešena je prozatím otázka, zda není možné vybudovat výrokový kalkul s menším počtem logických spojek; toho by bylo možno dosáhnout jednak vypuštěním některé z pěti uvedených spojek (dobře víme, že to fakticky možné je, neboť například spojku <£> lze vyjádřit pomocí spojek =>•, A), jednak zavedením nových spojek, které by eventuálně mohly být při tvorbě výrokového kalkulu výhodnější. K tomuto účelu je vhodné zavést pojem logické ekvivalence výrokových formulí, jehož užitečnost vyplývá bezprostředně z věty 3.19, podle které ke každé tabulce pravdivostních hodnot existuje více výrokových formulí. 3. Výrokový kalkul 25 3.22. Definice. Řekneme, že výrokové formule xjr je tautologie. Přímo z definice 3.22 plyne 3.24. Věta. Buďte a, /3, y libovolné výrokové formule. Pak platí: (i) a = a, (ii) je-li a = /3, pak je p = a, (iii) je-li a = p a p = y, pak je a = y. Nyní si ukážeme, že místo pěti logických spojek -■, v, A, =>•, vystačíme pouze s vhodnými dvojicemi. 3.25. Věta. Buď(p libovolná výroková formule. Pak existují formule a, /3, y takové, ž.e cp = = a = p = y a přitom platí: (a) ve formuli a se nevyskytují jiné logické spojky než. A, —> ; (b) ve formuli p se nevyskytují jiné logické spojky než. V, —> ; (c) ve formuli y se nevyskytují jiné logické spojky než. =>•,—>. Důkaz této věty nebudeme podrobně provádět. (Je například v [3]). Ukážeme si pouze, jak lze nalézt například formuli a. V následující definici zadáme rekurentně mechanicky počitatelnou funkci h na slovech výrokového kalkulu, která nám umožní k libovolné výrokové formuli najít logicky ekvivalentní výrokovou formuli, v níž se nevyskytují jiné logické spojky než A a ->. • 26 I. FORMÁLNÍ VÝSTAVBA MATEMATIKY 3.26. Definice. Funkci h na slovech výrokového kalkulu definujeme takto: není-li slovo (p výrokovou formulí, klademe h() ~ —>h([->&(?') a —■A(^r)]; (v) /i(

• i/f) ~ ->[A(^) a —■A(^t)]; (vi) /l(

[&(?>) a ~'/l(Vf)] a ~'[/l(Vf) a ->h{(p)\. 3.27. Poznámka. Z definice výrokové formule plyne, že definice 3.26 nám vskutku umožňuje převést libovolnou výrokovou formuli postupně na tvar, v němž se nevyskytují znaky v, =>• a Přitom je opravdu zřejmé, že funkce h je mechanicky počitatelná. Nyní bychom, přesně vzato, měli dokázat, že formule, kterou obdržíme postupným užitím definice 3.26, je logicky ekvivalentní s výchozí výrokovou formulí. Důkaz však ponecháme čtenáři. (Je vcelku zřejmé, že podmínky (i) - (iii) zajišťují, že funkce h nemění formuli, která je již napsána ve vhodném tvaru a podmínky (iv) - (vi) využívají vhodných elementárních tautologií. Tak například (iv) zřejmě využívá de Morganova pravidla.) 3.28. Příklad. Najděte k formuli

•, h{->A B) ~ -.[a(-.a) a ->h(B)] ~ -(-a a -5) h(C v -£>) ~ ->[->h(C) a -.A(-.D)] ~ -.(-.C a — D) h[A a (c v ->D)] ~ /i(a) a /i(c v -D) ~ a a -(-c a — D) a [(--a B) 4» D] ~ -.[a(-.a =^ 5) a -■ä(D)] a ->[h(D) a ->h(->A =^ B)] ~ ~ -[-(-a a -5) a -.D] a -.[D a —(-a a -5)] /i(h[A a (c v -■£>)]} ~ ~ -.] -.[-.(-.a a -5) a -.D] a -.[D a —(-a a -5)] a -[a a -.(-.C a -.-.D) Je tedy p ~ [(-a =» B) D] =» [a a (C v -"£>)]. Pak: 3. Výrokový kalkul 27 3.30. Definice. Definujme logické spojky,, |" a „\." následujícími tabulkami pravdivostních hodnot: p((A A B) (2) A|A = -A (3) A\B = ->A v ->B (4) A ; B = -(A v B) (5) A \, B = —>A A —>B Důkaz je triviální a přenecháme jej čtenáři. • Z vět 3.25 a 3.31 plyne 3.32. Důsledek. Buď(p libovolná formule výrokového kalkulu. Pak existují formule a, p takové, Že (p = a = p a formule a neobsahuje jinou logickou spojku než, \ a formule p jinou logickou spojku než, \. 28 I. FORMÁLNÍ VÝSTAVBA MATEMATIKY 4 Predikátový kalkul Některé věci nelze vědět — nevíme však, o které věci jde. Jaffova poučka Výrokový kalkul, který jsme podrobně probrali v §3, zkoumá závislost pravdivosti složených výroků na pravdivosti či nepravdivosti jednodušších výroků, z nichž je složen. Uvedli jsme však již, že v jeho obecnosti je současně i jeho omezení. Pravidly výrokového kalkulu by se měly řídit úvahy v matematice stejně jako v biologii, v lingvistice stejně jako v meteorologii. Výrokový kalkul je však v jistém slova smyslu jen prvním přiblížením k našemu cíli, tj. k popisu formalizace matematických teorií. Víme již, že výrokový kalkul nám vůbec neumožňuje rozhodovat, zda jednoduché — atomární — výroky dané teorie jsou pravdivé či nikoliv, ani nám neumožňuje rozhodnout, které formule v dané teorii jsou správně utvořené a podobně. V tomto paragrafu nám půjde pouze o syntaktický popis studované problematiky. Na rozdíl od výrokového kalkulu nám však predikátový kalkul umožní i syntaktický popis atomárních výroků. Víme již, že různé matematické teorie mají navzájem odlišné jazyky, užívají různých symbolů, tvoří se v nich formule odlišnými způsoby. Přesto však mají mnoho věcí společných. A právě tento „společný základ" nyní popíšeme. V jistém slova smyslu budeme postupovat obdobně jako v §3. Nejprve popíšeme abecedu, pak určíme, která slova v této abecedě budeme považovat za správně utvořená (ta budeme nazývat predikátové formule), budeme definovat tautologie predikátového kalkulu a podobně. Nejprve tedy k abecedě predikátového kalkulu. Vzhledem k tomu, že již budeme studovat i syntaktickou strukturu atomárních výroků, musí naše abeceda nutně obsahovat znaky, které jsou specifické pro danou teorii (například v teorii množin je to znak e, v aritmetice znaky +, < apod.). Kromě logických spojek je do naší abecedy nutno zařadit i znaky V a 3 (kvantifikátory). Samozřejmě abecedu vytvoříme tak, aby neobsahovala metaznaky, jichž budeme užívat analogicky jako v §§2 - 3. 4.1. Definice. Abeceda predikátového kalkuluje, tvořena následujícími znaky: 1. Znaky pro proměnné pro objekty (obvykle jsou to písmena latinské abecedy, případně s indexy). 2. Znaky —■, V, A, =>•, •£>•, V, 3 pro logické spojky a kvantifikátory. 3. Specifické znaky pro popisovanou teorii (například v teorii množin znak e). 4. Závorky ( a ). 4. Predikátový kalkul 29 4.2. Poznámka. V tomto paragrafu budeme proměnné pro objekty označovat malými písmeny a, b, c, ..., x, y, z atd. Velká písmena si prozatím rezervujeme pro výrokové proměnné, které budeme ještě potřebovat k zápisu výrokových formulí. O užití indexů v naší abecedě platí totéž, co jsme již uvedli v poznámce 3.2. 4.3. Definice. Řekneme, že proměnná x je vázána ve slově • 3z)) 4» (Ví V w) Pak jsou zřejmě: x, y,w podstatně volné proměnné ve

• z) V Ví \jr ~ Vxw(vu;) £ ~ f 4» (3x V z). Pak jsou slova 93, i/r slučitelná, slova \\r, q jsou také slučitelná, ale slova •, V, 3. 2. Je-li (p primitivní predikát a /libo volná substituce tvaru [£ -> rj], kde £, rj j sou proměnné pro objekty, pak je f() predikátová formule. 3. Jsou-li • (xfr) a ((p) <£> (xfr) predikátovými formulemi. 4. Je-li (p predikátová formule a proměnná x není ve slově

) a (Vx) ((p) predikátovou formulí. 5. Slovo, které nelze vytvořit pomocí (1) - (4), není predikátovou formulí. 4. Predikátový kalkul 31 4.9. Příklad. V teorii množin je slovo x e y primitivním predikátem. Podle definice 4.8 jsou tedy následující slova predikátovými formulemi: (a) (iěj)v(jě z), (b) -.((* v y) v (y vz)), (c) (x e z) 4» (-■((* e y) v (y e z))), (d) (Vx)((x e z) 4» (-((x e y) v (y e z)))) atd. Predikátovou formulí však není slovo (Vx)((xey)^((3x)(xez))), neboť ve formuli (x e y) =>• ((3x)(x e z)) je proměnná x vázaná a proto nelze této formuli předřadit slovo Vx. 4.10. Poznámka. I v predikátovém kalkulu, pokud to bude možné, budeme zjednodušovat zápis predikátových formulí. Z úmluvy 3.5 převezmeme všechna pravidla, která doplníme navíc o dohodu, že každý z kvantifikátorů V, 3 má přednost před kteroukoliv z logických spojek v, A, -i, =>•, takže například (3x)

Vl> ■ ■ ■ ,An ~+ Ýn\ ■ Pak je formule f(• Q) a (Q =>• R)] ^(P^R) tautologie výrokového kalkulu. Slova Ýi ~ (x e y) =3- (z e y) f 2 ~ (Vr) (x e t) Ý3 ~ (3iu)[(x £ w) a (u; £ z)] jsou zřejmě slučitelné formule. Podle pravidla 4.15 je tedy {{[(xey)^(zey)]^[(VO(xeť)]}/ a [(Vr)(x e 0] =>• j(3^)[(x s w) a (w s z)]] J [(x e y) =>■ (z e y)] =>• j(3w)[(x e w;) a (w; e z)]} J tautologie predikátového kalkulu. 4. Predikátový kalkul 33 (b) Podle věty 3.15(10) je tautologií formule (P a-P) =» g. Je tedy tautologií predikátového kalkulu například formule [(x £ v) A (x e y)] =» (Vz)(x e z) nebo formule Z příkladu 4.17 je vidět, že každá tautologie výrokového kalkulu je vlastně návodem k vytváření tautologií predikátového kalkulu. Lehce se však ukáže že pravidlo 4.15 nám ještě neumožňuje odvodit všechny tautologie predikátového kalkulu. Další pravidlo k získávání tautologií uvedeme nyní. 4.18. Pravidlo 2. Je-li (3x)

y]. Pak je (Vx)

• /() tautologie. 4.21. Poznámka. Jestliže je formule (Vx)

• f((p) tautologií triviálně. Pravidlo 4.20 rovněž není zajímavé v případě, kdy se proměnná x ve slově

y]. Pak je

(i e z)), / buď substituce [x -> w]. Pak je (3x)[(x e j) 4» (x e z)] 4» (3u)[(u ěj)(»ě z)] tautologie. Vidíme, že podle pravidla 4.23 nezáleží na označení vázané proměnné. 4.25. Pravidlo 5. Jsou-li následující dvě slova predikátové formule, jsou to tautologie: (a) (Wx)( 4» (Vx)V] (3x)

• xfr tautologie predikátového kalkulu, je i xfr tautologie predikátového kalkulu. (DP 2) Je-li x volná proměnná v tautologii -P) => -P tautologie výrokového kalkulu. Podle pravidla 4.15 je tedy predikátová formule

-(x e j) (i) 36 I. FORMÁLNÍ VÝSTAVBA MATEMATIKY elementární tautologií predikátového kalkulu. Podle pravidla 4.18(1) je pak ale elementární tautologií predikátového kalkulu i formule Ý ~ (3x)J[x ey)4 -(x e y)] 4-(jěj)) -(Vx)-J[(x ey)4 4^éj)]4-(iéj)|, (ii) tj. xfr ~ (3x)

-i(Vx)(-"^o). Poněvadž je výroková formule p (e p) zřejmě tautologií výrokového kalkulu, je opět podle pravidla 4.15 formule f =» |{(3z)[(y e z) a (io e z)]} =» VJ (iii) elementární tautologií. Pak ale podle (DP 1) je elementární tautologií i formule j(3z)[(j e z) a (w e z)]} =» f, což je ovšem formule (★), kterou chceme dokázat. Jinak řečeno, posloupnost formulí • \ý =>• (

• (

• xjr je formule, je také h^4ý. 5 Axiomatická teorie Pokusy musí být opakovatelné — jen tak mohou naprosto stejným způsobem vždy selhat. PÁTÁ FlNAGLOVA ZÁSADA Ukázali jsme si rozdíl mezi výrokovým a predikátovým kalkulem a víme již, jak užitečný je predikátový kalkul při popisu a zkoumání teorie ze syntaktického hlediska. Predikátový kalkul nám umožnil precizovat syntaktickou strukturu atomárních výroků a definovat dokazatelnost formule (v predikátovém kalkulu). V příkladu 4.33 jsme si ukázali, že pomocí predikátového kalkulu můžeme dokázat i poměrně komplikované formule a je zřejmé, že náš příklad byl přitom zvolen velmi jednoduše. Současně z §4 plyne, že dokazatelných formulí v predikátovém kalkulu je nekonečně mnoho. Čtenáři je však jistě zřejmé, že ani predikátový kalkul není dostatečným nástrojem k vybudování konkrétní matematické teorie. Víme totiž, že dokazatelné formule v predikátovém kalkulu nemohou vypovídat nic o tom, čím se dvě různé matematické teorie odlišují. Predikátový kalkul je pořád jen „společným základem" těch teorií, při jejichž výstavbě tohoto kalkulu použijeme. Navíc je podle poznámky 4.32 každá dokazatelná formule predikátového kalkulu tautologií, jinak řečeno, dosadíme-li do dokazatelné formule za podstatně volné proměnné libovolné konstanty dané teorie, obdržíme vždycky pravdivé tvrzení. Víme však, že při výstavbě matematické teorie nám nejde o hledání tautologií, ale právě naopak, chceme většinou dokázat pravdivost uzavřených formulí, které považujeme za zápisy výroků. 38 I. FORMÁLNÍ VÝSTAVBA MATEMATIKY My však již víme, co je nutno v této situaci provést. Jisté formule prohlásíme za pravdivé bez důkazu.Tyto formule nazveme axiómy dané teorie a z těchto axiómů pak odvozujeme další tvrzení. Jak lze takto vybudovat nějakou teorii prakticky, uvidíme v §6. Nyní si jen stručně uvedeme některé základní vlastnosti společné všem axiomatickým teoriím. K vytvoření axiomatické teorie je tedy nutno: (a) stanovit konkrétně primitivní predikáty (a tím tedy vlastně zadat predikátový kalkul), (b) udat soupis axiómů. Při výstavbě axiomatické teorie uvidíme, že axiómy jsou, zhruba řečeno, dvojího druhu. Některé axiómy pouze upřesňují jazyk matematické teorie, nejčastěji tak, že zadávají jisté vztahy mezi primitivními predikáty. Jiné axiómy naopak postulují základní vlastnosti objektů, které v dané situaci studujeme. Po formální stránce je nejjednodušší systém axiómů zadat tak, že udáme jejich soupis. To však není vždycky možné — například proto, že axiómů dané teorie je nekonečně mnoho. (Tak je tomu například u Zermelo-Fraenkelovy teorie množin — viz §6.) V takovém případě je obvykle udáván alespoň tvar formulí, které za axiómy považujeme. V každém případě je však přirozené požadovat, aby bylo o každé formuli možno mechanicky rozhodnout, zdaje nebo není axiómem. Nyní již předpokládejme, že jsme stanovili primitivní predikáty a axiómy teorie T. 5.1. Definice. Důkazem v teorii T nazýváme takovou posloupnost formulí, že každý člen této posloupnosti: (a) je axiómem teorie T, nebo (b) je elementární tautologií, nebo (c) je utvořen z některých předcházejících členů důkazu užitím pravidel (DP 1) a (DP 2). 5.2. Definice. Řekneme, že formule

\, ..., xfr =>• neni co dokazovat. Nechť tedy ý není totožná s (p. Oíi, «2, . . . , (p 5. Axiomatická teorie 41 je důkaz (p v T, důkaz —>

A -<$. Podle pravidla 4.15 a věty 3.15(10) je ((p A ->q>) =>• xjr elementární tautologie, takže xjr je dokazatelná podle (DP 1). Důkazem xjr v T je posloupnost di, a2, . . ., (p, Pi, P2, ■ ■ ■ , Ý, Yi> Y2, ■ ■ ■ , (P A -•(p, ((p A ->q>) =3- f, f. (b) Nechť• —'(p). Existuje tedy v T důkaz Oíi, «2, ...,#>=>• —<(p formule

■ -'(p) =3- -'(p, -'(p důkaz formule —>

•,•£>•, V, 3 pro logické spojky a kvantifikátory. 3. Specifický znak e. 4. Závorky ( a ). 6.2. Poznámka. (a) Abecedu definovanou v definici 6.1 nazýváme základní abecedou teorie tříd. Později bude vhodné tuto abecedu rozšířit o další znaky. (b) Definice 6.1 je v naprosté shodě s definicí 4.1. (c) Objekty naší teorie, označované znaky A, B, C, ..., X, Y, Z a podobně nazýváme třídy. (d) Specifický symbol e čteme slovy „je prvkem". (e) K označování slov v naší abecedě budeme užívat opět metaznaků )) =*(X = Y)] (tato formule znamená: existuje právě jedno X tak, ž.e (p). Symbol 3! můžeme opět buďto považovat za metaznak nebo o tento symbol můžeme doplnit základní abecedu a odpovídajícím způsobem pak rozšířit definici formule. 46 I. FORMÁLNÍ VÝSTAVBA MATEMATIKY Prozatím jsme uvedli jen jeden axióm. Nyní však již budeme nuceni zavést další. Promyslíme -li si totiž, co intuitivně rozumíme rovností dvou objektů, zjistíme, že kromě vlastností (1) - (3) z věty 6.10 musí být splněn požadavek, že dva sobě rovné objekty mají stejné vlastnosti, tj. v jakékoliv situaci lze jeden z nich nahradit druhým. Přesně řečeno, po rovnosti požadujeme, aby bylo splněno následující tvrzení: 6.12. Metavěta. Bud'(p{X\, ..., Xn) libovolná formule, v níž se nevyskytují proměnné Y\, ... ,Yn Pak je dokazatelná formule (VXj)... (VXJCVFj)... (Vy„){[(X! = Fj) A (*! = Y2) A ... ... A (Xn = Y„) A yiXu X„)] =» ■ (Y e W)} . Důkaz. Tvrzení plyne bezprostředně z definice 6.9 a z axiómu 2. • 6.14. Poznámka. Je zřejmé, že 6.13 je zvláštním případem metavěty 6.12. Stačí totiž do věty 6.13 za formuli =>• Q) a-g] b) (P a Q =» R) 4» [P =» (Q =» R)] c) [P =» (Q =» R)] =» [(P g) (P R)] d) [(P Q) a P] Q e) [(P v g) a-P] g f) [(P =>. g) a (R =>■ 5)] =>• [(P aS)4(6v i?)] (Návod: Určete, kdy p(Q v v i?) ~ 0, p(P A S) ~ 1. Pravdivost implikace pak bude zřejmá.) 6. Dokažte, že následující výrokové formule jsou tautologie: a) [(P V0 4 4 (-P v Q) (Návod: Vyšetřete případ p(P) ~ 1, P(G) ~0.) 6. Axiomatická teorie množin 51 b) j [(P aQ)^R]a [(P a Q) =» -i?]} =» A -g A -i?) (Návod: Vyšetřete případ /?(P) ~ p(Q) ~ 0, ~ 1. Uvědomte si, že lze přitom volit pravdivostní hodnoty tak, že p(P a Q) ~ 0, ~ 1.) 7. Vyjádřete formule ze cvičení 6 pomocí spojek -■, v, respektive -■, =>•, respektive -■, A. 8. K formulím A =>• B, A a B, (A =>• B) v C, (A 4» B) v [C A (A =>• 5)] najděte logicky ekvivalentní formule, v nichž se vyskytují pouze logické spojky |, respektive Kapitola 2 Základní množinové pojmy 1 Základní operace na systémech množin Právě o těch nejednodušších věcech nevíme vůbec nic. De Neversův zákon složitosti 1.1. Definice. Buď 7^0 libovolná (tzv. indexová) množina. Buď A, množina pro každé i e /. Sjednocením množin A,, i e 7, nazýváme množinu Je-li P| A, = 0, říkáme, že systém A,, i e 7, je disjunktní. Platí-li pro každé i, j & I, i ý j, í e/ Aŕ n Aj = 0, říkáme, že množiny A,-, i e 7, jsou po dvo disjunktní Nyní ukážeme, že sjednocení a průniky libovolných systémů množin mají zcela analogické vlastnosti jako odpovídající operace s konečně mnoha množinami. Následující tvrzení jsou zřejmá. 1.2. Veta. Buďte I ^ 0, M libovolné množiny, Ai, 5,- buďte množiny pro každé i e 7. Pak platí: Průnikem množin aŕ, i e 7, nazýváme množinu 52 1. Základní operace na systémech množin 53 (a) P| Ai c Ai c |J Aŕ pro fazží/e i e 7; re/ ŕe/ (b) n^nB^flAinflfii; re/ re/ re/ (c) U^US^UAíUUS,-; re/ re/ re/ (d) n a,- u n Bi = n(Ai u b}) c p(Aŕ u b,o ; /e/ í e/ í, j i e/ (e) U Aŕ n U b,- = U(Aŕ n b,-) 2 U(A; n b,); /e/ í e/ i, j i e/ (f) P|(M U A,) = M U P| Aŕ; ŕe/ ŕe/ (g) U(^nAi) = MnUAŕ; ŕe/ ŕe/ (h) M c Aŕ pra ikaží/e i e / =^ M c f| Aŕ; ŕ e/ (i) Aŕ c M pro každé i £ / =>• U A, c M. ŕe/ Distributivní zákony (f), (g) ve větě 1.2 lze zobecnit následujícím způsobem. 1.3. Věta. Budí ý 0 libovolná množina, buď Ti ý 0 množina pro každé i £ /. Položme M = [JTí, K = {X; X c M a pra fazžde i e 7 p/aďX n 7] ^ 0}. ŕe/ Buď konečně Ai množina pro každé t £ 7], i £ 7. 7>a& platí: (!) H U Ař = U H Ař; ŕe/íer; ZeZíeZ (2) u n a, = n u a,. ŕe/íer; XčK tčX Důkaz. Dokážeme například tvrzení (2). Důkaz vztahu (1) je zcela analogický. I. Bud'x e (J f| A, libovolný prvek. Pak existuje i'o e 7 tak, že x e P A,, tj. x e Ař ŕe/íer; íerio pro každé f e 7^0. Buď X & K libovolná množina. Podle definice množiny K je X n 7^0 7^ 0, tj. existuje to e X íl 7;,. Podle předpokladu platí x e A,0 a tedy tím spíše x e |J A,. Protože íeZ poslední vztah nastává pro každou množinu X e K, plyne odtud x e P |J A,. Dokázali XčK íeX jsme tak, že |J p At c p (J Ar. ŕe/íer; XčK t£X 54 II. ZÁKLADNÍ MNOŽINOVÉ POJMY II. Nyní zvolme libovolně x £ H U At. Pak pro každou množinu X e K platí x £ [J A,, XčK t£X íeX takže v každé množině X £ K existuje t £ x tak, že x e Ař. Položme ľe (í;íéM,i^A,). Pak zřejmě Y <£ K, takže existuje i'o £ / tak, že Y n 7;0 = 0. To však znamená, že pro každé t £ Ti0 platí x e Aí5 tj. x e P| A, a tím spíše x e U P| Ař. Dokázali jsme tak i opačnou inkluzi n U A, c u n XčK t£X i£l tčTi Formulace zobecněného komutativního i zobecněného asociativního zákona je podstatně jednodušší. Důkazy jsou snadné a proto je přenecháme čtenáři. 1.4. Věta. (Zobecněný komutativní zákon) Budí ý $ libovolná množina, A,- buď množina pro každé i £ I. Buď f: I -> / bijekce. Pak platí: (jA!=|jA/(!), f|A! = f|A/(!). re/ re/ re/ re/ 1.5. Věta. (Zobecněný asociativní zákon) Buď I ý 0 libovolná množina, buď {Jť, k £ K] rozklad na množině I. Bud'A, množina pro každé i £ 7. 7>a& platí: u*=uu*. o=nrv.- re/ k€K íěJ/c re/ IcěKíěJic Pro systémy množin lze snadno uvést i de Morganova pravidla. 1.6. Věta. (De Morganova pravidla) Buď A libovolná množina, buď 7?, množina pro každé i £ /, kde 7^0. Pak platí: (a) A - U Bi = p(A-Bi); (b) A - H B,- = U(A-Bi)- í e/ í e/ Důkaz. Důkazy obou tvrzení jsou zcela analogické. Dokážeme proto jen tvrzení (a): x e A - (J 7?,- [x e A A x ^ (J 7?,-] [x e A A pro každé i £ 7 je x ^ 7?,] 4» Ví £ re/ re/ £ 7: x £ A — 7?,- x £ Q(A — Bi). • re/ Ponecháme čtenáři, aby si promyslel, jak právě uvedená de Morganova pravidla souvisejí s pravidly (12) a (13) ve větě 3.15. Nyní zobecníme pojem kartézského součinu konečného počtu množin. 1.7. Definice. Buď 7^0 libovolná množina, A, buď množina pro každé i £ 7. Kartézským součinem množin A,, i £ 7, nazýváme množinu 0 At := {/; /: 7 -> (J A,-, /(i) £ Ar pro každé i £ 7}. re/ re/ 1. Základní operace na systémech množin 55 1.8. Poznámka, (a) Je-li v definici 1.7 I množina všech přirozených čísel, píšeme místo (g) A, ieN oo symbol (g A,. Podle definice je tento kartézský součin množina všech posloupností (ar)^i ! = 1 takových, že a, £ A, pro každé i £ /. (b) Nechť / = {1, 2}. Kartézské součiny (g A, a Aj x A2 nejsou formálně totožné, neboť prvky součinu (g A, jsou některá zobrazení množiny I do množiny A\ u A2, prvky Aj x A2 re/ jsou všechny uspořádané dvojice [x, j] takové, že x e A\, y £ A2. Je však zřejmé, že když každému prvku [x, y] £ A\ x A2 přiřadíme to zobrazení / e (g A,, pro které platí /(l) = x, re/ /(2) = v, dostáváme bijekci mezi oběma kartézskými součiny. Rozdíl mezi těmito formálními zápisy kartézského součinu není tedy podstatný a budeme jej nadále zanedbávat. (c) Nechť jsou si v definici 1.7 všechny množiny A, navzájem rovny, tj. A, = A pro každé i £ I. Z definice pak plyne, že (g A, = (g A je množina všech zobrazení množiny I do re/ re/ množiny A, tj. množina, kterou značíme A1. Z definice kartézského součinu je zřejmé, že platí: 1.9. Věta. Buď I ý 0> A,- buď množina pro každé i £ 7. ye (g A, =0 právě tehdy, když, re/ A,- = 0 pro některé i £ /. Důkaz. Vzhledem k tomu, že je důkaz jednoduchý, přenecháme jej čtenáři. Poznamenejme pouze, že k důkazu tvrzení, že z neprázdnosti množin A, plyne neprázdnost kartézského součinu, je nutno užít axiómu výběru (viz §4). • 1.10. Věta. (Distributivní zákon) Buď A ý 0 množina, Ba ý 0 buď množina pro každé a e A. Pro každé |J |J Ca/? a pro každé a e A platí (p(a) e £ U A„^] •<=>■ [Vor £ A: 3/3 £ 5„ tak, že q>(a) £ Ca/3] •<=>• [Vor £ A: £ (g CaK(a) <í=^ q> £ |J (g Cffy(ff). • aeA yeTaeA 56 II. ZÁKLADNÍ MNOŽINOVÉ POJMY Cvičení k §1 Nevěř na zázraky — spoléhej na ně. Šestá Finaglova zásada 1. Buďte X, Y, T množiny, F:T -> P(X), f:X -> Y. Dokažte, že platí: a) /(U F (t)) = U f [F (t)]; Vier / t£T b) f (íl F (t)) c p f[F(t)\ Ver / t€T 2. Dokažte, že když je zobrazení / injektivní, lze ve cvičení 1 (b) psát místo inkluze rovnost. 2 Dobře uspořádané množiny Nikdy předem nezdůrazňujte, Ž.e se chystáte říci něco významného. rossův zákon Jak v dalším uvidíme, budou hrát dobře uspořádané množiny v dalším textu významnou roli. 2.1. Definice. Uspořádaná množina se nazývá dobře uspořádaná, když každá její neprázdná podmnožina obsahuje nejmenší prvek. 2.2. Věta. Buď A dobře uspořádaná množina. Pak platí: (a) A je řetězec; (b) je-li A ý 0, obsahuje A nejmenší prvek; (c) je-li B c A, je B (s indukovaným uspořádáním) dobře uspořádaná; (d) je-li B = A, je B dobře uspořádaná; (e) buď x e A libovolný prvek. Není-li x největší prvek v A, existuje v A prvek y, který pokrývá prvek x (t j. y je bezprostřední následovník prvku x ). Důkaz. 2. Dobře uspořádané množiny 57 (a) Buďte x, v e A libovolné. Podle definice obsahuje množina {x, y] nejmenší prvek, takže prvky x, y jsou srovnatelné. (b) Tvrzení plyne z definice 2.1. (c) Buď B c A libovolná. Je-li 0^Xcfí libovolná, je X c A a podle definice X obsahuje nejmenší prvek. Je tedy 5 dobře uspořádaná. (d) Tvrzení je zřejmé. (e) Pro libovolný prvek x e A označme E(x) = {t; t e A, f > x}. Není-li x největší prvek v A, je E(x) ý 0 (neboť podle (a) je A řetězec), takže E(x) obsahuje nejmenší prvek íq. Nyní je zřejmé, že prvek to pokrývá prvek x. 2.3. Věta. Řetězec A je dobře uspořádaný právě tehdy, když, každý jeho klesající řetězec je konečný, tj. každá množina {x\, x2, ■ ■ .} ^ A taková, ž,ex\ > x2 > ■ ■ ■ > xn > . .., je konečná. Důkaz. I. Nechť každý klesající řetězec v A je konečný. Ukážeme, že A je dobře uspořádaná. Buď 0 ^ B c A libovolná. Potřebujeme dokázat, že B obsahuje nejmenší prvek. Zvolme i! e S libovolně. Je-li x\ nejmenší prvek B, je důkaz hotov. Není-li x\ nejmenší, existuje x2 e B, x2 < x1; neboť A je řetězec. Není-li x2 nejmenší v B, existuje X3 e B, X3 < x2 atd. Indukcí lze takto v B definovat klesající řetězec x\ > x2 > X3 > ..., který však podle předpokladu musí být konečný. Odtud již plyne, že B obsahuje nejmenší prvek. II. Nechť v řetězci A existuje nekonečný klesající řetězec x\ > x2 > ... . Pak množina 0 ý {x\, x2, ... x„, ...} c A neobsahuje nejmenší prvek, takže A není dobře uspořádaná množina. • Z věty 2.3 okamžitě plyne 2.4. Důsledek. Každý konečný řetězec je dobře uspořádaný. 2.5. Věta. Buď A dobře uspořádaná množina, buď B c A taková, ž.e existuje izomorfismus f: A —>- B. Pak pro každý prvek x e A platí x < f (x). Důkaz. Označme K = {x; x e A, f (x) < x} a připusťme, že K ý 0. Pak K obsahuje nejmenší prvek xo. Položme x\ = f(xo). Protože je xq e K, je /(xo) = x\ < xq. Protože je / izomorfismus, je f(x\) < f(xo) = x1; tj. x\ e K. To je však spor, neboťxq je nejmenší prvek množiny K. Je tedy K = 0. • 58 II. ZÁKLADNÍ MNOŽINOVÉ POJMY 2.6. Definice. Buď A libovolná uspořádaná množina. Množina X c A se nazývá začátek množiny A, když pro každý prvek t e X platí {w; m e A, m < t] c X. Začátek X c A se nazývá vlastní začátek množiny A, je-li X 7í A. 2.7. Věta. Dobře uspořádaná množina není izomorfní s žádným svým vlastním začátkem ani s jeho žádnou podmnožinou. Důkaz. Buď A dobře uspořádaná množina, B buď vlastní začátek v A. Pak je B c A, takže A — B ý 0. Množina A — B obsahuje nejmenší prvek oq. Je zřejmé, že a$ je horní závora množiny 5, ao ^ 5. Připusťme, že existuje X c B tak, že A = X. Buď /: A -> X izomorfismus. Pak je /(ao) £ X c 5, tj. /(ao) < ao> což podle věty 2.5 není možné. • 2.8. Důsledek. Buď A dobře uspořádaná množina, buďte B, C začátky v A. Je-li B = C, pak je B = C. Důkaz. Je-li B = A, B = C, je B = C podle věty 2.7. Buďte B, C vlastní začátky v A. Je-li B ý C, je buďto B vlastní začátek v C nebo C vlastní začátek v B. Pak ale B, C nemohou být podle věty 2.7 izomorfní. • 2.9. Označení. Buď A uspořádaná množina, x e A buď libovolný. Klademe A(x) = {t; t e A, t < x}. Je zřejmé, že pro každý prvek x e A je A(x) ý A a A(x) je začátek v A. Dále je zřejmé, že platí: 2.10. Lemma. Buď A dobře uspořádaná množina, B c A buď vlastní začátek v A. Pak existuje x e A tak, že B = A(x). 2.11. Věta. Buďte A, B dobře uspořádané množiny. Je-li A = B, existuje právě jeden izomorfismus f: A -> B. Důkaz. Buďte /: A —> B, g: A —> B izomorfismy a připusťme, že / ý g. Pak existuje xo e A tak, že /(xo) ^ g(xo). Protože je / izomorfismus, je A(xo) = B(/(xo)); protože je g izomorfismus, je A(xo) = B(g(xo)), takže B(/(xo)) = B(g(xo)). Podle důsledku 2.8 je pak ale B(f(x0)) = B(g(x0)), tj. /(x0) = g(x0): spor. • 2.12. Poznámka. Z předcházejícího je již zřejmé, že dobře uspořádané množiny jsou řetězce s jistými vlastnostmi. Podle důsledku 2.4 je každý konečný řetězec dobře uspořádaný, nekonečný řetězec je však dobře uspořádaný jen v některých případech. Například řetězec N všech přirozených čísel je dobře uspořádaný, ale řetězce Z, Q, respektive R dobře uspořádané nejsou. 2. Dobře uspořádané množiny 59 Následující věta udává, že struktura dobře uspořádaných řetězců je dokonce v jistém slova smyslu jednoznačně předepsána. 2.13. Věta. Buďte A, B dobře uspořádané množiny. Pak nastane právě jedna z. následujících možností: (1) A = B; (2) A = B(x) pro vhodný prvek x £ B; (3) B = A(x) pro vhodný prvek x £ A. Důkaz. Buďte A, B dobře uspořádané množiny. Řekneme, že prvek x e A je normální, jestliže existuje prvek y & B takový, že A(x) = B(y). Označme G = {x; x e A, x je normálni}. Zcela analogicky definujeme množinu H = {x; x e B, x je normálni}. Je-li A = 0 nebo 5 = 0, je tvrzení věty triviální. Nechť tedy A ^ 0 ý B. Pak je také G ý 0 ý H, neboť nejmenší prvek množiny A, respektive B je evidentně normální. Dále je zřejmé, že G je začátek v A a H je začátek v B. Podle lemmatu 2.10 to však znamená, že je G = A nebo G = A(ao) pro vhodný prvek ao £ A a analogicky H = B nebo // = 5(&o) pro vhodný prvek bo & B. Nyní dokážeme, že je G = H. Definujme zobrazení f.G—>H takto: pro x e G buď /(x) = j ten prvek v H, pro který platí A(x) = 5(y). Pak je zřejmě / izomorfismus G na H. Nyní mohou nastat čtyři možnosti. (a) G = A, íř = B. Pak je však A = B, takže platí (1). (b) G = A,H = B(b0). Pak je A = B(b0), tj. platí (2). (c) G = A(a0), H = B. Pak je 5 = A(a0), tj. platí (3). (d) G = A(oo), H = B(b0). Je však zřejmé, že poslední případ ve skutečnosti nastat nemůže. Ze vztahu G = H totiž plyne A(oq) = B(bo), takže ao e G, bo e íř a to není možné. • 2.14. Poznámka. Je-li A konečná množina, lze na ní jednoduše definovat uspořádání < tak, aby (A, <) byla dobře uspořádaná. Podle důsledku 2.4 stačí za relaci < zvolit jakékoliv úplné uspořádání. Je tedy přirozená otázka, zda lze dobré uspořádání definovat na každé množině. Odpověď na tuto otázku dal Ernst ZERMELO (viz věta 4.7). Vzhledem k potížím spojeným s důkazem Zermelova tvrzení tento stav objasníme v §4. V závěru tohoto paragrafu uveďme jednu z nejdůležitějších aplikací dobře uspořádaných množin, tak zvaný princip transfinitní indukce. Ze střední školy známe důkazovou metodu nazývanou úplná indukce (nebo též matematická indukce). Touto metodou se nejčastěji dokazují vzorce, formule apod., které mají být pravdivé pro všechna přirozená čísla. Připomeňme si, že důkaz úplnou indukcí spočívá v tom, že důkaz výroku (Vra e N) y (ji) se provede ve dvou krocích: 60 //. ZÁKLADNI MNOŽINOVÉ POJMY (1) V(l), (2) (V/i e N) (V(n) =>• V(n + 1)). Poněvadž množina N všech přirozených čísel je dobře uspořádaná, je zřejmé, že úplná indukce je speciálním případem následujícího tvrzení. 2.15. Věta. (Princip transfinitní indukce) Bud'W dobře uspořádaná množina s nejmenším prvkem xq. Bud' P(x) výroková funkce o jedné proměnné s definičním oborem W. Nechť platí: (1) P(xq) je pravdivý výrok; (2) pro každý prvek x £ W platí: je-li P (t) pravdivý výrok pro každý prvek t £ W, t < x, je také P (x) pravdivý výrok. Pak je P (x) pravdivý výrok pro každý prvek x € W. Důkaz. Nechť jsou splněny předpoklady věty. Připusťme, že množina W = {x; x e W, P (x) je nepravdivý výrok} je neprázdná. Protože W je dobře uspořádaná, obsahuje W nejmenší prvek jo- Je Jo > xo, neboť P(xq) je pravdivý výrok. Pro každé t & W,t < jo, je P(t) pravdivý výrok, takže podle předpokladu je také P (jo) pravdivý výrok: spor. Je tedy W = 0. • 2.16. Poznámka. V kapitole III uvidíme, že množina W při transfinitní indukci je obvykle nějaká množina tzv. ordinálních čísel. Uvědomme si také, že transfinitní indukci lze užít nejen k důkazům, ale i v definicích, respektive při popisu konstrukcí apod. Chceme-li totiž definovat objekt f (a) pro každé a e W (W je dobře uspořádaná množina s nejmenším prvkem xq), stačí podle věty 2.15 definovat objekt f(xo) a udat předpis, jak objekt f (a) definovat pomocí všech P e W, p < a. 3 Aritmetika uspořádaných množin / ta nejjednodušší myšlenka se dá vyjádřit složitě. Malekův zákon Nyní jednoduše zavedeme početní operace pro uspořádané množiny. 3.1. Definice. Buďte (G, < q), (H, < H) disjunktní uspořádané množiny. Jejich součtem G + H nazýváme uspořádanou množinu (GUH, <), na níž je uspořádání < definováno takto: Pro x, y e G U H platí x < y právě tehdy, když nastane jedna z možností: (1) x, y e G, x < g y; (2) x, y e H, x < h y ; (3) x e G, j e H. 3. Aritmetika uspořádaných množin 61 Relaci < definovanou v 3.1 můžeme vyjádřit takto: < = < g U < h U (G x H). Je však třeba dokázat, že uvedená definice je správná, tj. že G + H je vskutku uspořádaná množina. 3.2. Věta. Relace < definovaná v 3.1 je uspořádám na množině G U H. Důkaz. Musíme dokázat, že relace < je reflexivní, antisymetrická a tranzitivní. (a) Reflexivita: Buď x e G U H libovolný. Je-li x e G, platí x < q x, neboť < q je uspořádání na G a tedy je reflexivní. Podle definice relace < však odtud plyne x < x. Podobně postupujeme v případě x e H. (b) Antisymetrie: Buďte x, y e G U H libovolné takové, že x < y a y < x. Je-li x e G, j e G, platí x < Gy a y < q x. Protože je < G antisymetrická, plyne odtud x = y. Podobně obdržíme x = y i v případě, že x & H, y & H. Přitom není možné, aby například x e G, y & H, neboť v tomto případě nemůže platit y < x (vzhledem k předpokladu, že G n H = 0). Tím je antisymetrie relace < dokázána. (c) Tranzitivita: Buďte x, y, z e G U H libovolné takové, že x < y a y < z. Je-li x, y, z e G, respektive x, y, z e Tí, vyplývá platnost vztahu x < z okamžitě z tranzitivity relace < G , respektive < H . Nechť tedy neleží všechny prvky x, y, z v G, respektive v H. Vzhledem ke (3) v definici 3.1 je okamžitě zřejmé, že nutně platí x, y e G,z e Hnebox e G, j, z e //.V obou těchto případech však podle (3) platí x < z a relace < je tranzitivní. • 3.3. Příklad. Na obrázku 1 jsou hasseovské diagramy uspořádaných množin G, H a součtů G + H a H + G. G+H H+G Obr. 1 3.4. Poznámka. Z příkladu 3.3 je zřejmé, že operace + definovaná v 3.1 obecně není komutativní. Komutativní zákon neplatí ani v zeslabeném tvaru G + H = H + G. V dalším však ukážeme, že operace + je asociativní. 62 II. ZÁKLADNÍ MNOŽINOVÉ POJMY Definici 3.1 nyní zobecníme následujícím způsobem: 3.5. Definice. Buď 7^0 uspořádaná množina, buď G, uspořádaná množina pro každé i e 7. Nechť jsou množiny G i, i £ 7, po dvou disjunktní. Součtem G, množin G, přes re/ množinu 7 rozumíme uspořádanou množinu ([J G,■, <) s uspořádáním < definovaným takto: ie/ pro x, y £ U G,- platí x < y právě tehdy, když nastane jedna z následujících možností: ie/ (1) existuje i'o £ 7 tak, že x e G,0, j e G,0 a x < y v G,0; (2) x e d, y e G j a i < j y I. Podobně jako ve větě 3.2 bychom nyní měli dokázat, že relace < definovaná v 3.5 je uspořádání na množině U G,. Vzhledem k tomu, že důkaz věty 3.2 lze snadno přeformulovat ŕe/ i pro tento obecnější případ, přenecháme jeho provedení čtenáři. 3.6. Příklad. (a) Součet definovaný v 3.1 je zřejmě speciálním případem definice 3.5; odpovídá případu, kdy 7 je dvouprvkový řetězec. (b) Buď 7 = {a, b, c] uspořádaná množina s hasseovským diagramem na obrázku 2a, Ga,Gb, G c buďte uspořádané množiny s diagramy na obrázcích 2b, 2c, 2d. Na obrázku 2e je hasseovský diagram množiny G,. ŕe/ a) b) c) d) e) Obr. 2 3.7. Věta. f Asociativní zákon) Buď I ý $ uspořádaná množina, buďte G i, i e I, po dvou disjunktní uspořádané množiny. NechťI = Jk- Pak platí: kčK ŕe/ k€K íe/jt 3. Aritmetika uspořádaných množin 63 Důkaz. Množinová rovnost obou stran dokazovaného vztahu plyne z věty 1.4. Dokážeme rovnost uspořádání. Nechť tedy x, y e Y Existuje-li i'o e /, tak, že x e G,0, y e G,0, je zřejmě x < y í e/ v XI G, právě tehdy, když x < v v Y Yl Gi- Nechť tedy x e G,, y e G j, i < j v I. i€l k€K ŕe/jt Existuje-li ko & K tak, že i, y e /^0, je tvrzení zřejmé. Nechť tedy i e J^, j & Je, k < £ v K. Pak je x < y v X G, právě tehdy, když i < j. Avšak i < j v I právě tehdy, když k < £v K, re/ tj- x < y v Y Yl G i - Tím je věta dokázána. • k€K íe/jt Zvolíme-li ve větě 3.7 za / speciálně tříprvkový řetězec, plyne z ní 3.8. Důsledek. Buďte A, B,C libovolné po dvou disjunktní uspořádané množiny. Pak platí: (A + B) + C = A + (B + C). 3.9. Definice. Buďte (G, < q), (H, < H) uspořádané množiny. Jejich součinem G ■ H rozumíme uspořádanou množinu (G x H, <) s uspořádáním < definovaným takto: [xi, yi] < [x2, y2] v G ■ H <í=^> (l)yj < H y2 nebo _(2)yi = y2, X! < Gx2._ 3.10. Věta. Relace < definovaná v 3.9 je uspořádání na množině G x H. Důkaz, (a) Reflexivita relace < je zřejmá z definice. (b) Nechť [x\, y\] < [x2, y2] a současně [x2, y2] < [xj, yj]. Vzhledem k antisymetrii relace < H není možné, aby yj ^ y2. Pro yj = y2 však z antisymetrie relace < G okamžitě plyne x\ = x2. To znamená, že i relace < je antisymetrická. (c) Nechť[x!, yj < [x2, y2] a [x2, y2] < [x3, y3]. Je-li y1 < y2 < y3, plyne vztah [xb yj < < tx3> j3] z tranzitivity relace < H . Je-li yj = y2 = y3, plyne uvedený vztah z tranzitivity relace < G . Je-li yj = y2, y2 < y3, platí y1 < y3 a tedy [xj, yj < [x3, y3]. Podobně v případě y1 < y2, y2 = y3. Žádný další případ evidentně nastat nemůže, takže relace < je tranzitivní. • 3.11. Příklad. Na obrázku 3 jsou hasseovské diagramy uspořádaných množin G, H a jejich součinů G • H a H ■ G. 64 II. ZÁKLADNÍ MNOŽINOVÉ POJMY GH HG a) b) c) d) Obr. 3 3.12. Poznámka. Z příkladu 3.11 plyne, že ani násobení uspořádaných množin není obecně komutativní, a to ani v zeslabeném tvaru G • H = H • G. Podobně jako pro operaci + však i pro násobení platí asociativní zákon. 3.13. Věta. Buďte G, H, K libovolné uspořádané množiny. Pak platí (G ■ H) ■ K = G ■ (H ■ K). Důkaz. Množinová rovnost obou stran dokazovaného vztahu je zřejmá. Podle definice 3.9 platí [xi,yi, zi] < [x2, y2, z2] v (G • H) ■ K právě tehdy, když je zi < z2 nebo zi = z2, [xi, Ji] < [x2, yi\- Avšak [x\, yi] < [x2, y2] v G H právě tehdy, když je yi < y2neboy! = y2, x\ < x2. Přesně tytéž vztahy však platí, jestliže je [x1; y1; zi] < [x2, y2, z2] v G • (H ■ K). Odtud plyne, že v obou množinách (G • H) ■ K a G • (H ■ K) je definováno stejné uspořádání. • 3.14. Věta. (Levý distributivní zákon). Buďl ^ 0 uspořádaná množina, buďte G, Hi (i e I) uspořádané množiny. Nechť jsou množiny Hi po dvou disjunktní. Pak platí g-J2h' = T,g-h'- Důkaz. Množinová rovnost obou stran dokazovaného vztahu je zřejmá. Dokážeme rovnost uspořádání v obou množinách. Nechť tedy platí [xj, yj < [x2, y2] v G • Yl Hi- Pak nastane jedna z následujících dvou možností: (1) yi < y2 v Hi\ (2) yi = y2 A xi < x2 v G. Nechť nastane případ (1). Pak buď (la) existuje i0 e I tak, že y1,y2 e Hio ay1 < y2 v Hio, nebo (lb) yj e Hi, y2 e Hj a i < j v I. V obou případech (la) i (lb) však dostáváme tvrzení ekvivalentní s tím, že [xj, yj < < [x2, y2] v J2G ■ H- 3. Aritmetika uspořádaných množin 65 Nechť tedy nastane případ (2). Pak existuje i'o e 7 tak, že y1; y 2 £ 77,0. Tvrzení [x1; yj < < lx2, yi] v G ■ je však nyní ekvivalentní s tím, že lxi, yi] < tx2, y2] v G • 77,0 a tedy i v G • 77,. Tím je věta dokázána. • 3.15. Důsledek. Buďte G,H,K,Hf~)K = @, libovolné uspořádané množiny. Pak platí G ■ (H + K) = G ■ H+ G ■ K. 3.16. Poznámka. Pravý distributivní zákon, tj. tvrzení (5^ 7/,) ■ G = XX ^ • G) obecně neplatí. Položíme-li například G = {a}, 77 = {b}, pak G + 77 je řetězec {a < b}. Zvolíme-li nyní K = {c, d, e] tak, že hasseovský diagram uspořádané množiny (K, <) je na obrázku 3b, je zřejmě na obrázku 3c diagram množiny (G + 77) ■ K a na obrázku 3d diagram množiny G • K + H ■ K. Tyto dvě množiny však nejsou ani izomorfní. 3.17. Věta. BuďI ý 0 uspořádaná množina, buďte A{ i e I, po dvou disjunktní uspořádané množiny. Nechť existuje množina A tak, ž.e A{ = A pro každé i e I. Pak platí £> = A-/. i e/ Důkaz. Nechť pro každé i e I je g,: A, —»- A izomorfismus. Definujme zobrazení /: U A, —»- ŕ e/ A x I takto: bud'x e U A, libovolný prvek. Pak f (x) = [g,(x)> z], kde i e 7 je ten prvek, pro který platí x e A,. Pak je zřejmě / hledaný izomorfismus. • 3.18. Věta. Buď I ý 0 dobře uspořádaná množina. Buďte A,-, i e I, po dvou disjunktní dobře uspořádané množiny. Pak je A,- dobře uspořádaná množina. íe/ Důkaz. Buď 0 5 c £ Aŕ libovolná. Označme 7B = {/; i e 7, B d Aŕ 7í 0}. Pak je ŕe/ 0 7^ 7b c 7, takže 7# obsahuje nejmenší prvek íq. B d A,0 je nyní neprázdná podmnožina v A,0, takže 5 n A,0 obsahuje nejmenší prvek b. Je však zřejmé, že b je nejmenší prvek množiny B. • 3.19. Důsledek. Buďte A, B disjunktní dobře uspořádané množiny. Pak je A + B dobře uspořádaná množina. Z věty 3.18 a důsledku 3.19 plyne 3.20. Věta. Buďte G, H dobře uspořádané množiny. Pak je také množina G ■ H dobře uspořádaná. 3.21. Důsledek. Buďte G, H konečné řetězce. Nechť má řetězec G m prvků, a řetězec H nechť má n prvků. Pak je G ■ H řetězec obsahující m ■ n prvků. 66 II. ZÁKLADNÍ MNOŽINOVÉ POJMY 4 Axióm výběru a věty s ním ekvivalentní Neodpovídají-li fakta vaší teorii, je třeba se jich co nejrychleji zbavit. MAIERŮV ZÁKON V kapitole I jsme viděli, jak se postupuje při axiomatické výstavbě teorie množin a jak vypadají axiómy. V různých axiomatických teoriích jsou samozřejmě za axiómy volena odlišná tvrzení, vesměs jsou však axiómy vcelku jednoduchá tvrzení a proti jejich volbě nejsou vznášeny žádné principiální výhrady. Jedinou výjimkou je právě tak zvaný axióm výběru, někdy též nazývaný Zermelův axióm. V tomto paragrafu si ukážeme některé těžkosti s tímto axiómem spojené. Podrobněji budeme o axiómu výběru hovořit ještě v kapitole IV, §4. Nejprve si však ukažme, jaké důvody vedly k formulaci tohoto axiómu. 4.1. Příklad. (a) Buďte A, B, C, D následující množiny: A = {a, b, c}, B = {a, f g, h}, C = {c, d, e, f}, D = {a, f k}. Potřebujeme-li sestrojit množinu M takovou, že M c AUSUCUDa průnik množiny M s každou z množin A, B, C, D jejednoprvkový, můžeme zvolit například M = {b, e, g, k] nebo M = {a, e] a podobně. (b) Buď 7^0 libovolná množina, buďte A, ^ 0, i e I, po dvou disjunktní dobře uspořádané množiny. Pak můžeme bez potíží definovat množinu M s následujícími vlastnostmi: (i) M c (J Au (ii) pro každé i e / je M íl A, jednoprvková množina. Lze to udělat například tak, že množinu M utvoříme z nejmenších prvků všech množin Ai. Množina M je v obou případech definována tak, že jsme z každé ze zadaných množin vybrali jeden prvek. 4.2. Příklad. Definujme na množině R všech reálných čísel relaci q takto: q := {[x, y]; x e R, j e R, x — y je racionálni číslo}. Pak je zřejmě q ekvivalence na R. Utvoříme-li faktormnožinu R/g, je ihned vidět, že R/g> je nekonečná množina a každá třída rozkladu R/g> je rovněž nekonečná množina. Chceme-li nyní sestrojit množinu M analogicky jako v příkladech 4.1, je ihned vidět, že nelze vůbec podat konstrukci této množiny. Chceme-li vůbec tvrdit, že existuje množina M taková, že 4. Axióm výběru a věty s ním ekvivalentní 67 (i) M c R, (ii) pro každý prvek x e R/q je M n X jednoprvková množina, nelze toto tvrzení v běžných axiomatických systémech vůbec odvodit bez axiómu výběru. Nyní tedy axióm výběru zformulujeme. Nebudeme uvádět jeho symbolický zápis, pouze budeme tento zápis slovy interpretovat. Axióm výběru. Buď A ý 0 libovolná množina, buď{Ma, t }. Pak je zřejmě C = A neboje [A — C, C] řez v A. V obou případech však C obsahuje nejmenší prvek, který je zřejmě nejmenším prvkem množiny B. Je tedy množina A dobře uspořádaná. • Důkaz Zermelovy věty. Buď M libovolná množina. Je-li M konečná, lze ji podle poznámky 2.14 dobře uspořádat, takže není co dokazovat. Buď tedy M nekonečná. Označme M = {X; X c M, X 7^0}. Podle věty 4.3 vybereme z každé množiny X e M jeden prvek f(X). Tento prvek nazveme vyznačený prvek množiny X. Je-li A c M libovolná, nazveme připojeným prvkem k množině A vyznačený prvek množiny M — A a označíme jej p a- (Tj. p a = f(M — A).) Konečně pro každou A c M nazveme množinu A+ = A U {pA} následovníkem množiny A. Protože je pA £ A, je A c A+. 70 II. ZÁKLADNÍ MNOŽINOVÉ POJMY Nyní zavedeme následující označení: systém A c P (M) podmnožin v M nazveme řetězem v M, když platí: (1) 0 e A; (2) je-li 0 ý o Je nejmenší řetěz v M. Zřejmě je 0 e N(Aq), takže N(Aq) splňuje podmínku (1). Buď 0 ^ B. 1.2. Poznámka. Je zřejmé, že když A je konečná množina, platí A ~ B právě tehdy, když i B je konečná množina a obě množiny mají stejný počet prvků. 1.3. Příklad. (a) Množina N všech přirozených čísel je ekvivalentní s množinou S všech sudých čísel, neboť zobrazení /: N -> S definované vztahem f (x) = 2x je zřejmě bijekce. (b) Buďte a\ < a2, b\ < bi libovolná reálná čísla. Pak jsou intervaly (a\,a2), (^1,^2) ekvivalentní, neboť zobrazení /: (a\, a^) —> (b\, bj) definované vztahem ž»2 — b\ f (x) = -(x - aj) + bi a2 — a\ je zřejmě bijekce. 1.4. Věta. Buďte A, B, C libovolné množiny. Pak platí: 73 74 ///. KARDINÁLNÍ A ORDINÁLNÍ ČÍSLA (1) A ~ A; (2) A ~ B =>• B ~ A; (3) A~fiAfi~C4A~C. Důkaz. Tvrzení jsou zřejmá, neboť idA je bijekce, je-li f:A—>B bijekce, je také f^1. B —> A bijekce, a konečně, jsou-li f:A—>B,g:B—>C bijekce, je g o f: A —> C bijekce. • 1.5. Věta. Budí ^0 množina, A,-, 7?, (i e 7), A, 5, C buďte libovolné množiny. Pak platí: 1. Je-li f:I—>I bijekce, pak (g A, ~ (g Ay(i), zejména (A x 5) ~ (5 x A). re/ re/ 2. Nechť pro každé i £ 7 platí A t ~ 7?,. Pa^ (g A, ~ (g 7?,. re/ re/ 3. A ~ B P(A) ~ ^(5). 4. Jsou-li množiny A{ i množiny 7?,- /?o dvow disjunktní a platí-li A,- ~ 5,- pro každé i £ 7, p/aň'|J Ai ~ U 5ŕ- ŕe/ ŕe/ 5. Jsou-li množiny Ai po dvou disjunktní, pak Ai£í ~ (g A '; zejména pro disjunktní í e/ množiny B, C platí ABUC ~ (AB x Ac). 6. ABxC ~ (AB)C 7. ((g) Aŕ)B ~ (g) Af, zejména (A x 5)c ~ (Ac x Bc). ŕe/ ŕe/ Důkaz. Důkazy vztahů (1) - (4) jsou jednoduché a proto je nebudeme uvádět. (5) Pro každý prvek (p e Ai£í , tj. (p: U A, -> A, označme , pro které platí /(/) = (pt. Pak je zřejmě F požadovaná bijekce. (6) Buď / e aBxC libovolný prvek. Pro každý prvek c e C definujme zobrazení gc: B —> —> A, tj. prvek množiny AB, takto: gc(x) = f(x, c) pro každý prvek x e B. Defmujeme-li nyní F (y) = gy pro každý prvek y e C, je F.C —> AB, tj. F e (AB)C. Nyní je však zřejmé, že 1. Kardinální číslo. Spočetné množiny 75 zobrazení, které každému prvku / e A c přiřadí takto zkonstruované zobrazení F, je bijekce množiny ABxC na množinu (AB)C. (7) Buď / e ((g) Ai)B libovolný prvek. Pro každý prvek b e B je /(Z?) prvek množiny re/ (g) Aŕ,tj. f(b) = fb:I —> y A,-, přičemž ft(i) £ A, pro každé/ e /.Definujme nyní zobrazení re/ re/ fi\ B ^ At takto: = pro každý prvek b e 5. Zobrazení F: ((g) A,)B -> (g) Af definované vztahem F (/)(/) = /) je pak evidentně bijekce. • 1.6. Definice. Řekneme, že množina je spočetná, je-li ekvivalentní s množinou všech přirozených čísel. Množina, která je konečná nebo spočetná, se nazývá nejvýše spočetná. 1.7. Poznámka. Je-li A spočetná množina, existuje podle definice 1.1 bijekce /: N —> A. Takové funkce /, pro něž je Dom / = N, se nazývají posloupnosti. Lze tedy říci, že množina A je spočetná, lze-li její prvky uspořádat do posloupnosti. 1.8. Věta. Každá podmnožina spočetné množiny je nejvýše spočetná. Důkaz. Buď A spočetná množina. Podle poznámky 1.7 je tedy A = (a„)^r Buď B c A libovolná podmnožina. Buď ti\ nejmenší přirozené číslo takové, že ani e B, «2 nejmenší přirozené číslo takové, že «2 > n\ a a„2 e B atd. Posloupnost (a„k) je buďto konečná a tedy B je konečná, nebo je nekonečná a to znamená, že B je spočetná. • 1.9. Věta. Budí nejvýše spočetná množina, bud'A,- nejvýše spočetná množina pro každé i £ /. Pak je množina [J A,- nejvýše spočetná. re/ Důkaz. Je zřejmé, že stačí dokázat, že když je / spočetná a všechny A, jsou spočetné, pak je také U A, spočetná. V tomto případě můžeme bez újmy na obecnosti předpokládat, že / = N. re/ Každou z množin A, lze podle předpokladu uspořádat do posloupnosti takto: ^i = {^ii, ai2, . .. , a\n, . ..} M = {au, Q-22, ■ ■ ■ ,d2n, ■ ■ ■} A-n Cln2, . . . , ann, . . . } Pak je ale [J Ai = {au, a\2, a2\, a^, a22, a^i, í*i4, <223> a32> a4i> ■ ■ ■ L takže množina [J Ai je re/ re/ spočetná. • 76 777 KARDINÁLNÍ A ORDINÁLNÍ ČÍSLA 1.10. Důsledek. Množina všech celých čísel je spočetná. 1.11. Věta. Každá nekonečná množina A obsahuje spočetnou podmnožinu B takovou, ž.e množina A — B je opět nekonečná. Důkaz. Je-li množina A nekonečná, existují prvky a\,b\ £ A, a\ ýb\. Protože je A — {a\, b\\ nekonečná, existují prvky ai, bi e A — {a\, b\], ai ý bi atd. Indukcí lze zřejmě v A sestrojit dvě disjunktní spočetné podmnožiny s = K)~i> c = (bn)™1. Tím je tvrzení dokázáno. (Pozorný čtenář však jistě postřehl, že jsme v důkazu využili axiómu výběru.) • 1.12. Věta. Kartézský součin dvou spočetných množin je spočetná množina. Důkaz. Podle věty 1.5(2) víme, že když A ~ C, B ~ D, pak je A x B ~ C x D. Stačí tedy dokázat, že N2 je spočetná množina. Pro každý prvek [p, q] £ N2 nazveme výškou tohoto prvku číslo p + q. Je zřejmé, že pro každé n £ N, n > 1, existuje n — 1 dvojic výšky n: [í, n — 1], [2, n — 2], ..., [n — 1, 1]. Označme P„ = {[p, q]; [p, q] e N2, výška [p, q] je oo ra }. Pak je N2 = U P„ podle věty 1.9 spočetná. • n=2 1.13. Důsledek. Kartézský součin konečného (nenulového) počtu spočetných množin je spočetná množina. 1.14. Důsledek. Množina Q všech racionálních čísel je spočetná. Důkaz. Víme, že každé kladné racionální číslo r lze jednoznačně vyjádřit jako podíl - nesou-dělných přirozených čísel. Těchto podílů je nejvýše tolik, jako všech dvojic [p, q] e N2, tj. nejvýše spočetně mnoho. Odtud a z věty 1.9 nyní plyne tvrzení. • 1.15. Věta. Bud'A spočetná množina. Pak je množina K všech konečných posloupností prvků množiny A spočetná. Důkaz. Bud'ra e N libovolné. Podle důsledku 1.13 je množina A" všech uspořádaných ra-tic oo z prvků množiny A spočetná. Podle věty 1.9 je i množina K = U A" spočetná. • n=l 1.16. Důsledek. Množina všech polynomů (jedné proměnné) s racionálními koeficienty je spočetná. 1. Kardinální číslo. Spočetné množiny 77 Důkaz. Každému polynomu a§xn + a\xn 1 + • • • + a„_ix + a„ (oq ý 0) stačí přiřadit prvek 1.17. Poznámka. Nyní si můžeme uvést jeden z prvních dokladů toho, jak teorie množin umožnila zodpovědět problém jiné matematické disciplíny, v tomto případě teorie čísel. Reálné číslo se nazývá algebraické, je-li kořenem nějakého polynomu s racionálními koeficienty. Reálné číslo, které není algebraické, se nazývá transcendentní. Je okamžitě zřejmé, že každé racionální číslo je algebraické, stejně tak jako například čísla -J2, V3, V26 atd. Teprve v 19. století se však podařilo dokázat, že například číslo jt je transcendentní. Otázkou však bylo, kolik vlastně transcendentních čísel existuje. Teorie množin tuto otázku jednoduše vyřešila. Z faktu, že každý polynom ra-tého stupně má nejvýše n reálných kořenů a z důsledku 1.16 okamžitě plyne, že množina všech algebraických čísel je spočetná. V dalším uvidíme, že to znamená, že transcendentních čísel je „více" než čísel algebraických — viz důsledek 2.11. 1.18. Poznámka. Při formální výstavbě teorie množin lze přesně popsat, jak lze každé množině A přiřadit objekt card A, nazývaný kardinální číslo množiny A. Přitom pro každé dvě množiny A, B platí Poněvadž zde nebudeme tuto formalizovanou konstrukci uvádět, spokojíme se s konstatováním, že každé množině A lze přiřadit symbol card A tak, že je splněna výše uvedená podmínka (★). Kardinální číslo množiny A se často také nazývá mohutnost množiny A. Podle poznámky 1.2 mají dvě konečné množiny stejné kardinální číslo právě tehdy, když mají stejný počet prvků. Má tedy smysl přijmout následující označení: má-li konečná množina A n prvků, označíme card A = n. Zejména tedy card 0 = 0. Kardinální číslo spočetných množin značíme symbolem Ko — čti „alef" —je první písmeno hebrejské abecedy). (Důvod tohoto označení uvidíme v §6 - viz poznámka 6.9.) [oq, ai, ..., an] e Q' jj+i (*) Cvičení k §1 Pouze v jediném případě si můžeme být neomylně jisti: jsme-li si jisti, ž.e se mýlíme. HOLTENOVA POUČKA 1. Dokažte následující tvrzení: a) Množina všech intervalů v R, jejichž koncové body jsou racionální, je spočetná. b) Buď A nějaká množina po dvou disjunktních intervalů v R. Pak je A nejvýše spočetná. (Návod: Vyberte v každém intervalu jedno racionální číslo.) 78 KARDINÁLNÍ A ORDINÁLNÍ ČÍSLA 2. Buď / reálná funkce jedné reálné proměnné. Dokažte, že množina všech bodů, v nichž má funkce / ostrý lokální extrém, je nejvýše spočetná. (Návod: Využijte výsledku cvičení 3. Dokažte, že množina všech bodů nespojitosti monotónní reálné funkce jedné reálné proměnné je nejvýše spočetná. (Návod: Využijte cvičení l(b) a faktu, že monotónní funkce má v každém bodě limitu zleva i limitu zprava.) Následující Cantor-Bernsteinova věta patří k základním tvrzením teorie množin. 2.1. Cantor-Bernsteinova věta. Buďte A, B libovolné množiny. Existují-li množiny A\ c A, Bi c B takové, že A ~ B\, B ~ Au platí A ~ B. Důkaz. Je-li některá z množin A, B konečná, je tvrzení triviální. Buď tedy A nekonečná, f: B —> A\ buďbijekce. Je-li A\ = A, není co dokazovat. Nechť tedy je A\ C A a analogicky Bi c B. Označme A2 = f{B{). Pak platí: l(a).) 2 Nerovnost mezi kardinálními čísly Jde-li to s věcmi do háje, nikdo netuší, jak je hluboký. HANEŮV ZÁKON A2 C Aj C A, A ~ A2, B ~ Aj. (2.1.) Stačí tedy dokázat, že je A ~ Aj, neboť z tranzitivity relace ~ pak plyne A ~ B. Podle (1) existuje bijekce g: A —> A2. Pak platí: Aj c A =^ A3 := g(AO C A2, A2 c Aj =^ A4 := g(A2) C A3, A3 c A2 A5 := g(A3) C A4, Přitom platí 5(A Aj) = A2 - A3 A2) = A3 - A4 A3) = A4 - A5 Protože je g bijekce, plyne odtud ekvivalence následujících množin: 2. Nerovnost mezi kardinálními čísly 79 (A - AJ U (A2 - A3) U (A4 - A5) U ... U (A„ - An+1) U ... (A2 - A3) U (A4 - A5) U (A5 - A6) U ... U (An+1 - An+2) U ... (2.2.) Označme oo Z) := AnP|Ar. Pak je zřejmé, že platí: A = D U (A — Ai) u (Ai — A2) u (A2 - A3) u (A3 - A4) u ... Ai = D U (Ai - A2) U (A2 - A3) U (A3 - A4) U ... (2.3.) Protože pro sjednocení množin platí asociativní a komutativní zákon, lze vztahy (2.3) přepsat na tvar A = [D u (Aj - A2) u (A3 — A4) u ... ] u [(A — Aj) u (A2 - A3) u ... ] Aj = [D u (Aj - A2) u (A3 - A4) u ... ] u [(A2 - A3) u (A4 - A5) u ... ] V prvních závorkách množin A i Aj však stojí tytéž množiny, množiny ve druhých závorkách jsou podle (2.2) ekvivalentní. To však znamená, že A ~ A\, což jsme chtěli dokázat. • 2.2. Definice. Buďte a, b libovolná kardinální čísla, A, B libovolné takové množiny, že a = card A, b = card B. Pak klademe: a < b <í==^ existuje injektivní zobrazení f:A—>B. 2.3. Poznámka, (a) Relaci < mezi kardinálními čísly jsme definovali pomocí množin o příslušných mohutnostech. Analogicky budeme postupovat i později například při definici aritmetických operací. To však znamená, že je nutno dokázat, že platnost vztahu a < b nezávisí na konkrétní volbě množin A, B, přesněji řečeno, je nutno dokázat, že když je A ~ A\, B ~ B\, pak injekce A do B existuje právě tehdy, když, existuje injekce A\ do B\. Toto tvrzení je však evidentní a zformulování jednoduchého důkazu přenecháme čtenáři. V dalším pak tvrzení tohoto typu většinou nebudeme uvádět. (b) Definici 2.2 jsme mohli zformulovat i jinak. Uvědomíme-li si totiž, že zřejmě injekce A do B existuje právě tehdy, když, existuje B\ c B tak, ž,e A ~ B\, můžeme říci, že a < b <í==^ existuje B\ c B taková, že A ~ B\. 80 KARDINÁLNÍ A ORDINÁLNÍ ČÍSLA Nyní je však nutno dokázat, že relace < definovaná v 2.2 je uspořádání. Vzhledem k tomu, že později uvidíme, že neexistuje množina všech kardinálních čísel (tj. systém všech kardinálních čísel tvoří vlastní třídu), je nutno toto tvrzení zformulovat následovně: 2.4. Věta. Bud' A libovolná množina kardinálních čísel. Pak je (A, <) uspořádaná množina. Důkaz. Reflexivita a tranzitivita relace < je zřejmá, neboť id^ je injekce pro každou množinu A a složení dvou injekcí je opět injekce. Antisymetrie relace < plyne z Cantor-Bernsteinovy věty 6.10. • Následující tvrzení je dalším ekvivalentem axiómu výběru. 2.5. Věta. Pro každá dvě kardinální čísla a, b platí a < b nebo b < a. Důkaz. Buďte A, B libovolné takové množiny, že card A = a, card B = b. Podle Zermelovy věty 4.7 lze množiny A, B dobře uspořádat. Tvrzení nyní plyne z věty 2.13 v kapitole II. • 2.6. Poznámka. Podle věty 2.5 tvoří každá množina kardinálních čísel řetězec. Zejména platí 0 2. Pak platí card Yx > card X. Důkaz. Nejprve dokážeme, že platí card X < card Yx. Podle předpokladu existují prvky y\,yi £ Y, yx ý y2. Pro každý prvek x e X definujme zobrazení fx:X—> Y takto: f(t\ = l yi Pro r = x i j2 pro r e X, t i-x. Pak je pro xx, x2 £ X, xx 4 x2, zřejmě fxx 4 fX2, neboť například fxx (xx) = yu fX2 (xj) = y2. Zobrazení F: X —> Yx definované vztahem F (x) = fx pro každý prvek x e X je tedy injekce, což jsme chtěli dokázat. Nyní dokážeme, že je card X ^ card Yx. Připusťme, že existuje bijekce Yx. Definujme zobrazení /: X —> Y následovně: 2. Nerovnost mezi kardinálními čísly 81 ftx\ = í ^1. jestliže (p(x)(x) ý yr \ y2, jestliže Yx, je tzv. Cantorova diagonální metoda. Jejím speciálním případem je důkaz následujícího tvrzení. 2.9. Věta. Množina všech reálných čísel x, 0 < x < 1 je nespočetná. Důkaz. Buď x e (0, 1) libovolné. Pak lze x napsat pomocí dekadického rozvoje ve tvaru 0,aia2a^..., přičemž tento rozvoj je určen jednoznačně, vyloučíme-li rozvoje, v nichž se od jistého indexu počínaje vyskytuje pouze devítka. (Takže například číslo 0,3209 zapíšeme ve tvaru 0,321.) Předpokládejme nyní, že množina reálných čísel z intervalu (0, 1) je spočetná. Pak lze tato čísla uspořádat do posloupnosti (r„)^1 a každé číslo r, lze jednoznačně vyjádřit pomocí dekadického rozvoje takto: r\ = 0,aiia\2aijai4 . .. r2 = 0,a21a22a23a24 . .. r-i = 0,(331(332(333(334 . . . rn - 0,an\an2anjan4 .. . Zkonstruujme nyní číslo r = 0,aia2a^a4 ... takto: pro i = 1, 2, ..., n, ... je 1 je-li au i- 1 [ 2 je-li au = 1. Pak je r £ (0, 1) a pro každé n e N přitom r ý rn: spor. Interval (0, 1) tedy není spočetný. 2.10. Důsledek. Množina R všech reálných čísel je nespočetná a platí R ~ (0, 1). 82 KARDINÁLNÍ A ORDINÁLNÍ ČÍSLA Důkaz. Zobrazení f(x) = arctg x je bijekce R na interval (—f )• Podle příkladu 1.3(b) jsou však intervaly (—f, \) a (0, 1) ekvivalentní. • 2.11. Důsledek. (a) Množina I všech iracionálních čísel je nespočetná. (b) Množina všech transcendentních čísel je nespočetná. Důkaz, (a) Je R = Q U E a Q je podle důsledku 1.14 spočetná. Kdyby byla množina I spočetná, byla by R spočetná podle věty 1.9: spor. Je tedy I nespočetná. (b) Analogicky (z 1.9, 1.17 a 2.10). • 2.12. Věta. Bud'X libovolná množina. Pak platí card P(X) > card X. Důkaz. Je-li X = 0, je card X = 0 a card P(X) = card {0} = 1 > 0. Nechť tedy X 4 0. Zvolme ve větě 2.7 Y = {0, 1}. Definujme nyní zobrazení F:YX —> P(X) takto: pro každé f:X ^ Y je F(f) = {x; x e X, /(x) = 0}. Pak je zřejmě F bijekce a tvrzení věty nyní plyne z věty 2.7, neboť card^(X) = card7z > cardX. 2.13. Věta. Bud'M nespočetná množina, A nejvýše spočetná podmnožina množiny M. Pak je card M = card (M — A). Důkaz. Je M = (M — A) U A. Protože je A nejvýše spočetná množina, plyne z věty 1.9, že M — A je nespočetná. Podle věty 1.11 existuje spočetná množina A\ c M — A. Označme P =(M-A)-Al. Pak je M - A = Aj U P, tj. M = (A U Aj) U P. Protože je množina A U Aj spočetná, existuje bijekce /: Aj —»- A U A\. Položme pro každé x e M — A ^XJ j x pro x e P. Pak je g: (M — A) —> M bijekce a věta je dokázána. • 2.14. Důsledek. Bud' A libovolná nekonečná množina, B nejvýše spočetná množina. Pak card (A U B) = card A. 2. Nerovnost mezi kardinálními čísly 83 Důkaz. Je-li A spočetná, plyne tvrzení z věty 1.9. Je-li A nespočetná, plyne tvrzení z věty 2.13. Zásadní důležitost v teorii nekonečných množin má následující tvrzení: 2.15. Věta. Množina A je nekonečná právě tehdy, když, obsahuje vlastní podmnožinu B G A takovou, že A ~ B. Důkaz. I. Je-li A konečná, není podle poznámky 1.2 ekvivalentní s žádnou svou vlastní podmnožinou. II. Nechť je A nekonečná. Je-li spočetná, plyne tvrzení z věty 1.11, je-li nespočetná, plyne tvrzení z věty 2.13. • 2.16. Poznámka. Dosud jsme neuvedli, jak lze při axiomatické výstavbě teorie množin for-malizovat intuitivně zřejmý pojem konečné a nekonečné množiny. Nyní vidíme, že nám to umožňuje věta 2.15. Při axiomatické výstavbě lze podle této věty říci, že množina je nekonečná, je-li ekvivalentní s nějakou svou vlastní podmnožinou. Přitom je snad evidentní, že to, zda nekonečné množiny v axiomatické teorii existují nebo ne, závisí na tom, zda přijmeme nebo nepřijmeme axióm, který nám jejich existenci postuluje. (V ZF a GB samozřejmě takový axióm je.) Cvičení k §2 Nejméně vysilující je spolehnout se na vlastní síly. MURPHYHO PARADOX 1. Buďte (an)™=l, (b,,)^ rostoucí posloupnosti reálných čísel. Řekneme, že posloupnost (b„) roste než posloupnost (a„), když platí lim jf- = 0. Dokažte: a) Ke každé rostoucí posloupnosti existuje posloupnost, která roste rychleji. b) Je-li A ^ 0 taková množina rostoucích posloupností, že s každou posloupností obsahuje všechny posloupnosti, které rostou rychleji, pak je množina A nespočetná. (Návod: Důkaz provádějte sporem. Předpokládejte, že A je nejvýše spočetná a Cantorovou diagonální metodou sestrojte posloupnost, která roste rychleji než všechny posloupnosti z A.) 84 KARDINÁLNÍ A ORDINÁLNÍ ČÍSLA 3 Aritmetika kardinálních čísel Pokud vycházejí matematické poučky z,e skutečnosti, nejsou spolehlivé. Pokud jsou spolehlivé, nevycházejí z.e skutečnosti. Einsteinův postřeh Aby byl název kardinální číslo oprávněný, je přirozené požadovat, abychom pro kardinální čísla zavedli obvyklé spolehlivé a ze skutečnosti vycházející aritmetické operace. V tomto paragrafu ukážeme, jak je definován součet, součin a mocnina kardinálních čísel. Ponecháme na čtenáři, aby si promyslel, že pro konečná kardinální čísla budou uváděné definice odpovídat obvyklým aritmetickým operacím v množině nezáporných celých čísel. Poznamenejme ještě, že definici součtu a součinu dvou kardinálních čísel (a tedy i libovolného konečného počtu kardinálních čísel) lze zformulovat bez užití axiómu výběru. Pro definici součtu,qf respektive součinu nekonečného systému kardinálních čísel se však užití axiómu výběru nelze vyhnout. (Přesněji řečeno, bez axiómu výběru nelze dokázat, že každá množina kardinálních čísel má součet a součin.) 3.1. Definice. Buďte a, b libovolná kardinální čísla, A, B buďte libovolné takové množiny, že card A = a, card B = b, A n B = 0. Součtem kardinálních čísel a, b rozumíme kardinální číslo a + b := card (AU B). Obecněji: Buď K ý 0 libovolná množina, buď ak kardinální číslo pro každé k e K. Buďte Ak, k e K po dvou disjunktní množiny takové, že pro každé k e K platí card Ak = ak. Pak definujeme y^flfr := card Ak. kčK kčK 3.2. Poznámka. Nyní bychom při formálně přesném postupu měli dokázat, že: (a) pro každý systém ak, k e K, kardinálních čísel součet ak existuje; kčK (b) tento součet nezávisí na volbě množin Ak, tj. jsou-li Ak, respektive Bk po dvou disjunktní systémy množin takové, že pro každé k e K platí Ak ~ Bk, pak card |J = kčK = card (J Bk. k€K Dokázat bod (a) značí dokázat, že když K ý 0 je množina a ak, k e K, jsou libovolná kardinální čísla, pak existují po dvou disjunktní množiny Ak, k e K, takové, že card Ak = ak 3. Aritmetika kardinálních čísel 85 pro každý index k e K. Zvolme tedy libovolné množiny Bk, k € K, tak, že card Bk = a^. Položíme-li Ak := {k} x Bk, je zřejmě Ak ~ Bk, tj. card Ak = ak a množiny jsou evidentně po dvou disjunktní. Tvrzení (b) vyplývá z věty 1.5(4). Ve shodě s tím, co jsme uvedli již v poznámce 2.3, nebudeme v dalším úvahy tohoto typu opakovat a ponecháme ověření platnosti analogických vztahů u dalších aritmetických operací čtenáři. 3.3. Věta. (Komutativní zákon) Bud' K ý 0 libovolná množina, bud'ak kardinální číslo pro každé k e K. Bud' f permutace množiny K. Pak platí ^2,ak = ^2af(k). kčK kčK Důkaz. Tvrzení plyne z věty 1.4. • 3.4. Důsledek. Pro každá dvě kardinální čísla a, b platí a + b = b + a. Z věty 1.5 okamžitě plyne 3.5. Věta. Bud'K ý 0 libovolná množina, ak bud'kardinální číslo pro každé k £ K. Bud' {Kx; x e X} rozklad množiny K. Pak platí J2ak = J2J2ak- kčK xčX k£Kx 3.6. Důsledek. Pro každá tři kardinální čísla a, b, c platí (a + b) + c = a + (b + c). 3.7. Příklad. (a) Z věty 1.9 plyne, že: (i) Ko + w = Ho pro každé konečné kardinální číslo n; (ii) K0 + K0 = K0 + K0 + K0 = • • • = K0 + K0 + • • • + K0 + ... = K0; Ko-krát oo (iii) je-li pro každé přirozené číslo n: 1 < a„ < Ho, pak ^ a„ = Ho, například 1 + 2 + n=l oo + 3 • • • = E n = Ko- 86 KARDINÁLNÍ A ORDINÁLNÍ ČÍSLA (b) Je-li a > Ko libovolné, pak pro každé konečné n podle 2.14 platí a + n = a + $o = a. 3.8. Definice. Buďte a, b libovolná kardinální čísla, A, B buďte libovolné takové množiny, že card A = a, card B = b. Součin kardinálních čísel a, b definujeme takto: a ■ b := card (A x B). Obecněji: Buď K ý 0 množina, buď kardinální číslo pro každé k e K. Buďte Ak, k e K, libovolné takové množiny, že card Ak = ak Pro každý index k e K. Pak Y[ ak ■= card Ak. kčK kčK 3.9. Věta. (Komutativní zákon) Buď K ^ 0, ak buď pro každé k € K kardinálni číslo, f buď permutace množiny K. Pak Y\ak = Y\am- kčK kčK Důkaz. Potřebujeme dokázat, že pro libovolný systém množin Ak, k e K a pro libovolnou bijekci f: K -> K platí (g) Ak ~ ® A/^)- Buď q> e (g) A^ libovolný prvek. Pak je ifceí: ifceí: kčK U Afc a platí K bijekce, pak pro každé k e K platí kčK ((pof)(k) =(p[f(k)] e Af(k), takže ( kčK kčK -> Af(k) takto: F(93) =

[J Aj takové, že pro každý index kčK kčK k e K platí f (k) e Ak- Pro každé y & Y nyní položme (py := (g) (g) A i vztahem [(ř(^,)](v) = 5. Pro každý prvek x e U 5„ existuje právě jeden index ax e A takový, že x e 5ai, neboť množiny 5„ jsou a e A po dvou disjunktní. Položíme-li f (x) = [ax, fax(x)], je zřejmě / bijekce množiny U Ba na a e A množinu A x B. • 88 KARDINÁLNÍ A ORDINÁLNÍ ČÍSLA 3.16. Příklad. (a) 1 • a = a pro každé kardinální číslo a; (b) 2 • K0 = K0 + K0 = K0; (c) w • K0 = K0 + K0 + • • • + K0 = K0; (d) K0 • K0 = K0 + • • • + K0 + • • • = K0- 3.17. Poznámka. V příkladu 3.7 jsme viděli, že pro libovolné nekonečné kardinální číslo a a libovolné kardinální číslo b < Ko platí a + b = a (= max (a, b)). Podle příkladu 3.16 platí a ■ Ko = (= max (a> ^o)) Pro každé 0 ý a < Ko. V §6 odvodíme , že tyto vztahy jsou speciálním případem tzv. pohlcovacích zákonů: pro libovolná dvě kardinální čísla a,b, z nichž alespoň jedno je nekonečné (v případě součinu samozřejmě musí být obě nenulová) platí a + b = a ■ b = max (a, b). Aritmetika nekonečných kardinálních čísel je proto velmi jednoduchá. Nyní ještě musíme definovat mocniny kardinálních čísel. 3.18. Definice. Buďte a, b kardinální čísla, A, B buďte takové množiny, že card A = a, card B = b. Pak definujeme ab := card AB. První otázkou, kterou nyní musíme rozřešit, je to, zda operace umocňování souvisí „běžným" způsobem s násobením. Ze tomu tak opravdu je, uvidíme v následujícím tvrzení. 3.19. Věta. Bud' B libovolná množina, card B = b. Buďte ap kardinální čísla pro všechna P e B. Jsou-li si všechna čísla ap navzájem rovna, tj. platí-li ap = a pro všechna p e B, pak J-J ap = J"J a = ab. 3. Aritmetika kardinálních čísel 89 Důkaz. Potřebujeme dokázat, že když Ap,fS e fi,jsou takové množiny, že Ap ~ A pro všechna P e fi,pak (g) Ap ~ AB. Buď tedy /'^: A -> A p bijekce pro každé f3 e B. Pro každej e 0 A^buďF^): 5 -» A zobrazení definované takto: [F((p)]({3) = fp[(p(fi)] (= (//? o q>)(fi)). Pak je zřejmě F bijekce (g) A/j na AB. • 3.20. Příklad. (a) K95 = K0 • *o = ^o; (b) K£ = K0 • K0 ... K0 = K0 pro každé 1 < n < K0; (c) a° = 1 pro každé kardinální číslo a, zejména tedy 0° = 1; (d) 0fl = 0 pro každé a > 0. Cantorovu větu 2.7 nyní můžeme přeformulovat takto: 3.21. Věta. Buďte a, b libovolná kardinální čísla, a > 2. Pak ah > b. Z důkazu věty 2.12 a z věty 3.21 okamžitě plyne 3.22. Věta. Buď A libovolná množina, card A = a. Pak card P (A) = 2a, zejména tedy card P (A) > cardA. 3.23. Věta. Budí ý $ libovolná množina, a, b, c, aŕ(i e /) Ŕwŕfe kardinální čísla. Pak platí: (1) až>' = f] aa", z.ejména ab+c = ab ■ ac; 16/ (b) (abf = abc; (c) (]~[ a,)6 = f~[ af, zejména (a ■ b)c = ac ■ bc. Důkaz. Tvrzení věty plyne bezprostředně z věty 1.5(5) - (7). • O počítání s nerovnostmi mezi kardinálními čísly nás informuje následující tvrzení. 3.24. Věta. Bud A ý 0 množina, buďte ma, na taková kardinální čísla, ž.e pro každé a G A platí ma < na. Pak: (1) Yl ma < E w«; ciěA a€A 90 KARDINÁLNÍ A ORDINÁLNÍ ČÍSLA (2) f] ma < f] na. ciěA a e A Důkaz. (1) Buďte Ma a Na takové po dvou disjunktní systémy množin, že pro každé a e A platí card Ma = ma, card Na = na. Ze vztahu ma < na plyne, že Ma ~ N'a c Na. Pak ale podle věty 1.5(4) platí U Ma ~ U K c U tj. £ m„ < £ n„. uea aeA aeA a€A a€A Tvrzení (2) se dokáže analogicky. • Z vět 3.24 a 3.19 okamžitě plyne 3.25. Důsledek. Pro každá kardinální čísla m, n, p platí: (1) n < p =>• m" < mp; (2) m < n =ŕ mp < np. 3.26. Poznámka. Protože z věty 3.24 zejména plyne, že pro každá kardinálni čísla m, n, p taková, že m < n, platí m + p < n + pa rovněž m- p < n- p, vidíme, že pro počítání s nerovností < platí v aritmetice kardinálních čísel tatáž pravidla jako v aritmetice čísel přirozených. Je však zřejmé, že při počítání s ostrou nerovností < analogická pravidla neplatí: ačkoliv například 2 < 3, přesto 2 + Ko = 3 + Ko (a nikoliv 2 + Ko < 3 + Ko) nebo 5 • Ko = Ko • Ko = Ko (a nikoliv 5 • K0 < K0 • K0). 4 Mohutnost kontinua Odborník je člověk, který úzkostlivě dbá na to, aby se vyvaroval drobných chyb, zatím co se nezadržitelně řítí k jednomu velkému omylu. Weinbergův důsledek Allisonovy zásady Již ve větě 2.10 jsme odvodili, že množina R všech reálných čísel je nespočetná. Poněvadž číslo card R hraje v řadě úvah důležitou roli, budeme se jím nyní zabývat podrobněji. 4.1. Definice. Kardinální číslo c := 2^° nazýváme mohutností kontinua. Z věty 3.21 víme, že c = 2^° > Ko. Nyní uvedeme další vlastnosti čísla c. 4.2. Věta. Bud'n libovolné přirozené číslo (tj. 1 < n < Koj. Pak platí: (1) n + c = K0 + c = c + c = c; (2) n ■ c = K0 • c = c • c = c; 4. Mohutnost kontinua 91 (3) c" = c; (4) pro n > 1 platín*0 = = c*° = C. Důkaz. (1) Platí: c Podle věty 1.15 je G spočetná, takže podle věty 2.13 platí card (F — G) = cardF = c. Přiřadíme-li nyní každému prvku / = (ch,)^ e F — G číslo 0,a\a2 .. .an ..., obdržíme zřejmě bijekci množiny F — G na interval (0, 1). Dokázali jsme tak, že card (0, 1) = c. Z důsledku 2.10 okamžitě plyne, že i card R = c. Vzhledem k tomu, že card Q = Ko (důsledek 1.14) a rovněž množina algebraických čísel je spočetná (poznámka 1.17), plyne z předchozího okamžitě tvrzení (d) i (e). Tvrzení (c) plyne z příkladu 1.3(b). (Uvědomme si, že podle věty 4.2 na mohutnost intervalu reálných čísel nemá vliv, zda koncové body do tohoto intervalu patří či nikoliv.) = 2*° = c. = c. 92 KARDINÁLNÍ A ORDINÁLNÍ ČÍSLA Množina všech posloupností přirozených čísel je množina N . Její mohutnost K0° je však c podle věty 4.2(4), tj. platí (f). Tvrzení (g) plyne z věty 4.2(3), tvrzení (h) z věty 3.22. • 4.4. Příklad. V příkladu 3.7(iii) jsme odvodili, že l+2+3 + --- = ^w = K0. Nyní ukážeme, že Y\n=l 2 3> =c. Platí totiž 1 • 2 • 3 • ... < K0 • Kp • Kp • ... = = c, «o-krát avšak současně l-2-3---- = 2- 3- 4- ...> 2_2_2___. = 2*° = c. Ko-krát 4.5. Poznámka. Jak jsme uvedli již v §2, systém všech kardinálních čísel tvoří vlastní třídu. (Toto tvrzení dokážeme v §6, důsledek 6.15.) V definici 2.2 jsme na této třídě definovali uspořádání a z věty 2.5 víme, že vzhledem k tomuto uspořádání tvoří každá množina kardinálních čísel řetězec. Víme například, že Ko je nejmenší nekonečné kardinální číslo (poznámka 2.6) a že ke každému kardinálnímu číslu existuje číslo větší (poznámka 2.8), avšak prakticky žádné další informace o struktuře řetězce kardinálních čísel nemáme. Víme například, že Ko < 2^°, nevíme však, existuje-li kardinální číslo m takové, že Ko < m < 2®°. (Předpoklad, že takové číslo m neexistuje, tzv. hypotéza kontinua, patří k nejznámějším matematickým problémům 20. století. O jeho vyřešení viz poznámku 6.23.) V této chvíli neumíme ani rozhodnout, zda má každé kardinální číslo svého bezprostředního následníka či nikoliv. Tyto a další informace získáme pomocí tzv. ordinálních čísel. Cvičení k §4 Hlavní příčinou problémů jsou jejich řešení. Sevareidův zákon 1. Dokažte, že když je 2a > Kq, pak je 2a > c. 5. Ordinální typy a ordinální čísla 93 2. Dokažte následující tvrzení: Množina všech spojitých funkcí f: R -> R má mohutnost kontinua. (Návod: Buď (an)í^i posloupnost všech racionálních čísel. Přiřaďte každé spojité funkci /: R —> R posloupnost (/(an))^. Dokažte, že f ¥ 8 právě tehdy, když (f(a„)) ¥ ¥ (g(an))- Tvrzení pak lze již snadno odvodit.) 3. Dokažte, že množina všech funkcí /: R -> R má mohutnost 2C. 5 Ordinální typy a ordinální čísla Pokrok neznamená, Ž.e se chybná teorie nahradí správnou. Pokrok spočívá v tom, ž.e se chybná teorie nahradí takovou, na které to není tolik znát. Hawkinsova teorie pokroku V §1 jsme každé množině A přiřadili její kardinální číslo. Nyní analogicky každé uspořádané množině přiřadíme její ordinální typ. Tak jako podstata kardinálních čísel spočívala v tom, že card A = card B právě tehdy, když A ~ B, spočívá smysl ordinálních typů ve skutečnosti, že stejný ordinální typ mají právě jen izomorfní uspořádané množiny. 5.1. Definice. Řekneme, že uspořádané množiny A, B mají stejný ordinální typ a píšeme ~A~ = ~B, je-li A = B. 5.2. Poznámka. Pro ordinální typy některých často se vyskytujících množin je výhodné zavést si standardní označení. Tak například ordinální typ prázdné množiny značíme symbolem 0, ordinální typ řetězce o n prvcích (n libovolné přirozené) značíme symbolem n, ordinální typ množiny N všech přirozených čísel s obvyklým uspořádáním značíme co, ordinální typ množiny N* značíme co* a podobně1. (Značíme tedy stejnými symboly konečná kardinální čísla i ordinální typy konečných řetězců. K omylu však v dalším nedojde, neboť z kontextu bude vždy zřejmé, v jakém významu budeme těchto symbolů užívat.) 1 Připomeňme, že pro uspořádanou množinu A značí A* množinu uspořádanou duálně, tj. (A, <)* = (A, >). Typ co* má tedy například množina všech celých záporných čísel s obvyklým uspořádáním. 94 KARDINÁLNÍ A ORDINÁLNÍ ČÍSLA Z definice izomorfismu také plyne, že když A = B, pak také card A = card B (pozor: ne naopak!). Má tedy smysl mluvit o mohutnosti daného ordinálního typu. (Například typy co i co* mají mohutnost Ko.) Pomocí aritmetických operací mezi uspořádanými množinami, které jsme definovali v kapitole II, §3, nyní snadno zavedeme aritmetické operace mezi ordinálními typy. Poznamenejme ještě, že zápisem A = a rozumíme fakt, že ordinální typ uspořádané množiny A jsme označili symbolem a (například N = co). 5.3. Definice. Buďte a, p ordinální typy. Zvolme disjunktní uspořádané množiny A, B tak, že A = a, B = {3. Pak součet typů a, p definujeme vztahem: Obecněji: Buď 7^0 uspořádaná množina, buď a, ordinální typ pro každé i e I. Buďte A,, i e I, po dvou disjunktní uspořádané množiny takové, že A, = a, pro každé i e I. Pak definujeme 5.4. Poznámka. Podobně jako u početních operací s kardinálními čísly i operace mezi ordinálními typy definujeme pomocí množin o příslušných ordinálních typech. U každé operace je pak ale nutno dokázat, že výsledek nezávisí na konkrétní volbě těchto množin. K definici 5.3 je tedy nutno dokázat, že když A,, 5,, i e I jsou po dvou disjunktní systémy uspořádaných množina takové, že A, = 5, (tj. A, = 5,) pro každé i e I, pak také At = Yl Bi- Důkaz tohoto tvrzení je však jednoduchý a proto ho přenecháme čtenáři. V dalším pak již úvahy tohoto typu nebudeme opakovat. Z věty 3.11 v II. kapitole okamžitě plyne: 5.5. Věta. (Asociativní zákon) Budí ý 0 uspořádaná množina, buďoii ordinální typ pro každé i e I. Nechť I = Y h- Pak platí kčK a + p := A + B. 5.6. Důsledek. Buďte a, /3, y libovolné ordinální typy. Pak platí (a + P) + y = a + (fi + y). 5. Ordinální typy a ordinální čísla 95 5.7. Poznámka. Z příkladu 3.3 v II. kapitole plyne, že sečítání ordinálních typů obecně není komutativní. 5.8. Příklad. (a) co + 1 ý 1 + co, neboť je zřejmé, že 1 + co = co avšak co + 1 ^ co; (b) 1 + 2 + 3 + • • • + n + ■ ■ ■ = co. 5.9. Definice. Buďte a, p libovolné ordinální typy. Buďte A, B libovolné uspořádané množiny takové, že A = a, B = fi. Pak definujeme Z věty 3.14 v II. kapitole plyne levý distributivní zákon. 5.11. Věta. Bud' I ý $ uspořádaná množina, bud'a i ordinální typ pro každé i e /. Pak pro libovolný ordinální typ a platí 5.12. Důsledek. Buďte a, /3, y libovolné ordinální typy. Pak platí a-(P + y)=a-p+a-y. 5.13. Věta. Budí ý 0 uspořádaná množina, I = /3. Buďoti = a ordinální typ pro každé i e /. Pak platí a- p := A - B. Z věty 3.13 v II. kapitole plyne 5.10. Věta. Buďte a, /3, y libovolné ordinální typy. Pak platí (a ■ P) ■ y = a ■ (fi ■ y). a = a ■ p. Důkaz plyne z věty 3.17 v II. kapitole. 5.14. Příklad. (a) 2-ftj = 2 + 2 + 2 + -- - + 2+ -- - = ftj; 96 KARDINÁLNÍ A ORDINÁLNÍ ČÍSLA (b) (ú-2 = (ú + (úý(o; (c) a>-a> = co + a> + a> + -- - + a>+.... 5.15. Definice. Buď a libovolný ordinální typ. Mocninu s konečným exponentem definujeme indukcí takto: 5.16. Příklad. (a)a>=a>-a> = a> + a> + -- - + a>+... (b) a) + a)2 = ctí(l + ctí) = ctí • ctí = ctí2 (c) ctí2 + ctí = ctí • (ctí + 1) 7^ ctí2 (d) (ctí + ctí) • ctí = (ctí • 2) • ctí = ctí • (2 • ctí) = ctí2 (e) ctí • (ctí + ctí) = ctí • (ctí • 2) = (ctí • ctí) • 2 = co2 + ctí2 Uvědomme si, že všechny ordinální typy v příkladu 5.16 jsou spočetné. 5.17. Definice. Ordinální typ dobře uspořádané množiny se nazývá ordinální číslo. 5.18. Příklad. 0,1,2,3,...,co,co+í,cú + 2,cú + cú atd. jsou ordinální čísla, a>* není ordinální číslo, R není ordinální číslo atd. Z věty 3.18 v kapitole II. plyne 5.19. Věta. Budí ý 0 dobře uspořádaná množina, buď W(a). Dokážeme, že

~1: W(a) A zřejmě také izotonní, takže

W(ijl). Tzn., že množinu M lze jednoznačně psát jako řetězec M = {a0 <«!<•••< orf < ... }?<ří. 98 KARDINÁLNÍ A ORDINÁLNÍ ČÍSLA 5.29. Věta. Každé ordinální číslo a má svého bezprostředního následovníka, kterým je číslo a+1. Důkaz. Nechť A = a. Buď b £ A libovolný prvek (například {A}). Položme B = A + {b}. Pak B = a + 1. Protože A = B(b), platí a < a + 1. Buď nyní < a + 1 libovolné ordinální číslo. Podle definice uspořádání je typ některého začátku množiny B, takže zřejmě platí < a. Neexistuje tedy takové, žea<{3a + y

a; (2) a + p > p. Důkaz. (1) Je-li p > 0, je podle věty 5.32(1) a + 0 < a + fi, tj. a < a + fi. (2) Protože 0 < a, je 0 + < a + fi, tj. VJ a%. Protože ag není nej větší prvek v M, existuje ae+1 e M, ae+1 > ae > VJ a%. Buďte Aj, £ < M, po dvou disjunktní uspořádané množiny takové, že pro každé £ < M platí A^ = cŕj. Označme A = VJ Aj. Protože YJ < ae+1, existuje x e Ae+1 takový, že A = Ae+1(x). Protože Ae+1 c A, plyne odtud, že Ae+i je izomorfní s vlastní podmnožinou svého vlastního začátku, což je spor s větou 2.7. • V definici 5.15 jsme definovali mocninu libovolného ordinálnŕho typu v případě, že exponentem bylo konečné ordinální číslo. Transfmitní indukcí nyní tuto definici zobecníme. 5.35. Definice. Buď a libovolné ordinální číslo. Pak definujeme: 1. a°= 1; 2. a^+1 = ■ a; 3. = VJ ae pro £ ^ 0 limitní. 5.36. Příklad. coa = YJ afi = 1 + co + co2 + ... . g £ pro každé £ e M. Protože však a e M, plyne odtud a > a: spor. • 6.3. Věta. Buď M libovolná množina ordinálních čísel. Pak mezi ordinálními čísly, která nepatří do M, existuje nejmenší. Důkaz. Podle věty 6.1 existuje ordinální číslo a £ M. Pokud a není nejmenší číslo nepatřící do M, je W(a) - Hledaný prvek je nyní nejmenší prvek množiny W(a) — M. • 6.4. Poznámka. Je-li m konečné kardinální číslo, existuje právě jedno ordinální číslo mohutnosti m. Pro nekonečné kardinální číslo je však situace nepoměrně složitější. Podívejme se například, jak vypadá množina Z\ všech spočetných ordinálních čísel. Nejmenším prvkem množiny Z\ je prvek co. Je-li totiž a ordinální číslo, a < co, je a typ množiny izomorfní s některou množinou N(x), x e N, takže a je konečné ordinální číslo. Když využijeme odvozených vlastností aritmetických operací mezi ordinálními čísly, vidíme, že množina Z\ vypadá následovně (čtenář nechťsi promyslí, že všechna uváděná ordinální čísla jsou opravdu spočetná): co, co + 1, co + 2, ..., co + n,..., co + co = co ■ 2, co ■ 2 + 1, ..., co ■ 2 + n, ..., co • 2 + co = co • 3, 4, ..., co ■ n, ..., co ■ co = co2, co2 + 1, ..., co2 + n,... co2 + co, co2 + co + 1, ..., co2 + co + co = co2 + co ■ 2, co2 + co ■ 2 + 1, ..., co2 + co ■ 2 + co = co2 + co ■ 3, ..., co2+co-4,..., co2+co-co = co2+co2 = co2-2, co2-2+1,..., co2-2+co,..., co2-2+co+co = co2-2+co-2, ..., co2 ■ 2 + co ■ 3,..., co2 ■ 2 +a)2 = co2 ■ 3,..., co2 ■ 4,..., co2 ■ co = co3, co3 + 1,..., co3 +co,..., co3 + co • 2,..., co3 + co • 3,..., co3 + co2, ..., co3 + co2 + co, ..., co3 + co2 + co • 2,..., co3 + co2 • 2, . . . , CO + CO • í, . . . , CO + CO = CO ■ Z, ..., co • í, ..., co - co = co,...,co,...,co,..., C00J = £ Ctí", coa + 1,..., coa + co,..., coa + co ■ 2, ..., coa + co ■ co = coa + co2,... ,coa + C02 +CO, n• a+l e Z (m). Odtud však plyne, že Z(m) C U W(a) = a€Z(m) = W. Je-li /3 e W libovolný prvek a y < /3 libovolné ordinální číslo, je také y e W (neboť /3 e W(a) =^ y e W(a) c W). To znamená, že W = W(q), kde q je nejmenší ordinální číslo takové, že q £ W. Podle věty 5.26 platí W(q) = q, tj. W = q a číslo q je limitní ordinální číslo podle poznámky 6.6. Nyní však platí W = W(q) = W[co(m)] + Zim), tj. q = co (m) + £. Protože je q limitní, je nutně i £ limitní. (Kdyby totiž platilo £ = £ + 1, platilo by q = co (m) + (£ + 1) = (cti(m) + £) + 1 a q by nebylo limitní.) • 6.8. Definice. Buď m libovolné nekonečné kardinální číslo. Označme A(m) := {cti(n); Ko < n < m}. Nechť A(m) = a. Pak číslo m(m) označíme ctia a kardinální číslo m označíme K„. 6.9. Poznámka. Protože je A(m) množina ordinálních čísel, je dobře uspořádaná, tj. A(m) = a je ordinální číslo. Protože W(a) = a, je A(m) = W(a). Platí například A(K0) = {co(n)\ H0 < « < K0} = 0, tj. A(Ko) = 0. Nejmenší ordinální číslo o mohutnosti Ko, tj- číslo co, máme tedy podle 6.8 označit ctiQ. Značení čísla je přitom ve shodě s touto definicí. 102 KARDINÁLNÍ A ORDINÁLNÍ ČÍSLA Z definic 6.5 a 6.8 okamžitě plyne následující tvrzení: 6.10. Věta. Každé nekonečné číslo je některým alefem. Z uvedené konstrukce plyne, že každé počáteční ordinální číslo i každá mohutnost je coa, respektive K„, kde a je nějaké ordinální číslo. Nyní postupně ukážeme, že naopak každé ordinální číslo je indexem některého počátečního ordinálního čísla a tedy i některého alefu. 6.11. Věta. Buďte coa, cop libovolná počáteční ordinální čísla. Pak coa < cop právě tehdy, když a < ji. Důkaz. Podle poznámky 6.9 platí A(m) = W(a), kde a = A(m),A(n) = W(fJ), kde f> = A(n). Platí: a < p <í==^ W(a) je vlastní začátek v množině W(fi) <í=í> <í=í> A(m) je vlastní začátek v A(n) <í==^ co(m) < co(n) <í=^ <í=^ coa < cop. 6.12. Věta. Každé ordinální číslo je indexem některého alefu. Důkaz. Připusťme, že existuje ordinální číslo a, které není indexem žádného alefu a tedy ani žádného počátečního ordinálního čísla. Pak lze předpokládat, že a je nejmenší takové ordinální číslo. Mohou nastat dva případy: (a) a je izolované číslo, tj. a = f> + 1. Podle předpokladu tedy existuje počáteční ordinální číslo cot a $p = card cop. Označme cp = Z(K^). Podle věty 6.7 je cp limitní ordinální číslo. Označíme-li q = cop + cp, platí (viz důkaz věty 6.7) W(q) = Wicjop) + Z(Kp) = W(cjop) + {y; card y = K^}. Odtud však A(cardq) = {coa; a < cop} + cop, takže index počátečního ordinálního čísla mohutnosti card q je roven f> + 1 = a: spor. (b) a je limitní číslo. Platí a > 0, neboť 0 je indexem alefu. Podle předpokladu je každé ordinální číslo £ < a indexem některého počátečního ordinálního čísla co^. Toto číslo co^ je přitom podle věty 6.11 jednoznačně určeno. Položme nyní Z= (J Z(card£), W = |J Pak je cp = W opět počáteční ordinální číslo a zřejmě cp = coa: spor. • 6. Třída všech ordinálních čísel. Alefy 103 6.13. Důsledek. Každé ordinální číslo je indexem právě jednoho alefu, přičemž, pro každá ordinální čísla a, p platí a < p právě když H„ < . Odtud a z věty 5.27 plyne 6.14. Důsledek. Každá množina kardinálních čísel je dobře uspořádaná. Z důsledků 6.13 a 6.2 plyne 6.15. Důsledek. Neexistuje množina všech kardinálních čísel (tj. třída všech kardinálních čísel je vlastní). Z důsledku 6.13 a věty 5.29 plyne 6.16. Důsledek. Pro každé ordinální číslo a platí Ka < Ka+i, přičemž, neexistuje kardinální číslo m takové, ž.e Ka < m < Již v poznámce 3.17 jsme uvedli, že aritmetika nekonečných kardinálních čísel je jednoduchá vzhledem k platnosti tzv. pohlcovacích zákonů. Nyní již můžeme platnost těchto zákonů dokázat. Nejprve však uveďme jedno pomocné tvrzení. 6.17. Lemma. Buďte a > p libovolná ordinální čísla. Pak existuje právě jedno ordinální číslo y takové, že a = {3 + y. Důkaz. Buď A libovolná taková uspořádaná množina, že A = a. Pak v A existuje právě jeden začátek B takový, že B = p. Označíme-li y = A — B,jea = f3 + y. Zbývá tedy dokázat, že toto číslo y je určeno jednoznačně. Nechť p + Yi = {3 + y2. Podle věty 5.32(1) nemůže platit y\ < Yi am Yi < Y\, takže platí Yi = Y2- • 6.18. Věta. Pro každé ordinální číslo a platí Důkaz. Pro a = 0 jsme tvrzení dokázali v příkladu 3.16. Podle principu transfmitní indukce tedy stačí dokázat, že když • = pro každé £ < r, pak také Kr • Kr = Kr (při libovolné volbě čísla t). Položme tedy M := W(coľ) x W(cor) (podle definice platí card W(cor) = Kr). Pro y] e e M platí p < ĺúx, y < coľ. Číslo Á = p + y nazveme výškou prvku y]. Nejprve ukážeme, že Á = p + y < ĺúx . Označme a = card W({3), b = card W(y). Nechť například a < b. Pak platí a < b < Kr. Nyní mohou nastat tři případy: 104 KARDINÁLNÍ A ORDINÁLNÍ ČÍSLA (1) p, y jsou konečná ordinální čísla. Pak je tvrzení P + y < cor zřejmé. (2) p je konečné, y nekonečné. Pak je a + b = b, tj. card (P + y) = card y < < KT, tj. yS + y < Kr. (3) p, y jsou nekonečná kardinální čísla. Pak jsou a, b některé alefy a podle indukčního předpokladu platí a ■ a = a, b ■ b = b. Pak ale b Mx-Definujeme-li nyní uspořádání na Mx tak, aby / byl izomorfismus, je Mx = W(X + 1), tj. Mx = X + 1. Protože jsou množiny Mx, X < cůx, po dvou disjunktní, můžeme utvořit jejich součet; jinak řečeno, M lze uspořádat tak, že platí M = VJ Mk. Platí ~M = ů = (X + 1). XěW(ojt) XěW(ojt) Nyní dokážeme, že ů = cor. Protože podle věty 5.34 platí ů > cor, stačí dokázat, že nemůže platit ů > Lúr. Dokážeme to sporem. Připusťme tedy, že ů > cor. Pak ale existuje £j = [fi\,Y\\ e M tak, že pro vlastní začátek M(£i) platí M(%i) = cor. Označme X i = P\ + y\. Podle předchozího je X j < cor, tj. cardÁj < Kr. Pro každé £ = [b, y] e M(£\) však platí p + y < X\, takže tím spíše je P < X\, y < X\. Poněvadž je však card X\ < Kr, platí podle indukčního předpokladu card {[p, y] e M; p < Aj + 1, y < Aj + 1} = card Aj. Odtud však plyne, že card M(£i) < card Aj < Kr: spor. Tím je věta dokázána. • 6.19. Důsledek. (Pohlcovací zákony) Buďte a, p libovolná ordinální čísla, max (a, P) buď větší z nich. Pak platí tj. součet i součin dvou nekonečných kardinálních čísel je větší z těchto dvou kardinálních čísel. 6. Třída všech ordinálních čísel. Alefy 105 Důkaz. Nechť například < a. Pak je < H„ a platí K < K + tip < K + K = 2 • K < K ■ K = K«, tj. K„ + ^ = K„. Podobně tj. K-Xp= • Nyní již můžeme snadno určit mohutnost množiny Z(m) pro libovolné nekonečné kardinální číslo m. Platí 6.20. Věta. Pro každé ordinální číslo a platí card Z(K„) = Ha+1. Důkaz. Je zřejmé, že Z(K„) = W(coa+i) — W(coa). Avšak card Z(K„) je některý alef. Nechť tedy například card Z(K„) = KK. Protože W(coa+i) = Z(K„) + W(coa), dostáváme Ka+1 = KK + + K„ = Kmax(Ka), tj. a + 1 = max(y, a). Protože a < a + 1, znamená to, že y = a + 1. • Tvrzení věty 6.20 lze ještě zesílit. Podle ní totiž platí card Z(K„) = = Ka+i = card W(coa+i). Ukážeme, že množiny Z(K„) a W(ma+\) mají nejen stejné kardinální číslo, ale i stejný ordinální typ. 6.21. Věta. Bud'(júa libovolné počáteční ordinální číslo. Pak pro každý prvek £ e W((oa) platí W(coa) = W(coa) - Důkaz. Označme = W(eoa) - Pak W(eoa) = + Protože = £, platí card < K„, neboť £ < ma. Dále platí card W(coa) = Kfl = card + £(£)],takže card = H„, podle důsledku 6.19. Protože platí B(%) < coa acoa je nejmenší ordinální číslo o mohutnosti K„, plyne odtud celkem B(%) = coa. • 6.22. Důsledek. Pro každé ordinální číslo a platí Z(K„) = ftja+1. Důkaz. Platí Z(K«) = - Podle věty 6.21 platí Z(K„) = W(coa+1) - W(coa) = W(coa+1) =a+l. 106 KARDINÁLNÍ A ORDINÁLNÍ ČÍSLA 6.23. Poznámka. Mohutnost kontinua c = 2^° je podle věty 6.10 některým alefem. Podle věty 3.21 platíc > Kj. Již Cantor předpokládal, že c = Kj. Jak jsme uvedli již v 4.5, nazýval se tento předpoklad hypotéza kontinua. Tato hypotéza patří k nej známějším matematickým problémům 20. století. Samotný Cantor ji zformuloval již v r. 1878 a dokonce několikrát prohlašoval, že její důkaz v nejbližší době uveřejní. Nikdy se mu však hypotézu nepodařilo rozřešit. Dnes víme, že to bylo vcelku zákonité; hypotéza kontinua byla prostředky, které měl Cantor k dispozici, neřešitelná a odpověď se zcela vymyká představám, které mohli matematikové Cantorovy doby vůbec mít. Přes značné úsilí mnoha matematiků se tuto hypotézu dlouho nikomu nedařilo ani dokázat ani vyvrátit, ačkoliv řada důvodů stále výrazněji nasvědčovala tomu, že by hypotéza měla být správná. První významný krok učinil až v r. 1940 K. Gódel, který v jím vybudované axiomatické teorii množin2 dokázal, že pokud je tato teorie bezesporná, je bezesporná i teorie, která vznikne přidáním axiómu výběru a zobecněné hypotézy kontinua.3 Co z tohoto výsledku plyne? Kdyby bylo například v ZF možné hypotézu kontinua vyvrátit, musela by být teorie „ZF+hypotéza kontinua" sporná. Protože však není (pokud není ZF sporná sama o sobě, v což samozřejmě doufáme), plyne odtud, že hypotézu kontinua nelze v ZF vyvrátit. My však již víme, že to samozřejmě neznamená, že ji lze v ZF dokázat! Stejná situace byla i s axiómem výběru. Přes četné výhrady k jeho používání Gódelův výsledek znamenal, že axióm výběru nevede ke sporu.4 Definitivně byl problém hypotézy kontinua vyřešen v r. 1963, kdy americký matematik P. Cohen dokázal, že hypotéza kontinua tvoří v Zermelo-Fraenkelově teorii množin neroz-hodnutelné tvrzení (srovnej s definicí 5.11). Téměř současně s Cohenem, v r. 1964, dokázal totéž v teorii Gódel-Bernaysově český matematik P. Vopěnka. O této problematice se ještě zmíníme v kapitole IV, §5. Cvičení k §6. Nic není nemožné, pokud to nemusíte dělat sami. Weilerův zákon 1. Dokažte následující tvrzení: 2V tzv. teorii S, která je „hodně blízká" teorii ZF. Zejména bezespornost jedné z těchto teorií implikuje bezespornost druhé. 3Hypotéza kontinua je zvláštním případem tzv. zobecněné hypotézy kontinua 2^a = Ka+i pro každé ordinální číslo a. (Připomeňme si, že z věty 3.21 víme, že vždy platí 2^" > Ka+i.) 4Vzájemný vztah mezi axiómem výběru a zobecněnou hypotézou kontinua dokázali W. Sierpiŕiski (1947) a e. Specker (1952), když odvodili, že ze zobecněné hypotézy kontinua axióm výběru vyplývá. 6. Třída všech ordinálních čísel. Alefy 107 Bud'aa nekonečné kardinální číslo. Bud'K ý 0 libovolná taková množina, ž.e card K < < Ka. Buďte nik, k £ K, taková kardinální čísla, ž.e m^ < Ka pro každé k £ K. Pak kčK 2. Kardinální číslo K„ se nazývá iregulární, jestliže K„ = Yl mk, kde card K < kčK < K„, m k < K„ pro každé k e K. Nekonečné kardinální číslo, které není iregulární, se nazývá regulární. Dokažte: a) Každé číslo Ka+1 je regulární. (Návod: Využijte cvičení 1.) b) Číslo KM0 je iregulární. (Návod: Dokažte, že KM0 = K„.) n<úiQ 3. Všechna známá regulární čísla K„ jsou taková, že a je izolované ordinální číslo (považujeme -li nyní 0 za izolované číslo). Dodnes není známo, zda existují regulární kardinální čísla K„, jejichž index a je limitní ordinální číslo; takové kardinální číslo se nazývá nedosažitelné. Promyslete si, že pokud existuje nedosažitelné kardinální číslo K„, musí být nesmírně velké. (Uvažte, že mohutnost jeho indexu a by sama musela být nedosažitelným kardinálním číslem.) 4. Kardinální číslo m se nazývá měřitelné, jestliže existuje taková množina A, card A = m, a takové zobrazení /: P (A) -> {0, 1}, že platí: a) f (A) = 1; b) pro každý prvek a e A platí f ({a}) = 0; c) jsou-li množiny X„ c A, n = 1, 2, ..., po dvou disjunktní, pak (oo \ oo Číslo, které není měřitelné, se nazývá neměřitelné. Dokažte následující tvrzení: a) Ko ye neměřitelné. /3) Je-li Ka neměřitelné, je každé číslo m < Ka neměřitelné. y) Nejmenší měřitelné kardinální číslo je nedosažitelné, přičemž, nejmenší nedosažitelné kardinální číslo je ještě neměřitelné. (Viz [1], str. 318.) Kapitola 4 Historický vývoj teorie množin 1 Vývoj pojmu nekonečno. Dílo B. Bolzana Co dobře začíná — špatně skončí. Co špatně začíná — skončí ještě hůř. PUDDERŮV ZÁKON Teorie množin je dnes základem, na němž je vystavěna převážná část současné matematiky. Přes náročnost a vysokou abstraktnost této teorie jsou její základní pojmy natolik věrným odrazem reality, že jsou již zahrnuty i do učiva základní školy. Je proto do jisté míry překvapující, že se teorie množin jakožto samostatná matematická disciplína začala formovat až v 70. letech minulého století v díle vynikajícího německého matematika Georga Cantora. V této kapitole se budeme zabývat historií teorie množin a důsledky této teorie pro vývoj matematiky ve 20. století. Vzhledem k tomu, že teorie množin vznikla především z potřeby vyrovnat se s problematikou nekonečna, připomeneme nejprve, jak se vyvíjely představy matematiků a filozofů v tomto směru. Aktuální a potenciální nekonečno Často podléháme klamnému dojmu, že lidské poznatky se rozvíjejí „přímočaře": přidáváme pouze nové a nové poznatky k těm dřívějším, víme toho stále „více a více". Své představy podsouváme našim předkům a mnohdy si vůbec neuvědomujeme, že leckteré naše „samozřejmosti" ani zdaleka nemusely být „samozřejmé" v minulosti. 108 1. Vývoj pojmu nekonečno. 109 Na základní škole dětem říkáme, že množina N všech přirozených čísel je nekonečná (a nikdo se nad tím nepozastaví), všichni samozřejmě víme, že bodů na úsečce je nekonečně mnoho (a navíc jsme zjistili, že je jich „více" než přirozených čísel, protože je jich nespočetně mnoho, zatím co N je pouze spočetná). I malé děti chápou, že přímka nemá žádný konec a při pohledu na večerní oblohu přímo „cítíme" nekonečno vesmíru, který nás obklopuje. Málokdo si přitom uvědomuje, že po dlouhá staletí, dokonce ještě v minulém století, bylo všechno jinak. Vraťme se v našich úvahách do starého Řecka, kde se formovaly základy moderní vědy včetně matematiky. S pojmem „nekonečno" samozřejmě starořečtí filosofové běžně pracovali. Byli si však dobře vědomi problémů, které jsou s tímto pojmem spojeny.1 Postupně vykrystalizoval dvojí přístup k nekonečnu. Místo dlouhého teoretického popisu tyto přístupy ilustrujme na jednoduchém příkladu. Samozřejmě, že již staří Řekové dobře věděli, že přirozených čísel 1,2,3,...,«,... je nekonečně mnoho. Tuto skutečnost však můžeme popsat a chápat dvěma způsoby. Budeme-li postupně psát přirozená čísla, nikdy je nevypíšeme všechna. Za každým číslem následuje další, jakoukoliv předem stanovenou mez dříve nebo později překročíme. Takto chápané nekonečno popisující proces, který nikdy neskončí, mez, které nikdy nedosáhneme, to je tzv. potenciální nekonečno. My dnes však, pod vlivem vývoje, který trvá již několik desetiletí, chápeme nekonečnost systému přirozených čísel jinak: díváme se na množinu N jako kdybychom ji „viděli" hotovou, stavíme se do pozice, kterou Řekové přenechali bohům a která nebyla určena lidskému zkoumání. Nekonečné množiny si představujeme jako završené a zkoumáme bez obav vlastnosti těchto systémů. Tomuto nekonečnu, chápanému v završené, definitivní formě, se říká aktuální nekonečno. Z řady důvodů věcných i filozofických dospěli Řekové —jak jsme již naznačili — k tomu, že lidskému zkoumání je přístupné pouze nekonečno potenciální. Proto když Eukleidés ve 3. století př. Kr. hovoří o přímce, má na mysli úsečku, kterou může „neomezeně" prodlužovat, nikdy ji však nemůže prodloužit „do nekonečna", jak si to dnes představujeme my. Z téhož důvodu formuluje Eukleidés tvrzení o počtu prvočísel tak, že jich je více než, jakékoliv předem dané množství, neboť věděl a uměl dokázat, že jich není jen konečně mnoho. Nemohl však říci, že jich je „nekonečně mnoho", protože to by musel připustit aktuální nekonečno, tvářit se, že vidí množinu všech prvočísel hotovou, dokončenou. A proto také, abychom nezůstali jen u příkladů z matematiky, byl vesmír v antickém Řecku konečný. Za nej vzdálenější sférou stálic nebylo nic a nikoho nenapadalo klást si otázku, JZa mnohé uveďme Zénóna z Eleje, který proslulými aporiemi, z nichž nejznámější je Achilleus a želva, dokazoval nemožnost pohybu. Všechny aporie využívaly představy nekonečné dělitelnosti prostoru, respektive času. 110 IV. HISTORICKÝ VÝVOJ TEORIE MNOŽIN kterou si my, navyklí již nekonečnu aktuálnímu, snad ani nedovedeme nepoložit: co je za onou poslední sférou? Krása jejich vesmíru spočívala v jeho konečnosti, v řádu, který odpovídal jejich představám o harmonii světa. Vývoj pojmu nekonečno Chápání nekonečna, které se vyvinulo v antice, se udrželo dlouhá staletí. Lidskému poznávání bylo dáno nekonečno potenciální a myšlenka na aktuální nekonečno se jevila jako nepatřičná a člověku nepříslušející. Až velký raně renesanční myslitel Mikuláš Kusánský si jako jeden z prvních troufá rozvíjet myšlenku, co by to znamenalo, kdyby byl vesmír nekonečný. Jeho myšlenky však byly příliš odvážné a ojedinělé. Jen nesměle se v myšlenkách vědců rodily otázky, které nám dnes připadají samozřejmé, především pak ta, která v 70. letech 19. století koneckonců stála u zrodu teorie množin: má vůbec smysl porovnávat nekonečné systémy podle velikosti? Tuto otázku si například v roce 1638 položil jeden z géniů oné doby, Galileo Galilei. Ten si vypsal dvě řady čísel: přirozená čísla 1,2,3,4,5,... a jejich druhé mocniny 1,4,6,16,25,... a uvědomil si, dnešní terminologií řečeno, že mezi těmito množinami existuje bijekce! To by však mělo znamenat, že uvedené systémy čísel jsou stejně velké! A to se, vcelku zákonitě, Ga-lileimu jevilo jako naprostý nesmysl. Vždyť přece jeden ze základních Eukleidových logických axiómů, které byly nezpochybnitelným pilířem tehdejší matematiky, říká, že celek je větší než, část. A tady se zdá, že by druhý systém, který je evidentní částí prvního, měl být stejně velký. Jaký závěr z této „absurdní" situace Galilei vyvodil? Pro nekonečné systémy nemá otázka o jejich velikosti naprosto žádný smysl! Takový tedy byl stav úvah o nekonečnu zhruba v polovině 17. století. A záhy se měla celá situace ještě více zkomplikovat. Uvažovalo-li se zatím o (potenciálně) nekonečně velkých veličinách, ve druhé polovině 17. století se situace ještě více zdramatizovala. Jak je všeobecně známo, vzniká v této době diferenciální a integrální počet. Přestože jeho tvůrci Gottfried Wilhelm Leibniz a Isaac Newton přistoupili k jeho výstavbě z odlišných pozic, byl infinitesimální počet u obou založen na pojmu nekonečně malé veličiny. Jakkoliv tento pojem nebyl řádně definován a pravidla pro počítání s nekonečně malými veličinami byla dána jen velmi vágně, ukázalo se záhy, že diferenciální a integrální počet je vskutku mocným nástrojem nejen v matematice, ale i v řadě aplikací, především pak ve fyzice. Nejasnosti v jeho základech se však postupně vyhrocovaly a posléze v 18. století vyústily ve stav, který dnes nazýváme druhou krizí matematiky. 1. Vývoj pojmu nekonečno. 111 Problémy matematické analýzy se postupně odstraňovaly až od počátku 19. století. Zásadní roli zde sehrál Augustin Louis Cauchy zavedením limity na počátku dvacátých let, významně však do této problematiky zasáhl svými pracemi z matematické analýzy i Bolzano.2 Dospěli jsme tak v tomto stručném přehledu do období, v němž Bolzano píše své dílo Paradoxy nekonečna, které nás v souvislosti s teorií množin mimořádně zajímá. Zrekapitulujeme-li tedy stav v polovině 19. století, lze říci následující: vědecká komunita pracuje s potenciálním nekonečnem a odmítá nekonečno aktuální jako něco, co není přístupno lidskému zkoumání. V matematické analýze již sice existují nástroje k odstranění problémů s „nekonečně malými" veličinami, přesto však v matematické, fyzikální a další literatuře přetrvávají nesprávné a nelogické postupy, které člověka s tak kritickým a analytickým myšlením, jaké měl Bolzano, musely zákonitě vyprovokovat k formulaci svého náhledu na problematiku nekonečna. B. Bolzano a „Paradoxy nekonečna" Paradoxy nekonečna, nejznámější Bolzanova kniha, vyšly v roce 1851, tři roky po jeho smrti. Bolzano ji psal poslední dva roky před smrtí, v letech 1847 - 1848, a tak ji lze v mnoha ohledech považovat za vyvrcholení a uzavření jeho díla. Jakkoliv si Bolzano sám ze svých knih nejvíce cenil monumentální čtyřdílné učebnice logiky a metodologie vědy Wissenschaftlehre (v českém překladu Vědosloví), ovlivnily právě Paradoxy nekonečna další vývoj matematiky ze všech jeho děl nejvýrazněji. Podstatnou měrou k tomu samozřejmě přispěla i ta skutečnost, že rukopis nestihl osud mnoha jeho dalších děl, která zůstala ležet v nezpracované pozůstalosti dlouhá desetiletí. Bolzanův žák, František Příhonský, jenž po Bolzanově smrti rukopis obdržel se žádostí o přípravu do tisku, se tohoto úkolu vskutku obětavě a zodpovědně ujal a tak v roce 1851 mohly Paradoxy v Lipsku opravdu vyjít.3 Paradoxy nekonečna přitom nejsou ryze matematickou knihou. Jde spíše o dílo matematicko-filozofické, v němž je značná pozornost věnována i fyzice, lépe řečeno fyzikálnímu nazírání na svět, teologii apod. Bezesporu však je skutečností, jak v dalším ukážeme, že právě „matematické" pasáže knihy patří k těm pozoruhodnějším. Sledujeme-li vývoj hodnocení Bolzanova přínosu ke světové matematice, vypozorujeme záhy dva obvyklé extrémy: od přehlížení k nekritickému nadsazování a k podsouvání myšlenek a úmyslů, které Bolzano prokazatelně neměl. Jak v dalším uvedeme, hlavní Bolzanův přínos 2Poznamenejme, že tento proces zpřesňování matematické analýzy dovršil ve 2. polovině 19. století Karl Weierstrass zavedením tzv. „e — <5 jazyka". V rámci těchto snah byla v 70. letech minulého století řádně zavedena reálná čísla G. Cantorem a Richardem Dedekindem. V systému reálných čísel již samozřejmě nemohou existovat žádné „nekonečně malé" veličiny. 3Jak známo, Bolzano psal své práce německy nebo latinsky. Originální název německy psaných Paradoxů je Paradoxien des Unendlichen. Česky vyšly Paradoxy nekonečna až v roce 1963 (!) v zasvěceném překladu Otakara Zicha, který knihu doprovodil podrobnými poznámkami a komentárem. Z tohoto překladu také v dalším textu citujeme. 112 IV. HISTORICKÝ VÝVOJ TEORIE MNOŽIN lze spatřovat v těch myšlenkových proudech, které za zhruba čtvrt století vyvrcholily vznikem teorie množin. Zakladatel této teorie, Georg Cantor, Paradoxy dobře znal a vysoce je hodnotil.4 V této souvislosti se často píše o Bolzanovi jako o spoluzakladateli teorie množin, což je poněkud nadsazené a někdy se dokonce objevují evidentní nesprávnosti. Tak například jeden z nejznámějších historiků matematiky, Dirk Struik, píše, že Bolzano dospěl k pojmu spočetné a nespočetné množiny, což je naprostá nepravda. Pokusme se tedy objektivně zhodnotit faktický přínos Paradoxů nekonečna. Ty jsou ostatně natolik významné a v mnoha ohledech dodnes inspirativní, že ani v nejmenším nepotřebují nekritické a přehnané hodnocení k tomu, aby byly popravu považovány za jedno z nejvýznam-nějších děl matematické literatury minulého století. Obsah Paradoxů nekonečna Jak jsme již uvedli, nejsou Paradoxy ryze matematickou knihou, ale dílem, v němž se prolínají pasáže matematické, fyzikální, filozofické a teologické. Kdybychom se stručně snažili vystihnout základní myšlenky celého díla, byly by to asi dvě následující: 1. zdůvodnění, proč je v matematice nutno pracovat i s aktuálním nekonečnem; 2. analýza chyb, jichž se vědci dopouštějí při úvahách o nekonečnu. První z uvedených myšlenek Bolzano zdůraznil již mottem celé knihy, za něž si zvolil následující Leibnizův citát: Jsem natolik pro aktuální nekonečno, ž.e namísto abych připustil, Ž.e se ho příroda děsí, jak se běžně říká, jsem přesvědčen, ž.e je má v oblibě všude, aby lépe zdůraznila dokonalosti svého Tvůrce.5 Celá práce6 je rozdělena do 70 paragrafů. I přečtení obsahu, v němž jsou jednotlivé paragrafy stručně charakterizovány, dá čtenáři alespoň hrubou orientaci o obsahu práce. Současně se však může stát zdrojem omylů a dezinterpretací podobných Struikovu omylu, o němž jsme se zmínili před chvílí. Například §19 má „název" Existují nekonečné množiny, které jsou větší nebo menší než. jiné nekonečné množiny. To by mohlo vskutku evokovat dojem, že Bolzano dospěl k něčemu, co připomíná pojem kardinální číslo a odtud je pak jen krůček k tomu podsouvat mu „objevení" spočetných a nespočetných množin. Jak v dalším uvedeme, je podstata úplně jiná; Bolzano pouze v této pasáži dokumentuje, že například jedna úsečka (obsahující nekonečně mnoho bodů) může být částí jiné, větší úsečky apod. K pojmu „kardinální číslo", jak rovněž uvidíme, Bolzano ani v náznaku nedospěl. 4V práci Über unendliche lineare Punktmannigfaltigkeiten, Math. Ann. 21(1883) o nich píše jako o „skvělém a obsažném díle". 5Z terminologického hlediska je přitom zajímavé, že Bolzano v celé knize sám ani jednou neužije pojmu „aktuální", resp. „potenciální" nekonečno. Z celého jeho textu je evidentní, že aktuální nekonečno považoval za tak samozřejmé, že nepotřebovalo žádný přívlastek. Naopak, potenciální nekonečno dle něho žádným faktickým nekonečnem není, což v různých obměnách mnohokrát opisuje. 6Bolzanův text, bez poznámkového aparátu překladatele, má v českém překladu 100 stran. 1. Vývoj pojmu nekonečno. 113 Všimněme si nyní konečně obsahu Paradoxů systematicky a podrobněji. Prvních deset paragrafů tvoří stručný Bolzanův výklad toho, jak je nutno chápat pojem „nekonečný souhrn"; v naší dnešní terminologii je to nekonečná množina. Tato část dnešnímu čtenáři připadne zcela samozřejmá a argumentaci jistě přijme bez problémů, neboť je s aktuálním nekonečnem zvyklý zcela běžně pracovat. Následující pasáže knihy jsou polemikou a kritikou názorů některých filozofů a matematiků. Ocitujme některé pasáže z 11. a 12. paragrafu; v nich lze snadno vystopovat Bolzanův vztah k potenciálnímu nekonečnu. (Poznamenejme v této souvislosti, že například Cauchyho zmiňuje Bolzano ve své práci několikrát, vždy však v souvislostech poněkud nelichotivých. V pozdějších úvahách o matematické analýze, kde by odvolání se na Cauchyho bylo zcela na místě, se o něm zato nezmiňuje vůbec. Analogicky lze vystopovat i jeho „náklonnost" k některým filosofům, například k Hegelovi.) §11 Tímto nekonečnem, tak dobře známým matematikům, nelze však ještě uspokojit některé filosofy, zvláště novější doby, jako Hegela a jeho přívržence, kteří je pohrdavě nazývají špatným nekonečnem a tvrdí, že znají ještě mnohem vyšší, pravé, kvalitativní nekonečno, které nacházejí zejména v bohu a vůbec jen v absolutnu. Jestliže si myslí, jako Hegel, Erdmann a jiní, matematické nekonečno pouze jako veličinu, která je proměnná a jejíž růst nemá žádnou hranici (což ovšem mnozí matematikové, jak brzo uvidíme, stanovili jako výměr svého pojmu), pak s nimi souhlasím, když kritizují tento pojem jako veličinu do nekonečna pouze rostoucí, nikdy však nekonečna nedosahující. ... §12 Nevidím však také jinou možnost, než zamítnout jako nesprávné i jiné výměry nekonečna, jež byly podány samotnými matematiky v domnění, že představují jenom součásti tohoto jednoho a téhož pojmu. 1. Vskutku byli někteří matematikové přesvědčeni, jak jsem právě výše poznamenal, mezi nimi sám Cauchy (ve svém Cours d'Analyse a mnoha jiných spisech), autor článku „Nekonečno" v Klugelově slovníku, že definují nekonečno, jestliže je popíší jako proměnnou veličinu, jejíž hodnota neomezeně roste a podle toho může být větší než jakákoli sebe větší daná veličina. Mezí tohoto neomezeného růstu je nekonečně velká veličina. Tak je tangenta pravého úhlu, myšlená jako spojitá veličina, neomezená, bez konce, ve vlastním slova smyslu nekonečná. Chybnost tohoto výměru vysvítá již z toho, že co nazývají matematikové proměnnou veličinou, není vlastně veličina, nýbrž pouhý pojem, pouhá představa veličiny, a to taková představa, která v sobě pojímá nejen jednu jedinou veličinu, nýbrž dokonce nekonečně mnoho veličin, které se navzájem liší 114 IV. HISTORICKÝ VÝVOJ TEORIE MNOŽIN ve své hodnotě, tj. ve své velikosti. To, co nazýváme nekonečným, nejsou ony různé hodnoty, které tu představuje výraz tangens 0 a < 1) nelze jednoznačně přiřadit souhrnu (v). Tak najdeme zřetelný rozdíl mezi tak zvaným kontinuem a souhrnem utvořeným ze všech reálných algebraických čísel. §1. Vraťme se k rovnici (1), které vyhovuje algebraické číslo co a která je za uvedených předpokladů plně určena. Zvětšeme číslo n — 1, kde n je stupeň čísla co, o součet absolutních hodnot koeficientů uvedené rovnice a označme výsledek N; 2. Georg Cantor a jeho dílo 123 N nazveme výškou čísla co. Při použití obvyklého označení tedy platí N = n — 1 + |a0| + \ai\ + ■ ■ ■ + \an\. (3) Výška N je podle toho pro každé reálné algebraické číslo co jisté kladné celé číslo; obráceně, ke každé kladné celočíselné hodnotě N existuje jen konečně mnoho algebraických reálných čísel o výšce N; jejich počet označme cp(N). Je například cp(l) = 1, (p(2) = 2, (p(3) = 4. Nyní čísla souhrnu (co), tj. algebraická reálná čísla, postupně uspořádáme do řady tak, že nejprve vezmeme číslo co\ jako jediné číslo o výšce 1; poté vezmeme následující cp(2) =2 algebraická reálná čísla o výšce 2 a označme je co2, coj. K těmto můžeme připojit cp(3) = 4 čísla o výšce N = 3 tak, aby jejich velikosti vzrůstaly. Obecně můžeme tímto způsobem očíslovat všechna čísla z (co) až do určité výšky N = N\, rozmístit je na určená místa a za ně připojit reálná algebraická čísla o výšce N = N\ + 1 a sice tak, aby jejich velikosti vzrůstaly. Takto obdržíme souhrn (co) všech reálných algebraických čísel ve tvaru a s ohledem na dané uspořádání můžeme hovořit o v-tém reálném algebraickém čísle, přičemž není opomenuto žádné z čísel souhrnu (co). Je-li dána jakýmkoliv způsobem utvořená nekonečná řada navzájem různých reálných veličin lze v každém zadaném intervalu (a... P) určit číslo r\ (a tedy nekonečně mnoho takových čísel), které se nevyskytuje v řadě (4). Toto tvrzení nyní dokážeme. Mějme tedy libovolně zadaný interval (a ... P) takový, že a < ji. První dvě čísla naší řady (4), která leží uvnitř tohoto intervalu (z něhož vyloučíme hranici) můžeme označit a', B' tak, že a' < B1'. Stejně tak označme první dvě čísla z naší řady, která leží uvnitř (a'... B') jako a", B" a to tak, že a" < ji"; podle téhož pravidla utvoříme následující interval (a" ... B") atd. Zde uvedená čísla a',a" ... jsou podle definice jistá čísla naší řady (4), jejichž velikosti se monotónně mění a totéž platí o číslech velikost čísel a', a", ... neustále roste, velikost čísel B', p", ... klesá. Každý z intervalů (a ... P), (a'... p'), (a" ... p"), ... v sobě uzavírá všechny následující. — Jsou tedy nyní myslitelné dvě možnosti. Buďto je počet takto utvořených intervalů konečný; poslední z nich nechť je (cr(v)... /6(v)). Protože uvnitř tohoto intervalu může ležet nejvýše jedno číslo řady (4), můžeme Ců\, co2, ..., cov, ... §2. COi, co2, . .. ,cov, . . . (4) 124 IV. HISTORICKÝ VÝVOJ TEORIE MNOŽIN v tomto intervalu zvolit číslo n, které není ve (4) obsaženo. V tomto případě je věta dokázána. Nebo je počet utvořených intervalů nekonečně velký. Pak ale mají čísla a, a', a", ..., vzhledem k tomu, že jejich velikosti neustále rostou aniž by rostly do nekonečna, jistou horní závoru a°°. Totéž platí pro čísla 0, 0', 0", ..., jejichž velikosti klesají; jejich závoru označme Je-li a°° = (což je případ, který vždy nastane v případě souhrnu (co) všech reálných algebraických čísel), lze se lehce přesvědčit, podíváme-li se nazpět na definici intervalu, že číslo n = a°° = nemůže být v naší řadě obsaženo. (Kdyby totiž bylo číslo n v naší řadě obsaženo, měli bychom n = cop, kde p je jistý index. To však není možné, protože cop neleží uvnitř intervalu (a^ ... fí^), zatímco číslo n podle definice uvnitř tohoto intervalu leží.) Je-li však a°° < pak žádné číslo n z vnitřku intervalu (a°° ... y6°°) nebo též hranice tohoto intervalu, pokud jen odpovídá uvedeným požadavkům, není v řadě (4) obsaženo. Tvrzení dokázaná v tomto odstavci nám umožňují různá zobecnění, z nichž zvolíme následující: „Je-li cox, co2 , ..., co„, ... konečná nebo nekonečná řada vzájemně lineárně nezávislých čísel (takže není splněna žádná rovnice tvaru a\(ů\ + a^co^ + • • • + a„co„ = 0 s celočíselnými koeficienty, které nejsou všechny nulové) a je-li dán souhrn (Q) všech takových čísel Q, která lze určit pomocí racionálních funkcí s celočíselnými koeficienty z daných čísel co, pak v každém intervalu (a ... ji) existuje nekonečně mnoho čísel, která nejsou v (Q) obsažena." Skutečně, můžeme se podobně jako v §1 přesvědčit, že souhrn (Q) lze seřadit do tvaru í2j, £^2> ■ ■ ■ > > ■ ■ ■ > z čehož, vzhledem k §2, plyne správnost tvrzení. ★ ★ ★ Druhou Cantorovou prací, kterou zde v překladu uvedeme, je článek uveřejněný v r. 1890. V této krátké stati se poprvé objevuje známá důkazová metoda, dnes běžně nazývaná Cantorova diagonální metoda. Vyjádřeno v řeči kardinálních čísel je zde dokázáno, že 2^° > Ko a poté je ukázáno, že zcela analogicky lze pro každé kardinální číslo odvodit 2m > m. Povšimněme si, že ani v této práci se nevyskytuje pojem „množina", i když v této době již Cantor toto pojmenování v jiných pracích užíval. O jedné elementární otázce z nauky o souhrnech V práci nazvané: O jedné vlastnosti souhrnu všech reálných algebraických čísel (Journ. Math. Bd. 77, S. 258) se poprvé nachází důkaz věty, že existují souhrny, 2. Georg Cantor a jeho dílo 125 které nelze, byť jsou nekonečné, jednoznačně přiřadit souhrnu všech konečných celých čísel 1, 2, 3, ..., v, ... nebo, jak říkáme, které nemají mohutnost číselné řady 1, 2, 3, ..., v, ... .Z toho, co jsme tam dokázali v §2, okamžitě plyne, že například systém všech reálných čísel ležících v libovolném intervalu (a ... fJ) nelze sestavit do řady tvaru COi, ců2, ... ,cův, ... . Toto tvrzení však lze dokázat mnohem jednodušeji, nezávisle na vlastnostech iracionálních čísel. Jsou-li totiž m a w dva navzájem rozdílné objekty, můžeme studovat souhrn M prvků tvaru E = (xi,x2, ... ,xv, ...), které závisí na nekonečně mnoha souřadnicích xi, x2, ■ ■ ■, xv, ..., kde každá z těchto souřadnic je buďto m nebo w. K prvkům M patří například tři následující: E1 = (m, m, m, m, .. .), E11 = (w, w, w, w, . ..), E111 = (m, w, m,w, .. .). Nyní tvrdím, že takový systém M nemá mohutnost řady 1,2,..., v, . . . . Plyne to z následující věty: Je-li E\, E2, ■ ■ ■ , Ev, .. . jakákoliv jednoduchá nekonečná řada prvků systému M, pak existuje prvek Eq z, M, který není žádným z prvků Ev. K důkazu nechť je Ei = (<3i,i, tii,2, ■ ■ ■ , ®i,v, ■ ■ ■), E2 = ( a2,2> ■ ■ ■ ' a2,v, ■ ■ ■), ........................... Tato ajJLjV jsou zde buďto m nebo w. Buď E li = OV.l* aíí,2> ■ ■ ■ , ati,v, ■ ■ ■), nyní řada bi, b2, , ..., bv,... definována tak, že bv bude rovněž rovno m nebo w a přitom různé od avjV. Je-li tedy av jV = m, nechť je bv = w a je-li av jV = w, nechť bv = m. Povšimneme-li si nyní prvku Eo = (bi, b2, b3,...) z M, vidíme okamžitě, že rovnost £0 = EIÁ nemůže být splněna pro žádné celé číslo jjL. Kdyby totiž pro jisté jjl a pro všechny hodnoty v platilo 126 IV. HISTORICKÝ VÝVOJ TEORIE MNOŽIN pak by zejména platilo což je podle definice čísla bv vyloučeno. Z této věty bezprostředně plyne, že souhrn všech prvků z M nelze seřadit do tvaru řady E\, E2, ..., Ev, ...; dostali bychom totiž spor, že Eq by současně bylo i nebylo prvkem M. Tento důkaz překvapuje nejen svou velkou jednoduchostí, ale zejména tím, že princip v něm uvedený lze bezprostředně použít k důkazu obecnějšího tvrzení, že totiž mohutnosti systémů nemají maximum, což je totéž jako tvrzení, že ke každému zadanému systému L existuje jiný systém M, který má větší mohutnost než L. Buď například L lineární kontinuum, jako třeba souhrn všech reálných čísel, která jsou > 0 a < 1. Pod M rozumějme souhrn všech jednoznačných funkcí f(x), které nabývají hodnot 0 nebo 1, přičemž x proběhne všechny reálné hodnoty, které jsou > 0 a < 1. To, že M nemá menší mohutnost než L, plyne z toho, že v M existují podmnožiny, které mají stejnou mohutnost jako L; například je to podmnožina utvořená z těch funkcí proměnné x, které mají v jednom jediném xo z x hodnotu 1 a ve všech ostatních x mají hodnotu 0. M ale nemá ani stejnou mohutnost jako L. Kdybychom totiž souhrn M mohli jednoznačně popsat pomocí proměnné z, mohli bychom si M představit ve tvaru jednoznačné funkce obou proměnných x a z a. (1) Lehce lze dokázat, že když a < b, b < c, pak také a < c. Právě tak okamžitě z definice plyne, že když P\ je část množiny P, pak z a < P\ plyne také a < P a ze vztahu P < b plyne P\ b." §4. UMOCŇOVÁNÍ MOHUTNOSTÍ „Pokrytím množiny N prvky množiny M" nebo stručněji „pokrytím N prvky M" rozumíme pravidlo, kterým je s každým prvkem n z N svázán jistý prvek z M, přičemž jeden a tentýž prvek z M může být použit i opakovaně. Takto je tedy prvek z M, který je svázán s n, jistou jednoznačnou funkcí n a můžeme ho proto označit f (ji). Tuto funkci nazveme „pokrývači funkcí prvků n". Odpovídající pokrytí množiny N označíme f(N). Řekneme, že dvě pokrytí f\(N) a f2(N) jsou si rovna právě tehdy, když pro všechny prvky n z N platí rovnost f1(n) = f2(n); (1) to znamená, že když existuje byť jen jediný prvek n = no, pro který uvedená rovnost není splněna, pak již považujeme pokrytí f\(N) a f2(N) za navzájem různá. 2. Georg Cantor a jeho dílo 131 Kupříkladu můžeme, když Oto je jistý prvek z M, zadat pro všechny n f (n) = mQ. Takto je pak určeno pokrytí N prvky množiny M. Jiné pokrytí obdržíme, když pro dva různé prvky Oto a m\ z M a pro jistý prvek no z N zadáme f(n0) = ot0, f(n) = ml pro všechna n různá od n$. Souhrn všech rozdílných pokrytí N množinou M tvoří jistou množinu s prvky f(N). Nazveme ji „množinou všech pokrytí N prvky M" a označíme ji (N\M). Je tedy mm(N\M) = {/(#)}. (2) Platí-li M ~ M' a N ~ pak lze lehce odvodit, že také (N\M) ~ (iV'|M'). (3) Kardinální číslo množiny (N\M) tedy závisí jen na kardinálních číslech M = a a N = b. Můžeme proto definovat mocninu ab takto: afc = (N\M). (4) §6. NEJMENŠÍ KARDINÁLNÍ ČÍSLO ALEF NULA Množiny s konečným kardinálním číslem nazýváme „konečnými množinami"; všechny ostatní množiny nazýváme „transfmitními množinami" a jejich odpovídající kardinální čísla nazýváme „transfmitními kardinálními čísly". Souhrn všech konečných kardinálních čísel v nám udává následující příklad transfmitní množiny; jí odpovídající kardinální číslo (§1) „alef nula", symbolicky Ko, definujeme vztahem K0 = M. (1) To, že Ko je transfmitní číslo, tj. není rovno žádnému konečnému číslu /x, plyne z té jednoduché skutečnosti, že když přidáme k množině {v} nějaký nový prvek eo, je sjednocení ({v}, eo) ekvivalentní s původní množinou {v}. Existuje totiž mezi 132 IV. HISTORICKÝ VÝVOJ TEORIE MNOŽIN nimi vzájemně jednoznačné přiřazení, při němž prvku eo odpovídá první prvek 1 druhé množiny, prvku v první množiny pak odpovídá prvek v + 1. Podle §3 tak dostáváme H0+1 = K0. (2) V §5 jsme však dokázali, že (pro konečná /x) je /x + 1 různé od /x, takže Ko není rovno žádnému konečnému číslu /x. Číslo Ko je větší než všechna konečná čísla /x: K0 > /x. (3) Toto plyne okamžitě z §3, neboť/x = {1, 2, 3, ..., /x}, žádná část množiny {1, 2, 3, ..., /x} není ekvivalentní s množinou {v} a samotná množina {1, 2, 3, ..., /x} je částí {v}. Na druhé straně je Ko nejmenší transfmitní kardinální číslo. Je-li a jakékoliv transfmitní kardinální číslo různé od Ko, Pak K0 < a. (4) Toto plyne z následujících vět: A. V každé transfmitní množině T existuje podmnožina s kardinálním číslem Důkaz: Odstraníme-li podle nějakého pravidla z T konečný počet prvků t\, t2, ■ ■ ■, tv-i, zůstane zde pořád možnost odstranit i další prvek tv. Množina {?„}, kde v je libovolné konečné kardinální číslo, je podmnožinou v T s kardinálním číslem Ho, protože {tv} ~ {v} (§1). B. Je-li S transfmitní množina s kardinálním číslem Ho a S\ je transfmitní podmnožina v S, pak je rovněž. S\ = Ho- §15. ČÍSLA DRUHÉ ČÍSELNÉ TŘÍDY Z(K0) Druhá číselná třída Z (Ho) je souhrn {a} všech ordinálních typů dobře uspořádaných množin, jejichž kardinální číslo je Ho (§6). A. Druhá číselná třída obsahuje nejmenší prvek co = Limvv. Důkaz: Symbolem a> rozumíme typ dobře uspořádané množiny Fq = (fi, fi, ■ ■ ■, fv, ■ ■ ■), (1) 3. Antinomie teorie množin. 133 kde v probíhá všechna konečná ordinální čísla a f v < fv+1- (2) Je tedy (§7) co = F0 (3) a (§6) co = K0. (4) co je tedy číslo druhé třídy a sice to nejmenší. Je-li y jakékoliv ordinální číslo < co, musí být (§14) typem nějakého řezu v Fq. Fq má však pouze řezy s konečným ordinálním číslem v. Proto platí y = v. Neexistuje tedy transfinitní ordinální číslo, které by bylo menší než co, takže co je nejmenší takové. Podle toho, co jsme uvedli v §14 o Limvcrv je zřejmě co = Limvv. B. Je-li a libovolné číslo druhé třídy, pak za ním následuje jako nejbližší větší číslo téže číselné třídy číslo a + 1. 19. století bylo obdobím prudkého rozvoje přírodních i společenských věd. V řadách vědců řady oborů narůstá uspokojení nad dosaženými výsledky: zdá se jim, že přírodní vědy zmapovaly a popsaly vše podstatné v reálném světě. Zasloužilo by si hlubšího rozboru, čím to bylo způsobeno, že téměř současně — na přelomu 19. a 20. století — dochází v řadě z nich, včetně matematiky, k dramatickému zvratu. Tak například známý americký fyzik Albert Abraham Michelson, jehož jistě nebudeme podezírat z malého přehledu a nedostatku odbornosti, v roce 1894 prohlašuje: Důležité základní zákony a fakta ve fyzice již. byly všechny objeveny a jsou dnes tak pevně prokázány, ž.e možnost, ž.e by vůbec kdy byly nahrazeny v důsledku nových objevů, je nesmírně vzdálená... Naše budoucí objevy je třeba hledat na šestém desetinném místě! A = (f1,f2,..., /„) 3 Antinomie teorie množin. Třetí krize matematiky Nikdy není tak zle, aby nemohlo být ještě hůř. Gattusovo rozšíření Murphyho zákona 134 IV. HISTORICKÝ VÝVOJ TEORIE MNOŽIN Dva roky poté, v r. 1896, objevuje Antoine Henri Becquerel přirozenou radioaktivitu, v r. 1905 publikuje Albert Einstein speciální teorii relativity (vr. 1916 pak obecnou), ve 20. letech se konstituuje kvantová mechanika atd.: co z fyzikálního obrazu světa z konce 19. století vlastně přetrvalo až do dneška? Něco podobného se na přelomu století odehrálo i v matematice, s důsledky pro matematiku samotnou asi ještě závažnějšími. Uváděli jsme již, jak podrážděné reakce vyvolaly první Cantorovy množinové práce. Postupně se však prokázalo, jak mocným a potřebným nástrojem se teorie množin pro matematiku stala. Ke konci 19. století dosáhla teorie množin téměř všeobecného uznání a stala se základnou, na níž byla budována prakticky celá matematika. Všeobecné mínění matematiků té doby vystihuje známý výrok čelného francouzského matematika a fyzika Henri Poincarého, jednoho z vůdčích duchů tehdejšího vědeckého světa, který na II. mezinárodním matematickém kongresu v Paříži v roce 1900 prohlašuje: ... nyní v matematice zůstávají jen celá čísla a konečné, respektive nekonečné systémy celých čísel ... Matematika je plně aritmetizpvána. Dnes můžeme říci, ž.e dosáhla absolutní přesnosti. Je vskutku ironií osudu, že v době, kdy Poincaré tato slova pronášel, už bylo de facto jasné, že teorie oněch „nekonečných systémů celých čísel", jakožto část teorie množin, má k oné absolutní přesnosti dále než daleko. Antinomie teorie množin, z nichž první již byla tehdy známa, vyvedly matematiky krutě z mylného zdání, že mají k dispozici spolehlivou základnu pro výstavbu svých teorií. A strastiplná cesta za překonáním těchto antinomií, cesta, na jejíž konec matematika dodnes nedorazila, nám ukázala, jak podstatně je nutno revidovat původní představy o možnosti spolehlivého vybudování základů matematiky. (O tom však budeme podrobněji hovořit v §4.) Z tohoto hlediska není označení 3. krize matematiky pro období, které matematika od počátku 20. století prožívá, nijak přehnané. (Připomeňme si, že 1. krize matematiky cca v 5. stol. př. n.l. souvisela s objevem iracionálních čísel a se Zenónovými aporiemi o nemožnosti sestrojení konečných veličin z nekonečně mnoha částí. 2. krize matematiky, jak jsme již uvedli, je spojována s nejasnostmi kolem počítání s nekonečně malými veličinami. Newton a Leibniz při výstavbě infinitesimálního počtu nedovedli tyto operace řádně zdůvodnit. Během doby bylo čím dál nejasnější jak je možné, že nezdůvodněné postupy s přesně nedefinovanými veličinami dávají převážně správné výsledky. Tato krize byla překonána díky práci Cauchyho, Weierstrasse a dalších v 19. století.) V kapitole I jsme ukázali (viz větu 5.10), že když lze v nějaké teorii dokázat nějaké tvrzení a současně i jeho negaci, lze v této teorii dokázat každé tvrzení. Taková teorie je ovšem prakticky bezcenná. Přesně toto se ovšem stalo v Cantorově teorii množin, když se v ní objevily tzv. antinomie, někdy též nesprávně nazývané paradoxy. První z těchto antinomií publikoval v r. 1897 italský matematik Césare Búrali-Fořti v práci Una questione sui numeri transfiniti, Rendiconti Palermo 11, 154 - 164). Cantor sám znal tuto 3. Antinomie teorie množin. 135 antinomii již v r. 1895; spočívá v tom, že ordinální číslo dobře uspořádané množiny všech ordinálních čísel je větší než. všechna ordinální čísla (tzn., že existuje ordinální číslo větší než ono samo). (Srovnej s III. 6.2.) Po objevení této antinomie bylo ještě možno chovat jistou naději, že ji bude možno nějak odstranit a situaci tedy bude možno zachránit. (Samotný Cantor až do konce života věřil, že jeho teorii bude možno nějak „opravit".) V prvním desetiletí 20. století se však těchto antinomii objevila celá řada; jednoznačně se tak prokázalo, že tato sporná tvrzení se neobjevují jen na „periférii" matematiky a netýkají se jen objektů, bez nichž se lze snadno obejít, ale právě naopak, ukázalo se, že obtíže tkví v podstatě věci a celá teorie množin musí být vybudována na zcela nových základech. Za 80 let, které od té doby uplynuly, ovšem nebylo nalezeno všeobecně přijaté řešení této situace — viz §4. Nyní podáme stručný přehled nejznámějších antinomii. Nejznámější je antinomie, kterou v r. 1902 objevil a v r. 1903 publikoval anglický matematik, filozof, logik, sociolog a veřejný činitel, lord Bertrand Russell. (Nezávisle na něm objevil tuto antinomii rovněž Ernst Zermelo. Russellova antinomie spočívá, j ak j sme uvedli již v kapitole I, v tom, že když utvoříme „množinu S všech množin, které nejsou svým vlastním prvkem", vede ke sporu předpoklad S £ S i předpoklad S <£ S. Tato antinomie byla zpopularizována samotným Russellem a mnoha dalšími matematiky. Z celé řady těchto populárních variant uveďme alespoň následující: Jistý vojín, povoláním holič, dostal od svého velitele příkaz, že musí holit všechny vojáky své čety, kteří se neholí sami a nesmí holit nikoho jiného. Tím se ovšem tento vojín ocitl v neřešitelné situaci, neboť sám se má holit právě tehdy, když se sám nebude holit. V roce 1905 uveřejnil francouzský lékař a matematik — a v té době ředitel Oceánogra-fického muzea v Monaku — Jules Richard Richardova antinomieanúnomii, v níž vynikajícím způsobem využil (nebo zneužil?) Cantorovy diagonální metody. Nejsnáze lze tuto antinomii zformulovat takto: všech konečných posloupností českých slov (nazvěme tyto posloupnosti „větami") je spočetně mnoho. Některé z těchto vět jednoznačně definují nějaké reálné číslo, například „šest pětin", „nejmenší prvočíslo, které je větší než deset milionů" apod. Množina T všech těchto čísel je spočetná (neboť všech vět je pouze spočetně mnoho). Lze tedy množinu T uspořádat do posloupnosti. Nyní Cantorovou diagonální metodou sestrojíme číslo r £ T. To podle definice množiny znamená, že číslo r nelze definovat žádnou konečnou posloupností českých slov. To je však zřejmý spor s tím, že jsme takto číslo r právě definovali. Zjednodušením Richardovy antinomie je následující antinomie Berryho, kterou poprvé publikoval Russell v r. 1906: protože všech českých „vět" (ve výše uvedeném smyslu), které mají nejvýše 20 slov, je pouze konečně mnoho, existují nutně přirozená čísla, která takovou větou definovat nelze. Můžeme proto vyslovit následující definici: Buďk nejmenší přirozené číslo, které nelze definovat českou větou o nejvýše dvaceti slovech. Čtenář nechť si promyslí, co jsme právě udělali: větou o 14 slovech jsme definovali číslo, 136 IV. HISTORICKÝ VÝVOJ TEORIE MNOŽIN které nelze definovat žádnou větou, která by měla dvacet nebo méně slov! V literatuře (viz například [5]) lze najít ještě další antinomie. Uvedené ukázky však — doufejme — udávají dostatečný přehled o tom, jakého druhu byla ona tvrzení, která způsobila 3. krizi matematiky. Pravděpodobně je však nyní nutné podrobněji vysvětlit, proč uvedené antinomie nejsou jen zajímavými logickými hříčkami bez hlubšího významu (jak se původně řadě matematiků zdálo a jak na ně ostatně i dnes může pohlížet ten, kdo k matematice přistupuje „pseudoinženýrsky" jako ke snůšce výpočetních metod), ale závažnými problémy, které zbouraly pracně vybudovanou budovu moderní matematiky a způsobily v matematice dodnes nepřekonanou krizi. Nešlo jen o to, že se objevila v teorii množin sporná tvrzení, znehodnocující tuto teorii. Horší bylo, že — jak jsme již uvedli — v uvedené době již byla teorie množin základnou převážné části matematiky. (Je zřejmé, že to znamenalo, že teorii množin je nutno buďto „opravit" nebo najít jinou a „lepší" základnu. Co by však mělo a mohlo být onou novou základnou? To si prakticky nikdo nedovedl představit. Vynikající německý matematik David Hilbert, o němž budeme ještě hovořit v §4, to v r. 1925 vyjádřil často citovanými slovy: Nikdo nás nemůže vyhnat z ráje, který pro nás vybudoval Cantor. (Opravám „cantorovského ráje" se budeme věnovat v následujícím paragrafu.) Nejzávažnější důsledky antinomií však spočívaly ještě v něčem jiném. Připomeňme si, jaké bylo východisko Cantorovy teorie. „Množina" bylo jen synonymum slov souhrn, systém apod. Tento pojem je tak samozřejmý a názorný, že není nutno ho nijak definovat. (Podobně jako je v Eukleidově geometrii zřejmé, co je to bod nebo přímka. Ostatně pojem „množina" je jistě intuitivně jednodušší než například pojem „přímka".) O těchto souhrnech — množinách pak Cantor běžně užívanými matematickými a logickými metodami dokazuje tvrzení a odvozuje jejich vlastnosti. (Takto budované teorii se dnes říká „naivní", respektive „intuitivní" teorie množin.) Nebylo nejmenšího důvodu předpokládat, že teorie budovaná tímto způsobem by mohla být principiálně nesprávná; vždyť takto se matematika budovala od starověku. A přesto antinomie prokázaly, že matematiku takto bezelstně budovat nelze! Toto je nejzávažnější důsledek antinomií. A jaký je tedy „správný" způsob výstavby matematiky? Právě proto, že na odpovědi na tuto otázku se matematikové dodnes neshodli, hovoříme o důsledcích vzniklé situace jako o 3. krizi matematiky. Tato krize pochopitelně neznamená, že by se matematika ve 20. století nevyvíjela; dobře víme, že je tomu právě naopak. Tato krize samozřejmě ani nemá bezprostřední negativní důsledky na ty matematické disciplíny — a těch je samozřejmě většina — které přímo nesouvisejí s výstavbou základů matematiky. Matematik, který by se však stavěl do pozice, že jeho práce se toto všechno nedotýká, by nápadně připomínal pštrosa, strkajícího hlavu do písku. Jeden z velkých matematiků 20. století, Hermann Weyl, jenž je právě autorem téze o nástupu 3. krize matematiky, tuto situaci charakterizoval v r. 1946 slovy: 4. Východiska z, krize 137 Méně než, kdykoliv dříve jsme přesvědčeni o prvotních základech logiky a matematiky. Jako všichni a všechno v dnešním světě prožíváme „krizi". Ta trvá už, téměř padesát let. Na první pohled nám nepřekáží v každodenní práci; mohu se však přiznat, ž,e ve skutečnosti měla silný vliv na mou matematickou činnost: směrovala mé zájmy do oblasti, která se mě zdála relativně „bezpečnou", a neustále ve mně podrývala nadšenia odhodlání nezbytné pro každou vědeckou práci. 4 Východiska z krize Když, se všechno daří, něco se pokazí. První Chisholmův zákon Jak jsme uvedli v §3, bylo po objevení antinomií teorie množin zřejmé, že dosavadní styl výstavby matematiky je neudržitelný. Přístup matematiků k řešení vzniklé situace byl samozřejmě odlišný podle jejich filozofického i profesionálního zaměření. Přesně definovat a ohraničit jednotlivé myšlenkové proudy je přitom nemožné. V hrubých rysech však lze říci, že základní přístup k řešení byl dvojí: intuicionistický a formalistický, přičemž mezi formalistické směry patří několik vyhraněných a velmi odlišných skupin. Podle intuicionistických názorů byla matematika v posledních desetiletích budována nepřípustnými metodami. Některá logická pravidla, zřejmě platná pro konečné systémy, jako například princip vyloučeného třetího (tertium non datur — viz větu 3.15 (2)v kapitole L), byla nedovoleným způsobem přenesena i na nekonečné systémy. Intuicionisté odmítají aktuální nekonečno, neuznávají existenční důkazy. Objekt, který nelze zkonstruovat pomocí jiných uznaných postupů, prostě neexistuje. Je evidentní, že tím před nimi vyvstaly obrovské potíže. Po formální i obsahové stránce byli nuceni prakticky nově budovat řadu matematických disciplín, neboť jen malá část klasické matematiky pro ně byla „přípustná". V poslední době sílí tendence dívat se na intuicionismus jako na historickou kuriozitu. Přínos intuicionistů k rozvoji matematiky však byl nemalý. A přinejmenším k zamyšlení by nás měla přimět skutečnost, že mezi ně patřila řada nejvěhlasnějších matematiků posledních generací. První intuicionistické ideje v novodobé matematice lze najít v 70. - 80. letech 19. století v díle Leopolda Kroneckera, o němž již z §2 víme, že stál v čele proticantorovského hnutí. Zrod moderního intuicionismu je však spojován se jménem holandského matematika Leutzena Egberta Jana Brouwera, který základní intuicionistické ideje zformuloval ve své disertační práci v r. 1907. Kromě již zmíněných H. Weyla a H. Poincarého lze k intuicionistům přiřadit například matematiky takového kalibru, jako byli Emile Borel, Henri Leon Lebesgue či Nikolaj Nikolajevič Lužin. Základní formalistické přístupy k výstavbě teorie množin a základům matematiky jsou 138 IV. HISTORICKÝ VÝVOJ TEORIE MNOŽIN dvojí: metoda teorie typů a axiomatická výstavba. Zakladatelem teorie typů je již několikrát zmiňovaný B. Russell. Podle jeho mínění byly antinomie způsobeny tím, že pomocí všech prvků daného systému byl opět definován prvek daného systému. V teorii typů, kde jsou jednotlivé pojmy „hierarchicky" rozvrstveny, nemůže být pomocí prvků jisté úrovně definován prvek téže úrovně. Tím je samozřejmě vyloučen vznik antinomií Russellova druhu. Z prací rozvíjejících teorii typů uveďme alespoň dvě nejvýznam-nější a nejznámější. Je to především tzv. New Foundations amerického matematika Ormana Willarda van Quinea poprvé publikovaná v r. 1937 a dále tzv. Systém £ jiného amerického matematika Hao Wanga, poprvé Wangem popsaný v roce 1954. Teorie typů bývá často nesprávně zaměňována s jiným filozoficko-matematickým směrem, tzv. logicismem. Původ této záměny je jednoduchý — hlavním představitelem logicismu je zakladatel teorie typů Bertrand Russell. Zformulovat hlavní tezi logicismu není jednoduché; vyžadovalo by to zevrubnější rozbor vzájemného vztahu matematiky a matematické logiky. Nepřesně ji lze vyslovit asi následovně: všechny speciální matematické pojmy lz.e definovat pomocí slovníku matematické logiky a k důkazům matematických tvrzení není třeba žádných axiómů kromě logických ani žádných odvozpvacích pravidel kromě těch, která jsou akceptována logikou. Faktickým zakladatelem logicismu byl německý matematik Friedrich Ludwig Gottlob Frege. Jakou ideou byl Frege veden? Poslední čtvrtina 19. století byla obdobím značně úspěšné aritmetizace matematiky. (Svědectvím o této skutečnosti je například Poincarého výrok, který jsme citovali v úvodu 3. paragrafu nebo známý výrok Kroneckerův: Celá čísla stvořil Bůh, vše ostatní je dílem lidí.) Frege se pokoušel aritmetiku zredukovat na logiku. Jeho dílo zůstalo v době vzniku prakticky nepochopeno. Až Russell na tuto ideu navázal a pokoušel se totéž udělat s Cantorovou teorií množin. Právě při této práci přišel na onu klasickou antinomii nazvanou jeho jménem. Základním dílem logicismu je třídílná monografie Principia Mathematica, kterou v letech 1910-1913 vydal Russell společně s anglickým matematikem, filozofem a logikem Alfredem Northern Whiteheadem. Logicismus měl sice značný vliv na rozvoj matematické logiky, mezi matematiky však logicistická redukce matematiky na odnož logiky nikdy nezaznamenala větší ohlas. Většina matematiků za východisko z krize považovala axiomatickou výstavbu matematiky. Dnes je to nejběžnější a nejuznávanější způsob budování matematických teorií. Axiomatické metody již dokonce dávno překročily rámec matematiky samotné a jsou stále hojněji užívány i v jiných vědách, a to nejen přírodních. Proto se o nich zmíníme podrobněji. Je samozřejmé, že při deduktivní výstavbě nějaké vědecké teorie, kdy složitější pojmy definujeme pomocí pojmů jednodušších a nová tvrzení odvozujeme z tvrzení již dokázaných, není principiálně možno definovat všechny pojmy a dokázat všechna tvrzení. Na jisté úrovni je nutno započít; jisté tzv. „primitivní" pojmy je nutno zavést bez definice a jistá tvrzení — 4. Východiska z. krize 139 tzv. axiómy —je nutno pokládat za pravdivé bez důkazu. Zásady takové deduktivní výstavby vědy zpracoval již Aristoteles. První — a geniální — takto zpracované matematické dílo jsou Eukleidovy Základy. Nový impuls pro rozvoj axiomatické metody dala opět geometrie. Pokusy o důkaz 5. Eukleidova postulátu o rovnoběžkách, vedoucí — jak známo - až ke vzniku neeukleidovské geometrie, vyvolaly nový zájem o důslednou axiomatizaci geometrie. Tato práce byla završena dílem Davida Hilberta Grundlagen der Geometrie (1899), o němž se ještě později zmíníme. A 20. století je obdobím konjunktury axiomatického přístupu k matematice. Je samozřejmé, že v průběhu doby axiomatické metody zaznamenaly značný vnitřní vývoj. Tento proces lze zhruba rozdělit do tří základních etap: (a) tradiční axiomatika (Eukleidés); (b) formální axiomatika (19. století); (c) formalizovaná axiomatika (20. století). V čem spočívají hlavní rozdíly mezi axiomatikami jednotlivých období? Tradiční axiomatika byla popisována v běžném hovorovém jazyce. V tom ovšem bylo potenciálně skryto nebezpečí, že se v takto budované teorii objeví nepřesnosti, nejasnosti nebo dokonce zásadní obtíže; žádný hovorový jazyk není natolik přesný, aby se tomu dalo zabránit. Za druhé, při tradiční axiomatice nejsou přesně zformulována pravidla pro odvozování jedněch výroků z druhých. Při „intuitivně jasném" odvozování je ovšem vyloučena jednoznačná kontrola správnosti úsudků. Jak prokázaly antinomie, byla především tato okolnost zdrojem těch největších problémů. A konečně, v klasické axiomatice byly axiómy tvrzení, která nebylo nutno dokazovat proto, že byla zcela „samozřejmá". Teorie byla v tomto slova smyslu budována „sémanticky". V dalších dvou etapách vývoje axiomatických metod došlo ve všech uvedených bodech k výrazným změnám. Již ve 2. etapě, při budování formální axiomatiky, dochází mimo jiné k tomu, že: (a) je dán přesný počet výchozích pojmů a tvrzení; (b) jsou přesně stanovena odvozovací pravidla; (c) systém axiómů se mění v souhrn pravidel implicitně určujících, jak je možno pracovat s výchozími pojmy; (d) proces formální výstavby axiomatického systému je oddělován od jeho možných interpretací (tzv. modelů); (e) zkoumá se nezávislost, bezespornost a úplnost systémů axiómů (jak o tom hovoříme dále) pomocí modelů daného systému. 140 IV. HISTORICKÝ VÝVOJ TEORIE MNOŽIN Ve třetí, formalizovane etapě, dochází navíc k důslednému oddělení jazyka, v němž je daná teorie budována (tzv. „objektový jazyk") od jazyka užívaného k popisu objektového jazyka (tzv. „metajazyk"). (Rada antinomií právě vznikla záměnou těchto dvou jazyků.) Objektový jazyk je přitom „symbolizován", tj. na začátku je zadána „abeceda" (souhrn užívaných symbolů -znaků), jsou udána pravidla, jak tvořit, respektive poznávat správně utvořená „slova" (nazývaná „formule") a jsou dána pravidla odvozování jedněch formulí z dalších. Za axiómy jsou pak prohlášeny některé z formulí. Proces oddělení formální výstavby teorie od jejích modelů je takto zcela dovršen. (V uvedeném smyslu je například geometrie vyučovaná na školách pouze jedním z možných modelů axiomatické eukleidovské geometrie. Podobně je tomu s teorií množin, vyučovanou dnes u nás již od 1. třídy. Již v 1. kapitole jsme ostatně uvedli, že ve školách se de facto učí model ZF teorie.) Ještě než začneme hovořit o axiomatických teoriích množin, stručně k uvedeným požadavkům na volbu axiómů. Ta samozřejmě není předem jednoznačně determinována; volba axiómů je do značné míry věcí libovůle toho, kdo danou teorii vytváří. Jako přirozené se však jevilo požadovat, aby zvolená soustava axiómů byla vždy: 1. nezávislá (tzn., že žádný z axiómů nelze odvodit ze zbývajících; takové tvrzení by evidentně nebylo nutno považovat za axióm); 2. úplná (tzn., že axiómů je dostatečně mnoho k tomu, abychom mohli každé tvrzení této teorie buďto dokázat nebo vyvrátit — tj. dokázat jeho negaci); 3. bezesporná (chceme mít zaručeno, že z axiómů nelze odvodit současně nějaké tvrzení i jeho negaci; víme, že takové teorie je bezcenná). Nyní je přirozená otázka, zda lze axiomatický systém s uvedenými vlastnostmi sestrojit. (Původně o tom ovšem nenapadlo nikoho pochybovat.) Relativně nejméně problémů působí nezávislost. Její případné porušení je de facto jen „kosmetickou vadou" dané teorie a její odstranění není obtížné. Není-li však teorie úplná, je to značně nepříjemné, neboť to značí, že v této teorii nutně existují tvrzení, která nelze ani dokázat, ani vyvrátit. (Zdálo by se ovšem, že tuto obtíž by mělo jít odstranit jednoduše přidáním dalších axiómů.) A není-li teorie bezesporná, je to pro ni naprostá katastrofa. Zatím však, co například pro eukleidovskou geometrii se podařilo úplnost a bezespornost prokázat ve výše uvedené Hilbertově monografii z r. 1899, dokázat úplnost a bezespornost budovaných axiomatických teorií množin se nikomu nepodařilo. To, že se podařilo objasnit, zda lze úplnou a bezespornou teorii množin (a další teorie) sestrojit, patří k největším úspěchům moderní matematiky. Skutečnost, že odpověď je záporná, byla jistě překvapující a nepříjemná. Značí totiž výrazné omezení možností axiomatických metod. Podrobněji však budeme o této problematice hovořit v §5. První úspěšnou axiomatickou teorií množin byla teorie, kterou v letech 1904 -1908 vybudoval již zmíněný německý matematik Ernst Zermelo. Základní Zermelova idea spočívala v tom, 4. Východiska z. krize 141 že nelze předpokládat —jak to činil Cantor — že každý souhrn objektů tvoří množinu. Pomocí axiómů je nutno dosáhnout toho, aby množin bylo „dostatečně mnoho", nikoliv však tolik, aby mohlo docházet k antinomiím. Žermelův systém axiómů později částečně modifikoval a dalšími axiómy doplnil izraelský matematik Abraham A. Fraenkel. Zermelo-Fraenkelova teorie množin (nadáleji budeme značit ZF) je dnes nejrozšířenější axiomatizovanou množinovou teorií. Skutečnost, že v rámci ZF nelze pracovat se všemi systémy, například se „systémem všech množin", „systémem všech grup" a podobně, je však v mnoha ohledech nepříjemná. V roce 1925 však publikoval americký matematik maďarského původu John von Neumann práci, v níž se mu podařilo tuto obtíž obejít. Jeho ideu využil švýcarský matematik Isaak Paul Bernays, který v letech 1937 - 1954 vypracoval vlastní axiomatiku teorie množin (přesněji řečeno „teorie tříd"). Taje základem tzv. Gódel-Bernaysovy teorie tříd (nadáleji značíme GB), která vznikla syntézou axiomatiky Bernaysovy a axiomatického systému Kurta Gódela, poprvé publikovaného v r. 1940. (O Gódelovi budeme podrobněji hovořit v §5.) Zatímco v ZF jsou nedefinované pojmy „množina" a e, jsou to v GB pojmy „třída" a e. Některé axiómy ZF jsou současně i axiómy v GB. Proto lze řadu množinových pojmů na třídy převést. (Například „obvyklé" množinové operace apod.) Třídy, které jsou prvkem nějaké jiné třídy, se v GB nazývají „množinami". „Vlastní třídy" jsou pak ty třídy, které množinami nejsou. Lze dokázat, že množiny ve smyslu ZF jsou i množinami ve smyslu GB (takže GB je vlastně „rozšířením" ZF). Vlastní třídou je například „třída všech množin". Na rozdíl od množin nemají vlastní třídy například žádné kardinální číslo. (Tuto problematiku jsme probírali v 1. kapitole.) Podrobnější rozbor role jednotlivých axiómů a přehled dalších axiomatických systémů nebudeme uvádět. Obojí lze nalézt například v již citované knize [5], kde je uveden i obsáhlý přehled další literatury. Pouze o jednom axiómu se pro jeho výjimečné postavení zmíníme podrobněji. Jak čtenář jistě tuší, máme nyní na mysli axióm výběru. Tento axióm, jak známo, nám zajišťuje, že k libovolnému systému neprázdných množin existuje množina, která má s každou z těchto množin jednoprvkový průnik. První — a negativní — zmínku o principu zformulovaném v tomto axiómu lze nalézt v r. 1890 u známého italského matematika Giuseppe Peana v práci Démostration de ľintegrabilité des équations differentielles ordinaires, Math. Ann. 37, 182-228. V roce 1902 se 0 tomto principu zmiňuje další italský matematik Beppo Levi. Intuitivně tohoto axiómu užíval 1 Cantor, aniž si ovšem uvědomoval, že užívá principu dosud v matematice, respektive v logice neužívaného. V této souvislosti je zajímavá jedna okolnost. Již v §2 jsme uvedli, jak těžce na Cantora již v r. 1884 doléhaly neúspěchy spojené s hypotézou kontinua. Cantor byl vždy pevně přesvědčen, že každá mohutnost je některým alefem, nikdy se mu však nepodařilo tuto skutečnost dokázat; dnes, po vyřešení hypotézy kontinua, je nám ovšem jasné, proč tomu tak bylo. Jak však v jednom dopise píše Cantorův žák Felix Bernstein — který v r. 1897 jako první dokázal 142 IV. HISTORICKÝ VÝVOJ TEORIE MNOŽIN známou větu o ekvivalenci dvou množin, po něm pojmenovanou (věta III. 2.1.) — pokoušel se někdy v r. 1901 společně s Cantorem sestrojit bijekci mezi kontinuem a množinou Z(Ko), která má mohutnost Kj. Přitom však narazili na nepřekonatelné těžkosti, které právě Levi navrhoval odstranit pomocí uvedeného principu. Axióm výběru poprvé explicitně zformuloval E. Zermelo v r. 1904 v práci Beweis, dass jede Menge wohlgeordnet werden kann, Math. Ann. 59, 514-516, kde ho užil, jak to ostatně název práce uvádí, k důkazu tvrzení, že každou množinu lze dobře uspořádat. (Tomuto tvrzení se dnes běžně říká Zermelova věta, axióm výběru pak bývá často nazýván Zermelovým axiómem.) Rada matematiků vznášela proti axiómu výběru od počátku četné výhrady. (Samozřejmě, že vzhledem ke své nekonstruktivnosti byl zcela nepřijatelný především pro intuicionisty.) Tyto výhrady se ještě zostřily poté, co Felix Hausdorff pomocí axiómu výběru dokázal tvrzení o paradoxním rozdělení koule; odvodil totiž, že její polovina je kongruentní s její třetinou. (Důkaz tohoto tvrzení je uveden v knize [8], která je první monografií věnovanou teorii množin. Tato kniha měla nesmírný vliv na řadu matematiků a na vývoj těch matematických disciplín, které jsou na teorii množin založené.) Později dokázali další autoři, především polští matematici Stefan Banach a Alfred Tarski i jiné paradoxní důsledky axiómu výběru. Jak se však záhy prokázalo, zamítnutí tohoto axiómu by na druhé straně způsobilo neskonalé problémy, neboť řadu „běžných" tvrzení v různých matematických teoriích nelze bez jeho užití prokázat. Poté, co A. Fraenkel v r. 1922 dokázal nezávislost axiómu výběru na ostatních axiómech v běžných teoriích množin a K. Gódel v r. 1938 odvodil jeho bezespornost, se situace víceméně ustálila ve stavu, který trvá dodnes. Axiómu výběru sice užíváme, ale jen tehdy, když je to nezbytné a jeho užití je většinou zdůrazněno. Jak přívrženci axiomatické výstavby matematiky, tak matematici přiklánějící se k teorii typů, samozřejmě cítili nutnost dokázat, že jimi budované teorie jsou bezesporné. Klasické metody, použitelné ještě například pro důkaz bezespornosti eukleidovské, respektive neeuklei-dovské geometrie, však nebyly pro disciplíny operující s aktuálním nekonečnem použitelné. Bylo proto nutné vypracovat k těmto účelům metodu novou. Nejsystematičtěji se tímto úkolem zabýval již několikrát zmiňovaný David Hilbert, autor návrhu dnes všeobecně nazývaného hilbertovský program. První nástin tohoto programu podal Hilbert již v r. 1904, aniž by se jím však dále zabýval. Až v roce 1917, kdy reagoval na neustálé výpady intuicionistů, se k této problematice vrátil a zabýval se jí pak prakticky do své smrti. Zvláště intenzívně se na tomto programu pracovalo v letech 1920 - 1930, kdy s Hilbertem spolupracovala celá řada mladých matematiků; kromě již zmíněných Bernayse a von Neumanna to byli především Wilhelm Ackermann a Jacques Herbrand. Stručně popišme, jaká byla Hilbertova idea. Vycházel z toho, že je nutno dokázat, že užívané matematické důkazové metody jsou dostatečně silné k tomu, aby jimi bylo možno vybudovat 5. Gôdelovy výsledky 143 celou klasickou matematiku včetně teorie množin, vycházející přitom z vhodně zvolených axiómů, současně však nejsou natolik silné, aby jejich aplikací bylo možno dojít k antinomiím. (Jak vidět, Hilbert byl skálopevně přesvědčen o správnosti základů klasické matematiky.) Celý tento program měl být realizován ve dvou etapách. V první etapě měla být matematika, především pak aritmetika, analýza a teorie množin, plně formalizována. Tato formalizace by spočívala v tom, že všechna pravdivá tvrzení, především samozřejmě axiómy, by byla převedena na posloupnosti symbolů zbavených jakéhokoliv obsahu. S těmito posloupnostmi by se pracovalo pomocí jistého počtu přesně definovaných od-vozovacích pravidel. Takto — ryze syntakticky — by byla vybudována klasická matematika, přičemž by k této práci nebylo zapotřebí prakticky žádné „intuice"; povolené transformace posloupností by vzhledem k fmitnosti všech procesů mohl teoreticky provádět i stroj. Ve druhé etapě mělo být dokázáno, že výše uvedeným způsobem nelze nikdy dojít ke spornému tvrzení, například k formuli „1 = 2". Použité metody přitom musí být natolik jednoduché, aby o jejich správnosti nebylo nejmenších pochyb. Základním požadavkem samozřejmě byla fmitnost. (Tuto část, v níž měla být dokázána bezespornost matematiky, nazval Hilbert mctamatcmatikou.) Na uvedeném programu vykonal Hilbert se svými žáky obrovský kus práce. V době, kdy se již zdálo, že celý program by mohl být zdárně ukončen, však výsledky A. Tarského, Alonza Churche a především K. Gódela prokázaly, že hilbertovský program je nerealizovatelný. Jak uvidíme v dalším paragrafu, plyne z Gódelových výsledků nerealizovatelnost 1. i 2. etapy. Hilbert, který byl ještě po objevení antinomií v Cantorově teorii množin tak pevně přesvědčen o správnosti základů matematiky, že prohlásil: Předpoklad existence objektivních rozporů ve vnějším světě je klasickým případem nesmyslu, nesl velmi těžce toto zhroucení svých idejí. Nedlouho před svou smrtí prohlásil: Kde máme hledat naději a jistotu, když, dokonce matematické myšlení selhalo. Dnes si sice nemyslíme, že selhalo matematické myšlení, avšak vyrovnat se s Gôdelovými výsledky znamenalo podstatně revidovat představy o možnostech formální výstavby matematiky — a nejen matematiky. 5 Gôdelovy výsledky Zákonitě musí jednou nastat ta nejhorší možná situace. Druhý Soddův zákon Kurt Gódel, jeden z nej větších matematiků a logiků moderní éry, se narodil v r. 1906 v Brně, kde absolvoval střední školu. Studoval na univerzitě ve Vídni, kde promoval v r. 1930. V r. 1940 emigroval do USA a až do své smrti v r. 1978 působil v Princetonu (což bylo mimo jiné působiště 144 IV. HISTORICKÝ VÝVOJ TEORIE MNOŽIN A. Einsteina). Dostalo se mu řady poct a uznání; jmenujme za všechny alespoň Einsteinovu cenu za rok 1951, což je nejvyšší americké ocenění vědecké práce. Svými výsledky ovlivnil tvář moderní matematiky jako málokdo jiný. V poslední době se stalo jistou módou citovat Gódelovy výsledky, zejména proslulou větu o neúplnosti z r. 1931 ([9]) i mimo matematiku (většinou samozřejmě nepřesně nebo zcela překroucené). Vzhledem k mimořádné závažnosti této věty se o ní zmíníme podrobněji. (Mohli bychom samozřejmě uvést původní Gódelovu práci, ale čtenář bez hlubší logické přípravy by pravděpodobně měl s jejím studiem nepřekonatelné potíže. V dalším se proto pokusíme alespoň popsat ideu důkazu, mimochodem geniální a elegantní.) Předpokládejme, že zkoumáme nějakou axiomatickou teorii T zahrnující aritmetiku (tj. axiómy aritmetiky jsou tvrzeními v T). Víme, že takovou teorií je například teorie množin. Jak dobře víme z kapitoly I, výstavba takové formalizovane teorie začíná zadáním abecedy. Označme abecedu teorie symbolem A. Vzhledem k tomu, že A je konečná nebo spočetná množina (což jistě můžeme bez újmy na obecnosti předpokládat), existuje jistě prosté zobrazení množiny A do množiny N všech přirozených čísel. Definujme speciálně toto zobrazení tak, že pro každé a e A je g (a) prvočíslo eventuálně číslo 1. Nechťje například toto zobrazení definováno takto: a: va=^«»-( ) V 3 = e X Y Z ... g(a): 1 2 3 5 7 11 13 17 19 23 29 31 37 41 ... Víme, že „slovo" nad danou abecedou je konečná posloupnost prvků množiny A. Protože je A nejvýše spočetná množina (a samozřejmě neprázdná), je množina S všech slov nad A spočetná. Existuje tedy prosté zobrazení h S -> N. Sestrojení této injekce nazýváme „gódelizací" dané množiny slov. Abychom ze znalosti čísla h(• a =>•. Označíme-li G množinu všech malých Gódelových čísel, je zřejmě G vlastní podmnožinou v N. I když je většina těchto čísel nesmírně veliká, lze pro každé přirozené číslo rozhodnout, zda platí x e G nebo x ^ G. Pro dané přirozené číslo x je tedy „x e G" aritmetické tvrzení. Víme však, že v teorii T se nepracuje se všemi slovy, ale jen s tzv. „formulemi", což jsou slova utvořená podle zadaných pravidel. Například X e Y je formule v teorii množin, =>• a =>• samozřejmě formule není. Označíme-li F množinu všech formulí, je F vlastní podmnožina množiny S. Množina všech konečných posloupností formulí je spočetná, protože F je nejvýše spočetná. Některé z těchto posloupností — vytvořené podle přesně stanovených pravidel — se nazývají „důkazy". Označme D množinu všech důkazů. 5. Gôdelovy výsledky 145 Je-li q>i,q>2, ... ,cpn důkaz, říkáme, že je to důkaz formule (pn a o formuli (pn říkáme, že je dokazatelná. (Dokazatelné formule jsou tedy poslední formule v důkazech.) Je zřejmé, že dokazatelná formule může mít i více důkazů (i když nalezení alespoň některého z nich může být nesmírně obtížné.) Je-li

x = u A y = v. Kartézským součinem množin A, B nazýváme množinu A x B := {[x, j]; x e A, j e B}. Je zřejmé, že operace x není komutativní. Nerozlišujeme-li však součiny (A x B) x C a A x (B x C), můžeme operaci x považovat za asociativní. Zejména je tak zřejmé, co rozumíme množinou A"+1 := A" x A pro každé přirozené n. (A1 = A). Relací mezi množinami A, B (v tomto pořadí) rozumíme každou podmnožinu q součinu A x B. Je-li g> relace mezi množinami A, B, nazýváme jejím definičním oborem množinu Domg> := {x e A; By e 5 tak, že [x, y] e £>}. Oborem hodnot této relace g> rozumíme množinu Sg> := {y e B; 3x e A tak, že [x, y] e g}. Je-li gCAxí relace, pak relace g>_1 k ní inverzní je relace mezi B, A definovaná takto: q'1 := {[x,y]; [y,x] £ g}. Je-li gCAxBaffCfixC, pak jejich složením rozumíme relaci a o q c A x C definovanou takto: cr o £ := {[x, z]; x e A, z, £ C, 3y e 5 tak, že [x, y] £ g, [y, z] e a}. Buď g> c A x B. Říkáme, že q je zobrazení z A do B, jestliže ke každému prvku x e A existuje nejvýše jeden prvek z & B takový, že [x, y] £ q. Místo [x, y] & q pak obvykle píšeme y = £>(x). Je-li g> zobrazení z A do 5 a platí Domg> = A, říkáme, že g> je zobrazení A do B. Tuto skutečnost symbolicky označíme q: A —> B. Zobrazení /: A -> 5 se nazývá surjektivní (též surjekce nebo zobrazení raa), jestliže 3/ = B. Zobrazení /: A -> 5 se nazývá injektivní (též injekce nebo prosté zobrazení), jestliže x, y e A, x ^y =» /(x) ^/(y). Zobrazení, které je současně injekcí i surjekcí, se nazývá bijekce. 150 Dodatek Je-li /: A -> B zobrazení, je relace / zobrazení z B do A zřejmě právě tehdy, když je / injektivní. Symbolem id^ rozumíme identické zobrazení na množině A (tj. zobrazení A do A definované tak, že id^(x) = x pro každý prvek x e A). Jsou-li A, B množiny, pak AB značí množinu všech zobrazení B do A. Buď /: A —> B, C c A. Restrikcí f\C zobrazení / na množinu C rozumíme zobrazení g.C—>B definované takto: g(x) = f(x) pro každý prvek x e C. Relace na množině Relací na množině A rozumíme každou podmnožinu g množiny A2. Označíme-li P(x) množinu všech podmnožin množiny X, je množina 9t(A) všech relací na A rovna množině P (A2). Diagonální relací na A rozumíme relaci := {[x, x]; x e A}. Je-li g> relace na A, píšeme místo [x, y] e g> obvykle xgy a místo [x, y] ^ g> píšeme xgTy. Některé často se vyskytující vlastnosti relací mají speciální pojmenování. Zejména řekneme, že relace g na A je: (a) reflexivní, jestliže pro každý prvek x e A platí xqx ; (b) areflexivní, jestliže pro každý prvek x e A platí xgx; (c) symetrická, jestliže x, y £ A, xg>y =>• yg>x ; (d) asymetrická, jestliže x, y e A, xg>y =>• ygx; (e) antisymetrická, jestliže x, y e A, xg>y A yg>x =>• x = y; (f) tranzitivní, jestliže x, y, z e A, xg>y A ygz, =>• xg>z; (g) úplná, jestliže pro každé x, y e A platí xgy nebo yg>x nebo x = y. Poněvadž relace na A jsou množiny, má smysl hovořit o průniku relací, sjednocení relací, rozdílu relací a podobně. Je například zřejmé, že když q, a jsou tranzitivní relace na A, pak q Ha je rovněž tranzitivní relace na A, avšak g U a je relace na A, která nemusí být tranzitivní. Uspořádané množiny Uspořádáním na množině A nazýváme každou relaci na A, která je současně reflexivní, antisymetrická i tranzitivní. Je-li A množina, g uspořádání na A, nazývá se dvojice (A,g) uspořádaná množina. Nemůže-li však dojít k nedorozumění, hovoříme často o uspořádané množině A (a nikoliv (A,g)). Je-li uspořádání g úplné, tj. pro každé dva prvky x, y e A platí xgy nebo ygx, nazývá se (A, g) řetězec. 151 Relaci uspořádání nejčastěji značíme symbolem <. Prvky x, y v uspořádané množině (A, <) se nazývají srovnatelné, platí-li x < y nebo y < x. V opačném případě se nazývají nesrovnatelné. Je-li x < y avšak i^j, píšeme x < y. Jestliže platí x < y a neexistuje z tak, že x < z < y, říkáme, že prvek y pokrývá prvek x (nebo prvek x je pokryt prvkem y). Uspořádaná množina se nazývá protiřetézec, když jsou každé dva její různé prvky nesrovnatelné. (Uspořádáním na této množině je pak zřejmě diagonální relace.) V řetězci jsou naopak každé dva prvky srovnatelné. Je-li A nějaký systém množin, pak je zřejmě inkluze c uspořádáním na A. Máme-li nějaký systém množin uspořádat, pak to právě nejčastěji uděláme inkluzí. Pro libovolnou množinu A jsou tedy (P(A), c) i (9t(A), c) uspořádané množiny. Konečné uspořádané množiny obvykle znázorňujeme tzv. hasseovským diagramem. Prvky uspořádané množiny A při tom znázorníme jako body v rovině, větší prvky umístíme „výše" než menší prvky a dva různé prvky spojíme úsečkou právě tehdy, když jeden pokrývá druhý. Na následujícím obrázku je hasseovský diagram množiny (P(A), c), kde A = {a, b, c}. {b,c} Je-li (A, <) uspořádaná množina, značí Ä množinu A s duálním uspořádáním, tj. množinu (A, >). Místo Ä se často píše též A*. Buďte A, B uspořádané množiny. Zobrazení f:A—> B se nazývá izotonní, jestliže pro každé dva prvky x, y e A platí: x < y =>• f (x) < f (y). Zobrazení /: A -> B se nazývá izomorfismus, když: (i) / je bijekce, (ii) / je izotonní, (iii) f^1 je izotonní. Uspořádané množiny A, B se nazývají izomorfní (což značíme A = B), jestliže existuje alespoň jeden izomorfismus f: A—> B. Buď A uspořádaná množina, 0 7^ B c A. Prvek a e A se nazývá horní závora množiny 5, když pro každý prvek x & B platí x < a. B se nazývá í/iora ohraničená (v A), jestliže v A existuje alespoň jedna horní závora množiny 5. Analogicky se definuje dolní závora a zJo/a ohraničená množina. Řekneme, že B je v A ohraničená, je-li v A ohraničená shora i zdola. 152 Dodatek Buď A uspořádaná množina. Prvek a e A se nazývá největší prvek množiny A, když pro každý prvek x e A platí x < a. Prvek a e A se nazývá maximální prvek množiny A, jestliže v A neexistuje prvek x > a. Analogicky je definován nejmenší a minimální prvek uspořádané množiny. Je zřejmé, že největší prvek v A je maximálním prvkem a nejmenší prvek minimálním prvkem. Největší (respektive nejmenší) prvek v A — pokud existuje —je určen jednoznačně, zatím co maximálních (respektive minimálních) prvků může v A existovat víc. Buď A uspořádaná množina, 0 / 8 c A. Nejmenší horní závora množiny B v A (pokud existuje) se nazývá suprémum množiny B v A; značíme ji sup^5. Z výše uvedeného plyne, že suprémum množiny — pokud existuje — je určeno jednoznačně. Duálně je definováno infimum množiny B v A (inf AB). Uspořádaná množina A se nazývá svaz, existuje-li pro každé dva prvky x, j e A jejich suprémum i infimum v A. A se nazývá úplný svaz, má-li každá 0^5 c A v A suprémum i infimum. Je zřejmé, že pro každou množinu A je (P(A), c) úplný svaz. (Protože 9Í(A) = P (A2), plyne odtud, že systém všech relací na libovolné množině tvoří vzhledem k množinové inkluzi úplný svaz.) Ekvivalence a rozklady Relace q na množině A se nazývá ekvivalence, je-li reflexivní, symetrická a tranzitivní. Symbolem 8(A) označme množinu všech ekvivalencí na množině A. Snadno lze dokázat, že (S (A), c) je úplný svaz s nejmenším prvkem 0 a největším prvkem A2. Infimum neprázdné množiny relací je přitom jejich průnik, suprémum však obecně není jejich sjednocení (vzhledem k tomu, že sjednocení nezachovává tranzitivitu). Buď A ý 0 množina. Systém A po dvou disjunktních neprázdných podmnožin množiny A se nazývá rozklad na A, když U X = A. XčÄ Prvky rozkladu A nazýváme třídy rozkladu A. Každý prvek tak podle definice leží právě v jedné třídě daného rozkladu A. Označme X(A) množinu všech rozkladů na množině A. Definujme na X(A) relaci < takto: Pro A, B e X (A) je A < B právě tehdy, když ke každé třídě X e A existuje třída Y e B, tak, že X c y. Pak je < uspořádání na X (A). Je-li A < 5, říkáme, že A je zjemnení rozkladu B a B je zákryt rozkladu A. 153 Buď A ý 0 libovolná množina. Pak ke každé ekvivalenci g na A existuje právě jeden rozklad A na A a ke každému rozkladu A na A existuje právě jedna ekvivalence g na A tak, že pro každé prvky x, y e A platí xgy právě tehdy když x, y patří do téže třídy rozkladu A. Ve výše uvedeném smyslu každá ekvivalence g e 8(A) určuje právě jeden rozklad na A. Tento rozklad nazýváme faktormnozinou množiny A podle g; značíme jej A/g. Zobrazení F: S (A) —»- X(A) definované vztahem F(g) = A/g je nejen bijekce, ale dokonce izomorfismus (8(A), c) na (X(A), <). Platí tedy (g(A),Q = (X(A),<). Zejména odtud plyne, že (X(A), <) je úplný svaz. Literatura [1] KURATOWSKI K., MOSTOWSKI A.: Set Theory, Amsterdam, 1967. [2] tarski A.: Introduction to Logic and to the Methodology of Deductive Sciences, New York, 1965, český překlad: Úvod do logiky a metodologie deduktivních ve