Spočetné množiny

Určit velikost konečné množiny je jednoduché, spočítáme počet prvků. Takže množina M = {a, b, c, d, e} má velikost 5, zapíšeme |M| = 5.

U nekonečných množin je situace o poznání složitější. Jak bychom mohli porovnat velikost nekonečných množin? Lze to vůbec, nebo jsou všechny nekonečné množiny „stejně velké“?

Pro příklad si vezměme množinu přirozených čísel a množinu sudých přirozených čísel. Máme tak množiny ℕ = {1, 2, 3, 4, 5, 6, …} a S = {2, 4, 6, …}. Chtělo by se říci, že množina přirozených čísel je větší než množina sudých čísel, protože přirozená čísla v sobě obsahují všechna sudá čísla a ještě k tomu nějaké prvky navíc — lichá čísla.

Takže bychom mohli napsat, že platí S ⊂ ℕ, množina S je vlastní podmnožinou množiny ℕ. A mohli bychom říci, že pokud S ⊂ ℕ, tak je množina ℕvětší — obsahuje přece více prvků než množina S.

Jedním z důvodů, proč nemůžeme množiny měřit podle relace podmnožiny, je fakt, že množiny mohou mít různou velikost, přestože ani jedna množina není podmnožinou druhé. To lze předvést i na konečných množinách: A = {1, 3, 4, 9} aB = {b, u, r, z, m}. Platí: |A| = 4 a |B| = 5. Množina B je větší než množina A, přitom ale neplatí A ⊂ B. V případě nekonečných množin to můžeme vidět na sudých a lichých číslech. Ani jedna množina není podmnožinou jiné.

Relace podmnožiny tak nebude ideální kandidát na rozhodování, zda je jedna množina větší než druhá.

Zkusíme jiný přístup. Máme dvě množiny, A a B. Můžeme říci, že mají stejnou velikost, pokud mezi nimi existuje bijektivní zobrazení. Co to znamená? Že vezmeme prvek z množiny A, prvek z množiny B a vytvoříme dvojici [a, b]. Tyto prvky z množin odstraníme a pokračujeme dále. Pokud dokážeme „vyprázdnit“ obě množiny, našli jsme bijektivní zobrazení.

Příklad na konečných množinách: A = {a, b, c} a B = {1, 2, 3}. První dvojice by mohla být [a, 1], další [b, 2] a nakonec [c, 3]. Vyčerpali jsme všechny prvky z obou množin, našli jsme bijektivní zobrazení. Důležité je, že toto není jediné bijektivní zobrazení. I toto je platné řešení: [a, 3], [b, 1], [c, 2].

U nekonečných množin je to už trochu zajímavější. Zkusíme lichá a sudá přirozená čísla. Intuitivně cítíme, že by jich mělo být stejně. Zkusíme to. Vezmeme první liché číslo a zobrazíme ho na první sudé číslo: [1, 2]. Dále druhé liché a druhé sudé: [3, 4]. Atd. Dostáváme tak dvojice: [1, 2], [3, 4], [5, 6], [7, 8], …Mohli bychom napsat, že každé liché číslo l se zobrazuje na sudé číslo l+1 a každé sudé číslo s je obrazem lichého čísla s−1. Pro každé liché a pro každé sudé číslo tak máme nějakou dvojici, která to číslo obsahuje. Množiny lichých a sudých čísel jsou tak stejně velké.

Nyní zkusíme stejný postup a porovnáme množinu přirozených a sudých čísel. Máme tak množiny ℕ = {1, 2, 3, 4, 5, 6, …} a S = {2, 4, 6, …}. Intuitivně očekáváme, že množina přirozených čísel bude větší.

Zkusme nyní ale najít dané bijektivní zobrazení. Můžeme říci, že každé přirozené číslo n se zobrazují na svůj dvojnásobek, na 2n. Tím dostaneme dvojice [1, 2], [2, 4], [3, 6], [4, 8], [5, 10], … Pro každé přirozené číslo n tak máme dvojici [n, 2n] a pro každé sudé číslo s máme dvojici [s/2, s]. Našli jsme bijektivní zobrazení, množina sudých čísel a množina přirozených čísel je tak stejně velká, mají stejnou kardinalitu.

Toto se může zdát zmatené, protože přirozená čísla přece obsahují více prvků, než sudá čísla. Přirozená čísla obsahují všechny sudá čísla a ještě k tomu všechna lichá čísla. Nicméně dokážeme nalézt bijekci, takže jsou obě množiny stejné.

Přirozená čísla se ve skutečnosti definují nejmenší velikost nekonečné množiny. Zda má nějaká jiná množina stejnou velikost jako množina přirozených čísel lze často zjistit poměrně snadno — stačí nalézt bijekci na přirozená čísla, což v praxi znamená, že stačí, když dokážeme prvky naší množiny M očíslovat, uspořádat.

