Mohutnost množiny (také kardinalita množiny) je pojmem teorie množin vyjadřující velikost, počet prvků u konečných, ale i nekonečných množin. Značí se většinou , někdy též . Pojem „kardinalita“ zdůrazňuje, že pro vyjádření mohutností lze použít kardinální čísla, což v nejběžnější axiomatizaci (ZFC) platí beze zbytku, zatímco v jiných (ZF) existují množiny, které nelze bijektivně zobrazit na žádné kardinální číslo.
Mnohá fakta, která jsou pro konečné množiny samozřejmá, u nekonečných množin neplatí. Například, že může existovat bijekce mezi množinou a množinou o jeden prvek větší, když . Například je bijekce mezi přirozenými čísly (bez nuly) a přirozenými čísly s nulou.
Množiny prostě zobrazitelné do přirozených čísel se nazývají spočetné. Spočetné jsou mnohé množiny „menší“ než přirozená čísla, např. množina všech prvočísel. Stejně tak i mnohé množiny „mnohem větší“, jako celá čísla, racionální čísla, algebraická čísla, n-tice racionálních čísel, a dokonce množina všech konečných posloupností (nejrůznějších délek) přirozených čísel, nebo analogicky množina všech slov nad konečnou či spočetnou formální abecedou.
Proto je při studiu nekonečných množin nutné oprostit se od všech předpokladů kromě těch, které se dají exaktně dokázat. V naivní i axiomatické teorii množin jsou dokazatelné např. tyto dvě věty:
Cantorova věta: U žádné množiny neexistuje bijektivní (dokonce ani prosté) zobrazení z do , tj. takové, které by každé podmnožině přiřadilo prvek (pokaždé jiný) . Jinými slovy, každá množina, konečná i nekonečná, má významně více podmnožin, než kolik má prvků. Důsledkem je, že množina reálných čísel je nespočetná.
Cantorova–Bernsteinova věta: Existuje-li prosté zobrazení z množiny do a též nějaké prosté zobrazení z do , pak mezi a existuje bijekce.
V axiomatické teorie množin se pak pro porovnávání velikostí množin zavádí pojem kardinální číslo. Přijetí dodatečného axiomu, axiomu výběru (jenž je ekvivalentní s principem dobrého uspořádání) značně zpřehledňuje porovnávání velikostí množin, protože pak pro každou množinu existuje právě jedno kardinální číslo, s nímž má stejnou mohutnost. Toto číslo se nazývá kardinalita.
Formální definice Nechť , jsou množiny. Řekneme, že množina má stejnou nebo menší mohutnost než množina , jestliže existuje zobrazení , které je injektivní. Píšeme . Řekneme, že množiny , mají stejnou mohutnost (říkáme také, že jsou ekvivalentní), jestliže existuje zobrazení které je bijektivní. Píšeme . Řekneme, že množina má menší mohutnost než množina , jestliže , ale přitom neplatí . Píšeme .
Souvislost s kardinálními čísly Výše jsme definovali pojem „mít větší mohutnost“, ale nikoli pojem „mohutnost“:
Právě uvedené pojmy jsou mnohem snazší k pochopení, než pojem kardinálního čísla, a lze je zavádět i bez znalosti kardinálních čísel. Jsou velmi užitečným nástrojem pro práci s „běžnými“ množinami (například lze jimi snadno dokázat, že algebraických čísel je méně než reálných a tedy nutně musí existovat transcendentní čísla). Relace „mít menší/větší/stejnou“ mohutnost umožňují kvalitativně množiny co do velikosti srovnávat, ale neposkytují způsob, jak jejich velikosti vyjádřit kvantitativně.
Pro kvantifikování velikostí nekonečných množin slouží kardinální čísla. Pojem mohutnost se pak používá jako synonymum k pojmu kardinalita; oba značí kardinální číslo vyjadřující velikost příslušné množiny. Kardinální čísla lze mezi sebou porovnávat; kardinalita množiny A je menší než kardinalita množiny B, právě tehdy, když A má menší mohutnost než B.
S ohledem na to, že je ekvivalence a že kardinální čísla jsou určena především k „zastupování ostatních množin ve věci jejich mohutnosti“, nabízí se samozřejmě otázka, zda je každá množina stejně mohutná, jako některé z kardinálních čísel, tj. zda v každé třídě rozkladu relace je alespoň jeden kardinál. Odpověď zní ano – ale pouze za předpokladu, že přijmeme axiom výběru – bez něj mohou ve světě množin existovat takové množiny, které nelze vzájemně jednoznačně zobrazit na žádný kardinál.
Vlastnosti pojmu mohutnosti
Základní vlastnosti relace ≈ Relace je reflexivní, symetrická a tranzitivní:
Jedná se tedy o ekvivalenci na univerzální třídě – všechny myslitelné množiny se rozpadají do skupin (tříd ekvivalence neboli faktortříd) podle své mohutnosti.
Základní vlastnosti relace ≼ Relace je (na univerzální třídě ) reflexivní a tranzitivní:
Nejedná se však o uspořádání, neboť tato relace není antisymetrická a to ani slabě:
Například pro dvě různé množiny a platí .
Cantorova-Bernsteinova věta uvedená v následujícím odstavci, poukazuje na fakt, že relace je „skoroantisymetrická“ – dává do vztahu relace a v následujícím smyslu. Protože relace je ekvivalencí na univerzální třídě , lze univerzální třídu podle této relace faktorizovat. Cantorova-Bernsteinova věta pak říká, že relace (resp. její přirozené přenesení na třídu faktortříd ) je na slabě antisymetrická, a tedy je neostrým uspořádáním.
Základní vlastnosti relace ≺ Jiná situace je u relace , která je antireflexivní, antisymetrická i tranzitivní:
Je tedy ostrým uspořádáním na V.
V případě přijetí axiomu výběru je toto uspořádání lineární vzhledem k ekvivalenci : .
Cantorova-Bernsteinova věta Cantorova-Bernsteinova věta uvádí do souvislosti obě relace týkající se mohutnosti:
Myšlenka důkazu této věty je uvedena v samostatném článku.
Cantorova věta Cantorova věta uvádí do vztahu mohutnost množiny a její potenční množiny:
Příklady
Z0+ a Z+ Nekonečné množiny porušují lidskou intuitivní představu, že žádná množina nemůže být ekvivalentní (tj. stejně velká) se svojí částí (vlastní podmnožinou). Například množina Z0+ celých nezáporných čísel (tedy přirozených čísel včetně nuly) je ekvivalentní s množinou Z+ celých kladných čísel (tj. přirozených čísel bez nuly). Touto ekvivalencí je zobrazení f(x) = x + 1, které splňuje všechny požadavky bijekce ze Z0+ do Z+: Jeho definiční obor je přesně Z0+ Jeho obor hodnot je přesně Z+ (je surjektivní) Různým argumentům přiřadí různé hodnoty, tedy je prosté (injektivní)
Z+ a Z Celých čísel je stejně, jako celých kladných čísel. To lze dokázat tak, že celá čísla seřadíme: 0, 1, -1, 2, -2, 3, -3, 4, -4……
Formálně zapsáno, tuto ekvivalenci množin dosvědčuje zobrazení f(x) definované takto:
f(0) = 1 (nula je na první pozici ve výše uvedené posloupnosti) f(x) = 2× pro x>0 (například trojka je na šesté pozici) f(x) = 1+2|x| pro x<0 (například -3 je na sedmé pozici)
Uspořádané dvojice a n-tice Uspořádaných dvojic celých kladných čísel je stejně, jako celých kladných čísel. To lze dokázat tak, že uspořádané dvojice (a,b) seřadíme podle a+b a v případě rovnosti a dvojice se shodným a+b podle b
(1,1); (2,1); (1;2); (3,1); (2,2); (1,3); (4,1); (3,2); (2,3); (1,4); (5,1) atd...
Bijekcí je zde zobrazení (označíme jej T2(x,y)), které dvojici čísel přiřadí její pozici ve výše uvedené posloupnosti. Například T2(2,2) = 5.
Podobně lze na celá kladná čísla zobrazit uspořádaná trojice: T3(x,y,z) = T2 (T2(x,y), z). Toto lze zobecnit pro každé přirozené číslo n>0: Bijekci mezi množinami n-tic a Z+ tvoří zobrazení Tn(x1, x2 ... xn-1, xn) = T2 (Tn-1 (x1, x2 ... xn-1), xn) Racionální čísla V prvním kroku odhlédneme od toho, že např. , a seřadíme všechny zlomky podle |a|+b, přičemž zlomky se stejným |a|+b seřadíme podle a. Obdržíme posloupnost:
Množina racionálních čísel je (dle své definice) ekvivalentní s množinou zlomků v základním tvaru; v naší posloupnosti však máme i zlomky, které nejsou v základním tvaru, například . To lze vyřešit dvěma způsoby:
můžeme z posloupnosti vynechat zlomky, které nejsou v základním tvaru, a u každého čísla uvažovat jeho index v takto vybrané posloupnosti. Prvním takto vynechaným číslem bude na deváté pozici; proto zlomek , který měl v původní posloupnosti index 10, bude ve vybrané posloupnosti mít index 9. Každému racionálnímu číslu pak přiřadíme index odpovídajícího zlomku ve vybrané posloupnosti a tak obdržíme hledanou bijekci.
Druhou možností je použít Cantorovu-Bernsteinova větu: platí, protože platí, protože každému racionálnímu číslu můžeme přiřadit index odpovídající zlomku v základním tvaru. Tím ovšem nevyčerpáme všechna přirozená čísla, neboť některé zlomky nejsou v základním tvaru. Jsou splněny předpoklady Cantorovy-Bernsteinovy věty, a proto jsou množiny Z+ a Q ekvivalentní.
Posloupnosti čísel Uvažme množinu P všech konečných posloupností celých kladných čísel libovolné délky (včetně prázdné posloupnosti délky nula). Zdánlivě je P větší, než množina všech n-tic pro jakékoli pevné n. Ve skutečnosti je však P ekvivalentní se Z+. Pro důkaz uvažujme zobrazení, které posloupnosti (a1, a2…, an) přiřadí číslo
T2(1+n, Tn(a1, a2, ..., an))
Jedničku přičítáme proto, abychom funkci T2 nepředali nulu, jde-li o posloupnost délky 0; takové posloupnosti přiřadíme číslo T2(1, 1) – což neplyne u uvedené formule, protože funkci T0 nemáme definovanou; funkci T1 lze definovat jako T1(x) = x.
Toto zobrazení ještě není bijekcí, protože v jeho oboru hodnot neleží čísla T2(1, 2), T2(1, 3), T2(1, 4) atd. (Jinými slovy: je jen jedna prázdná posloupnost, ale my pro ni máme "rezervováno" nekonečně mnoho míst.) Bijekci dále sestrojíme stejným způsobem, jako výše u racionálních čísel.
Algebraická čísla Reálné číslo se nazývá algebraické, pokud je kořenem nějakého polynomu s celočíselnými koeficienty. Každý takový polynom má jen konečně mnoho kořenů.
Proto můžeme každému algebraickému číslu x přiřadit přirozené číslo T3(n,p,q), kde: n je nejmenší stupeň polynomu, mezi jehož kořeny patří x p je nejmenší číslo, které je kódem některého z takových polynomů. Polynom s koeficienty z0 až zn lze zakódovat jako Tn+1 (c(z0), c(z1), …, c(zn)), kde c je bijekce z celých do celých kladných čísel q vyjadřuje, kolikátým kořenem polynomu je číslo x.
Z tohoto zobrazení lze vytvořit bijekci stejně, jako u racionálních čísel.
Reálná čísla a potence celých kladných čísel Vztah plyne přímo z Cantorovy věty uvedené výše.
Potenční množina přirozených čísel je ekvivalentní s množinou reálných čísel (). To plyne z Cantorovy-Bernsteinovy věty, protože jsou splněny její předpoklady: , což je dosvědčováno injektivním zobrazením f(M) = , kde každé množině lze přiřadit koeficienty takto: když , jinak . Jinými slovy, číslo f(M) bude mít v desetinném rozvoji jedničku na i-tém desetinném místě, pokud i je prvkem M. plyne z toho, že , protože každé reálné číslo lze prostě zobrazit do otevřeného intervalu zobrazením , kde číslu lze přiřadit množinu všech pozic, na kterých je v binárním desetinném rozvoji jednička. Například číslo lze binárně zapsat jako 0,1 nebo jako 0,011111111111…. Pro definici injektivního zobrazení preferujeme první z těchto zápisů; proto toto zobrazení není surjektivní. Z toho plyne, že množina reálných čísel není spočetná.
Důkaz existence transcendentních čísel Reálné číslo se nazývá transcendentní, pokud není algebraické. Výše jsme dokázali, že množina algebraických čísel je spočetná, zatímco množina reálných čísel nikoli. Proto nemohou být totožné, čili existují transcendentní čísla. Toto je snazší důkaz existence, než dokazovat například, že Ludolfovo číslo je transcendentní; je to ovšem důkaz nekonstruktivní (nedává návod, jak transcendentní číslo nalézt).
Mohutnosti některých množin Mohutnost konečné množiny je rovna počtu jejích prvků.
Spočetné množiny Mohutnost množiny přirozených čísel se obvykle označuje ("alef nula" – alef je první písmeno hebrejské abecedy). Množiny se stejnou mohutností, jako přirozená čísla, se nazývají spočetné. Každá nekonečná podmnožina přirozených čísel je spočetná, např. množina: sudých přirozených čísel, prvočísel.
Naopak některé množiny, které intuitivně vnímáme jako větší, mají stejnou mohutnost, jako přirozená čísla. Mohutnost rovnou mají množiny: přirozených čísel, celých čísel, racionálních čísel, algebraických čísel, všech konečných podmnožin přirozených čísel.
Reálná čísla (kontinuum)