Teorema de Cantor

Este teorema no se si es "el teorema de Cantor", pero por lo menos es un teorema de Cantor. La prueba del teorema utiliza el método diagonal introducido por Cantor y utilizado después en muchas otras pruebas, entre ellas la del halting problem. El teorema dice:

Si X es un conjunto, no existe biyección entre x y P(x) (conjunto de partes de X).

Prueba

Sea $h:x\rightarrow P(x)$ una biyección. En particular es sobreyectiva.

Sea $A=\{x_{0}\in x:x_{0}\not \in h(x_{0})\}$

Si $x_{0}\in x,h(x_{0})\in P(x)\Rightarrow h(x_{0})\subseteq x$.

$A\in P(x)$. Entonces existe $y_{0}\in x$ tal que $h(y_{0})=A$

Si $y_{0}\in A\Rightarrow y_{0}\in h(y_{0})\Rightarrow y_{0}\not \in A$.

Si $y_{0}\not \in A\Rightarrow y_{0}\in h(y_{0})\Rightarrow y_{0}\in A$.

Absurdo!

Notas

El teorema fue demostrado en clase a nivel divulgativo por el profesor Alejandro Petrovich en el curso de Lógica y Computabilidad del segundo cuatrimestre del 2006.