Seja P(X) o conjunto cujos elementos são os subconjuntos de X. Prove por indução ao que se X é finito então card P(X) = 2^card(X) .(card é o número...

Para provar que se X é finito, então card P(X) = 2^card(X), podemos usar a indução matemática. Base da indução: Se X é um conjunto finito com um único elemento, então P(X) tem dois elementos, o conjunto vazio e o próprio X. Portanto, card P(X) = 2^1 = 2. Hipótese da indução: Suponha que a afirmação seja verdadeira para um conjunto finito X com n elementos. Passo da indução: Vamos provar que a afirmação também é verdadeira para um conjunto finito X com n+1 elementos. Considere um elemento x em X. Podemos dividir P(X) em dois subconjuntos: aqueles que contêm x e aqueles que não contêm x. O primeiro subconjunto tem a mesma cardinalidade que P(X-{x}), pois cada subconjunto de X que contém x pode ser obtido adicionando x a um subconjunto de X-{x}. O segundo subconjunto tem a mesma cardinalidade que P(X-{x}), pois cada subconjunto de X que não contém x é um subconjunto de X-{x}. Portanto, temos: card P(X) = card {subconjuntos de X que contêm x} + card {subconjuntos de X que não contêm x} = card P(X-{x}) + card P(X-{x}) = 2 * card P(X-{x}) = 2 * 2^(n-1) (pela hipótese da indução) = 2^n = 2^(n+1)/2 = 2^(card X) Portanto, a afirmação é verdadeira para todo conjunto finito X.