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 $y$:n, kun $y\in B$, jälkeläisten lukumäärä.

Merkitään $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\}$ ja $A_{i}=:\left\{x{\text{:llä rajattomasti jälkeläisiä}}\right\}$. 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$.

Määritellään:

$h(x)={\begin{cases}f(x),{\text{kun }}x\in A_{e}\cup A_{i},\\g^{-1}(x),{\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]|$.

Kirjallisuutta

• Thompson, Jan & Martinsson, Thomas: Matematiikan käsikirja, s. 347. Helsinki: Tammi, 1994. ISBN 951-31-0471-0.