El conjunto potencia
¿OK? ¿Lo entendiste? A lo mejor te ayuda un ejemplo...
Todos los subconjuntos
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.
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á 2n elementos
Ejemplo: en el ejemplo {a,b,c} hay tres elementos (a,b y c).
Así que el conjunto potencia tendrá 23 = 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:
Ejemplo: ¿cuántos elementos tiene el conjunto potencia de S={1,2,3,4,5}?
Bien, S tiene 5 elementos, así que:
|P(S)| = 2n = 25 = 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
¡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.
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).