CAPÍTULO 5. CARDINALIDAD
140
5.1.1.
Cardinalidad del conjunto potencia
Ahora calcularemos el número de elemento del conjunto potencia. Para hacerlo usaremos
el Principio de inducción. El paso inductivo está basado en la siguiente idea. Consideremos
el conjunto potencia de {1, 2, 3}. Clasificamos los subconjuntos de {1, 2, 3} en dos grupos: el
primero consiste de aquellos que no contienen al 3 y el segundo del resto, es decir, aquellos
que sí contienen al 3
∅
{1}
{2}
{1, 2}
{3}
{1, 3}
{2, 3}
{1, 2, 3}
Notemos que los conjuntos que están en la primera fila son precisamente los subconjuntos
de {1, 2}, es decir, en el primer grupo hemos puestos todos los elementos de P({1, 2}). Y los
que colocamos en el segundo grupo se obtienen agregando el 3 a los conjuntos del primer
grupo.
De lo dicho anteriormente se concluye que el número de elementos de P({1, 2, 3}) es el
doble que el de P({1, 2}). El lector debe tener presente esta idea cuando lea la prueba que
damos a continuación.
Teorema 5.14. Sea n un natural con n ≥ 1, entonces P({1, 2, · · · , n}) tiene 2 n elementos.
Demostración: La demostración la haremos por inducción.
Base de la inducción: Para n = 1, tenemos que P({1}) = {∅, {1}} tiene 2 1 elementos.
Paso inductivo: Supongamos que el resultado es cierto para k y mostrémoslo para k + 1. La
hipótesis inductiva es que P({1, 2, 3 · · · , k}) tiene 2k elementos. Consideremos los siguientes
conjuntos:
A = {X ∈ P({1, 2, 3 · · · , k + 1}) : k + 1 ∈ X}
B = {X ∈ P({1, 2, 3 · · · , k + 1}) : k + 1 ∈ X}.
Observemos que B es igual a P({1, 2, 3 · · · , k}) (verifíquelo!). Tenemos que A ∩ B = ∅ y
además que P({1, 2, 3 · · · , k + 1}) = A ∪ B (verifíquelo!). La hipótesis inductiva nos dice
que B tiene 2k elementos. Mostraremos en seguida que A también tiene 2k elementos. Supongamos esto por un momento y terminemos la verificación del paso inductivo. Como A∪B
es igual a P({1, 2, 3 · · · , k + 1}) y A y B son disjuntos, entonces podemos usar el teorema
5.3 y concluir que P({1, 2, 3 · · · , k + 1}) tiene 2k + 2k elementos. Como 2 · 2k = 2k+1 , hemos
mostrado que P({1, 2, 3 · · · , k + 1}) tiene 2k+1 elementos. Con esto terminamos la verificación del paso inductivo.
Nos quedó pendiente mostrar que A tiene 2k elementos. En realidad es bastante sencillo
darse cuenta de ésto. Analizando con cuidado la definición de A vemos que A tiene tantos
elementos como B, pues a cada conjunto X en B le corresponde exactamente uno de A,
precisamente el conjunto X ∪ {k + 1}. Esta es la idea que presentamos antes de enunciar el
teorema para el caso particular del conjunto potencia de {1, 2, 3}. Precisaremos estas ideas
a continuación.