Matematický ústav Slezské univerzity v Opavě Logika a teorie množin M. Marvan LOGIKA A TEORIE MNOŽIN 1. Místo úvodu Tento text je určen posluchačům navštěvujícím přednášku Logika a teorie množin. Ve shodě s autorovými preferencemi pojednává zejména o Kelley-Morseově teorii s axiómem výběru a axiomem regularity, méně už o logice. Některé partie jsou prozatímně nahrazeny odkazem na knihu T. Salát a J. Smítal, Teória množin, což v textu označujeme odkazem [TM, n!-n2], kde nii n2 jsou čísla stránek, na nichž je příslušná partie vyložena v uvedené knize. 2. Úvod Teorie množin a matematická logika jsou dvě vzájemně provázané matematické disciplíny. Obě leží v základech moderní matematiky. Jako součásti matematiky obě vznikly v 19. století. Matematická logika je výsledkem snahy formalizovat proces matematického uvažování. Vytváří a používá jazyk, v němž lze formulovat matematická tvrzení i jejich důkazy. Pojednává obecně o axiomatických teoriích, důkazových metodách, dokazatelnosti, bezespornosti apod. Je nástrojem k rozhodování o pravdivosti v matematice. Mezi zakladatele náleží Gottlob Frege (1848-1925). Ve spisu Begriffsschrift (1879) si položil za cíl odhalit všechny logické principy matematických důkazů. Každý i intuitivně zřejmý krok bylo třeba rozpoznat a popsat jako axiom. V důsledku se aritmetika měla stát částí logiky. Vděčíme mu za zavedení kvantifikátorů V, 3. Na Fregeho navázali Giuseppe Peano (1858-1932), Bertrand Russel (1872-1970) a další. Teorie množin je speciální axiomatická teorie, jež dnes leží v základech prakticky všech ostatních matematických disciplín. Její prvotní podobu vytvořil německý matematik Georg Cantor (1845-1918). Významným předchůdcem byl Bernard Bolzano (1781-1848), autor knihy Paradoxy nekonečna (1851). 2.1. Naivní teorie množin Za zakládající publikaci teorie množin lze považovat Cantorův článek z roku 1874, v němž dokazuje existenci nekonečně mnoha transcendentních čísel (v jeho době byla známa pouze dvě transcendentní čísla, e a ir). Od počátku byla teorie množin přijímána jako poněkud kontroverzní (odmítali ji např. Kronecker, Brouwer, Poincaré). K vymezení všech pojmů Cantor používá přirozeného jazyka, jeho dílo neobsahuje žádnou definici množiny. Takto neformálně budovaná teorie se dnes nazývá naivní teorie množin. Cantor ji propracoval do značné hloubky; v ohnisku jeho zájmu ležel pojem mohutnost množiny. Množiny mají stejnou mohutnost, existuje-li mezi nimi bijekce. Jakmile Cantor mezi množiny zahrnul i souhrn SUT všech možných mohutností, vyvstal paradox. Ukázalo se, že samotná množina SUT by nutně měla ještě větší mohutnost, neobsazenou v SUT. O dva roky dříve, v roce 1887, Burali-Forti objevil podobný paradox v Cantorově teorii ordinálních čísel. Na Cantora navázal Frege dvousvazkovým dílem Základní zákony aritmetiky (Grundgesetze der Arithmetik) (1893, 1903). Pátý základní zákon se, v moderním označení, týkal množiny M0 = {X | c/>(X)} logika a teorie množin všech X, pro něž platí nějaká podmínka (p(X). Shodou okolností těsně před vydáním druhého svazku Bertrand Rüssel upozornil na paradox, vznikající ve speciálním případě N = {X I X <£ X}. Russelův paradox spočívá v tom, že obě možnosti JVgJVÍJV^JV vedou ke sporu. Vskutku, jestliže N E N, pak musí platit podmínka N ^ N. A naopak, jestliže N ^ N, pak nesmí platit podmínka N (jL N. Jelikož naivní pokusy o vybudování teorie množin nevedly ke zdaru, byla posléze vybudována jako axiomatická teorie. 2.2. Logické paradoxy Od antických dob jsou známy příklady logických úvah vedoucích k paradoxním závěrům. Výskyt paradoxů v základech matematiky je krajně nežádoucí. Příklad. Epimenidův paradox. V moderní verzi je obsažen v tvrzení "Tento výrok je nepravdivý." Epimenidés, sám Kréťan, pravil, že Kréťané [za všech okolností] lžou. Paradox nastává, snažíme-li se zjistit, zda je Epimenidův výrok pravdivý. V Epimenidově paradoxu snadno spatříme logický kruh, protože věta vypovídá o své vlastní (ne) pravdivosti. Příklad. Holičův paradox. Holič obdržel rozkaz holit všechny muže, kteří se neholí sami. Má holit sám sebe? Tímto způsobem Russel popularizoval svůj paradox zmíněný výše. Příklad. Grelling-Nelsonův paradox. Rozdělme přídavná jména středního rodu na heterologická a homologická. Přídavné jméno nechť je homologické, má-li za všech okolností vlastnost, kterou samo popisuje (například přídavná jména české, čtyřslabičné, pětislabičné, sedmnáctipísmenné, devot enáctipísmenné jsou homologická); nechť je heterologické v opačném případě. Paradox se vyjeví, pokusíme-li se určit, jaké je přídavné jméno heterologické. Příklad. Berryho paradox. Méně než deseti slovy lze určit jen konečně mnoho čísel. Proto existují čísla, která nelze určit méně než deseti slovy. Nicméně, každá neprázdná podmnožina množiny přirozených čísel má nejmenší prvek. Proto existuje "nejmenší číslo, které nelze určit méně než deseti slovy." Zde vzniká paradox, protože zmíněné číslo je určeno větou o devíti slovech. Následující příklad ukazuje, že následky může mít logický paradox i v reálném světě. Příklad. Arbitrův paradox. Dvě společnosti uzavřely smlouvu, v níž se mimo jiné dohodly, že v případě sporu se místo k soudu obrátí na arbitra, který jejich spor rozhodne. Jedna ze společností poté předložila nezpochybnitelné důkazy, že smlouva je od počátku neplatná. Pokud arbitr uzná, že smlouva je od počátku neplatná, pozbude práva spor rozhodnout. Pokud arbitr uzná platnost smlouvy a spor rozhodne, vzhledem k předloženým důkazům platnost smlouvy uznat nemůže. O logických paradoxech lze všeobecně říci, že vznikají, protože se nějaké výroky uplatňují siřeji, než bylo původně předvídáno a zamýšleno a nakonec vedou k nějaké formě logického kruhu. U lingvistických paradoxů vidíme i směšování jazyka jímž mluvíme s jazykem o němž mluvíme. 3. Axiomatická teorie množin a tříd V rámci naivní teorie množin vznikl Russelův paradox ohledně definice N = {X I X X}. 2 logika a teorie množin Obecně se můžeme ptát, zda lze korektně definovat soubor M0 = {X | 4>{x)} všech množin X, majících nějakou vlastnost (p(X) a zda je potom množina. Zdá se, že neexistuje žádný jednoduchý způsob, jak rozeznat přípustné vlastnosti 4>{X) od nepřípustných. Východiskem je vybudování axiomatické teorie množin, k čemuž bylo učiněno mnoho pokusů. Historicky první Zermelo-Fraenkelova teorie (zkráceně ZF) vzniku Russelova paradoxu zabraňuje tím, že nepovažuje zápis N = {X \ X ^ X} za korektní definici množiny. V rámci ZF N není množina; otázka co N je zůstává nezodpovězena. V důsledku potom není množinou ani soubor všech množin, načež není množinou ani soubor všech grup, všech topologických prostorů a podobných struktur. Nicméně, i takové soubory mohou být a bývají předmětem matematických úvah, například v teorii kategorií a na ni navazující algebraické topologii. Proto je žádoucí i těmto "nemnožinovým" souborům poskytnout místo v budované teorii. Ukazuje se, že soubor {X | (X)} všech množin X s vlastností 4>(X) sám o sobě k paradoxům nevede. Obecně však není množinou, nýbrž je příkladem tak zvané třídy. Třídy přirozeně vznikají i v teorii množin samotné (máme třídu všech množin, třídu všech kardinálních čísel, třídu všech ordinálních čísel, které nejsou množinami). Axiomatizujeme-li jen množiny, je za jejich hranicí naprostá terra incognita, axiomatizujeme-li třídy, je tam něco, s čím se dá pracovat. Třídy jsou axiomatizovány kupříkladu v Gôdel—Bernays-von Neumannově teorii a Kelley-Morseově teorii. Rozdíl mezi oběma posledně jmenovanými tkví v tom, že druhá je o něco odvážnější (bude upřesněno níže). Kelley teorii tříd uveřejnil v dodatku ke knize Obecná topologie (General topology) z roku 1957. S nepodstatnými odchylkami budeme níže budovat právě Kelley-Morseovu teorii. Při výkladu se budeme snažit, aby čtenář na konci chápal "co si lze dovolit s třídami" a "co si lze dovolit s množinami." Zdůrazněme, že množina je speciální případ třídy. 3.1. Formule Jazyk teorie tříd používá následující symboly: 1. Symbol G. Čte se "je prvkem" nebo "náleží do" nebo "patří do." 2. Symboly proměnných, což jsou malá i velká písmena latinské abecedy, případně i další symboly kromě symbolů uvedených v bodech 1, 3, 4, 5. 3. Logické spojky ~1, a, v, =>, <ř=>. 4. Kvantifikátory V, 3. 5. Závorky (, ). Například, x,X,y\,U2 jsou symboly proměnných. Označují třídy (a tedy i množiny jako speciální případ tříd). Nadbytečné závorky můžeme vynechat. Postupně budeme některé další užitečné symboly přidávat, např. =, ^, n, U, {, }, 0, 0, 1, 2, 3. Dále budeme induktivně definovat formule teorie tříd, zkráceně formule. Všechny formule budou neprázdné konečné posloupnosti symbolů jazyka teorie tříd. Ne všechny posloupnosti budou formule, protože ne všechny posloupnosti dávají smysl v teorii tříd. Například posloupnost x G y dává smysl a bude formulí, zatímco G x G a x\/3 nikoliv. Současně budeme definovat, které proměnné, vyskytující se ve formuli, jsou volné a které jsou vázané (každá bude buď volná anebo vázaná, nikoliv obojí). Pravdivost formule bude záležet na hodnotách volných proměnných. Vázané proměnné zase bude možné přejmenovat, podobně jako smíme přejmenovat sčítací index nebo integrační proměnnou. 3 logika a teorie množin Samotné formule budeme označovat písmeny řecké abecedy. Naše induktivní dennice obsahuje čtyři pravidla Fi až F4, která postupně uvedeme. Formulí bude každá posloupnost, která vznikne jako výsledek konečného počtu kroků, spočívajících v uplatnění některého z pravidel Fi až F4. Fi Každá posloupnost X G Y, kde X, Y jsou proměnné, je formule. Obě proměnné X, Y jsou volné. Formule zavedená pravidlem Fi se nazývá atomická formule. Jiné atomické formule nezavedeme. F2 Je-li (p formule, pak i ~\((p) je formule. Vázané a volné proměnné jsou u ~\((p) tytéž jako U (p. Příklad. Příkladem formule vzniklé podle pravidla F2 je formule ~~\(X G Y). Obvykle ji zkracujeme nal^ľ. Obě proměnné X, Y jsou volné. F3 Je-li (p formule a x její volná proměnná, pak (\/x)((p) resp. (3x)((f>) jsou formule. Proměnná x je v obou formulích (\/x)((p) a (3x)((f>) vázaná, ostatní proměnné jsou volné nebo vázané podle toho, zda jsou volné nebo vázané ve formuli (p. Čteme "pro každé x" resp. "existuje x." Uplatněním pravidla F3 jsme proměnnou x takzvaně kvantifikovali, přestala být volnou proměnnou a stala se vázanou. Příklad. Příkladem formule vzniklé podle pravidla F3 je (3a;) (x G X). Ve výchozí atomické formuli x £ X byly obě proměnné volné, ve výsledné formuli je x vázaná a X volná. Smysl formule (3a;) x E X je, že X je neprázdná. 3.1. Poznámky. 1. Závorky lze vynechávat, pokud to neohrožuje srozumitelnost. Například, pravidlo F3 vyžaduje, abychom psali (3x)((3X)(x G X)), ale množství závorek ke srozumitelnosti nepřispívá. Dostatečně srozumitelné jsou i zápisy (3x)(3X)(x G X) nebo dokonce 3x 3X x G X úplně bez závorek. V tomto textu se pokusíme zachovávat rozumné množství závorek, abychom dosáhli dobré srozumitelnosti i bez zavedení explicitních pravidel pro čtení (bez zavedení precedence operací). 2. Lze připustit i vázání proměnných, které se ve formuli vůbec nevyskytují, ale takový kvantifikátor je zbytečný. Abychom se mohli spolehnout, že proměnná je buď vázáná anebo volná, ale ne obojí, zavedeme slučitelnost formulí. 3.2. Definice. Říkáme, že formule cp, ip jsou slučitelné, jestliže každá proměnná, která se vyskytuje v obou formulích, je buď v obou vázaná nebo v obou volná. F4 Jsou-li , tjj slučitelné formule, pak WaW, WvW, (0)=^), (0)^(VO jsou formule; nazývají se složené formule. Proměnná je volná resp. vázaná ve složené formuli, je-li volná resp. vázaná v alespoň jedné z formulí (p,ip. 4 logika a teorie množin Příklad. Formule

), protože volné a vázané proměnné jsou u obou stejné, s výjimkou X, která se změnila z volné na vázanou. Platí-li tvrzení pro každou ze slučitelných formulí (p,ip, neexistuje proměnná, která by byla volná v jedné a vázaná v druhé, a proto tvrzení platí i pro složené formule (pAtp, Vip, 4> => tp, 4> <=>• tp. Nejsou-li dvě formule slučitelné, pak libovolnou společnou proměnnou, která je vázaná jen v jedné z formulí, můžeme přejmenovat, tj. označit jiným symbolem tak, aby se nový symbol v druhé formuli nevyskytoval. Takto si lze slučitelnost vždy vynutit. Později ukážeme, že takové přejmenování nemá vliv na pravdivost formule. Příklad. Uvažujme opět o neslučitelných formulích

(x) je pravdivá právě tehdy, když (p(x) platí pro všechna x; formule (3x) (p(x) je pravdivá právě tehdy, když existuje x takové, že platí 4>(x). P4 Pravdivost formulí (p Alp, 0 V ip, (p ip, (p <í=> ip v závislosti na pravdivosti formulí (p, ip je dána známou tabulkou: 4> ip (p Alp (pWip 4>^> ip 4> -^ip 1 1 1 1 1 1 1 0 0 1 0 0 0 1 0 1 1 0 0 0 0 0 1 1 5 logika a teorie množin Chybějící pravidlo Pi, umožňující posoudit pravdivost atomických formulí, uvedeme později. Kdybychom je mohli uvést již teď, nebylo by třeba budovat axiomatickou teorii, neboť bychom již teď mohli rozhodnout o pravdivosti všech formulí. Všimněme si, že (p <ř=> ip platí právě tehdy, když mají (p a ip stejné pravdivostní hodnoty. Formule (p a ip jsou pak co do pravdivosti a nepravdivosti zaměnitelné. Řekneme, že formule (p, ip jsou logicky ekvivalentní V tomto textu budeme logickou ekvivalenci formulí <4> ip platí'. Někdy se k zápisu logické ekvivalence používá symbol '='. Má vlastnost reflexivity ( = pro každou formuli ), symetrie (jestliže

= x)- Zdůrazněme však, že

{X,Uu...,Un)^(t>{Y,Uu...,Un) čili 4>(X, U\, .. ■, Un) a 4>(Y, U±, .. ., Un) platí nebo neplatí současně. Tvrzení dokážeme indukcí vzhledem k délce formule. Délkou formule se rozumí počet znaků ve formuli, sestrojené podle pravidel Fi až F4 včetně všech závorek. Je zřejmé, že atomické formule jsou nejkratší (každá sestává ze tří znaků) a každé pravidlo F2 až F4 vytváří formule delší než jsou jednotlivé komponenty. Důkaz. Je-li (p(X,U) atomická formule U e X, plyne tvrzení z definice rovnosti tříd. Je-li 4>{X, U) atomická formule X e U, plyne tvrzení z axiomu invariance, přesněji, z tvrzení 3.6. 7 logika a teorie množin Pro ostatní formule se postupuje indukcí. Předpokládejme, že tvrzení platí pro všechny formule kratší než formule (p(X, U\,..., Un). Nechť je formule (X, U±,..., Un) tvaru ~\tp(X, U±,..., Un) podle pravidla F2. Jelikož je ip(X, Ui,..., Un) kratší než tp(Y, U\,..., Un) podle indukčního předpokladu. Pak ovšem platí (X, U\,..., Un) <ř=> 4>(Y, U\,..., Un). Nechť je (X, Ui,..., Un), a proto platí ip(X, U, Ui,..., Un) ip(Y, U, Ui,..., Un) podle indukčního předpokladu. Načež ovšem 4>{X,U1,...,Un)^4>{Y,U1,...,Un). Analogicky ohledně pravidla F4. E$0. Schéma axiomů specifikace. Buď (x, U±,..., Un) formule s volnými proměnnými x, U\,..., Un, buď Z proměnná, která se ve cp nevyskytuje. Pak je (Vt/i) • • • (Vt/„)(3Z)(Vx) [x e Z & (x eU A 4>(x, ř7i,..., Un))} axiom. Slovy: Existuje třída Z, závislá na U±,. .. , Un, jejíž prvky jsou právě všechny množiny x takové, že platí (p(x, U\,..., Un). Třída Z se nazývá třída specifikovaná formulí4>{x, U±,.. ., Un) a označuje se {xeU I cPix,^,...,^)}. Odtud okamžitě plyne pravidlo pro rozhodování o pravdivosti atomických formulí s pravou stranou Z = {x E U \ (x, Ui,..., Un)}- Pi Nechť Z = {x E U \ (x, Ui,..., Un)} je třída specifikovaná formulí (x, U±,..., Un). Potom pro každou množinu x platí x E Z ^ x e V). Vztah ACBse nazývá inkluze. Ostrá inkluze A C B se zavádí formulí A c B & (A C B) A (A í B). Následující cvičení ukazuje, že C má vlastnosti uspořádání. 9 logika a teorie množin Cvičení. Ukažte, že platí U Q U (reflexivita), (U CV AV CU) ^ U = V (antisymetrie), (U CV AV CW) CW (tranzitivita). Cvičení. Ukažte, že platí 0 c u, u c u, u cv ouuv = v, u cv nv = u. Je-li U třída, zavádíme omezené kvantifikátory (3X G U) a (\/X G U) předpisem, že (3X G U) 4(X, Ui,..., Vn) & (3X) X G U A (X, Ví,..., Vn), (VX G U) 4(X, Ui,..., Vn) & (VX) X G U => 4>{X, ví, ..., K). platí pro libovolnou formuli 4>{X, V\,.. ., V„). Sjednocení a průnik třídy množin definujeme předpisem |J U = {x G U | (3X G t/) x G X} = {x G W | (3X) (X G t/ A x G X)}, f)u = {x e U \ (VX e U)x e X} = {x G U | (VX) (X G Č7 x G X)}. Vidíme, že P| U obsahuje právě ta x, která leží ve všech množinách X G U. Oproti tomu (J U obsahuje právě ta x, která leží v alespoň jedné množině X G U. Možný a obvyklý je též zápis xeu xeu 3.9. Tvrzení. Platí f|0 = w, U0 = Důkaz. Ohledně první rovnosti zřejmě P| 0 C U. Dokažme opačnou inkluzi U C P|0. Buď i G W libovolná množina. Ale x G P| 0 právě tehdy, když pro každou třídu X platí implikace Iel=^iGl. Taková implikace ovšem platí, a to z toho důvodu, že předpoklad X G 0 není nikdy pravdivý. Ohledně druhé rovnosti zřejmě 0 C (J0. Dokažme opačnou inkluzi (J0 C 0. Ale x G (J 0 právě tehdy, když pro každou třídu X platí X G 0 A x G X. Avšak X G 0 neplatí nikdy, a proto x G [J 0 neexistuje, a tudíž (J 0 C 0. Cvičení. Nechť ŕ7 C U. Ukažte, že pak platí 10 logika a teorie množin Cvičení. Nechť x £ X. Ukažte, že pak platí f] X c i c (Jx 3.8. Třída všech podmnožin Třída pU všech podmnožin třídy U je definována předpisem pU = {z g u I z c u}. Není snad nutno zdůrazňovat, že pokud t/ je vlastní třída, pak neexistuje třída všech podtříd v U. C. Dva axiomy ohledně podmnožin. Ci Je-li X množina a z c X, pak Z je množina. C2 Je-li X množina, pak pX je množina. Lze ukázat, že axiomy Ci, C2 lze nahradit jediným. Platí totiž věta 3.10. Tvrzení. Dvojice axiomů Ci, C2 je ekvivalentní axiomu c (\/x eU)(3Y eu)(\/z)(z cx ^ z eY). Důkaz. Nechť platí axiomy Ci a C2. Nechť X je množina. Položme Y = pX, což je množina podle C2, přičemž každá podtřída Z c x je množina podle Ci, a proto z g pX Tím je dokázána formule C. Nechť platí formule C. Nechť X je množina. Pak existuje množina Y taková, že pro každou třídu Z platí implikace Z c X => Z g U. Dokažme Ci. Jestliže zci, pak z g Y, a tedy z je množina a Ci je dokázáno. Dokažme C2. Snadno se vidí, že pX c U, načež pX je množina, protože U je množina. Tím je dokázáno C2. 3.11. Tvrzení. Univerzum U je vlastní třída. Důkaz. Připusťme, že U je množina. Pak i podtřída N = {X g U \ X ^ X} je množina a dostáváme spor N g N <ř=> N ^ N (Russelův paradox). Tudíž, U není množina. 3.9. Existence množin Všimněme si, že doposud jsme nedokázali existenci ani jedné množiny. Všechny doposud uvedené axiomy připouštějí i možnost, že vůbec žádná třída není množinou, čili možnost, že W = 0. D. Axiom existence množin. 0 g U, aneb prázdná třída je množina. Ekvivalentně stačí předpokládat existenci alespoň jedné množiny. 3.12. Tvrzení. Axiom D a tvrzení 11 logika a teorie množin jsou ekvivalentní. Důkaz. Je.li U neprázdná, pak existuje alespoň jedna množina, označme ji U. Jelikož 0 C U, je 0 rovněž množina podle Ci. 3.13. Tvrzení. P|W = 0, \Ju=U. Důkaz. Ohledně první rovnosti zřejmě 0 C f]U. Dokažme opačnou inkluzi f]U C 0. Připusťme, že existuje x E f]U. Jelikož 0 G U, z podmínky x G f]U plyne, že x náleží všem množinám, a tedy i prázdné množině, což je spor. Tudíž, x G f]U neexistuje. Ohledně druhé rovnosti zřejmě [JU C U. Dokažme opačnou inkluzi U C [JU. Buď x G U libovolná množina. Ale x G {JU právě tehdy, když existuje třída X taková, že X G U a x G X. Takové X existuje, například px. 3.10. Jednoprvková množina Je-li x množina, definujeme třídu {x} předpisem {x} = {y G U | y = x}. Cvičení. Rozhodněte, zda platí a) 9 e {0 i; b) 0C {0}. 3.14. Tvrzení. Platí (Vx G U) {x} G U, aneb je-li x množina, pak i {x} je množina. Důkaz. Nechť x je množina. Platí x G px, protože x Q x. Tudíž, {x} C px, načež {x} je množina, protože px je množina podle C2. Množina {x} se nazývá jednoprvková množina s prvkem x. Pokud stejný předpis použijeme v případě, že x je vlastní třída, dostaneme {a;} = 0, protože množina y splňující y = x neexistuje. Předpoklad, že x je množina, je lépe ponechat jako ochranu před možným nedorozuměním. Všimněte si, že už umíme sestrojit nekonečné množství množin 0, {0}, {{0}}, {{{0}}}, atd. Každé dvě jsou různé, což snadno zjistíme porovnáním prvků. Například 0 7^ {0}, protože množina na levé straně nemá žádné prvky a množina na pravé straně prvek má, a sice 0. Podobně {0} 7^ {{0}}, protože kdyby platila rovnost {0} = {{0}}, muselo by o jejich prvcích platit 0 = {0}, což jsme již vyloučili. Nicméně, všechny zatím konstruovatelné množiny jsou jednoprvkové. 3.15. Definice. Jsou-li x,y množiny, zavedeme třídu {x, y} = {u G W \ u = xWu = y} Je-li x =/= y, nazývá se dvouprvková třída s prvky x, y nebo též neuspořádaná dvojice prvků x, y. 12 logika a teorie množin Je-li x = y, pak evidentně {x,y} = {x} = {y}. E. Axiom dvojice. (Vx e U){Vy G U)(3u e U)(Vz e U) (z e u & (z = x V z = y)) čili jsou-li x, y množiny, pak třída {x, y} je množina. F. Axiom sjednocení. (VS1 eU) (]JS euy Je-li S množina, pak (J S1 je množina. Sjednocováním množiny množin vždy dostaneme zase množinu. To samozřejmě nemusí platit pro sjednocení vlastní třídy množin. Analogii pro průniky nepotřebujeme, protože plyne z axiomu Ci. Cvičení. XuY = \J{X,Y}. Vidíme, že i sjednocení dvou množin je množina (podle axiomu sjednocení). Všimněme si, že se zásoba prokazatelně existujících množin opět rozšířila, například o {0,{0}}, {0,{0,{0}}}, {0,{0,{0,{0}}}}, atd. Stále však jde o množiny s konečně mnoha prvky (zde vždy se dvěma prvky). Zřejmě {x,y} = {x} U {y}. Jsou-li x, y, z množiny, lze analogicky zavést {x, y, z} = {x, y} U {z} = {x} U {y} U {z}. A tak dále. 3.11. Kartézský součin Kartézský součin je další významná množinová konstrukce, kterou lze bez problémů rozšířit na třídy. 3.16. Definice. Nechť a, b jsou množiny, pak předpisem [a, b] = {{a},{a,b}} definujeme uspořádanou dvojici [a,b]. 3.17. Tvrzení. Jsou-li a, b, c, d množiny, pak [a, b] = [c, d] právě tehdy, když a = c A b = d. Důkaz. Rozborem možných případů snadno zjistíme, že {{a}, {a, b}} = {{c}, {c, d}} právě tehdy, když a = c a současně b = d. Uspořádaná dvojice [a, b] je jednoznačně určena zadáním dvou prvků a jejich pořadím, na rozdíl od množiny {a, b}, která je určena zadáním dvou prvků bez ohledu na pořadí. 13 logika a teorie množin 3.18. Definice. Jsou-li A, B třídy, definujeme třídu A x B = {x e U I (3a e A)(3b e B) x = [a, b}} všech uspořádaných dvojic [a, b] prvků tříd A, B a nazýváme ji kartézský součin tříd A, B. Běžně se používá i zápis A x B = {[a,b] | a e A, b e B}. Příklad. {9,0} x {4,*} = {P,*], [ b p~ľ a. 3.21. Definice. Buď p relace mezi třídami A, B, buď a relace mezi třídami B, C. Relace a o p (čti „a po p") mezi třídami A,C, definovaná předpisem (7 o p = {(a, c) | (3b G B)(a p b A b cr c)}, se nazývá složení relací p a cr. Cvičení. Buď p relace mezi třídami A, B. Pak platí 1. p o idA = p; 2. ids o p = p. Buď navíc a relace mezi třídami B, C. Pak platí 3. (a o p)-1 = p-1 o a-1. Cvičení. 1. Ukažte, že (p-1)-1 = P- 2. Nechť p C p', a C a'. Dokažte, že pak p o a C p' o a'. 3.13. Zobrazení Zobrazení je speciální případ relace mezi třídami A, B. Definice. Buďte A, B množiny. Zobrazení f z třídy A do třídy B je relace / c A x B, která splňuje podmínku: Pro každý prvek a e A existuje právě jeden prvek b G B takový, že platí [a, b] G /. Intuitivně jde o přiřazení hodnoty: každému prvku z třídy A se přiřadí právě jedna "hodnota" z třídy B. Prvek b se pak obvykle označuje /(a), někdy také fa. Nazývá se hodnota zobrazení / v prvku a nebo také obraz prvku a při zobrazení /. Zápisem / : A —> B vyjadřujeme, že / je zobrazení z třídy A do třídy B. Jiný zápis: A —> B. Místo b = f (a) často píšeme / : a b nebo a i—> b. Zavedeme-li zvláštní kvantifikátor 3! s významem "existuje právě jeden," lze podmínku na zobrazení zapsat jako (Vae Ä)(3\beB) [a,b] e f. "Existuje právě jeden" znamená "existuje, a pokud jsou dva, pak jsou stejné," čili (3! x e X) (x) ((3a; E X) (x)) A ((Vx e X)(W e X) ((x) A (x')) => x = x'). Příklad. Identická relace na třídě A je zobrazení a nazývá se identické zobrazení, z třídy A do ní samé a značí se id^ : A —* A. Platí id^ (a) = a pro každé a £ A. Je-li aci podtřída, pak je la = {(a, a) \ a G A} zobrazení, které prvku a £ A přiřadí týž prvek ffl G X: lax(o) = a. Zobrazení lax se nazývá vloženípodtřídy. Cvičení. Buďte f : A —> B, g : B —> C dvě zobrazení. Pak je relace g o f zobrazení A —>Ca (Va G A) (gof)(a)=g(f(a)). 15 logika a teorie množin Zobrazení g o f se nazývá kompozice zobrazení /, g. Cvičení. (1) Budiž f : A —> B zobrazení. Pak / o idA = idB o f = /. (2) Buďte / : A —> B, g : B —> C, h : C —> D zobrazení. Pak h o (ff o /) = (h o g) o /. Jak vyplýva z (2), zápis h o g o f je jednoznačný i při vynechaných závorkách. Je-li relace f C. A x B zobrazením / : A —> B, neznamená to ještě, že i opačná relace /_1 je zobrazením. Je-li prvek b G B obrazem prvku a e A, pak se prvek a nazývá vzor prvku b při zobrazení f. Třída všech vzorů prvku b G B při zobrazení / se značí To jest, f(a)=b&aef-1{b}. Zatímco obraz obecného prvku a e A vždy existuje a je jediný, vzor prvku b e B obecně existovat nemusí a nemusí být ani jediný. Pro obecnou podmnožinu B' Q B definujeme f^B' = {aeA\f(a)eB'}. Speciálním případem je f-1{b} z předchozího odstavce. 3.22. Poznámka. Zdůrazněme, že vzor f-1 {b} prvku b je třída a může být i vlastní. Uvedme příklad. Přiřadíme-li každé množině množinu prázdnou, dostáváme konstantní zobrazení U —> {0} a vzorem prvku 0 je celá třída U. Následkem toho vzory nemusí tvořit třídu. To je nepříjemné omezení, protože že nějaká kolekce takových vzorů intuitivně existuje a občas s ní i potřebujeme pracovat. Má to i poněkud paradoxální charakter, protože v těch případech, kdy všechny vzory při zobrazení / třídu tvoří, existuje i bijekce mezí ní a obrazem f A. který třídou je. To je slabina naší axiomatizace. Cvičení. Dokažte, že pro / C A x B a B', B" C B platí f-1(B'nB") = r1B'nr1B", /-1(B'UB") = /~1B'U/-1B". 3.23. Definice. Zobrazení f : A —> B se nazývá surjektivní (surjekce) neboli zobrazení na třídu B, jestliže má každý prvek b G B alespoň jeden vzor v A: (V6 G B)(3a e A)b = f (a). Zobrazení f : A —> B se nazývá injektivní (injekce) neboli prosté, jestliže má každý prvek b e B nejvýše jeden vzor v A: (Va G A)(W G A) (f (a) = f {a') =>a = a!). Zobrazení / : A —> B se nazývá bijektivní (bijekce), je-li surjektivní a injektivní současně. Cvičení. Buď f : A —> B zobrazení. Dokažte, že následující podmínky jsou ekvivalentní: (1) Zobrazení / je bijektivní. (2) Existuje zobrazení g : B —> A takové, že gof = idA, fog = idB. (3) Relace f^1 C B x A opačná k relaci / C A x B je zobrazení. Zobrazení g s vlastnostmi (2) je opět bijektivní a splývá s relací f^1 z (3). 16 logika a teorie množin Zobrazení g = f 1 z předchozího tvrzení se nazývá inverzní k f. Je definováno předpisem: f-1(b) = a^b = f(a). Cvičení. Buďte f : A —> B, g : B —> C bijekce. Dokažte, že (g o f)^1 = f^1 o g^1. Cvičení. Buďte f : A —> B, g : B —> C dvě zobrazení. (1) Je-li zobrazení g o f injektivní, pak je i zobrazení / injektivní. (2) Je-li zobrazení g o f surjektivní, pak je i zobrazení g surjektivní. (3) Je-li zobrazení g o f bijektivní, pak je i zobrazení g bijektivní. Dokažte. Cvičení. Buďte f : A —> B, g : A —> B dvě zobrazení. Dokažte, že platí: (1) Buď h : B —> C injektivní zobrazení takové, že ho f = hog. Pak / = g. Jinými slovy, injektivním zobrazením lze krátit zleva. (2) Buď h : D —> A surjektivní zobrazení takové, že / o h = g o h. Pak / = g. Jinými slovy, surjektivním zobrazením lze krátit zprava. Příklad. Buď A C X potřída, la = {(a, a) \ a 6 A} přílušné vložení. Je-li / : X —> Y nějaké zobrazení, pak kompozice / o lax představuje zobrazení A —> Y, které se nazývá zúžení (též restrikce nebo restrinkce) zobrazení / na podmnožinu A a značí se }\a'- Í\a : A X Y. Všimněte si, že zúžení je dáno týmž předpisem a \—> f (a) jako /. Je-li množina Y obsažena v jiné množině Z, pak existuje i kompozice ty z ° / : X —> Z. V tomto případě říkáme, že / vzniká rozšířením oboru hodnot, ale zvláštní dohodnuté označení neexistuje. Cvičení. Ukažte, že lax je injektivní. Buď / : X —> Y zobrazení, buď A C X podtřída. Položme fA={yeY | (3a e A)y = f(a)}, což často zkracujeme f A = {/(a) | a e A}. Nazývá se obraz podtřídy A C X při zobrazení /. Cvičení. Buď f : X —> Y zobrazení. Ukažte, že / : X —> fX, x \—> f(x), je surjektivní zobrazení a platí / = lfx,y o / . Je-li A množina, očekávali bychom, že i f A je množina, ale ve skutečnosti je k tomu potřeba zvláštní axiom. G. Axiom substituce. Je-li / : X —> Y zobrazení a X množina, pak fX je množina. V Zermelo-Fraenkelově axiomatizaci je na tomto místě schéma axiomů, v němž hrají roli substituce, odtud název. Příklad. Označme IÁ\ třídu všech jednoprvkových množin, které definujeme jako množiny tvaru {a}, kde a je množina. Ukažme, že IÁ\ je vlastní třída. Uvažujme o zobrazení s : IÁ —> U\, a i—> {a}. Zobrazení s je zřejmě surjektivní i injektivní (proč?), čili bijekce. Existuje proto inverzní zobrazení t : IÁ\ —> U, {a} i—> a, které je rovněž bijekce. Kdyby IÁ\ byla množina, pak by nutně i IÁ = tlÁ\ byla množina, což, jak víme, není. 17 logika a teorie množin 3.24. Definice. Nechť/je množina a F : I —> U zobrazení, které každému prvku i E I přiřadí množinu Fi E U. Zobrazení F : I —> U se obecně nazývá systém množin. Definujeme \jFl = {J{Fl\leI} = {jFI, iei f]Fl = f]{Fl\ieI} = f]FL iei Axiom substituce spolu s axiomem sjednocení dává následující tvrzení. 3.25. Tvrzení. NechťI je množina a F : I —> U zobrazení. Pak iei je množina. Důkaz. Třída (J FI je množina podle axiomu sjednocení, protože FI je množina množin podle axiomu substituce. Nyní můžeme dokázat, že kartézský součin dvou množin je množina. 3.26. Tvrzení. Buďte A, B množiny. Pak A x B je množina. Důkaz. AxB = Ax \J{b} = \J Ax {b}, beB beB kde A x {b} jsou množiny podle axiomu substituce, protože A x {b} je obrazem množiny A při zobrazení s—> [a, b]. 3.27. Definice. Budte f : X —> Y a, g : Y —> X zobrazení. Jestliže g o f = idx, pak říkáme, že zobrazení g je levá inverze zobrazení /. Jestliže f og = idy, pak říkáme, že zobrazení g je pravá inverze zobrazení /. 3.28. Tvrzení. Buď f : A —> B injektivní zobrazení množin, přičemž A^%. Pak má f levou inverzi. Důkaz. Protože A je neprázdná, existuje c E A. Konstruujme g : B —> A. Jestliže b E f A, pak má právě jeden vzor, čili existuje a takové, že = {a}. Položíme g (b) = a, načež 9(f(a)) = 9 (b) = a- Jestliže naopak b ^ f A, pak položíme g (b) = c. Snadno se vidí, že g o f = idA. Jiný způsob: Označíme-li g = {(b, a)EfAxA\b = f(a)}, (g je ohraničení relace /_1 na obraz f A), je g zobrazením f A —> A a, platí g o f = id^. Nyní dodefinujeme g na prvcích neležících v f A tak, že jim přiřadíme hodnotu c, čímž neporušíme rovnost g o f = id^. 18 logika a teorie množin Cvičení. Je předpoklad A 7^ 0 nutný? Duální tvrzení, že každé surjektivní zobrazení má pravou inverzi, ze zatím uvedených axiomů nevyplývá. Připomeňme si obvyklý důkaz v rámci naivní teorie množin. Buď / : X —> Y surjektivní zobrazení. Pak má každý prvek y e Y alespoň jeden vzor x G X takový, že f (x) = y. Pro každé y e Y vyberme právě jeden ze vzorů a označme jej g (y). Dostáváme zobrazení g : Y —> X. Z konstrukce vyplývá, že platí / o g = idy. Uvědomme si však, že zatím umíme konstruovat třídy jedině specifikací, tedy nějakou formulí definující onu třídu, čili jednoznačným předpisem. Podtřídu jCľxI jsme však nekon-struovali jednoznačným předpisem, nýbrž jsme pro každé y G Y libovolně vybrali jeden prvek z neprázdné množiny f~1{y}. AC. Axiom výběru. Je-li X množina neprázdných množin, existuje zobrazení t : X —> [J X takové, že (Vx G X) t (x) G x. Zobrazení t se nazývá výběrové zobrazení, protože vybírá po jednom prvku z každé množiny x G X. 3.29. Tvrzení. Buď f : A —> B surjektivní zobrazení množin. Pak má pravou inverzi. Důkaz. Buď / : A —> B injektivní zobrazení. Pak je | y G Y} systém neprázdných množin a podle axiomu výběru existuje výběrové zobrazení t splňující T~(f~1{y}) G f-1 {y}-Nyní stačí položit g(y) = T(/"1{y}), aby platilo g(y) G f'1 {y}, a tedy fog = idy. Axiom výběru byl po staletí používán nevědomky, dokud jej v roce 1904 "neobjevil" Ernst Zermelo (1871-1953). Axiomu výběru umožňuje nekonstruktivní důkazy existence, tedy důkazy, které neposkytují žádný předpis k sestrojení objektu, jehož existence je dokazována. Typickým případem je Brouwerova věta o pevném bodu (každé spojité zobrazení uzavřené koule do sebe sama má pevný bod). S vědomým použitím axiomu výběru byla zpočátku spojena jistá nedůvěra, protože se záhy objevily důkazy některých poněkud paradoxních výsledků, například Banach-Tarského věty, podle níž lze jednotkovou kouli v trojrozměrném Euklidovském prostoru rozložit na konečný počet částí (pět) a z nich použitím shodných transformací sestavit dvě jednotkové koule (části jsou neměřitelné, a proto nejde o skutečný paradox). Dnes již axiom výběru téměř nikdo nezpochybňuje. Nicméně, libovůle spojená s volbou výběrového zobrazení způsobuje, že "konstrukce" využívající axiom výběru jsou nejednoznačné a neopakovatelné. Přesvědčivé příklady uvedeme v následujícím oddílu (§ 3.14). Proto je zajímavé sledovat, která tvrzení jsou s axiomem výběru ekvivalentní. Příkladem je tvrzení o existenci pravé inverze u surjekcí. 3.30. Tvrzení. Z posledního tvrzení (existence pravé inverze ke každé surjekci mezi množinami) plyne axiom výběru. Důkaz. Buď X množina neprázdných množin. Pak je X x (J X množina a podtřída všech dvojic [x, a] takových, že a G x G X, je též množina. Uvažujme o zobrazeních pi : E —> X, [x, a] p2 : E —>• X, [x, a] a. 19 logika a teorie množin Zobrazení p\ je surjektivní, protože každá množina x G X je podle předpokladu neprázdná. Buď q pravá inverze k p\, čili p\ o q = \áx- Máme q{x) = [pi(q(x)), P2(q(x))] G E, načež P2{q{xj) G Pi(q(x)) = x pro každé x. Vidíme, že P2 o q je výběrová funkce. Výběrová funkce pro konečný počet objektů existuje i bez axiomu výběru. Snadno ji popíšeme formulí. Například pro jednu neprázdnou množinu x obsahující prvek c je výběrovou funkcí {[x, c]}. Cvičení. Bertrand Rüssel popularizoval axiom výběru výrokem, že je nutný k výběru množiny z nekonečného počtu ponožek, ale není nutný k výběru množiny z nekonečného počtu bot. Vysvětlete. Nápověda: Ponožky jednoho páru považujeme za nerozlišitelné. Příklad tvrzení ekvivalentního s axiomem výběru poskytuje také kartézský součin systému množin. Buď F : I —> U, i i—> Fi, systém množin, kde I je množina. Označme 3.31. Tvrzení. Kartézský součin neprázdné množiny množin je neprázdný. Důkaz. Prvek kartézského součinu je totéž co výběrová funkce. V teorii tříd lze formulovat axiomy silnější než axiom výběru pro množiny. Uvedeme dva, ale nebudeme je používat. Axiom globálního výběru. Je-li T = li \ {0} třída všech neprázdných množin, existuje zobrazení r : T —> U takové, že (\fx G T) t (x) G x. Axiom globálního výběru praví, že výběrová funkce existuje i pro vlastní třídy neprázdných množin. Neříká nic nového o množinách, pouze o vlastních třídách. Axiom globálního výběru implikuje, že i kartézský součin vlastní třídy neprázdných množin je neprázdný. Axiom omezené velikosti. Je-li C vlastní třída, pak existuje bijekce C —> U. Axiom omezené velikosti praví, že všechny vlastní třídy jsou "stejné" v tom smyslu, že libovolné tvrzení o jedné z nich lze přenést na každou jinou. Přestože je jeho formulace velmi odvážná, není v rozporu s ostatními axiomy. 3.14. Relace ekvivalence 3.32. Definice. Buď p C A x A relace na třídě A. Relace p se nazývá - reflexivní, jestliže pro každé a e A platí apa; - symetrická, jestliže platí implikace a p b =>• b p a; - tranzitivní, jestliže platí implikace (a p b A b p c) a p c. Príklady. 1. Identická relace id^ je reflexivní, symetrická i tranzitivní. 2. Relace "G" na univerzální třídě U není ani reflexivní, ani symetrická, ani tranzitivní. 3. Relace "c" na univerzální třídě U je reflexivní a tranzitivní, ale není symetrická. Cvičení. Graf relace na množině můžeme kreslit tak, že prvky množiny A zobrazíme body v rovině a mezi prvky vedeme šipku, jsou-li v relaci. Jak se pozná graf reflexivní resp. symetrické resp. tranzitivní relace? 20 logika a teorie množin Cvičení. Najděte chybu v následujícím „důkazu" nepravdivého tvrzení, že každá symetrická a tranzitivní relace p je reflexivní: "Je-li a p b, pak ze symetrie plyne b p a, načež z tranzitivity plyne a p a." 3.33. Definice. Reflexivní, symetrická a tranzitivní relace na třídě se nazývá relace ekvivalence (nebo prostě ekvivalence, pokud nemůže dojít k záměně s logickou ekvivalencí). Příklady. 1. Identická relace id a je ekvivalence na třídě A. 2. Na univerzální třídě IÁ zavedeme relaci ekvivalence ~ předpisem: A ~ B právě tehdy, když existuje bijekce A —> B. 3.34. Definice. Buď p ekvivalence na třídě A. Pro libovolné a E A označme Mp = {x E A \ a p x}. Třída [a] p se nazývá třída rozkladu podle ekvivalence p. 3.35. Tvrzení. Buď p ekvivalence na třídě A. Pro libovolné a E A platí a E [a] p, a p b [a]p = [b]p, Wp n [b]p ^ 0 => [a]p = [b]p. Navíc, pokud jsou [a]p množiny, platí U Wp = A. a£A 3.36. Poznámka. Pokud je alespoň jedna třída [a]p vlastní, není sjednocení UcjgaMp ^en" nováno, protože nemáme k dispozici zobrazení a—> [a]p. Každé ekvivalenci na množině přísluší rozklad. Ekvivalenci na vlastní třídě přísluší rozklad jen tehdy, když je každá třída rozkladu množinou. 3.37. Definice. Nechť je každá třída [a]p rozkladu třídy A podle ekvivalence p množinou. Třída A/p={BEU\ (3a EA)B= [a]p\ = {[a]„ \ a E A} se nazývá faktorová třída podle ekvivalence p. Faktorová třída A/p množiny A je opět množina, protože je obrazem množiny A při zobrazení A —> U, a i—> [a]p. Cvičení. Nalezněte všechny rozklady na množině A = {1, 2, 3} (je jich pět). Cvičení. Buď p ekvivalence na třídě A, buď a ekvivalence na třídě B. Zaveďme relaci 7 = p x a na třídě C = A x B předpisem (a1,b1) 7 (a2, b2) ffli p a2 Ah a b2. Ukažte, že 7 je relace ekvivalence. Ukažte, že třídy ekvivalence 7 jsou právě třídy U x V, kde U je třída ekvivalence p a V je třída ekvivalence a. Podle axiomu výběru lze vytvořit množinu tím, že z každé třídy rozkladu některé množiny vybereme po jednom prvku. 21 logika a teorie množin Příklad. V tomto příkladu použijeme množiny K, Q, Z reálných, racionálních a celých čísel (vše, co o nic potřebujete vědět, jste se dozvěděli v matematické analýze). Na množině K zavedeme relaci ~q předpisem Snadno se uláže, že ~q je relace ekvivalence. Podle axiomu výběru existuje množina U, která má s Příklad. Vitaliho množina je podmnožina V uzavřeného intervalu [0,1] taková, že pro každé r G K existuje právě jedno číslo v EV takové, že r — v G Q, kde Q C K je množina racionálních čísel. Získáme ji výběrem prvků z tříd ekvivalence r = s <4> r — s G Q. O množinách Q a K viz níže. 3.15. Von Neumannova konstrukce přirozených čísel Zatím uvedené axiomy nemají dost síly, aby prokázaly existenci nekonečné množiny, jakou je třeba množina všech přirozených čísel. Navíc, pokud je naším cílem vybudování matematiky "z ničeho," měli bychom přirozená čísla zkonstruovat jen s použitím těch nástrojů, které nám zatím teorie tříd poskytuje. Von Neumann navrhl definovat přirozené číslo jako množinu všech předcházejících přirozených čísel. Je-li 0 první (nejmenší) přirozené číslo, dostáváme postupně 0 = 0, 1 = {0} = {0} 2 = {O,1} = {0,{0}} 3 = {O,1,2} = {0,{0},{0,{0}}} 4 = {0,1, 2, 3} = {0, {0}, {0, {0}}, {0, {0}, {0, {0}}}} atd. Vidíme, že platí 1 = 0 U {0}, 2 = 1 U {1}, 3 = 2 U {2}, atd. 3.38. Definice. Řekneme, že množina N je induktivní, jestliže platí (i) leiV; (ii) jestliže n g N, pak n u {n} g N. Dále, 2 = {N g U | (0 g N) A (Vn) (n g N => n U {n} g N)} se nazývá třída všech induktivních množin. H. Axiom nekonečna. 1^0 (třída všech induktivních množin je neprázdná) aneb (3N g U) ((0 g N) A (Vn) (n g N => n U {n} g N)) (existuje induktivní množina). Množinu přirozených čísel označujeme N a definujeme jako průnik všech induktivních množin. Tudíž, Nei 22 logika a teorie množin což je množina, protože N je podtřída alespoň jedné induktivní množiny N, která existuje podle axiomu nekonečna. Několik prvních přirozených čísel jsme vypsali výše, další lze snadno doplnit. Je-li n přirozené číslo, pak se n U {n} nazývá následovník čísla n a označuje se an nebo n + 1. 3.16. Princip matematické indukce Princip matematické indukce umožňuje dokazovat tvrzení závislá na přirozenám čísle, neboli tvrzení tvaru (Vn G N)4>(n). 3.39. Tvrzení. Buď K C N množina taková, že platí 0 G K a implikace n G K =>• n + 1 E K. Pak platí K = N. Důkaz. Podle předpokladu je K induktivní, a proto obsahuje průnik všech induktivních množin, čili N C K. Opačnou implikaci jsme předpokládali, a proto K = N. 3.40. Důsledek. Buď 4>(n) formule taková, že platí (p(0) a implikace 4>(n) =>■ (p(n + 1). Pak platí 4>(n) pro všechna n G N. Důkaz. Položíme K = {n G N | 4>(n)}. Princip matematické indukce také umožňuje konstruovat množiny nebo dokonce třídy Xn závislé na přirozeném čísle n. K tomu stačí dokazovat formule tvaru (VnGN)(3X„)0(n,X„). V tom případě hovoříme o rekurzívní definici tříd Xn. Následující axiom vypadá na první pohled záhadně, ale je užitečný tím, že zjednodušuje řadu důkazů. I. Axiom regularity. (VX G U) (X ž 0 => (3x G X) x n X = 0), čili každá neprázdná množina obsahuje prvek, který je s ní disjunktní. Axiom regularity vylučuje existenci obtížně představitelných a snadno postradatelných vztahů mezi množinami, jako například a G a nebo a G Ď G a a podobných. 3.41. Tvrzení. Neexistuje množina a taková, že a G a. Důkaz. Množina {a} je neprázdná, a proto existuje podle axiomu regularity takový prvek b G {a}, že Ď n {a} = 0. Jelikož jediným prvkem množiny {a} je a, máme b = a, a tedy a n {a} = 0. Připusťme, že platí a G a. Pak a n {a} = {a} =/= 0, což je spor. Tudíž, a ^ a. Lze definovat množinu obsahující samu sebe, aniž by byla definována kruhem? Je {{{■■■}}} (tečky označují nekonečné opakování vložených závorek) korektně definovaná množina? Axiom regularity je tu od toho, aby nás podobných bezedných otázek zbavil. 23 logika a teorie množin 3.42. Tvrzení. Neexistují množiny a, b takové, že a G b a b G a. Tudíž, ze dvou množin jen jedna může být prvkem druhé. Důkaz. Množina {a, b} je neprázdná, a proto existuje podle axiomu regularity takový prvek c G {a, b}, že c D {a, b} = 0. Jsou dvě možnosti. Je-li c = a, pak a D {a, b} = 0, a proto b ^ a. Je-li c = b, pak b D {a, b} = 0, a proto a ^ b. 3.43. Tvrzení. Neexistuje systém množin {/„ | n G N} takový, že (Vn G N) fn+i G /„. Tudíž, neexistuje nekonečná posloupnost množin /o 3 /i 3 /2 3 ■ ■ ■ 3 /» 3 fn+i 3 ■ ■ ■■ Důkaz. Označme S = {/„ | n G N}, což je množina a je neprázdná, a proto existuje podle axiomu regularity takový prvek s G S, že s D S = 0. Podle konstrukce musí existovat n G N takové, že s = fn. Pak ale /„+i G /„ a současně /„+i G S, což znamená, že s D S =/= 0, spor. 3.44. Poznámka. Je možné postulovat existenci množin, narušujících axiom regularity, aniž by to bylo bylo ve sporu s ostatními axiomy. Množiny splňující a G a jsou pak přípustné. Axiom reularity je posledním axiomem teorie tříd a potažmo teorie množin, který zavádíme. Kapitolu završíme ukázkami, jak vybudovat základy matematické analýzy, protože bez toho by naše počínání nemělo rozumný důvod. 3.17. Aritmetika přirozených čísel V této části budeme definovat sčítání a násobení přirozených čísel. Následovníka čísla n prozatím budeme označovat an, od označení n + 1 dočasně upustíme. 3.45. Tvrzení. Neexistuje m G N takové, že am = 0. Důkaz. Muselo by platit to U {to} = 0, ale levá strana obsahuje m jako prvek a pravá nikoliv. 3.46. Tvrzení. Nechť m, n G N splňují cm = am. Pak n = m. Jinak řečeno, zobrazení a : N —> N je injektivní. Důkaz. Podle předpokladu n U {n} = m U {m}. Levá strana obsahuje n jako prvek, a proto i pravá, načež n G m nebo n G {m}. Pravá strana obsahuje m jako prvek, a proto i levá, načež m G n nebo m G {n}. Nemůže platit n G m a m G n současně, a proto platí n G {m} nebo m G {n}. Ve prvním i druhém případě zřejmě n = m a jsme hotovi. Nyní máme dokázány všechny tzv. Peanovy axiomy, ze kterých lze odvodit všechny aritmetické vlastnosti přirozených čísel. Každé zobrazení N x N —> N se nazývá binární operace na množině N. Ukažme nyní, jak lze zavést binární operace známé z aritmetiky. 3.47. Tvrzení. Existuje právě jedno zobrazení N x N N, splňující n + 0 = n, n + am = a(n + m), právě jedno zobrazení N x N N, splňující n ■ 0 = 0, n ■ am = n + (n • m) 24 logika a teorie množin a právě jedno zobrazení N x N-> N, splňující nA0 = 1, nham = n ■ (nAm). Důkaz. Pro každé n G N definujme zobrazení an : N —> N rekurzivní formulí an(0) = n, an(arn) = cran(m), zobrazení f3n : N —> N rekurzivní formulí Pn(0)=0, f3n(<7m) = an(f3n(m)) a zobrazení 7„ : N —> N rekurzivní formulí 7„(0) = 1, 7„(crm) = /3„(7„(m)). Podle tvrzení 3.39 jsou zobrazení an, f3n i 7„ definována na celé množině N. Podle tvrzení 3.39, 3.46 a 3.45 jsou definována jednoznačně. Položíme n + m = an(m), n ■ m = f3n(m), nhm = 7„(m). Nyní dokážeme, že an = n + 1. Máme postupně n + 1 = an(\) = an(uO) = ítqí„(0) = cm. Cvičení. Ověřte každý krok právě uvedeného důkazu. Právě definované binární operace +, • , A mají všechny vlastnosti operací sčítání, násobení a umocňování přirozených čísel, zejména platí následující formule aritmetiky přirozených čísel: a + 0 = a, a + b = b + a, a + (b + c) = (a + b) + c, a • (b + c) = (a • b) + (a • c), (a • ď)ac = (aAc) • (ďac), (aA6)Ac = aA(6 • c), aA0 = 1, a • 1 = a, a ■ b = b ■ a, a ■ (b ■ c) = (a • b) ■ c, aA(Ď + c) = (aA6) • (aAc), aAl=a, lAa = l. Cvičení. Dokažte indukcí formule aritmetiky přirozených čísel. 3.48. Poznámka. Všimněte si, že při naší definici platí 0° = 1 (přecházíme k obvyklému zápisu umocňování), zatímco neplatí 0a = 0 pro a to mnohé formule. Například zápis 0. Zjednodušuje + a\X + aQ = ~y ' an je možný jen tehdy, když 0° = 1 a jinak se musí pro x = 0 sjednat výjimka. Rovnost 0° = 1 bude v platnosti i v oboru kardinálních čísel a v oboru ordinálních čísel, které zavedeme později. Poznámka 3.49 níže je k neurčitým výrazům typu 0°. 25 logika a teorie množin 3.18. Celá, racionální a reálná čísla Nyní zavedeme celá, racionální a reálná čísla. Z konstrukce bude jasné, že tvoří množinu. Aritmetické operace se zavádějí známým způsobem a nebudeme s tím zdržovat výklad. Dobře známa je konstrukce celých čísel jako dvojic [+,n], kde n G N, nebo [— , n], kde n G N \ {0} (znaménka + a — jsou symboly různé od symbolů označujících přirozená čísla). Definujeme-li třídu Z celých čísel jako sjednocení ({+} x N) U ({—} x (N \ {0})). Je zřejmé, že Z je množina. Alternativně můžeme zavést Z = ({+, —} x N)/p, kde p je relace ekvivalence, jejíž jedinou třídou obsahující více než jeden prvek je {[+, 0], [—, 0]} (ztotožňujeme +0 a —0). Konstrukce racionálních čísel jako dvojic p/q nesoudělných čísel, kde pGZagGN \ {0}, je též dobře známa. Třídu Q racionálních čísel můžeme konstruovat jako faktorovou množinu součinu Z x (N\ {0}) podle ekvivalence [pi, qi] p [p2, 92] ^ Pi2 {0,1} = 2, a proto je prvkem množiny 2N všech zobrazení N —> 2. Jelikož však atd., je nutno vyloučit posloupnosti, které od některého místa počínaje sestávají ze samých jedniček; budeme jim říkat nadbytečné posloupnosti. Každou posloupnost 0, a\ ... a„0111. .. přitom lze nahradit posloupností, 0, ai ... a„1000 ..., která od stejného místa počínaje sestává ze samých nul a jedna nula bezprostředně předcházející samým jedničkám se změní na jednu jedničku bezprostředně předcházející samým nulám. Tudíž, polouzavřený interval I lze ztotožnit s podmnožinou množiny 2N, z níž jsou vynechány nadbytečné posloupnosti ve shora uvedeném smyslu. Množina reálných čísel je pak identifikovatelná se součinem Z x I. 3.49. Poznámka. V matematické analýze se 0° považuje za neurčitý výraz. Jde ovšem jen o to, že limita typu 0° může nabývat libovolných hodnot, to jest, že při lim^^c f(x) = 0 a lim-j^c g(x) = 0 závisí limita na volbě funkcí f(x) a g(x). Nijak to není ve sporu se stanovením hodnoty 0° učiněným výše. Znamená to však, že funkce 0X je nespojitá v nule (zato x° je spojitá a obě být spojité zřejmě nemohou). Řečené však nebrání jiným autorům považovat 0° za nedefinovaný výraz vždy. Je to v pořádku, pokud se nezapomene na všechna nutná opatření, na něž jsme jedním příkladem upozornili v poznámce 3.48. 0,111... = 1,000..., 0,0111... = 0,1000... lim f{x)9{x) 26