Cantorteoremet

Cantorteoremet er eit teorem i matematikken som seier at ein kvar mengd $A$ har strengt mindre kardinalitet enn potensmengden $2^A$ til $A$.

Prov

Anta at det finst ein bijeksjon $f:A\to 2^A$. For kvar $a\in A$ er det to moglegheitar. Me har anten $a\in f(a)$ eller $a\in ̸f(a)$. La $X=\{a\in A\mid a\in ̸f(a)\}$. $X$ er ein delmengd av $A$ og dermed $X\in 2^A$. Men sidan $f$ er ein bijeksjon, så finst det ein $x\in A$ slik at $f(x)=X$. Viss $x\in f(x)$, får me frå definisjonen av $X$ at $x\in ̸f(x)$ og dette er ein sjølvmotseiing. Viss derimot $x\in ̸f(x)$ får me igjen frå definisjonen av $X$ at $x\in f(x)$ og dette er ein sjølvmotseiing. Det kan derfor ikkje eksistera ein bijeksjon $f$. Derimot finst det ein injeksjon $g:A\to 2^A$ gitt ved $g(a)=\{a\}$. Dette viser at $A$ har strengt mindre kardinalitet enn $2^A$.