Cantorova–Bernsteinova věta

Cantorova-Bernsteinova věta (také Cantorova-Schröderova-Bernsteinova věta) je matematické tvrzení z oblasti teorie množin, které má zásadní význam pro srovnávání nekonečných mohutností. Tvrdí, že

• existuje-li prosté zobrazení z množiny $A$ do $B$ (jinými slovy $A$ má nejvýše stejnou mohutnost, jako $B$),
• a pokud zároveň existuje prosté zobrazení z $B$ do$A$ (tj. $A$ má nejméně stejnou mohutnost, jako $B$),
• pak mezi nimi existuje bijekce, tj. obě mají stejnou mohutnost.

Toto tvrzení lze dokázat v naivní i axiomatické teorii množin, a to i bez použití axiomu výběru, který porovnání nekonečných mohutností zásadně usnadňuje. Platí tedy i ve „světech matematiky“ (tj. modelech ZF), které axiom výběru nesplňují.

Znění

Nejpřirozenější formulací Cantorovy-Bernsteinovy věty je následující:

Má-li množina A mohutnost menší nebo rovnu než množina B a množina B má mohutnost menší nebo rovnu než množina A, pak množiny A,B mají stejnou mohutnost.

Zapracujeme-li do této formulace i definici pojmu mohutnosti, dostaneme zápis o trochu méně srozumitelný, z nějž je však lépe vidět podstata problému:

Existují-li prosté zobrazení množiny A do množiny B, a prosté zobrazení množiny B do množiny A, pak existuje bijekce mezi těmito dvěma množinami.

Příklad použití

Tato věta je užitečná v případech, kdy pro množinu, jejíž mohutnost je zkoumána, lze najít horní i dolní odhad její mohutnosti a oba dva jsou stejné.

Mohutnost reálných čísel

Reálná čísla lze bijektivně zobrazit na $\mathbb {P} (\mathbb {N} )$, tj. množinu všech podmnožin přirozených čísel. Bez Cantorovy-Bersteinovy věty je ovšem důkaz pracný.

Reálná čísla lze funkcí arkus tangens zobrazit na otevřený interval $(-\pi /2,\pi /2)$ a ten lineárně „posunout a stlačit“ na $(0;1)$. Proto stačí nalézt bijekci mezi $(0;1)$ a $\mathbb {P} (\mathbb {N} )$.

Důkaz bez použití věty

Každý prvek $\mathbb {P} (\mathbb {N} )$ lze chápat jako posloupnost nul a jedniček, potažmo jako desetinný rozvoj nějakého reálného čísla z $\langle 0;1\rangle$ v binární (tj. dvojkové) soustavě; dvojkovou soustavou lze zapisovat reálná čísla podobně, jako v desítkové soustavě. Např. množině $\{2,5,6\}\in \mathbb {P} (\mathbb {N} )$ lze přiřadit desetinný rozvoj $0,010011$ (který je konečný, tj. pokračující dále jen nulami) a tento rozvoj reprezentuje reálné číslo $2^{-2}+2^{-5}+2^{-6}={\frac {16+2+1}{64}}=0{,}296875$.

Pokud se množina všech takových binárních rozvojů označí $^{\mathbb {N} }2$, každé číslo z $(0;1)$ lze takto reprezentovat alepoň jedním rozvojem z $^{\mathbb {N} }2$, ale ne vždy jednoznačně: např. konečný rozvoj $0{,}011$ reprezentuje stejné reálné číslo ($3/8=0{,}375$), jako rozvoj $=0{,}01011{\overline {1}}\ldots$, v němž symbol ${\overline {1}}$ značí, že rozvoj pokračuje dále jen jedničkami.

Proto je třeba najít množinu $V$ „vyřazených“ desetinných rozvojů tak, aby nevyřazené přesně koresponovaly s reálnými čísly z $(0;1)$, tj. aby existovala bijekce mezi $(0;1)$ a množinovým rozdílem $^{\mathbb {N} }2-V$. K tomu poslouží $V$ skládající se z konečných rozvojů a z rozvoje $0{,}{\overline {1}}$.

Dále je potřeba v $^{\mathbb {N} }2-V$ zvolit dvě nekonečně spočetné množiny $S_{1},S_{2},S_{1}\cap S_{2}=\emptyset$; to lze různými způsoby.

Hledanou bijekcí mezi $^{\mathbb {N} }2$ a $^{\mathbb {N} }2-V$ je pak zobrazení, které

• Prvku množiny $S_{1}$ nebo $S_{2}$ přiřadí prvek $S_{2}$; takové přiřazení existuje, neboť sjednocení dvou spočetně nekonečných množin je opět spočetně nekonečná množina.
• Prvku $V$ přiřadí nějaký prvek $S_{1}$; to lze, neboť obě jsou nekonečně spočetné.
• Ostatní prvky budou zobrazeny na sebe samotné, tj. na $^{\mathbb {N} }2-V-S_{1}-S_{2}$ bude zobrazení definováno jako identita.

