¿Cuántos elementos hay en el conjunto de potencia?

los set de poder de un conjunto UN es la colección de todos los subconjuntos de A. Cuando se trabaja con un finito conjunto con norte elementos, una pregunta que podríamos hacernos es: "¿Cuántos elementos hay en el conjunto de poder de UN? Veremos que la respuesta a esta pregunta es 2^norte y demostrar matemáticamente por qué esto es cierto.

Buscaremos un patrón observando el número de elementos en el conjunto de potencia de UN, dónde UN tiene norte elementos:

• Si UN = {} (el conjunto vacío), entonces UN no tiene elementos pero P (A) = {{}}, un conjunto con un elemento.
• Si UN = {a}, entonces UN tiene un elemento y P (A) = {{}, {a}}, un conjunto con dos elementos.
• Si UN = {a, b}, entonces UN tiene dos elementos y P (A) = {{}, {a}, {b}, {a, b}}, un conjunto con dos elementos.

En todas estas situaciones, es sencillo ver conjuntos con un pequeño número de elementos que si hay un número finito de norte elementos en UN, entonces el poder establecido PAG (UN) tiene 2norte elementos. Pero, ¿continúa este patrón? Solo porque un patrón es verdadero para

Pero este patrón continúa. Para demostrar que este es realmente el caso, utilizaremos la prueba por inducción.

La prueba por inducción es útil para probar afirmaciones sobre todos los números naturales. Logramos esto en dos pasos. Para el primer paso, anclamos nuestra prueba mostrando una declaración verdadera para el primer valor de norte que deseamos considerar El segundo paso de nuestra prueba es suponer que la declaración es válida para norte = k, y la demostración de que esto implica que la declaración es válida para norte = k + 1.

Para ayudar en nuestra prueba, necesitaremos otra observación. De los ejemplos anteriores, podemos ver que P ({a}) es un subconjunto de P ({a, b}). Los subconjuntos de {a} forman exactamente la mitad de los subconjuntos de {a, b}. Podemos obtener todos los subconjuntos de {a, b} agregando el elemento b a cada uno de los subconjuntos de {a}. Esta adición de conjunto se logra mediante la operación de conjunto de unión:

• Conjunto vacío U {b} = {b}
• {a} U {b} = {a, b}

Estos son los dos elementos nuevos en P ({a, b}) que no eran elementos de P ({a}).

Vemos una ocurrencia similar para P ({a, b, c}). Comenzamos con los cuatro conjuntos de P ({a, b}), y a cada uno de estos agregamos el elemento c:

• Conjunto vacío U {c} = {c}
• {a} U {c} = {a, c}
• {b} U {c} = {b, c}
• {a, b} U {c} = {a, b, c}

Y así terminamos con un total de ocho elementos en P ({a, b, c}).

Ahora estamos listos para probar la declaración, "Si el conjunto UN contiene norte elementos, luego el conjunto de potencia P (A) tiene 2^norte elementos."

Comenzamos señalando que la prueba por inducción ya ha sido anclada para los casos. norte = 0, 1, 2 y 3. Suponemos por inducción que la declaración es válida para k. Ahora deja el set UN Contiene norte + 1 elementos. Podemos escribir UN = si U {x}, y considere cómo formar subconjuntos de UN.

Tomamos todos los elementos de P (B), y por la hipótesis inductiva, hay 2^norte de estos. Luego agregamos el elemento x a cada uno de estos subconjuntos de si, resultando en otros 2^norte subconjuntos de si. Esto agota la lista de subconjuntos de siy el total es 2^norte + 2^norte = 2(2^norte) = 2^{norte + 1} elementos del conjunto de poder de UN.