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 ^;?) (p a-p) =» e (p a Q) =» p -(p a g) 4» (-p v-j3) -(p v g) 4» (-p a-j3) [(P ^Q)^P]^P P^lQ^(P^Q)] (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{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
2. 3. Výrokový kalkul 23 Definujme nyní (p ~ (->A„+1 A (pi) V (An+Í A c/>2). Výroková formule
An+i, B -> 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ď q) 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í xjr ~ 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ě • ((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)cp predikátová formule, jsou formule
1. (3x) y]. Pak je (Vx)cp =>• /(>) tautologie.
4.21. Poznámka. Jestliže je formule (Vx)cp nepravdivá, je formule (Vx)cp =>• /(>) tautologií triviálně. Pravidlo 4.20 rovněž není zajímavé v případě, kdy se proměnná x ve slově y]. Pak je
w]. Pak je
(3x)[(x e v) 4» (x e z)] 4» (3w)[(" e v) 4» (w e 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)) -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 =» Jj(3z)[(j 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 • neni co
dokazovat. Nechť tedy ý není totožná s 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 cp).
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 , 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 7. 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 £ I.
Pak je množina [J A,- nejvýše spočetná. re/
Důkaz. Je zřejmé, že stačí dokázat, že když je I 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 I = N.
re/
Každou z množin A, lze podle předpokladu uspořádat do posloupnosti takto:
Ai = {au, ai2, . .. , a\n, . ..}
a2 = {(221, <222, ■ ■ ■ , din, ■ ■ ■ }
Aft cin2, . .. , ann, . ..}
Pak je ale [J Ai = {au, a\i, a^\, au, «22, a3i, ai4, an, a32, a4i, ■ ■ ■}, 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 ř = (J 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 ^ 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.
re/
Pak je zřejmé, že platí:
A = z) u (A - Ai) u (Ai - A2) u (A2 - A3) u (A3 - A4) u ...
Ai = 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
777. 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,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é /: 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 X 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 = ^2 a fí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 • • • = £ 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
K bijekce, pak pro každé k e K platí
kčK
((pof)(k) =(p[f(k)] e Af(k), takže ( [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 [<í>( B. Pro každý prvek x e U Ba existuje právě jeden index ax e A takový, že x e Bax, neboť množiny Ba jsou
po dvou disjunktní. Položíme-li f(x) = [ax, fax(x)], je zřejmě / bijekce množiny U Ba na
množinu A x B. •
88
777. 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 /J e B, pak
Y\ ap= Wa = 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) = /^(/J)] (= (//? o (p)(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 7) Ŕ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 Na, tj. £ m„ < £ n„.
uea aeA aeA aeA aeA
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 =3- 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 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í p < a + 1 libovolné ordinální číslo. Podle definice uspořádání je p typ některého začátku množiny B, takže zřejmě platí p < a. Neexistuje tedy p takové, žea a + y -(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 ^