LOGIKA A TEORIE MNOŽIN 4.10. Tvrzení. Nechť a, ď, b, b' jsou mohutnosti takové, že a < a', b < b'. Pak 1° a+b A1, g : B —> B1. Snadno se ukáže, že zobrazení f U g a f x g zkonstruovaná v částech 1° a 2° důkazu tvrzení 4.8 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 hi,h2 : B —> A přiřazena stejná zobrazení h[ = h'2 : B1 —> A'. Pak / o h[ o g = / o h!2 ° g, čili / o h\ = f o /i2. 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.8? 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 <•••< N0. Důkaz. Připomeňme, že n + 1 = {0,1, 2,..., n}. Neostré nerovnosti < plynou z existence injektivních vložení 0^{O}^{O,1}^{O,1,2}^-..^N. Nerovnosti n + 1 / n bezprostředně vyplývají z klasického Dirichletova principu. Důkaz Dirichletova principu povedeme indukcí. Označme Dn tvrzení: "Pro n 6 N neexistuje injektivní zobrazení n + 1 —> n." Tvrzení Do 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+l. Připomeňme, že n+ 2 = {0,1, 2,..., n + 1}. Prvek f(n+ 1) 6 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+l —> ra + 1 \ {f(n+ 1)} a je rovněž injektivní. Avšak n+ 1 \ {f(n+ 1)} ~ n (zkonstruujte bijekci), takže jsme obdrželi injektivní zobrazení n+l —> n, což je ve sporu s Dn. Zbývá dokázat nerovnost n < No Pro všechna hě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. 35 LOGIKA A TEORIE MNOŽIN 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 —> pA je bijektivní zobrazení. Označme X = {a e A | a g F (a)}. Jelikož je F surjektivní, existuje x 6 A takové, že F(x) = X. Pak nastane právě jedna ze dvou možností. 1) x 6 X, čili x 6 F(x), načež x $ X podle definice množiny X, spor; 2) x f£ X, čili x £ F(x), načež x 6 X podle definice množiny X, spor. Tudíž, ,4 pA, a proto a ^ 2a. 4.14. Důsledek, iř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ž Hq, 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 = #R. 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 6 {0,1}. Takové posloupnosti můžeme přiřadit třeba reálné číslo s desetinným rozvojem ^ anWn = 0, a0aia2 ... 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ž r Q R injektivním zobrazením 2N —> I(a, b) (jakým?). Potažmo i do zbývajících intervalů I(a, b], I[a, b), l[a, b]. Z Cantor-Bernstainovy věty vyplývá, že existují bijekce mezi množinami 2W, R, I(a, Ď), I(a, Ď], I[a, Ď), I[a, b]. 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 M. 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ř. Cvičení. Najděte bijekci mezi 1(0, 1] a I[0, 1]. Návod: Upravte kontrakci z předchozího cvičení. Cvičení. Ukažte, že t=c + l = c + 2=---=c + No = t + c = c+ t + c=---=NoXc = c x c = c x c x c =• • • = cN°. Cvičení. Ukažte, že #C = c. Cvičení. Ukažte, že množina všech spojitých funkcí M —► M 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í 2N —► R. Posloupnosti [a„]„en nul a jedniček jsme přiřadili reálné číslo s desetinným rozvojem a„10" = 0, aaa\a-2. .. . Obrazem tohoto zobrazení je podmnožina v M, 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( j^, -^), 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. 37 LOGIKA A TEORIE MNOŽIN 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) < #21, 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í St = U On, 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™ = No (proč?). Dostáváme tedy #21 < # J 2t„ < J2 = J2 N° = N°x N° = nePÍ new new 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. Pro přirozená čísla n 6 N definujme 3„ rekurzivním předpisem 30 = No, = 2^n. Podle Cantorovy věty zřejmě 3o < 3i < 32 <• • •. Máme 31 = 2N° = c, 32 = 2Jl = 2C, 33 = 232 = 22\ ... a také 3o = #N, 3i = #pN, 32 = #ppN, 33 = #pppN, ... Cvičení. Ukažte, že mohutnost II2 mají množiny 1) pM všech podmnožin množiny reálných čísel; 2) MR všech reálných funkcí jedné reálné proměnné; 3) ~ž2n€N K všech reálných funkcí konečně mnoha reálných proměnných. 38