TEORIE MNOŽIN - PŘÍKLADY
J. ROSICKÝ
1. Množiny
1. Zformulujte axiom extensionality, slovně a pomocí predikátové logiky.
2. Zformulujte axiom dvojice, slovně a pomocí predikátové logiky.
3. Zformulujte schéma axiomů vyčlenění, slovně a pomocí predikátové logiky.
4. S pomocí schématu axiomů vyčlenění sestrojte průnik a rozdíl množin A, B.
5. Zformulujte axiom sjednocení, slovně a pomocí predikátové logiky.
6. Zformulujte axiom množiny podmnožin, slovně a pomocí predikátové logiky.
7. Pro množiny a, b, definujte množinu (a,b), t.j., uspořádanou dvojici prvků a, b.
8. Pomocí axiomů teorie množin, sestrojte kartézský součin A x B množin A, B.
9. Zformulujte axiom nekonečna, slovně a pomocí predikátové logiky.
10. Zformulujte schéma axiomů nahrazení, slovně a pomocí predikátové logiky.
11. Dokažte (A x B)c 2á Ac x Bc.
12. Dokažte, že pro libovolnou množinu A platí |A\ < \V(Á)\. Udejte příklad množiny A takové, že \A\ = \V{A)\.
13. Dokažte (AB)C = ABxC.
14. Dokažte, že pro disjunktní množiny A, B platí CAuB = CA x CB.
15. Definujte tranzitivní množinu. Rozhodněte, která z následujících množin je tranzitivní: 0, {0}, {{0}}, {0, {0}}.
Date: Březen 27, 2020.
2
2. Kardinální čísla
1. a) Udejte příklad nekonečných množin A,B,C takových, že \A\ < \B\ < \C\. b) Vysvětlete proč kardinální čísla netvoří množinu.
2. Definujte
a) kardinální číslo,
b) uspořádání kardinálních čísel. Je toto uspořádání
a) lineární
b) dobré?
3. Nalezněte
a) nej menší kardinální číslo,
b) nejmenší nekonečné kardinální číslo,
c) nejmenší nespočetné kardinální číslo.
4. Reálné číslo se nazývá algebraické, pokud je kořenem polynomu s celočíselnými koeficienty. Dokažte, že množina algebraických čísel je spočetná.
5. a) Ukažte, že neexistuje množina A taková, že pro libovolnou množinu B platí \B\<\A\.
b) Nalezněte množinu A takovou, že pro libovolnou množinu B platí \A\ < \B\.
6. Dokažte, že platí a) \A\ < \A U B\,
b) \A\ <\Ax A\.
c) Rozhodněte, zda platí \B\ < \ A — B\ pro libovolné množiny A, B.
7. a) Definujte součet a + /3, součin a ■ j3 a mocninu a13 kardinálních čísel, b) Dokažte, že platí K0 •     = ^o-
8. a) Uveďte definici spočetné množiny.
b) Nalezněte 5 navzájem různých spočetných množin.
9. Dokažte, že sjednocení dvou spočetných množin je spočetná množina.
10. a) Dokažte, že nekonečná podmnožina spočetné množiny je spočetná.
b) Uveďte příklad dvou množin, které mají různou mohutnost a přitom nejsou ani konečné, ani spočetné.
11. Dokažte, že množina IR všech reálných čísel je nespočetná.
3
12. Určete mohutnost množiny C všech komplexních čísel.
13. Pro libovolné kardinální číslo Ka platí Ka • Ka = Na. Z tohoto vztahu dokažte, že pro libovolná kardinální čísla Na, platí:
a) Ka •     = max{Ka, K^}
b) Ka +     = max{Ka, K^}
16. a) Udejte příklad nekonečných množin A,B,C takových, že \A\ < \B\ < \C\. b) Udejte příklad množiny, která má právě spočetně mnoho podmnožin.
17. Vysvětlete, proč neexistuje největší kardinální číslo Rozhodněte, zda existuje největší kardinální číslo < Ni
18. Určete mohutnost množiny N* všech konečných posloupností přirozených čísel. Výsledek zdůvodněte.
19. Určete mohutnost množiny Rel(N) všech binárních relací na množině přirozených čísel. Výsledek zdůvodněte.
20. Seřaďte následující množiny podle mohutností (s vyznačením případných rovností): množina I iracionálních čísel, množina M(M) čtvercových reálných matic, množina ]RE reálných funkcí, množina M[x] polynomů s reálnými koeficienty a množina C komplexních čísel.
21. Seřadte následující množiny podle mohutností (s vyznačením případných rovností): Z, IRE, Q, P(IR), 0, P(N), I (I označuje množinu všech iracionálních čísel):
22. a) Definujte mocninu 'R^f kardinálních čísel Ha a H^.
b) Seřaďte následující kardinální čísla podle velikosti: K0, 2K°, Kq°.
23. a) Definujte regulární kardinální číslo, b) Dokažte, že        je vždy regulární.
14. Dokažte
a) |N x N| = \N\
b) \R x R\ = \R\
24. a) Definujte singulární kardinální číslo.
b) Udejte příklad singulárního kardinálního čísla.
25. a) Definujte mocninu 'R^f kardinálních čísel Ka a N/?.
b) Uspořádejte následující kardinální čísla podle velikosti: Ni, Ko • Ni, 2Kl, Kq1.
26. Reálné číslo se nazývá transcendentní, pokud není kořenem polynomu s celočíselnými koeficienty. Dokažte, že množina všech transcendentních reálných čísel je nespočetná.
27. Určete mohutnost množiny všech nekonečných řad
oo
a) E dix\ aj G IR pro i = 0,1,...,
i=0
oo
b) E/i^Ň fi : K-> M pro i = 0,1,....
i=0
28. Udejte příklad množiny mohutnosti
a) N0,
b) 2K°,
c)
29. Určete mohutnost množiny
a) všech konečných posloupností symbolů {a,b},
b) všech spočetných posloupností symbolů {a, b}.
30. A) Definujte nedosažitelné kardinální číslo, b) Je Kw nedosažitelné?
3. Dobře uspořádané množiny
1. Buď A dobře uspořádaná množina a / : A —^ A prosté izotonní zobrazení. Dokažte, že pro všechna x E A platí x < f {x). (Návod: Uvažte podmnožinu {x G A, f(x) < x}.)
2. a) Nalezněte tři navzájem neisomorfní spočetné dobře uspořádané množiny, b) Udejte příklad nespočetné dobře uspořádané množiny.
3. a) Udejte příklad dobře uspořádané množiny A takové, že Aop je rovněž dobře uspořádaná.
b) Udejte příklad dobrého uspořádání na množině N x N.
4. a) Definujte vlastní začátek uspořádané množiny.
5
b) Ukažte, že libovolný vlastní začátek dobře uspořádané množiny A je tvaru A(a) = {iG A\x < a} pro nějaké a E A.
5. Dokažte, že dobře uspořádaná množina není isomorfní s žádným svým vlastním začátkem.
6. Definujte lexikografický součin A ■ B dobře uspořádaných množin A, B. Dokažte, že A ■ B je dobře uspořádaná množina.
7. a) Definujte, kdy se uspořádaná množina nazývá dobře uspořádaná.
b) Uveďte příklad uspořádané množiny, která není dobře uspořádaná.
c) Nalezněte všechna možná dobrá uspořádaní množiny {1,2,3}.
8. Definujte lexikografický součin A ■ B dobře uspořádaných množin A, B. Dokažte, že uspořádané množiny A ■ {B ■ C) a {A ■ B) ■ C jsou izomorfní.
9. Zformulujte a dokažte princip transfinitní indukce.
10. Nalezněte dobré uspořádání množiny
a) Z všech celých čísel
b) Q všech racionálních čísel
c) všech polynomů, jejichž koeficienty jsou nezáporná celá čísla.
11. Udejte příklad dobře uspořádané množiny A, izotonního zobrazení / : A —>• A a prvku a E A tak, že f {a) < a.
12. Buď A dobře uspořádaná množina. Dokažte, že existuje jediný isomorfismus A —ř A.
13. (1) Definujte
a) uspořádanou množinu
b) lineárně uspořádanou množinu
c) dobře uspořádanou množinu (2) Udejte příklad
(a) uspořádané množiny, která není lineárně uspořádaná
(b) lineárně uspořádané množiny, která není dobře uspořádaná
(c) konečné lineárně uspořádané množiny, která není dobře uspořádaná.
14. Rozhodněte, kolik existuje navzájem neizomorfních dobrých uspořádání množiny N přirozených čísel. Nalezněte tři z nich.
6
15. a) Definujte pojem dobře uspořádané množiny.
b) Rozhodněte, které z následujících množin (s uspořádáním < podle velikosti) jsou dobře uspořádané: {—3, 0,1, 3, 5}, N, Z, [0,1].
16. a) Definujte, kdy dobře uspořádané množiny A, B nazýváme izomorfní.
b) Nalezněte 2 navzájem neizomorfní konečné dobře uspořádané množiny.
c) Nalezněte 2 navzájem neizomorfní spočetné dobře uspořádané množiny.
17. Nalezněte nějaké dobré uspořádání množiny M2(Q) čtvercových matic nad Q stupně 2.
18. Rozhodněte, zda uspořádaná množina A je dobře uspořádaná. V kladném případě napište ano, v záporném uveďte neprázdnou podmnožinu X C A, která nemá nej-menší prvek:
a) A = R,
b) A = Z,
c) A = P({0,1}) (uspořádaná inkluzí).
19. Rozhodněte, zda pro libovolné dobře uspořádané množiny A, B, C platí distributivní zákon
A-(B + C) = (A-B) + (A-C).
V kladném případě napište ano a uveďte důkaz, v záporném případě uveďte ne a udejte dobře uspořádané množiny A, B, C, pro které tvrzení neplatí.
20. Nalezněte 2 navzájem neizomorfní dobrá uspořádání množiny N přirozených čísel, která nemají největší prvek.
21. Dokažte, že libovolná podmnožina dobře uspořádané množiny je dobře uspořádaná.
22. Definujte
a) pojem izomorfismu dvou dobře uspořádaných množin,
b) pojem vlastního začátku dobře uspořádané množiny.
Udejte příklad dobře uspořádané množiny izomorfní se svým vlastním začátkem.
23. Rozhodněte, zda pro libovolné dobře uspořádané množiny A, B, C platí distributivní zákon
(B + C)- A = (B ■ A) + (C ■ A).
V kladném případě napište ano a uveďte důkaz, v záporném případě uveďte ne a udejte dobře uspořádané množiny A, B, C, pro které tvrzení neplatí.
7
4. Ordinálni čísla 1. a) Seřaďte následující ordinálni čísla podle velikosti: 2u),u) + l,u) + u)1,u)1+u,l +
uj, uj + uj, uj + 1 + uj.
b) Rozhodněte, zda existuje největší spočetné ordinálni číslo.
c) Nalezněte nej menší ordinálni číslo > uj2 + uj + 1,
d) Nalezněte nejmenší nespočetné ordinálni číslo.
2. a) Definujte součin a ■ j3 ordinálních čísel a,/3 (s vysvětlením v definici použitých pojmů).
b) Charakterizujte ordinálni čísla a taková, že a ■ 2 = 2 • a.
3. Ukažte, že množina spočetných ordinálních čísel je nekonečná.
4. Definujte
a) ordinálni číslo,
b) uspořádání ordinálních čísel,
c) součet ordinálních čísel,
d) součin ordinálních čísel.
5. Nalezněte 3 navzájem neizomorfní dobrá uspořádání množiny N všech přirozených čísel, udejte jejich ordinálni čísla a seřadte je podle velikosti.
6. a) Definujte součet a + /3 a součin a ■ j3 ordinálních čísel.
b) Nakreslete Hasseův diagram dobře uspořádaných množin, které mají ordinálni čísla uj + 1 a 1 + uj.
c) Dokažte, že platí w + 1 / 1 +
7. a) Nakreslete Hasseův diagram dobře uspořádaných množin, které mají ordinálni čísla 2 • uj a uj ■ 2.
b) Dokažte, že platí 2-w/w-2.
c) Ordinálni čísla uj,uj + 1,1 + uj,2-uj,uj-2 seřadte podle velikosti.
8. a) Nakreslete Hasseův diagram dobře uspořádané množiny, která má ordinálni číslo uj ■ uj.
b) Definujte mocninu a13 ordinálních čísel.
9. Nalezněte (v dobře uspořádané třídě ordinálních čísel):
a) třetí nejmenší nekonečné ordinálni číslo
b) nějaké ordinálni číslo a s vlastností uj2 < a < uj3
c) největší spočetné ordinálni číslo
d) u-té nespočetné ordinálni číslo
10. Určete ordinální čísla
\w ,T ,...,nw ,...,ujw
(kde n je přirozené číslo). Rozhodněte, která z těchto ordinálních čísel jsou spočetná a která jsou nespočetná.
11. Seřaďte podle velikosti ordinální čísla uj, 2 • uj, uj ■ 2, uj2, 2W ,uj ■ uj
12. a) Definujte mocninu a13 ordinálních čísel a a /3.
b) Určete ordinální čísla lw a 2W
c) Rozhodněte, zda ujw = uj. Své rozhodnutí zdůvodněte.
13. a) Definujte ordinální číslo uj\.
b) Rozhodněte, zda uj\ < ujw . Své rozhodnutí zdůvodněte.
14. a) Definujte součet ordinálních čísel a + /3.
b) Rozhodněte, zda uj + uj = uj. Své rozhodnutí zdůvodněte.
c) Rozhodněte, zda uj + uj2 = uj2. Své rozhodnutí zdůvodněte.
15. Následující ordinální čísla seřaďte podle velikosti (a vyznačte případné rovnosti):
10,10ľ, uj10, uj + uj, uj", uju 10 + uj.
16. Následující ordinální čísla seřaďte podle velikosti (a vyznačte případné rovnosti):
uj + 1 + uj,uj ■ (uj + 1), (1 + uj) ■ uj, (1 + uj) ■ (uj + l),uj + 1 + uj2 + uj.
17. Nalezněte nejmenší ordinální číslo a takové, že ordinální mocnina a" je
a) konečné ordinální číslo,
b) spočetné ordinální číslo,
c) nespočetné ordinální číslo.
18. Vyjádřete ujľ v Cantorově normálním tvaru (t.j.,
uji = uj10 ■ rriQ + uj11 ■ ni\ + • • • + ujlh ■ nik,
kde k,rriQ,rrii,... ,rrik jsou nenulová přirozená čísla a 70 > 71 > • • • > 7^ ordinální čísla.
19. a) Definujte mocninu a13 ordinálních čísel a a /3. b) Spočtěte ordinální číslo uj".
20. a) Nalezněte ordinální čísla ô < uj a p < 3 taková, že uj = 3 • ô + p. b) Nalezněte ordinální čísla ô < uj± a p < uj taková, že ujľ = uj ■ ô + p.
9
21. Rozhodněte, zda
(a) ojw = oj,
(b) oj^ = oj",
(c) existuje nej menší ordinální číslo a takové, že oja = a,
(d) v kladném případě v (c) rozhodněte, zda toto číslo je spočetné.
22. Rozhodněte, zda pro ordinální čísla a,/3 platí
qu = /T =>■ a = /3.
Své rozhodnutí zdůvodněte.
23. Nalezněte oj-té nespočetné ordinální číslo.
24. Dokažte, že oj"1 = oj\.
25. Ordinální číslo A se nazývá nespočetné, pokud \A\ > No-
a) Rozhodněte, zda existuje infimum množiny všech nespočetných ordinálních čísel. V kladném případě jej nalezněte, v záporném případě tvrzení dokažte.
b) Rozhodněte, zda existuje supremum množiny všech nespočetných ordinálních čísel. V kladném případě jej nalezněte v záporném případě tvrzení dokažte.
26. Nalezněte
(a) třetí nejmenší nekonečné ordinální číslo,
(b) nějaké limitní ordinální číslo a s vlastností oj2 < a < oj3,
(c) uj-té nespočetné ordinální číslo.
27. a) Definujte mocninu a13 ordinálních čísel a a /3.
b) Určete ordinální číslo 2UJl. Využijte přitom vztahu: l<«,/3<7=^aí/3< a7.
28. Rozhodněte, zda pro ordinální čísla a, j3,7 platí tvrzení
a < f3 =>■ a7 < /37. Tvrzení bud dokažte nebo vyvratte protipříkladem.
29. Cantorův normální tvar ordinálního čísla a je
a = uj10 ■ rriQ + uj11 ■ ni\ + • • • + ujlk ■ nik,
kde k,niQ,nii,... ,nik jsou nenulová přirozená čísla a 70 > 71 > • • • > 7^ ordinální čísla.
Vyjádřete v tomto tvaru uj2 + oj± + oj + 1.
10
30. Buďte a < (5 a 7 ordinální čísla. Rozhodněť nebo udejte protipříklad):
a) 7 + a < 7 + /3,
b) a + 7 < (3 + 7.
,e, zda platí (tvrzení buď dokažte
31. Cantorův normální tvar ordinálního čísla a je
a = uj
,70 .
niQ + uj'
,71 .
mi + • • • + ujlh ■ nik
kde k,rrio,rrii,... ,rrik jsou nenulová přirozená čísla a 70 > 71 > • • • > 7^ ordinální čísla.
Vyjádřete v tomto tvaru     + ui + u + 1. 32. Definujte ordinální číslo v axiomatické teorii množin.
1. Zformulujte
a) axiom výběru,
b) princip dobrého uspořádání,
c) princip maximality.
2. Zformulujte axiom výběru a princip dobrého uspořádání. Dokažte, že princip dobrého uspořádání implikuje axiom výběru.
3. Dokažte, že z principu dobrého uspořádání vyplývá, že uspořádání kardinálních čísel je lineární.
4. Dokažte, že z linearity uspořádání kardinálních čísel vyplývá princip dobrého uspořádání.
5. Dokažte, že princip maximality implikuje princip dobrého uspořádání.
6. Dokažte, že za axiomu výběru má každý vektorový prostor bazi (t.j. lineárně nezávislou množinu generátorů).
1. a) Určete W3.
b) Nalezněte nej menší a s vlastností uj G Wa.
c) Nalezněte jednoprvkovou množinu, která nepatří do
2. a) Udejte příklad množiny patřící do W$ ale ne do W4. b) Nalezněte nej menší a s vlastností ujľ G Wa.
5. Axiom výběru
6. Axiom regularity
11
c) Nalezněte jednoprvkovou množinu, která nepatří do WLÚ1.
3. a) Udejte příklad množiny patřící do       ale ne do Wn pro žádné n E oj.
b) Nalezněte nej menší a s vlastností V(N) G Wa.
c) Nalezněte konečnou množinu, která nepatří do W^.
6. Zformulujte axiom regularity (pomocí predikátové logiky).
7. Definujte řád množiny x. Určete řád ordinálního čísla ujw.
8. Pro jaké ordinální číslo a je Wa model ZFC?
9. Pro jaké ordinální číslo a je Wa model ZFC bez schématu axiomů nahrazení?
10. Dokažte, že x C W implikuje x G W.
11. Dokažte, že pokud x G y, pak řád x je menší než řád y.
7. Permutační model
1. Definujte symetrickou množinu.
2. Definujte dědičně symetrickou množinu.
3. Kdy je podmnožina x C A množiny atomů symetrická?
4. Je množina V (A) podmnožin množiny atomů dědičně symetrická?
5. Popište permutační model teorie množin s atomy.
8. Teorie množin v algebře a analýze
1. Definujte následující pojmy: strom, hladina, výška stromu, větev, kofinální větev.
2. Zformulujte a dokažte Kônigovu větu.
3. Definujte slabě kompaktní kardinální číslo.
4. Definujte náledující pojmy: filtr, vlastní filtr, hlavní filtr, ultrafiltr.
5. Udejte příklad vlastního filtru na N, který není hlavní.
6. Udejte příklad ultrafiltru na N.
12
7. Ukažte, že filtr Jna M takový, že pro libovolnou ACM platí buď A G J7 nebo M \ A G J7 je ultrafiltr.
8. Dokažte, že pro libovolný vlastní filtr J7 na množině M existuje ultrafiltr U na M takový, že T Cti.
9. Definujte dvouhodnotovou míru na množině M.
10. Dokažte, že pro libovolnou dvouhodnotovou míru fi na množině M je
{A C M\fi(A) = 1}
ultrafiltr.
11. Definujte spočetně aditivní dvouhodnotovou míru na množině M.
12. a) Definujte spočetně úplný filtr na množině M.
b) Udejte příklad spočetně úplného filtru na množině IR.
13. Definujte měřitelné kardinální číslo.
14. Definujte silně kompaktní kardinální číslo.