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 cp výrokovou formulí ve smyslu definice 3.3, je p(
• ý), 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 formuliA, 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) 93 ~ -1-1A (c) 93 ~ A =3- ->A (d) 93 ~ -.(-.--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 (P2 ~ A v B, 934 ~ A =3- B,
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(r) ~ p(C), je-li p(A) ~ 0, je p(r) ~ 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
2.
3. Výrokový kalkul
23
Definujme nyní
(p ~ (->A„+1 A (pi) V (An+Í A 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 -"[A(^) 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 B) 4» D] ~ -.[A(-.A =>• Z?) a -/i(Z))] a -■[ä(D) a -/i(-A =^ 5)] ~ ~ -[-(-A a -5) a -.D] a -.[D a —(-A a -5)]
/i( )]} ~
~ -.] -.[-.(-.A a -5) a -.D] a -.[D a —(-A a -5)] a -[A a -.(-.C a -.-.D)
Je tedy
p ~ [(-A =» 5) 4» 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í Ý ~ Vxw(vu;) £ ~ f 4» (3x V z).
Pak jsou slova 93, i/r slučitelná, slova i/r, g> jsou také slučitelná, ale slova 93, q slučitelná nejsou.
Je zřejmé, že v žádné teorii nemá smysl uvažovat všechna možná slova vytvořená v abecedě definované v 4.1. „Správně" vytvořená slova budeme, podobně jako v §3, opět definovat rekurentně; udáme návod, jak lze ze slov jednodušších vytvářet slova složitější. K tomu je však především nutné mít k dispozici „základní", nejjednodušší formule, které již nevznikají z formulí jednodušších. Ve výrokovém kalkulu roli těchto formulí plnily přímo výrokové proměnné. V predikátovém kalkulu tuto úlohu zastávají tzv. primitivní predikáty.
30
I. FORMÁLNÍ VÝSTAVBA MATEMATIKY
Definovat primitivní predikáty však v této chvíli nemůžeme. Čtenář si již jistě uvědomil, že každá matematická teorie nutně má své vlastní primitivní predikáty. (Představíme-li si totiž, co po primitivních predikátech požadujeme, snadno si uvědomíme, že to zřejmě budou formule, z nichž se po dosazení konstant za proměnné stanou atomární výroky dané teorie; v aritmetice jsou to například slova „x < y", „x + y < z" apod., v teorii množin slovo „x e y" atd.).
Shrneme-li tedy uvedené úvahy, znamená to, že při budování každé teorie je nutno, kromě jiného, po zadání abecedy stanovit primitivní predikáty, přesněji řečeno: prohlásit některá slova za primitivní predikáty. V každé teorii jsou přitom tyto primitivní predikáty stanoveny jinak a je tak do značné míry na vůli toho, kdo teorii tvoří, která slova za primitivní predikáty prohlásí. Při jejich volbě je však užitečné dodržovat jistá pravidla.
Především je vhodné, aby primitivních predikátů bylo co nejméně. Poněvadž primitivní predikáty hrají roli nejjednodušších formulí, nesmí se v nich vyskytovat logické spojky a z mnoha důvodů předpokládáme, že se v nich nevyskytují ani kvantifikátory. (Později uvidíme, že teorii množin lze vybudovat pomocí jediného primitivního predikátu „x e y".) Často jsou primitivní predikáty stanoveny tak, že jsou za primitivní predikáty prohlášena jistá slova, z nichž lze všechny ostatní primitivní predikáty obdržet substitucí proměnných za proměnné.
Vlastnosti primitivních predikátů shrneme do následující úmluvy.
4.7. Dohoda.
1. Je-li (p primitivní predikát, pak se ve •, 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)cp v \fr značí ((3x)(cp)) v (\fr) a nikoliv (3x)(cp v \fr).
4.11. Definice. Řekneme, že predikátová formule je uzavřená, nevyskytuje-li se v ní podstatně volná proměnná.
4.12. Poznámka. Každé dvě uzavřené formule jsou slučitelné. Uvědomme si rovněž, že každé tvrzení matematické teorie je nutně uzavřenou formulí, což však zdaleka neznamená, že by každá uzavřená formule měla být pravdivým výrokem. Je-li 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) 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 y) (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)) -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 =>• A -<$. Podle pravidla 4.15 a věty 3.15(10) je
((p A ->q>) =>• Ý
elementární tautologie, takže xfr 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ť •,•£>•, 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 £ (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, y & 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 B 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, . ..} c A taková, ž,ex\ > x2 > • • • > x„ > . .. ,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 5 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 5, 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 -> 5. pro každý prvek x £ A platí x < f (x).
Důkaz. Označme Ä' = {x; x e A, /(x) < x} a připusťme, že K ý 0. Pak Ä' obsahuje nejmenší prvek xo. Položme x\ = f(xo). Protože je xq e K, je /(xo) = xi < xo- Protože je / izomorfismus, je /(xj < /(xo) = xi> tj- xi e K. To je však spor, neboťxq je nejmenší prvek množiny Ä'. 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 f(ao) e X c B, 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) 7^ 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) 7^ g(xo). Protože je / izomorfismus, je A(xo) = 5(/(xo)); protože je g izomorfismus, je A(xo) = B(g(xo)), takže 5(/(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 ý $ ý 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 // = B(&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) = y ten prvek v H, pro který platí A(x) = B(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 = 5(Z?0), tj. platí (2).
(c) G = A(a0), H = B. Pak je 5 = A(a0), tj. platí (3).
(d) G = A(oo), íř = B(feo).
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 & 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 < g j Aj < 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 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 //nebox e G, y, 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 Y G i množin G, přes
množinu 7 rozumíme uspořádanou množinu ([J G,■, <) s uspořádáním < definovaným takto:
pro x, y £ U G,- platí x < y právě tehdy, když nastane jedna z následujících možností:
ŕe/
(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 Y^, G i.
re/
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 = Y J k- Pak platí:
kčK
re/ 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 < j 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 • // <í=^> (l)yi < 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 yi = y2, y2 < y3, platí yj < y3 a tedy [xj, yj < [x3, y3]. Podobně v případě yj < 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 < Zi nebo zi = z2, [xi, Ji] < [x2, y2]. Avšak [x1; 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í [x1; yj < [x2, y2] v G • Yl Hi- nastane jedna z následujících dvou možností:
(1) yi < y2 v Y Hr,
(2) y: = 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 [x1; yj < < [x2, y2] v YG ■ Hi.
3. Aritmetika uspořádaných množin
65
Nechť tedy nastane případ (2). Pak existuje i'o e 7 tak, že y1; y2 £ 77!0. Tvrzení \x\, yj < < lx2, yi] v G ■ je však nyní ekvivalentní s tím, že
[xi, yi] < [x2, y2] v G ■ Hi0 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 + 77 ■ K. Tyto dvě množiny však nejsou ani izomorfní.
3.17. Věta. Budí ý $ 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 /(x) = [g,(x), /], kde i e I je ten prvek,
íe/
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 7, po dvou disjunktní dobře
uspořádané množiny. Pak je X A,- dobře uspořádaná množina.
íe/
Důkaz. Buď 0 5 c £ Aŕ libovolná. Označme 7B = {i; i e 7, 5 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 Ti 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, 77 dobře uspořádané množiny. Pak je také množina G ■ 77 dobře uspořádaná.
3.21. Důsledek. Buďte G, 77 konečné řetězce. Nechťmá řetězec G m prvků, a řetězec 77 nechť má n prvků. Pak je G ■ 77 ř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 AUBUCUDa 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 A,-.
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 M, j e M, x — y je racionálni číslo}.
Pak je zřejmě q ekvivalence na R. Utvoříme-li faktormnožinu m./q, je ihned vidět, že m./q je nekonečná množina a každá třída rozkladu m./q 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, , 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
(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 = {a21, a22, . .. ,a2„, . ..}
A-n &n2-> ■ ■ ■ > ■ ■ ■ }
Pak je ale [J Ai = {au, a\i, a2\, a^, a22, a^i, í*i4, <223> a32> a4i> ■ ■ ■ L takže množina A,- je
re/ re/
spočetná. •
76
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 a2, b2 £ A — {a\, b\], a2 ý b2 atd. Indukcí lze zřejmě v A sestrojit dvě disjunktní spočetné podmnožiny
B = (an)T=1, 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
n }. Pak je N2=[JP„ 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, BiCfi 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(Aj) 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
00
D := AnP|Aŕ.
Pak je zřejmé, že platí:
A = D U (A — Aj) u (Aj — A2) u (A2 - A3) u (A3 - A4) u ...
Aj = D U (Aj — 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 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,aia2a3 ■ ■ ■ > 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,aiiai2ai3 [J Aj takové, že pro každý index
kčK kčK
k e K platí f (k) e Ak- Pro každé y e Y nyní položme (py := (S) ® Ak vztahem [O^Ky) = ~1: W(a) A zřejmě také izotonní, takže cp je izomorfismus. •
5.27. Věta. Každá množina ordinálních čísel je dobře uspořádaná.
Důkaz. Buď M libovolná množina ordinálních čísel, N ý 0 její libovolná podmnožina. Zvolme a e N libovolně. Není-li a nejmenší prvek množiny N, je P = N n W(a) ^ 0. Protože je 0 ^ P c W(a), obsahuje množina P podle věty 5.26 nejmenší prvek f). Je však zřejmé, že p je nejmenší prvek množiny N, takže množina M je dobře uspořádaná. •
5.28. Poznámka. Buď M ^ 0 libovolná množina ordinálních čísel. Podle věty 5.27 je M = fi ordinální číslo. Podle věty 5.26 platí W(ijl) = /x, tj. W(ijl) = M. Podle věty 2.11 existuje právě jeden izomorfismus f:M—> 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(»ě 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)( -(Vx)-J[(x ey)4
4^éj)]4-(iéj)|, (ii) tj. xfr ~ (3x)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 ý 4>o existuje— například 0. Protože je Aq řetěz, je A e Aq-Nyní dokážeme, že je a = pA.
Připusťme, že je a ^ p a-Pak je a £ A+ D A, přičemž A+ e Aq: spor, neboť A je sjednocení všech množin z Aq, které neobsahují prvek a. Je tedy a = p a, tj. a = g (A), takže g je surjekce.
Tím je tvrzení (<5) dokázáno.
Defmujeme-li nyní na množině M relaci < takto:
x, y e M, x < y g~\x) c g-^v),
je zřejmé, že (M, <) je dobře uspořádaná, neboť g je evidentně izomorfismus.
Dokázali jsme tedy, že pomocí axiómu výběru lze dokázat Zermelovu větu. •
4.10. Poznámka. V důkazu Zermelovy věty jsme uvedli „konstrukci" dobrého uspořádání na libovolné množině M. Ve skutečnosti však obecně nedovedeme každou množinu dobře uspořádat (nelze například udat konkrétní dobré uspořádání množiny R všech reálných čísel, byť podle Zermelovy věty takové dobré uspořádání existuje). Víme již, že potíž tkví v podstatě axiómu výběru. Tohoto axiómu jsme užili jen v počátku důkazu, když jsme v každé množině vybírali jeden prvek. Právě tato okolnost však způsobila to, že důkaz Zermelovy věty je pouze „existenční" a nikoliv „konstruktivní".
Kapitola 3
Kardinální a ordinální čísla
1 Kardinálni číslo. Spočetné množiny
Věda má vždycky pravdu. Nenechte se zmást fakty. FlNAGLOVO KRÉDO
1.1. Definice. Řekneme, že množiny A, B jsou ekvivalentní a píšeme A ~ B, jestliže existuje bijekce f: A -> 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\ < b^ libovolná reálná čísla. Pak jsou intervaly (a\,a2), (^1,^2) ekvivalentní, neboť zobrazení /: (a\, a^) —> (b\, b^) definované vztahem
ž»2 — b\ f (x) = -(x - ai) + ^
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,-, B, (i e /), 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 £ / platí A t ~ B,. Pa£ (g) A, ~ (g) B,.
re/ re/
3. A ~ B P(A) ~ ^(5).
4. Jsou-li množiny A{ i množiny B, /?o dvow disjunktní a platí-li A,- ~ 5,- pro každé i £ /, p/aň'|J Ai ~ U
ŕe/ ŕe/
5. Jsou-li množiny Ai po dvou disjunktní, pak Ai£í ~ Q£) 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 B)c ~ (Ac x Bc).
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: y A, -> A, označme