Cantorin–Schröderin–Bernsteinin lause

Tähän artikkeliin tai osioon ei ole merkitty lähteitä, joten tiedot kannattaa tarkistaa muista tietolähteistä. Voit auttaa Wikipediaa lisäämällä artikkeliin tarkistettavissa olevia lähteitä ja merkitsemällä ne ohjeen mukaan.

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 ${\displaystyle A}$ ja ${\displaystyle B}$ välillä on olemassa injektiiviset funktiot ${\displaystyle f:A\to B}$ ja ${\displaystyle g:B\to A}$, on olemassa bijektio ${\displaystyle h:A\to B}$. Tarkoitettaessa joukkojen mahtavuutta tämä tarkoittaa, että jos ${\displaystyle |A|\leq |B|}$ ja ${\displaystyle |A|\geq |B|}$, on oltava ${\displaystyle |A|=|B|}$. Tulos on usein hyödyllinen, jos joukkoja on tarpeen järjestää niiden mahtavuuden mukaan.

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

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

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

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

Olkoot

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

Olkoon

${\displaystyle 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ä ${\displaystyle h:A\to B}$ on bijektio.

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

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

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

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

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