Počitatelná sada

Spočetná množina je nekonečná množina, jejíž prvky lze očíslovat přirozenými čísly . Formálněji: množina je spočetná, pokud existuje bijekce s množinou přirozených čísel: jinými slovy, spočetná množina je množina, která je svou mocností ekvivalentní množině přirozených čísel. V hierarchii alephs je mohutnost počitatelné množiny označena („aleph-nula“). $X$ $X\leftrightarrow \mathbb {N}$ $\aleph _{0}$

Vlastnosti

Spočetná množina je „nejjednodušší“ nekonečná množina v následujícím smyslu: v každé nekonečné množině existuje spočetná podmnožina . Ve skutečnosti budeme náhodně vybírat prvky z nekonečné množiny a k nim přiřazovat čísla. Protože množina je nekonečná, pro každou přirozenou je v ní prvek, který lze porovnat s číslem , ze kterého se na principu indukce vytvoří sestrojená podmnožina bude bijektivní s . $1,\,2,\,3,\,\ldots$ $n$ $n+1$ $\mathbb {N}$

Navíc, každá podmnožina spočetné množiny je buď konečná, nebo spočetná (ne více než spočetná). Prvky původní množiny vyčíslujeme přirozenými čísly, což je možné, protože je spočetná. U každého prvku víme, zda leží v naší podmnožině nebo ne. Procházíme-li je v pořadí, pokud další prvek neleží v podmnožině, přeskočíme jej; pokud leží, přiřaďte mu další číslo (číslování začneme ). Podle principu indukce bude podmnožina ekvivalentní , pokud není konečná. Všimněte si, že při řazení v pořadí jsme mezi již zvažovanými prvky žádný nevynechali. $jeden$ $\mathbb {N}$

Také nanejvýš spočetné (konečné nebo spočetné) sjednocení maximálně spočetných množin je nanejvýš spočetná množina . Vyjmenujeme prvky kombinovaných množin (nastavíme bijekci pomocí ). Existuje-li konečný počet počátečních množin , očíslujeme prvky — jejich sjednocení: Z indukce je snadné vidět, že je ustavena bijekce s . V případě nekonečného sjednocení toto pravidlo neplatí, ale podobné číslování je možné. Lze to vizualizovat následovně (další závěr však lze formalizovat): zapišme si prvky každé množiny (seřazené podle čísel) do sloupce. Udělejme z nich tabulku, jejíž sloupce definují každou množinu obsaženou ve sjednocení a řádky - určitá čísla každé z nich. Z levého horního rohu se staneme hadem, který obejde celý stůl a očísluje každou buňku na cestě. Indukcí objedeme celý stůl a výsledný svazek se ukáže jako spočetný. Obecně řečeno, stůl samotný bude muset být „postaven“ stejným hadem, protože je nekonečný. Prvky konečných množin lze vždy přiřadit jako první, čímž posuneme číslování o nějaké číslo. $\mathbb {N}$ $A,\,B,\,C,\,\ldots$ $n$ $S$ $s_{1}=a_{1},\;s_{2}=b_{1},\;\ldots ,\;s_{n+1}=a_{2},\;s_{n+ 2 }=b_{2},\;\ldots$ $\mathbb {N}$

Je také snadné ukázat, že přímý součin konečného počtu více než spočetných množin není více než spočetný . Uvažujme součin dvou množin, jeho počitatelnost je stanovena číslováním tabulky podobné výše uvedené, jejíž řádky jsou prvky jedné množiny a sloupce druhé. Součin konečného počtu množin se rozdělí na faktory, z nichž každý bude součinem původní multiplikační množiny a kartézským součinem dvou množin. Rozšiřme výsledný produkt od konce: očíslujme součin dvou množin, z nichž prvky jedné získáme očíslováním součinu dvou „příchozích“ množin, z nichž prvky jedné získáme stejným způsobem. . Pokračujme v rekurzi, která se neuzavře, protože množin je konečný počet. Všimněte si, že všechna čísla bude nutné hledat pomocí indukce a postupně doplňovat potřebné destičky na správných místech.

Nakonec , pokud k nekonečné množině přidáme konečnou nebo spočetnou množinu, dostaneme množinu, která je ekvivalentní původní [1] . Platnost výroku lze snadno ukázat, pokud v původní množině zvolíme spočetnou podmnožinu . Tedy, . Připojení k nejvýše spočetné množině nemění její mohutnost, takže pro nejvýše spočetnou množinu platí: . $A$ $B$ $A=(A\setminus B)\cup B\;\leftrightarrow (A\setminus B)\cup \mathbb {N}$ $B$ $C$ $A\cup C=(A\setminus B)\cup (B\cup C)\;\leftrightarrow (A\setminus B)\cup \mathbb {N} \;\leftrightarrow A$

Všimněte si, že množina všech konečných podmnožin spočetné množiny je spočetná . Množina konečných podmnožin prvků je spočetná, protože je podmnožinou kartézského součinu původních množin. Množina všech konečných podmnožin je spojením konečných podmnožin s určitým počtem prvků (které jsou spočetné), tedy spočetně. $n$ $n$