Tedy dokážeme-li prvky množiny seřadit tak, abychom rozhodli, který prvek je první, který druhý, třetí, čtvrtý, desátý, atp., tak je množina stejně velká jakoℕ. O takové množině pak říkáme, že je spočetná.

Lehce vidíme, že sudá a lichá přirozená čísla jsou spočetná, protože umíme určit první, druhé, třetí atp. sudé/liché číslo. Co sudá celá čísla? Tj. množina S ={…, −4, −2, 0, 2, 4, …}. Dokážeme je uspořádat? Dokážeme, stačí vzít stejné uspořádání jako minule a hned za kladné sudé číslo zapíšeme i jeho zápornou variantu: S = {0, 2, −2, 4, −4, 6, −6, …}. Podobně například pro celá čísla.

Zajímavějším příkladem jsou racionální čísla, zlomky. Dokážeme je uspořádat? Dokážeme, ale bude to už o trochu složitější, Sestrojíme tabulku, která má nekonečně mnoho řádků a sloupců. V každé buňce bude zlomek. V n-tém řádku a m-tém sloupci budeme mít zlomek n/m. Tedy v 1. řádku a 2. sloupci máme ½a ve třetím řádku a čtvrtém sloupci máme 3/4.

Jak nyní tato čísla seřadit, očíslovat? Nemůžeme je očíslovat po řádcích nebo po sloupcích, protože bychom se hned utopili v daném řádku/sloupci. Místo toho vezmeme čísla po diagonálách: (první diagonála:) 1/1, (druhá diagonála:) 2/1, 1/2, (třetí diagonála:) 3/1, 2/2, 1/3, (čtvrtá diagonála:) 4/1, 3/2, 2/3, 1/4, … Je tam ještě plno duplicitních zlomků, ale to nevadí. Co vadí více je, že tam nejsou záporná čísla. To lze vyřešit jednoduše, vždy, když napíšeme nějaký zlomek, umístíme hned za něj jeho zápornou variantu. A pak už nám úplně na začátku chybí nula. A to už je vše, máme všechna racionální čísla v posloupnosti.

Celkově tak dostáváme posloupnost: 0, 1/1, −1/1, 2/1, −2/1, 1/2, −1/2, 3/1, −3/1, 2/2, −2/2, 1/3, −1/3, …

Jsou reálná čísla stejně velká jako přirozená čísla? Rozhodnutí bude ještě složitější než v případě racionálních čísel. Provedeme důkaz sporem. Předpokládejme, že reálná čísla jsou spočetná a že existuje bijektivní zobrazení na přirozená čísla. Předpokládejme tak, že jdou uspořádat. A dejme tomu, že toto následující zobrazení je ono uspořádání:

V tabulce je prvních sedm reálných čísel, která jsou v našem uspořádání. Toto uspořádání samozřejmě může být libovolné, nemusí to být seřazeno podle velikosti čísel.

Dle předpokladu jsou v této nekonečné tabulce uspořádána všechna reálná čísla. (Tabulka je opět nekonečná, zde je jen prvních sedm záznamů.) My se teď pokusíme najít/sestrojit takové číslo, které je reálné, ale není uvedeno v této tabulce. Pokud takové číslo nalezneme, tak je to spor s tím, že jsou v tabulce všechna reálná čísla, z čehož můžeme dále usoudit, že množina reálných čísel není spočetná.

Ono číslo, které v tabulce není, sestrojíme takto:

Začneme tím, že napíšeme 0, … Takto bude naše nové reálné číslo vypadat na začátku. Na prvním desetinném místě pak bude taková číslice, které není na první místě v prvním reálném čísle našeho uspořádání (v tabulce je to zvýrazněno rámečkem). Tam je číslice 3, takže zvolíme například 1 a dostáváme číslo 0, 1…

Pokračujeme dále. Na druhém místě bude číslice, která není na druhém místě druhého reálného čísla. Tam je 9, takže například 2. Dostaneme číslo 0, 12… Na třetím místě bude číslice, která je odlišná od třetí číslice ve třetím reálném čísle. Tam je 3, takže zvolíme třeba 7. Dostáváme 0, 127…

A tak dále a tak dále. Vždy na n-té pozici nového čísla bude číslice, která je odlišná od číslice, která je na n-té pozici n-tého čísla v našem uspořádání.

Co tím získáme? Získáme tím číslo, které se liší od všech čísel v našem uspořádání minimálně o jednu číslici. Vezměme si poslední dočasný výsledek: 0, 127… Toto číslo se určitě liší od prvního čísla v našem uspořádání minimálně v první číslici — protože jsme to tak sestavili. Od druhého čísla se liší minimálně v druhé číslici. Od třetího v třetí číslici. Obecně toto nové číslo se čísla v uspořádání, které je na n-tém místě, liší nejméně v číslici na n-té pozici.

Toto nově sestrojené číslo tak nenajdeme v tabulce, která měla symbolizovat bijekci mezi přirozenými čísly a reálnými čísly. Reálná čísla jsou tak větší než přirozená čísla. Reálná čísla nejsou spočetná, jsou nespočetná.