Teorema de Cantor

Si n es finito es obvio, lo demostramos por inducción

Se cumple para n=1 ya que 1 < 2^1 = 2

Supongamos se cumple para n > 1

N <2^n

n+1 < 2n < 2·2^n = 2^(n+1)

Luego se cumple para n+1

Si n no es finito hay demostrar que no puede establecerse una aplicación f suprayectiva entre un conjunto A de cardinal n y el conjunto de las partes de A, P(A).

Para ello consideramos este conjunto

C={x€A | x no pertenece a f(x)}

Por ejemplo si

f(1) = {1,2}

f(2) = {1,3,5}

Tendríamos que 1€B, 2 no€ B

Como C € P(A) y f es suprayectiva tendrá que haber en elemento a€A tal que f(a) = C

Y ahora vamos a llegar a un absurdo preguntándonos si a € C o no.

Si a€C por la definición de C tendremos a no€ f(a)=C

Absurdo, no se puede pertenecer y no pertenecer a C al mismo tiempo.

Y si a no€ C por la definición de C se tiene que cumplir a € f(a)=C

Absurdo igualmente.

Luego a no puede ni pertenecer ni no pertenecer a C lo cual es absurdo y por tanto a no puede existir y entonces C no tiene antiimagen, por lo cual f no es suprayectiva y el cardinal de A es estrictamente menor que el de P(A)

Y eso es todo.