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žín, což v textu označujeme odkazem [TM, ni-rig], kde ni,ri2 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 f). 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 mohutnostmiiožiny. Množiny mají stejnou mohutnost, existuje-li mezi nimi bijekce.
Jakmile Cantor mezi množiny zahrnul i souhrn 93Í všech možných mohutností, vyvstal paradox. Ukázalo se, že samotná množina 93Í by nutně měla ještě větší mohutnost, neobsazenou v 93Í. 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 | <j>(X)}
logika a teorie množin
všech X, pro něž platí nějaká podmínka 4>{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 g X}.
Russelův paradox spočívá v tom, že obě možnosti N £ N i N ^ N vedou ke sporu. Vskutku, jestliže N £ N, pak musí platit podmínka N ^ N. A naopak, jestliže N ^ N, pak nesmí platit podmínka N ^ 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é, de-vatená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 | <j>(X)}
všech množin X, majících nějakou vlastnost 4>{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 TV = {X \ X £ X} za korektní definici množiny. V rámci ZF TV není množina; otázka co TV 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 \ 4>(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 €. Cte 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 ~|, A, V, =>, <S>.
4. Kvantifikátory V, 3.
5. Závorky (, ).
Například, x,X,yi,U'2 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 € y dává smysl a bude formulí, zatímco Giga 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í definice 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 € 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 <f> formule, pak i ~\((j>) je formule. Vázané a volné proměnné jsou u ~\((j>) tytéž jako
u <f>.
Příklad. Příkladem formule vzniklé podle pravidla F2 je formule ~\(X G Y). Obvykle ji zkracujeme na X 0 Y. Obě proměnné X, Y jsou volné.
F3 Je-li <f> formule a x její volná proměnná, pak (\/x)((j>) resp. (3x)((j>) jsou formule. Proměnná a; je v obou formulích (\/x) (</>) a (3a;) (</>) vázaná, ostatní proměnné jsou volné nebo vázané podle toho, zda jsou volné nebo vázané ve formuli <f>.
Č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
(3x) (x e X).
Ve výchozí atomické formuli x G X byly obě proměnné volné, ve výsledné formuli je x vázaná a X volná. Smysl formule (3x) x G 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 € X)), ale množství závorek ke srozumitelnosti nepřispívá. Dostatečně srozumitelné jsou i zápisy (3x)(3X)(x € X) nebo dokonce 3x 3X x € 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 <f>, 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 <f>, ip slučitelné formule, pak
WaW,   WvW,   fa)=>M,   (<!>)& M
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í <f>, ip.
4
logika a teorie množin
Příklad. Formule <p = (3x) i£pi|) = i£z jsou neslučitelné, protože x je jednou vázaná a jednou volná. Zbývající proměnné y, z se vyskytují každá jen v jedné z formulí, a proto nemají na slučitelnost vliv. Potom
4> Aip = ((3x) i£i/)a(iEz) není' formule.
3.3. Tvrzení. Vyskytuje-li se proměnná X ve formuli <f>, pak je v ni buď volná anebo vázaná, ale nikoliv obojí.
Důkaz. Tvrzení platí pro atomické formule, neboť v těch se vyskytují pouze volné proměnné. Platí-li tvrzení pro formuli cp, platí i pro ~\(p, protože volné a vázané proměnné jsou u obou stejné. Platí-li tvrzení pro formuli (p s volnou proměnnou X, platí i pro (\/x)(<p) resp. (3x)(<p), 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 (pAip, 4>Vtp,
<f>=>ip, <f><=>ip.
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 <p = (3x) iEt/air = iEz. Pokud ve formuli <p zaměníme x například za u, takže <p = (3it) u G y, budou obě formule slučitelné a
4> Aip = ((3it) u e y) A (x e z)
bude formule.
Pro názornost se někdy za symbolem formule uvádějí v závorkách všechny její volné proměnné.
Příklad. Formuli (3x) x G y můžeme označit např. <p nebo, pro názornost, <j>(y), ale nikoliv <p(x,y) ani 4>(y,z).
3.2. Pravdivost formulí
Přejděme k otázce pravdivosti formulí ve smyslu klasické logiky se dvěma pravdivostními hodnotami 1 (formule je pravdivá, formule platí) a 0 (formule je nepravdivá, formule neplatí).
O pravdivosti formulí budeme rozhodovat na základě pravdivosti jejich podformulí pomocí pravidel Pi až P4, odpovídajících pravidlům Fi až F4 pro konstrukci formulí teorie tříd. P2 Formule ~\<f> je pravdivá právě tehdy, když <f> je nepravdivá.
P3 Formule (\/x) 4>{x) je pravdivá právě tehdy, když 4>{x) platí pro všechna x; formule (3a;) 4>{x) je pravdivá právě tehdy, když existuje x takové, že platí 4>{x).
P4 Pravdivost formulí (p A ip, 4>V ip, <f> => ip, <f> <^ ip v závislosti na pravdivosti formulí (p, ip je dána známou tabulkou:
4>	i>	(p Alp	4>\/ tp		
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 <f> <S> ip platí právě tehdy, když mají <f> a ip stejné pravdivostní hodnoty. Formule <f> a ip jsou pak co do pravdivosti a nepravdivosti zaměnitelné. Řekneme, že formule 4>, ip jsou logicky ekvivalentní
V tomto textu budeme logickou ekvivalenci formulí 0, ip vždy vypisovat slovy '0 O V1 platí'. Někdy se k zápisu logické ekvivalence používá symbol '='. Má vlastnost reflexivity (0 = 0 pro každou formuli 0), symetrie (jestliže 0 = ip, pak ip = 0) a tranzitivity (jestiže 0 = ip a ip = \, Pak 0 = x). Zdůrazněme však, že 0 = ip není formule teorie tříd (nesmíme směšovat jazyk, kterým mluvíme, s jazykem, o kterém mluvíme).
Formule bez volných proměnných má jednoznačně určenu pravdivostní hodnotu f nebo 0; před zjišťováním pravdivostní hodnoty formule s volnými proměnnými je nutno za volné proměnné zvolit nějaké konkrétní třídy.
Nyní již máme shromážděny základní rekvizity pro budování axiomatické teorie tříd. Dále budeme systematicky uvádět jeden axiom za druhým a mezitím zavádět další pomocné pojmy. Kdybychom vypsali všechny axiomy naráz, aniž bychom měli pomocné pojmy k dispozici, byly by velmi komplikované a zcela nesrozumitelné.
Pro jistotu uveďme, že axiomy jsou pokládány za pravdivé formule. Další pravdivé formule (platná tvrzení) z nich odvozujeme pomocí pravidel P2 až P4 a dalších standardních důkazových postupů, o nichž předpokládáme, že jsou dostatečně známy a proto je podrobně nevypisujeme. Již dříve jsme v jednom příkladu zavedli symbol g" tak, aby formule X g" Y měla stejný smysl jako ~\{X G Y). Ať za X,Y dosadíme cokoliv, vždy budou mít X g" Y a ~\{X € Y) stejnou pravdivostní hodnotu. Vidíme, že X £ Y a ~\{X € Y) jsou logicky ekvivalentní.
Zdůrazněme, že X £ Y není atomická formule, ačkoliv tak na první pohled vypadá. Je to jen stručný zápis pro neatomickou formuli 1(X € Y). Pravdivostní hodnota formule X £ Y je zcela jednoznačně odvoditelná z pravdivostní hodnoty atomické formule X €iY. Další podobné stručné zápisy zavedeme níže.
3.3. Množiny
V axiomatické teorii tříd můžeme a budeme množiny definovat.
3.4. Definice. Třída X je množina, jestliže existuje třída Y taková, že I £ ľ. Zapisujeme X g U . Třída, která není množinou, se nazývá vlastní třída.
Podtržením zdůrazňujeme, že g U je (prozatím) nedílný symbol. Brzy zavedeme třídu U všech množin, přičemž X £lA & X g U bude znamenat totéž a podtržení se stane zbytečným.
3.4. Rovnost tříd
Zavedeme ještě jedno označení. Řekneme, že dvě třídy jsou si rovny a zapisujeme X = Y, jestliže mají stejné prvky. Zde je formální definice:
3.5. Definice. Třídy X, Y jsou si rovny, jestliže platí
(VČ7) (í/Gl^í/Gľ). Zapisujeme X = Y.
6
logika a teorie množin
V předchozím textu už jsme symbol '=' několikrát použili ve smyslu obecné rovnosti či totožnosti formulí nebo tříd. Pro třídy jsme teď zavedli rovnost jako označení pro fakt, že mají stejné prvky, což není ve sporu s dřívějším použitím. Pro formule zůstaneme u neformální definice rovnosti jako totožnosti. Je zřejmé, že totožné formule jsou logicky ekvivalentní, ale ne naopak.
Všimněme si, že je-li U vlastní třída, pak rozhodně neplatí ani U G X ani U G Y, takže ekvivalence í/€X<S>í/€7je pravdivá pro všechny vlastní třídy U. Stačí tedy posuzovat ekvivalenci U G X <S> U G Y pouze v případě, že U je množina.
Fakticky je "=" relace mezi třídami, o níž lze snadno ukázat, že je reflexivní, symetrická a tranzitivní.
Cvičení.    Ukažte, že platí (VX) X = X,
(VX)(VY) {X = Y =*> Y = X), (VX)(VY)(VZ) {{X = Y A Y = Z) =*> X = Z). Nápověda: Dokažme první tvrzení. To je ekvivalentní pravdivosti formule
(vx)(vu) (u e x) o (u e x).
Jelikož (U G X) O (U G X) platí pro libovolnou pravdivostní hodnotu atomické formule U G X, je první tvrzení dokázáno.
Podle definice rovnosti tříd má X = Y za následek U G X <S> U G Y pro každé U. Odnikud však nevyplývá, že by X = Y mělo za následek ilgľoľíľ pro každé V. To je nutno postulovat, přičemž tak samozřejmě stačí učinit pro implikaci.
A. Axiom invariance. Platí
(VX)(Vr)(W) ((X = Y A X G V) => Y G V). Slovy: Jestliže X = Y, pak z X G V plyne Y G V.
3.6. Tvrzení. Nechť X = Y a V je libovolná třída. Pak
X G V & Y G V. Slovy: X G V a Y G V platí nebo neplatí současně.
Důkaz. Z axiomu invariance plynou implikace X€iV=>Y€iV&Y€iV=>X€iV.
3.7. Tvrzení.  NechťX = Y a U\, ...,[/„ jsou libovolné třídy. Pak platí
4>(X,U1,...,Un)^(t>(Y,U1,...,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 4>{X, U) atomická formule U G X, plyne tvrzení z definice rovnosti tříd. Je-li 4>{X, U) atomická formule X G 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 4>{X, U\,..., Un).
Nechť je formule 4>{X, U\,..., Un) tvaru ~\ip(X, U\,..., Un) podle pravidla Fg. Jelikož je ip(X, Uu...,Un) kratší než <f>(X, Uu..., Un), platí i/j(X, Uu ... ,Un) ip(Y, Uu...,Un) podle indukčního předpokladu. Pak ovšem platí 4>{X, U\,..., Un) <S> 4>(Y, U\,..., Un).
Nechť je c/)(X, Uu ..., Un) tvaru (VČ7) ip(X, U, Uu ..., Un) nebo (3U) ip(X, U, Uu ..., Un) podle pravidla F3. Opět je ip(X, U, U\,..., Un) kratší než 4>{X, U\,..., Un), a proto platí ip(X,U,Ui,... ,Un) il>(Y, U, Ui,..., Un) podle indukčního předpokladu. Načež ovšem <j>(X,U1,...,Un)^<j>(Y,U1,...,Un).
Analogicky ohledně pravidla F4.
B^. Schéma axiomů specifikace. Buď <f>(x, U\,..., Un) formule s volnými proměnnými x, U\,... ,Un, buď Z proměnná, která se ve <f> nevyskytuje. Pak je
(Vč7i) • • • (\/Un)(3Z)(\/x) [x e Z & (x eU A (/>(x, Uu ..., Un))}
axiom. Slovy: Existuje třída Z, závislá na Ui,..., Un, jejíž prvky jsou právě všechny množiny x takové, že platí 4>{x, U\,..., Un).
Třída Z se nazývá třída specifikovaná formulí 4>{x, U\,..., Un) a označuje se
{xeU I <f)(x,Uu...,Un)}.
Odtud okamžitě plyne pravidlo pro rozhodování o pravdivosti atomických formulí s pravou stranou Z = {x g U \ 4>{x, U\,..., Un)}:
Pi Nechť Z = {x g U  I 4>{x, U\,..., Un)} je třída specifikovaná formulí <f>(x, U\,..., Un). Potom pro každou množinu x platí
x e Z     (j>(x, Ui,..., Un).
Slovy: Je-li x množina, pak s € Z je pravdivá právě tehdy, když platí <f>(x, U\,..., Un).
Požadavek x g U je důležitý, protože zabraňuje vzniku Russelova paradoxu.
V úvodu jsme se zmínili o dvou variantách teorie tříd, Gôdel-Bernays-von Neumannově a Kelley-Morseově. První z nich ve schématu axiomů specifikace připouští jen formule, jejichž proměnnými jsou množiny, zatímco druhá připouští obecné třídy. Gôdel-Bernays-von Neumannových axiomů je potom méně než Kelley-Morseových axiomů       a naopak, Kelley-Morseových tříd je více něž Gôdel-Bernays-von Neumannových.
3.5. Univerzální třída
Doposud byl g U nedělitelný symbol. Nyní zavedeme třídu U předpisem U = {x g U I x = x}.
Zdůrazněme, že nejde o definici kruhem, protože symboly U na levé straně a g U na pravé straně jsou různé. Protože formule x = x je vždy pravdivá, je U třída všech množin. Nazývá se též univerzální třída čili univerzum. Později ukážeme, že univerzum U je vlastní třída.
Zápis x £lA znamená právě tolik, že x je množina, čili právě tolik, co x g U . Nadále budeme používat jen první z nich.
8
logika a teorie množin
3.6. Prázdná třída
Prázdnou třídu 0 zavedeme předpisem 0 = {x e U I x ^ x}.
Jelikož x ^ x neplatí pro žádnou množinu, neexistuje množina, která by ležela v prázdné třídě, což vysvětluje její název.
3.7. Algebra tříd
Axiom specifikace umožňuje zavést operace s třídami, které jsou přímým zobecněním dobře známých množinových operací:
unv = {xeu\xeu Axev}, uuv = {xeu\xeu\/xev}, u\v = {x eu \x eu Al(x e v)}.
Máme i unární operaci doplňku třídy
u = {x eu \ i(x e u)},
kde množinová analogie není, protože doplňkem množiny je vždy vlastní třída.
Cvičení.    Ukažte, že platí
UCihí=U, ř7U0 = ř7,
Í7n0 = 0, uuu = u,
unu = u, uuu = u,
unv = v nu, u u v = vuu,
(u n v) n w = u n {v n w), {u u v) u w = u u {v u w),
{u n v) u w = (u u w) n (y u w), {u u v) n w = (u n w) u {v n w).
Cvičení.    Ukažte, že platí
W = 0, 0=W,
(í7ny)~ = uuv,   (uuv)~ = unv, u = u.
Přímé zobecnění má i inkluze.
3.8. Definice. Řekneme, že třída U je podtřída třídy V a zapisujeme U C V, jestliže platí formule
(yx) (x e u => x e v).
Vztah A C B se nazývá inkluze. Ostrá inkluze A C -B se zavádí formulí AcB«(4CB)a(4/4 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 C U (reflexivita), (UCVAVCU)^-U = V (antisymetrie), (UCVAVCW)^-UCW (tranzitivita).
Cvičení.    Ukažte, že platí
0 C U, U C U,
U C V o ŕ7 U U = v,    u c V o ŕ7 n U = u.
Je-li U třída, zavádíme omezené kvantifikátory (3X G U) a (VX G Č7) předpisem, že
(3X e u)<f)(x,vu...,vn) & (3x)x e u/\<f>(x,vu...,vn), (vx e [/) (t>(x, Ui,..., vn) & (vx)x e [/ ^ </>(x, Vi,..., vn).
platí pro libovolnou formuli 4>{X, V\,..., U„).
Sjednocení a průnik třídy množin definujeme předpisem
(J u = {x e u | (3X e č/) x e x}
= {xeu\ (3X) (x eu Axe x)}, f] f/ = {x e u | (vx e č/) z e x}
= {x e u (vx) (x e [/ => z e x)}.
Vidíme, že |"| [7 obsahuje právě ta z, která leží ve všech množinách X G [7. Oproti tomu |J U obsahuje právě ta z, která leží v alespoň jedné množině X € U. Možný a obvyklý je též zápis
\Ju=\Jx, f]u=f]x.
X<EU X<EU
3.9. Tvrzení. Platí
f|0 = W,     (J0 = 0.
Důkaz. Ohledně první rovnosti zřejmě |"| 0 C U. Dokažme opačnou inkluzi U C |"|0. Buď x £ U libovolná množina. Ale z € |"| 0 právě tehdy, když pro každou třídu X platí implikace IěÍ=>iěI. Taková implikace ovšem platí, a to z toho důvodu, že předpoklad X € 0 není nikdy pravdivý.
Ohledně druhé rovnosti zřejmě 0 C |J 0. Dokažme opačnou inkluzi |J 0 C 0. Ale z € |J 0 právě tehdy, když pro každou třídu X platí X € 0 A z G X. Avšak X € 0 neplatí nikdy, a proto z € IJ 0 neexistuje, a tudíž |J 0 C 0.
Cvičení.    Nechť U C V. Ukažte, že pak platí
10
logika a teorie množin
Cvičení.    Nechť x G X. Ukažte, že pak platí P| X C x C (J X.
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 e u I z c u}.
Není snad nutno zdůrazňovat, že pokud ř7 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. Cg 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 (VX G t/)(3Y G U) (VZ) {Z C X ^ 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 ZCI^ZeY. Dokažme Ci. Jestliže Z C X, pak Z G Y, a tedy Z je množina a Ci je dokázáno. Dokažme C2. Snadno se vidí, že C y, načež pX je množina, protože y 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 TV = {X G U \ X £ X} je množina a dostáváme spor N €i 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 e 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í.
(~]U = 9,     {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 € f]H- Jelikož 0 € U, z podmínky x € f)U plyne, že x náleží všem množinám, a tedy i prázdné množině, což je spor. Tudíž, x € f)U neexistuje.
Ohledně druhé rovnosti zřejmě [JU C U. Dokažme opačnou inkluzi U C |JW. Buď x € U libovolná množina. Ale x € |JW právě tehdy, když existuje třída X taková, želGtíaiĚl. Takové X existuje, například px.
3.10. Jednoprvková množina
Je-li x množina, definujeme třídu {x} předpisem
{x} = {y e U I y = x}.
Cvičení.    Rozhodnete, zda platí
a) 0 G {0};
b) 0C {0}.
3.14. Tvrzení. Platí
(yx e u) {x} e 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 C x. Tudíž, {x} C px, načež {x} je množina, protože px je množina podle Cg.
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 {x} = 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 ^ {0}, protože množina na levé straně nemá žádné prvky a množina na pravé straně prvek má, a sice 0. Podobně {0} ^ {{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 e U \ u = x\/ u = 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.
(Vz e U)(\/y e U)(3u e U) (V z e U) (z e u & (z = xV z = y)) čili jsou-li x, y množiny, pak třída {x, y} je množina.
F. Axiom sjednocení.
(VSeW) ((Jsew).
Je-li S množina, pak |J S 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. x {*,*} = {[<?,*], [<?,*], [0,*], [O,*]}.
Cvičení.    1. Buďte A, B libovolné třídy, buďte A' C A, B' C B jejich podtřídy. Ukažte, že platí
A' x B' = (A x 5') n (A' x B). 2. Buďte A, B libovolné třídy, buďte A', A" podtřídy třídy A. Dokažte, že platí
Později dokážeme, že kartézský součin množin je množina, ale neobejdeme se bez dalšího axiomu.
3.12. Relace a zobrazení
Relace a zobrazení mezi třídami se definují úplně stejně jako mezi množinami. Pro úplnost níže uvádíme základní definice, ale důkazy tvrzení ponecháváme jako cvičení.
3.19. Definice. Buďte A, B libovolné třídy. Relace (neboli korespondence) mezi třídami A, B je libovolná podtřída kartézského součinu Ax B. Je-li p C A x B relace a jsou-li a € A, b € B množiny takové, že [a, b] € p, pak říkáme, že a je v relaci p s b a stručně zapisujeme a p b. Relace na třídě A je zvláštní případ, kdy A = B.
Příklady. 1. Prázdná množina 0 C A x B je relace mezi třídami A,B. Žádné dva prvky a G A, b E B nejsou v této relaci.
2. Celá třída A x B je rovněž relace mezi třídami A, B. Každé dva prvky a E A, b E B jsou v této relaci.
3. Identická relace na třídě A je podtřída id^ = { [a, a] \ a G A }. Prvky a, b G A jsou v této relaci právě tehdy, když a = b.
(A' n A") x B = (A' x B) n (A" x B), (A' U A") x B = (A' x B) U (A" x B).
3. Buďte A, U libovolné třídy. Dokažte, že platí
A x f]U A x [J U
f](A x U), \J(A x U).
14
logika a teorie množin
3.20. Definice. Je-li p C A x B relace mezi třídami A, B, je relace p 1 C B x A mezi třídami B, A definovaná předpisem
P_1 := { [b, a] \ a pb} se nazývá opačná relace k relaci p. Zapamatujte si: a p b <S> b p-1 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 „cr po p") mezi třídami A, C, definovaná předpisem
a o p = {(a, c) | (36 e B) (a p b Ab a c)},
se nazývá složení relací p a a.
Cvičení.    Buď p relace mezi třídami A, B. Pak platí
1. po idA = p;
2. ids o p = p.
Buď navíc a relace mezi třídami B, C. Pak platí
3. (a o p)-1 = /9-1 o cr-1.
Cvičení.    1. Ukažte, že (p-1)-1 = p.
2. Nechť p C p', cr C cr'. 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 G A existuje právě jeden prvek b G B takový, že platí [a,b] €/.
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 / :«—> b nebo a i—> &.
Zavedeme-li zvláštní kvantifikátor 3! s významem "existuje právě jeden," lze podmínku na zobrazení zapsat jako
(Va e A) (31 b e B) [a, b] e f.
"Existuje právě jeden" znamená "existuje, a pokud jsou dva, pak jsou stejné," čili
(31 x e x)4>(x) & ({3x e x)4>(x)) a ((vx e x)(W e x) (<f>(x) a 4>(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í idA(o) = a pro každé a G A.
Je-li A C X podtřída, pak je la = {(a, a) \ a G A} zobrazení, které prvku a E A přiřadí týž prvek a G X: iAx(a) = 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, /i : C —► D zobrazení. Pak
/í ° (fl 0 /) = {h o g) o f.
Jak vyplývá 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 G 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 G A vždy existuje a je jediný, vzor prvku b G B obecně existovat nemusí a nemusí být ani jediný.
Pro obecnou podmnožinu B' C B definujeme
f~1B' = {a e A \ f (a) G B'}.
Speciálním případem je z předchozího odstavce.
3.22. Poznámka. Zdůrazněme, že vzor prvku b je třída a může být i vlastní. Uveďme 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í
/-1(B'ns") = /-1B'n/-1B",
f-1 (B'L) B") = T1 B'L) T1 B".
3.23. Definice. Zobrazení / : 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:
(V&G B)(3ae A)b= f (a).
Zobrazení f : A —> B se nazývá injektivní (injekce) neboli prosté, jestliže má každý prvek & G -B nejvýše jeden vzor v A:
(Va G A)(Wa' 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 /-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        = /-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) Bud'/i : 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 f 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, u = {(d,a) | a 6 ^4} přílušné vložení.
Je-li f : 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-
J\a : A X Y.
Všimněte si, že zúžení je dáno týmž předpisem a i—> f (a) jako /.
Je-li množina Y obsažena v jiné množině Z, pak existuje i kompozice íyz ° / : 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 | (3aeA)y = f(a)}, což často zkracujeme
fA={f(a)\aeA}. 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 i—> f(x), je surjektivní zobrazení a platí / = LfX,Y ° /•
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—Praenkelově axiomatizaci je na tomto místě schéma axiomů, v němž hrají roli substituce, odtud název.
Příklad. Označme U\ třídu všech jednoprvkových množin, které definujeme jako množiny tvaru {a}, kde a je množina.
Ukažme, že U\ je vlastní třída. Uvažujme o zobrazení s : U —> Ui, a i—> {a}. Zobrazení s je zřejmě surjektivní i injektivní (proč?), čili bijekce. Existuje proto inverzní zobrazení t : U\ —> li, {a} i—> a, které je rovněž bijekce. Kdyby U\ byla množina, pak by nutně i U = tli\ 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 € / přiřadí množinu Fi Gtí. Zobrazení F : I —> U se obecně nazývá systém množin. Alternativně píšeme {Fi}i<El. Definujeme
\jF< = \J{Fl\ieI} = \jFI,
i€l
f]Fi = f]{Fi\i€l} = f]FL
i€l
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
O
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 {&} = (J Ax {&},
b<EB b<EB
kde A x {b} jsou množiny podle axiomu substituce, protože A x {b} je obrazem množiny A při zobrazení a i—> [a, b].
3.27. Definice. Buďte f : X —> Y & g :Y ^ X zobrazení. Jestliže
gof = idx,
pak říkáme, že zobrazení g je levá inverze zobrazení /. Jestliže fog = idy,
pak říkáme, že zobrazení g je pravá inverze zobrazení /.
3.28. Tvrzení. Bud'f : A —> B injektivní zobrazení množin, přičemž A ^ 0. Pak má f levou inverzi.
Důkaz. Protože A je neprázdná, existuje c G A. Konstruujme g : B —> A. Jestliže b G f A, pak má právě jeden vzor, čili existuje a takové, že = {a}. Položíme g(b) = a, načež
g(f(a)) = g(b) = a. Jestliže naopak b £ f A, pak položíme g {ti) = c. Snadno se vidí, že gof = 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 —>4a platí g o / = 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 / = 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 G Y alespoň jeden vzor x G X takový, že f (x) = y. Pro každé y G 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 g CY x X 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í r : X —> |J X takové, že (\/x G X) t (x) G x.
Zobrazení r se nazývá výběrové zobrazení, protože vybírá po jednom prvku z každé množiny x e X.
3.29. Tvrzení. Buď f : A —> B surjektivní zobrazeni množin. Pak má pravou inverzi.
Důkaz. Buď / : A —> B injektivní zobrazení. Pak je {f~1{y} \ y G Y} systém neprázdných množin a podle axiomu výběru existuje výběrové zobrazení r splňující t(/_1{í/}) G f~1{y}. Nyní stačí položit g(y) = r(/-1{y}), aby platilo g(y) G /_1{y}> a tedy / 0 9 = 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 {_} 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] 1—> x, P2 : E —> X,     [x, a] 1—> a.
19
logika a teorie množin
Zobrazení p\ je surjektivní, protože každá množina i £ 1 je podle předpokladu neprázdná. Buď g pravá inverze k pi, čili p\ o q = idx- Máme q(x) = \j>i(q(x)),p2(q(x))] G E, načež P'ž{q{x)) G Pi(q(x)) = x pro každé x. Vidíme, že P2 o q je výběrové zobrazení.
Výběrové zobrazení 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ěrovým zobrazením {[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ď {Fi}iei systém množin. Označme
Prvky kartézského součinu nazýváme /-tice a používáme pro ně příhodný zápis [/i]iej, přičemž
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é zobrazení.
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 = U \ {0} třída všech neprázdných množin, existuje zobrazení r : T —> U takové, že (Vx G T) t (x) G x.
Axiom globálního výběru praví, že výběrové zobrazení 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 G 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.
Pří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á.
20
logika a teorie množin
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?
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^ je ekvivalence na třídě A.
2. Na univerzální třídě U 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 € A označme
[<Ap = {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 € A platí
a e [a]p,
a p b <S> [a]p = [b]p, [a] p n [b] p ^ 0 => [a] p = [b] p. Navíc, pokud jsou [a]p množiny, platí
U Wp = A.
3.36. Poznámka. Pokud je alespoň jedna třída [a]p vlastní, není sjednocení (Jae^Hp definová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 = {B e U   (3a e A) B = [a]p} = {[a]p  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
(ai, 61) 7 (02, 62) O ai p a2 A 61 cr 62-
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 }e třída ekvivalence o.
21
logika a teorie množin
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.
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 ~<j předpisem
Snadno se uláže, že ~<j 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 G V 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 = sOr — sGQ. 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í (nej menší) 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 TV je induktivní, jestliže platí
(i) 0 e N;
(ii) jestliže n G N, pak n U {n} G N. Dále,
X = {N G U | (0 G N) A (Vn) (n G N => n U {n} e N)} se nazývá třída všech induktivních množin. H. Axiom nekonečna.
X^0
(třída všech induktivních množin je neprázdná) aneb
(3N e U) ((0 G N) A (Vn) (n G N => n U {n} G N)) (existuje induktivní množina).
22
logika a teorie množin
Množinu přirozených čísel označujeme N a definujeme jako průnik všech induktivních množin. Tudíž,
N= n N=f]i,
N<EI
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í Q € K a implikace n€iK=>n + l€iK. 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í <f>(0) a implikace 4>{n) => 4>{n + 1). Pak platí 4>{n) pro všechna n € N.
Důkaz. Položíme K = {n € 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
(Vn€N)(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 e u) (x ^ 0   (3a; e 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 a a podobných.
3.41. Tvrzení. Neexistuje množina a taková, že a € a.
Důkaz. Množina {a} je neprázdná, a proto existuje podle axiomu regularity takový prvek b G {a}, že b D {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 € a. Pak a n {a} = {a} ^ 0, což je spor. Tudíž, a £ a.
23
logika a teorie množin
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.
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 n {a, b} = 0. Jsou dvě možnosti. Je-li c = a, pak a n {a, b} = 0, a proto b £ a. Je-li c = b, pak b n {a, b} = 0, a proto a £ b.
3.43. Tvrzení. Neexistuje systém množin {/„}„epí takový, že (Vn G N)/„+i G /„.
Tudíž, neexistuje nekonečná posloupnost množin /o 3 f\ 3 f2 3 ■ ■ ■ 3 fn 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 n S = 0. Podle konstrukce musí existovat n G N takové, že s = /„. Pak ale fn+i € fn a současně fn+i € S, což znamená, že s n 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 m U {m} = 0, ale levá strana obsahuje m jako prvek a pravá nikoliv.
3.46. Tvrzení. Nechť m, n G N splňují an = 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),
24
logika a teorie množin
právě jedno zobrazení N x N —-> N, splňující
n ■ 0 = 0,    n ■ am = n + (n ■ m) a právě jedno zobrazení N x N —> N, splňující
nA0 = 1,    nAam = n ■ (nAm).
Důkaz. Pro každé n € N definujme zobrazení an : N —> N rekurzivní formulí
an(0) = n,    an{am) = aan(m), zobrazení (3n : N —> N rekurzivní formulí
/3„(0) = 0,    /3„(ffm) = a„(A,(m)) a zobrazení 7„ : N —> N rekurzivní formulí
7„(0) = 1,    jn(o-m) = /3„(7„(m)).
Podle tvrzení 3.39 jsou zobrazení an, (3n 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), nAm = 7„(m).
Nyní dokážeme, že an = n + 1. Máme postupně
n + 1 = an(l) = «„(0-0) = aan(0) = an.
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 ■ 1 = a,
a + b = b+a, a-b=b-a,
a + (b + c) = (a + b) + c,        a ■ (b ■ c) = (a ■ b) ■ c,
a ■ (b + c) = (a ■ b) + (a ■ c),    aA(b + c) = (aAb) ■ (aAc),
(a ■ b)Ac = (aAc) ■ (bAc),
(aAb)Ac = aA(b-c),
aA0 = l, 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 = 0. Zjednodušuje to mnohé formule. Například zápis
anxn + • • • + a\x + ciq = anxn
o
-10
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 € 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 p€Zat/€N \ {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, q{\ p [p2, 52]     P1Q2 = P'žQi- Zřejmě je Q množina.
Dobře známa je konstrukce rálných čísel jako Dedekindových řezů. Zde uvedeme jinou definici pomocí dvojkových rozkladů, čili jako posloupností dvojkových cifer 0,1. Reálné číslo
z polouzavřeného intervalu I = [0,1) lze ztotožnit se zobrazením N —> {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, ai ... «„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 2W, 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 limx—>c f(x) = 0 a limx^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^
26
logika a teorie množin
4. Mohutnosti
Velmi důležitou relaci ekvivalence představuje ekvivalence ~, kdy dvě množiny A, B považujeme za ekvivalentní právě tehdy, když existuje bijekce A —> B. Konečné množiny jsou ekvivalentní právě tehdy, když mají stejný počet prvků (dokažte). Ekvivelence je zobecnění "rovnosti počtu prvků" na obecné množiny.
Cvičení.    Ukažte, že právě definovaná relace ~ je reflexivní, symetrická a tranzitivní.
Cvičení. Ukažte, že pro libovolnou množinu A platí A x A ~ A2. (A2 je množina všech zobrazení z dvouprvkové množiny 2 = {0,1} do A.
Důležitý příklad ekvivalence poskytuje následující tvrzení.
4.1. Tvrzení. Je-li X množina, pak
pX ~ 2X,
tj. existuje bijekce mezi množinou pX všech podmnožin v X a množinou všech zobrazení z X do dvouprvkové množiny.
Důkaz. Bijekcí je zobrazení pX —> 2X, které dané podmnožině A C X přiřadí zobrazení f a '■ X —> 2X, definované předpisem
, , \ _ í 1, jestliže x € A, 1a(x) - j 0;    jestliže X£A.
Inverzní bijekcí 2X —> pX je zobrazení, které zobrazení / : X —> 2X přiřadí vzor /_1{1} jedničky.
O ekvivalentních množinách pravíme, že mají stejnou mohutnost. Nic nám nebrání zavést nějaké symboly pro jednotlivé mohutnosti. Obecně se takové symboly nazývají kardinální čísla.
Nabízí se myšlenka definovat mohutnosti jako třídy rozkladu W/~ podle ekvivalence ~. Prvky rozkladu tj. třídy ekvivalence ~, jsou však vesměs vlastní třídy, a proto nemohou být prvky
jiných tříd. To je další drobný nedostatek zvolené axiomatizace, který se však dá snadno obejít.
Mohutnost množiny A značíme #A. Podle definice #A = #B$$A~B.
Pro každé n € N, množiny ekvivalentní s množinou n = {0,..., n—1} (ekvivalentně, množiny o n prvcích), nazýváme n-prvkové množiny. Třída n-prvkových množin budiž označena Un. Za příslušné kardinální číslo volíme prostě n G N, to jest, #n = n.
Množiny náležející sjednocení
(J Un
se nazývají konečné množiny. Množinu N ztotožňujeme s množinou konečných mohutností. Ostatní mohutnosti se nazývají nekonečné mohutnosti.
Množiny ekvivalentní s množinou N se nazývají spočetné množiny. Spočetná mohutnost se označuje symbolem (^ Je první písmeno hebrejské abecedy a čte se alef). Máme tedy #N = ^o- Ještě se dočkáme nekonečně mnoha dalších alefů (dokonce budou tvořit vlastní třídu) a každá nekonečná mohutnost bude některým alefem.
27
logika a teorie množin
Příklad. Se spočetnými množinami jste se již seznámili v přednášce z matematické analýzy. Měli byste (nalezením příslušné bijekce) umět ověřit, že
Návod: Uspořádejte celá resp. racionální čísla do posloupnosti Z výsledku plyne, že #Z = #(N x N) = #Q = K0.
Zatím nemůžeme definovat třídu kardinálních čísel. Tento nedostatek napravíme později. Předesíláme, že kardinální čísla tvoří vlastní třídu.
4.1. Aritmetika kardinálních čísel
Nyní zavedeme sčítání, násobení a umocňování kardinálních čísel, které bude zobecněním obdobných aritmetických operací s přirozenými čísly. Budeme k tomu potřebovat další výsledky o množinách.
Při sčítání mohutností se používá disjunktní sjednocení množin.
4.2. Definice. Buďte A, B dvě množiny. Množina ({0} x A) U ({1} x B) se nazývá disjunktní sjednocení množin A, B a značí se A U B.
Snadno se vidí, že množiny {0} x A a {1} x B nemají žádné společné prvky (proč?) a v tom spočívá smysl této konstrukce. Později ji zobecníme na systémy množin.
4.3. Tvrzení. Budie A, B dvě disjunktní množiny. Pak AUB~iUB. Důkaz. Zadejme zobrazení h : AU B —> AU B předpisem
Ukažte jako cvičení, že h je bijekce.
4.4. Tvrzení. Budie A ~ A' dvě ekvivalentní množiny a B ~ B' jiné dvě ekvivalentní množiny. Pak
1° AUB ~ Ä UB', 2° AxB~ÄxB',
3°       BA ~ B'A' jsou ekvivalentní množiny.
Důkaz. Buďte g a '■ A —> A' a g b '■ B —> B' bijekce. 1° : Zaveďme zobrazení
Snadno se ukáže, že gA U gs je bijekce s inverzí gA 1 U (Jb 1. Tudíž, A U B a A' U B' jsou ekvivalentní.
N~Z,    N ~ N x N,    N ~ Q.
když x G A, když x G B.
g a U gB ■ A U B —> A' U B'
předpisem
když x = [0, a] e {0} x A, když x = [1,6] e {1} x B.
28
logika a teorie množin
2° : Zaveďme zobrazení
g a x qb ■ A x B —> A1 x B1
předpisem
{ga x gB)(a, b) = [gA(a),gB(b)].
Snadno se ukáže, že qa x gB je bijekce s inverzí <M_1 x gB~ľ. Tudíž, A x B a A' x B' jsou ekvivalentní.
3° . Zobrazení BA —> _B'A , / ^ ffs ° / ° ffÄ1' m^ inverzi _B'A —> _BA, /i i—> g^1 o /i o g^, a proto je bijektivní. Tudíž, BA a B'A jsou ekvivalentní.
V důsledku posledního tvrzení můžeme zavést sčítání, násobení a umocňování kardinálních čísel předpisy
1°       #i+#B = #(iUB),
2°       #Ax#B = #(A x B),
3o = #(BA).
Jinak řečeno, k daným mohutnostem libovolně vybereme množiny, které je reprezentují, provedeme s nimi odpovídající množinovou operaci a zjistíme mohutnost výsledku.
Cvičení.    Přesvědčte se, že 1 + 1 = 2, 1 x 2 = 2, l2 = 1, 21 = 2.
Cvičení.    Ukažte, že K0 + 1 = K0 + 2 =• • • = K0 + K0 = K0. Návod: Uspořádávání do posloupnosti.
Cvičení.    Ukažte, že K02 = K03 =• • • = K0. (Pozor, K0N° = K0 neplatí!) Návod: Uspořádávání do posloupnosti.
Pro operace s kardinálními čísly platí obvyklé zákony aritmetiky. 4.5. Tvrzení. Buďte a, b, c libovolné mohutnosti. Pak a + b = b + a,
0 + a = a,
(a+ b) + c = a+ (b + c), a x b = b x a,
1 x a = a,
(a x b) x c = a x (b x c),
ax(b + c) = axb + axc,
0xo=0,
ab+c = ab x ac,
a6xc = (a6)c,
(a x b)c = ac x bc,
a° = l,
a1 = a.
Důkaz. Nechť a = 4^A, b = #-B, c = #C. Jako cvičení nalezněte potřebné bijekce.
29
logika a teorie množin
Cvičení.    Ukažte, že pro každou mohutnost m platí lm = 1, m + m = 2 x m, m2 = m x m. A pokud m/0, pak 0m = 0.
Operace s kardinálními čísly mají i analogie pro systémy kardinálních čísel.
4.6. Definice. Buď {Fi}iei systém množin. Jeho disjunktní sjednocení definujeme jako sjednocení
Podobně jako u binární operace U platí, že sjednocované množiny {i} x Fi nemají žádné společné prvky (proč?) a opět v tom spočívá smysl této konstrukce.
4.7. Tvrzení. Buď {Fi}iei systém množin po dvou disjunktních, čili takových, že Fi n Fj = 0, kdykoliv i^jel. Pak Uí£j Fi ~ |Jíej Ft.
Důkaz. Zadejme zobrazení h : {Ji<El Fi —> Uiei Fi předpisem
\JFi = \J{{t}xFi).
h(x) = [i, x
když x € Fi.
Ukažte jako cvičení, že h je bijekce.
4.8. Tvrzení. Budie Fi ~ F[ systémy ekvivalentních množin. Pak
1
O
Lh-U*?
2'
lO
jsou ekvivalentní množiny.
Důkaz. Buďte Qi : Fi —> F( bijekce. 1° : Zaveďme zobrazení
předpisem
Snadno se ukáže, že |_|ieJ g% je bijekce s inverzí        Qi   ■ Odtud tvrzení. 2° : Zaveďme zobrazení
ieJ      ieJ ieJ
předpisem
30
logika a teorie množin
Snadno se ukáže, že Yliei 9i Je bijekce s inverzí Yíiei 9%    Odtud tvrzení.
Při troše velkorysosti můžeme se systémem {Fi}iei spojit systém kardinálních čísel fj = j^Fi (ignorujeme fakt, že dosud nemáme třídu kardinálních čísel). Díky právě dokázanému tvrzení lze definovat součet a součin systému kardinálních čísel předpisem
rif i=#nfi-
Jde o přímá zobecnění výše definovaných binárních operací '+' a 'x' (ty dostáváme pro dvouprvkové systémy množin).
Platí analogie formulí z tvrzení 6.7, zejména
a x ^ bi = ^ a x bi a^ei** =l[ab ,
i€l
n*ľ=iR
Dokažte je jako cvičení.
Analogií komutativního a asociativního zákona je, že se v definici neuplatňuje žádné uspořádání indexové množiny.
Cvičení.    Ukažte, že
neN neN neN
a obecně
m = Kq x m.
4.2. Uspořádání mohutností
Řekneme, že mohutnost a je menší nebo rovna mohutnosti b, a zapisujeme a < b, jestliže existuje injektivní zobrazení A —> B takové, že a = j^A a b = #-B. Injektivní zobrazení existuje nebo neexistuje nezávisle na volbě reprezentantů A, B. S trochou velkorysosti dostáváme relaci < mezi kardinálními čísly (odhlédneme-li od toho, že zatím neumíme definovat třídu kardinálních čísel).
Relace < je zřejmě reflexivní (skrze identické zobrazení) a tranzitivní (skrze skládání in-jektivních zobrazení). Cantor-Bernsteinova věta praví, že relace < je i antisymetrická. Jde o netriviální tvrzení.
Pokud jste zapomněli, co je antisymetrie, odskočte níže na definici 5.1 a zase se vraťte. 4.9. Cantor-Bernsteinova věta. Jestliže a < b a zároveň b < a, pak a = b.
31
logika a teorie množin
Důkaz. Nechť a = j^A a b = #-B. Podle předpokladu existují injektivní zobrazení / : A —> B a g : B —> A. Konstruujme bijektivní zobrazení A —> B. Označme
A0	= A,	B0	= B,
A!	= gB0,	Si	= fA0
A2	= gBi,	B2	= !AX
A3	= gB2,	B3	= ÍM
Ai	= gB3,	B4	= fA3
a obecně Ai+\ = gBi, Bi+\ = fAi pro každé přirozené číslo i. Přitom
A0 d Aí d A2 d ■ ■ ■, B0d BíD B2d • • •,
Dále g dává bijekci Bi —> Ai+\ a / dává bijekci Ai —> Bi+\. Tudíž, g\bi-1\bi Je bijekce
Bi-i \ Bi —> Ai\ Ai+i a podobně /|aí_i\Aí Je bijekce
Ai-i \Aí^>Bí \ Bi+Í. Složením dostáváme bijekce
A0 \ A1     B1 \ B2     A2 \ A3     B3 \ BA     ■ ■ ■ zprostředkované zobrazením / a bijekce
B0 \ B1     A1 \ A2     B2 \ B3     A3 \ AA     ■ ■ ■ zprostředkované zobrazením g. Z nich je možné sestavit bijekce mezi sjednoceními
[J A2i \ A2i+i <—> [J B2i+i \ B2i+2
a rovněž mezi sjednoceními
[J B2i \ B2i+i <—>     A2i+i \ A2i+2.
Celkově je tím nalezena bijekce mezi podmnožinami \jB,\Bl+1 ^ \JAí\Aí+1.
Podmnožina Ui<EŇ B{\Bi+i resp. {Ji<EŇ A{\Ai+i ovšem není rovna celému A resp. B. Nicméně, (J A\Al+1 =A\ f]Ai,     UB,\% = B\Í1B-
32
logika a teorie množin
Inkluze C plyne z inkluzí Ai\Ai+i C A\P|ieW Ai pro každé i; podobně pro B. Opačnou inkluzi D dokážeme úvahou, že pro libovolný prvek a G A \ f]i<EŇ Ai existuje nejmenší i takové, že a (JL Ai+\, načež a G Ai \ Ai+\. Tudíž, zatím jsme našli bijekci
A \ f] A, ~ B \ f] B,
a ještě zbývá zkonstruovat bijekci mezi průniky HieM^-i a HiePí^i- To lze provést například následujícím způsobem:
r\Al=f]A2l=f](gofyA^f]f(gofyA
iew        iew iew iew
= f](f°gYfA= f]B2l+1 = f]Bi.
Důkaz je hotov.
Cantor-Bernsteinova věta je velmi užitečná při výpočtech mohutností. Dokázat dvě nerovnosti (najít dvě injektivní zobrazení) bývá velmi často mnohem snazší než najít bijekci. Příklady najdete v pojednání o mohutnosti kontinua níže.
Hodí se i následující tvrzení o nerovnostech mezi mohutnostmi.
4.10. Tvrzení. Nechť a, a', b, b' jsou mohutnosti takové, že a < a', b < b'. Pak
1° a+b<a' + b', 2° a x b < a' x b', 3°       a6 < a'6'.
Důkaz. Nechť a = #A, a' = #A', b = #B, b' = #B'. Podle předpokladu existují injektivní zobrazení / : A —> A', g : B —> B'. Snadno se ukáže, že zobrazení f U g a f x g zkonstruovaná v částech 1° a 2° důkazu tvrzení 4.4 jsou injektivní (proveďte podrobně sami).
V případě 3° je potřeba zkonstruovat injektivní zobrazení AB —> A'B . Buď h : B —> A libovolné zobrazení. Z injektivity zobrazení g : B —> B' plyne, že existuje zobrazení h : B' —> A takové, že h o g = h (proč?). Pak je kompozice h' = foh hledané zobrazení B' —> A'.
Dokažme injektivitu přiřazení h \—> h!. Nechť jsou dvěma zobrazením h\,hi : B —> A přiřazena stejná zobrazení h[ = h'2 : B' A'. Pak / o h[ o g = f o h'2 o g, čili / o h\ = f o h2. Jelikož je / injektivní, smíme jím krátit zleva, načež h\ = h2 a důkaz je hotov.
Cvičení.    Proč se v případě 3° nedá použít konstrukce z důkazu tvrzení 4.4?
Klasický Dirichletův princip praví, že pro žádné přirozené číslo n neexistuje injektivní zobrazení n + 1 —> n. Dokážeme jej jako součást obecnějšího tvrzení.
4.11. Dirichletův princip. Platí
0 < 1 < 2 < 3 <•••< tt0-
Důkaz. Připomeňme, že n + 1 = {0,1, 2,..., n}.
33
logika a teorie množin
Neostré nerovnosti < plynou z existence injektivních vložení 0 -> {0} -> {0,1} -> {0,1, 2} ->----> N.
Nerovnosti n + 1 ^ n bezprostredné vyplývají z klasického Dirichletova principu. Důkaz Dirichletova principu povedeme indukcí. Označme Dn tvrzení: "Pro n G N neexistuje injektivní zobrazení n + 1 —> n." Tvrzení L>o zřejmě platí (proč?). Nechť Dn platí pro pro některé n, dokažme platnost Dn+\. Důkaz povedeme sporem. Připusťme tedy, že existuje injektivní zobrazení / : n + 2 —> n+1. Připomeňme, že n + 2 = {0,l,2,...,n+l}. Prvek /(n + 1) G n+1 není obrazem žádného jiného prvku z n + 2, jak plyne z injektivity. Pak je dobře definována restrikce f\n+i : n+1 —> n + 1 \ {/(n + 1)} aje rovněž injektivní. Avšak n + 1 \ {/(n+ 1)} ~ n (zkonstruujte bijekci), takže jsme obdrželi injektivní zobrazení n+1 —> n, což je ve sporu s Dn.
Zbývá dokázat nerovnost n < Pro všechna n G N. Označme Dn tvrzení: "Pro přirozené číslo n neexistuje injektivní zobrazení N —> n." Důkaz indukcí proveďte jako cvičení (princip je podobný, opět je nutno z injektivního zobrazení N —> n + 1 vyčlenit injektivní zobrazení N -> n).
4.12. Tvrzení. Jestliže a < b < c, pak a < c.
Důkaz. Nechťa< b < c. Zřejmě a < c (složení injektivních zobrazení je injektivní). Připusťme, že a = c. Pak a < b < a a z Cantor-Bernsteinovy věty plyne, že a = b, spor.
4.13. Cantorova věta. Pro každou mohutnost a platí a < 2a.
Důkaz. Nechť a = #A Injektivní zobrazení A —> pA je například a i—> {a}. Odtud A ^ pA, a tedy a < 2a.
Připusťme, že A ~ pA. Nechť F : A —>      je bijektivní zobrazení. Označme
X = {a G A | a g F (a)}.
Jelikož je F surjektivní, existuje x G A takové, že F(x) = X. Pak nastane právě jedna ze dvou možností.
1) x £ X, čili x G F(x), načež x e" X podle definice množiny X, spor;
2) x £ X, čili x £ F(x), načež x £ X podle definice množiny X, spor. Tudíž, A / pA, a proto a ^ 2a.
4.14. Důsledek. _/ýe každému kardinálnímu číslu existuje větší kardinální číslo.
Poznamenejme, že zatím neumíme odpovědět na otázku, zda existují nesrovnatelné mohutnosti, tj. mohutnosti a, b, pro něž nenastává žádná z možností a < b, a = b, a > b. Odpověď je záporná (neexistují), ale vyžaduje větší úsilí. Odložíme ji do jedné z dalších kapitol spolu s tzv. pohlcovacími zákony, které umožňují stanovovat součty a součiny libovolných mohutností bez zdlouhavého počítání. Mezitím se budeme věnovat dalším mohutnostem, které mají uplatnění v matematické analýze.
4.3. Mohutnost kontinua
Mohutnost 2H°, o níž zatím víme jen tolik, že je nespočetná (ostře větší než podle Cantorovy věty), se nazývá mohutnost kontinua. Značí se c. Pojmenování pochází z názvu "kontinuum" pro množinu reálných čísel.
4.15. Tvrzení. Platí c = #K.
34
logika a teorie množin
Důkaz. 1) Nerovnost c < #R dokážeme konstrukcí injektivního zobrazení 2N —> R. Zobrazení N —> 2 je totéž, co posloupnost [a„]„eN nul a jedniček, an € {0,1}. Takové posloupnosti můžeme přiřadit třeba reálné číslo s desetinným rozvojem
Přiřazení je injektivní, protože různým posloupnostem odpovídají různá reálná čísla (problematická splynutí jako např. 1 = 0, 999 ... se nevyskytnou díky tomu, že jsme zvolili číselnou soustavu se základem 10 ^ 2).
2) Nerovnost #R < c dokážeme konstrukcí injektivního zobrazení R —> 2^ (racionálních čísel je též spočetně mnoho). Přiřazení budiž
Důkaz injektivity: Nechť jsou r\ < r2 různá reálná čísla. Pak Q<ri ^ Q<r2i protože existuje racionální číslo r\ < q < r 2 a toto číslo q náleží Q<r2 a nenáleží Q<ri. Důkaz je hotov.
Stejně tak mají mohutnost kontinua intervaly I(a, 6), I(a, b], l[a,b), l[a, b], kde a < b jsou reálná čísla (pro jednoznačnost používáme značení obvyklé v analýze, ale s předsunutým písmenem I). Stačí si všimnout, že pro ně prochází již provedený důkaz rovnosti c = #R jen s malou modifikací nahrazující injektivní zobrazení 2W —> R injektivním zobrazením 2W —> I(a, b) (jakým?). Potažmo i do zbývajících intervalů I(a, b], l[a, b), l[a, b].
Z Cantor-Bernstainovy věty vyplývá, že existují bijekce mezi množinami 2W, R, I(a, b), I(a, 6], I[a, 6), I[a, &]. Z důkazu Cantor-Bernstainovy věty pak také vyplývá návod, jak by bylo možné ony bijekce sestavit, ale je zřejmé, že konstrukce by byly značně komplikované. V sadě následujících cvičení ukážeme, jak takové bijekce sestrojit snáze.
Cvičení.    Najděte bijekci mezi 1(0,1) a K. Návod: kompozice tg a lineární funkce.
Cvičení.    Najděte bijekci mezi 1(0,1) a 1(0,1].
Návod: Oba intervaly rozložte na sjednocení spočetně mnoha jednobodových množin a spočetně mnoha otevřených intervalů, např.
{q e Q I q < r}.
Cvičení.    Najděte bijekci mezi 1(0,1] a I[0,1]. Návod: Upravte kontrukci z předchozího cvičení.
Cvičení.    Ukažte, že
c = c+ l = c + 2=---=c + K0 = c + c = c + c + c=---=K0xc
= CX(=tX(Xt - •■=("'.
Cvičení.    Ukažte, že #C = c.
35
logika a teorie množin
Cvičení.    Ukažte, že množina všech spojitých funkcí K —> K má mohutnost kontinua. Návod: Spojitá funkce je určena svými hodnotami na racionálních číslech.
Příklad. Cantorovo diskontinuum V první části důkazu věty 4.15 jsme sestrojili injektivní zobrazení 2 —> K. Posloupnosti [an]nÉN nul a jedniček jsme přiřadili reálné číslo s desetinným rozvojem
an10n = 0, a$a\a-2 . . .
Obrazem tohoto zobrazení je podmnožina v K, která se nazývá Cantorovo diskontinuum. Můžeme ji popsat jako množinu všech reálných čísel z intervalu I[0,1], jejichž desetinný rozvoj obsahuje jen nuly a jedničky (včetně rozvojů s nekonečně mnoha po sobě jdoucími jedničkami). Stejnou množinu dostaneme tak, že z intervalu I[0,1] vyloučíme otevřený interval I(jg, y^), tedy prostředních osm desetin, což opakujeme do nekonečna. Jak se dá ukázat, z jednotkového intervalu takto vyloučíme intervaly v celkové délce 1. Přesto má Cantorovo diskontinuum mohutnost kontinua.
Cvičení.    Dokažte tvrzení uvedená v předchozím příkladu.
4.4. Cantorův důkaz existence transcendentních čísel
V Cantorově době byla známa jen jednotlivá transcendentní čísla, přičemž množina transcendentních čísel není dodnes úplně prozkoumána. Cantor překvapivě snadno dokázal, že transcendentních čísel je nekonečně mnoho.
Připomeňme definice. Algebraickým číslem se rozumí komplexní číslo, které je kořenem nenulového polynomu s racionálními koeficienty. Transcendentním číslem se rozumí komplexní číslo, které není algebraické.
4.16. Tvrzení. Mohutnost množiny algebraickcýh čísel je No.
Důkaz. Nechť 21 je množina všech algebraických čísel.
1) < #2íj protože každé racionální číslo je algebraické (proč?).
2) Ukažme, že #21 < No- Množinu algebraických čísel vyjádříme jako sjednocení
a = U 2i„,
kde n je stupeň příslušného minimálního polynomu (minimální polynom algebraického čísla a je polynom minimálního stupně mezi polynomy s racionálními koeficienty a kořenem a). Mohutnost množiny 2t„ je n x #Q™ = n x No™ =     (proč?). Dostáváme tedy
#2Í < # |J 2Í„ < ^ #2Í„ = ^ N0 = N0 x N0 = No-
nePÍ nePÍ nePÍ
Důkaz je hotov.
4.17. Důsledek. Mohutnost množiny transcendentních čísel je c.
4.5. Další mohutnosti matematické analýzy
Již jsme se zmínili, že existuje nekonečně mnoho (dokonce vlastní třída) nekonečných mohutností. Kromě alefů N, které patří k poměrně obtížným pojmům, existuje nekonečná řada mohutností 3 (beth, druhé písmeno hebrejské abecedy), které jsou mohutnostmi množin hojných v analýze.
36
logika a teorie množin
Pro přirozená čísla n € N definujme 3„ rekurzivním předpisem
Podle Cantorovy věty zřejmě 3q < 3i < 32 <• • •. Máme
31=2No = c,    32 = 23l=2c,    33=232=22\ ...
a také
30=#N,    3i=#pN,    32 = #pPN,    33=#ppPN, ...
Cvičení.    Ukažte, že mohutnost ^2 mají množiny
1) pK všech podmnožin množiny reálných čísel;
2) KR všech reálných funkcí jedné reálné proměnné;
3) J^neJV ^    všech reálných funkcí konečně mnoha reálných proměnných.
4.18. Poznámka. Čím se aritmetika kardinálních čísel liší od aritmetiky přirozených čísel? Především nelze krátit ani v součtech ani v součinech. Například 1 + = 0 + ačkoliv 1^0. Podobně 1 x ^ = 2 x No, ačkoliv 1^2. Nelze pak zavést ani rozumné odečítání a dělení.
Společné zase mají to, že ani v oboru kardinálních čísel neexistují dělitelé nuly. Když a x b = 0, pak a = 0 nebo b = 0, protože kartézský součin neprázdných množin je neprázdný. Žádné důsledky pro krácení to ovšem nemá, protože není k dospozici odečítání.
5. Dobře uspořádané množiny a ordinální čísla
Na předchozích stránkách jsme došli k jisté představě o kardinálních číslech (mohutnostech množin), které je ovšem prozatím značně děravá. O nekonečných mohutnostech hodnověrně víme jen tolik, že existuje vzrůstající řada nekonečných mohutností, ale nevíme skoro nic o ostatních mohutnostech.
Nej lepší znalosti máme o spočetných množinách, kde funguje metoda matematická indukce. Metodu lze snadno zobecnit na obecnější dobře uspořádané množiny. Zobecnění se nazývá transfinitní indukce.
Zatímco kardinální čísla zobecňují přirozená čísla ve smyslu množství, ordinální čísla zobecňují přirozená čísla ve smyslu seřazení. Pokračování za konečná čísla je ovšem rozdílné. Na jedno nekonečné kardinální číslo připadá nekonečně mnoho ordinálních čísel. Například, zatímco existuje jen jedna spočetná mohutnost spočetných ordinálních čísel je nekonečně mnoho a dokonce nespočetně mnoho (přesně Ki). A že paradoxů není nikdy dost, uvidíme, že mezi kardinálními čísly a ordinálními čísly existuje bijekce.
5.1. Uspořádání
Nejdříve připomeneme pojmy týkající se obecných relací uspořádání.
5.1. Definice. Řekneme, že relace < na třídě A je antisymetrická, jestliže platí implikace (a < b A b < a) => a = b pro všechna a, b € A.
Reflexivní, antisymetrická a tranzitivní relace se nazývá uspořádání.
Je-li < uspořádání na třídě A, pak > definovaná předpisem a>b<^b<aje rovněž uspořádání na třídě A.
Je-li < uspořádání na třídě A, pak relace < definovaná předpisem a < b <S> (a < b A a ^ b) se nazývá ostré uspořádání. Podobně >.
37
logika a teorie množin
Třída spolu se zadaným uspořádáním se nazývá uspořádaná třída. Množina spolu se zadaným uspořádáním se nazývá uspořádaná množina.
Každá podtřída B C A uspořádané třídy A je uspořádaná třída, definujeme-li indukované uspořádání na B formulí <b = <a H (B x B), to jest, klademe-li a <b b <S> a <a b pro a, b € B. Podobně pro ostré uspořádání.
Příklad. Inkluze C je uspořádání na univerzální třídě U a každé její podtřídě. Ostrá inkluze C je ostré uspořádání na univerzální třídě U a každé její podtřídě.
Příklad.    Množiny N,Z,Q, K jsou uspořádány obvyklým způsobem "podle velikosti." Příklad.    Prázdná relace 0 x 0 na prázdné množině je ostré i neostré uspořádání.
5.2. Definice. Buď A uspořádaná třída. Prvek m € A se nazývá největší prvek resp. nejmenší prvek, jestliže
(Vet € A) a < m    resp.    (Va G A) m < a.
Prvek m € A se nazývá maximální prvek resp. minimální prvek, jestliže
(Va G A) (m < a => m = a)    resp.    (Va G A) (a < m => m = a).
Příklad.    Univerzální třída U má nejmenší prvek 0 a nemá žádný největší prvek.
Cvičení.    Uspořádaná třída má nejvýše jeden největší a nejvýše jeden nejmenší prvek.
Cvičení. Největší prvek uspořádané třídy je jediným maximálním prvkem této třídy. Nejmenší prvek uspořádané třídy je jediným minimálním prvkem této třídy.
Cvičení. Uveďte příklad uspořádané množiny, která má jediný maximální prvek a žádný největší prvek.
Návod. Množina je nutně nekonečná.
5.3. Definice. Buď X uspořádaná třída, A C X její podtřída. Prvek m G X se nazývá horní závora resp. dolní závora podtřídy A, jestliže
(Va G A) a < m    resp.    (Va G A) m < a.
Existuje-li nejmenší horní závora, nazývá se supremum a značí se sup A. Existuje-li největší dolní závora, nazývá se infimum a značí se inf A.
Cvičení. Každá množina A C U (tj. množina množin) má supremum i infimum vzhledem k uspořádání inkluzí a platí sup A = |J A a inf A = |~| A.
5.2. Řetězce
5.4. Definice. Prvky a, b uspořádané množiny se nazývají srovnatelné, jestliže platí
(a < b) V (6 < a).
Uspořádání < na třídě A je úplné, jestliže jsou každé dva prvky třídy A srovnatelné. Třída spolu s úplným uspořádáním se nazývá úplně uspořádaná třída. Úplně uspořádaná množina se nazývá řetězec.
38
logika a teorie množin
Příklad.    Množina reálných čísel s obvyklým upořádáním je řetězec.
Podmnožina řetězce s indukovaným uspořádáním je opět řetězec (protože nemá nesrovnatelné prvky) a nazývá se podřetězec.
Příklad. Intervaly I(a, 6), I(a, 6], l[a, b), l[a, b] jakož i množiny N,Z,Q tvoří podřetězce v řetězci reálných čísel.
Příklad.   Uspořádání třídy U inkluzí není úplné. Množiny {a} a {b}, kde a / 6, jsou nesrovnatelné.
Buď M řetězec, buďte m,n € M dva prvky takové, že m < n a neexistuje p € M takové, že m < p < n. Pak řekneme, že prvek n je následovník prvku m, resp., že prvek m je předchůdce prvku n a zapisujeme m <o n nebo n o> m.
Cvičení. Ukažte, že každý prvek a E M má nejvýše jednoho předchůdce a nejvýše jednoho následovníka .
5.3. Dobré uspořádání
5.5. Definice. Řekneme, že uspořádaná třída T je dobře uspořádaná, jestliže každá neprázdná podtřída A C T obsahuje nejmenší prvek.
5.6. Tvrzení. Každá dobře uspořádaná třída je úplně uspořádaná.
Důkaz. Připusťme, že existují nesrovnatelné prvky a, b. Pak množina {a, b} nemá nejmenší prvek.
Příklad.    Každý konečný řetězec je dobře uspořádaný.
Příklady.    1. Množiny Z, Q, K nejsou dobře uspořádané, neboť neobsahují nejmenší prvek.
2. Polouzavřený interval I[0,1) není dobře uspořádaná množina, protože jeho podmnožina 1(0,1) neobsahuje nejmenší prvek.
5.7. Tvrzení. Množina přirozených čísel je dobře uspořádaná.
Důkaz. Buď ACH neprázdná podmnožina, buď a € A libovolný prvek. Prvky větší než a nemají vliv na existenci nejmenšího prvku, prvky menší nebo rovné a zase tvoří neprázdný konečný řetězec, který má nejmenší prvek.
Připomeňme, že prvek b uspořádané množiny je následovníkem prvku a, jestliže a < b a neexistuje c takové, že a < c < b.
5.8. Tvrzení. Každý prvek dobře uspořádané třídy, s výjimkou největšího, má následovníka.
Důkaz. Buď X dobře uspořádaná třída, buď a € X libovolný prvek, který není největším prvkem v X. Nechť B = {x € X \ a < x}. Kdyby byla třída B prázdná, bylo by x > a pro všechny prvky x € X (protože X je úplně uspořádaná) a a by byl největším prvkem v X, což podle předpokladu není. Tudíž, B je naprázdná a podle předpokladu má nejmenší prvek. Označme jej b. Evidentně a < b. Ukažme, že b je následovník prvku a. Připusťme opak, tedy že existuje prvek c takový, že a < c < b. Pak c G B, a tedy nutně b < c, což je spor.
Dobře uspořádanou množinu můžeme znázornit diagramem, v němž jsou prvky seřazeny zleva doprava od menších k větším a každý prvek je spojen úsečkou se svým následovníkem.
39
logika a teorie množin
Příklady.    Pětiprvkový řetězec má diagram
o—o—o—o—o. Množina přirozených čísel má diagram
O-O-O-O- • • • ;
kde tři tečky znamenají spočetné opakování vzoru o—.
Cvičení. Ukažte, že v dobře uspořádané množině nemůže existovat nekonečná ostře klesající posloupnost prvků • • • < CL2 < ai < ao.
5.4. Transflnitní indukce
Princip transflnitní indukce umožňuje dokazovat tvrzení tvaru
(Vz e x) (t>(x),
kde X je dobře uspořádaná třída. Indukční krok spočívá v důkazu, že z pravdivosti 4>{x) pro všechna x < a plyne pravdivost 4>{a).
5.9. Tvrzení. Buď 4>{x) formule, buď X dobře uspořádaná třída. Nechť pro všechna a € X podmínka (\/x < a) 4>{x) implikuje 4>{a). Pak je 4>{x) pravdivá pro všechna x € X.
Důkaz. Buď A C X podtřída, tvořená prvky x, pro něž 4>{x) neplatí. Připusťme, že A ^ 0. Pak existuje nejmenší prvek a € A, což je nejmenší prvek, pro něž <f> neplatí. Pro všechny prvky x < a (pokud existují) potom 4>{x) platí, takže, podle předpokladu, platí i 4>{a), což je ve sporu s a € A. Tudíž, A = 0, a tedy 4>{x) platí pro všechna x G X.
Může se zdát, že 4>{x) nemusí platit pro nejmenší prvek a třídy X. Opak je pravdou, neboť třída {x € X | x < a} je v tomto případě prázdná, a proto je podmínka (\/x < a) 4>{x) splněna.
Princip transflnitní indukce také umožňuje konstruovat množiny Fx závislé na prvku dobře uspořádané třídy X. K tomu stačí dokazovat formule tvaru
(\/xeX)(3FxeU)ct>(x,Fx).
V tom případě hovoříme o transfinitně rekurzívní konstrukci tříd Fx.
5.5. Izotonní zobrazení a izomorflsmy
5.10. Definice. Zobrazení / : X —>Y mezi uspořádanými třídami se nazývá izotonní, jestliže platí implikace a <b => f (a) < f(b) pro libovolná a, b G X.
Zobrazení / : X —> Y mezi uspořádanými třídami se nazývá ostře izotonní, jestliže platí implikace a < b => f (a) < f (b) pro libovolná a, b G X.
Příklad. Identické zobrazení idx ■ X —> X je izotonní i ostře izotonní při jakémkoliv uspořádání na X. Konstantní zobrazení X —> 1 (všichni na jednoho) je izotonní, ale nikoliv ostře izotonní, má-li X více než jeden prvek.
Cvičení.    Nechť je injektivní zobrazení izotonní. Ukažte, že je potom ostře izotonní.
40
logika a teorie množin
Je-li bijektivní zobrazení izotonní, neznamená to ještě, že i inverzní zobrazení je izotonní. Nejjednodušším protipříkladem je zobrazení dvouprvkové množiny sestáváající ze dvou nesrovnatelných prvků na dvouprvkový řetězec.
5.11. Definice. Bijektivní zobrazení / : X —> Y mezi uspořádanými třídami se nazývá izomorfismus, jsou-li / i /_1 izotonní. Říkáme, že uspořádané třídy X,Y jsou izomorfní, pokud mezi nimi existuje izomorfismus. Zapisujeme X = Y.
Cvičení.    Každý izomorfismus X —> Y je ostře izotonní zobrazení.
5.12. Tvrzení. Každé bijektivní izotonní zobrazeníX —> Y, kde třída X je řetězec, je izomorfismus.
Důkaz. Nechť f (a) < /(&). Protože X je úplně uspořádaná, platí a < b nebo a = b nebo b < a. Druhá možnost odporuje injektivitě, třetí odporuje izotónnosti a zbývá jen první, tedy a < b.
6. Ordinální čísla
O izomorfních uspořádaných množinách říkáme, že mají stejný ordinální typ. Ordinální čísla můžeme definovat jako ordinální typy dobře uspořádaných množin. Znamená to, že dvě ordinální čísla jsou si rovna, právě když jsou ordinálními typy izomorfních dobře uspořádaných množin. Pro ordinální typy zavedeme zvláštní symboly. Podobným způsobem jsme zavedli kardinální čísla, jen místo bijekcí mezi množinami rozhodují izomorfismy dobře uspořádaných množin.
Izomorfismus uspořádaných množin je bijekce, a proto mají izomorfní uspořádané množiny stejnou mohutnost. Odtud plyne, že každé ordinální číslo má určitou mohutnost, přičemž může existovat více různých ordinálních čísel stejné mohutnosti.
Podobně jako u mohutností taková definice neumožňuje utvořit třídu ordinálních čísel. To nám dovolí až von Neumannova definice ordinálních čísel čili ordinálů, kterou uvedeme později. Není tak názorná jako definice pomocí ordinálních typů.
Příklady. 1. Každé přirozené číslo n označuje rovněž ordinální typ řetězce o n prvcích (již víme, že je dobře uspořádaný). Jeho diagram sestává z n bodů spojených úsečkami, např. 1,2,3 mají po řadě diagramy
o ,      o—o ,      o—o—o .
2. Symbolem uj se označuje ordinální typ množiny všech přirozených čísel uspořádaných podle
velikosti (rovněž dobře uspořádaná množina). Výše jsme uvedli její diagram o—o—o—o--• •. Jinou
názornou ilustrací čísla uj je nekonečné sloupořadí
lllllt
(nekonečná řada skoupů táhnoucích se k obzoru).
6.1. Aritmetika ordinálních čísel
Podobně jako kardinální čísla, lze i ordinální čísla sečítat, násobit a umocňovat. Operace sčítání a násobení definujeme podobně jako stejnojmenné operace s kardinálními čísly, pouze je potřeba zařídit, aby disjunktní sjednocení a součiny dobře uspořádaných množin byly dobře uspořádané množiny. (Podobný postup není možný v případě umocňování.)
Upozorněme též, že operace s ordinálními čísly nejsou komutativní.
41
logika a teorie množin
6.2. Sčítání ordinálních čísel
6.1. Definice. Buďte A, B dvě dobře uspořádané množiny. Množina ({0} x A) U ({1} x B) s uspořádáním daným formulí
(i, a) < (j,b) i<jV(i = jAa< b)
se nazývá disjunktní sjednocení dobře uspořádaných množin nebo také součet dobře uspořádaných množin A, B a značí se AU B nebo A + B.
Slovy: Prvky disjunktního sjednocení uspořádáme
1. podle prvních složek, přičemž 0 < 1;
2. v případě rovnosti podle druhých složek, přičemž použijeme uspořádání z té množiny, kde se oba prvky nacházejí.
Nebo jinak: Prvky původem z A předcházejí všechny prvky původem z B, kdežto dvojice prvků původem z jedné a téže množiny jsou uspořádány stejně jako ve "své" množině. Schematicky
A
B
6.2. Definice. Buďte a, (3 po řadě ordinální typy dobře uspořádaných množin A, B. Součet a + (3 definujeme jako ordinální typ disjunktního sjednocení AU B.
Definice je korektní, protože jsou-li A = A', B = B' izomorfní dobře uspořádané množiny, pak jsou i A U B, A' U B' izomorfní dobře uspořádané množiny. Ohledně izomorfismu se důkaz vede podobně jako ohledně ekvivakence množin (jsou-li f,g izomorfismy, je i / U g izomorfismus). Ohledně dobrého uspořádání je důkaz proveden níže v zobecnění na systémy.
Příklad.    Kolik je 1 + 2? Máme
o U o—o = | o |—| o—o | = o—o—o,
a tedy 1 + 2 = 3.
Poznámka. Ordinální čísla jsou spíš obdobou řadových číslovek než číslovek základních, přesto si dovolíme se na ně ptát otázkou "kolik?" spíše než otázkou "kolikátý?".
Příklad.    Kolik je 1 + lúI Máme
0 U O-O--• • = | O |-1 O-O-       • • • | = O-O-       • • • = uj
neboli
1 lllh lllk
(sloup a sloupořadí = sloupořadí). Tudíž, 1 + oj = oj. Podobně 2 + oj = oj, atd. Příklad.    Kolik je oj + 1? Máme
o—o--• • U o = | o—o— • • • |—| o | = o—o— • • • o.
neboli
lllk     l    lllh l
Vidíme, že u + 1 / u. Vskutku, v uje jediný prvek, 0, který nemá přechůdce, kdežto v oj + 1 jsou takové prvky dva. Podobně w+2/iij + l (proč?), atd.
42
logika a teorie množin
Příklad.    Kolik je co + co? Máme o—o--• • U o—o--• •
— | o—o— • • • I—I o—o--• • I
— o—o— • • • o—o--• •
neboli
lilu.  Ilk   lili, lilu,
(dvě nekonečná sloupořadí za sebou). Vidíme, že lú+lú je další ordinální číslo, různé od již sestrojených. Podobně uj + uj + 1,       uj + uj + uj jsou po řadě
lllklllkl lilu llhJlln.
další nová ordinální čísla.
Shora uvedené příklady ukazují, že na rozdíl od sčítání kardinálních čísel není sčítání or-dinálních čísel komutativní. Například 1 + uj = uj^ío + 1. Nicméně, sčítání ordinálních čísel je asociativní (ověřte jako cvičení).
Vyplatí se rovnou zavést i zobecnění na systémy. Dobře uspořádaný systém dobře uspořádaných množin je systém {Ai}iei, kde jednotliví sčítanci Ai i indexová množina / jsou dobře uspořádáni. Disjunktní sjednocení
uspořádáme podle předpisu
(i, Cli) < (j, CLj) Í < j V (i = j A Cli < Aj)
(zde a,i G Ai a a j G Aj).
Opět platí, že prvky disjunktního sjednocení uspořádáváme
1. podle prvních složek, přičemž přebíráme uspořádání z /;
2. v případě rovnosti podle druhých složek, přičemž použijeme uspořádání z té množiny, kde se oba prvky nacházejí.
Schematicky
-<4íi		Ai2		Ai3
přičemž jednotlivé "bloky" jsou uspořádány stejně jako jejich indexy v množině /.
Je zřejmé, že dříve zavedené disjunktní sjednocení dvou množin je speciální případ, kdy indexovou množinou je řetězec 0—1. Zobecnění na n-prvkový řetězec je zřejmé — obdržíme součet n množin.
6.3. Tvrzení. Disjunktní sjednocení dobře uspořádaného systému dobře uspořádaných množin je dobře uspořádaná množina.
Důkaz. Buď B neprázdná podmnožina v disjunktním sjednocení |_|ieJ Ai. Nechť Ig je množina všech indexů i takových, že B n Ai ^ 0. Zřejmě je Ib ^ 0 neprázdná (proč?) podmnožina v dobře uspořádané množině /, takže má nejmenší prvek, což je podle definice nejmenší index i takový, že BnAi ^0. Pak je ovšem BnAi neprázdná podmnožina dobře uspořádané množiny Ai, takže má nejmenší prvek, který je současně nejmenším prvkem podmnožiny B (proč?).
6.4. Definice. Buďte olí ordinální typy dobře uspořádaných množin Ai, i G /, kde I je dobře uspořádaná. Součet ~Ž2Í<EI ai definujeme jako ordinální typ disjunktního sjednocení |_|ieJ Ai.
43
logika a teorie množin
Příklad. Máme
jak je snadno vidět z diagramu
| o |—| o—o |—| o—o—o |--• •
6.3. Násobení ordinálních čísel
Jako další operaci zavedeme násobení, přičemž se ukáže, že v případě dvou operandů jde o speciální případ sčítání systému ordinálních čísel.
6.5. Definice. Buďte A, B dvě dobře uspořádané množiny. Množina A x B s uspořádáním daným formulí
(a,b) < (a',b')
a < a' V (a = a' A b < b')
se nazývá lexikografický součin dobře uspořádaných množin nebo jen součin dobře uspořádaných množin A, B a značí se A x B.
Slovy: Prvky součinu uspořádáme
1. podle prvních složek,
2. v případě rovnosti podle druhých složek.
Původ přívlastku "lexikografický" nalezneme ve slovníkovém uspořádání dvoupísmenných slov. Je to dobře patrné v níže uvedených příkladech.
Jinak: A krát B znamená, že prvky množiny A nahradíme kopiemi mnžiny B; v rámci jedné a téže kopie přebíráme uspořádání z B, zatímco mezi různými kopiemi přebíráme uspořádání z A. Schematicky
B		B		B
Z definic je patrné, že součin A x B není nic jiného, než disjunktní součet A x B = \_\B
A
systému sestávajícího z kopií množiny B, po jedné pro každý prvek z A, a proto je dobře uspořádaný.
Příklad.    Počítejme 3x3. Máme
r [0,0]   [0,1] [0,2h 3x3=   [1,0]    [1,1]    [1,2] \ {[2,0]    [2,1]    [2,2] J
s lexikografickým uspořádáním
[0,0] < [0,1] < [0,2] < [1,0] < [1,1] < [1,2] < [2,0] < [2,1] < [2,2].
Vidíme, že zároveň jde o disjunktní sjednocení
[0,0]—[0,1]—[0,2] - [1,0]—[1,1]—[1,2] - [2,0]—[2,1]—[2,2]
44
logika a teorie množin
Jelikož součin dvou dobře uspořádaných množin je speciálním případem součtu systému množin, je dobře uspořádán. Můžeme pak pro ordinální čísla a, (3, která jsou po řadě or-dinálními typy množin A, B, definovat součin a(3 = a x (3 jako ordinální typ množiny A x B. Cislo a se nazývá násobitel (multiplicator), čislo (3 násobenec (multiplicandus). Jelikož násobení není obecně komutativní, na pořadí záleží.
Pro zapamatování: Při zápisu "x" násobíme v pořadí "kolikrát co," to jest, a x (3 má význam "akrát /?."
Poznámka. Obvyklý je i zápis součinu v převráceném pořadí jako (i ■ a = a x (3, což znamená, že násobíme v pořadí "co kolikrát," to jest, a ■ (i má význam "a /3krát." Důvody pro převrácený zápis uvedeme v souvislosti s umocňováním níže.
Pro zachování historické pravdy uveďme, že G. Cantor původně zavedl součin ekvivalentní součinu "x" [v práci Ueber unendliche, lineare Punktmannichfaltigkeiten, Mathematische Annalen 21 (1883) 545-591 na str. 551], ale později přešel k převrácenému součinu.
Příklad.    Kolik je 2 x ui = |_|2 uil Dostáváme
což jew + iij neboli
llllli llk
(dvě nekonečná sloupořadí za sebou). Pro srovnání, ux2 = \_\^ 2 je
| o—o |—| o—o |—| o—o |--• •
čili
o-o-o-o-       • • • ,
což je uj. Vidíme, Že2xw/iti = iijx2. Příklad.    Kolik je ui x ui = [J^ uil Dostáváme
| o—o— • • • I—I o—o— • • • I—I o—o— • • • I--
čili
o—o— • • • o—o— • • • o—o—......
nebo názorněji
lili, ll„. i lili, ll., k.,......
(dvojitě nekonečné sloupořadí). Může se psát i jako mocnina uP.
Stejný výsledek dostaneme, když v Ik. nahradíme každý sloup celým sloupořadím. Všimněte si, že ui prvků nemá předchůdce.
Cvičení.    Kolik je 1 + uP"! Kolik je ui + u2?
Cvičení.    Ukažte, že každý prvek z u>2 je tvaru a\u> + ao, kde ai, ao jsou přirozená čísla. Návod: Viz předchozí obrázek.
45
logika a teorie množin
Příklad.    Dvojnásobek ordinálního čísla u>2 je 2u>2 = 2xuJ, což je
l l lllk    l lllllt  llil., lil, l l lili,,    lil!, ||„
(dvě nekonečné řady nekonečných sloupořadí). Všimněte si, že 2uj prvků nemá předchůdce. Podobně trojnásobek atd.
Příklad. Co je w3? Definujeme jej jako w-násobek ordinálního čísla u>2. Znázornit jej můžeme diagram
(trojitě nekonečné sloupořadí). Stejný výsledek dostaneme, když v uj2 nahradíme každý sloup sloupořadím, čili jako w2-násobek ordinálního čísla ui. Všimněte si, že u>2 prvků nemá předchůdce.
Cvičení.    Ukažte, že každý prvek z u3 je tvaru a^iJ2 + a\U) + ao, kde 02, ai, ao jsou přirozená čísla.
Příklad.    Analogicky u>4 je
(čtyřnásobně nekonečné sloupořadí). Stejný výsledek dostaneme, když v u> nahradíme každý sloup sloupořadím, čili jako w3-násobek ordinálního čísla ui. V tomto případě uŕ prvků nemá předchůdce.
Cvičení.    Zobrazte tento PDF soubor na monitoru a pozorujte obrázky při zvětšujícím se rozlišení.
Cvičení. Ukažte, že každý prvek z uj4 je tvaru a^uj3 + (I2U)2 + a\w + ao, kde 02, ai, ao jsou přirozená čísla.
Příklad. Libovolnému polynomu p = anxn + dn-ix11-1 + • • • + a\x + ao £ N [x] jedné neurčité x s koeficienty z N odpovídá ordinální číslo p(uj) = anuin +an-icún~1 + • • • + a\u> + ao, přičemž pro různé polynomy p, q jsou čísla p(uj) a q(ui) různá. Připomeňme však, že je nutno dodržet pořadí sčítanců (proč?).
Čísla p(uj) vyčerpávají ordinální čísla, která lze vyjádřit pomocí konečných součtů a součinů přirozených čísel a čísla uj.
Na rozdíl od nekonečných součtů, nekonečné součiny ani nekonečné mocniny nenesou přirozené dobré uspořádání. Například 2H°, množina spočetných posloupností čísel 0,1, sice připouští lexikografické uspořádání, ale snadno najdeme nekonečnou klesající posloupnost
[1,0,0,0,0,...]     >     [0,1,0,0,0,...]     >     [0,0,1,0,0,...], ...
Nekonečné součiny a mocniny je nutno konstruovat jiným způsobem.
6.6. Definice. Nechť a, ß jsou ordinální čísla. Položme
aß=\J ak.
keß
Vysvětlení: Jde o ordinální typ prostého, nikoliv disjunktního, sjednocení množin ak. Konečné mocniny ak jsou stejně jako předtím konečné součiny
46
logika a teorie množin
a jsou vloženy jeden do druhého, ak C ak+1, prostřednictvím zobrazení [ai, a-i,..., \—> [0, cti, a,2, ■ ■ ■, fifc], takže prvky z ak předcházejí ostatním v ak+1 (tvoří tam počátek; obecně počátky zavedeme v příštím oddílu). Potom ak C ak+2 prostřednictvím zobrazení [cii, a,2, ■ ■ ■, a-k] 1—* [0, 0, cti, a,2, ■ ■ ■, Ok], atd.
Příklad. Počítejme
2^ = y 2fe
Zde 2° je jednoprvková množina 1 = {0}, vložená do 21 = {0,1} jako prvek [0,1]. Přitom 21 = {0,1} je vložená do 22 jako prvky [0, 0], [0,1], zatímco 22 je vložená do 23 jako prvky [0, 0,0], [0,0,1], [0,1, 0], [0,1,1], atd. Vidíme, že sjednocení [Jk€^ 2 lze ztotožnit s množinou všech posloupností . .. , 02, 0,2, o-o nekonečných směrem doleva, kde a\ je 0 nebo 1, ale jen konečně mnoho prvků a% je nenulových. Uspořádání zůstává lexikografické, čili rozhodujs se podle nejlevějšího nenulového a%. Dostáváme
(...,0,0,0) < (...,0,0,1) < (...,0,1,0) < (...,0,1,1) <•••,
což je izomorfní řetězci uj, čili
2" = LU.
Poznámka. Všimněte si, že oproti kardinálnímu číslu 2H° je ordinální číslo 2" spočetné.
Příklad. Počítejme 1" = [Jk€LJ lfe- Jelikož 1 C 2, můžeme použít postup z předchozího příkladu, kde se omezíme jen na posloupnosti sestavené z prvků z 1. Tam je ovšem jediný prvek 0 a proto 1" obsahuje jediný prvek, a sice nulovou posloupnost . .. , 0, 0, 0. Tudíž,
1" = 1.
Příklad. Počítejme u". Opět můžeme použít postup z předchozího příkladu, ale tentokrát budou posloupnosti ...,02,02,00 sestaveny ze všech přirozených čísel, přičemž vše ostatní zůstane stejné, včetně uspořádání. Dostáváme
(...,0,0,0,0) < (...,0,0,0,1) < (...,0,0,0,2) < •••
< (...,0,0,1,0) < (...,0,0,1,1) < (...,0,0,1,2) <•••
< (...,0,0,2,0) < (...,0,0,2,1) < (...,0,0,2,2) <• • •
< • • •
< (...,0,1,2,0) < (...,0,1,2,1) < (...,0,1,2,2) <•••,
což není žádné z dosud zkonstruovaných ordinálních čísel, protože všechna doposud zkonstruovaná ordinální čísla jsou tvaru p{ui) = cnujn + cn-iujn~1 + • • • + c\ui + co a odpovídají posloupnostem an,.. ., 0,2, 0,2, ao konečné délky. Vidíme, že u" je zcela nové ordinální číslo.
Diagram množiny u" obdržíme, když v množině tu nahradíme každý sloup množinou uj (vznikne uP), poté opět nahradíme každý sloup množinou uj (vznikne ui3), a tak dále do nekonečna. Vznikne tak sobě podobná množina, jejíž každá část je podobná celku, čili fraktál.
Příklad. Podle podobného návodu se sestrojí číslo u" , jen použité posloupnosti budou indexovány prvky z 1/. Analogicky 1/    , atd.
47
logika a teorie množin
Poznámka. Ordinální čísla oj" , oj" , oj"   , ■ ■ ■, jsou opět spočetná.
Zde naši exkurzi do zoo ordinálních čísel ukončíme. Vidíme, že svět ordinálních čísel je mnohem rozmanitější než svět kardinálních čísel. Zdůrazněme, že všechna zatím zkonstruovaná ordinální čísla mají spočetnou mohutnost.
Z obvyklých zákonů aritmetiky platí pro operace s ordinálními čísly jen některé. Již jsme viděli, že obecně naplatí komutativní zákon ani pro sčítání, ani pro násobení.
6.7. Tvrzení. Budie a, (3, 7 libovolná ordinální čísla. Pak
Q + a = a = a + Q,
(a + (3) + 7 = a + ((3 + 7),
lxa = tt = axl,
(a x (3) x 7 = a x ((3 x 7),
{a + (3) X7 = aX7 + aX7,
Oxa = 0 = axO,
a° = l,
a1 = a.
afJ+l = al x a/3;
(a^yi = a->xl3.
Všimněte si změny pořadí (3 a 7 v posledních dvou identitách.
Poznámka. Použijeme-li převrácený zápis součinu, který jsem označili "• ", nenastane změna pořadí exponentů v posledních dvou identitách,
zato bude platit jiný distributivní zákon, a sice
a ■ (0 + 7) = Oí ■ (3 + OL ■ 7.
Cvičení.    Ukažte, že a x (Ji + 7) nemusí být rovno a x (3 + a x j. Z distributivních zákonů mezi násobením a sčítáním tak platí jen jeden. Návod: Volte a = 2, (i = oj, 7 = 1.
Cvičení.    Ukažte, že (a x /3)7 nemusí být rovno ani a1 x fP, ani fP x a1. Návod: Volte a = oj, (i = 7 = 2.
6.4. Uspořádání ordinálních čísel
6.8. Definice. Nechť A je řetězec. Podmnožina I C Ase nazývá počátek v A, jestliže s každým prvkem a£í obsahuje i všechny prvky b G A takové, že b < a.
Počátek / se nazývá vlastní, když I ^ A.
Příklad. Prázdná množina je vlastním počátkem libovolného řetězce. Každý řetězec je svým vlastním počátkem.
48
logika a teorie množin
Příklad. Otevřené a uzavřené intervaly Prázdná množina je vlastním počátkem libovolného řetězce. Každý řetězec je svým vlastním počátkem.
Cvičení.    Počátek K C J počátku J C I je počátek K C I. Dokažte.
Cvičení.    Jsou-li /, ľ dva počátky v řetězci A, pak buď I C. ľ nebo ľ C I. Dokažte.
Návod: Připusťme naopak, že I \I' a I' \ I jsou neprázdné a obsahují po řadě prvky i a i'. Jelikož A je řetězec, jsou i a i' srovnatelné...
Cvičení. 1. Je-li {/jjjej systém počátků v řetězci A, pak je sjednocení Ujej Ij také počátek v A. Dokažte.
2. Je-li {/jjjej neprázdny systém počátků v řetězci A, pak je průnik Ij také počátek v A.
Dokažte.
Nadále bude A dobře uspořádaná množina. Pro libovolný prvek a € A zaveďme Aa = {x e A I x < a}. Množina Aa je zřejmě vlastní počátek v A.
Příklad.    Vlastní počátky v uj jsou právě všechna konečná ordinální čísla.
6.9. Tvrzení. Buďte I c A vlastní počátek. Pak existuje prvek a € A takový, že
Důkaz. Jestliže / je vlastní počátek, pak je rozdíl A\I neprázdný a obsahuje nejmenší prvek. Označme jej a. Pak / = Aa.
6.10. Tvrzení. Buďte A, B dobře uspořádané množiny. Pak nastane právě jedna ze tří možností:
1. A je izomorfní s B;
2. A je izomorfní s některým vlastním počátkem v B;
3. některý vlastní počátek v A je izomorfní s B.
Naivní důkaz by mohl spočívat v konstrukci izomorfizmu <f> po jednotlivých krocích, kdy v každém kroku přiřadíme nejmenšímu prvku, který ještě nemá obraz, nejmenší prvek, který ještě nemá vzor. Výsledkem bude jeden z případů věty v závislosti na tom, zda se vyčerpají obě množiny současně nebo jedna z nich dříve. Nemáme však žádné axiomy, které by nám dovolily provádět konstrukce v nekonečně mnoha krocích.
Důkaz. Uvažujme o množině M všech trojic (/, J, <f>), kde / je počátek v A a J je počátek v B & <f> : I ^ J je izomorfismus, který splňuje
(f)Aa = ž?0(o).
Prvky a € A, které leží v některém z počátků /, tj. a € |J /, jakož i prvky b G B, které leží v některém z počátků J, tj. b G |J J, nazveme vypořádané. Je zřejmé, že vypořádané prvky z A tvoří počátek v A a vypořádané prvky z B tvoří počátek v B (je-li a vypořádaný a a' < a, je a' vypořádaný ohraničením izomorfizmu na prvky < a').
Jeden a týž prvek a může ležet ve vícero počátcích /, ale vždy s touž přiřazenou hodnotou 4>{a), nazávislou na /, jak plyne transfmitní indukcí s použitím podmínky 4>Aa = B^^ (ověřte).
49
logika a teorie množin
Jsou-li všechny prvky z A nebo z B vypořádané, pak jsme hotovi a nastane jeden z případů věty v závislosti na tom, zda vypořádané prvky vyčerpají obě množiny nebo jen jednu z nich. Jinak označíme a nejmenší nevypořádaný prvek z A ab nejmenší nevypořádaný prvek z B. To znamená, že prvky z Aa i z B^ jsou vypořádané, a existuje <f> : Aa —> B^, ležící v M. Definujme A = {a} U Aa, B = {b} U Bi, a čj) : A —> B předpisem 4>\Aa = <ť a 4>{a) = Zjišťujeme, že (A, B£ M a a,b jsou rovněž vypořádané, což je spor.
6.11. Definice. Buďte a, ß ordinální čísla, která jsou po řadě ordinálními typy dobře uspořádaných množin A, B. Definujme uspořádání mezi a, ß tak, že možnosti
a = ß,    a < ß,    a > ß
nastávají po řadě v případech
1. A je izomorfní s B;
2. A je izomorfní s některým vlastním počátkem v B;
3. některý vlastní počátek v A je izomorfní s B. z předchozí věty,
Ukažme, že definice skutečně zavádí uspořádáním které je navíc úplné. Reflexivita a tranz-itivita jsou zřejmé, z věty plyne úplnost (že vždy nastane alespoň jedna z možností a = ß, a < ß, a > ß), ale antisymetrie pak plyne z toho, že nemohou současně nastat dvě různé možnosti.
7. Zermelova věta a její důsledky
Zermelova věta praví, že každou množinu lze dobře uspořádat. Jde o velmi důležitou větu, jejímž důsledkem je, že na každé množině lze uplatnit transfmitní indukci a s její pomiocí dokazovat významná tvrzení.
7.1. Zermelova věta. Na každé množině existuje dobré uspořádání.
Ernst Zermelo (1871-1953) dokázal tuto větu jako první v práci E. Zermelo, Beweis, daß jede Menge wohlgeordnet werden kann, Math. Annalen 59 (1904) 514-516.
Je známo několik důkazů, které všechny používají axiom výběru. Nevyhnutelnost jeho použití plyne z toho, že axiom výběru je sám důsledkem Zermelovy věty. Dobré uspořádání totiž umožňuje zkonstruovat výběrové zobrazení tak, že se z každé podmnožiny vybere nejmenší prvek.
0 důkazech. Buď A libovolná množina. Původní Zermelův důkaz spočívá v tom, že se aplikací axiomu výběru z každé neprízdné podmnožiny B € 2A \ {0} vybere po jednom prvku. Poté se indukcí konstruuje uspořádání na A, přičemž indukční krok spočívá v tom, že se k množině P všech již vyřízených prvků připojí prvek vybraný z doplňku A \ P a prohlásí za větší než všechny prvky z P. Přitom je však nutno zařídit, že indukční krok probíhal na nějaké dobře uspořádané množině, což je hlavní komplikace důkazu.
Jednodušší jsou důkazy používající ordinály (viz níže), protože třída všech ordinálů O je dobře uspořádaná i bez axiomu výběru a transfmitní rekurzí lze konstruovat injektivní zobrazení z libovolné množiny do O. Ačkoliv ordinály umožňují významná zjednodušení důkazů, v tomto textu je odsuneme až na samotný konec výkladu. Upřednostníme některé důsledky Zermelovy věty, které jsou významné
1 pro aplikovatelnou matematiku a nejen pro řešení vnitřních problémů teorie množin.
50
logika a teorie množin
Cvičení.    Najděte dobré uspořádání množiny Z celých čísel. Nápověda: Ordinální typ uj + uj.
Cvičení.    Najděte dobré uspořádání množiny Q racionálních čísel. Nápověda: Ordinální typ uj x uj.
7.2. Poznámka. Přestože podle Zermelovy věty existuje dobré uspořádání množiny reálných čísel, není známa žádná formule, která by takové uspořádání zadávala.
Důvod je patrný i z torza důkazu Zermelovy věty, které jsme uvedli. Není totiž známa ani žádná formule, která by zadávala výběrové zobrazení pR \ {0} —> R, tj. umožňovala vybrat po jednom prvku z každé neprázdné množiny reálných čísel.
7.1. Hausdorffův princip maximality
V následujících odstavcích popíšeme některé další důsledky axiomu výběru, které se často používají v různých oblastech matematiky mimo teorii množin.
7.3. Haussdorfův princip. Každý řetězec v uspořádané množině lze rozšířit na maximální řetězec.
Maximálním řetězcem se rozumí řetězec, ke kterému nelze přidat žádný další prvek (to jest, po přidání libovolného prvku přestane být řetězcem). Při důkazu použijeme Zermelovu větu.
Důkaz. Buď (A, <) libovolná uspořádaná množina, B její podřetězec. Princip důkazu spočívá v tom, že k řetězci přidáváme další prvky takové, že výsledek zůstává řetězcem, přičemž uplatníme transfinitní rekurzi. Podle Zermelovy věty na množině A existuje i dobré uspořádání, které označíme ^. Transfinitní rekurzí nad dobrým uspořádáním ^ definujeme zobrazení <p : A —> pA tak, aby
je je maximální řetězec, protože kdyby bylo možné k němu přidat další prvek, během transfinitní rekuze by k tomu došlo.
7.2. Zornovo lemma
V různých partiích matematiky se běžně provádějí konstrukce maximálních prvků pomocí Zornova lemmatu. Jde o obvyklý název výsledku, který v roce 1935 publikoval německý matematik Max Zorn a v nepříliš odlišné podobě v roce 1922 polský matematik Kazimierz Kuratowski. Proto se někdy nazývá Kuratowského-Zornovo lemma.
7.4. Zornovo lemma. Nechť A je uspořádaná množina taková, že každý řetězec v A má horní závoru. Pak ke každému prvku a € A existuje prvek b € A, který je maximálním prvkem v A a a < b.
Zornovo lemma je snadným důsledkem Hausdorffova principu.
Pak
b u u m
51
logika a teorie množin
Důkaz. Podle Hausdorffova principu lze jednoprvkový řetězec {a} rozšířit na maximálním řetězec /, který jej obsahuje. Podle předpokladu má / horní závoru b. Prvek b je hledaným prvkem. Zaprvé platí a <b, protože a € / a b je horní závora řetězce /. Zadruhé je b maximální prvek v A, protože kdyby nebyl, existoval by v A prvek c > b. Prvek c by byl ostře větší než všechny prvky z /, načež by / U {c} byl řetězec v A obsahující /, v rozporu s maximalitou /.
Zornovo lemma se obvykle aplikuje v situacích, kdy A je systém nějakých množin (např. algebraických struktur), pro něž platí, že sjednocení řetězce do sebe vložených struktur je opět prvkem systému (a v této podobě lemma dokázal K. Kuratowski v r. 1922). Dá se tak například ukázat, že každou vlastní podalgebru lze vložit do maximální vlastní podalgebry. Analogické tvrzení se dokazuje pro vlastní ideály okruhů apod.
7.3. Srovnatelnost kardinálních čísel
Z Zermelovy věty snadno plyne, že libovolná dvě kardinální čísla a, b jsou srovnatelná. Množiny A, B, které mají po řadě mohutnosti a, b, můžeme podle Zermelovy věty dobře uspořádat, a potom podle věty 6.10 existuje injektivní zobrazení A —> B nebo B —> A.
8. Ordinály
V předchozích odstavcích jsme se seznámili s ordinálními čísly v podobě tříd izomorfních dobře uspořádaných množin, což odpovídá původnímu Cantorovu pohledu, ale nelze pak zavést třídu všech ordinálních čísel. Tento nedostatek lze odstranit zavedením ordinálů, speciálních dobře uspořádaných množin takových, že každá dobře uspořádaná množina je izomorfní s právě jedním ordinálem. Existuje vícero možností a verzí. Společnou vlastností je, že ordinály jsou (podobně jako von Neumannova přirozená čísla) dobře uspořádané množiny všech menších ordinálů.
Pro každé ordinální číslo cr totiž platí, že je izomorfní se systémem všech vlastních počátků aa, a € cr, uspořádaným inkluzí, protože
a < b    <S>     aa C at,.
Definici ordinálů obdržíme, pokud v předchozím tvrzení "izomorfnf' zaměníme za "identický".
8.1. Definice (E. Zermelo, J. von Neumann). Dobře uspořádaná množina cr se nazývá ordinál, je-li každý prvek z € cr identický s počátkem az tj.
z = az = {( € cr | C < z}. (1)
Třídu všech ordinálů označíme O.
Příklad.    0 = 0 je ordinál, protože nemá žádné prvky.
Příklad.    1 = {0} je ordinál, protože jediným prvkem je 0 a pro něj platí lo = 0 = 0.
Příklad.    2 = {0,1} s uspořádáním 0 < 1 je ordinál, protože 2o = 0 = 0 a 2i = {0} = 1.
Příklad. Dobře uspořádaná množina oj je ordinál, neboť pro každé von Neumannovo přirozené číslo n platí ojn = {0,1, 2,.. . , n — 1} = n.
52
logika a teorie množin
8.2. Tvrzení. Každý prvek ordinálu je zase ordinál.
Důkaz. Nechť je a je ordinál a r € a. Pak r = aT je počátek v a, čili r je dobře uspořádaná množina. Současně je každý prvek ( £ t roven počátku a q = tq (protože ( < r). Tudíž, r je ordinál.
Ordinály lze snadno uspořádat.
8.3. Definice. Řekneme, že ordinál a je ostře menší než ordinál r a zapoisujeme a < r, jestliže a je počátkem v r.
Všechna následující tvrzení uvedeme bez důkazu. Není to tím, že by důkazy byly dlouhé, ale semestr je krátký.
8.4. Tvrzení. Pro každé dva ordinály platí buď a < r nebo a = r nebo a > r.
8.5. Tvrzení. Třída O všech ordinálů je vlastní třída.
Důkaz tvrzení je znám jako Burali-Fortiho paradox. Burali-Forti (1861-1931) jej v dobách naivní teorie množin odvodil z předpokladu, že ordinální čísla tvoří množinu.
8.6. Tvrzení. Třída O všech ordinálů je dobře uspořádaná.
Uvedené tvrzení nám umožňuje provádět transfinitní indukci na ordinálech.
8.7. Důsledek. Každá množina ordinálů je dobře uspořádaná.
8.8. Tvrzení. Každá dobře uspořádaná množina je izomorfní s právě jedním ordinálem.
8.9. Tvrzení. Je-li a ordinál, pak i a + {a} je ordinál a jeho ordinální typ je a + 1.
8.10. Důsledek. Všechna von Neumannova přirozená čísla jsou ordinály.
8.11. Tvrzení. Je-li {<Tí}1<ej systém ordinálů, pak IJiej ai Je také ordinál. Příklad.    Podle posledního tvrzení je uj = UneN n ordinál.
9. Třída všech kardinálních čísel
Výše jsme zavedli kardinální čísla prostřednictvím tříd ekvivalence. Třídy ekvivalence (kromě jednoprvkové třídy [0]^) se ovšem ukázaly být vlastními třídami, a proto z nich není možné sestavit třídu kardinálních čísel. Nyní ukážeme, jak v každé třídě vybrat po jednom reprezentantu tak, aby zmíněné potíže odpadly.
Podle Zermelovy věty lze každou množinu dobře uspořádat a podle tvrzení 8.8 potom existuje bijekce na některý ordinál. Tudíž, každá množina je v bijekci s některým ordinálem.
9.1. Definice. Mohutnost množiny X je nejmenší ordinál £ takový, že existuje bijekce mezi X a £. Zapisujeme £ = #X.
Ordinál £ se nazývá kardinální číslo, jestliže je nejmenším prvkem množiny ordinálů jedné a téže mohutnosti.
Příklad.    K0 = cu.
53
logika a teorie množin
9.2. Důsledek. Každá dvě kardinální čísla jsou srovnatelná. Třída všech kardinálních čísel je dobře uspořádaná.
Podle Cantorovy věty ke každému kardinálnímu číslu existuje větší. Protože je třída kardinálních čísel dobře uspořádaná, má každé kardinální číslo svého následovníka.
Pro každý ordinál a € O definujeme transfinitní rekurzí nekonečné kardinální číslo \Ka následujícím způsobem.
9.3. Definice. Jsou-li pro všechny ordinály r < a definována kardinální čísla \KT, definujeme KCT jako nejmenší kardinální číslo větší než všechna \KT.
Příklad. Nejmenší kardinální číslo větší než Ko je Ki. Nejmenší kardinální číslo větší než Ki je K2. Nejmenší kardinální číslo větší než všechna K„,nG N, je K^.
9.4. Tvrzení. Každé nekonečné kardinální číslo je rovno \Ka pro některý ordinál a.
9.5. Poznámka. Otázka, kterému alefu je rovno c, však nemá jednoznačnou odpověď. Evidentně, c > ^Oj ale odnikud neplyne rovnost c = ani žádná jiná rovnost c = NCT pro konkrétní a > 0 lze pouze některé možnosti vyloučit, napříjklad je známo, že c ^
Hypotéza kontinua je předpoklad, že = 2H° = c. Zobecněná hypotéza kontinua je předpoklad, že KCT+i = 2H<J. Je dokázáno, že hypotéza kontinua je tvrzení nezávislé na dosud uvedených axiomech.
9.1. Pohlcovací zákony
Dále lze dokázat tak zvané pohlcovací zákony aritmetiky kardinálních čísel. Platí pro všechna kardinální čísla a, b, z nichž alespoň jedno je nekonečné a znějí
a+b=axb= max(a, b).
Dokazuje se pro všechny alefy (kardinální čísla tvaru Ka) v podobě
+ N/3 = N„ x \i,0 = max(Na, N^),
načež se využije toho, že každá nekonečná mohutnost je některým alefem.
54