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  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 
 1 jälkeläinen, kun 
 2 jälkeläistä, kun 
 3 jälkeläistä, kun 
  jne.

Vastaavalla tavalla määritellään :n, kun , jälkeläisten lukumäärä. 

Merkitään ,  ja . Koska  ja  ovat bijektioita, niin , ,  jne. ovat bijektioita, joten yksikäsitteisesti joko ,  tai . Tällöin  ja . 

Määritellään: 

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 

Joukko-oppi