TEORIE MNOŽIN J. ROSICKÝ 1. Množiny Pojem množiny je základním pojmem matematiky. Množina je určena svými prvky, t.j., množinou rozumíme souhrn prvků. Teorii množin vybudoval německý matematik G. Cantor v roce 1872. Výše uvedené vymezení pojmu množiny není přesnou definicí. Vede také k rozporům nebot jsou "souhrny", které za množiny považovat nemůžeme. Později uvidíme, že nemůžeme vytvořit "množinu" všech množin. Ne-jjednodšší příklad takové zakázané "množiny" nalezl B. Russel v roce 1900. Je to souhrn M = {x\ ^ x} všech množin x, které neobsahují sebe jako prvek. Totiž, pokud by M byla množina, můžeme si položit otázku, zda M G M. Pokud ano, pak, podle definice M platí M ^ M. Pokud ne, pak, opět podle definice M, platí M G M. V obou případech dostáváme spor. Řešení problému definice pojmu množiny podává axiomatická teorie množin. My budeme pracovat v tzv. naivní teorii množin, t.j., na základě výše uvedené nepřesné "definice". Budeme však opatrní v jejím používání: ne všechny souhrny budeme považovat za množiny. Zároveň si naznačíme, jak vypadá axiomatická teorie množin. Základní (a vlastně jedinou) vlastností množin je, že mají prvky. Píšeme a E A, což znamená, že a je prvkem množiny A. Malá a velká písmena používáme pro názornost; ve skutečnosti v teorii množin není nic jiného než množiny, t.j., i a je množina. Fakt, že množina je určena svými prvky je vyjádřen následujícím axiomem (který je prvním axiomem axiomatické teorie množin): Axiom extensíonalíty: Dvě množiny jsou stejné, právě když mají stejné prvky. Pomocí predikátové logiky (v jazyce s jediným binárním relačním symbolem G, což je jazyk axiomatické teorie množin) se tento axiom zapíše následovně: (AI) (Wx,y)(x = y o (Vz)(z G x o z G y)). Máme-li množiny A, B, můžeme utvořit novou množinu {A, B}, která má za prvky právě A a B. Tento způsob tvorby množin se nazývá axiom dvojíce. Pomocí formule predikátové logiky se zapíše následovně: (A2) (Vx,y)(3z)(Vt)(t e z ^ t = x\I t = y). Late: Březen 17, 2020. 1 2 Pro libovolnou množinu A a libovolnou "množinovou vlastnost" iGi). Uspořádaná dvojice (a,b) se definuje jako množina (a, b) = {{a}, {a, b}}. Tato definice je v duchu teorie množin: vše je množina, tedy i uspořádaná dvojice. Snadno se ověří, že platí (a, b) = (c, d) a = c a b = d. Kartézský součin množin A, B nyní definujeme jako A x B = {(a,b)\a G A,b G B}. Za pomocí axiomů se zapíše následovně A x B = {(a, b) G V(V(A U B))\a eAAbeB}. Potřebujeme utvořit množinu všech nezáporných celých čísel ^ = {0,1,2,-- - ,n,---}. To umožuje axiom nekonečna. Jeho přesná formulace je následující (A7) (3x)(0 G x A (Vy)(y G x y U {y} G x)). Množiny x z axiomu nekonečna se nazývají induktivní Pak = (^{rryrr induktivní}. Tento průnik existuje nebot se můžeme omezit na podmnožiny dané induktivní množiny a těch je pouze množina. Dosud jsme se seznámili s následujícími axiomy teorie množin: axiom extension-ality, axiom dvojice, axiom vyčlenění, axiom sjednocení, axiom množiny podmnožin a axiom nekonečna. První udává, kdy jsou dvě množiny stejné, další popisují "povolené" způsoby tvorby množin. K plné Zermelo-Fraenkelově teorii množin (což je štandartní axiomatika teorie množin, označuje se ZF) nám chybí již jen dva dosti technické axiomy: axiom regularity a schéma axiomů nahrazení, kterým se budeme věnovat později. 4 Ideální teorie množin by kromě axiomu extensionality obsahovala pouze axiom říkající, že pro libovolnou množinovou vlastnost f{x) je {a\íp(a) platí} množina. Russelův paradox však ukazuje, že tato teorie je sporná. Axiomy Zermelo-Fraenkelovy teorie množin uvádjí povolené případy výše uvedeného "ideálního" axiomu. 2. Kardinální čísla Každé množině A přiřadíme symbol \A\ takový, že \A\ = \B\, právě když množiny A, B mají stejnou mohutnost. Symboly \A\ se nazývají kardinálni čísla. Kardinální číslo \A\ rovněž nazýváme mohutnost množiny A. Poněvadž "mít stejnou mohutnost" je relace ekvivalence, postup je korektní. Není však podán v termínech teorie množin nebot kardinální čísla nejsou definována jako množiny. Později naznačíme, jak lze kardinální čísla definovat v termínech teorie množin. Příklady 2.1. (1) Nezáporná celá čísla považujeme za kardinální čísla a sice za mohutnosti konečných množin. (2) Mohutnost spočetné množiny značíme K0. (3) Mohutnost množiny reálných čísel nazýváme mohutnost kontinua a značíme ji c. Položíme \A\ < \B\, jestliže existuje prosté zobrazení A —>• B. Relace < mezi kardinálními čísly je zřejmě reflexivní a tranzitivní. Ukážeme, že je uspořádání. Především si uvědomíme, že pokud A C B, pak \A\ < \B\ (nebo zobrazení inkluze A —> B je prosté). Věta 2.2 (Cantor-Bernsteinova věta). Z \A\ < \B\ a \B\ < \A\ plyne \A\ = \B\. Důkaz. Mějme prostá zobrazení f : A —> B & g : B —y A. Musíme ukázat, že pak existuje bijekce A —>• B. Uvažujme zobrazení h : V (A) —> V (A) definované vztahem h(X) = A-g(B-f(X)) Necht X,Y e V (A), X C Y. Pak postupně platí f (X) C f (Y), B-f (Y) C B-f (X), g (B - f (Y)) C g (B - f (X)) a h(X) C h(Y). Tedy h : V {A) -> V {B) je isotonní zobrazení (obě množiny V (A), V (B) jsou uspořádané množinovou inkluzí). Podle Tarského věty o pevném bodu existuje CCA tak, že C = A-g(B-f(C)). Definujme zobrazení t : A —^ B takové, že t (x) = f (x) pro x E C a t (x) = g^{x) pro x ^ C. Definice je korektní nebot pro x ^ C platí x G g {B — f {C)). Ukážeme, že t : A —^ B je bijekce. Předpokládejme, že pro x G C a y ^ C platí t (x) = t (y). Pak f {x) = g~ľ(y), takže g(f(x)) = y ^ C. Zároveň f {x) ^ B — f (C) (nebot x G C), takže g(f(x)) ^ 5 g(B — f (C)) a tedy g(f(x)) E C; spor. Tedy t je prosté zobrazení nebot obě zúžení t na C a A — C jsou prostá. Necht y E B, y t(A). Pak y ^ /(C), takže y E B - f (C) a tedy g (y) £ C. To však znamená, že y = t(g(y)), spor. Tedy t je zobrazení na. □ Poznámka 2.3. (1) Poněvadž zobrazení / : A —>• "P(A), /(a) = {a} je vždy prosté, pro libovolnou množinu A platí \A\ < \V(A)\. Z Cantorovy věty plyne, že vždy \A\ < \V(A)\. Odsud plyne, že neexistuje největší kardinální číslo. Věta 2.4. Kardinálni čísla netvoři množinu. Důkaz. Předpokládejme, že existuje množina J a množiny Ai, i E I tak, že \Ai\, i E I vyčerpává všechna kardinální čísla. Poněvadž Aj C (J Ai, platí \Ai\ < \ [J Ai\. íei íei Tedy | |J Ai\ je největší kardinální číslo, což odporuje 2.3. □ iei Z Cantorovy a Cantor-Bernsteinovy věty rovněž plyne, že neexistuje množina všech množin. Pro takovou množinu M by totiž platilo, že |"P(M)| < \M\ nebot libovolná podmnožina M je prvkem M. Tedy |"P(M)| = \M\, spor. Zatím nejsme schopni zjistit, zda uspořádání kardinálních čísel je lineární. Dosud známá kardinální čísla jsou 0 < 1 < • • • < K0 < c. Zřejmě K0 je minimální nekonečné kardinální číslo. Otázka, zda c je nej menší nespočetné kardinální číslo je nerozhodnutelná. Věta 2.5. c = \V(uj)\. Důkaz. Definujme zobrazení / : 2W —> IR desetinným rozvojem f(h) = 0,h(0)h(l)h(2)... kde h : uj —> 2. Poněvadž / je prosté zobrazení, víme, že c > Z konstrukce reálných čísel jako řezů ve spočetné množině Q víme, že c < Tedy c = □ Operace s kardinálními čísly: Nech a = \A\ a /3 = \B\, přičemž množiny A, B jaou v (1) disjunktní. Položme (1) a + f3 = \AU B\ (2) a ■ (5 = \A x B\ (3) a? = \AB\ Bute J, Ai,i E I množiny, přičemž Ai jsou navzájem disjunktní. (4) E^ = IIMI iei iei Definice je korektní nebot operace nezávisí na volbě množin A, B. Skutečně, jsou-li / : A —^ A' a g : B —^ B' bijekce, pak / U g : A U B A' U B' pro A, B a A', B' disjunktní 6 / x g : A x B -> A' x B' a h:AB^(Ä)B', h(u) = f-u-g-1 jsou bijekce. Operace +, • jsou asociativní, komutativní a distributivní, což plyne z vlastností množinových operací U, x. Navíc, z vlastností mocnin množin plyne, že platí (a . = cP • /37 = t/ • a1. Dále platí a• 5 prosté zobrazení, pak zobrazení / U ide '■ AU C B U C a / x -ieře :AxC->5xC jsou rovněž prostá. Tvrzení věty 2.4 lze přepsat ve tvaru c = 2K° Věta 2.6. N0 • K0 = K0; K0 + K0 = N0. Důkaz. Platí N0 + K0 = |N| + M = |Z| = K0 Podobně K0 • = plyne z toho, že Q je spočetná množina. □ Věta 2.7. Je-Zž S spočetná množina reálných čísel, pak \R — S\ = c. Důkaz. Máme \R x R\ = 2W • 2K° = 2Ko+K° = 2K°. Tedy místo R mižeme vzít množinu IR x IR. Buď tedy S C I x R spočetná množina. Existuje x G R tak, že S H (M x {x}) = 0. Tedy {x} x 1 C 1 - S, takže \R - S\ = c. □ Důsledek 2.8. Mohutnost množiny iracionálních čísel je c. Věta 2.9. Mohutnost množiny všech konečných posloupností přirozených čísel je K0. Důkaz. Buď P množin všech konečných posloupností přirozených čísel. Zřejmě < \P\- Pro důkaz opačné nerovnosti zapišme libovolné přirozené číslo a v dvojkové soustavě. Posloupnost aľ.. .an pak určuje racionální číslo 0, aľ2a22 ... an. Poněvadž různé posloupnosti zřejmě určují různá racionální čísla, platí \P\ < |Q| = K0. □ Důsledek 2.10. Mohutnost množiny konečných podmnožin spočetné množiny je K0. 7 Připomeme, že reálné číslo se nazývá algebraické, pokud je kořenem polynomu s celými koeficienty. Libovolné racionální číslo je zřejmě algebraické. Reálná čísla, která nejsou algebraická se nazývají transcendentní Transcendentní jsou například čísla 7T, e; důkaz je však obtížný. Ukážeme, že transcendentní čísla existují (a že jich je víc než algebraických). Věta 2.11. Množina A všech algebraických čísel je spočetná. Důkaz. Množina všech polynomů s celými koeficienty se označuje Z[rr]. Z 2.9. plyne, že to je spočetná množina, t.j., existuje bijekce / : uj —> 7L\x\. Definujme zobrazení g : A —>• uj x uj vztahem g (a) = (n,k), kde n je nejmenší číslo takové, že a je kořen polynomu f(n) a a je přitom k-tf reálný kořen tohoto polynomu v uspořádání podle velikosti. Zobrazení g je zřejmě prosté, takže |A| < N°. Poněvadž Q C A, A je spočetná množina. □ Důsledek 2.12. Množina všech transcendentních čísel má mohutnost kontinua. Důkaz plyne z 2.8 a 2.11. 3. Dobře uspořádané množiny Definice 3.1. Řekneme, že lineárně uspořádaná množina je dobře uspořádaná, jestliže libovolná její neprázdná podmnožina má nejmenší prvek. Přídavné jméno lineárně jsme mohli v definici vynechat nebo to plyne z existence nej menších prvků dvouprvkových podmnožin. Libovolná podmnožina dobře uspořádané množiny je zřejmě dobře uspořádaná. Příklad 3.2. (1) Libovolná konečná lineárně uspořádaná množina je dobře uspořádaná. uj je dobře uspořádaná. (2) ujop ,7L, Q a IR nejsou dobře uspořádané. Věta 3.3. Bud A dobře uspořádaná množina a f : A —>• A prosté izotonní zobrazení. Pak pro všechna a E A platí a < f (a). Důkaz. Buď X = {a G A\f(a) < a}. Pokud I / |, existuje nejmenší prvek clq G X. Platí /(ao) < ao? takže /(/(do)) < f (do)- Tedy /(ao) £ X, což je spor s f(a0) < oq. □ Předpoklad, že / je prosté je podstatný; pro konstantní zobrazení tvrzení neplatí. Definice 3.4. Podmnožina Z uspořádané množiny A se nazývá začátek, pokud x G Z, y < x implikuje y E Z. Začátek Z se nazývá vlastní, pokud Z ^ A. Věta 3.5. Dobře uspořádaná množina není isomorfní s žádným svým vlastním začátkem. Důkaz. Předpokládejme, že Z je vlastní začátek dobře uspořádané množiny A a / : A —^ Z isomorfismus. Existuje prvek a G A — Z. Poněvadž f {a) G Z musí platit f {a) < a, což je spor s větou 3.3. □ 8 Je-li A uspořádaná množina a a E A, pak položíme A(a) = {x E A\x < a} Zřejmě A(a) je vlastní začátek v A. V dobře uspořádané množině A je libovolný vlastní začátek Z tvaru A(a) pro nějaké a E A. Za a je třeba vzít nejmenší prvek množiny A — Z. Věta 3.6. Budte A, B dobře uspořádané množiny. Pak existuje nejvýše jeden isomorfismus A —>• B. Důkaz. Buďte f,g:A^-B isomorfismy. Předpokládejme, že / ^ g. Pak existuje a E A takové, že f (a) < g(a). Poněvadž A(a) = B(f(a)) a A(a) = B(g(a)) platí B(f(a)) = B(g(a)). Navíc B(f(a)) je začátek v B(g(a)). Totiž pro libovolné c < f (a) existuje d E A tak, že c = f {d). Zřejmě d < a, takže c E B(f(a)). Dostáváme spor s 3.5. □ Důsledek 3.7. Bud A dobře uspořádaná množina a f : A —^ A isomorfismus. Pak f = idA- Věta 3.8. Budte A, B dobře uspořádané množiny. Pak nastane pravé jedna z následujících možností: (1) A^B (2) A je isomorfní s vlastním začátkem B (3) B je isomorfní s vlastním začátkem A. Důkaz. Je-li jedna z množin A, B prázdná, tvrzení zřejmě platí. Předpokládejme, že obě množiny A, B jsou neprázdné. Položme A0 = {a E A\ existuje b E B s A(a) = B(b)} B0 = {b E B\ existuje a E A s B(b) = A(a)}. Poněvadž Aq obsahuje nejmenší prvek A a Bq obsahuje nejmenší prvek v B, množiny Aq, Bq jsou neprázdné. Navíc to zřejmě jsou začátky (Aq v A a Bq v B). Dokážeme, že Aq = Bq. Definujme zobrazení / : Aq —> Bq tak, že A(a) = B(f(a)). Z definice množin Aq,Bq a 3.5 plyne, že takové zobrazení existuje právě jedno. Navíc to je zřejmě isomorfismus. Ukážeme, že nemůže nastat situace, kdy A0 / Aa současně B0 ^ B. V tomto případě však existují a E A a b E B tak, že Aq = A(o) a Bq = B(b). Tedy a E Aq a, b E Bq, což není možné. Ověřili jsme, že vždy nastane jedna z možností (l)-(3) a zbývá ověřit, že tyto možnosti se navzájem vylučují. Nastanou-li však dvě možnosti současně, vznikne dobře uspořádaná množina isomorfní se svým vlastním začátkem, což odporuje ??. □ 9 Poznámka 3.9. Z 3.8 plyne, že pro dobře uspořádané množiny A, B nastane právě jedna z možností \A\ = \B\, \A\ < \B\, \B\ < \A\. Tedy kardinální čísla dobře uspořádaných množin jsou lineárně uspořádaná. Pokud by libovolná množina šla dobře uspořádat, kardinální čísla by byla lineárně uspořádaná. Uvidíme, že tomu tak je i naopak: pokud kardinální čísla jsou lineárně uspořádaná, pak libovolnou množinu lze dobře uspořádat. Zatím umíme dobře uspořádat každou konečnou i spočetnou množinu. Neumíme např. dobře uspořádat množinu IR. Uvidíme, že problém, zda libovolnou množinu lze dobře uspořádat, je na základě dosavadních axiomů ZF nerozhodnutelný. Význam dobře uspořádaných množin spočívá mimo jiné v tom, že poskytují prostředí pro rozšíření pojmu indukce. Věta 3.10 (transfinitní indukce). Bud A dobře uspořádaná množina. Nechi pro libovolný prvek a E A je dán výrok V (a). Předpokládejme, že pro libovolné a E A platí: (*) Je-li pravdivý výrok V(x) pro libovolné x < a, je pravdivý výrok V (a). Pak výrok V (a) je pravdivý pro všechna a E A. Důkaz. Necht B = {a G A\V(a) je nepravdivý}. Předpokládejme, že množina B je neprázdná. Bud a nejmenší prvek v B. Dostáváme spor s (*). □ Obvyklá matematická indukce je transfinitní indukce pro u. Z (*) plyne, že výrok V je pravdivý pro nejmenší prvek v A. Součin lineárně uspořádaných množin již nemusí být lineárně uspořádaný. V teorii dobře uspořádaných množin proto pracujeme s tzv. lexikografickým součinem. Definice 3.11. Lexikografický součin A ■ B dobře uspořádaných množin A, B je kartézský součin A x B vybavený uspořádáním (a, b) < (c, d) a < c nebo a = c,b < d. Věta 3.12. Budte A, B dobře uspořádané množiny. Pak A - B je dobře uspořádaná množina. Důkaz. Necht X C AxB je neprázdná podmnožina lexikografického součinu A-B. Bu a0 nejmenší prvek v p±(X) a b0 nejmenší prvek v P2(Pi1(a>o) Hl). Zřejmě (a0, &o) je nejmenší prvek v X. □ Lexikografický součin není obecně komutativní. Např., 2-waw-2 nejsou isomorfní. Totiž uj ■ 2 = u, zatímco 2 • u jsou dvě kopie u nad sebou. Věta 3.13. Pro libovolné uspořádané množiny A,B,C platí (A-B)-C^A-(B-C). Důkaz. V (A-B)-C platí 10 (a, b, c) < (a', b', d) ^ (a, b) < (a', b') nebo (a, b) = (a', b'),c< d <š=> a < a' nebo a = a',b < b' nebo a = a',b = b',c < d. Podobně, v A ■ (B ■ C)) platí (a, 6, c) < (a', 6', c') a < a' nebo a = a', (b, c) < (b', c') <š=> a < a' nebo a = a',b < b' nebo a = a',b = b',c < d. Součet (kardinální) disjunktních uspořádaných množin A, B můžeme definovat jako jejich sjednocení A U B spolu s uspořádáním, které na A, resp. B splývá se zadaným uspořádáním a libovolné prvky a E A, b E B jsou nesrovnatelné. Takový součet dvou lineárně uspořádaných množin není lineárně uspořádaný. V teorii dobře uspořádaných množin proto pracujeme s jiným (tzv. ordinálním) součtem. Definice 3.14. Součet A + B dvou disjunktních dobře uspořádaných množin definujeme jako jejich sjednocení A U B vybavené uspořádáním x G A,y G B. Součet dobře uspořádaných množin není komutativní. Např., uj + 1 není isomorfní s 1 + oj. Totiž, 1 + uj = u, zatímco oj + 1 není isomorfní s oj. Věta 3.15. Pro libovolné navzájem disjunktní dobře uspořádané množiny A,B,C □ (3) x a, c G Aj, a < c nebo (6) a £ Ai,c £ Aj,i < j nebo a = c, 6 < cř. Uspořádání v (^(A • 5) je dáno následovně: (a, b) < (c, cř) <í=>(a, b), (c, ď) G A • 5, (a, b) < (c, cř) nebo ^ (a, 6) G A • B, (c, d) G Aj ■ B, i < j. To však nastane právě když a, c £ Ai,a < c nebo (8) a = c,b < d nebo a £ Ai, b £ Aj, i < j. Tím je tvrzení dokázáno. □ Levý distributivní zákon neplatí: u • (1 + 1) = uj^uj + uj = uj-1+uj-1. 12 Věta 3.20. Bud I uspořádaná množina a Ai = A po dvou disjunktní uspořádané množiny. Pak platí ^2 Ai = I ■ A. iei Důkaz. Buďte ji : Ai —> A, i E / isomorfismy. Pak zobrazení / : |J Ai —> I x A iei dané předpisem f (a) = (i, f i (a)) pro a G Ai je bijekce. Pro a, b E [j Ai platí iei a < b v 2, Ai <=>a, b E A,h a < b nebo (9) iei a E Ai,b E Aj, i < j. To však nastane právě když (i, fi{a)) < (j, fj(b)) v I x A. □ 4. Ordinální čísla Každé dobře uspořádané množině A přiřadíme symbol A tak, že A = B, právě když A = B. Symboly A se nazývají ordinální čísla. Poněvadž relace "být isomorfní" je relací ekvivalence, postup je korektní. Není však veden v termínech teorie množin, což později opravíme. Definice 4.1. Ordinální číslo n-prvkové dobře uspořádané množiny označíme n. Ordinální číslo dobře uspořádané množiny u značíme u. Položíme A < B, pokud A je isomorfní se začátkem B. Relace < je zřejmě reflexivní a tranzitivní. Z věty 3.8 plyne, že se jedná o lineární uspořádání (na třídě všech ordinálních čísel). Právě uvedená formulace je korektní nebo < zřejmě nezávisí na volbě reprezentantů. Uspořádání ordinálních čísel uvedených v příkladu nahoře je 0 < 1 < .. .n < .. .lu Pro libovolné ordinální číslo a položíme ty(a;) = {/3\/3 < a je ordinální číslo} Například, W(0) = 0, W(n) = {0,..., n - 1} a W(u) = {0,1,..., n,... }. Věta 4.2. Množina W(a) je dobře uspořádaná pro libovolné ordinální číslo a a platí W{a) = a. Důkaz. Necht a = A. Položme f(x) = A(x) pro libovolné x E A. Zřejmě / : A —> W(a) je prosté zobrazení. Mějme /3 < a, j3 = B. Pak existuje x E A tak, že B = A(x). Tedy /3 = f{x), takže / je isomorfismus. □ Věta 4.3. Ordinální čísla jsou dobře uspořádaná relací <. 13 Důkaz. Buď Z / | množina ordinálních čísel. Uvažujme a E Z. Pak bu a je nejmenší prvek v Z nebo množina ty (a) H Z je neprázdná. Pak její nejmenší prvek (který existuje nebo a je ordinální číslo) je zřejmě nejmenší prvek v Z. □ Ordinální číslo a se nazývá limitní, pokud množina ty (a) nemá největší prvek. V opačném případě se nazývá izolované. Tedy ordinální číslo 0 je limitní. Operace s ordinálními čísly: Nech a = A a /3 = B, přičemž dobře uspořádané množiny A, B jsou v (1) disjunktní. Položme (1) a + (5 = A + B (2) a ■ (5 = ~B~A Definice je korektní nebo operace zřejmě nezávisí na volbě dobře uspořádaných množin A, B. Operace +, • jsou asociativní, což plyne z vět 3.13 a 3.15. Z věty 3.19 plyne platnost levého distributivního zákona qí-(/3 + 7) = qí-/3 + qí-7 Dále platí «+0=0+«=« a.o = o-« = o a ■ 1 = 1 • a = a a ■ 2 = a + a Operace +, • nejsou komutativní. Např. platí 1+uj = uj^uj+1 2-uj = uj^uj-2 = uj + uj Všimněme si faktu, že izolovaná ordinální čísla jsou právě ordinální čísla tvaru a + 1. 111:i I dobře uspořádaná množina, AÍ7 i E I, dobře uspořádané množiny a «j = A,i. Pak ordinální číslo ^2iej&i definujeme předpisem íei íei Definice zřejmě opět nezávisí na volbě dobře uspořádaných množin Ai. Z 3.19 a 3.20 plyne íei íei a = a ■ I iei Třídu všech ordinálních čísel označíme W. Symbol ty (a) je ve shodě s obecným označením A(x) pro začátek. Ve ty má nejen každá podmnožina, ale i každá podtřída Z C ty má nejmenší prvek (důkaz je stejný). 14 Věta 4.4. Bud M množina ordinálních čísel. Pak existuje ordinální číslo a takové, že j3 < a pro libovolné j3 G M. Důkaz. Pokud M = 0, pak a = 0. Má-li M největší prvek j3, pak a = j3 + 1. Pokud M nemá největší prvek, uvažujeme množinu A= u ^O3) Poněvadž A je dobře uspořádaná nmožina, pro a = A platí /3 < a pro všechna (5 G M. □ Poznámka 4.5. Z 4.4 plyne, že W není množina a neobsahuje největší prvek. Důsledek 4.6. Pro libovolnou množinu M ordinálních čísel existuje sup M ve W. Důkaz. Tvrzení je zřejmé, pokud M má největší prvek. Nech M nemá největší prvek. Bez ujmy na obecnosti můžeme předpokládat, že z < /?2 G M plyne fli G M. Ordinální číslo a z 4.4 patří do třídy W — M, která je proto neprázdná, takže obsahuje nejmenší prvek. Ten je zřejmě supM. □ Konečně, pro libovolná ordinální čísla a,/3 definujeme mocninu a13 následovně: a° = l a?+1 = a?-a a13 = sup{«7\7 < /3} pro 0 < /3 limitní. (Zde je použito 5.7) Definice je založena na větě 3.10, t.j. na transfinitní indukci. Později uvidíme, že mocnina ordinálních čísel má následující vlastnosti = afi -ď1 Nyní si můžeme udělat představu o začátku třídy W ordinálních čísel (v jejím uspořádání): 0,1,2,... ,n, ...,u),u) + l,...,u) + u) = u- 2,... ,u • n,.. .u ■ u = u2,... ,un,.. .u1^, n luy i, . . . , luy , . . . 60, . . . Přitom každé limitní ordinální číslo je vždy supremum všech menších ordinálních čísel. Totiž, vztahy lu = \J n uj + uj = \J uj + n n A. Pak existuje prosté izotonní zobrazení / : A —> B na vlastní začátek B. Složení g : A —^ A zobrazení / s inkluzí B —> A je prosté izotonní zobrazení. Pro a G B — f {A) platí g (a) < a. Dostáváme spor s 3.3. Lemma 5.2. Pro libovolná ordinální čísla a,ß,^y platí (1) a < ß 7 + a < 7 + ß (2) a < ß => a + 7 < ß + 7. Důkaz. (1) je zřejmé, (2) plyne z 5.1. □ Lemma 5.3. Pro libovolná ordinální čísla a,ß a pro libovolné 0 < 7 platí (1) a<ß^^-a<^-ß (2) a < ß =>■ a ■ 7 < ß ■ 7. Důkaz. (1) je zřejmé, (2) plyne z 5.1. □ Lemma 5.4. Pro libovolná ordinální čísla a < ß existuje právě jedno ordinální číslo 7 tak, že a + 7 = ß. Důkaz. Je zřejmý. □ Lemma 5.5. Pro libovolná ordinální čísla a a 0 < ß existují ordinální čísla 8 < a a p < ß tak, že a = ß ■ ô + p. 5. Ordinální aritmetika Lemma 5.1. Bud A dobře uspořádaná množina a B C A. Pak B < A. □ 16 Důkaz. Podle 5.3 (2) platí a = 1 • a < j3 ■ a. Pokud nastane rovnost, zvolíme ô = a a p = 0. Necht a sup(a • fy) nebot a ■ fy < a ■ supfy pro všechna i E I (podle 5.3 (1)). Je-li 7 = supfyi izolované ordinální číslo, pak existuje j E I tak že supfy = fy a tvrzení platí. Buď 7 limitní. Pak fy < supfy pro všechna j E I a tedy a ■ fy < a ■ supfy pro pro všechna j E I (podle 5.3 (1)). Předpokládejme, že a = sup(a ■ fy) < a ■ 7. Podle 5.5 existují ordinální čísla ô < a & p < a tak, že a = a ■ ô + p. Tedy, podle 5.2 (1) o = a ■ ô + p < a ■ ô + a = a ■ ô + a ■ 1 = a ■ (ô + 1). Platí ô < 7 nebot v opačném případě 7 < ô a tedy a ■ 7 < a ■ ô (podle 5.3), Odsud by plynulo a-ô■ a13 < ď< (3) 1 < a asup^ = supaPi. Důkaz. Důkaz provedeme transfinitní indukcí podle 7. Tvrzení platí pro 7 = 0. Předpokládejme, že platí pro všechna ô < 7. Je-li 7 = 5+1, pak podle indukčního předpokladu a 5.3 (1) platí cP = a5 ■ a < f35 ■ a < f35 ■ (5 = fy1. Je-li 7 limitní, pak cí1 = sup{«V < 7} < sup{/3 = oP'\ Je-li 7 limitní, pak (s použitím 5.9 (2)), (f/)7 = sup{(f/) 71 > • • • > 7fc tak, že a = u10 ■ rriQ + • • • + ulk ■ m^. Důkaz. Budeme postupovat transfinitní indukcí podle a. Pro a = 1 máme a = u°. Buď 1 < a a předpokládejme, že věta platí pro všechna /3 < a. Buď X = {7\w7 < a}. Z 5.8 (2) plyne, že X je množina. Podle 5.8 (3), wsuPx = sup{w7\7 eX} a. Pokud cj70 • mo = a, věta je dokázána. Necht uJO ■ rriQ < a. Pak a = uj10 ■ rriQ + /3 18 (podle 5.4. Platí /3 < uj10 nebo uj10 < j3 implikuje a = u10 ■ m0 + f3 > u 10 ■ m0 + u10 = u10 ■ (m0 + 1), což je spor s maximalitou rriQ. Podle indukčního předpokladu existují přirozená čísla k,rrii,... ,rrik a ordinální čísla 7i > • • • > 7fc tak že /3 = uj11 ■ ni\ + • • • + ulk ■ ni},. Z maximality 70 plyne že 7o > 7i- Tedy a = uj10 ■ rriQ + • • • + ujlk ■ nik ■ a důkaz je ukončen. □ Příklad 5.11. Jedná se o rozvoj ordinálního čísla 0 < a v mocninách uj . Lze ukázat, že přirozená čísla k,niQ,... ,nik a ordinální čísla 7o > 7i > • • • > 7fc jsou určena jednoznačně. 6. Axiom výběru Axiom výběru: Buď I množina a Ai, i G / neprázdné množiny. Pak množina LJ Ai iei je rovněž neprázdná. Axiom říká, že libovolná množina neprázdných množin {Ai\i G /} má tzv. výběrovou funkci, t.j. zobrazení f:I^\jA,t iei takové, že f (i) G Ai pro libovolné i E I. Axiom výběru se označuje AC. Zermelo-Fraenkelova teorie množin s axiomem výběru se označuje ZFC a je to v současné době "standardní" teorie množin. Příčinou zvláštního postavení axiomu výběru je jeho "nekonstruktivní" charakter. Zatímco všechny ostatní axiomy ZF přesně popisují, jakou množinu vytváří, AC pouze tvrdí, že určitá množina (t.j., výběrová funkce) existuje, aniž by řekl, jak vypadá. Výběrová funkce vždy existuje (bez AC), pokud množina I je konečná, např. I = {1,... ,n}. Stačí zvolit prvky a« G Ai pro i = 1,..., n a položit / = {(1, ai),..., (n, an)}. Tato výběrová funkce je vytvořena použitím axiomu dvojice. Takovou možnost již nemáme pro nekonečnou množinu I a to ani v případě, pokud množiny Ai jsou konečné nebo dokonce dvouprvkové. Princip dobrého uspořádáni: Libovolnou množinu lze dobře uspořádat. Tento princip má rovněž "nekonstruktivní" charakter nebot neříká, jak příslušné dobré uspořádání vypadá. Nahlédneme to např. na existenci dobrého uspořádání množiny IR reálných čísel. Ukážeme, že princip dobrého uspořádání je (v ZF) ekvivalentní s axiomem výběru. Věta 6.1. Princip dobrého uspořádáni implikuje axiom výběru. 19 Důkaz. Buď I množina a 0 ^ AÍ7 i E I. Podle principu dobrého uspořádání lze množinu LU iei dobře uspořádat. V tomto dobrém uspořádání, má libovolná množina A,i nej menší prvek <2j. Pak f (i) = clí definuje výběrovou funkci iei □ Je poučné si uvědomit, že důkaz nelze vést následovně: libovolná množina Aí lze dobře uspořádat, takže má nej menší prvek aÍ7 atd. Totiž existuje celá množina D i dobrých uspořádání množiny A4 a k výběru nějakého z nich pro všechna i E I používáme axiom výběru (pro množiny DÍ7 i E I). Ukážeme si další "skrytá" použití axiomu výběru. Tato použití dokumentují, že AC běžně užíváme. Příklad 6.2. Známé tvrzení matematické analýzy říká, že funkce / : IR —y IR je spojitá v bodě a, právě, když an —> a implikuje f(an) —> f (a) pro libovolnou posloupnost (an). Nutnost podmínky je zřejmá. Dostatečnost se dokazuje následovně. Necht / není spojitá v a. Pak existuje okolí V bodu f (a) takové, že pro libovolné 0 < n existuje an s vlastnostmi \an — a\ < ^, f(an) ^ V. Pak an —> a, ale neplatí f(an) —> f (a). Použitá posloupnost an je však výběrová funkce N (J {x\\x - a\ < -, f(x) Í V} Lze ukázat, že (bez určité formy) AC tvrzení neplatí, t.j., že "nemáme dost posloupností" . Příklad 6.3. Dokážeme, že sjednocení spočetné množiny spočetných množin je spočetná množina. Mějme spočetné množiny AÍ7 i E oj. Množiny A4 lze tedy zapsat posloupnostmi Aí = {dio, au,..., din,... } Uspořádáme-li množinu A = |J Aí po diagonálách A = {a00, a01, a10,...}, vidíme, že množina A je spočetná. Použití AC spočívá ve výběru uspořádání množin Aí do posloupností. Takových posloupností je vždy množina D i a na množiny D i musíme opět uplatnit AC. Princip maximality Buď A uspořádaná množina taková, že libovolný řetězec v A má horní závoru. Pak ke každému a E A existuje maximální prvek b E A tak, že a < b. Věta 6.4. Princip maximality implikuje princip dobrého uspořádáni. 20 Důkaz. Buď A množina. Uvažujme množinu D = {(B, R)\R C A x A, R je dobré uspořádání na B C A} Poněvadž (0,0) G D, platí máme / |. Pro (B1} Rľ), (B2, R2) £ -D položíme (.Bi, < (B2,R2), pokud je začátek (B2,R2). Zřejmě < je uspořádání množiny Ověříme, že D spluje předpoklad principu maximality. Buď CCD řetězec. Pak Q= U R (B,R)eC je lineární uspořádání množiny U B (B,R)eC Uvažujme 0 ^ X C Z. Pro libovolné x G X existuje (5, R) E C tak, že x E B. Zřejmě nejmenší prvek podmnožiny X H-B je nejmenším prvkem množiny X. Tedy Q je dobré uspořádání množiny Z, takže (Z, Q) G -D. Zřejmě (Z, Q) je hledanou horní závorou řetězce C v D. Podle principu maximality existuje maximální prvek (B, R) v D. Ukážeme, že pak B = A. V opačném případě existuje prvek a E A — B a pro Bq = B U {a} a R0 = R U (5 x {a}) U {(a, a)} platí (B0,R0) E D a zárove (B, R) < (B0,R0), což není možné. □ Věta 6.5. Axiom výběru implikuje princip maximality. Důkaz. Bud A uspořádaná množina taková, že libovolný řetězec v A má horní závoru a necht a E A. Buď / výběrová funkce na množině všech neprázdných podmnožin množiny A. To znamená, že f{X) E X pro libovolné 0 ^ X C A. Existuje dobře uspořádaná množina B taková, že \B\ < \A\ neplatí. V opačném případě by se W skládala z ordinálních čísel podmnožin množiny A, které lze dobře uspořádat. Poněvadž dobrých uspořádání podmnožin množiny A je pouze množina, dostali bychom spor s 4.5. Transfinitní indukcí definujme zobrazení g : C —^ A definované na podmnožině C množiny B tak, že a je obrazem nej menšího prvku množiny B a g(b) = f({x E A\g{y) < x pro všechna y < b}) Zobrazení g je zřejmě prosté. Poněvadž \B\ < \A\ neplatí, existuje b E B tak že g není definováno pro b. Buď b nejmenší prvek v B s touto vlastností. Pak existuje c E C tak že c < b a neexistuje x E B, c < x < b. V opačném případě by obraz g byl řetězec v A bez horní závory. Zřejmě g (c) je hledaný maximální prvek v A takový, že a < g (c). □ 21 7. Kardinální aritmetika Věta 7.1 (AC). Kardinálni čísla jsou dobře uspořádaná relací <. Důkaz. Libovolnému kardinálnímu číslu a přiřadíme ordinální číslo a* tak, že a < p & a* < p* Odsud již vyplyne tvrzení věty nebo ordinální čísla jsou dobře uspořádaná relací < dle 4.3. _ Necht a = \A\. Buď Ma množina všech ordinálních čísel P takových, že P = (A, ^) pro nějaké dobré uspořádání ^ množiny A. Z AC víme, že Ma ^ 0, takže Ma má nejmenší prvek, který označíme a*. Definice zřejmě nezávisí na volbě množiny A. Implikace a* < p* =>. a < p je zřejmá. Necht a < /3. Pak a* < P* nebo P* < a*. V druhém případě platí P < a, takže a = P, takže a* = /3*. □ Předchozí věta nám umožuje indexovat nekonečná kardinální čísla pomocí ordinálních čísel. Třída kardinálních čísel pak (ve svém uspořádání <) vypadá následovně 0,1,..., n,... N0, Ni,..., K, ■ ■ ■ K, ■ ■ ■ #a, ■ ■ ■ Indexování provedeme následovně. Již dříve jsme nejmenší nekonečné kardinální číslo označili No- Nyní Ki je nejmenší nespočetné kardinální číslo. Z 7.1 víme, že takové kardinální číslo existuje. Máme-li již sestrojena kardinální čísla pro všechna ordinální čísla P < a, pak Ka je nejmenší kardinální číslo větší než všechna pro P < a. Z 7.1 plyne, že takové kardinální číslo existuje. Poněvadž pro libovolné kardinální číslo K existuje pouze množina kardinálních čísel menších než K, K = Ka pro nějaké ordinální číslo a. Tímto postupem jsme vlastně sestrojili bijekci mezi ordinálními čísly a nekonečnými kardinálními čísly. V důkazu věty 7.1 jsme libovolnému kardinálnímu číslu a přiřadili ordinální číslo a* a sice nejmenší ordinální číslo mohutnosti a. Budeme značit K = ua Třídu W ordinálních čísel si pak můžeme představit následovně 0, l,...,n,.. .u0,.. .e0,.. . .ua,... (srv. s kapitolou 5; u = ujq). Věta 7.2. Axiom výběru je ekvivalentní s tím, že kardinální čísla jsou lineárně uspořádaná relací <. Důkaz. Implikace =^ plyne z 7.1. Předpokládejme, že kardinální čísla jsou lineárně uspořádaná relací <. Ukážeme, že pak libovolnou množinu lze dobře uspořádat, což implikuje AC. Buď A množina. Z důkazu věty 6.5. víme, že existuje dobře uspořádaná množina B taková, že \B\ < \A\ neplatí. Tedy \A\ < \B\ nebo předpokládáme, že kardinální 22 čísla jsou lineárně uspořádána relací <. Tedy existuje prosté zobrazení / : A —>• B, které nám umožní definovat dobré uspořádání množiny A: a x C X. Ordinální čísla tranzitivní jsou. Definice ordinálního čísla v ZF tedy zní: ordinální číslo je tranzitivní množina dobře uspořádaná relací G. Věta 7.4 (AC). Pro libovolné nekonečné kardinální číslo K platí K • K = K Důkaz. Již víme, že za AC jsou kardinální čísla právě Na, kde a G W. Transfinitní indukcí budeme tedy dokazovat, že Pro a = 0 tvrzení platí (viz 2.6). Předpokládejme, že 0 < a a že tvrzení platí pro všechna /3 < a. Dokážeme, že tvrzení platí pro a. Tím bude důkaz ukončen. Na množině W(uja) x W(uja) budeme uvažovat tzv. maximo-lexikografickéuspořádání. Je definováno tak, že (/3,7) < (S,e), právě když max{/3,7} < max{5, e} nebo max{/3,7} = max{5, e} a /3 < ô nebo max{/3,7} = max{5, e}, /3 = ô a 7 < e 23 Zřejmě se jedná o dobré uspořádání. Označme rj = W(ua) x W(ua) takže W(ua) x W(ua) 9á W(ri) Stačí, když dokážeme, že platí rj = ua. Pak totiž bude platit Ka • Ka = \W(ua) x W(ua)\ = \W(ua)\ = Ka Především platí u)a < i] nebo \W(ua)\ < \W(ua) x W(ua)\ = \W(V)\ a uja je nejmenší ordinální číslo mohutnosti Na. Předpokládejme, že ua < rj. Pak existují ordinální čísla 7, ô < ua tak, že (druhý výraz zde označuje začátek určený dvojicí (7, ô) v W(uja) x W(uja)). Položme £ = max{7, 5} + 1 Zřejmě ^ < uja. Z definice maximo-lexikografického uspořádání plyne, že W((7,í))C W(Ox^(0 tedy |W^a)| = |W((7,5))| < x W(£)\ = \W(£)\ (poslední rovnost plyne z indukčního předpokladu). Poněvadž £ < ua, platí \W(ua)\ < \W(£)\ < \W(ua)\ Dostáváme spor a důkaz je tím ukončen. □ Věta 7.5 (AC). Pro libovolná ordinální čísla a,j3 platí ■ N/3 = max^a, K^} Důkaz. Necht například a < j3. Pak platí Kp = 1 • *p < K ■ *p < *p ■ *p = *p takže Ka • = N^. □ Důsledek 7.6 (AC). Pro libovolná ordinální čísla a,j3 platí Důkaz. Necht například a < j3. Pak platí Kp• x C W. (3) x G y eW r (x) < r (y). Důkaz. (1) Pro a limitní je tvrzení zřejmé. Stačí tedy ukázat, že Wa C Wa+i pro libovolné a. Dokážeme to transfinitní indukcí. Necht to platí pro libovolné /3 < a. Je-li 0 < a limitní, pak Wa+1 = V(Wa) D U V{Wp) = (J wp+1 = wa. /3• A permutace. Definujme / : WA —> WA následovně: (1) fo = /, (2) fa+1(x) = {fa(y)\yex}, (3) fa= U f P Pro 0 ŕ a limitní, /3 WA je isomorfismus, t.j., bijekce taková, že (1) /(0) = 0, (2) f (A) = A, (3) x ey^f(x) G f (y). Důkaz. Transfinitní indukcí. Definice 9.4. Množina x G WA se nazývá symetrická, jesttliže existuje konečná množina atomů N(x) = {a±,..., an} taková, že pro libovolnou permutaci / : A —^ A platí f(ai) = cií, i = 1,..., n f (x) = x. N (x) se nazývá nosič x. Množina x se nazývá dedičné symetrická, pokud je symetrická a každý prvek z tranzitivního obalu T (x) je symetrická množina. Příklady 9.5. (1) Libovolná množina x £ V je dědičně symetrická s N (x) = 0. (2) Libovolné a G A je dědičně symetrická s N (a) = {a}. (3) Množina x C A je symetrická, právě když je konečná nebo její doplněk je konečný. V prvním případě N (x) = x, v druhém N (x) = A — x. Tyto množiny jsou dědičně symetrické. (4) V (A) je symetrická množina s nosičem 0. Není však dědičně symetrická. Necht Pa označuje třídu všech dědičně symetrických množin s množinou atomů A. Věta 9.6. PA je model ZFA. Důkaz. 0, A G Pa a (0), (A) platí. (Aľ) plyne z toho, že x E Pa implikuje x C PA. (A2) Necht x,y E Pa- Zřejmě {x, y} je symetrická s nosičem N (x) UN(y). Zřejmě {x, y} je dědičně symetrická. (A3) Necht x,t\,...,tn G Pa a x = {z G y\f(z, t\,..., tn)}. Ukážeme, že x je n symetrická množina s nosičem N (x) = N (y) U |J N (ti). Buď / : A —^ A per- mutace taková že f (a) = a pro libovolné a G N (x). Poněvadž / je isomorfismus, tp(z,tlv .. ,tn) platí, právě když platí ip(f(z), f (h),..., f(tn) = if(f(z),t1,...,tn). Tedy f (x) = x, takže x je symetrická množina, která je zřejmě dědičně symetrická. 29 (A4) Necht x A v Pa platí g(N) C N (g). Podobně pro zobrazení h : A —y N platí h(A) C N (h). Tedy g ani h nejsou injektivní. □ 10. Teorie množin v algebře a analýze Definice 10.1. Částečně uspořádaná množina T se nazývá strom, jestliže ix = {y\y ■ b e 7. Příklady 10.9. (1) V (M) je filtr, nazývá se nevlastní Ostatní filtry se nazývají vlastní. 2) Pro X c M t X = {A C M\,X C A} je filtr. Nazývá se hlavní. 3) J7 = {A C M\ M — A je konečná} je filtr. Pokud M je nekonečná, tento filtr není hlavní. Definice 10.10. Maximální vlastní filtr se nazývá ultrafiltr. Příklad 10.11. t {x} je ultrafiltr. Věta 10.12. Vlastní filtr j7 je ultrafiltr, právě když pro libovolnou podmnožinu A C M platí AeT nebo M — A e T. 31 Důkaz. Necht J7 splňuje podmínku věty a J7 C Q filtr, J7 ^ Q. Pro A G Q — J7 platí M-AeF, takže 0 = A n (M - A) G Q. Tedy 0 = "P(M), takže T je ultrafiltr. Naopak, buď J7 ultrafiltr a X C M tak, že M — X (jz J7. Pak Q = {A C M| existuje B e J7, B f] X C A}. Pak C/ je filtr, J7 C G, X E Q a, M — X ^ Q. Poněvadž J7 je ultrafiltr, Q = J7, takže X G J7. □ Věta 10.13 (AC). Pro libovolný filtr J7 na množině M existuje ultrafiltr U na M takový, že J7 C U. Důkaz. Plyne z 6.5 a toho, že sjednocení řetězce vlastních filtrů je vlastní filtr. □ Definice 10.14. Dvouhodnotová míra na množině M je zobrazení fi : V(M) —> 2 takové že (1) /i(0) = 0, fi(M) = 1, (2) A C B fj,(A) < fj,(B), (3) A n B = 0 =>■ n(A U 5) = //(A) + n(B). Věta 10.15. Je-li fi dvouhodnotová míra na množině M, pakU={A C M\ fi(A) = 1} je ultrafiltr. Důkaz. Necht A, B e U. Podle (3), 1 = n(A) = fi(A C\B)+ fi(A - B), 1 = fi(B) = fi(A H B) + - A). Pokud //(A H B) = 0, pak //(A - B) = fi(B - A) = 1 a tedy U 5) = n 5) + - B) + - A) = 2, což není možné. Tedy A H B G W. Odsud zřejmě plyne, že U je filtr, který je ultrafiltr vzhledem k (3) a 10.12. Poznámka 10.16. (1) Naopak, pokud ti je ultrafiltr na M, pak jjl(A) = 1 AeW definuje dvouhodnotovou míru na M. Vlastnosti (1) a (2) jsou zřejmé. Necht A H 5 = 0, AU B e U &, A ^ U. Pak M-AeWa tedy B = (M - A) n (AU B) eU, což dává (3). Definice 10.17. Dvouhodnotová míra fi na množině M se nazývá spočetně aditivní, jestliže pro navzájem disjunktní množiny AÍ7 i < uj platí 32 Věta 10.18. Míra fi na M je spočetně aditívni, právě když pro příslušný ultrafiltrU platí Ai eU,i < uj =>• Pl A eU. Důkaz. I. Buď U ultrafiltr určený spočetně aditivní mírou fi. Necht Ai G U, i < uj. Množiny Bi = (M- Ai) - \J(M - A,) j