¿Cómo podría mostrar que para un conjunto finito A de cardinalidad n, la cardinalidad de P (A) es [matemática] 2 ^ n [/ matemática]?

Answer 1

Deje [math] A_n [/ math] ser una secuencia de conjuntos con elementos [math] \ {x_1, x_2, x_3, \ ldots, x_n \} [/ math] para que [math] | A_n | = n [/ math ] Tenga en cuenta que [math] \ mathcal {P} (A_1) = \ {\ emptyset, \ {x_1 \} \} [/ math] para que [math] | \ mathcal {P} (A_1) | = 2 [/ matemáticas].

Entonces, para algunos [math] n \ in \ mathbb N [/ math], tenemos [math] | \ mathcal {P} (A_n) | = 2 ^ n [/ matemáticas]. Ahora considere [math] | \ mathcal {P} (A_ {n + 1}) | [/ math].

Por cada [matemática] S \ en \ matemática {P} (A_ {n + 1}) [/ matemática] tal que [matemática] x_ {n + 1} \ notin S [/ matemática] vemos que [matemática] S \ in \ mathcal {P} (A_ {n}) [/ math]. Además, para todas las [matemáticas] S \ in \ mathcal {P} (A_ {n + 1}) [/ math] tal que [math] x_ {n + 1} \ in S [/ math] luego [math] S \ barra diagonal inversa x_ {n + 1} \ in \ mathcal {P} (A_ {n}) [/ math]. Entonces, la cardinalidad de [matemáticas] | \ matemática {P} (A_ {n + 1}) | \ le 2 \ cdot | \ matemática {P} (A_ {n}) | = 2 ^ {n + 1} [/ matemáticas].

Entonces (en la otra dirección), si [math] S \ in \ mathcal {P} (A_ {n}) [/ math] entonces [math] S \ in \ mathcal {P} (A_ {n + 1}) [/ math] y [math] S \ cup x_ {n + 1} \ in \ mathcal {P} (A_ {n + 1}) [/ math]. Entonces, la cardinalidad de [matemática] | \ matemática {P} (A_ {n + 1}) | \ ge 2 \ cdot | \ matemática {P} (A_ {n}) | = 2 ^ {n + 1} [/ matemáticas].

Las dos desigualdades implican [matemática] | \ matemática {P} (A_ {n + 1}) | = 2 ^ {n + 1} [/ matemática].

Entonces el resultado sigue por inducción.

Answer 2

Sugerencia: un subconjunto de [math] A [/ math] se define al recorrer cada uno de los elementos [math] n [/ math] y decidir si está dentro o fuera del subconjunto.

Answer 3

Lo demuestra por inducción en n:

Para [math] n = 1 [/ math], los subconjuntos de un conjunto de un elemento [math] \ {a \} [/ math] son ​​obviamente [math] \ emptyset [/ math] y [math] \ {a \} [/ math], por lo que el conjunto de potencia tiene cardinalidad [math] 2 = 2 ^ 1 [/ math].

Luego, suponga que su declaración ya fue probada para todos los conjuntos de cardinalidad [matemática] n [/ matemática]. Ahora dejemos que [math] X [/ math] sea cualquier conjunto de cardinalidad [math] n + 1 [/ math]. Arreglar un elemento [math] x_0 \ en X [/ math].

Deje que [math] X_0 \ subset X [/ math] sea el subconjunto [math] X – \ {x_0 \} [/ math]. Entonces [math] X_0 [/ math] tiene elementos [math] n [/ math], y por hipótesis de inducción [math] P (X_0) [/ math] tiene elementos [math] 2 ^ n [/ math]. Ahora debe contar los subconjuntos de [math] X [/ math] que no son subconjuntos de [math] X_0 [/ math]. Pero eso es muy fácil: cada uno de estos conjuntos debe tener [math] x_0 [/ math] como elemento, porque de lo contrario ya estaría subconjunto del [math] X_0 [/ math] más pequeño. Al eliminar [math] x_0 [/ math] se convierte en un subconjunto de [math] X_0 [/ math]. Así que de nuevo hay [subtítulos matemáticos] 2 ^ n [/ math] de [math] X [/ math] que no son subconjuntos de [math] X_0. [/ Math] De ahí la cardinalidad de [math] X [/ math] es [matemática] 2 ^ n + 2 ^ n = 2 * 2 ^ n = 2 ^ {n + 1} [/ matemática]. Que era lo que queríamos probar.