Důkaz s použitím věty

Důkaz s využitím Cantorovy-Bersteinovy věty je snazší a nevyžaduje tolik technických konstrukcí:

• Reálných čísel z $(0;1)$ je „alespoň tolik“, jako množin z $\mathbb {P} (\mathbb {N} )$, protože každé takové množině $M$ lze přiřadit reálné číslo, které má v desetinném rozvoji jen (např.) pětky a šestky, přičemž šestky jsou právě na pozicích z $M$.
• Platí ale též, že čísel v $(0;1)$ je „nejvýše tolik“, jako podmnožin $N$, protože každému číslu lze přiřadit jeho desetinný rozvoj, přičemž existují-li dva, použije se ten konečný (tj. končící samými nulami).

Z těchto dvou prostých zobrazení plyne podle Cantorovy-Bersteinovy věty, že existuje bijekce mezi $\mathbb {P} (\mathbb {N} )$ a $(0;1)$ a tedy i $\mathbb {R}$.

Spojité funkce

Buď $^{\mathbb {R} }\mathbb {R}$ množina všech reálných funkcí, tj. zobrazení z $\mathbb {R}$ do $\mathbb {R}$. Buď $\mathbb {Cont} (^{\mathbb {R} }\mathbb {R} )$ množina těch reálných funkcí, které jsou spojité. Cantorovou-Bernsteinovou větou lze dokázat, že $\mathbb {Cont} (^{\mathbb {R} }\mathbb {R} )$ má stejnou mohutnost, jako $\mathbb {R}$.

Dolním odhadem mohutnosti $\mathbb {Cont} (^{\mathbb {R} }\mathbb {R} )$ je samotné $\mathbb {R}$: každému reálnému číslu $c$ lze přiřadit např. konstantní funkci $f(x)=c$. Toto prosté zobrazení z $\mathbb {R}$ do $\mathbb {Cont} (^{\mathbb {R} }\mathbb {R} )$ dokazuje, že spojitých funkcí na $\mathbb {R}$ je nejméně tolik, jako reálných čísel.

Stačí nalézt prosté zobrazení v opačném směru, tj. z $\mathbb {Cont} (^{\mathbb {R} }\mathbb {R} )$ do $\mathbb {R}$, které dokáže, že spojitých funkcí je „nejvýše tolik“, jako reálných čísel. K tomu lze využít fakt, že spojitá funkce je jednoznačně určena svými hodnotami v racionálních bodech. Buď $^{\mathbb {Q} }\mathbb {R}$ množina všech zobrazení z racionálních čísel do reálných. Ne každý prvek $^{\mathbb {Q} }\mathbb {R}$ definuje spojitou funkci, ale každá spojitá funkce je jednoznačně definována některým prvkem $^{\mathbb {Q} }\mathbb {R}$. To je prostým zobrazením z $\mathbb {Cont} (^{\mathbb {R} }\mathbb {R} )$ do $^{\mathbb {Q} }\mathbb {R}$.

V předchozí sekci bylo dokázáno, že existuje bijekce mezi reálnými čísly a $^{\mathbb {N} }2$, tj. zobrazeními z přirozených čísel do dvouprvkové množiny. Každý prvek $^{\mathbb {Q} }\mathbb {R}$ lze tedy reprezentovat jako zobrazení $g$, které racionálnímu číslu přiřadí zobrazení, které je prvkem $^{\mathbb {N} }2$. K němu lze sestrojit zobrazení $h$, které dvojici $(q,n)$ z kartézského součinu $\mathbb {Q} \times \mathbb {N}$ přiřadí číslo, které přirozenému číslu $n$ přiřadí zobrazení $g(q)$. Tedy je-li $d=(q,n)$ uspořádaná dvojice z $\mathbb {Q} \times \mathbb {N}$, je $h(d)=g(q)(n)\in 2$. Podrobněji řečeno, jelikož $g(q)$ je zobrazení z $\mathbb {N}$ do dvouprvkové množiny, jeho hodnota pro $n$ je prvek dvouprvkové množiny značené $2$. Při zavedeném značení tedy platí $g(q)\in ^{\mathbb {N} }2,g\in ^{\mathbb {Q} }(^{\mathbb {N} }2),h\in ^{\mathbb {Q} \times \mathbb {N} }2$.

Existuje bijekce mezi $\mathbb {Q} \times \mathbb {N}$ a $\mathbb {N} \times \mathbb {N}$ a tedy i $\mathbb {N}$. Z ní lze zkonstruovat bijekci mezi $^{\mathbb {Q} \times \mathbb {N} }2$ a $^{\mathbb {N} }2$.

