Cantorin lause

Cantorin lause on joukko-opin lause, jonka mukaan joukolla ei koskaan ole sama mahtavuus kuin potenssijoukollaan. Lauseen avulla voidaan myös osoittaa, että potenssijoukko on aina nimen omaan alkuperäistä joukkoa mahtavampi. Äärellisille joukoille Cantorin lause on helposti havaittavissa, mutta se pätee myös äärettömien joukkojen kohdalla.

Todistus
Kaksi joukkoa ovat yhtä mahtavat, jos ja vain jos niiden välille voidaan muodostaa bijektio, toisin sanoen mikäli näiden kahden eri joukon alkiot saadaan jollakin tavalla järjestettyä pareiksi niin, että kaikki molempien joukkojen alkiot ovat mukana jossain pareista. 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


Luokka:Joukko-oppi
Luokka:Seulonnan keskeiset artikkelit