Cómo probar el conjunto de potencia (X + Y) = conjunto de potencia (X) x conjunto de potencia (Y)

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.

  1. ¿De cuántas maneras hay para establecer el primer bit? – simple, es {0} o {1} – 2 formas .
  2. ¿De cuántas maneras hay para establecer el primer y segundo bits? – {0, 0}, {0, 1}, {1, 0}, {1, 1} – entonces 4 formas .
  3. ¿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.

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).

El conjunto de potencia de un conjunto [matemática] X [/ matemática] es el conjunto de todos los subconjuntos del conjunto [matemática] X [/ matemática]. Considere [math] A = \ {a \} [/ math] y [math] B = \ {b \} [/ math] donde [math] a \ neq b [/ math]. Entonces

[matemáticas] P (A \ cup B) = P (\ {a, b \}) = \ {\ emptyset, \ {a \}, \ {b \}, \ {a, b \} \} [/ matemáticas]

y

[matemáticas] P (A) \ times P (B) = \ {\ emptyset, \ {a \} \} \ times \ {\ emptyset, \ {b \} \} = \ {(\ emptyset, \ emptyset) , (\ emptyset, \ {b \}), (\ {a \}, \ emptyset), (\ {a \}, \ {b \}) \} ~. [/ math]

Entonces, [matemáticas] P (A \ copa B) \ neq P (A) \ veces P (B) [/ matemáticas] en este caso. Entonces el reclamo no es cierto. ¡Entonces no puedes probarlo!

Creo que la pregunta está motivada por el siguiente hecho: si [math] A \ cap B = \ emptyset [/ math] then [math] | P (A \ cup B) | = | P (A) \ veces P (B) | [/ math].