Množinová aritmetika

Cantor-Bernstien

"Cantor-Bernsteinova veta" (tiež známa ako "veta o ekvivalencii kardinality") znie nasledovne:
Veta- Cantor-Bernstein.
Ak existujú dve množiny \small A a \small B, pre ktoré existujú injektívne zobrazenia f: \small A \to \small B a g: \small B \to \small A , potom existuje bijektívne zobrazenie medzi \small A a \small B , t.j. \small A a \small B majú rovnakú kardinalitu.

Poznámky - Injektívne zobrazenie.
  • f: \small A \to \small B je injekcia, čo znamená, že každý prvok z \small A je priradený k jedinečnému prvku v \small B .
  • g: \small B \to \small A je tiež injekcia, teda každý prvok z \small B je priradený k jedinečnému prvku v \small A .
Dôsledok vety.
Toto tvrdenie umožňuje porovnávať kardinality nekonečných množín. Ak existujú injektívne zobrazenia medzi množinami, potom tieto množiny majú "rovnaký počet prvkov", kde porovnávanie veľkosti množín nie je také jednoduché ako u konečných množín. Túto vetu budeme veľmi často využívať, ak budeme chcieť dokázať, že dve množiny majú rovnakú kardinalitu. Mnohokrát je totiž jednoduchšie skonštruovať injekcie oboma smermi, než priamo nájsť bijekciu medzi danými množinami.
Dôkaz vety.
Dôkaz sa dá rozčleniť do niekoľkých krokov:
  1. Predpoklady
    Máme dve množiny \small A a \small B a zobrazenia:
        f: \small A \to \small B je injektívne (teda f je funkcia, ktorá priraďuje rôzne prvky a_1 a a_2 z \small A rôznym prvkom v \small B );
      g: \small B \to \small A je tiež injektívne. Cieľom je nájsť bijekciu medzi \small A a \small B , teda zobrazenie, ktoré je aj injektívne (jednoznačne priraďuje prvky) a surjektívne (každý prvok v \small A má svoj obraz v \small B ).
  2. Zostavenie zobrazenia
    Začneme tým, že vytvoríme zobrazenie h: \small A \to \small B pomocou f a g .
    A. Rozdelíme množinu \small A na disjunktné podmnožiny, ktoré budeme označovať ako **reprezentatívne triedy**. Tieto triedy sú definované pomocou cyklov zobrazenia g a zobrazenia f .
    B. Pre každý prvok a \in \small A hľadáme najbližší obraz v \small B , ktorý je spojený s a cez f a g . Týmto spôsobom vytvoríme "uzavretú" bijekciu.
  3. Dôkaz injektivity a surjektivity
    **Injektivita:** Zobrazenie h je injektívne, pretože pri zostavovaní h používame injektívne zobrazenia f a g , a každé spojenie medzi \small A a \small B je jedinečné.
    **Surjektivita:** Zobrazenie h je surjektívne, pretože každý prvok b \in \small B je dosiahnutý z nejakého a \in \small A , vďaka tomu, že g je injektívne.
  4. Uzavretie dôkazu
    Keďže h je injektívne aj surjektívne, je to bijekcia, a preto \small A a \small B majú rovnakú kardinalitu.
Týmto je dôkaz dokončený.
Tento dôkaz používa princíp z "vybudovania" bijekcie pomocou injektívnych zobrazení, ktorý je kľúčovým nástrojom v Cantor-Bernsteinovej vete.
Poznámky k zostaveniu zobrazenia
Keďže f je injekcia, tak obrazom prvku a ∈ \small A je nanajvýš jeden prvok b ∈ \small B: f(a) = b . Tento prvok b , ak existuje, má najviac jedného rodiča a' = f^{-1}(b) atď.


Takýmto spôsobom sledujme všetkých predkov daného prvku a ∈ A tak dlho, ako to je len možné. Môžu nastať tri navzájom sa vylučujúce prípady:

  1. každý predok daného prvku má rodiča; t.j. existuje nekonečná reťaz predkov,
  2. prvok má takého predka v množine \small A, ktorý už nemá rodiča (reťaz končí v \small A),
  3. prvok má takého predka v množine \small B, ktorý už nemá rodiča (reťaz končí v \small B).
Vzhľadom na uvedené tri prípady rozdelíme \small A na tri podmnožiny \small A_1, \small A_2, \small A_3 a podobne rozdelíme \small B na tri podmnožiny \small B_1, \small B_2, \small B_3. Definujme zobrazenie h:\small A → \small B takto: 
 
h(x) =
\begin{cases}
f(x), & \text{ak } x \in \small A_1 \cup \small A_3, \\
g^{-1}(x), & \text{ak } x \in \small A_2.
\end{cases} ,
ktoré je bijektívne. Pozrite si ilustračný nasledujúci príklad.
\( .\)