Cantorin–Schröderin–Bernsteinin lause

Joukko-opissa käytettävä Cantorin–Schröderin–Bernsteinin lause on nimetty Georg Cantorin, Felix Bernsteinin ja Ernst Schröderin mukaan. Lauseessa esitetään, että jos joukkojen $A$ ja $B$ välillä on olemassa injektiiviset funktiot $f:A\to B$ ja $g:B\to A$ , on olemassa bijektio $h:A\to B$ . Tarkoitettaessa joukkojen mahtavuutta tämä tarkoittaa, että jos $|A|\leq |B|$ ja $|A|\geq |B|$ , on oltava $|A|=|B|$ . Tulos on usein hyödyllinen, jos joukkoja on tarpeen järjestää niiden mahtavuuden mukaan.

Todistus

Olkoot $f:A\to B$ ja $g:B\to A$ injektioita sekä $B^{*}=\left\{f(x)\mid x\in A\right\}$ ja $A^{*}=\left\{g(y)\mid y\in B\right\}$ . Nyt $f:A\to B^{*}$ ja $g:B\to A^{*}$ ovat bijektioita, joten on olemassa käänteisfunktiot $f^{-1}:B^{*}\to A$ ja $g^{-1}:A^{*}\to B$ , jotka ovat bijektioita.

Määritellään $x$ :n jälkeläisten lukumäärä, kun $x\in A$ :

ei jälkeläisiä, kun $x\notin A^{*}$
1 jälkeläinen, kun $g^{-1}(x)\notin B^{*}$
2 jälkeläistä, kun $f^{-1}(g^{-1}(x))\notin A^{*}$
3 jälkeläistä, kun $g^{-1}(f^{-1}(g^{-1}(x)))\notin B^{*}$
jne.

Vastaavalla tavalla määritellään muuttujan $y$ jälkeläisten lukumäärä, kun $y\in B$ .

Olkoot

{\begin{aligned}A_{e}&=\left\{x{\text{:llä 0 tai parillinen lkm jälkeläisiä}}\right\},\\A_{o}&=\left\{x{\text{:llä pariton lkm jälkeläisiä}}\right\}\ {\text{ja}}\\A_{i}&=\left\{x{\text{:llä rajattomasti jälkeläisiä}}\right\}.\end{aligned}}

Koska $f^{-1}:B^{*}\to A$ ja $g^{-1}:A^{*}\to B$ ovat bijektioita, niin $f^{-1}(g^{-1}(x))$ , $g^{-1}(f^{-1}(g^{-1}(x)))$ , $f^{-1}(g^{-1}(f^{-1}(g^{-1}(x))))$ jne. ovat bijektioita, joten yksikäsitteisesti joko $x\in A_{e}$ , $x\in A_{o}$ tai $x\in A_{i}$ . Tällöin $A_{e}\cap A_{o}=A_{o}\cap A_{i}=A_{e}\cap A_{i}=\emptyset$ ja $A_{e}\cup A_{o}\cup A_{i}=A$ .

Olkoon

$h(x)={\begin{cases}f(x),\quad &{\text{kun}}\ x\in A_{e}\cup A_{i}\\g^{-1}(x),\quad &{\text{kun}}\ x\in A_{o}.\end{cases}}$

Osoitetaan vielä, että $h:A\to B$ on bijektio.

Olkoon $y\in B$ . Joko $g(y)\in A_{e}\cup A_{i}$ tai $g(y)\in A_{o}$ . Jos $g(y)\in A_{e}\cup A_{i}$ , niin $g(y)$ :llä on vähintään kaksi jälkeläistä, joten $\exists x\in A_{e}\cup A_{i}$ siten, että $f(x)=y$ . Jos $g(y)\in A_{o}$ , niin $g^{-1}(g(y))=y$ . Näin ollen $h(x):A\to B$ on surjektio.

Olkoot $x_{1},x_{2}\in A$ ja $x_{1}\neq x_{2}$ . Väite: $h(x)$ on injektio $\implies h(x_{1})\neq h(x_{2})$ . Tehdään vastaoletus: $h(x_{1})=h(x_{2})$ . Koska $f$ on injektio ja $g^{-1}:A^{*}\to B$ on bijektio, niin $x_{1}\in A_{e}\cup A_{i}$ ja $x_{2}\in A_{o}$ , joten $f(x_{1})=g^{-1}(x_{2})$ . Koska $f^{-1}:B^{*}\to A$ ja $g^{-1}:A^{*}\to B$ ovat bijektioita, niin, kuten edellä, $f(x_{1})$ :llä on pariton tai rajaton määrä ja $g^{-1}(x_{2})$ :llä 0 tai parillinen määrä jälkeläisiä. Ollaan saatu ristiriita sen kanssa, että $f(x_{1})=g^{-1}(x_{2})$ . Täytyy siis päteä $x_{1}\neq x_{2}\implies h(x_{1})\neq h(x_{2})$ . Näin ollen $h(x):A\to B$ on injektio.

Siispä $h(x):A\to B$ on bijektio. $\square$

Esimerkki

Reaalilukujen joukon avoin väli $(0,1)$ ja suljettu väli $[0,2]$ ovat yhtä mahtavia joukkoja, koska on olemassa injektiot $f:(0,1)\to [0,2]$ ja $g:[0,2]\to (0,1)$ , kun $f(x)=x+{\frac {1}{2}}$ ja $g(x)={\frac {x}{4}}+{\frac {1}{4}}$ . Eli $|(0,1)|=|[0,2]|$ .