Teorema de Cantor

De Cuba-Wiki
Saltar a: navegación, buscar

Si A es un conjunto, no existe biyección entre A y P(A) (conjunto de partes de X). O, equivalentemente, que el conjunto de partes de A tiene cardinalidad estrictamente mayor que A.

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. Fue la primera aparición del método diagonal de Cantor que luego fue usado para probar otros importantes teoremas como por ejemplo el Halting Problem.

Prueba[editar]

Sea A un conjunto y una biyección, debemos llegar a un absurdo suponiendo que es sobreyectiva. Queremos mostrar que hay elementos de la imagen que no tienen preimagen.

Definimos como el conjunto de números "no egoistas", estos son los que, a través de f llegan a un conjunto donde ellos mismos no están incluidos.

Supongamos que , por lo tanto existe un .

  • Si , pero por definición de B: . Absurdo.
  • Si , pero por definición de B: . Absurdo.