Cantorin–Schröderin–Bernsteinin lause

Malline:LähteetönJoukko-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|\le |B|$ ja $|A|\ge |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^{*}=\{f(x)\mid x\in A\}$ ja $A^{*}=\{g(y)\mid y\in B\}$. 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{array}{cc}{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{array}$

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=\mathrm{\varnothing }$ ja $A_e\cup A_o\cup A_i=A$.

Olkoon

$h(x)=\{\begin{array}{cc}f(x),& \text{kun}x\in A_e\cup A_i\\ g^{-1}(x),& \text{kun}x\in A_o.\end{array}$

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 $\mathrm{\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\ne x_2$. Väite: $h(x)$ on injektio $⟹h(x_1)\ne 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\ne x_2⟹h(x_1)\ne h(x_2)$. Näin ollen $h(x):A\to B$ on injektio.

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

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

• Malline:Kirjaviite