| 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
ja
välillä on olemassa injektiiviset funktiot
ja
, on olemassa bijektio
. Tarkoitettaessa joukkojen mahtavuutta tämä tarkoittaa, että jos
ja
, on oltava
. Tulos on usein hyödyllinen, jos joukkoja on tarpeen järjestää niiden mahtavuuden mukaan.
Todistus
Olkoot
ja
injektioita sekä
ja
. Nyt
ja
ovat bijektioita, joten on olemassa käänteisfunktiot
ja
, jotka ovat bijektioita.
Määritellään
:n jälkeläisten lukumäärä, kun
:
- ei jälkeläisiä, kun
![{\displaystyle x\notin A^{*}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/93060c4f4bc6d87741dd7dbb20ec5fa5513c1666)
- 1 jälkeläinen, kun
![{\displaystyle g^{-1}(x)\notin B^{*}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/47f2f8aa5d817207cfb4b76fef16de0da44895c6)
- 2 jälkeläistä, kun
![{\displaystyle f^{-1}(g^{-1}(x))\notin A^{*}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0ff4a1c47fe9b335e2185b0567443c8f2b97968c)
- 3 jälkeläistä, kun
![{\displaystyle g^{-1}(f^{-1}(g^{-1}(x)))\notin B^{*}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/81878312dd566b484e7f27bac5ea4f2f8a4983b1)
- jne.
Vastaavalla tavalla määritellään muuttujan
jälkeläisten lukumäärä, kun
.
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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f231a80a3c7e50a18f16ddad3b5e5996c6e234db)
Koska
ja
ovat bijektioita, niin
,
,
jne. ovat bijektioita, joten yksikäsitteisesti joko
,
tai
. Tällöin
ja
.
Olkoon
Osoitetaan vielä, että
on bijektio.
Olkoon
. Joko
tai
. Jos
, niin
:llä on vähintään kaksi jälkeläistä, joten
siten, että
. Jos
, niin
. Näin ollen
on surjektio.
Olkoot
ja
. Väite:
on injektio
. Tehdään vastaoletus:
. Koska
on injektio ja
on bijektio, niin
ja
, joten
. Koska
ja
ovat bijektioita, niin, kuten edellä,
:llä on pariton tai rajaton määrä ja
:llä 0 tai parillinen määrä jälkeläisiä. Ollaan saatu ristiriita sen kanssa, että
. Täytyy siis päteä
. Näin ollen
on injektio.
Siispä
on bijektio.
Esimerkki
Reaalilukujen joukon avoin väli
ja suljettu väli
ovat yhtä mahtavia joukkoja, koska on olemassa injektiot
ja
, kun
ja
. Eli
.
Kirjallisuutta
- Thompson, Jan & Martinsson, Thomas: Matematiikan käsikirja, s. 347. Helsinki: Tammi, 1994. ISBN 951-31-0471-0.
Tämä matematiikkaan liittyvä artikkeli on tynkä. Voit auttaa Wikipediaa laajentamalla artikkelia.