1. Mějme množinu \( A = \{1, 2, 3, 4, 5\} \). Určete, zda je tato množina konečná, spočetná nebo nespočetná.
Řešení příkladu:
Množina \( A \) obsahuje pět prvků, které jsou přirozená čísla. Jelikož je počet prvků konečný, množina \( A \) je konečná. Všechny konečné množiny jsou zároveň spočitatelné, protože lze vytvořit bijekci mezi množinou a podmnožinou přirozených čísel. Tedy:
\( A \) je konečná \( \Rightarrow \) \( A \) je spočetná.
2. Uvažujme množinu všech celých čísel \( \mathbb{Z} \). Určete, zda je spočetná nebo nespočetná.
Řešení příkladu:
Celá čísla zahrnují kladná, záporná čísla a nulu. I když jsou nekonečná, můžeme je uspořádat do posloupnosti:
\( 0, 1, -1, 2, -2, 3, -3, \ldots \)
Každému číslu můžeme přiřadit jedno přirozené číslo, např. \( f(n) = (-1)^n \cdot \left\lfloor \frac{n}{2} \right\rfloor \). Tato funkce je bijekce mezi \( \mathbb{N} \) a \( \mathbb{Z} \), proto je \( \mathbb{Z} \) spočetná množina.
3. Mějme množinu všech reálných čísel mezi \(0\) a \(1\), tedy \( (0,1) \). Je tato množina spočetná?
Řešení příkladu:
Množina \( (0,1) \subset \mathbb{R} \) je interval všech reálných čísel mezi 0 a 1. Pomocí Cantorova diagonálního důkazu lze ukázat, že nelze vytvořit bijekci mezi \( \mathbb{N} \) a \( (0,1) \). Tedy množina reálných čísel v intervalu \( (0,1) \) je nespočetná.
4. Určete, zda je množina všech konečných binárních řetězců spočetná.
Řešení příkladu:
Konečný binární řetězec je posloupnost nul a jedniček o konečné délce. Například: „“, „0“, „1“, „10“, „11“, atd. Existuje nekonečně mnoho takových řetězců, ale každý má konečnou délku. Vytvořením uspořádaného seznamu podle délky a lexikograficky lze vytvořit bijekci s \( \mathbb{N} \). Tedy:
\( \Rightarrow \) množina všech konečných binárních řetězců je spočetná.
5. Mějme množinu všech racionálních čísel \( \mathbb{Q} \). Je tato množina spočetná?
Řešení příkladu:
Racionální čísla jsou všechna čísla ve tvaru \( \frac{p}{q} \), kde \( p \in \mathbb{Z} \), \( q \in \mathbb{N} \). I když je jich nekonečně mnoho, lze je uspořádat do tabulky (např. Cantorův argument) a přečíslit diagonálně. Tím vzniká bijekce s \( \mathbb{N} \).
\( \Rightarrow \mathbb{Q} \) je spočetná množina.
6. Množina všech podmnožin \( \mathbb{N} \): je spočetná nebo nespočetná?
Řešení příkladu:
Podmnožinou \( \mathbb{N} \) může být každá množina obsahující libovolné prvky z \( \mathbb{N} \). Množina všech podmnožin \( \mathcal{P}(\mathbb{N}) \) má vyšší mohutnost než \( \mathbb{N} \) a nelze mezi nimi vytvořit bijekci.
\( \Rightarrow \mathcal{P}(\mathbb{N}) \) je nespočetná.
7. Množina všech konečných podmnožin množiny \( \mathbb{N} \). Je spočetná?
Řešení příkladu:
Konečných podmnožin \( \mathbb{N} \) je nekonečně mnoho, ale každá taková množina obsahuje jen konečný počet přirozených čísel. Můžeme je zakódovat jako binární řetězce konečné délky, a tedy jsou spočetné.
\( \Rightarrow \) Množina všech konečných podmnožin \( \mathbb{N} \) je spočetná.
8. Je množina všech funkcí \( f : \mathbb{N} \to \{0,1\} \) spočetná?
Řešení příkladu:
Každá funkce \( f : \mathbb{N} \to \{0,1\} \) lze chápat jako nekonečný binární řetězec. Počet těchto funkcí odpovídá mohutnosti množiny \( \{0,1\}^\mathbb{N} \), což je stejně jako množina podmnožin \( \mathbb{N} \), tedy nespočetná.
9. Uvažuj množinu všech slov nad abecedou \( \{a,b\} \), která mají konečnou délku. Je spočetná?
Řešení příkladu:
Konečných slov nad konečnou abecedou je nekonečně mnoho, ale všechna jsou konečné délky. Můžeme je uspořádat podle délky a lexikograficky, a tím vytvořit bijekci s \( \mathbb{N} \).
\( \Rightarrow \) množina všech konečných slov nad \( \{a,b\} \) je spočetná.
10. Je množina všech reálných čísel \( \mathbb{R} \) spočetná nebo nespočetná?
Řešení příkladu:
Množina reálných čísel \( \mathbb{R} \) má vyšší mohutnost než \( \mathbb{N} \). Cantorův diagonální důkaz ukazuje, že neexistuje bijekce mezi \( \mathbb{N} \) a \( \mathbb{R} \).
\( \Rightarrow \mathbb{R} \) je nespočetná množina.
11. Je množina všech přirozených čísel dělitelných třemi konečná, spočetná nebo nespočetná?
Řešení příkladu:
Označme množinu všech přirozených čísel dělitelných třemi jako \( A = \{ n \in \mathbb{N} \mid \exists k \in \mathbb{N} : n = 3k \} \). Tato množina má tvar \( \{3, 6, 9, 12, \ldots\} \), tedy jde o aritmetickou posloupnost s diferencí 3.
Počet prvků v této množině je nekonečný, protože neexistuje žádné největší přirozené číslo dělitelné třemi. Přesto lze prvky této množiny jednoznačně očíslovat pomocí bijektivní funkce \( f : \mathbb{N} \to A \) definované jako \( f(k) = 3k \).
Protože existuje bijekce mezi \( \mathbb{N} \) a \( A \), množina \( A \) je spočetná. Konečná není, protože obsahuje nekonečně mnoho prvků. Nespočetná být nemůže, protože jakákoli podmnožina \( \mathbb{N} \), která má nekonečně mnoho prvků, je spočetná.
Závěr: Množina všech přirozených čísel dělitelných třemi je nekonečná a spočetná.
12. Uvažuj množinu všech dvojic přirozených čísel \( \mathbb{N} \times \mathbb{N} \). Je tato množina spočetná?
Řešení příkladu:
Každý prvek množiny \( \mathbb{N} \times \mathbb{N} \) je uspořádaná dvojice \( (a, b) \), kde \( a, b \in \mathbb{N} \). Na první pohled se zdá, že těchto dvojic je více než prvků v samotné množině \( \mathbb{N} \), avšak existuje způsob, jak tuto množinu spočítat.
Představme si dvojice jako body v rovině celých čísel. Uspořádáme je pomocí tzv. Cantorova diagonálního číslování: pro každé přirozené číslo \( n \) definujeme množinu dvojic \( (a, b) \) tak, aby \( a + b = n \). Například:
\( (1,1),\ (1,2),\ (2,1),\ (1,3),\ (2,2),\ (3,1),\ \ldots \)
Tímto způsobem lze seřadit všechny dvojice do posloupnosti, kde každé dvojici odpovídá jedno přirozené číslo. Tato posloupnost vytváří bijekci mezi \( \mathbb{N} \) a \( \mathbb{N} \times \mathbb{N} \).
Závěr: Množina všech dvojic přirozených čísel je spočetná, protože lze vytvořit bijekci s \( \mathbb{N} \).
13. Určete, zda je množina všech polynomů s celočíselnými koeficienty a jednou proměnnou spočetná.
Řešení příkladu:
Označme tuto množinu jako \( P = \{ p(x) = a_0 + a_1x + \cdots + a_nx^n \mid a_i \in \mathbb{Z},\ n \in \mathbb{N} \} \). Každý polynom je konečný součet s celočíselnými koeficienty.
Každý polynom lze jednoznačně reprezentovat jako konečnou posloupnost celých čísel \( (a_0, a_1, \ldots, a_n) \), kde pouze konečný počet z nich je nenulových. Množina všech konečných posloupností celých čísel je spočetná, protože:
1. Množina \( \mathbb{Z} \) je spočetná.
2. Množina všech konečných posloupností z \( \mathbb{Z} \) je sjednocením množin \( \mathbb{Z}^n \) pro všechna \( n \in \mathbb{N} \).
3. Každá množina \( \mathbb{Z}^n \) je spočetná (dokazuje se indukcí nebo pomocí bijekce s \( \mathbb{N} \)).
4. Spočetné sjednocení spočetných množin je opět spočetné.
Z toho plyne, že množina všech polynomů s celočíselnými koeficienty je spočetná.
Závěr: Množina všech polynomů s celočíselnými koeficienty a jednou proměnnou je spočetná.
14. Je množina všech iracionálních čísel spočetná?
Řešení příkladu:
Označme množinu všech iracionálních čísel jako \( I = \mathbb{R} \setminus \mathbb{Q} \). Víme, že \( \mathbb{R} \) je nespočetná množina a \( \mathbb{Q} \) je spočetná množina.
Uvažujme, že pokud bychom od nespočetné množiny \( \mathbb{R} \) odečetli spočetnou množinu \( \mathbb{Q} \), dostaneme množinu \( I \), která zůstává nespočetná. Odebrání spočetné množiny z nespočetné nemění její mohutnost.
Dále si lze představit, že mezi libovolnými dvěma reálnými čísly existuje nekonečně mnoho iracionálních čísel. Například mezi 0 a 1 najdeme číselně mnoho čísel jako \( \sqrt{2}/2, \pi/4, e/3 \), která nejsou racionální.
Závěr: Množina všech iracionálních čísel je nespočetná.
15. Je množina všech konečných posloupností z množiny \( \mathbb{N} \) spočetná?
Řešení příkladu:
Každá konečná posloupnost z \( \mathbb{N} \) může být reprezentována jako uspořádaná n-tice \( (a_1, a_2, \ldots, a_n) \), kde \( n \in \mathbb{N} \) a každý \( a_i \in \mathbb{N} \). Množina všech takových n-tic pro pevné \( n \) je \( \mathbb{N}^n \), což je spočetná množina.
Pak je množina všech konečných posloupností sjednocením všech \( \mathbb{N}^n \) pro \( n \in \mathbb{N} \):
\( S = \bigcup_{n = 1}^{\infty} \mathbb{N}^n \)
Každá \( \mathbb{N}^n \) je spočetná a spočetné sjednocení spočetných množin je opět spočetná množina. Proto i množina všech konečných posloupností z \( \mathbb{N} \) je spočetná.
Závěr: Množina všech konečných posloupností z \( \mathbb{N} \) je spočetná.
16. Určete, zda je množina všech racionálních čísel mezi \(0\) a \(1\) spočetná.
Řešení příkladu:
Nejprve uvažujme definici racionálního čísla. Každé racionální číslo lze zapsat ve tvaru \( \frac{p}{q} \), kde \( p \in \mathbb{Z} \), \( q \in \mathbb{N} \) a \( q \ne 0 \). V intervalu \( (0,1) \) jsou pouze taková racionální čísla, u kterých je \( 0 < \frac{p}{q} < 1 \), což znamená, že \( 0 < p < q \).
Pro každé pevné \( q \in \mathbb{N} \), \( q \geq 2 \), existuje konečně mnoho takových \( p \), že \( 0 < p < q \), a \( \frac{p}{q} \) je v základním tvaru (tedy \( \gcd(p, q) = 1 \)). Označme tuto množinu jako \( A_q = \left\{ \frac{p}{q} \mid 1 \leq p < q,\ \gcd(p,q) = 1 \right\} \). Množina všech racionálních čísel mezi 0 a 1 je sjednocením všech těchto množin:
\( A = \bigcup_{q=2}^{\infty} A_q \)
Každá množina \( A_q \) je konečná a protože spočetné sjednocení konečných (nebo spočetných) množin je spočetné, plyne, že množina \( A \) je spočetná. Jinými slovy: existuje očíslování všech racionálních čísel mezi 0 a 1 tak, že každému lze přiřadit přirozené číslo.
Závěr: Množina všech racionálních čísel mezi 0 a 1 je spočetná.
17. Je množina všech nekonečných binárních posloupností spočetná?
Řešení příkladu:
Množina všech nekonečných binárních posloupností je množina všech funkcí \( f: \mathbb{N} \to \{0,1\} \). Každá taková posloupnost odpovídá nekonečné sekvenci nul a jedniček, například: \( (0,1,1,0,1,\ldots) \).
Představme si, že každá binární posloupnost reprezentuje binární zápis reálného čísla v intervalu \( [0,1] \). Každou takovou posloupnost lze tedy ztotožnit s číslem:
\( x = \sum_{n=1}^{\infty} \frac{a_n}{2^n} \), kde \( a_n \in \{0,1\} \)
Tímto způsobem lze definovat bijekci mezi množinou všech nekonečných binárních posloupností a podmnožinou reálných čísel z intervalu \( [0,1] \). Jelikož množina \( \mathbb{R} \) je nespočetná a existuje bijekce s binárními posloupnostmi, je i množina všech nekonečných binárních posloupností nespočetná.
Závěr: Množina všech nekonečných binárních posloupností není spočetná, ale nespočetná.
18. Mějme množinu všech podmnožin množiny přirozených čísel. Je tato množina spočetná?
Řešení příkladu:
Množina všech podmnožin množiny \( \mathbb{N} \) se nazývá potenční množina \( \mathcal{P}(\mathbb{N}) \). Každou podmnožinu lze charakterizovat pomocí charakteristické funkce \( \chi_A : \mathbb{N} \to \{0,1\} \), kde \( \chi_A(n) = 1 \), pokud \( n \in A \), a \( 0 \), pokud \( n \notin A \).
Tím vzniká korespondence mezi podmnožinami \( \mathbb{N} \) a nekonečnými binárními posloupnostmi. Ukázali jsme již v předchozím příkladu, že množina všech nekonečných binárních posloupností je nespočetná. Proto i množina všech podmnožin \( \mathbb{N} \) je nespočetná.
Závěr: Množina všech podmnožin množiny \( \mathbb{N} \) je nespočetná.
19. Je množina všech konečných řetězců nad abecedou \( \{a, b\} \) spočetná?
Řešení příkladu:
Nejprve si definujme, co je konečný řetězec. Každý konečný řetězec nad abecedou \( \{a, b\} \) je konečná posloupnost symbolů \( a \) a \( b \), například \( aab \), \( babba \), \( \varepsilon \) (prázdný řetězec) apod.
Pro každý délkový stupeň \( n \in \mathbb{N}_0 \) (včetně 0) je počet všech řetězců délky \( n \) roven \( 2^n \). Množina všech konečných řetězců tedy vzniká jako sjednocení množin řetězců všech délek:
\( L = \bigcup_{n=0}^{\infty} \{a, b\}^n \)
Každá množina \( \{a, b\}^n \) obsahuje konečně mnoho řetězců (konkrétně \( 2^n \)), a sjednocení spočetně mnoha konečných množin je spočetná množina. Navíc lze jednotlivé řetězce očíslovat například lexikograficky: \( \varepsilon, a, b, aa, ab, ba, bb, aaa, \ldots \).
Závěr: Množina všech konečných řetězců nad abecedou \( \{a, b\} \) je spočetná.
20. Určete, zda množina všech konečných podmnožin množiny \( \mathbb{N} \) je spočetná.
Řešení příkladu:
Každou konečnou podmnožinu množiny \( \mathbb{N} \) lze chápat jako konečný výběr prvků z \( \mathbb{N} \), tj. jako konečnou množinu čísel \( \{n_1, n_2, \ldots, n_k\} \), kde \( n_i \in \mathbb{N} \), \( k \in \mathbb{N} \). Existuje nekonečně mnoho takových množin, ale každá z nich je konečná.
Množinu všech konečných podmnožin lze popsat jako sjednocení všech množin k-prvkových podmnožin pro každé \( k \in \mathbb{N} \):
\( \bigcup_{k=1}^{\infty} \{ A \subseteq \mathbb{N} \mid |A| = k \} \)
Každá množina k-prvkových podmnožin \( \mathbb{N} \) je spočetná. To lze ukázat pomocí toho, že každou takovou množinu lze jednoznačně kódovat pomocí vzestupně uspořádané k-tice přirozených čísel, což je množina izomorfní s podmnožinou \( \mathbb{N}^k \). Množina \( \mathbb{N}^k \) je spočetná, a tedy i její podmnožina je spočetná.
Sjednocení spočetně mnoha spočetných množin je opět spočetná množina.
Závěr: Množina všech konečných podmnožin množiny \( \mathbb{N} \) je spočetná.
21. Je množina všech aritmetických posloupností s celočíselnými členy spočetná?
Řešení příkladu:
Aritmetická posloupnost je určena prvním členem \( a \in \mathbb{Z} \) a diferencí \( d \in \mathbb{Z} \), tedy má tvar:
\( a, a + d, a + 2d, a + 3d, \ldots \)
Každá aritmetická posloupnost s celočíselnými členy je tedy jednoznačně určena dvojicí \( (a, d) \in \mathbb{Z} \times \mathbb{Z} \). Tím pádem existuje zřejmá bijekce mezi množinou všech aritmetických posloupností a množinou \( \mathbb{Z} \times \mathbb{Z} \).
Množina \( \mathbb{Z} \) je spočetná a kartézský součin dvou spočetných množin je opět spočetný, protože existuje bijekce \( f: \mathbb{N} \to \mathbb{Z} \times \mathbb{Z} \) například pomocí diagonálního číslování (Cantorovo diagonální uspořádání).
Závěr: Množina všech aritmetických posloupností s celočíselnými členy je spočetná, protože je v bijekci se spočetnou množinou \( \mathbb{Z} \times \mathbb{Z} \).
22. Určete, zda je množina všech racionálních čísel se sudým jmenovatelem spočetná.
Řešení příkladu:
Uvažujme množinu všech racionálních čísel \( \frac{p}{q} \), kde \( p \in \mathbb{Z} \), \( q \in \mathbb{N} \) a \( q \) je sudé číslo. Jmenovatel tedy patří do množiny sudých čísel: \( q \in \{2, 4, 6, 8, \ldots\} \).
Pro každý pevný sudý jmenovatel \( q = 2k \), kde \( k \in \mathbb{N} \), existuje spočetně mnoho čitatelů \( p \in \mathbb{Z} \), takže odpovídající zlomek \( \frac{p}{q} \) je racionální číslo se sudým jmenovatelem.
Formálně lze psát:
\( A = \bigcup_{k=1}^{\infty} \left\{ \frac{p}{2k} \mid p \in \mathbb{Z} \right\} \)
Každá množina \( \left\{ \frac{p}{2k} \mid p \in \mathbb{Z} \right\} \) je spočetná (protože \( \mathbb{Z} \) je spočetná) a sjednocení spočetně mnoha spočetných množin je opět spočetné.
Závěr: Množina všech racionálních čísel se sudým jmenovatelem je spočetná.
23. Je množina všech posloupností z \( \mathbb{N} \), které jsou nakonec konstantní, spočetná?
Řešení příkladu:
Posloupnost \( (a_n)_{n \in \mathbb{N}} \) je nazývána nakonec konstantní, pokud existuje index \( N \in \mathbb{N} \), že pro všechna \( n \geq N \) platí \( a_n = c \) pro nějaké pevné \( c \in \mathbb{N} \).
Každou takovou posloupnost lze rozdělit na dvě části: první konečná část délky \( N \), kde se mohou hodnoty měnit, a druhá část od \( N \) dále, kde jsou všechny hodnoty rovny nějakému číslu \( c \in \mathbb{N} \).
Počet všech konečných posloupností (různých hodnot) délky \( N \) s hodnotami v \( \mathbb{N} \) je spočetný (protože \( \mathbb{N}^N \) je spočetná množina pro každé \( N \)). Počet všech takových možných zakončení (hodnoty \( c \)) je rovněž spočetný.
Takže pro každé \( N \in \mathbb{N} \) a každé zakončení \( c \in \mathbb{N} \) existuje spočetně mnoho nakonec konstantních posloupností. Sjednocení všech takových možností přes všechna \( N \in \mathbb{N} \) a všechna \( c \in \mathbb{N} \) dává opět spočetnou množinu.
Závěr: Množina všech nakonec konstantních posloupností přirozených čísel je spočetná.
24. Určete, zda je množina všech algebraických čísel spočetná.
Řešení příkladu:
Algebraické číslo je takové komplexní číslo, které je kořenem nějakého neidenticky nulového polynomu s celočíselnými koeficienty, tj. existuje polynom:
\( f(x) = a_0 + a_1 x + a_2 x^2 + \ldots + a_n x^n \in \mathbb{Z}[x] \)
takový, že \( f(\alpha) = 0 \).
Množinu všech polynomů s celočíselnými koeficienty lze identifikovat s množinou konečných posloupností čísel z \( \mathbb{Z} \), tedy s množinou \( \bigcup_{n=1}^\infty \mathbb{Z}^{n+1} \), což je spočetná množina (každý vektor je konečné délky a \( \mathbb{Z} \) je spočetná).
Každý takový polynom má nejvýše tolik kořenů, kolik je jeho stupeň. To znamená, že množina všech kořenů všech takových polynomů je spočetné sjednocení konečných množin, a proto je také spočetná.
Závěr: Množina všech algebraických čísel je spočetná.
25. Je množina všech iracionálních čísel spočetná?
Řešení příkladu:
Reálná čísla \( \mathbb{R} \) tvoří nespočetnou množinu. Racionální čísla \( \mathbb{Q} \) tvoří spočetnou podmnožinu \( \mathbb{R} \).
Iracionální čísla definujeme jako doplněk množiny \( \mathbb{Q} \) v množině \( \mathbb{R} \):
\( \mathbb{R} \setminus \mathbb{Q} \)
Kdyby množina všech iracionálních čísel byla spočetná, pak by množina \( \mathbb{R} = \mathbb{Q} \cup (\mathbb{R} \setminus \mathbb{Q}) \) byla sjednocením dvou spočetných množin, a tedy také spočetná.
To však je v rozporu s tím, že \( \mathbb{R} \) je nespočetná množina, což bylo dokázáno např. Cantorovým diagonálním důkazem. Tedy náš předpoklad je chybný.
Závěr: Množina všech iracionálních čísel je nespočetná.
26. Je množina všech uzavřených intervalů s racionálními krajními body podmnožinou spočetné množiny?
Řešení příkladu:
Každý uzavřený interval lze zapsat ve tvaru \( [a, b] \), kde \( a, b \in \mathbb{Q} \) a \( a \leq b \). Jelikož se omezujeme pouze na racionální čísla, všechny krajní body pocházejí ze spočetné množiny \( \mathbb{Q} \).
Každý takový interval je určen uspořádanou dvojicí \( (a, b) \), kde \( a \in \mathbb{Q} \), \( b \in \mathbb{Q} \), a \( a \leq b \). Nezahrnujeme tedy libovolné dvojice, ale pouze ty, kde první složka není větší než druhá.
Množina všech dvojic \( (a, b) \in \mathbb{Q} \times \mathbb{Q} \) je spočetná, protože kartézský součin dvou spočetných množin je opět spočetný.
Navíc množina všech dvojic \( (a, b) \) s podmínkou \( a \leq b \) je podmnožina množiny všech dvojic \( \mathbb{Q} \times \mathbb{Q} \), takže je rovněž spočetná (podmnožina spočetné množiny může být buď konečná, nebo spočetná).
Každý interval tedy odpovídá právě jedné takové dvojici. Existuje tedy zřejmá bijekce mezi množinou všech uzavřených intervalů s racionálními krajními body a podmnožinou \( \mathbb{Q} \times \mathbb{Q} \).
Závěr: Množina všech uzavřených intervalů s racionálními krajními body je spočetná, jelikož je podmnožinou spočetné množiny \( \mathbb{Q} \times \mathbb{Q} \).
27. Určete, zda je množina všech konečných podmnožin přirozených čísel spočetná.
Řešení příkladu:
Nechť \( \mathbb{N} \) je množina přirozených čísel. Hledáme množinu všech konečných podmnožin této množiny.
Pro každé \( n \in \mathbb{N} \) existuje konečný počet podmnožin velikosti právě \( n \), konkrétně tolik, kolik je možných výběrů \( n \) různých prvků z \( \mathbb{N} \). Tato množina výběrů je spočetná, protože:
Počet všech uspořádaných \( n \)-tic s různými prvky z \( \mathbb{N} \) je spočetný (jelikož \( \mathbb{N}^n \) je spočetné a filtrujeme jen konečné množství těch, co mají různé prvky).
Množinu všech konečných podmnožin \( \mathbb{N} \) tedy můžeme zapsat jako:
\( A = \bigcup_{n=0}^\infty \left\{ B \subseteq \mathbb{N} \mid |B| = n \right\} \)
Každá množina \( \left\{ B \subseteq \mathbb{N} \mid |B| = n \right\} \) je spočetná, a sjednocení spočetně mnoha spočetných množin je opět spočetné.
Závěr: Množina všech konečných podmnožin přirozených čísel je spočetná.
28. Je množina všech funkcí \( f: \mathbb{N} \to \{0,1\} \), které mají konečnou podporu, spočetná?
Řešení příkladu:
Podporou funkce \( f \) označujeme množinu \( \{n \in \mathbb{N} \mid f(n) \ne 0\} \). Říkáme, že funkce má konečnou podporu, pokud tato množina je konečná.
Funkce \( f: \mathbb{N} \to \{0,1\} \) s konečnou podporou má tedy pouze konečně mnoho hodnot rovno 1 a ostatní hodnoty jsou rovny 0.
Každou takovou funkci lze identifikovat s konečnou podmnožinou \( A \subseteq \mathbb{N} \), která obsahuje právě ty indexy, kde \( f(n) = 1 \). Zbytek funkcí je 0.
Proto je množina všech takových funkcí ekvivalentní s množinou všech konečných podmnožin \( \mathbb{N} \), což jsme již v předchozím příkladu dokázali, že je spočetná množina.
Závěr: Množina všech funkcí \( f: \mathbb{N} \to \{0,1\} \) s konečnou podporou je spočetná.
29. Je množina všech periodických posloupností z množiny \( \{0,1\} \) spočetná?
Řešení příkladu:
Periodická posloupnost je taková posloupnost \( (a_n) \), že existuje přirozené číslo \( p \) (perioda), pro které platí:
\( \forall n \in \mathbb{N} \quad a_{n+p} = a_n \)
Každou periodickou posloupnost lze zcela určit hodnotami na prvních \( p \) pozicích (při znalosti periody). Každá taková perioda je kladné přirozené číslo, a na prvních \( p \) místech mohou být libovolné hodnoty z množiny \( \{0,1\} \).
Pro každé pevné \( p \) existuje právě \( 2^p \) takových posloupností (všechny binární řetězce délky \( p \)). Množina všech periodických posloupností pak je:
\( \bigcup_{p=1}^\infty \{0,1\}^p \)
Každá množina \( \{0,1\}^p \) je konečná (konkrétně \( 2^p \) prvků), a sjednocení spočetně mnoha konečných množin je spočetná množina.
Závěr: Množina všech periodických posloupností z množiny \( \{0,1\} \) je spočetná.
30. Určete, zda množina všech nekonečných podmnožin množiny \( \mathbb{N} \) je spočetná nebo nespočetná.
Řešení příkladu:
Celkový počet všech podmnožin množiny \( \mathbb{N} \) je \( 2^{\aleph_0} \), tedy nespočetně mnoho (stejná mohutnost jako reálná čísla).
Množina všech konečných podmnožin \( \mathbb{N} \) je spočetná, jak jsme si dokázali v předchozích příkladech.
Doplněk této množiny — tj. množina všech nekonečných podmnožin \( \mathbb{N} \) — je potom roven:
\( \mathcal{P}(\mathbb{N}) \setminus \{ \text{všechny konečné podmnožiny} \} \)
Spočetná množina odebraná z nespočetné množiny stále zůstává nespočetná.
Závěr: Množina všech nekonečných podmnožin \( \mathbb{N} \) je nespočetná.
31. Je množina všech řetězců nad abecedou \( \{a, b\} \), které mají délku menší než \(1000\), spočetná?
Řešení příkladu:
Řetězec délky \( n \) nad abecedou \( \{a, b\} \) je uspořádaná \( n \)-tice prvků, kde každý prvek je buď \( a \), nebo \( b \). Počet všech možných řetězců délky \( n \) je tedy \( 2^n \).
Hledáme množinu všech řetězců, které mají délku menší než 1000, tedy množinu:
\( A = \bigcup_{n=0}^{999} \{a, b\}^n \)
Každá množina \( \{a, b\}^n \) obsahuje právě \( 2^n \) prvků, což je konečný počet. Sjednocujeme konečně mnoho konečných množin, což je konečná množina.
Přesněji, celkový počet prvků je:
\( \sum_{n=0}^{999} 2^n \)
Tato suma je konečná, protože má pouze 1000 členů. Výsledkem je konečné číslo.
Závěr: Množina všech řetězců nad \( \{a, b\} \) s délkou menší než 1000 je konečná, tedy triviálně i spočetná.
32. Ukažte, že množina všech racionálních čísel mezi \(0\) a \(1\) je spočetná.
Řešení příkladu:
Racionální číslo mezi 0 a 1 lze vyjádřit jako zlomek \( \frac{m}{n} \), kde \( m, n \in \mathbb{N} \), \( m < n \) a \( \gcd(m,n) = 1 \). Tyto zlomky představují právě racionální čísla v intervalu \( (0,1) \).
Množinu všech těchto zlomků můžeme indexovat uspořádanými dvojicemi \( (m, n) \), kde \( m < n \), \( m, n \in \mathbb{N} \). Takových dvojic je spočetně mnoho, protože:
\( \mathbb{N} \times \mathbb{N} \) je spočetná množina a podmnožina této množiny, kde \( m < n \), je opět spočetná.
Každé racionální číslo mezi 0 a 1 má tedy odpovídající dvojici \( (m,n) \). Navíc, zlomky lze zapsat v základním tvaru, takže každé racionální číslo má pouze jeden základní tvar, což zajišťuje jednoznačnost.
Pro vytvoření bijekce s \( \mathbb{N} \) lze tyto zlomky uspořádat např. podle součtu \( m+n \), podobně jako ve slavné Cantorově diagonální konstrukci.
Závěr: Množina všech racionálních čísel v intervalu \( (0,1) \) je spočetná, protože lze zavést bijekci mezi touto množinou a množinou přirozených čísel.
33. Mějme množinu všech polynomů s racionálními koeficienty. Je tato množina spočetná?
Řešení příkladu:
Polynom lze zapsat jako:
\( f(x) = a_0 + a_1x + a_2x^2 + \dots + a_nx^n \)
kde \( a_i \in \mathbb{Q} \) a \( n \in \mathbb{N} \). Každý polynom má tedy konečný počet racionálních koeficientů.
Pro daný stupeň \( n \) tvoří koeficienty \( (a_0, a_1, \dots, a_n) \) prvek množiny \( \mathbb{Q}^{n+1} \), což je spočetná množina (kartézský součin konečného počtu spočetných množin je spočetný).
Množina všech polynomů je sjednocení přes všechny stupně:
\( \bigcup_{n=0}^\infty \mathbb{Q}^{n+1} \)
Každá množina \( \mathbb{Q}^{n+1} \) je spočetná, a spočetné sjednocení spočetných množin je opět spočetné.
Závěr: Množina všech polynomů s racionálními koeficienty je spočetná.
34. Je množina všech konečných posloupností celých čísel spočetná?
Řešení příkladu:
Konečná posloupnost celých čísel délky \( n \) je uspořádaná \( n \)-tice prvků z množiny \( \mathbb{Z} \). Tedy každá taková posloupnost je prvek množiny \( \mathbb{Z}^n \).
Jelikož \( \mathbb{Z} \) je spočetná množina, tak i \( \mathbb{Z}^n \) je spočetná pro každé \( n \in \mathbb{N} \).
Množina všech konečných posloupností je sjednocení množin \( \mathbb{Z}^n \) přes všechna \( n \):
\( \bigcup_{n=0}^\infty \mathbb{Z}^n \)
Každá \( \mathbb{Z}^n \) je spočetná a sjednocujeme spočetně mnoho spočetných množin, takže výsledek je spočetný.
Závěr: Množina všech konečných posloupností celých čísel je spočetná.
35. Je množina všech podmnožin množiny všech konečných slov nad abecedou \( \{0,1\} \) spočetná?
Řešení příkladu:
Nejprve zjistíme, kolik je všech konečných slov nad \( \{0,1\} \). Tato množina je spočetná, neboť ji lze popsat jako:
\( \bigcup_{n=0}^\infty \{0,1\}^n \)
Každá \( \{0,1\}^n \) je konečná množina o \( 2^n \) prvcích, a spočetné sjednocení konečných množin je spočetné.
Označme tuto množinu jako \( S \). Platí tedy, že \( S \) je spočetná.
Hledáme množinu všech podmnožin \( \mathcal{P}(S) \). Pokud je \( S \) spočetná, pak její potenční množina \( \mathcal{P}(S) \) má mohutnost \( 2^{\aleph_0} \), což je stejná mohutnost jako množina reálných čísel.
Závěr: Množina všech podmnožin množiny všech konečných slov nad \( \{0,1\} \) je nespočetná.
36. Je množina všech prvočísel konečná, spočetná nebo nespočetná?
Řešení příkladu:
Nejprve si ujasněme, co znamená pojem prvočíslo. Prvočíslo je takové přirozené číslo větší než 1, které má právě dva dělitele: 1 a samo sebe.
Množinu všech prvočísel značíme často \( \mathbb{P} \). Například: \( 2, 3, 5, 7, 11, \dots \)
Otázkou je, zda je množina \( \mathbb{P} \) konečná, spočetná nebo nespočetná.
1. Konečnost můžeme hned vyloučit. Již Eukleidés ve starověku dokázal, že prvočísel je nekonečně mnoho. Důkaz je elegantní:
Předpokládejme, že existuje pouze konečně mnoho prvočísel \( p_1, p_2, \dots, p_n \). Zkonstruujme číslo \( N = p_1 \cdot p_2 \cdot \dots \cdot p_n + 1 \). Číslo \( N \) není dělitelné žádným z uvedených prvočísel (vždy zůstane zbytek 1), takže je buď nové prvočíslo, nebo má prvočíselný dělitel, který není v seznamu. To je spor. \Rightarrow prvočísel je nekonečně mnoho.
2. Nyní zvažme, zda je \( \mathbb{P} \) spočetná.
Množina všech přirozených čísel \( \mathbb{N} \) je spočetná. Jelikož \( \mathbb{P} \subseteq \mathbb{N} \), a jde o nekonečnou podmnožinu spočetné množiny, je \( \mathbb{P} \) také spočetná.
Závěr: Množina všech prvočísel je nekonečná a spočetná.
37. Ukažte, že množina všech párných celých čísel je spočetná.
Řešení příkladu:
Párná celá čísla tvoří podmnožinu celých čísel \( \mathbb{Z} \). Jsou to čísla ve tvaru \( 2k \), kde \( k \in \mathbb{Z} \). Například: \( \dots, -4, -2, 0, 2, 4, \dots \)
Množinu těchto čísel označíme jako \( P = \{ x \in \mathbb{Z} \mid x \equiv 0 \mod 2 \} \).
Pro zjištění, zda je množina \( P \) spočetná, hledáme bijekci mezi \( \mathbb{Z} \) a \( P \).
Definujme zobrazení \( f: \mathbb{Z} \to P \) předpisem \( f(k) = 2k \). Zkontrolujme vlastnosti tohoto zobrazení:
– Surjektivita: Pro každé párné číslo \( p \in P \) existuje \( k = \frac{p}{2} \in \mathbb{Z} \), takže \( f(k) = p \).
– Injektivita: Pokud \( f(k_1) = f(k_2) \), pak \( 2k_1 = 2k_2 \Rightarrow k_1 = k_2 \).
Funkce \( f \) je tedy bijekcí.
Závěr: Množina všech párných celých čísel je spočetná.
38. Dokažte, že kartézský součin dvou spočetných množin je opět spočetný.
Řešení příkladu:
Nechť \( A \) a \( B \) jsou spočetné množiny. To znamená, že existují bijekce \( f: \mathbb{N} \to A \), \( g: \mathbb{N} \to B \).
Chceme ukázat, že \( A \times B \) je spočetná množina, tj. že existuje bijekce \( h: \mathbb{N} \to A \times B \).
Nechť \( A = \{ a_0, a_1, a_2, \dots \} \), \( B = \{ b_0, b_1, b_2, \dots \} \). Pak všechny uspořádané dvojice \( (a_i, b_j) \) můžeme uspořádat do mřížky (nekonečné matice).
Uspořádáme dvojice podle součtu indexů \( i + j \):
– součet 0: \( (a_0, b_0) \)
– součet 1: \( (a_0, b_1), (a_1, b_0) \)
– součet 2: \( (a_0, b_2), (a_1, b_1), (a_2, b_0) \)
… a tak dále. Každý prvek \( (a_i, b_j) \) se v tomto pořadí objeví právě jednou.
Tímto způsobem lze očíslovat prvky množiny \( A \times B \) přirozenými čísly, což je přesně bijekce s \( \mathbb{N} \).
Závěr: Kartézský součin dvou spočetných množin je spočetný.
39. Mějme množinu všech přirozených čísel, která jsou druhými mocninami celých čísel. Je tato množina spočetná?
Řešení příkladu:
Definujeme množinu:
\( M = \{ n \in \mathbb{N} \mid n = k^2 \text{ pro nějaké } k \in \mathbb{Z} \} \)
Každé celé číslo má druhou mocninu, která je kladná (nebo nula), tedy prvkem \( \mathbb{N} \).
Například: \( (-3)^2 = 9 \), \( 0^2 = 0 \), \( 4^2 = 16 \). Množina všech druhých mocnin celých čísel je množina:
\( \{0^2, 1^2, (-1)^2, 2^2, (-2)^2, \dots\} = \{0, 1, 4, 9, 16, 25, \dots\} \)
Každý prvek této množiny je jednoznačně určen nějakým \( k \in \mathbb{N} \). Navíc existuje funkce \( f(k) = k^2 \), která zobrazuje \( \mathbb{N} \) do množiny druhých mocnin.
Funkce je surjektivní a každý prvek má konečně mnoho preobrazů (například \( 9 \) má \( 3 \) a \( -3 \)).
Proto lze vytvořit bijekci mezi \( \mathbb{N} \) a \( M \) — buď přímo, nebo pomocí indexace.
Závěr: Množina všech druhých mocnin celých čísel je spočetná.
40. Ukažte, že množina všech konečných množin přirozených čísel je spočetná.
Řešení příkladu:
Označme \( \mathcal{F} \) jako množinu všech konečných podmnožin \( \mathbb{N} \).
Každou konečnou množinu lze zapsat jako uspořádanou množinu s rostoucími prvky: například \( \{2, 5, 7\} \). Takových množin je spočetně mnoho, protože:
1. Množina všech množin s právě jedním prvkem \( \{n\} \), kde \( n \in \mathbb{N} \), je spočetná.
2. Množina všech množin se dvěma prvky \( \{i,j\} \) pro \( i < j \) je podmnožina \( \mathbb{N} \times \mathbb{N} \), což je spočetné.
3. Podobně pro každé pevné \( k \), je množina všech množin s \( k \) prvky spočetná.
Množina všech konečných podmnožin je sjednocením přes všechna \( k \):
\( \mathcal{F} = \bigcup_{k=0}^\infty \mathcal{P}_k(\mathbb{N}) \), kde \( \mathcal{P}_k \) značí podmnožiny s \( k \) prvky.
Každá \( \mathcal{P}_k(\mathbb{N}) \) je spočetná, protože lze přirozeně očíslovat každou takovou množinu.
Spočetné sjednocení spočetných množin je opět spočetné.
Závěr: Množina všech konečných podmnožin \( \mathbb{N} \) je spočetná.
41. Proveďte podrobný důkaz, že každá konečná množina je spočetná.
Řešení příkladu:
Nejprve si připomeňme definice:
– Množina je konečná, pokud existuje nějaké přirozené číslo \( n \), že množina má právě \( n \) prvků.
– Množina je spočetná, pokud existuje bijekce mezi množinou a množinou přirozených čísel nebo její konečnou podmnožinou.
Chceme tedy ukázat, že každá konečná množina je spočetná. To znamená, že pokud množina \( A \) má právě \( n \) prvků, pak existuje bijekce \( f: A \to \{1, 2, \dots, n\} \subseteq \mathbb{N} \).
Postup:
1. Označíme množinu \( A = \{a_1, a_2, \dots, a_n\} \).
2. Definujeme zobrazení \( f: A \to \{1, 2, \dots, n\} \) tak, že \( f(a_i) = i \) pro \( i = 1, \dots, n \).
3. Toto zobrazení je bijekce, protože:
- je injektivní – různé prvky \( a_i \neq a_j \) mají různá obrazy \( f(a_i) \neq f(a_j) \),
- je surjektivní – každý prvek \( k \in \{1, \dots, n\} \) je obrazem právě jednoho prvku \( a_k \in A \).
Tím jsme explicitně ukázali, že pro konečnou množinu existuje bijekce na konečnou podmnožinu přirozených čísel.
Proto je každá konečná množina spočetná, protože spočetná množina zahrnuje i konečné množiny.
Tento jednoduchý, avšak klíčový fakt se využívá při dalších úvahách o konečných a spočetných množinách.
42. Je množina všech funkcí z konečné množiny \( A = \{1, 2, \dots, n\} \) do konečné množiny \( B \) konečná nebo spočetná? Důkladně vysvětlete.
Řešení příkladu:
Nechť \( A = \{1, 2, \dots, n\} \) je konečná množina s \( n \) prvky a \( B \) je konečná množina s \( m \) prvky.
Otázka je, jak velká je množina všech funkcí \( F = \{ f \mid f: A \to B \} \).
Nejprve si uvědomme, že funkce \( f \) je určena hodnotami \( f(1), f(2), \dots, f(n) \), kde každá z nich je prvek množiny \( B \).
Tedy každá funkce odpovídá n-tici prvků z \( B \):
\( (f(1), f(2), \dots, f(n)) \in B^n \)
Protože \( |B| = m \), existuje \( m \) možností pro každý prvek \( f(i) \), a tak celkem:
\( |F| = m^n \)
Jelikož \( m \) a \( n \) jsou konečná čísla, \( m^n \) je také konečné číslo.
Závěr:
Množina všech funkcí z konečné množiny do konečné množiny je konečná množina s \( m^n \) prvky.
Tento výsledek je důležitý pro pochopení kartézských mocnin a funkčních prostorů nad konečnými množinami.
43. Ukažte, že množina všech posloupností přirozených čísel s konečným počtem nenulových prvků je spočetná.
Řešení příkladu:
Množina \( S \) všech posloupností \( (a_1, a_2, a_3, \dots) \), kde \( a_i \in \mathbb{N} \), a současně pouze konečně mnoho \( a_i \) je nenulových, označíme jako:
\( S = \{ (a_i)_{i=1}^\infty \mid \exists N \in \mathbb{N} : \forall i > N, a_i = 0 \} \)
To znamená, že každá posloupnost v \( S \) má tvar, kde za nějakým indexem \( N \) jsou všechny hodnoty nulové.
Každou takovou posloupnost lze jednoznačně identifikovat s konečným vektorem délky \( N \), protože prvky od \( N+1 \) jsou nulové.
Tedy množinu \( S \) lze vyjádřit jako sjednocení množin všech konečných vektorů různé délky:
\( S = \bigcup_{N=0}^\infty \mathbb{N}^N \)
Kde \( \mathbb{N}^N \) označuje množinu všech \( N \)-ticí přirozených čísel.
Pro pevné \( N \) je množina \( \mathbb{N}^N \) spočetná, protože je kartézským součinem spočetně mnoha množin \( \mathbb{N} \) (konkrétně \( N \)-krát), a kartézský součin spočetných množin je spočetný (viz příklad 38).
Sjednocení spočetně mnoha spočetných množin je opět spočetné.
Závěr:
Množina všech posloupností s konečným počtem nenulových prvků je spočetná.
Tento fakt je základem pro konstrukci různých typů řad a funkcí s konečným počtem nenulových hodnot.
44. Ukažte, že množina všech konečných slov nad konečnou abecedou je spočetná.
Řešení příkladu:
Nechť \( \Sigma \) je konečná abeceda s \( m \) znaky. Množina všech slov délky \( n \) nad touto abecedou je \( \Sigma^n \), tedy množina všech posloupností délky \( n \) z prvků \( \Sigma \).
Velikost \( \Sigma^n \) je \( m^n \), tedy konečné číslo.
Množina všech konečných slov nad \( \Sigma \) je sjednocením přes všechny délky:
\( W = \bigcup_{n=0}^\infty \Sigma^n \)
Každá \( \Sigma^n \) je konečná, takže sjednocení spočetně mnoha konečných množin.
Sjednocení spočetně mnoha konečných množin může být spočetné nebo nespočetné? Zde platí, že sjednocení spočetně mnoha konečných množin je spočetné, pokud každá z nich je konečná a všechny jsou spočetně mnoho.
Provedeme očíslování slov:
1. Seřadíme slova podle délky.
2. Pro každou délku \( n \) jsou slova uspořádána lexikograficky.
Tímto způsobem lze vytvořit explicitní bijekci mezi \( W \) a \( \mathbb{N} \).
Závěr:
Množina všech konečných slov nad konečnou abecedou je spočetná.
Tento výsledek je klíčový v teorii formálních jazyků a teorii automatů.
45. Mějme množinu všech racionálních čísel \( \mathbb{Q} \). Proveďte podrobný důkaz, že \( \mathbb{Q} \) je spočetná.
Řešení příkladu:
Množina racionálních čísel \( \mathbb{Q} \) je definována jako množina všech čísel, která lze vyjádřit jako poměr dvou celých čísel, kde jmenovatel je různý od nuly:
\( \mathbb{Q} = \{ \frac{p}{q} \mid p \in \mathbb{Z}, q \in \mathbb{N}, q \neq 0 \} \)
Chceme ukázat, že \( \mathbb{Q} \) je spočetná množina.
Postup:
1. Nejprve si uvědomíme, že \( \mathbb{Z} \) je spočetná a \( \mathbb{N} \) je spočetná (důkaz viz předchozí příklady).
2. Protože \( \mathbb{Q} \) lze vnímat jako kartézský součin \( \mathbb{Z} \times \mathbb{N} \), kde každému prvku \((p,q)\) odpovídá racionální číslo \( \frac{p}{q} \), platí, že je třeba ukázat, že kartézský součin dvou spočetných množin je spočetný.
3. Kartézský součin spočetných množin \( \mathbb{Z} \times \mathbb{N} \) je spočetný. (To je známý fakt – například lze uspořádat prvky do dvourozměrné mřížky a pak je očíslovat po diagonálách.)
4. Nicméně racionální čísla se opakují, protože např. \( \frac{2}{4} = \frac{1}{2} \). Proto je potřeba omezit se na zlomky v základním tvaru.
5. Definujeme množinu:
\( Q‘ = \{ \frac{p}{q} \mid p, q \in \mathbb{Z}, q > 0, \gcd(p,q) = 1 \} \)
Každý racionální zlomek má právě jeden základní tvar v \( Q‘ \).
6. Množina \( Q‘ \) je podmnožinou \( \mathbb{Z} \times \mathbb{N} \), kde se navíc uplatňuje podmínka \( \gcd(p,q) = 1 \).
7. Podmnožina spočetné množiny může být spočetná nebo konečná, pokud není prázdná. V našem případě \( Q‘ \) není prázdná.
Závěr:
Množina všech racionálních čísel je spočetná, protože lze vyjádřit jako spočetnou podmnožinu kartézského součinu dvou spočetných množin.
Tento výsledek je základem pro teorii čísel a ukazuje zajímavý kontrast vůči množině reálných čísel, která je nespočetná.
46. Ukažte, že každá podmnožina konečné množiny je konečná a určete počet všech podmnožin dané konečné množiny.
Řešení příkladu:
Nejprve si připomeňme, co znamená, že množina je konečná:
Množina \( A \) je konečná, pokud existuje přirozené číslo \( n \), že \( A \) má právě \( n \) prvků. Označme tedy \( |A| = n \).
Chceme ukázat, že jakákoliv podmnožina \( B \subseteq A \) je rovněž konečná, a spočítat, kolik podmnožin množina \( A \) má.
Krok 1: Každá podmnožina konečné množiny je konečná
Protože \( A \) má konečně mnoho prvků, podmnožina \( B \subseteq A \) nemůže mít více prvků než \( A \), tedy \( |B| \leq n \). Jelikož je \( B \) podmnožinou, množina prvků \( B \) je buď prázdná, nebo obsahuje prvky z \( A \), ale ne více než \( n \).
Tedy podmnožina \( B \) musí být konečná, protože její počet prvků je nejvýše \( n \).
Krok 2: Počet všech podmnožin konečné množiny \( A \)
Každý prvek množiny \( A \) může být buď v podmnožině zahrnut, nebo nikoliv. Pro každý z \( n \) prvků tedy máme dvě možnosti.
Celkový počet podmnožin je tedy:
\( 2^n \)
To vyplývá z principu násobení, protože počet možností je \( 2 \times 2 \times \dots \times 2 = 2^n \).
Podrobnější důkaz:
Nechť \( A = \{a_1, a_2, \dots, a_n\} \). Pro každou podmnožinu \( B \subseteq A \) definujeme charakteristickou funkci \( \chi_B : A \to \{0,1\} \), kde
\( \chi_B(a_i) = \begin{cases} 1, & \text{pokud } a_i \in B \\ 0, & \text{pokud } a_i \notin B \end{cases} \)
Tato funkce jednoznačně odpovídá podmnožině \( B \) a naopak, každá taková funkce určuje právě jednu podmnožinu.
Množina všech funkcí \( A \to \{0,1\} \) má velikost \( 2^n \), protože pro každý z \( n \) prvků jsou 2 možnosti.
Tedy bijekce mezi množinou všech podmnožin \( P(A) \) a množinou funkcí \( A \to \{0,1\} \) znamená, že \( |P(A)| = 2^n \).
Závěr:
Každá podmnožina konečné množiny je konečná a celkový počet podmnožin konečné množiny \( A \) s \( n \) prvky je \( 2^n \).
47. Dokažte, že sjednocení konečně mnoha spočetných množin je spočetné, a ukažte na příkladu.
Řešení příkladu:
Nejprve si definujme, co znamená, že množina je spočetná:
Množina \( A \) je spočetná, pokud existuje bijekce mezi \( A \) a množinou přirozených čísel \( \mathbb{N} \) nebo s její konečnou podmnožinou.
Máme konečně mnoho spočetných množin \( A_1, A_2, \dots, A_k \), každá je spočetná.
Chceme ukázat, že jejich sjednocení
\( A = A_1 \cup A_2 \cup \dots \cup A_k \)
je také spočetné.
Krok 1: Spočetnost jednotlivých množin
Protože každá \( A_i \) je spočetná, existuje bijekce \( f_i: \mathbb{N} \to A_i \) nebo na konečnou podmnožinu \( \{1, \dots, n_i\} \to A_i \).
Krok 2: Konstrukce bijekce na sjednocení
Zkonstruujeme zobrazení \( F: \mathbb{N} \to A \) jako složení prvků všech \( A_i \) postupně, například:
1. Vypíšeme všechny prvky z \( A_1 \) v pořadí podle \( f_1 \).
2. Poté všechny prvky z \( A_2 \) podle \( f_2 \).
…
k. Nakonec všechny prvky z \( A_k \) podle \( f_k \).
Tímto způsobem zřejmě vyjmenujeme všechny prvky \( A \), protože \( A \) je sjednocení všech \( A_i \).
Krok 3: Dokázání spočetnosti
Pokud každá množina \( A_i \) má bijekci s částí \( \mathbb{N} \), pak sjednocení konečně mnoha takových množin má bijekci s konečným součtem těchto částí.
To je opět spočetná množina.
Příklad:
Nechť \( A_1 = \{2n \mid n \in \mathbb{N}\} \) – sudá čísla, a \( A_2 = \{2n + 1 \mid n \in \mathbb{N}\} \) – lichá čísla.
Obě množiny jsou spočetné, protože existuje bijekce \( f_1(n) = 2n \) a \( f_2(n) = 2n + 1 \).
Sjednocení \( A = A_1 \cup A_2 = \mathbb{N} \) je spočetné, což je zřejmé.
Závěr:
Sjednocení konečně mnoha spočetných množin je spočetná množina.
48. Pro množiny \( A = \{1, 2, 3\} \) a \( B = \mathbb{N} \) určete, zda je množina funkcí \( B \to A \) konečná, spočetná nebo nespočetná a zdůvodněte to.
Řešení příkladu:
Nejprve si uvědomme, že množina \( A = \{1, 2, 3\} \) je konečná s třemi prvky a množina \( B = \mathbb{N} \) je spočetná, ale nekonečná.
Hledáme množinu všech funkcí \( f : B \to A \), tedy množinu všech zobrazení, která každému přirozenému číslu přiřadí jeden z prvků \( A \).
Velikost této množiny funkcí je rovna počtu všech nekonečných posloupností, kde každý člen je z množiny \( A \).
Formálně lze říct, že množina všech funkcí \( B \to A \) má kardinalitu \( |A|^{|B|} \).
Známe, že \( |A| = 3 \) a \( |B| = \aleph_0 \) (kardinál nekonečné spočetné množiny).
Kardinální mocnina \( 3^{\aleph_0} \) je známý výraz, který odpovídá velikosti množiny všech funkcí z \( \mathbb{N} \) do tříprvkové množiny.
Je známo, že \( k^{\aleph_0} = 2^{\aleph_0} \) pro každé konečné \( k \geq 2 \), což je kardinál nespočetné množiny (tzv. kardinál kontinuua).
Tedy množina všech funkcí \( B \to A \) má stejnou velikost jako množina reálných čísel, je nespočetná.
Závěr:
Množina všech funkcí z \( \mathbb{N} \) do \( \{1,2,3\} \) je nespočetná.
49. Ukažte, že množina všech racionálních čísel \( \mathbb{Q} \) je spočetná.
Řešení příkladu:
Nejprve si připomeňme, že racionální čísla lze vyjádřit ve tvaru \( \frac{p}{q} \), kde \( p \in \mathbb{Z} \) a \( q \in \mathbb{N} \setminus \{0\} \).
Chceme ukázat, že množina všech takových zlomků je spočetná.
Krok 1: Množina celých čísel \( \mathbb{Z} \) je spočetná
To je známý fakt, protože existuje bijekce mezi \( \mathbb{Z} \) a \( \mathbb{N} \). Například lze rozumně seřadit čísla takto:
\( 0, 1, -1, 2, -2, 3, -3, \dots \)
Krok 2: Množina dvojic \( (p, q) \) s \( p \in \mathbb{Z} \), \( q \in \mathbb{N} \setminus \{0\} \) je spočetná
Množina \( \mathbb{Z} \times \mathbb{N} \) je kartézský součin dvou spočetných množin, a protože kartézský součin dvou spočetných množin je spočetný, i tato množina je spočetná.
Krok 3: Množina všech zlomků \( \frac{p}{q} \) je tedy spočetná nebo menší, protože každý zlomek je reprezentován nějakým párem \( (p,q) \).
Je však třeba vzít v úvahu, že několik různých párů může reprezentovat stejné racionální číslo (například \( \frac{2}{4} = \frac{1}{2} \)).
Proto je množina všech racionálních čísel výsledkem podílu množiny spočetných dvojic podle vztahu ekvivalence.
Protože množina ekvivalenčních tříd je podmnožinou množiny všech těchto dvojic, je také spočetná nebo menší.
Konečný závěr:
Množina \( \mathbb{Q} \) je spočetná.
50. Pro množinu \( A = \mathbb{N} \) určete, zda je množina všech konečných podmnožin \( A \) spočetná nebo nespočetná a proč.
Řešení příkladu:
Nechť \( A = \mathbb{N} \) je množina přirozených čísel.
Zajímá nás množina všech konečných podmnožin této množiny, označíme ji třeba \( \mathcal{F} \).
Chceme zjistit, zda je množina \( \mathcal{F} \) spočetná nebo nespočetná.
Krok 1: Každá konečná podmnožina je ohraničená nějakou maximální hodnotou.
Proto lze každou konečnou podmnožinu zařadit do nějaké množiny všech podmnožin s prvky maximálně do čísla \( n \), tedy do množiny všech podmnožin množiny \( \{1, 2, \dots, n\} \).
Krok 2: Množina všech podmnožin konečné množiny \( \{1, 2, \dots, n\} \) je konečná (má velikost \( 2^n \)), tedy spočetná.
Krok 3: Množina všech konečných podmnožin \( \mathcal{F} \) je sjednocení množin všech podmnožin konečných množin \( \{1, \dots, n\} \) pro všechna \( n \in \mathbb{N} \), tedy
\( \mathcal{F} = \bigcup_{n=1}^\infty P(\{1, 2, \dots, n\}) \)
Krok 4: Každá množina \( P(\{1, \dots, n\}) \) je spočetná (je konečná), a sjednocení spočetně mnoha spočetných množin je spočetné (viz předchozí příklad).
Závěr:
Množina všech konečných podmnožin \( \mathbb{N} \) je spočetná.
51. Dokažte, že sjednocení konečně mnoha konečných množin je konečná množina.
Řešení příkladu:
Nejprve si připomeňme definici konečné množiny. Množina je konečná, pokud existuje bijekce mezi touto množinou a množinou \(\{1, 2, …, n\}\) pro nějaké přirozené číslo \(n\). Cílem je tedy ukázat, že sjednocení konečně mnoha konečných množin je samo konečná množina.
Nechť máme konečný počet množin \(A_1, A_2, \dots, A_k\), kde každá \(A_i\) je konečná.
Potřebujeme dokázat, že množina \(S = A_1 \cup A_2 \cup \dots \cup A_k\) je konečná.
Krok 1: Odhad velikosti sjednocení
Protože každá množina \(A_i\) je konečná, existuje přirozené číslo \(n_i = |A_i|\). Množina \(S\) je podmnožinou množiny obsahující všechny prvky, které se vyskytují v kterékoli z množin \(A_i\).
Velikost sjednocení je tedy omezená zhora součtem velikostí jednotlivých množin:
\[ |S| = |A_1 \cup A_2 \cup \dots \cup A_k| \leq |A_1| + |A_2| + \dots + |A_k| = n_1 + n_2 + \dots + n_k. \]
Krok 2: Součet konečného počtu přirozených čísel je konečné číslo
Protože \(k\) je konečné a každé \(n_i\) je konečné přirozené číslo, jejich součet je také konečný.
Krok 3: Závěr
Tím je jasné, že množina \(S\) má konečný počet prvků, tedy je konečná.
Celkově jsme tedy dokázali, že sjednocení konečně mnoha konečných množin je konečná množina.
52. Ukažte, že každá konečná množina je spočetná.
Řešení příkladu:
V zadání je požadavek ukázat, že každá konečná množina je spočetná. Toto je základní vlastnost konečných množin, avšak podrobně si rozepíšeme, co spočetnost znamená a proč konečná množina tuto vlastnost splňuje.
Krok 1: Definice spočetnosti
Množina je spočetná, pokud existuje bijekce mezi touto množinou a množinou přirozených čísel \(\mathbb{N}\) nebo její podmnožinou. V praxi to znamená, že její prvky lze očíslovat pomocí přirozených čísel.
Krok 2: Konečná množina a její velikost
Pokud množina \(A\) je konečná, pak existuje přirozené číslo \(n\) takové, že je bijektivně ztotožnitelná s množinou \(\{1, 2, …, n\}\).
Krok 3: Vztah mezi konečnou množinou a spočetnou množinou
Množina \(\{1, 2, …, n\}\) je podmnožinou \(\mathbb{N}\) a je tedy spočetná (jelikož spočetná množina je právě taková, která je buď konečná nebo stejně veliká jako \(\mathbb{N}\)).
Krok 4: Závěr
Tím pádem je každá konečná množina spočetná, protože ji můžeme očíslovat pomocí prvků z \(\mathbb{N}\), konkrétně z množiny \(\{1, 2, …, n\}\).
Závěrem: Každá konečná množina je spočetná, protože její prvky lze jednoznačně očíslovat.
53. Ukažte, že kartézský součin konečně mnoha spočetných množin je spočetný.
Řešení příkladu:
Tento problém je klasickou úlohou z teorie množin a vyžaduje důkladnou znalost vlastností spočetných množin a jejich kartézských součinů.
Krok 1: Výchozí definice
Nechť máme konečný počet spočetných množin \(A_1, A_2, \dots, A_k\). Každá \(A_i\) je spočetná, tedy existuje bijekce \(f_i : \mathbb{N} \to A_i\).
Krok 2: Kartézský součin
Kartézský součin těchto množin je množina všech \(k\)-ticí \((a_1, a_2, \dots, a_k)\), kde \(a_i \in A_i\).
Krok 3: Ukážeme, že kartézský součin je spočetný
Protože každá množina \(A_i\) je spočetná, existuje očíslování jejích prvků pomocí přirozených čísel. Tedy každý prvek \(a_i\) můžeme přiřadit číslo \(n_i\) tak, že \(f_i(n_i) = a_i\).
Tedy kartézský součin můžeme ztotožnit s množinou všech \(k\)-ticí přirozených čísel \((n_1, n_2, \dots, n_k)\).
Krok 4: Spočetnost kartézského součinu přirozených čísel
Je známé, že kartézský součin konečně mnoha množin \(\mathbb{N}\) je spočetný. To lze ukázat například pomocí diagonálního uspořádání.
Krok 5: Závěr
Proto je kartézský součin konečně mnoha spočetných množin také spočetný.
54. Dokažte, že podmnožina spočetné množiny je konečná nebo spočetná.
Řešení příkladu:
Nechť \(A\) je spočetná množina a \(B \subseteq A\) je libovolná podmnožina.
Krok 1: Definice spočetné množiny
Protože \(A\) je spočetná, existuje buď bijekce nebo prostá funkce \(f : \mathbb{N} \to A\), která pokrývá všechny prvky \(A\).
Krok 2: Vlastnosti podmnožiny
Podmnožina \(B\) obsahuje některé prvky \(A\), tedy existuje podmnožina \(\mathbb{N}_B \subseteq \mathbb{N}\), která jsou indexy prvků zobrazených do \(B\) funkcí \(f\).
Krok 3: Podmnožina \(\mathbb{N}\) je buď konečná nebo spočetná
Každá podmnožina množiny přirozených čísel je konečná nebo spočetná, protože \(\mathbb{N}\) je spočetná a podmnožiny \(\mathbb{N}\) mají tyto vlastnosti.
Krok 4: Závěr
Protože existuje injektivní zobrazení z \(B\) do \(\mathbb{N}_B\), a \(\mathbb{N}_B\) je konečná nebo spočetná, pak i \(B\) je konečná nebo spočetná.
55. Ukažte, že množina všech konečných podmnožin spočetné množiny je spočetná.
Řešení příkladu:
Nechť \(A\) je spočetná množina. Zkoumáme množinu všech konečných podmnožin této množiny, označme ji \(F\).
Krok 1: Rozdělení množiny \(F\)
Množinu \(F\) lze rozdělit na sjednocení množin všech podmnožin pevné velikosti:
\[ F = \bigcup_{n=0}^\infty F_n, \]
kde \(F_n\) je množina všech podmnožin množiny \(A\) o velikosti \(n\).
Krok 2: Počet podmnožin pevné velikosti
Každé \(F_n\) je množina všech kombinací velikosti \(n\) z množiny \(A\). Protože \(A\) je spočetná, lze ukázat, že \(F_n\) je spočetná pro každé fixní \(n\).
Krok 3: Spočetnost sjednocení spočetných množin
Protože sjednocení spočetně mnoha spočetných množin je spočetné, je i \(F\) spočetná.
Krok 4: Závěr
Celkově tedy množina všech konečných podmnožin spočetné množiny je spočetná.
56. Dokažte, že množina všech všech konečných posloupností přirozených čísel je spočetná.
Řešení příkladu:
Nejprve si ujasníme, co znamená konečná posloupnost přirozených čísel. Konečná posloupnost délky \( n \) je uspořádaná n-tice prvků z \( \mathbb{N} \), tedy prvek z kartézského součinu \( \mathbb{N}^n \).
Naším úkolem je ukázat, že množina všech těchto konečných posloupností, tedy
\( S = \bigcup_{n=1}^\infty \mathbb{N}^n \),
je spočetná.
Krok 1: Množina \( \mathbb{N}^n \) je spočetná pro každé pevné \( n \).
Proč? Kartézský součin konečně mnoha spočetných množin je spočetný. To je dobře známý fakt, který lze ukázat např. pomocí indukce na \( n \). Konkrétně:
– Pro \( n=1 \) je \( \mathbb{N}^1 = \mathbb{N} \) jasně spočetná.
– Předpokládejme, že \( \mathbb{N}^k \) je spočetná. Potom \( \mathbb{N}^{k+1} = \mathbb{N}^k \times \mathbb{N} \) je kartézský součin spočetných množin, tedy opět spočetná.
Krok 2: Nyní zvažujeme sjednocení množiny \( S = \bigcup_{n=1}^\infty \mathbb{N}^n \).
Jedná se o spočetné sjednocení spočetných množin.
Z předchozí znalosti víme, že sjednocení spočetně mnoha spočetných množin je opět spočetná množina. Toto plyne z toho, že spočetnou rodinu spočetných množin lze očíslovat a následně vyjmenovat jejich prvky „prolínáním“ (např. pomocí diagonálního argumentu).
Proto je i množina všech konečných posloupností z \( \mathbb{N} \) spočetná.
Závěr:
Množina všech konečných posloupností přirozených čísel je spočetná.
57. Dokažte, že množina všech konečných podmnožin spočetné množiny je spočetná.
Řešení příkladu:
Nechť \( A \) je spočetná množina. Chceme dokázat, že množina všech konečných podmnožin \( A \), označme ji \( \mathcal{F} \), je spočetná.
Krok 1: Protože \( A \) je spočetná, existuje bijekce \( f: \mathbb{N} \to A \), tedy prvky \( A \) můžeme očíslovat.
Krok 2: Každá konečná podmnožina \( B \subseteq A \) má konečný počet prvků, řekněme \( |B| = n \). Pak lze \( B \) reprezentovat jako n-tici prvků z \( A \) (nezáleží na pořadí, ale toto bereme jako zjednodušení, protože množinu lze reprezentovat množinou uspořádaných n-tic s vhodnou úpravou).
Krok 3: Protože \( A \) je spočetná, množina všech n-tic z \( A \), tedy \( A^n \), je spočetná. Toto plyne z vlastnosti kartézského součinu spočetných množin.
Krok 4: Množina všech konečných podmnožin \( \mathcal{F} \) je sjednocení množin všech podmnožin o velikosti 1, 2, 3, …, tedy
\( \mathcal{F} = \bigcup_{n=0}^\infty \{ B \subseteq A : |B| = n \} \)
Krok 5: Každá tato množina podmnožin velikosti \( n \) je podmnožinou množiny \( A^n \) (po úpravě na uspořádané n-tice), která je spočetná.
Krok 6: Sjednocení spočetně mnoha spočetných množin je opět spočetné. Proto je \( \mathcal{F} \) spočetná.
Závěr:
Množina všech konečných podmnožin spočetné množiny je spočetná.
58. Určete, zda je množina všech funkcí z \( \mathbb{N} \) do konečné množiny \( A = \{1,2,3,4\} \) spočetná či nespočetná. Zdůvodněte podrobně.
Řešení příkladu:
Nechť \( A = \{1,2,3,4\} \) je konečná množina o velikosti 4.
Množina všech funkcí z \( \mathbb{N} \) do \( A \) je množina všech posloupností, kde každý člen je z \( A \). Označme tuto množinu \( F = A^{\mathbb{N}} \).
Krok 1: Velikost množiny \( F \) je rovna kardinálu \( |A|^{|\mathbb{N}|} \), tj. \( 4^{\aleph_0} \).
Krok 2: Je známo, že pro konečné \( k \geq 2 \) platí rovnost kardinálu \( k^{\aleph_0} = 2^{\aleph_0} \), tedy počet všech funkcí \( \mathbb{N} \to A \) je stejný jako počet všech podmnožin \( \mathbb{N} \), což je kardinál kontinuua (tj. velikost množiny reálných čísel).
Krok 3: Kardinál \( 2^{\aleph_0} \) je nespočetný, což znamená, že množina všech funkcí z \( \mathbb{N} \) do \( A \) je nespočetná.
Závěr:
Množina všech funkcí \( \mathbb{N} \to \{1,2,3,4\} \) je nespočetná.
59. Ukažte, že podmnožina spočetné množiny je spočetná nebo konečná. Rozveďte detailní důkaz.
Řešení příkladu:
Nechť \( A \) je spočetná množina a \( B \subseteq A \) je její libovolná podmnožina.
Cílem je dokázat, že \( B \) je konečná nebo spočetná množina.
Krok 1: Pokud je \( B \) konečná, je tvrzení triviálně pravdivé.
Krok 2: Předpokládejme, že \( B \) není konečná. Musíme ukázat, že je spočetná.
Krok 3: Protože \( A \) je spočetná, existuje bijekce \( f: \mathbb{N} \to A \). Vyjmenujeme tedy prvky \( A \) jako \( a_1, a_2, a_3, \dots \).
Krok 4: Podmnožinu \( B \) lze pak vyjmenovat tak, že projdeme \( A \) podle \( f \) a vybereme ty prvky, které jsou v \( B \).
Krok 5: Jelikož \( B \) je nekonečná (tedy ne konečná), máme nekonečně mnoho prvků v \( B \) mezi těmi, které projdeme.
Krok 6: Vyjmenujeme tedy prvky \( B \) jako posloupnost \( b_1, b_2, b_3, \dots \), kde \( b_i \) je \( i \)-tý prvek \( B \) podle pořadí \( f \).
Krok 7: Tím jsme zkonstruovali injekci z \( \mathbb{N} \) do \( B \), což znamená, že \( B \) je alespoň spočetná.
Krok 8: Zároveň \( B \subseteq A \) implikuje, že \( B \) nemůže být větší než \( A \), tedy \( B \) je maximálně spočetná.
Závěr:
Každá podmnožina spočetné množiny je konečná nebo spočetná.
60. Dokažte, že množina všech posloupností z \( \{0,1\} \) je nespočetná.
Řešení příkladu:
Zvažme množinu všech nekonečných posloupností, kde každý prvek je 0 nebo 1. Tuto množinu označíme jako \( S = \{0,1\}^\mathbb{N} \).
Krok 1: Budeme dokazovat nespočetnost pomocí Cantorova diagonálního argumentu.
Krok 2: Předpokládejme, že \( S \) je spočetná. Pak lze prvky \( S \) vyjmenovat jako posloupnost:
\( s_1 = (s_{1,1}, s_{1,2}, s_{1,3}, \dots) \)
\( s_2 = (s_{2,1}, s_{2,2}, s_{2,3}, \dots) \)
\( s_3 = (s_{3,1}, s_{3,2}, s_{3,3}, \dots) \)
\( \dots \)
Krok 3: Sestrojme novou posloupnost \( t = (t_1, t_2, t_3, \dots) \) takto:
Pro každé \( n \) nastavíme \( t_n = 1 – s_{n,n} \) (pokud je \( s_{n,n} = 0 \), pak \( t_n = 1 \), a naopak).
Krok 4: Posloupnost \( t \) se liší od každé posloupnosti \( s_n \) alespoň na \( n \)-tém prvku, což znamená, že \( t \neq s_n \) pro všechna \( n \).
Krok 5: To je však v rozporu s předpokladem, že jsme vyjmenovali všechny prvky \( S \).
Závěr:
Množina všech posloupností z \( \{0,1\} \) je tedy nespočetná.
61. Dokažte, že množina všech racionálních čísel \(\mathbb{Q}\) je spočetná.
Řešení příkladu:
Úkolem je ukázat, že množina všech racionálních čísel je spočetná. Připomeňme, že racionální čísla jsou všechna čísla, která lze vyjádřit jako zlomek \(\frac{p}{q}\), kde \(p \in \mathbb{Z}\) a \(q \in \mathbb{N}\), tedy celočíselný čitatel a přirozený jmenovatel.
Krok 1: Definice spočetnosti
Spočetná množina je taková, která může být zobrazená bijektivně nebo injektivně na množinu přirozených čísel \(\mathbb{N}\). Proto chceme najít funkci, která každému racionálnímu číslu přiřadí unikátní přirozené číslo.
Krok 2: Způsob očíslování racionálních čísel
Nejprve si uvědomíme, že množina \(\mathbb{Z}\) celých čísel je spočetná, a také \(\mathbb{N}\) je spočetná. Kartézský součin \(\mathbb{Z} \times \mathbb{N}\) je také spočetný (viz předchozí příklad o kartézském součinu spočetných množin).
Krok 3: Racionální čísla jako prvek kartézského součinu
Každé racionální číslo lze tedy jednoznačně přiřadit prvku z \(\mathbb{Z} \times \mathbb{N}\) (čitatel, jmenovatel). Abychom měli jednoznačnost, bereme pouze zlomky v základním tvaru, tj. kde \(p\) a \(q\) jsou nesoudělná čísla.
Krok 4: Spočetnost všech základních zlomků
Množina všech takových zlomků je podmnožinou \(\mathbb{Z} \times \mathbb{N}\), tedy je nejvýše spočetná.
Krok 5: Vytvoření explicitního očíslování
Prvky \(\mathbb{Z}\) očíslujeme pomocí funkce:
\[ f_{\mathbb{Z}}(n) = \begin{cases} 0 & \text{pokud } n=0, \\ 2k-1 & \text{pokud } n=k > 0, \\ 2k & \text{pokud } n=-k < 0. \end{cases} \]
Tím zajišťujeme bijekci mezi \(\mathbb{N}\) a \(\mathbb{Z}\).
Krok 6: Očíslování párů
Pomocí Cantorovy diagonální metody očíslujeme všechny dvojice \((p,q) \in \mathbb{Z} \times \mathbb{N}\).
Krok 7: Vyřazení nejednoznačností
Abychom měli pouze základní zlomky, vyřadíme ty, které nejsou v základním tvaru. Jelikož vyřazujeme podmnožinu, stále je výsledná množina maximálně spočetná.
Krok 8: Závěr
Racionální čísla tedy lze očíslovat, což znamená, že množina \(\mathbb{Q}\) je spočetná.
62. Dokažte, že množina všech posloupností konečných délek z konečné množiny je spočetná.
Řešení příkladu:
Zadání zní: Mějme konečnou množinu \(A\). Prozkoumejme množinu všech konečných posloupností prvků z \(A\).
Krok 1: Charakteristika konečných posloupností
Konečná posloupnost délky \(n\) je uspořádaná \(n\)-tice prvků z \(A\), tedy prvek z kartézského součinu \(A^n\). Pro každé pevné \(n \in \mathbb{N}\) je množina \(A^n\) konečná, protože \(A\) je konečná a počet prvků je \(|A|^n\).
Krok 2: Množina všech konečných posloupností
Množina všech konečných posloupností z \(A\) je tedy sjednocení množin \(A^n\) pro všechna \(n \in \mathbb{N}\):
\[ S = \bigcup_{n=0}^\infty A^n. \]
Pro \(n=0\) definujeme \(A^0 = \{\emptyset\}\) jako množinu obsahující prázdnou posloupnost.
Krok 3: Spočetnost sjednocení
Protože \(A\) je konečná, každé \(A^n\) je konečné. Nyní sjednocujeme spočetně mnoho konečných množin, protože indexujeme od \(n=0\) do nekonečna.
Krok 4: Spočetnost sjednocení spočetně mnoha konečných množin
Je známo, že sjednocení spočetně mnoha konečných množin je spočetné.
Krok 5: Závěr
Množina všech konečných posloupností z konečné množiny je tedy spočetná.
63. Dokažte, že množina všech konečných slov nad konečnou abecedou je spočetná.
Řešení příkladu:
Téma tohoto příkladu je velmi podobné předchozímu o konečných posloupnostech, protože slova nad abecedou jsou konečné posloupnosti znaků.
Krok 1: Definice
Nechť \(\Sigma\) je konečná abeceda (množina symbolů). Množina všech slov je množina všech konečných posloupností prvků z \(\Sigma\).
Krok 2: Rozdělení podle délky slov
Stejně jako u posloupností, lze rozdělit množinu slov na množiny slov pevné délky:
\[ W = \bigcup_{n=0}^\infty \Sigma^n, \]
kde \(\Sigma^n\) je množina slov délky \(n\).
Krok 3: Velikost množin \(\Sigma^n\)
Protože \(\Sigma\) je konečná s \(|\Sigma|=k\), platí \(|\Sigma^n| = k^n\), což je konečné číslo.
Krok 4: Spočetnost sjednocení
Jelikož \(W\) je sjednocením spočetně mnoha konečných množin, je \(W\) spočetná množina.
Krok 5: Závěr
Množina všech konečných slov nad konečnou abecedou je spočetná.
64. Ukažte, že množina všech podmnožin spočetné množiny je nespočetná.
Řešení příkladu:
Máme spočetnou množinu \(A\) a chceme ukázat, že množina všech jejích podmnožin, tedy \(\mathcal{P}(A)\), je nespočetná.
Krok 1: Definice potenční množiny
Potenční množina \(\mathcal{P}(A)\) obsahuje všechny možné podmnožiny \(A\), včetně prázdné množiny a \(A\) samotné.
Krok 2: Předpoklad opaku
Předpokládejme, že \(\mathcal{P}(A)\) je spočetná. Potom by existovala bijekce mezi \(\mathcal{P}(A)\) a \(\mathbb{N}\).
Krok 3: Použití Cantorova důkazu
Podobně jako v Cantorově důkazu nespočetnosti reálných čísel můžeme vytvořit diagonální množinu, která nemůže být v žádném seznamu všech podmnožin.
Krok 4: Konstrukce diagonální množiny
Označíme si seznam všech podmnožin jako \(S_1, S_2, S_3, \ldots\) a definujeme množinu
\[ D = \{a_i \in A : a_i \notin S_i\}. \]
Krok 5: Absurdní závěr
Množina \(D\) nemůže být žádným \(S_i\), protože pokud by byla, dostáváme rozpor – pokud \(a_i \in D\), pak \(a_i \notin S_i\) a naopak.
Krok 6: Závěr
Tím jsme ukázali, že potenční množina spočetné množiny není spočetná, tedy je nespočetná.
65. Ukažte, že množina všech konečných funkcí z konečné množiny do spočetné množiny je spočetná.
Řešení příkladu:
Nechť \(A\) je konečná množina a \(B\) je spočetná množina. Zkoumáme množinu všech funkcí \(f: A \to B\).
Krok 1: Charakteristika funkcí
Protože \(A\) je konečná, řekněme, že \(|A|=n\), funkce \(f\) je určena hodnotami \(f(a_1), f(a_2), \ldots, f(a_n)\), kde každý \(f(a_i) \in B\).
Krok 2: Identifikace funkcí s n-ticemi
Množina všech funkcí z \(A\) do \(B\) odpovídá kartézskému součinu \(B^n = B \times B \times \cdots \times B\) (n-krát).
Krok 3: Spočetnost kartézského součinu spočetných množin
Protože \(B\) je spočetná, a konečný kartézský součin spočetných množin je opět spočetný, je množina všech funkcí spočetná.
Krok 4: Závěr
Množina všech funkcí z konečné množiny do spočetné množiny je tedy spočetná.
66. Ukažte, že množina všech konečných podmnožin spočetné množiny je spočetná.
Řešení příkladu:
Nechť \(A\) je spočetná množina. Cílem je dokázat, že množina všech konečných podmnožin množiny \(A\) je spočetná.
Krok 1: Definice konečné podmnožiny
Konečná podmnožina množiny \(A\) je taková, která obsahuje konečný počet prvků z \(A\). Označme množinu všech konečných podmnožin jako \(\mathcal{F}\).
Krok 2: Rozklad množiny \(\mathcal{F}\) podle kardinality podmnožin
Množinu \(\mathcal{F}\) můžeme rozložit jako sjednocení množin všech podmnožin pevné velikosti \(n\):
\[ \mathcal{F} = \bigcup_{n=0}^\infty \mathcal{F}_n, \]
kde \(\mathcal{F}_n = \{ X \subseteq A : |X| = n \}\).
Krok 3: Každá \(\mathcal{F}_n\) je spočetná
Pro pevné \(n\) můžeme vyjádřit \(\mathcal{F}_n\) jako množinu všech \(n\)-prvkových kombinací z množiny \(A\). Protože \(A\) je spočetná, existuje bijekce mezi \(A\) a \(\mathbb{N}\).
Krok 4: Spočetnost množiny všech \(n\)-prvkových kombinací z \(\mathbb{N}\)
Ukážeme, že množina všech \(n\)-prvkových podmnožin \(\mathbb{N}\) je spočetná. Využijeme toho, že množina všech uspořádaných \(n\)-tek z \(\mathbb{N}\) je spočetná (jelikož \(\mathbb{N}^n\) je spočetná).
Krok 5: Vztah mezi uspořádanými \(n\)-tkami a \(n\)-prvkovými podmnožinami
Každé \(n\)-prvkové podmnožině odpovídá právě \(n!\) uspořádaných \(n\)-tek (permutací). Protože permutací je konečně mnoho, a \(\mathbb{N}^n\) je spočetná, množina všech \(n\)-prvkových podmnožin je také spočetná.
Krok 6: Sjednocení spočetně mnoha spočetných množin je spočetné
Množina \(\mathcal{F}\) je sjednocením spočetně mnoha spočetných množin \(\mathcal{F}_n\), proto je také spočetná.
Závěr:
Množina všech konečných podmnožin spočetné množiny je tedy spočetná.
67. Dokažte, že podmnožina spočetné množiny je buď konečná, nebo spočetná.
Řešení příkladu:
Nechť \(A\) je spočetná množina a \(B \subseteq A\) její podmnožina. Máme dokázat, že \(B\) je buď konečná, nebo spočetná.
Krok 1: Definice spočetnosti a konečnosti
Spočetná množina je buď konečná, nebo má bijekci s \(\mathbb{N}\). Chceme tedy ukázat, že \(B\) nemůže být nespočetná podmnožina \(A\).
Krok 2: Argumentace podle velikosti množiny \(B\)
Pokud je \(B\) konečná, je tvrzení splněno. Pokud není konečná, pak má nekonečně mnoho prvků.
Krok 3: Vytvoření injekce z \(\mathbb{N}\) do \(B\)
Protože \(B \subseteq A\) a \(A\) je spočetná, existuje bijekce \(f: \mathbb{N} \to A\). Pak lze omezit \(f\) na množinu \(\mathbb{N}‘ \subseteq \mathbb{N}\), aby pokrývala \(B\).
Krok 4: Spočetnost podmnožiny
Tím pádem existuje injekce z \(\mathbb{N}\) do \(B\), což znamená, že \(B\) je spočetná.
Závěr:
Podmnožina spočetné množiny je tedy konečná nebo spočetná.
68. Ukažte, že kartézský součin dvou spočetných množin je spočetný.
Řešení příkladu:
Nechť \(A\) a \(B\) jsou spočetné množiny. Cílem je ukázat, že \(A \times B\) je také spočetná množina.
Krok 1: Definice spočetnosti
Spočetnost znamená existenci bijekce z množiny na \(\mathbb{N}\). Proto chceme najít bijekci nebo injekci z \(A \times B\) do \(\mathbb{N}\).
Krok 2: Využití očíslování množin \(A\) a \(B\)
Protože \(A\) a \(B\) jsou spočetné, existují bijekce
\[ f: A \to \mathbb{N}, \quad g: B \to \mathbb{N}. \]
Krok 3: Vytvoření zobrazení pro \(A \times B\)
Definujeme zobrazení \(h: A \times B \to \mathbb{N} \times \mathbb{N}\) jako
\[ h(a,b) = (f(a), g(b)). \]
Krok 4: Spočetnost \(\mathbb{N} \times \mathbb{N}\)
Je známý fakt, že \(\mathbb{N} \times \mathbb{N}\) je spočetná množina. Například Cantorova diagonální metoda definuje bijekci z \(\mathbb{N} \times \mathbb{N}\) na \(\mathbb{N}\).
Krok 5: Závěr
Protože \(A \times B\) lze zbijektovat s podmnožinou spočetné množiny \(\mathbb{N} \times \mathbb{N}\), je i \(A \times B\) spočetná.
69. Dokažte, že množina všech konečných funkcí z \(\mathbb{N}\) do konečné množiny \(A\) je spočetná.
Řešení příkladu:
Nechť \(A\) je konečná množina a zkoumáme množinu všech funkcí \(f: D \to A\), kde \(D \subseteq \mathbb{N}\) je konečná.
Krok 1: Charakteristika konečných funkcí
Konečná funkce znamená, že definiční obor je konečný podmnožina \(\mathbb{N}\). Označíme délku definičního oboru jako \(n\).
Krok 2: Rozklad podle délky definičního oboru
Množinu všech konečných funkcí rozdělíme na sjednocení množin funkcí s pevnou délkou definičního oboru:
\[ \mathcal{F} = \bigcup_{n=0}^\infty \mathcal{F}_n, \]
kde \(\mathcal{F}_n\) jsou všechny funkce definované na množině o velikosti \(n\).
Krok 3: Spočetnost \(\mathcal{F}_n\)
Pro pevné \(n\) jsou všechny funkce určené hodnotami v \(A\) pro každý z \(n\) prvků definičního oboru. Proto \(\mathcal{F}_n\) je množina funkcí o velikosti \(|A|^n\), která je konečná, protože \(A\) je konečná.
Krok 4: Sjednocení spočetně mnoha konečných množin
Množina \(\mathcal{F}\) je sjednocením spočetně mnoha konečných množin, proto je spočetná.
Závěr:
Množina všech konečných funkcí z \(\mathbb{N}\) do konečné množiny \(A\) je spočetná.
70. Dokažte, že množina všech posloupností s konečně mnoha nenulovými členy nad spočetnou množinou je spočetná.
Řešení příkladu:
Nechť \(A\) je spočetná množina a zkoumáme množinu všech posloupností \((a_n)_{n=1}^\infty\) s hodnotami v \(A\), které mají pouze konečně mnoho nenulových členů (tj. členů odlišných od nějaké fixní neutrální hodnoty, například nuly).
Krok 1: Rozklad podle počtu nenulových členů
Pro každé \(k \in \mathbb{N}\) označme \(\mathcal{S}_k\) množinu posloupností s právě \(k\) nenulovými členy.
Krok 2: Popis posloupností s \(k\) nenulovými členy
Taková posloupnost je určená výběrem \(k\) pozic z \(\mathbb{N}\) a přiřazením hodnot z \(A\) do těchto pozic.
Krok 3: Spočetnost výběru pozic a hodnot
Množina všech \(k\)-prvkových podmnožin \(\mathbb{N}\) je spočetná. Pro každou takovou podmnožinu máme \(A^k\) možností přiřazení hodnot, kde \(A\) je spočetná, takže \(A^k\) je spočetná jako konečný kartézský součin spočetných množin.
Krok 4: Sjednocení přes \(k\)
Množina všech posloupností s konečně mnoha nenulovými členy je sjednocením \(\bigcup_{k=0}^\infty \mathcal{S}_k\). Jelikož sjednocení spočetně mnoha spočetných množin je spočetné, je celá množina spočetná.
Závěr:
Množina všech posloupností s konečně mnoha nenulovými členy nad spočetnou množinou je spočetná.
71. Ukažte, že každá konečná množina je také spočetná a vysvětlete vztah mezi konečností a spočetností.
Řešení příkladu:
Nejprve si připomeňme definice:
- Konečná množina je taková množina, která obsahuje konečný počet prvků, tj. existuje přirozené číslo \(n\), že množina má právě \(n\) prvků.
- Spočetná množina je taková, která je buď konečná, nebo má stejnou velikost jako množina přirozených čísel \(\mathbb{N}\) (existuje bijekce mezi množinou a \(\mathbb{N}\)).
Cíl: Ukázat, že každá konečná množina je zároveň spočetná, a tedy konečnost je podmnožinou spočetnosti.
Krok 1: Označme konečnou množinu \(A\) a její počet prvků \(n\).
Tedy \( |A| = n \) pro nějaké přirozené číslo \(n\).
Krok 2: Ukažme existenci bijekce mezi \(A\) a množinou \(\{1, 2, \ldots, n\}\).
Protože \(A\) má právě \(n\) prvků, lze je očíslovat jako \(a_1, a_2, \ldots, a_n\). Definujeme zobrazení \(f : A \to \{1, 2, \ldots, n\}\), kde \(f(a_i) = i\).
Krok 3: Ověření, že \(f\) je bijekce
Zobrazení \(f\) je jednoznačné, protože každému prvku \(a_i\) přiřazuje právě jedno číslo \(i\) a každé číslo v \(\{1, \ldots, n\}\) je obrazem právě jednoho prvku z \(A\).
Krok 4: Spočetnost konečné množiny
Množina \(\{1, 2, \ldots, n\}\) je podmnožinou \(\mathbb{N}\), a tedy je spočetná. Protože existuje bijekce mezi \(A\) a \(\{1, 2, \ldots, n\}\), je \(A\) také spočetná.
Závěr:
Každá konečná množina je také spočetná. Spočetnost tedy zahrnuje konečné množiny jako speciální případ. To znamená, že spočetné množiny jsou obecnější pojem než konečné množiny.
72. Ukažte, že sjednocení konečně mnoha spočetných množin je spočetné.
Řešení příkladu:
Nechť máme konečný počet spočetných množin \(A_1, A_2, \ldots, A_k\). Cílem je ukázat, že jejich sjednocení \(A = \bigcup_{i=1}^k A_i\) je spočetné.
Krok 1: Charakteristika spočetných množin
Každá množina \(A_i\) je buď konečná, nebo má stejnou kardinalitu jako \(\mathbb{N}\). Proto existuje injekce \(f_i : A_i \to \mathbb{N}\).
Krok 2: Vytvoření injekce z \(A\) do \(\mathbb{N} \times \{1, \ldots, k\}\)
Definujeme zobrazení \(F: A \to \mathbb{N} \times \{1, \ldots, k\}\) tak, že pokud \(x \in A_i\), pak \(F(x) = (f_i(x), i)\).
Krok 3: Spočetnost \(\mathbb{N} \times \{1, \ldots, k\}\)
Množina \(\{1, \ldots, k\}\) je konečná, a tedy spočetná. Kartézský součin spočetné množiny \(\mathbb{N}\) s konečnou množinou je spočetný.
Krok 4: Závěr
Protože existuje injekce z \(A\) do spočetné množiny \(\mathbb{N} \times \{1, \ldots, k\}\), je \(A\) spočetná.
Výsledkem je, že sjednocení konečně mnoha spočetných množin je spočetná množina.
73. Ukažte, že množina všech konečných řetězců nad konečnou abecedou je spočetná.
Řešení příkladu:
Nechť máme konečnou abecedu \( \Sigma \) o velikosti \(k\). Zkoumáme množinu všech konečných řetězců nad touto abecedou, tj. množinu \( \Sigma^* = \bigcup_{n=0}^\infty \Sigma^n \), kde \( \Sigma^n \) je množina všech řetězců délky \(n\).
Krok 1: Velikost \(\Sigma^n\)
Počet řetězců délky \(n\) nad abecedou o velikosti \(k\) je \(k^n\), což je konečné číslo (protože \(k\) je konečné).
Krok 2: Sjednocení množin \(\Sigma^n\)
Množina všech konečných řetězců je sjednocením všech \(\Sigma^n\) pro \(n \in \mathbb{N}\). Jedná se tedy o sjednocení spočetně mnoha konečných množin.
Krok 3: Spočetnost sjednocení spočetně mnoha konečných množin
Sjednocení spočetně mnoha konečných množin je spočetné, protože spočetné sjednocení konečných množin nelze „narůst“ do nespočetné množiny.
Závěr:
Množina všech konečných řetězců nad konečnou abecedou je spočetná.
74. Dokažte, že pokud je \(A\) konečná a \(B\) spočetná, pak množina všech funkcí z \(A\) do \(B\) je spočetná.
Řešení příkladu:
Nechť \(A\) je konečná množina o velikosti \(n\) a \(B\) je spočetná množina. Zkoumáme množinu všech funkcí \(f: A \to B\).
Krok 1: Počet funkcí z \(A\) do \(B\)
Každá funkce je určena výběrem hodnoty z \(B\) pro každý prvek \(a \in A\). Protože \(A\) má \(n\) prvků a \(B\) je spočetná, množina všech funkcí má kardinalitu rovnu kartézskému součinu \(B^n\).
Krok 2: Spočetnost \(B^n\)
Kartézský součin spočetných množin je spočetný, pokud jde o konečný počet faktorů. Jelikož \(n\) je konečné, platí, že \(B^n\) je spočetné.
Závěr:
Množina všech funkcí z konečné množiny do spočetné množiny je spočetná.
75. Ukažte, že množina všech konečných podmnožin spočetné množiny je spočetná.
Řešení příkladu:
Nechť \(A\) je spočetná množina. Zkoumáme množinu všech konečných podmnožin množiny \(A\), označme ji \(\mathcal{F}\).
Krok 1: Rozklad podle velikosti podmnožiny
Množinu \(\mathcal{F}\) lze vyjádřit jako sjednocení všech množin \(\mathcal{F}_n\), kde \(\mathcal{F}_n\) je množina všech podmnožin \(A\) o velikosti \(n\), tj.
\[ \mathcal{F} = \bigcup_{n=0}^\infty \mathcal{F}_n. \]
Krok 2: Spočetnost každé \(\mathcal{F}_n\)
Každá \(\mathcal{F}_n\) je množina všech \(n\)-prvkových podmnožin spočetné množiny \(A\). Je známo, že množina všech \(n\)-prvkových podmnožin spočetné množiny je spočetná (lze ji uspořádat podle lexikografického uspořádání nebo přiřadit jim kódy).
Krok 3: Sjednocení spočetně mnoha spočetných množin
Sjednocení spočetně mnoha spočetných množin je spočetné, proto množina \(\mathcal{F}\) je spočetná.
Závěr:
Množina všech konečných podmnožin spočetné množiny je spočetná.
76. Ukažte, že množina všech nekonečných posloupností složených pouze z nul a jedniček není spočetná.
Řešení příkladu:
Nechť množina S obsahuje všechny nekonečné posloupnosti prvků z množiny {0,1}. Chceme dokázat, že S není spočetná.
Krok 1: Připomeňme si definici spočetnosti a nespočetnosti
Spočetná množina je množina, která má stejnou kardinalitu jako množina přirozených čísel ℕ, tedy lze její prvky očíslovat (vytvořit bijekci s ℕ). Pokud taková bijekce neexistuje, množina je nespočetná.
Krok 2: Použití Cantorovy diagonální argumentace
Předpokládejme pro spor, že množina S je spočetná. Pak lze všechny nekonečné posloupnosti {0,1}^ℕ vyjmenovat jako s₁, s₂, s₃, …, kde každý sᵢ = (s_{i1}, s_{i2}, s_{i3}, …) je nekonečná posloupnost nul a jedniček.
Vytvoříme novou posloupnost t = (t₁, t₂, t₃, …), kde prvek tᵢ bude definován jako doplněk prvku s_{ii}:
tᵢ = 1, pokud s_{ii} = 0; tᵢ = 0, pokud s_{ii} = 1.
Krok 3: Kontrola, že t není v seznamu sᵢ
Tato posloupnost t se liší od každé posloupnosti sᵢ alespoň na i-tém místě, protože právě tam se liší v hodnotě.
Tedy t nemůže být žádnou z posloupností sᵢ, což je spor s tím, že jsme všechny posloupnosti vyjmenovali.
Závěr: Množina všech nekonečných posloupností z {0,1} není spočetná.
77. Pro množiny \(A\) a \(B\) dokažte, že pokud je \(A\) spočetná a \(B\) konečná, pak kartézský součin \(A × B\) je spočetný.
Řešení příkladu:
Nechť A je spočetná množina a B konečná množina o velikosti k. Cílem je ukázat, že kartézský součin A × B = {(a,b) : a ∈ A, b ∈ B} je spočetný.
Krok 1: Charakteristika množin
Množina A je spočetná, což znamená, že existuje bijekce f: A → ℕ nebo alespoň injekce do ℕ. Množina B je konečná, tedy má konečný počet prvků k.
Krok 2: Rozdělení kartézského součinu
Kartézský součin lze rozložit jako sjednocení k množin:
A × B = ⋃_{b ∈ B} (A × {b})
Kde každá množina A × {b} je bijektivní s A.
Krok 3: Spočetnost jednotlivých částí
Každá množina A × {b} je v podstatě kopie množiny A, tedy spočetná.
Krok 4: Sjednocení konečně mnoha spočetných množin
Sjednocení konečně mnoha spočetných množin je spočetné. Protože počet b ∈ B je konečný, sjednocení všech A × {b} je spočetné.
Závěr: Množina A × B je spočetná.
78. Ukažte, že množina všech prvočísel je spočetná.
Řešení příkladu:
Množina všech prvočísel P = {2,3,5,7,11,…} je podmnožinou množiny přirozených čísel ℕ.
Krok 1: Množina P je podmnožinou spočetné množiny ℕ
Množina ℕ je spočetná a množina všech prvočísel je její podmnožina.
Krok 2: Podmnožina spočetné množiny může být konečná nebo spočetná
Množina prvočísel je nekonečná, což je známý fakt z teorie čísel (Euclidův důkaz nekonečnosti prvočísel).
Krok 3: Je množina P spočetná?
Množina P je podmnožinou ℕ a je nekonečná. Podmnožina spočetné množiny, která je nekonečná, je spočetná právě tehdy, když lze její prvky očíslovat.
Protože můžeme prvočísla uspořádat v rostoucím pořadí a přiřadit jim přirozená čísla podle pořadí (2 je první, 3 druhé, 5 třetí atd.), existuje bijekce mezi P a ℕ.
Závěr: Množina všech prvočísel je spočetná.
79. Dokažte, že podmnožina konečné množiny je vždy konečná.
Řešení příkladu:
Nechť A je konečná množina o velikosti n a B ⊆ A je její podmnožina.
Krok 1: Počet prvků v podmnožině
Protože B ⊆ A, každý prvek b ∈ B je zároveň v A. Maximální možný počet prvků v B je tedy n.
Krok 2: Konečnost podmnožiny
Jelikož B má nejvýše n prvků, je také konečná.
Závěr: Podmnožina konečné množiny je konečná.
80. Dokažte, že množina všech funkcí z konečné množiny do konečné množiny je konečná.
Řešení příkladu:
Nechť A a B jsou konečné množiny, kde |A| = m a |B| = n.
Krok 1: Charakteristika funkcí z A do B
Funkce f: A → B přiřazuje každému prvku z A právě jeden prvek z B.
Krok 2: Počet všech funkcí z A do B
Pro každý prvek v A existuje n možností přiřazení (prvků z B).
Proto počet všech funkcí je \(n^m\), což je konečné číslo (mocnina konečného čísla).
Závěr: Množina všech funkcí z konečné množiny A do konečné množiny B je konečná.
81. Dokažte, že sjednocení konečně mnoha spočetných množin je spočetné.
Řešení příkladu:
Nechť máme konečný počet spočetných množin \(A_1, A_2, \ldots, A_k\), kde každá \(A_i\) je spočetná. Cílem je ukázat, že sjednocení těchto množin \(A = \bigcup_{i=1}^k A_i\) je spočetné.
Krok 1: Definice spočetné množiny
Spočetná množina je množina, jejíž prvky lze očíslovat přirozenými čísly, tedy existuje bijekce mezi touto množinou a podmnožinou \(\mathbb{N}\).
Krok 2: Spočetnost jednotlivých množin \(A_i\)
Každá množina \(A_i\) je spočetná, tedy existuje surjekce nebo bijekce \(f_i: \mathbb{N} \to A_i\), která umožňuje očíslovat prvky \(A_i\).
Krok 3: Konstrukce očíslování sjednocení
Protože počet množin je konečný, tedy \(k\) je konečné, můžeme uspořádat jejich prvky do tabulky:
A₁: a₁₁, a₁₂, a₁₃, a₁₄, ...
A₂: a₂₁, a₂₂, a₂₃, a₂₄, ...
...
A_k: a_k₁, a_k₂, a_k₃, a_k₄, ...
Tuto tabulku můžeme „prolézt“ diagonálním způsobem či jiným uspořádáním, aby každému prvku z této sjednocené množiny přiřadilo unikátní přirozené číslo. Postupně procházíme řádky a sloupce, čímž vytvoříme seznam všech prvků z \(A\).
Krok 4: Ošetření opakujících se prvků
Pokud se některý prvek opakuje v různých množinách \(A_i\), při očíslování jej můžeme vynechat, aby každý prvek byl v seznamu právě jednou.
Závěr: Tento konstrukční postup zajišťuje, že sjednocení konečně mnoha spočetných množin je opět spočetná množina.
82. Dokažte, že množina všech polynomů s celočíselnými koeficienty je spočetná.
Řešení příkladu:
Nechť \(P\) je množina všech polynomů jedné proměnné s celočíselnými koeficienty, tj. polynomů tvaru
\(p(x) = a_0 + a_1 x + a_2 x^2 + \ldots + a_n x^n\), kde \(a_i \in \mathbb{Z}\) a \(n \in \mathbb{N}_0\).
Krok 1: Rozdělení množiny \(P\) podle stupně polynomu
Množinu \(P\) lze rozdělit na sjednocení množin polynomů pevného stupně \(n\):
\(P = \bigcup_{n=0}^\infty P_n\), kde \(P_n\) je množina polynomů stupně nejvýše \(n\).
Krok 2: Spočetnost jednotlivých množin \(P_n\)
Pro pevné \(n\) je množina \(P_n\) v bijekci s množinou \(\mathbb{Z}^{n+1}\), protože každý polynom je určen posloupností koeficientů \((a_0, a_1, \ldots, a_n)\).
Krok 3: Spočetnost \(\mathbb{Z}^{n+1}\)
Množina \(\mathbb{Z}\) je spočetná. Konečný součin spočetných množin je spočetný, tedy \(\mathbb{Z}^{n+1} = \mathbb{Z} \times \ldots \times \mathbb{Z}\) (n+1 krát) je spočetný.
Krok 4: Sjednocení spočetně mnoha spočetných množin
Množina \(P\) je sjednocením spočetně mnoha spočetných množin \(P_n\). Spočetné sjednocení spočetných množin je opět spočetné (viz předchozí příklad).
Závěr: Množina všech polynomů s celočíselnými koeficienty je spočetná.
83. Proveďte důkaz, že množina všech konečných podmnožin spočetné množiny je spočetná.
Řešení příkladu:
Nechť \(A\) je spočetná množina. Máme prokázat, že množina všech konečných podmnožin \(A\) je spočetná.
Krok 1: Označení množiny konečných podmnožin
Označme množinu všech konečných podmnožin \(A\) jako \(\mathcal{F}(A)\).
Krok 2: Rozdělení podle velikosti podmnožiny
Množinu \(\mathcal{F}(A)\) lze vyjádřit jako sjednocení množin podmnožin fixní velikosti:
\(\mathcal{F}(A) = \bigcup_{n=0}^\infty \{ B \subseteq A : |B| = n \}\)
Krok 3: Spočetnost množiny podmnožin pevné velikosti
Pro pevné \(n\) je množina všech podmnožin \(A\) o velikosti \(n\) podmnožinou kartézského součinu \(A^n\) (se správnou úpravou na uspořádané \(n\)-tice bez opakování).
Protože \(A\) je spočetná, \(A^n\) je spočetné (kartézský součin spočetných množin je spočetný). Množina všech podmnožin velikosti \(n\) je tedy podmnožinou spočetné množiny, a tedy také spočetná.
Krok 4: Spočetné sjednocení spočetných množin
Sjednocení spočetně mnoha spočetných množin je spočetné, tedy \(\mathcal{F}(A)\) je spočetná.
Závěr: Množina všech konečných podmnožin spočetné množiny je spočetná.
84. Dokažte, že množina všech posloupností konečné délky složených z přirozených čísel je spočetná.
Řešení příkladu:
Nechť \(S\) je množina všech posloupností konečné délky, kde každý prvek je přirozené číslo.
Krok 1: Rozdělení podle délky posloupnosti
Množinu \(S\) lze vyjádřit jako sjednocení množin posloupností pevné délky \(n\):
\(S = \bigcup_{n=0}^\infty \mathbb{N}^n\), kde \(\mathbb{N}^0\) je množina obsahující prázdnou posloupnost.
Krok 2: Spočetnost \(\mathbb{N}^n\)
Pro pevné \(n\) je \(\mathbb{N}^n\) kartézským součinem spočetných množin, tedy také spočetná.
Krok 3: Sjednocení spočetně mnoha spočetných množin
Sjednocení spočetně mnoha spočetných množin je spočetné, proto \(S\) je spočetná.
Závěr: Množina všech konečných posloupností z přirozených čísel je spočetná.
85. Dokažte, že podmnožina spočetné množiny může být nespočetná pouze tehdy, pokud není podmnožinou spočetných prvků.
Řešení příkladu:
Nechť \(A\) je spočetná množina a \(B \subseteq A\).
Krok 1: Vlastnost podmnožin spočetné množiny
Každá podmnožina spočetné množiny je buď konečná, nebo spočetná. Není možné, aby byla nespočetná, protože to by znamenalo větší kardinalitu než má \(A\).
Krok 2: Definice nespočetné množiny
Nespočetná množina má větší kardinalitu než \(\mathbb{N}\), tedy nelze její prvky očíslovat.
Krok 3: Závěr
Pokud by podmnožina \(B\) byla nespočetná, pak by musela obsahovat prvky mimo množinu \(A\), což je spor s předpokladem \(B \subseteq A\).
Proto podmnožina spočetné množiny nemůže být nespočetná. Pokud tedy chceme množinu nespočetnou, nesmí být podmnožinou spočetné množiny.
86. Ukažte, že každá podmnožina konečné množiny je konečná a určete počet všech podmnožin konečné množiny o n prvcích.
Řešení příkladu:
Nechť \(M\) je konečná množina s \(|M| = n\), kde \(n\) je konečné přirozené číslo.
Krok 1: Každá podmnožina konečné množiny je konečná
Podmnožina \(A \subseteq M\) obsahuje nějaký počet prvků z množiny \(M\). Protože \(M\) má právě \(n\) prvků, žádná podmnožina nemůže mít více než \(n\) prvků, tedy každá podmnožina je konečná.
Krok 2: Určení počtu všech podmnožin
Podmnožina konečné množiny s \(n\) prvky může obsahovat \(k\) prvků, kde \(k = 0, 1, 2, \ldots, n\).
Počet podmnožin o velikosti \(k\) je dán kombinatorickým číslem (binomickým koeficientem):
\[ \binom{n}{k} = \frac{n!}{k! (n-k)!} \]
Celkový počet všech podmnožin je pak součtem všech těchto kombinací:
\[ \sum_{k=0}^n \binom{n}{k} = 2^n \]
Krok 3: Interpretace
To znamená, že množina s \(n\) prvky má přesně \(2^n\) různých podmnožin, což zahrnuje i prázdnou množinu a samotnou množinu \(M\).
Závěr: Každá podmnožina konečné množiny je konečná a počet všech podmnožin konečné množiny o \(n\) prvcích je \(2^n\).
87. Ukažte, že množina všech konečných posloupností z konečné množiny s \(m\) prvky je spočetná a určete její mohutnost.
Řešení příkladu:
Nechť \(M\) je konečná množina s \(|M| = m\), kde \(m\) je konečné přirozené číslo.
Krok 1: Definice množiny konečných posloupností
Posloupnost délky \(n\) z množiny \(M\) je uspořádaný \(n\)-tice prvků z \(M\), tedy prvek z kartézského součinu \(M^n\).
Krok 2: Počet posloupností pevné délky
Počet všech posloupností délky \(n\) je \(|M|^n = m^n\), protože na každou pozici můžeme vybrat libovolný z \(m\) prvků.
Krok 3: Sjednocení pro všechny délky
Množina všech konečných posloupností je sjednocením množin \(M^n\) pro \(n = 0, 1, 2, \ldots\), tj.
\[ S = \bigcup_{n=0}^\infty M^n \]
kde \(M^0\) je množina obsahující prázdnou posloupnost.
Krok 4: Spočetnost sjednocení
Protože každá množina \(M^n\) má konečný počet prvků \(m^n\), jde o konečné množiny. Nyní sjednocujeme spočetně mnoho konečných množin, tj. \(S\) je sjednocením spočetně mnoha konečných množin.
Podle vlastnosti spočetných množin je sjednocení spočetně mnoha konečných (nebo spočetných) množin opět spočetné.
Závěr: Množina všech konečných posloupností z konečné množiny s \(m\) prvky je spočetná. Její mohutnost je spočetná, konkrétně kardinalita této množiny je spočetná.
88. Dokažte, že množina všech konečných podmnožin spočetné množiny je spočetná.
Řešení příkladu:
Nechť \(A\) je spočetná množina. Chceme ukázat, že množina všech konečných podmnožin \(A\) je spočetná.
Krok 1: Charakteristika konečných podmnožin
Konečné podmnožiny \(A\) jsou množiny, které mají konečný počet prvků. Označíme množinu všech konečných podmnožin jako \(F\).
Krok 2: Vyjádření jako sjednocení
Množinu \(F\) lze vyjádřit jako sjednocení všech podmnožin délky \(n\) pro \(n \in \mathbb{N}_0\): \[ F = \bigcup_{n=0}^\infty \{ B \subseteq A : |B| = n \}. \]
Krok 3: Každá množina podmnožin pevné velikosti je spočetná
Protože \(A\) je spočetná, lze ji uspořádat jako posloupnost \(A = \{a_1, a_2, a_3, \ldots\}\). Množina všech podmnožin \(n\)-tice z \(A\) je tedy v bijekci s množinou všech uspořádaných \(n\)-ticí bez opakování z \(A\).
Počet uspořádaných \(n\)-ticí z \(A\) je spočetný, jelikož spočetné množiny z \(A\) mají spočetně mnoho prvků a výběr \(n\)-prvků je obdobou kombinací.
Z toho plyne, že množina všech podmnožin velikosti \(n\) je spočetná.
Krok 4: Sjednocení spočetně mnoha spočetných množin je spočetné
Množina \(F\) je sjednocení spočetně mnoha množin, z nichž každá je spočetná. Podle vlastnosti spočetných množin je tak i \(F\) spočetná.
Závěr: Množina všech konečných podmnožin spočetné množiny \(A\) je spočetná.
89. Ukažte, že množina všech funkcí z konečné množiny \(M\) do spočetné množiny \(N\) je spočetná.
Řešení příkladu:
Nechť \(M\) je konečná množina s \(|M| = m\) a \(N\) je spočetná množina.
Krok 1: Charakteristika funkcí z \(M\) do \(N\)
Funkce \(f: M \to N\) přiřazují každému prvku \(x \in M\) nějaký prvek \(f(x) \in N\).
Krok 2: Počet funkcí
Protože \(M\) je konečná a má \(m\) prvků, funkce \(f\) lze chápat jako uspořádanou \(m\)-tici prvků z \(N\), kde každý prvek odpovídá hodnotě funkce na jednom prvku \(M\).
Krok 3: Množina funkcí jako kartézský součin
Množina všech funkcí je tedy kartézským součinem \(N \times N \times \cdots \times N = N^m\).
Krok 4: Spočetnost kartézského součinu
Protože \(N\) je spočetná a \(m\) je konečné číslo, kartézský součin \(N^m\) je spočetný. To plyne z toho, že konečný součin spočetných množin je spočetný.
Závěr: Množina všech funkcí z konečné množiny \(M\) do spočetné množiny \(N\) je spočetná.
90. Ukažte, že podmnožina \(\mathbb{Q}\) všech racionálních čísel, která leží v intervalu \([0,1]\), je spočetná.
Řešení příkladu:
Chceme dokázat, že množina \(\mathbb{Q} \cap [0,1]\) je spočetná.
Krok 1: Charakteristika racionálních čísel v \([0,1]\)
Racionální čísla lze vyjádřit ve tvaru \(\frac{p}{q}\), kde \(p, q \in \mathbb{Z}\), \(q > 0\) a zlomky jsou v základním tvaru.
Krok 2: Omezení hodnoty
Pro čísla v intervalu \([0,1]\) platí \(0 \le \frac{p}{q} \le 1\), tedy \(0 \le p \le q\).
Krok 3: Spočetnost množiny zlomků
Pro každé pevné \(q \in \mathbb{N}\) existuje konečně mnoho \(p\) splňujících \(0 \le p \le q\). Množina všech takových zlomků pro dané \(q\) je tedy konečná.
Krok 4: Sjednocení přes všechna \(q\)
Množina \(\mathbb{Q} \cap [0,1]\) je sjednocení všech těchto konečných množin přes \(q=1,2,3,\ldots\), tedy sjednocení spočetně mnoha konečných množin.
Krok 5: Vlastnost spočetnosti sjednocení
Sjednocení spočetně mnoha konečných množin je spočetné.
Závěr: Množina racionálních čísel v intervalu \([0,1]\) je spočetná.
91. Ukažte, že podmnožina spočetné množiny je buď konečná, nebo spočetná. Dále určete, zda může být podmnožina spočetné množiny nespočetná.
Řešení příkladu:
Nechť \(A\) je spočetná množina a \(B \subseteq A\) je její libovolná podmnožina. Chceme ukázat, že \(B\) je buď konečná, nebo spočetná.
Krok 1: Definice spočetnosti
Množina je spočetná, pokud existuje prostá a na z \(\mathbb{N}\) do této množiny. Jinými slovy, prvky lze uspořádat do posloupnosti.
Krok 2: Podmnožina konečné množiny
Pokud je \(A\) konečná, pak každá podmnožina \(B\) je konečná, protože je podmnožinou konečné množiny.
Krok 3: Podmnožina spočetné množiny
Pokud \(A\) je spočetná (ale nekonečná), lze ji vyjádřit jako posloupnost \(A = \{a_1, a_2, a_3, \ldots\}\). Podmnožinu \(B\) můžeme reprezentovat jako množinu některých prvků této posloupnosti. Zde jsou dvě možnosti:
- Pokud \(B\) má konečně mnoho prvků, pak je konečná.
- Pokud \(B\) má nekonečně mnoho prvků, pak lze tyto prvky uspořádat jako posloupnost vybráním z \(A\) s zachováním pořadí. Proto existuje prostá a na z \(\mathbb{N}\) do \(B\), tedy \(B\) je spočetná.
Krok 4: Může být podmnožina spočetné množiny nespočetná?
Není možné, aby podmnožina spočetné množiny byla nespočetná, protože nespočetné množiny mají větší kardinalitu než spočetné. Kdyby podmnožina \(B\) byla nespočetná, znamenalo by to, že \(B\) má větší počet prvků než \(A\), což je v rozporu s tím, že \(B \subseteq A\).
Závěr: Podmnožina spočetné množiny je vždy buď konečná, nebo spočetná, a nikdy nemůže být nespočetná.
92. Dokažte, že sjednocení konečně mnoha spočetných množin je spočetné.
Řešení příkladu:
Nechť \(A_1, A_2, \ldots, A_n\) jsou spočetné množiny. Chceme ukázat, že jejich sjednocení \(A = \bigcup_{i=1}^n A_i\) je spočetné.
Krok 1: Charakteristika spočetných množin
Každá množina \(A_i\) je spočetná, což znamená, že existuje prostá a na z \(\mathbb{N}\) funkce \(f_i : \mathbb{N} \to A_i\), která bijektivně zobrazuje přirozená čísla na prvky \(A_i\).
Krok 2: Konstrukce zobrazení pro sjednocení
Chceme ukázat, že existuje prostá a na z \(\mathbb{N}\) do \(A\). Jelikož \(n\) je konečné číslo, můžeme jednotlivé množiny uspořádat do posloupnosti a z jejich jednotlivých zobrazení vytvořit společné zobrazení.
Krok 3: Vytvoření zobrazení z \(\mathbb{N}\) do \(A\)
Definujme zobrazení \(g: \mathbb{N} \to A\) tak, že pro každé \(k \in \mathbb{N}\) přiřadíme:
\[ g(k) = f_i(m), \quad \text{kde } i = ((k – 1) \bmod n) + 1, \quad m = \left\lfloor \frac{k – 1}{n} \right\rfloor + 1 \]Tedy \(k\) rozkládáme na dvojici \((i,m)\), kde \(i\) určuje, z které množiny \(A_i\) bereme prvek, a \(m\) určuje pořadí prvku v této množině.
Krok 4: Ověření prostoty a úplnosti
Protože každé \(f_i\) je prostá a na z \(\mathbb{N}\), a indexy \(i\) cyklicky procházejí všechny hodnoty od 1 do \(n\), zobrazení \(g\) pokrývá všechny prvky všech \(A_i\). Může nastat, že některé prvky se objeví vícekrát (pokud množiny mají společné prvky), ale to nevadí, protože podmnožina spočetné množiny je stále spočetná. Pro odstranění duplicity můžeme aplikovat restrikci na obraz zobrazení, čímž získáme prostou funkci.
Závěr: Sjednocení konečně mnoha spočetných množin je spočetné.
93. Ukažte, že množina všech konečných podmnožin spočetné množiny je spočetná.
Řešení příkladu:
Nechť \(A\) je spočetná množina. Definujeme množinu \(F\) jako množinu všech konečných podmnožin \(A\), tj.
\[ F = \{B \subseteq A \mid B \text{ je konečná}\}. \]Cíl: Ukázat, že \(F\) je spočetná.
Krok 1: Spočetnost množiny \(A\)
Protože \(A\) je spočetná, lze ji uspořádat jako posloupnost
\[ A = \{a_1, a_2, a_3, \ldots\}. \]Krok 2: Spočetnost množin konečné velikosti
Každá konečná podmnožina \(B \subseteq A\) má nějakou konečnou velikost \(k \in \mathbb{N}\). Označme
\[ F_k = \{B \subseteq A \mid |B| = k\}. \]Pak
\[ F = \bigcup_{k=0}^\infty F_k, \] kde \(F_0 = \{\emptyset\}\).Krok 3: Spočetnost jednotlivých \(F_k\)
Každá \(F_k\) je množina všech podmnožin \(A\) o velikosti \(k\). Pro spočetnou množinu \(A\) lze ukázat, že množina všech \(k\)-prvkových podmnožin je spočetná, protože lze uspořádat všechny možné výběry \(k\) prvků v posloupnosti.
Konkrétně, protože prvky \(A\) jsou očíslovány, každá podmnožina o velikosti \(k\) odpovídá \(k\)-tici vzestupně uspořádaných přirozených čísel (indexů prvků). Množina všech \(k\)-ticí přirozených čísel je spočetná.
Krok 4: Spočetné sjednocení spočetných množin
Protože každé \(F_k\) je spočetné a \(F\) je sjednocení spočetně mnoha spočetných množin \(F_k\), pak \(F\) je spočetné podle známé vlastnosti spočetnosti (spočetné sjednocení spočetných množin je spočetné).
Závěr: Množina všech konečných podmnožin spočetné množiny je spočetná.
94. Dokažte, že kartézský součin dvou spočetných množin je spočetný.
Řešení příkladu:
Nechť \(A\) a \(B\) jsou spočetné množiny. Chceme ukázat, že jejich kartézský součin
\[ A \times B = \{(a,b) \mid a \in A, b \in B\} \] je spočetný.Krok 1: Usazení na přirozených číslech
Protože \(A\) a \(B\) jsou spočetné, existují prostá a na z \(\mathbb{N}\) funkce
\[ f : \mathbb{N} \to A, \quad g : \mathbb{N} \to B. \]Krok 2: Konstrukce zobrazení z \(\mathbb{N} \times \mathbb{N}\) do \(A \times B\)
Pro každou dvojici \((m,n) \in \mathbb{N} \times \mathbb{N}\) definujeme
\[ h(m,n) = (f(m), g(n)) \in A \times B. \]Krok 3: Spočetnost \(\mathbb{N} \times \mathbb{N}\)
Je známé, že \(\mathbb{N} \times \mathbb{N}\) je spočetná množina. Například lze uspořádat všechny dvojice \((m,n)\) podle diagonál
\[ (1,1), (1,2), (2,1), (1,3), (2,2), (3,1), \ldots \]Toto uspořádání vytváří bijekci mezi \(\mathbb{N}\) a \(\mathbb{N} \times \mathbb{N}\).
Krok 4: Složení funkcí
Složení této bijekce s funkcí \(h\) vytváří prostou a na z \(\mathbb{N}\) do \(A \times B\), což znamená, že \(A \times B\) je spočetné.
Závěr: Kartézský součin dvou spočetných množin je spočetný.
95. Dokažte, že množina všech konečných posloupností prvků spočetné množiny je spočetná.
Řešení příkladu:
Nechť \(A\) je spočetná množina. Definujeme množinu všech konečných posloupností prvků z \(A\) jako
\[ S = \bigcup_{k=0}^\infty A^k, \] kde \(A^k\) je množina všech posloupností délky \(k\) z prvků \(A\), přičemž \(A^0 = \{\emptyset\}\) obsahuje pouze prázdnou posloupnost.Cíl: Ukázat, že \(S\) je spočetná.
Krok 1: Spočetnost jednotlivých \(A^k\)
Protože \(A\) je spočetná, existuje prostá a na z \(\mathbb{N}\) funkce \(f : \mathbb{N} \to A\). Množina \(A^k\) je pak kartézským součinem \(k\)-krát:
\[ A^k = A \times A \times \cdots \times A \quad (k \text{-krát}). \]Podle předchozího příkladu je kartézský součin konečně mnoha spočetných množin spočetný. Proto je \(A^k\) spočetné pro každé pevné \(k\).
Krok 2: Spočetné sjednocení spočetných množin
Množina \(S\) je sjednocení všech \(A^k\) pro \(k \in \mathbb{N}_0\). Protože sjednocujeme spočetně mnoho spočetných množin, je \(S\) spočetné.
Závěr: Množina všech konečných posloupností prvků spočetné množiny je spočetná.
96. Ukažte, že množina všech konečných posloupností z spočetné množiny je spočetná.
Řešení příkladu:
Nechť \(A\) je spočetná množina. Chceme dokázat, že množina všech konečných posloupností prvků z \(A\) je spočetná.
Krok 1: Definice konečných posloupností
Konečná posloupnost délky \(n\) z \(A\) je uspořádaná \(n\)-tice prvků z \(A\), tedy prvek kartézského součinu \(A^n\).
Krok 2: Spočetnost jednotlivých množin posloupností pevné délky
Protože \(A\) je spočetná, kartézský součin \(A^n\) (součin \(n\)-krát) je také spočetný pro každé konečné \(n\). To plyne z vlastnosti, že konečný součin spočetných množin je spočetný.
Krok 3: Sjednocení množin všech posloupností různých délek
Množina všech konečných posloupností je sjednocením množin všech posloupností délky \(n\), tedy \[ S = \bigcup_{n=0}^\infty A^n, \] kde \(A^0\) je množina obsahující prázdnou posloupnost.
Krok 4: Spočetnost sjednocení spočetně mnoha spočetných množin
Každá množina \(A^n\) je spočetná, a protože sjednocujeme spočetně mnoho takových množin, výsledná množina \(S\) je také spočetná.
Závěr: Množina všech konečných posloupností z spočetné množiny \(A\) je spočetná.
97. Dokažte, že podmnožina všech přirozených čísel, která jsou dělitelné daným přirozeným číslem \(k\), je spočetná a určete její mohutnost.
Řešení příkladu:
Nechť \(k \in \mathbb{N}\) je pevné přirozené číslo. Definujeme množinu \[ M = \{ n \in \mathbb{N} : k \mid n \}, \] tedy množinu všech přirozených čísel dělitelných \(k\).
Krok 1: Vyjádření množiny \(M\)
Každý prvek \(n\) z \(M\) lze zapsat jako \(n = k \cdot m\), kde \(m \in \mathbb{N}\).
Krok 2: Bijekce mezi \(\mathbb{N}\) a \(M\)
Funkce \(f : \mathbb{N} \to M\) definovaná předpisem \(f(m) = k \cdot m\) je bijekce.
Krok 3: Spočetnost množiny \(M\)
Protože \(\mathbb{N}\) je spočetná a \(f\) je bijektivní, množina \(M\) je také spočetná.
Závěr: Množina všech přirozených čísel dělitelných číslem \(k\) je spočetná a má stejnou mohutnost jako množina \(\mathbb{N}\), tedy je spočetná.
98. Ukažte, že množina všech konečných množin přirozených čísel je spočetná.
Řešení příkladu:
Nechť \(\mathbb{N}\) je množina přirozených čísel. Chceme dokázat, že množina všech konečných podmnožin \(\mathbb{N}\) je spočetná.
Krok 1: Vyjádření jako sjednocení množin podmnožin pevné velikosti
Množina všech konečných podmnožin \(\mathbb{N}\) je sjednocení množin všech podmnožin s pevnou velikostí \(n\), tedy \[ F = \bigcup_{n=0}^\infty \{ A \subseteq \mathbb{N} : |A| = n \}. \]
Krok 2: Spočetnost podmnožin pevné velikosti
Pro pevné \(n\) je množina všech podmnožin velikosti \(n\) v bijekci s množinou všech uspořádaných \(n\)-ticí bez opakování prvků z \(\mathbb{N}\).
Uspořádané \(n\)-tice prvků z \(\mathbb{N}\) jsou spočetné, protože \(\mathbb{N}\) je spočetná a konečný součin spočetných množin je spočetný.
Tedy i množina všech podmnožin velikosti \(n\) je spočetná.
Krok 3: Sjednocení spočetně mnoha spočetných množin
Sjednocení spočetně mnoha spočetných množin je spočetné, tedy i množina všech konečných podmnožin \(\mathbb{N}\) je spočetná.
Závěr: Množina všech konečných podmnožin přirozených čísel je spočetná.
99. Dokažte, že množina všech funkcí z konečné množiny do konečné množiny je konečná a určete její počet.
Řešení příkladu:
Nechť \(M\) a \(N\) jsou konečné množiny s \(|M| = m\) a \(|N| = n\).
Krok 1: Definice funkce z \(M\) do \(N\)
Funkce \(f: M \to N\) přiřazují každému prvku z \(M\) právě jeden prvek z \(N\).
Krok 2: Počet funkcí
Každý prvek v \(M\) má \(n\) možností, kam se zobrazí. Proto celkový počet funkcí je \[ n^m, \] protože na každou z \(m\) pozic vybíráme nezávisle jeden z \(n\) prvků.
Krok 3: Závěr
Množina všech funkcí z konečné množiny \(M\) do konečné množiny \(N\) je konečná a její počet je \(n^m\).
100. Ukažte, že množina všech posloupností z prvků konečné množiny je spočetná.
Řešení příkladu:
Nechť \(M\) je konečná množina s \(|M| = m\).
Krok 1: Definice posloupností
Posloupnost je funkce z množiny \(\mathbb{N}\) do \(M\), tedy prvek z kartézského součinu \[ M^\mathbb{N} = \{ (a_1, a_2, a_3, \ldots) : a_i \in M \}. \]
Krok 2: Mohutnost množiny všech posloupností
Pokud je \(m > 1\), pak množina všech nekonečných posloupností má mohutnost \(m^{\aleph_0}\), což je nekonečno větší než spočetnost. Proto není spočetná.
Krok 3: Omezení na konečné posloupnosti
Pokud však omezíme množinu na konečné posloupnosti (tj. posloupnosti s konečnou délkou), pak podle předchozího příkladu je tato množina spočetná.
Závěr: Množina všech nekonečných posloupností z konečné množiny není spočetná, ale množina všech konečných posloupností je spočetná.