Základní pojmy z teorie množin. Množina bude pro nás jakýkoli souhrn objektů, které budeme nazývat prvky množiny. Existuje přesná matematická definice pojmu množina, ale my si vystačíme s intuitivní představou. Pouze v závěru kapitoly si ukážeme, že tato intuitivní představa má své omezení a že ne každý soubor objektů lze považovat za množinu. Začneme s připomenutím obvyklého značení. ∅ prázdná množina, N = {1, 2, . . . } přirozená čísla, Z = {. . . , −2, −1, 0, 1, 2, . . . } celá čísla, R = (−∞, ∞) reálná čísla. Je-li V nějaká vlastnost, pak symbol {x ∈ A | x má vlastnost V } označuje množinu všech prvků z A, které mají vlastnost V . Příklad. {x ∈ R | x = m/n, kde m ∈ Z a n ∈ N} = Q, množina racionálních čísel. Jiný příklad je množina {m ∈ N | m je dělitelné právě dvěma z čísel 1, 2, . . . , m}, což je množina všech prvočísel. Dále si připomeneme základní množinové vztahy a operace. • B ⊂ A, B je podmnožina množiny A. Vždy platí A ⊂ A a ∅ ⊂ A. Pokud chceme zdůraznit, že B ⊂ A, ale B 6= A, píšeme B $ A a řekneme, že B je vlastní podmnožina množiny A. • A1 ∪ A2 = {x | x ∈ A1 nebo x ∈ A2 }, sjednocení množin A1 a A2 . Pro sjednocení většího počtu množin užíváme značení analogické sumaci m [
Ak = A1 ∪ · · · ∪ Am ,
∞ [
Ak = A1 ∪ A2 ∪ . . . .
k=1
k=1
• A1 ∩ A2 = {x | x ∈ A1 a x ∈ A2 }, průnik množin A1 a A2 . Pro průnik většího počtu množin užíváme podobně m \
Ak = A1 ∩ · · · ∩ Am ,
k=1
∞ \
k=1
1
Ak = A1 ∩ A2 ∩ . . . .
2 • A \ B = {x ∈ A | x ∈ / B}, množinový rozdíl. • A × B = {(a, b) | a ∈ A, b ∈ B}, kartézský součin množin A a B. Pro součin více množin píšeme m Y
∞ Y
Ak = A1 × · · · × Am ,
k=1
Ak = A1 × A2 × . . . .
k=1
Jsou-li všechny množiny A1 = A2 = · · · = A, pak součin budeme zkracovat symbolickým zápisem Am v případě součinu m množin a AN v případě nekonečného součinu. Příklad. ∞ [
(−k, k) = R,
k=1
∞ [
h k1 , ki k=1
= (0, ∞),
∞ \
(0,
1 k)
= ∅,
k=1
∞ \
h0, k1 ) = {0}.
k=1
• h0, 1i2 = {(x, y) | x, y ∈ h0, 1i} je jednotkový čtverec v rovině. Podobně h0, 1i3 je jednotková krychle a např. h0, 1i4 je zápis čtyřrozměrné jednotkové krychle. • Množina
∞ Y
k=1
Ak = (a1 , a2 , . . . ) ak ∈ Ak , k ≥ 1
je množina všech posloupností takových, že na k-tém místě stojí prvek z množiny Ak . Specielně {0, 1}N je množina všech posloupností vytvořených z nul a jedniček. O něco složitější než předchozí základní množinové operace jsou následující dvě: Mějme posloupnost množin (Ak ). Množinu ∞ \ ∞ [
Ak
n=1 k=n
nazýváme limes inferior posloupnosti množin (Ak ) a množinu ∞ [ ∞ \
Ak
n=1 k=n
nazýváme limes superior posloupnosti množin (Ak ). Podívejme se blíže např. na první z těchto množin, limes inferior. Začíná operací sjednocení přes n = 1, 2, . . . , což znamená, že postupně sjednocujeme množiny ∞ \
k=1
Ak ,
∞ \
Ak ,
k=2
∞ \
Ak , . . .
k=3
Prvek x náležící limes inferior leží ve sjednocení výše uvedených množin, tj. leží v jedné z nich. Proto existuje index n0 , že ∞ \ x∈ Ak . k=n0
3 Můžeme tak říci, že prvek x patří do limes inferior množin (Ak ) právě, když od jistého indexu n0 prvek x patří do všech množin Ak s k ≥ n0 . Podobně platí, že x patří do limes superior množin (Ak ) právě, když x leží v nekonečně mnoha množinách posloupnosti (Ak ). Z tohoto popisu plyne vztah mezi limes inferior a limes superioir ∞ \ ∞ [
n=1 k=n
Ak ⊂
∞ [ ∞ \
Ak ,
n=1 k=n
neboť náleží-li prvek do všech množin Ak pro k ≥ n0 , pak samozřejmě leží v nekonečně mnoha množinách posloupnosti (Ak ). Příklad. Uvažujme posloupnost množin (Ak ), k ∈ N, která je definovaná ( (0, 1) pro k liché Ak = h3, 5i pro k sudé. Pak limes superior posloupnosti (Ak ) je (0, 1) ∪ h3, 5i a limes inferioir je ∅. Jiný příklad je posloupnost množin (Ak ), k ∈ N, definovaná Ak = h(−1)k , k2 i. Zde limes superior posloupnosti (Ak ) je h−1, ∞) a limes inferioir je h1, ∞). Poslední příklad vyžaduje trochu zamyšlení. Označme si (nk ) jakoukoli posloupnost přirozených čísel takovou, že se v ní žádné členy neopakují a položíme Ak = (−∞, nk i. Limes inferior a limes superior posloupnosti (Ak ) jsou nyní stejné a rovnají se množině reálných čísel R. Obrátíme pozornost k základním vztahům mezi množinovými operacemi. Věta 1. (de Morganova pravidla) Mějme množiny B, A1 , A2 , . . . . Pak platí T S∞ (i) B \ ∞ k=1 Ak = k=1 (B \ Ak ), S T∞ (ii) B \ ∞ k=1 Ak = k=1 (B \ Ak ).
Důkaz. Ukážeme pouze první bod. Druhý je zcela stejný, jen se navzájem prohodí symboly ∩ a ∪. T T Mějme x ∈ B \ ∞ / ∞ k=1 Ak . To je ekvivalentní tomu, že x ∈ B a x ∈ k=1 Ak . Což je opět to samé jako, že existuje index k0 , že x ∈ B a x ∈ / Ak0 , tj. existuje index k0 , že x ∈ B \ Ak0 . S Jinými slovy, x ∈ ∞ (B \ A ). k k=1 Definice. Řekneme, že zobrazení f : A −→ B je bijekce (množiny A na množinu B), jestliže je prosté (tj. a1 6= a2 ⇒ f (a1 ) 6= f (a2 )) a jeho obor hodnot je roven množině B.
4 Můžeme si představovat, že bijekce zprostředkovává „kopírováníÿ jedné množiny na druhou. Existuje-li mezi množinami A a B bijekce, je jedna množina kopií druhé. Rovněž je vidět, že inverzní zobrazení k bijekci zůstává bijekcí a složení dvou bijekcí je opět bijekce. Existuje-li bijekce mezi dvěma konečnými množinami, musí mít obě stejný počet prvků. Výhoda takového porovnání spočívá v tom, že nemusíme vědět kolik mají příslušné množiny prvků k tomu, abychom je prohlásili za stejně velké. Proto se tento způsob hodí i pro porovnávání velikostí jakýchkoli množin, nejen konečných. Definice. Řekneme, že množiny A a B mají stejnou mohutnost (zápis |A| = |B|), jestliže existuje bijekce množiny A na množinu B. Existuje-li prosté zobrazení množiny A do množiny B, pak budeme tento fakt značit |A| ≤ |B|. V případě konečných množin je mohutnost množiny rovna počtu prvků. Místo názvu mohutnost se také často používá slovo kardinalita. Označení zavedené v definici je vhodné při zapamatování důležitého tvrzení, tzv. Schröder - Bernsteinovy věty. Tato věta nám pomáhá ukázat, že dvě množiny mají stejnou mohutnost, aniž bychom museli explicitně sestrojit příslušnou bijekci. Věta 2. Mějme množiny A a B takové, že existuje prosté zobrazení množiny A do množiny B a také prosté zobrazení množiny B do množiny A. Pak A a B mají stejnou mohutnost. V označení, které jsme si zavedli, je formulace této věty přirozená: Je-li |A| ≤ |B| a |B| ≤ |A|, pak |A| = |B|. Abychom mohli pracovat i s nekonečnými množinami, potřebujeme si vyjasnit, co znamená, že množina je nekonečná. Návrhy pro definici nekonečné množiny typu, že má nekonečně mnoho prvků nic neřeší, neboť jsme jeden nevyjasněný pojem pouze nahradili jiným pojmem stejně vágním. Musíme najít vlastnost, která jasně odlišuje konečné a nekonečné množiny. U konečných množin je zřejmé, že jejich vlastní podmnožiny mají méně prvků než celá množina. V řeči bijekce to znamená, že neexistuje bijekce takové množiny na svoji vlastní podmnožinu. Negací této vlastnosti dostaneme to, co charakterizuje množiny nekonečné. Definice. Množina A je nekonečná, jestliže existuje bijekce na její vlastní podmnožinu. Množina N je podle výše uvedené definice nekonečná, neboť např. zobrazení f : N −→ N dané f (n) = n + 1 je bijekce celé množiny N na vlastní podmnožinu {2, 3, . . . }. Rovněž bijekce f (n) = 2n přirozených čísel na množinu sudých čísel opět ukazuje, že množina N je nekonečná. Definice. Má-li množina A stejnou mohutnost jako množina přirozených čísel, |A| = |N|, nazývá se spočetná. Výše vedené příklady ukazují, že {2, 3, . . . } i množina sudých čísel jsou spočetné. Následující věta obsahuje prostředky výhodné pro dokazování spočetnosti. Věta 3. (i) Množina A je spočetná právě, když se všechny její prvky dají seřadit do prosté posloupnosti. Specielně, nekonečná podmnožina spočetné množiny je rovněž spočetná.
5 (ii) Je-li f : A −→ B zobrazení spočetné množiny A na nekonečnou množinu B, je i B spočetná. Důkaz. (i) Je třeba ověřit dvě implikace. V té první předpokládáme, že množina A je spočetná. Pak existuje bijekce f : N −→ A a ta nám umožní vytvořit posloupnost f (1) , f (2) , f (3), . . . prvků z A. Tato posloupnost obsahuje všechny prvky množiny A a navíc je prostá, neboť f je prosté zobrazení. Pro druhou implikaci předpokládáme, že množinu A lze uspořádat do prosté posloupnosti a1 , a2 , a3 , . . . Budeme definovat zobrazení f : N −→ A následovně f (1) = a1 , f (2) = a2 , .. . f (n) = an , .. . Protože posloupnost je prostá, je i zobrazení f prosté. Protože v posloupnosti jsou obsaženy všechny prvky množiny A je obor hodnot f celá množina A. Jinými slovy, f je bijekce přirozených čísel na množinu A, a tedy A je spočetná. Pro dodatečné tvrzení z bodu (i) si stačí seřadit danou spočetnou množinu do posloupnosti a její nekonečná podmnožina se stane vybranou podposloupností. (ii) Ze vzoru f −1 (b) každého bodu b ∈ B vezmeme jeden prvek. Ty vytvoří podmnožinu A0 ⊂ A. Protože A je spočetná, je podle již dokázaného bodu (i) množina A0 rovněž spočetná. Na ní je zobrazení f prosté, tj. f je bijekce množiny A0 na množinu B. Důležité na tvrzení (ii) je, že o zobrazení f nemusíme předpokládat, že je prosté. Předchozí výsledek nám spolu s následující větou říká, že spočetné množiny jsou nekonečné množiny s nejmenší mohutností. Věta 4. Každá nekonečná množina obsahuje spočetnou podmnožinu. Důkaz. Mějme nekonečnou množinu A a volme si a1 ∈ A libovolně. Protože A je nekonečná, je množina A \ {a1 } neprázdná. Zvolíme si v ní prvek a2 ∈ A \ {a1 }. Rovněž množina A \ {a1 , a2 } je neprázdná a tedy obsahuje nějaký prvek a3 ∈ A \ {a1 , a2 }. Tak pokračujeme dále až vytvoříme nekonečnou prostou posloupnost a1 , a2 , a3 , . . . prvků z A. Označíme-li si B = {a1 , a2 , a3 , . . . } je podle Věty 3(i) množina B spočetná podmnožina množiny A. V této chvíli je na místě otázka, zda existují také množiny, které jsou větší než spočetné. Podíváme se množiny, které vypadají na pohled větší než množina N.
6 Příklad. Množina Z celých čísel. Tuto množinu můžeme seřadit do prosté posloupnosti např. následujícím způsobem: 0, 1, −1, 2, −2, 3, −3, . . . Podle Věty 3(i) je množina Z spočetná. Kdybychom chtěli najít vzorec pro odpovídající bijekci množiny N na množinu Z, tak má tvar hni f (n) = (−1)n , 2
kde [x] značí celou část (reálného) čísla x.
Příklad. Množina N×N je rovněž spočetná, neboť ji můžeme vypsat do prosté poloupnosti podle pravidla naznačeného na obrázku. .. . •
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
···
Tzn. (1, 1), (1, 2), (2, 1), (1, 3), (2, 2), (3, 1), · · · . Věta 5.
(i) Jsou-li množiny A a B spočetné, je spočetná i množina A × B.
(ii) Sjednocení spočetně mnoha spočetných množin je opět spočetná množina. Důkaz. (i) Protože množiny A a B jsou spočetné, lze je podle Věty 3(i) seřadit do prosté posloupnosti A = {a1 , a2 , . . . }, B = {b1 , b2 , . . . }. Definujme zobrazení f : N × N −→ A × B předpisem f (m, n) = (am , bn ). Pak f je bijekce množiny N × N na množinu A × B. O množině N × N víme z příkladu před větou, že je spočetná. Proto i množina A × B je spočetná. (ii) Mějme spočetné množiny A1 , A2 , . . . a každou seřadíme do prosté posloupnosti A1 = {a11 , a12 , . . . }, A2 = {a21 , a22 , . . . }, .. .
7 Definujeme zobrazení f : N × N −→
S∞
k=1 Ak
předpisem
f (m, n) = amn .
S To je zobrazení množiny N × N na celou množinu ∞ k=1 Ak . Toto f ovšem nemusí být prosté, neboť množiny A1 , A2 , . . . mohou mít nějaké prvky společné. Nicméně podle Věty 3(ii) je sjednocení opět spočetná množina.
Příklad. Množina Q racionálních čísel je spočetná. Q=
∞ nm o [ An , m ∈ Z, n ∈ N = n n=1
kde An je množina všech zlomků se jmenovatelem n, tj. n o 2 1 0 1 2 An = . . . , − , − , , , , . . . . n n n n n
Protože všechny množiny An jsou spočetné (mají stejnou mohutnost jako Z), je podle Věty 5(ii) množina Q také spočetná.
Věta 6. Mějme spočetnou množinu A. Pak platí (i) Ak je spočetná pro každé k ∈ N; (ii) konečných podmnožin množiny A je spočetně mnoho. Důkaz. (i) Tvrzení budeme dokazovat pomocí matematické indukce přes k. Je-li k = 1, pak tvrzení je zřejmé, neboť A1 = A. Předpokládejme, že množina Ak je spočetná a chceme dokázat, že i Ak+1 je spočetná. Protože Ak+1 = Ak × A, je podle Věty 5(i) součin těchto dvou spočetných množin opět spočetná množina. (ii) Označme si ∞ [ B = A ∪ A2 ∪ A3 ∪ · · · = Ak . k=1
Ak
Podle bodu (i) jsou všechny množiny spočetné a Věta 5(ii) říká, že i jejich spočetné sjednocení, tj. množina B, je spočetné. Množina B jsou všechny uspořádané k-tice prvků z A pro všechna k ∈ N. Uvažujme zobrazení f z množiny B do množiny všech konečných podmnožin A takové, že uspořádané k-tici přiřadíme k-prvkovou podmnožinu skládající se z prvků dané k-tice. Toto zobrazení sice není prosté, ale zobrazuje B na množinu všech konečných podmnožin A. Podle Věty 3(ii) je množina konečných podmnožin spočetná. Zatím to vypadá, že všechny množiny, na které jsme narazili jsou spočetné. Je na čase ukázat, že tomu tak není.
8 Příklad. Množina reálných čísel z intervalu (0, 1) není spočetná. Abychom si to ukázali, předpokládejme na chvíli, že (0, 1) spočetná je. Podle Věty 3 je možné všechna čísla z (0, 1) vypsat jako členy jisté posloupnosti. Pišme si členy této posloupnosti pod sebe. x1 = 0. a1 a2 a3 · · · , x2 = 0. b1 b2 b3 · · · , x3 = 0. c1 c2 c3 · · · , .. . kde symboly za desetinou tečkou znamenají číslice v desítkovém zápisu každého čísla. Těchto symbolů za desetinou tečkou může být konečně i nekonečně mnoho. Budeme předpokládat, že je jich vždy nekonečně mnoho, neboť ve vyjádření každého čísla xk lze konec doplnit nulami, je-li potřeba. Uvažujme číslo y ∈ (0, 1), jehož desetiný rozvoj y = 0. y1 y2 y3 · · · splňuje následující požadavky: y1 6= a1 , y2 6= b2 , y3 6= c3 atd. Takové číslo snadno sestrojíme, dokonce takových čísel je více. Toto y však není rovno žádnému z čísel x1 , x2 , . . . , neboť se od x1 liší na místě desetin, od x2 na místě setin atd. To je spor s předpokladem, že výše napsaná posloupnost obsahuje všechna čísla v (0, 1). Před následující větou zavedeme označení pro množinu všech podmnožin dané množiny A. P(A) = {B | B ⊂ A} a P(A) nazýváme potenční množinou množiny A. Věta 7. Množina P(N) všech podmnožin přirozených čísel není spočetná. Důkaz. Důkaz provedeme sporem. Předpokládejme, že P(N) je spočetná. Podle Věty 3 je možné takouvou množinu napsat do posloupnosti P(N) = {A1 , A2 , . . . , }. Nyní utvoříme speciální podmnožinu S přirozených čísel tím, že budeme procházet postupně čísla 1, 2, 3, . . . a u každého z nich se rozhodneme, zda-li ho dáme do množiny S nebo nikoli. Rozhodování se řídí podle následujícího algoritmu: Je-li 1 ∈ / A1 , dáme číslo 1 do množiny S. Jinak posloupíme k číslu 2. Je-li 2 ∈ / A2 , dáme číslo 2 do množiny S. Jinak posloupíme k číslu 3. Je-li 3 ∈ / A3 , dáme číslo 3 do množiny S. Jinak posloupíme k číslu 4. .. . Zápis množiny S je tedy S = {n ∈ N | n ∈ / An }. Protože v seznamu {A1 , A2 , . . . , } jsou zapsány všechny podmnožiny množiny N, je tam někde i množina S, tj. existuje m, že S = Am . Potíže nastanou, když budeme chtít zjistit, zda množina S obsahuje číslo m či nikoliv.
9 Kdyby m ∈ S = {n ∈ N | n ∈ / An }, tak m ∈ / Am = S. Kdyby m ∈ / S = Am , tak m ∈ S.
- spor. - spor.
Jiná možnost už není, takže samotná existence množiny S vede ke sporu. Protože existence S vyplývala z možnosti zapsat množinu P(N) do posloupnosti, není možné P(N) takto vyjádřit, a tedy P(N) není spočetná. Symbolicky lze tvrzení Věty 7 zapsat |P(N)| > |N|. Nekonečné množiny, které nejsou spočetné budeme nazývat nespočetné, a tedy Větu 7 můžeme vyslovit ve tvaru, že P(N) je nespočetná, neboli všech podmnožin přirozených čísel je nespočetně mnoho. Vidíme, že množina A je nespočetná právě tehdy, je-li její mohutnost větší než mohutnost přirozených čísel, |A| > |N|. Z Věty 7 vyplývá také, že nekonečných podmnožin přirozených čísel je nespočetně mnoho. Zjistili jsme totiž ve Větě 6 (ii), že konečných podmnožin přirozených čísel je spočetně mnoho. Protože P(N) = {konečné podmnožiny} ∪ {nekonečné podmnožiny}, a P(N) je nespočetná, musí být systém nekonečných podmnožin také nepočetný. Příklad. Ukážeme si, že všech posloupností tvořených nulami a jedničkami je nespočetně mnoho. Množina všech takových posloupností je {0, 1}N . K tomu, aby množina {0, 1}N byla nespočetná stačí ukázat, že její mohutnost je stejná jako mohutnost P(N), o které to víme. Sestrojíme bijekci f : P(N) −→ {0, 1}N následovně. Chceme každé podmnožině A přirozených čísel přiřadit nějakým vhodným způsobem posloupnost (an ) vytvořenou z nul a jedniček: Mějme množinu A ⊂ N a definujme posloupnost (an ) ( 1 n ∈ A; an = 0 n∈ / A. Položíme f (A) = (an ). Např. f (∅) = (0, 0, . . . ), f (N) = (1, 1, . . . ) nebo f ({lichá čísla}) = (1, 0, 1, 0, . . . ) apod. Takto definované zobrazení f je prosté a obor hodnot jsou všechny posloupnosti nul a jedniček. Je to bijekce množiny P(N) na {0, 1}N , a tedy i {0, 1}N je nespočetná. Na závěr dokážeme slavnou Cantorovu větu o kardinalitách. (Georg Cantor, německý matematik, zakladatel teorie množin (1845 - 1918).) Věta 8. Pro každou množinu A platí, že |P(A)| > |A|. Důkaz. Protože vždycky |A| ≤ |P(A)|, neboť např. všechny jednoprvkové podmnožiny už mají stejnou mnohutnost jako A, stačí nám dokázat, že |A| = 6 |P(A)|. Předpokládejme, že |A| = |P(A). Existuje tedy bijekce f : A −→ P(A),
10 která každému prvku a ∈ A přiřadí nějakou podmnožinu f (a) množiny A. Může se stát, že prvek a leží ve své přiřazené podmnožině, a ∈ f (a), nebo se může stát, že a ve své přiřazené množině neleží, a ∈ / f (a). Uvažujme množinu S těch prvků a, pro které nastává druhá z možností, S = {a ∈ A | a ∈ / f (a)}. Protože zobrazení f je bijekce, obor hodnot jsou všechny podmnožiny množiny A. Existuje tedy speciální prvek a0 ∈ A takový, že f (a0 ) = S. Hledaný spor nastane, budeme-li se pokoušet zjistit, zda a0 leží či neleží v množině S. Kdyby a0 ∈ S = {a ∈ A | a ∈ / f (a)}, tak a0 ∈ / f (a0 ) = S, Kdyby a0 ∈ / S = f (a0 ), tak a0 ∈ S,
- spor. - spor.
Jiná možnost už není, takže samotná existence množiny S vede ke sporu. Protože existence S vyplývala z předpokladu |A| = |P(A)|, tato rovnost neplatí. Uvedeme si jeden důsledek Cantorovy věty, kterým je často zmiňované tvrzení, že množina všech množin je nesmyslný pojem vedoucí ke sporu. Používá se jako argument k tomu, že ne každý soubor objektů je množina; např. soubor všech množin nemůže být množinou. Uvažujme A = {B | B je množina}, což je soubor všech množin. Kdyby i A byla množina, můžeme aplikovat Cantorovu větu a dostaneme, že |P(A)| > |A|. Na druhou stranu, každý prvek P(A) je podmnožina A, specielně je to množina, a tedy patří do A. Patří-li každý prvek z P(A) do A, je P(A) ⊂ A. Pak ale P(A) nemůže mít větší mohutnost než A.
Cvičení. (1) Dokažte, že pro množiny A, B jsou následující podmínky ekvivalentní: (a) B ⊂ A; (b) B \ A = ∅; (c) A ∪ B = A; (d) A ∩ B = B. (2) Uvažujme podmnožiny množiny X a definujme pro ně operaci A|B := X \ (A ∩ B). Vyjádřete operace ∩, ∪ a \ pomocí operace |. (3) Nalezněte posloupnost A1 , A2 , A3 , . . . navzájem různých podmnožin R takovou, že (a) (b)
∞ \
n=1 ∞ \
n=1
An = (−1, 1) a
∞ [
An = h−2, 2i;
n=1
An = {1} a
∞ [
n=1
An = h0, ∞);
11 (c) (d) (e)
∞ \
n=1 ∞ \
n=1 ∞ \
n=1
An = ∅ a An = Z a
∞ [
n=1 ∞ [
An = R; An = R;
n=1
An =
∞ [
An .
n=1
(4) Nalezněte limes superior a limes inferior posloupnosti množin (Ak ), k ∈ N, definované (a) Ak = (2−k , 2−k + 1); (b) Ak = h(−2)k , 3k i; (c) Ak = hqk , 1i, kde (qk ) jsou všechna racionální čísla z intervalu h0, 1i seřazená do prosté posloupnosti. (5) Je-li A1 , A2 , . . . libovolná S posloupnost S∞ množin, pak existují disjunktní množiny Bk , Bk ⊂ Ak , s vlastností ∞ B = k=1 k k=1 Ak .
(6) Mějme konečnou množinu A a zobrazení f : A −→ A. Které z následujích tvrzení je pravdivé? (a) Je-li A \ f (A) = ∅, pak f je prosté. (b) Je-li A \ f (A) 6= ∅, pak f není prosté. Které z těchto tvrzení bude platit v případě, že množina M nekonečná? (7) Mějme nekonečnou množinu A a prvek x0 ∈ / A nepatřící do A. Ukažte, že množiny A ∪ {x0 } i A mají stejnou mohutnost, tj. |A ∪ {x0 }| = |A|. (8) Dokažte, že množina N × N × N je spočetná. (9) Ukažte, že množina všech polynomů s celočíselnými koeficienty je spočetná.
(10) Ukažte, že každý interval (a, b), a < b, má stejnou mohutnost jako interval (0, 1). (11) Ukažte, že interval (0, 1) má stejnou mohutnost jako R. (12) Nalezněte bijekci intervalu h0, 1) na interval (0, 1). (13) Ukažte, že interval (0, 1) a čtverec (0, 1)2 mají stejnou mohutnost. (14) Je množina iracionálních čísel spočetná nebo nespočetná? (15) Existuje množina s největší mohutností?
Řešení. (2) A|A = X \ A, (A|B)|(A|B) = A ∩ B, (A|A)|(B|B) = A ∪ B.
12 (3a) Např. A1 = (−1, 1), A2 = h−2, 2i a zbylé An , n ≥ 3 jsou jakékoli navzájem různé podmnožiny A2 obsahující A1 . (3b) Např. A1 = {1}, An = h0, k) pro n ≥ 2. (3c) Např. An = (−n + 1, n − 1). (3d) Např. An = Z ∪ (−n + 1, n − 1). (3e) Takové navzájem různé množiny neexistují. (4a) lim Ak = lim Ak = (0, 1i, (4b) lim Ak = R, lim Ak = ∅, (4c) lim Ak = (0, 1i a lim Ak = {1}. S (5) Položíme Bk = Ak \ i
