Cantorin lause

Cantorin lause on joukko-opin lause, joka sanoo että joukon mahtavuus ei ole sama kuin potenssijoukkonsa. Tällä tiedolla voidaan helposti osoittaa lisätulos, jonka mukaan potenssijoukko on aina alkuperäistä joukkoa mahtavampi. On nopeasti havaittavissa, että lause pätee äärellisille joukoille, mutta lause on todistettu oikeaksi myös äärettömien joukkojen kohdalla.

Todistus
Kaksi joukkoa ovat yhtä mahtavat jos ja vain jos niiden välille voidaan muodostaa bijektio, ts mikäli näiden kahden eri joukon alkiot saadaan jollakin tavalla järjestettyä pareiksi kattaen molemmista joukoista kaikki alkiot. Cantorin lauseen todistamiseksi riittää siis osoittaa, että millekään joukolle A ei ole olemassa surjektiivista funktiota A:sta sen potenssijoukkoon, eli täytyy löytää ainakin yksi A:n osajoukko B, jolla ei ole alkukuvaa A:ssa. Se löytyy seuraavasti:

Tämähän tarkoittaa määritelmänsä nojalla, että jokaiselle :n alkiolle  pätee  jos ja vain jos . Millekään :lle ei päde , eli toisin sanoen  ei kuulu :n arvojoukkoon. Näin ollen potenssijoukon mahtavuus on suurempi.

Tulos voidaan tarkastaa vastaoletuksella:  on bijektio, joten se on surjektio. Tällöin on olemassa  siten, että . Nyt , missä ensimmäinen ekvivalenssi saadaan :n määritelmästä ja toinen ekvivalenssi oletuksesta . Ollaan päädytty ristiriitaan, joten ei ole olemassa  siten, että . Näin ollen ei ole olemassa surjektiota , joten joukot  ja  eivät ole yhtä mahtavia.

Historiaa
Georg Cantor todisti lauseen vuonna 1891 julkaisussa Über eine elementare Frage der Mannigfaltigkeitslehre. Samassa julkaisussa hän todisti reaalilukujen numeroitumattomuuden.

Kirjallisuutta
 

Joukko-oppi
Seulonnan keskeiset artikkelit