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.
Lähteet
Kirjallisuutta
Luokka:Joukko-oppi Luokka:Seulonnan keskeiset artikkelit