Tím je sestrojena série prostých zobrazení

$\mathbb {R} \rightarrow \mathbb {Cont} (^{\mathbb {R} }\mathbb {R} )\rightarrow ^{\mathbb {Q} }\mathbb {R} \leftrightarrow ^{\mathbb {Q} }(^{N}2)\leftrightarrow ^{\mathbb {Q} \times \mathbb {N} }2\leftrightarrow ^{\mathbb {N} }2\leftrightarrow \mathbb {R}$

Bijekce jsou zde vyznačeny dvojitou šipkou; poslední z nich byla dokázána v předchozí sekci. Složením těchto zobrazení dostáváme

$\mathbb {R} \rightarrow \mathbb {Cont} (^{\mathbb {R} }\mathbb {R} )\rightarrow \mathbb {R}$

To dokazuje, že reálných čísel je „nejvýše tolik“ a zároveň „nejméně tolik“ jako spojitých funkcí. Podle Cantorovy-Bersteinovy věty tedy mezi těmito množinami existuje bijekce; bez této věty by důkaz vyžadoval podstatně složitější technickou konstrukci.

Důkaz

Zobrazení h

Nechť $f:A\rightarrow B$ a $g:B\rightarrow A$ jsou prostá zobrazení. Definujeme zobrazení $h:P(A)\rightarrow P(A)$, kde P(A) je potenční množina A (množina všech podmnožin A), takto pro $U\subseteq A:h(U)=g[B-f[A-U]]$ (viz obrázek). Snadno je vidět, že h je monotónní (pro $U\subseteq V$ je $h(U)\subseteq h(V)$). Dále se dokáže, že každé monotónní zobrazení mezi P(A) a P(A) má pevný bod (množinu U takovou, že $U\,=\,h(U)$). K tomu stačí zvolit $U=\bigcup \{V\subseteq A;V\subseteq h(V)\}$. Nakonec, je-li $W\subseteq A$ pevný bod h, položíme $F(x)={\begin{cases}f(x){\mbox{ pro x}}\in A-W\\g^{-1}(x){\mbox{ pro x}}\in W\end{cases}}$. Snadno se ověří, že $F:A\rightarrow B$ je bijekce.

Jiný důkaz

Zobrazení $f$ i $g$ je množina uspořádaných dvojic; je třeba rozhodnout, které dvojic z $D=f\cup g$ zařadit do hledaného zobrazení $h$.

Buď $R_{0}$ množina dvojic $(a,b)$, které v $h$ být musí, protože v $D$ neexistuje jiná dvojice s týmž $a$ nebo v něm neexistuje jiná dvojice s týmž $b$. Pak množina $S_{0}$ dvojic, které v $h$ být jistě nemohou, je tvořena takovými dvojicemi z $D$, které mají společnou první nebo druhou složku s některou dvojicí z $R_{0}$.

Pak ale musí v $h$ být každá dvojice $(a,b)$ pro kterou v $D$ žádná dvojice s týmž $a$ (nebo týmž $b$) buď neexistuje, nebo je mezi vyloučenými, tj. $(a,b)\in S_{0}$. Buď $R_{1}$ množina takových dvojic.

Obdobně, jako $R_{0},S_{0},R_{1}$ se sestrojí $S_{1}$, pak $R_{2},S_{2}$, pak $R_{3},S_{3}$ atd. Postupně se tak rozšiřuje informace o tom, které dvojice v hledaném $h$ jistě budou v každé bijekci mezi $A$ a $B$ a které jistě nebudou v žádné.

V $h$ tedy musí ležet všechny dvojice z kterékoli $R_{i}$ pro přirozené $i$, tj. $h\supseteq \bigcup _{i\in \mathbb {N} }R_{i}$. Lze ukázat, že vhodná bijekce $h$ vznikne, pokud chybějící hrany doplníme z $f$.

Historie

Prvním, kdo formuloval tvrzení Cantorovy-Bernsteinovy věty, byl roku 1882 Georg Cantor. Ještě téhož roku se však Cantor svěřil Dedekindovi, že toto tvrzení nedovede dokázat. Cantor pravdivost tohoto tvrzení mnohokrát ohlásil, dokázáno však bylo až v letech 1896 resp. 1897 Friedrichem W. Schröderem a Felixem Bernsteinem.

Literatura

• BALCAR, Bohuslav; ŠTĚPÁNEK, Petr. Teorie množin. 2. vyd. Praha: Academia, 2001. 464 s. Dostupné online. ISBN 80-200-0470-X. Kapitola I5, s. 78. 

Externí odkazy

• Obrázky, zvuky či videa k tématu Cantorova-Bernsteinova věta na Wikimedia Commons

Portály: Matematika