Teorema de Cantor

El teorema de Cantor es un resultado formalizable en la teoría de conjuntos de Zermelo-Fränkel, que afirma lo siguiente:

El conjunto potencia de cualquier conjunto A tiene una cardinalidad estrictamente mayor que la cardinalidad del propio A.

Discusión

El teorema de Cantor es obvio para conjuntos finitos: si un conjunto finito tiene n elementos entonces el conjunto de partes de ese conjunto tiene 2n elementos. El hecho de que sea válido para todo conjunto infinito no es del todo intuitivo, pero permite establecer varios resultados interesantes:

Para ilustrar la validez de este teorema para conjuntos infinitos se reproduce a continuación una demostración.

Demostración

Consideremos una función cualquiera f: A \to \mathcal{P}(A), entonces demostrar el teorema de Cantor requiere probar que f no es sobreyectiva (exhaustiva). Y para probar que f no es sobreyectiva basta encontrar un subconjunto de A que no sea la imagen de ningún elemento de A a través de f. Cantor consideró un subconjunto particular B definido como:

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


Y probó que ese subconjunto no puede ser la imagen de ningún elemento de A. El argumento que construyó Cantor es por reducción al absurdo presuponiendo que existe a\in A: B = f(a), puesto que B es un subconjunto de A. Ahora podemos distinguir dos casos:

  1. Si a\in B, entonces por la definición de B se tiene que a\notin B, lo cual es contradictorio.
  2. Si a\notin B, entonces por la definición de B se tiene que a\in B, lo cual es contradictorio.

En ambos casos llegamos a una contradicción, por tanto no existe dicha a y entonces f (que es una función cualquiera) no es sobreyectiva, como queríamos demostrar.

Referencia

This article is issued from Wikipedia - version of the Saturday, February 07, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.