El conjunto potencia

Un conjunto potencia es el conjunto de todos los subconjuntos de un conjunto.

¿OK? ¿Lo entendiste? A lo mejor te ayuda un ejemplo...

Todos los subconjuntos

conjunto potencia {a,b,c}

Para el conjunto conjunto {a,b,c}:

Y el conjunto vacío {} es un subconjunto de {a,b,c}
Y estos son subconjuntos: {a}, {b} y {c}
Y estos también son subconjuntos: {a,b}, {a,c} y {b,c}
Y {a,b,c} es subconjunto de {a,b,c}

De hecho, si haces una lista de todos los subconjuntos de S={a,b,c} tendrás el conjunto potencia de {a,b,c}:

P(S) = { {}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c} }

Piensa en que estas son las diferentes maneras de elegir los elementos (el orden no importa), incluido tomarlos todos o ninguno.

helado

Ejemplo: La tienda tiene helado de banana, chocolate y limón.

¿Qué ordenas?

Nada en absoluto.
O tal vez solo de banana: ...banana. O solo {chocolate} o solo {limón}
O dos juntos: {banana, chocolate} o {banana, limón} o {chocolate, limón}
¡O los tres! {banana, chocolate, limón}

Pregunta: si la tienda también tiene sabor a fresa, ¿qué opciones tienes? Solución más tarde.

Cuántos subconjuntos

¡Fácil! Si el conjunto original tiene n elementos, el conjunto potencia tendrá 2ⁿ elementos

Ejemplo: en el ejemplo {a,b,c} hay tres elementos (a,b y c).

Así que el conjunto potencia tendrá 2³ = 8, ¡y así es, como ya vimos antes!

Notación

El número de elementos de un conjunto se suele escribir |S|, así que ahora escribimos:

|P(S)| = 2ⁿ

Ejemplo: ¿cuántos elementos tiene el conjunto potencia de S={1,2,3,4,5}?

Bien, S tiene 5 elementos, así que:

|P(S)| = 2ⁿ = 2⁵ = 32

Verás en un momento porqué el número de elementos es una potencia de 2.

¡Es binario!

Y esto es lo más sorprendente. Si quieres crear un conjunto potencia, escribe la sucesión de números binarios (usando n dígitos), y luego dejar que "1" signifique "poner el miembro correspondiente en este subconjunto".

Así que "101" se reemplaza por 1 a, 0 b y 1 c para conseguir que {a,c}

Se entiende mejor con un ejemplo:

	abc	Subconjunto
0	000	{ }
1	001	{c}
2	010	{b}
3	011	{b,c}
4	100	{a}
5	101	{a,c}
6	110	{a,b}
7	111	{a,b,c}

Bueno, no están ordenados, pero están todos.

Otro ejemplo

helado

¡Vamos a comer! Tenemos cuatro sabores de helado: banana, chocolate, limón y fresa. ¿De cuántas maneras podemos combinarlos?

Vamos a usar letras para los sabores: {b, c, l, f}. Algunos ejemplos de combinaciones son

{} (ninguno, estás a dieta)
{b, c, l, f} (todos los sabores)
{b, c} (banana y chocolate van bien juntos)
etc.

Vamos a hacer una tabla:

	bclf	Subconjunto
0	0000	{}
1	0001	{s}
2	0010	{l}
3	0011	{l,f}
...	... etc ..	... etc ...
12	1100	{b,c}
13	1101	{b,c,f}
14	1110	{b,c,l}
15	1111	{b,c,l,f}

Y el resultado es (después de ordenar):

P = { {}, {b}, {c}, {l}, {f}, {b,c}, {b,l}, {b,f}, {c,l}, {c,f}, {l,f}, {b,c,l}, {b,c,f},
{b,l,f}, {c,l,f}, {b,c,l,f} }

Simetría

¿Te has fijado en que en la tabla de arriba el primer subconjunto es vacío y el último tiene todos los elementos?

¿Y te has dado cuenta de que el segundo subconjunto es "f", y el penúltimo tiene todos excepto "f"?

De hecho si pones un espejo en medio de la tabla verás que hay una especie de simetría.

Esto es porque los números binarios que hemos usado tienen una simetría bonita y elegante.

Un ejemplo primordial

El conjunto potencia es útil en áreas donde no lo esperamos.

Quiero calcular todos los factores (no solo los factores primos, sino todos los factores) de un número.

Una manera sería probar todas las posibilidades. Así que para encontrar todos los factores de, digamos 330, podríamos probar con 2,3,4,5,6,7,8,9,10... ¡etc!

Se puede mejorar, claro, pero aun así llevaría mucho tiempo con números grandes (en mis experimentos el ordenador trabajaba durante horas).

Pero los factores primos se pueden calcular rápidamente, ¿no puedo combinar los factores primos de alguna manera para construir todos los factores?

Déjame ver, los factores primarios de 510 son 2×3×5×17 (usando la calculadora de factorización en primos).

Entonces, todos los factores de 510 son:

2, 3, 5 y 17,
2×3, 2×5 y 2×17 también, y
2×3×5 y 2×3×17 y ...
... ¡Ajá! ¡Al igual que el helado, necesitaba un Conjunto Potencia!

Y esto es lo que obtuve:

	2,3,5,17	Subconjunto	Factores de 510
0	0000	{ }	1
1	0001	{17}	17
2	0010	{5}	5
3	0011	{5,17}	5 × 17 = 85
4	0100	{3}	3
5	0101	{3,17}	3 × 17 = 51
	... etc ...	... etc ...	... etc ...
15	1111	{2,3,5,17}	2 × 3 × 5 × 17 = 510

¿Y el resultado? Los factores de 990 son 1, 2, 3, 5, 6, 10, 11, 15, 22, 30, 33, 55, 66, 110, 165, 330, y −1, −2, −3, etc. también (puedes usar la Calculadora de todos los factores.

Automático

No he podido resistirme a hacerlo disponible para ti de manera automática.

Así que si necesitas calcular un conjunto potencia, prueba el creador de conjuntos potencia

¡Refuerza tu aprendizaje resolviendo los siguientes retos sobre este tema! (Nota: están en inglés).