Teorema de Cantor

O teorema de Cantor é un resultado formalizable na teoría de conxuntos de Zermelo-Fraenkel, que afirma o seguinte:

O conxunto de partes de calquera conxunto A ten unha cardinalidade estritamente maior cá cardinalidade do propio A.

Discusión

O teorema de Cantor é obvio para conxuntos finitos: se un conxunto finito ten n elementos entón o conxunto de partes dese conxunto ten 2ⁿ elementos. O feito de que sexa válido para todo conxunto infinito non é de todo intuitivo, pero permite establecer varios resultados interesantes:

Existe unha infinidade de cardinais transfinitos, o que significa que en realidade existen moitos tipos de infinito (de feito unha infinidade), cada un maior que o anterior. Este resultado a priori é moi pouco intuitivo, pero tremendamente importante na fundamentación das matemáticas.
Non existe ningún xeito de enumerar todos os subconxuntos de $\mathbb {N}$ .

Para ilustrar a validez deste teorema para conxuntos infinitos reprodúcese a continuación unha demostración.

Demostración

Considérese unha función calquera $f:A\to {\mathcal {P}}(A)$ ; demostrar o teorema de Cantor require probar que $f$ non é sobrexectiva e para probar que $f$ non é sobrexectiva abonda con atopar un subconxunto de $A$ que non sexa a imaxe de ningún elemento de $A$ a través de $f$ .

Cantor considerou un subconxunto particular $B$ definido como:

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

e probou que ese subconxunto non pode ser a imaxe de ningún elemento de $A$ .

O argumento que construíu Cantor é por redución ao absurdo presupondo que existe $a\in A:B=f(a)$ , posto que $B$ é un subconxunto de $A$ . Entón pódense distinguir dous casos:

Se $a\in B$ , entón pola definición de $B$ tense que $a\notin B$ , o que é contraditorio.
Se $a\notin B$ , entón pola definición de $B$ tense que $a\in B$ , o que é contraditorio.

En ambos os casos chégase a unha contradición, e polo tanto non existe esa $a$ e entón $f$ (que é unha función calquera) non é sobrexectiva, como se quería demostrar.

Véxase tamén

Bibliografía

Halmos, Paul, Naive set theory. Princeton, NJ: D. Van Nostrand Company, 1960. Reimpreso por Springer-Verlag, Nova York, 1974. ISBN 0-387-90092-6 (Springer-Verlag edition).
Jech, Thomas, 2003. Set Theory: The Third Millennium Edition, Revised and Expanded. Springer. ISBN 3-540-44085-2.