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:

$B=\left\{\,x\in A:x\not \in f(x)\,\right\}.$

Tämähän tarkoittaa määritelmänsä nojalla, että jokaiselle $A$:n alkiolle $x$ pätee $x\in B$ jos ja vain jos $x\notin f(x)$. Millekään $x$:lle ei päde $f(x)=B$, eli toisin sanoen $B$ ei kuulu $f$:n arvojoukkoon. Näin ollen potenssijoukon mahtavuus on suurempi.

Tulos voidaan tarkastaa vastaoletuksella: $f:A\to {\mathcal {P}}(A)$ on bijektio, joten se on surjektio. Tällöin on olemassa $a\in A$ siten, että $f(a)=B$. Nyt $a\in B\iff a\notin f(a)\iff a\notin B$, missä ensimmäinen ekvivalenssi saadaan $B$:n määritelmästä ja toinen ekvivalenssi oletuksesta $f(a)=B$. Ollaan päädytty ristiriitaan, joten ei ole olemassa $a\in A$ siten, että $f(a)=B$. Näin ollen ei ole olemassa surjektiota $f:A\to {\mathcal {P}}(A)$, joten joukot $A$ ja ${\mathcal {P}}(A)$ 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

• Lipschutz, Seymour: Set Theory and Related Topics. McGraw-Hill, 1964. ISBN 0-07-037986-6