Seja \wp(X) o conjunto das partes de X. Prove, indutivamente, que se X é finito, então \# \wp(X)=2^{\# X}.

Passo 1

O enunciado pede para provar, por indução sobre o número de elementos de um conjunto finito X, que o número de subconjuntos de X (isto é, o cardinal do conjunto das partes \wp(X)) é dado por
\#\wp(X)=2^{\#X}.
O conteúdo principal aqui é indução finita e contagem de subconjuntos.

Passo 2

Caso base ( \#X=0):
Quando X=\emptyset temos \wp(\emptyset)=\{\emptyset\}, logo
\#\wp(\emptyset)=1=2^0.
Portanto a propriedade vale para n=0.

Passo 3

Hipótese de indução:
Suponha que para todo conjunto finito Y com \#Y=n valha
\#\wp(Y)=2^n.

Passo 4

Passo indutivo ( \#X=n+1):
Seja X um conjunto finito com \#X=n+1. Escolha um elemento x\in X e defina
X' = X\setminus\{x\},
que tem \#X'=n pela remoção de exatamente um elemento.

Passo 5

Particionamos \wp(X) em dois subcoleções disjuntas:
A = \{S\subseteq X \mid x\notin S\},
B = \{S\subseteq X \mid x\in S\}.
Há bijeção natural entre \wp(X') e A (cada subconjunto de X' é também subconjunto de X sem x) e outra bijeção entre \wp(X') e B dada por S\mapsto S\cup\{x\}. Pela hipótese de indução,
\#A = \#\wp(X') = 2^n \quad\text{e}\quad \#B = 2^n.

Passo 6

Como \wp(X)=A\cup B e A\cap B=\emptyset, temos
\#\wp(X) = \#A + \#B = 2^n + 2^n = 2\cdot2^n = 2^{n+1}.
Isto completa o passo indutivo e a prova por indução está concluída.

Resposta

\#\wp(X) = 2^{\#X}

Exercícios relacionados