Množina všech podmnožin počitatelné množiny je však spojitá a není spočetná . Ukažme si skutečnost v obecnějším smyslu, že neexistuje bijekce mezi určitou množinou a množinou všech jejích podmnožin. Předpokládejme opak. Vybereme množinu všech prvků původní množiny, které nejsou spojeny s množinami obsahujícími samy sebe. Takový je samozřejmě prvek množiny všech podmnožin. Nelze jej přirovnat k žádnému prvku, který v něm leží na jedné straně (z definice), stejně jako k žádnému prvku, který v něm na druhé straně neleží (protože jinak by v něm takový prvek již ležel). Množina, kterou jsme sestrojili, je tedy prázdná, ale podmnožin obsahujících určitý prvek je vždy více než jedna; To znamená, že korespondence není individuální. Rozpor znamená, že předpoklad existence bijekce je nesprávný.

Příklady

Spočetné jsou množiny přirozených čísel $\mathbb {N}$ , celých čísel $\mathbb {Z}$ , racionálních čísel $\mathbb {Q}$ , algebraických čísel $\mathbb {A}$ . Počitatelné jsou objekty vyplývající z rekurzivních procedur , konkrétně se jedná o vypočitatelná čísla , aritmetická čísla (v důsledku toho je spočetný i kruh period , protože každá perioda je vyčíslitelná ). Množina všech konečných slov v spočetné abecedě a množina všech slov v konečné abecedě jsou spočetné. Jakékoli objekty, které lze definovat porovnáním jedna ku jedné s počitatelnou množinou, jsou spočetné, například: jakákoli nekonečná rodina neprotínajících se otevřených intervalů na reálné ose; množina všech přímek v rovině , z nichž každá obsahuje alespoň dva body s racionálními souřadnicemi ; jakákoli nekonečná množina bodů v rovině, jejíž všechny párové vzdálenosti mezi prvky jsou racionální.

Nespočetná množina je taková nekonečná množina , která není spočetná, jako jsou zejména množiny reálných čísel $\mathbb {R}$ , komplexních čísel $\mathbb {C}$ , čtveřice , Cayleyových čísel . Jakoukoli množinu lze tedy nazvat buď konečnou, nebo spočetnou nebo nepočitatelnou. $\mathbb {H}$ $\mathbb O$

Zajímavosti

Na první pohled se zdá nemožné vytvořit vzájemnou korespondenci mezi, řekněme , a , protože prvků druhé sady, jak se zdá, je dvakrát tolik. Ale tady máme co do činění s naším vnímáním pojmu nekonečno jako něčeho, co nemá konce. Tuto skutečnost můžete zkusit vnímat na následujícím, v jistém smyslu absurdním, příkladu. $\mathbb {N}$ $\mathbb {Z}$

Představme si, že pro zasedání galaktické rady byl postaven hotel s nekonečným počtem pokojů a tak se stalo, že všechny pokoje byly obsazeny. V tu chvíli dorazili diplomaté, které bylo potřeba přesídlit. Vzhledem k tomu, že existuje nespočet hotelových pokojů a samotných obyvatel, navrhneme následující strategii pro přesídlení nově příchozích. Přesuňme hosty z -té místnosti do -té, bydlící v -té v -té a pak v pořádku. V uvolněných prvních pokojích totiž ubytujeme ty, co dorazili. Hotel, jak byl plně obsazen, však zůstane. Jak se ukázalo, žádná prázdná místa nebyla. V reprezentaci nekonečna jako určité konečnosti se nachází rozpor. Nekonečno je však charakterizováno právě absencí svého konce, jinými slovy, nekonečno s přidáním konce je úplně stejné nekonečno. $n$ $jeden$ $(n+1)$ $2$ $(n+2)$ $n$

Také je možné poměrně elegantní formou zabalit důkaz o absenci bijekce mezi určitou množinou a množinou všech jejích podmnožin. První nazvěme množina lidí (lze předpokládat, že akce se odehrávají ve stejné galaxii), a druhou společnost. Předpokládejme, že v každé společnosti je jeden (a jediný) zástupce zastupující pouze jeho. Za hrdiny označme ty, kteří reprezentují společnost, do které nepatří. Ukazuje se, že hrdina nemůže představovat všechny hrdiny. Ale to nemůže udělat ani nehrdina, protože spácháním takového hrdinského činu by se stal hrdinou. V galaxii proto nebyli žádní hrdinové, jinak je náš předpoklad mylný. Ne každá společnost se ale bez hrdiny obejde, takže naše domněnka je jistě mylná. Ukazuje se, že žádná bijekce neexistuje

Poznámky

↑ Brudno, 1971 , s. čtrnáct.

Literatura

Brudno A. L. Teorie funkcí reálné proměnné. - M. : Nauka, 1971. - 119 s.