Diagonalización de Cantor

El método de diagonalización de Cantor es comúnmente usado para demostrar que cierto conjunto no es enumerable. Un claro ejemplo se muestra en la prueba de que el conjunto de partes de los naturales, el cual posee el mismo cardinal que el conjunto de todas las funciones de dominio natural y codominio 2, no es enumerable.

Por lo general, estos razonamientos se realizan por reducción al absurdo, suponiendo que se tiene la función biyectiva con los naturales u otro conjunto de cardinal contable (Por ejemplo, en el caso estudiado, se supondrá que existe "f" función biyectiva de dominio natural y codominio, conjunto de todas las funciones de dominio natural y codominio 2.

El fin de estos argumentos, es construir un elemento del conjunto que se cree no enumerable, donde se observe que dicha elemento es un complemento de la diagonal principal. De ahí el término de obtener contradicciones por diagonalización.

Un Dato curioso a tener en cuenta, es que el Teorema de Cantor resulta ser también un argumento de diagonalización