El conjunto de potencia de cualquier conjunto S, es el número total de formas en que puede elegir cualquier número de elementos (es decir, subconjuntos) de S. Esto es en realidad, 2 ^ | S | Número de subconjuntos. Aquí, | S | = cardinalidad de S (el número de elementos que tiene S).
¿Por qué? Imagina que hay n elementos en S. Entonces | S | = n .
Para cada elemento, cree un solo bit (0/1), de modo que tenga una cadena de n bits. Póngalos todos a 0 inicialmente.
- ¿De cuántas maneras hay para establecer el primer bit? – simple, es {0} o {1} – 2 formas .
- ¿De cuántas maneras hay para establecer el primer y segundo bits? – {0, 0}, {0, 1}, {1, 0}, {1, 1} – entonces 4 formas .
- ¿De cuántas maneras hay para establecer el primer, segundo y tercer bit? {0, 0, 0}, {0, 0, 1}, {0, 1, 0}, {1, 0, 0}, {0, 1, 1}, {1, 0, 1}, {1 , 1, 0}, {1, 1, 1} – entonces 8 formas .
- …
- …
¿Ves un patrón arriba? Aquí estamos obteniendo potencias de 2, por cada bit adicional que consideremos. Por lo tanto, para todos los n bits de S, esperaríamos 2 ^ n posibilidades. Aquí se muestra intuitivamente, pero también puede probarlo por inducción.
- ¿Cuál es la diferencia entre el múltiple lineal y el subespacio lineal vectorial?
- ¿Cuál es la diferencia entre Algebra 1 y Algebra 2?
- ¿Qué se entiende por vector axial?
- Cómo mostrar que un subconjunto contiene el vector cero
- ¿Qué curso de matemáticas es el álgebra abstracta más difícil o el álgebra lineal?
De la definición anterior, entonces, conjunto de potencia (X + Y) = 2 ^ | X + Y |.
El operador de cardinalidad anterior tiene una buena propiedad:
| X + Y | = | X | + | Y |.
Inglés simple: el número de elementos en (X + Y) es el número de elementos en (X) + el número de elementos en (Y).
Entonces, [matemáticas] 2 ^ {| X + Y |} = 2 ^ {(| X | + | Y |)} [/ matemáticas]
[matemática] x ^ {(a + b)} = x ^ {a} * x ^ {b} [/ matemática] – propiedad fundamental de exponenciación (La prueba para x = e está aquí, pero puede probarlo para cualquier real x> 0).
Entonces, [matemáticas] 2 ^ {(| X | + | Y |)} = 2 ^ {| X |} * 2 ^ {| Y |} [/ matemáticas]
= conjunto de potencia (X) * conjunto de potencia (Y).