Jak porovnat velikosti dvou množin?
U konečných množin obvykle postupujeme tak, že spočítáme jejich prvky a pak porovnáme sumy mezi sebou. Velikost konečné množiny totiž můžeme vyjádřit snadno přirozeným číslem. Existuje však zobecnění, kterému říkáme mohutnost nebo kardinalita. Touto metodou navíc dokážeme porovnat i nekonečné množiny.
George Cantor se věnoval teorii množin a jako kritérium pro srovnání velikosti množin určil existenci vzájemně jednoznačného zobrazení. Jestliže takové zobrazení mezi dvěma množinami existuje, pak mají stejnou mohutnost. Cantor byl první, kdo se tohoto kroku důsledně odvážil.^1 Tato metoda je známá jako Cantorova-Bernsteinova věta.
Pro tyto množiny mohou tedy nastat následující tři případy:
- Pokud množiny A a B mají stejný počet prvků, existuje prosté zobrazení A na B.
- Pokud množina A má méně prvků než B, existuje prosté zobrazení A do B, ale neexistuje prosté zobrazení B do A.
- Pokud množina B má méně prvků než A, existuje prosté zobrazení B do A, ale neexistuje prosté zobrazení A do B.
Pokud u konečných množin existuje prosté zobrazení jedné na druhou, potom každé jiné prosté zobrazení jedné do druhé je také zobrazením na tuto množinu. Přirozená čísla jsou kardinálními čísly konečných množin.
Nekonečné množiny
U nekonečných množin budeme považovat za „stejně velké“, přesněji říkat, že mají stejnou mohutnost, pokud mezi nimi existuje bijektivní zobrazení.
Příklad: N nechť je množina všech přirozených čísel, S množina všech sudých přirozených čísel.
- f(n) = n je prosté zobrazení S do N, které není zobrazením na N.
- g(n) = 4⋅n je prosté zobrazení N do S, které není na zobrazením S.
- h(n) = 2⋅n je prosté zobrazení S na N, tedy bijekce.
Zavedení operace mohutnosti
Mohutnost množiny A označujeme card(A)
, nebo moh(A)
, někdy též |A|
.
Množiny, které mají mohutnost stejnou jako je mohutnost množiny přirozených čísel (ℕ) se nazývají spočetné. Lze je charakterizovat tím, že všechny jejich prvky lze seřadit do posloupnosti.
Cantor - Bernsteinova věta
Abychom mohli mohutnosti porovnávat navzájem potřebujeme následující větu, která vpodstatě říká, co už jsme si tu naznačili. Tedy:
Nechť existuje prosté zobrazení množiny A do množiny B a současně existuje prosté zobrazení množiny B do množiny
f: A → B a g: B → A.
Potom existuje zobrazení h: A → B
které je bijektivní.
Rovnost
Říkáme, že množiny A a B mají stejnou mohutnost, pokud existuje bijektivní zobrazení mezi A a B.
Menší nebo rovna
Říkáme, že množina A má mohutnost menší nebo rovnu mohutnosti B, pokud existuje prosté zobrazení A do B, tedy na podmnožinu B.
menší než
Říkáme, že mohutnost množiny A je menší než mohutnost množiny B, pokud existuje prosté zobrazení A do B a neexistuje prosté zobrazení A na B.
Kardinální číslo je společná vlastnost množin stejné mohutnosti.