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 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 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 = #5 ^ A ~ B. Pro každé n 6 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 6 N, to jest, =frn = n. Množiny náležející sjednocení 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é mohutností. Množiny ekvivalentní s množinou N se nazývají spočetné množiny. Spočetná mohutnost se označuje symbolem (N je první písmeno hebrejské abecedy a čte se alef). Máme tedy #N = No- 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. ,x 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 = N0. Mohutnost množiny reálných čísel se nazývá mohutnost kontinua. Budeme se jí podrobně zabývat později. 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 Ä) 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. K dispozici je i obecnější definice, která má podobnou podstatu. 4.3. Definice. Buď F : I —> U systém množin. Jeho disjunktní sjednocení definujeme jako sjednocení Podobně platí, že i sjednocované množiny {i} x Fi nemají žádné společné prvky (proč?) a opět v tom spočívá smysl této konstrukce. 4.4. Tvrzení. 1°. Budte A, B dvě disjunktní množiny. Pak A U B ~ A U B. 2°. Buď F : I —> U systém množín po dvou disjunktních, čilí takových, že U i H U j = 0, kdykoliv i^jel. Pak Uí£j Fi ~ Uíei Fi. Důkaz. 1°. Zadejme zobrazení h : Au B —> A U B předpisem Ukažte jako cvičení, že h je bijekce. 2°. Analogicky. Při násobení mohutností se používá kartézský součin množin, který už známe z dřívějška. Důkaz. Cvičení. N ~ Z, N ~ N x N, N ~ Q. [0, x], když x 6 A, [l, x], když x 6 B. 28 LOGIKA A TEORIE MNOŽIN 4.5. Tvrzení. Buďte A ~ A' dvě ekvivalentní množiny a B ~ B' jiné dvě ekvivalentní množiny. Pak 1° AUB ~ Ä UB', 2° A x B ~ i' x B', 3° BA ~ BM' jsou ekvivalentní množiny. Důkaz. Buďte qa '■ A —> A' & gs ■ B —> B' bijekce. 1° : Zaveďme zobrazení Snadno se ukáže, že qa U qb je bijekce s inverzí qa~x U 9b-1 ■ Tudíž, ^4 U _B a A' U B' jsou ekvivalentní. 2° : Zaveďme zobrazení gA x gB '■ A x B —> A' x B' předpisem Í9A x 9E>){a, b) = [ffA(a),ffs(&)]- Snadno se ukáže, že qa x qb je bijekce s inverzí B'A , / i—> §b ° / ° fl^1, má inverzi B'A —> BA, h \—> g^1 oho g a, 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° #Í + #B = #(ÍUB), 2° #Ax#B = #(Ax B), 3° (#B)(#A) = #(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 N0 + 1 = No + 2 =• • • = N0 + N0 = N0. Návod: Uspořádávání do posloupnosti. Cvičení. Ukažte, že No2 = No3 =• • • = No. (Pozor, NoN° = No neplatí!) Návod: Uspořádávání do posloupnosti. g a U gB ■■ A U B A' U B' předpisem když x = [0, a] e {0} x ^4, když x = [1,6] e {1} x B. 29 LOGIKA A TEORIE MNOŽIN Pro operace s kardinálními čísly platí obvyklé zákony aritmetiky. 4.6. 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, 0 x a= 0, ab+c = ab x ac, a6xc = (a6)c, (a x b)c = ac x bc, a° = l, a1 = a. Důkaz. Cvičení. Nalezněte potřebné bijekce. Cvičení. Ukažte, že pro každou mohutnost m platí m + m = 2xm, m2=mxm. 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 = =f/=A a b = jj=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 4.11 a zase se vraťte. 4.7. Cantor-Bernsteinova věta. Jestliže a < b a zároveň b < a, pak a = b. Důkaz. Nechť a = j^A a b = =$B. Podle předpokladu existují injektivní zobrazení f : A —> B a g : B —> A. Konstruujme bijektivní zobrazení A —> B. Označme ^0 = A, B0 = B, Aí = gBo, Bx = fAo m = gBi, B2 = fAí A,, = gB2, Bz = fA2 A4 = gB3, B4 = fA3 30 LOGIKA A TEORIE MNOŽIN a obecně Ai+i = gBi, Bi+\ = fAi pro každé přirozené číslo i. Přitom A0 D Ax D A2 D ■ ■ •, B0 D ^ D B2 D ■ ■ ■, Dále g dává bijekci Bi —> Ai+i a / dává bijekci Ai —> Bi+\. Tudíž, g\Bi_1\Bi Je bijekce B2_i \ B, A, \ Al+1 a podobně f\Ai_1\Ai Je bijekce Aí-íXAí Bi\Bi+1. Složením dostáváme bijekce A0 \ A1 — B1 \ B2 — A2 \ A3 — B3 \ BA — • • • zprostředkované zobrazením / a bijekce B0 \ Bi — \ m — B2 \ £3 — ^3 \ ^4 — • • • zprostředkované zobrazením g. Z nich je možné sestavit bijekce mezi sjednoceními (J J42í \ ^2í+i (J B2í+i \ B2í+2 a rovněž mezi sjednoceními (J B2í \ B2í+i (J ^2í+i \ ^2í+2- Celkově je tím nalezena bijekce mezi podmnožinami Podmnožina Uígpí Bí \-Bj+i resp. Uígpí j4í\j4j+i ovšem není rovna celému A resp. B. Nicméně, U^i\4i+i=^\n^> UBA-Bí+i = B\ f] B,. Inkluze C plyne z inkluzí Aí\Aí+\ C j4\nigpjPro každé i; podobně pro B. Opačnou inkluzi I) dokážeme úvahou, že pro libovolný prvek a 6 A \ Hí^n -^í existuje nejmenší i takové, že a tfz Ai+i, načež a 6 Ai \ Ai+\. Tudíž, zatím jsme našli bijekci A \ f) At ^ B \ f| Bt a ještě zbývá zkonstruovat bijekci mezi průniky P)ieN j4j a P\i€^Bi. To ^ze Provést například následujícím způsobem: r\A^f]A2^f](goffAMf]f(gofyA iew iew iew iew Důkaz je hotov. 31