Question

Demonstre por P.I.F.

Se A é um conjunto finito com n elementos, então o conjunto das partes de A, tem ${2}^{n}$ elementos:

#Cálculo e explicação

Answer 1

A base é $n=1$. Considere o conjunto $\text{A}=\{a\}$. O conjunto das partes de $\text{A}$ é $\text{P}(\text{A})=\{\{ \ \},\{a\}\}$, que possui $2^{1}=2$ elementos. A base está ok.

Pela hipótese de indução, se $\text{A}$ é um conjunto finito com $n=k$ elementos, então o conjunto das partes de $\text{A}$ tem $2^{k}$ elementos.

Vamos provar o passo indutivo, mostrando que essa proposição vale para $n=k+1$

Pela hipótese de indução, com $k$ elementos podemos formar $2^{k}$ subconjuntos. Seja $a_{k+1}$ o $(k+1)-\acute{\text{e}}\text{simo}$ elemento de $\text{A}$

Note que há $2$ possibilidades para cada um dos $2^{k}$ subconjuntos já formados: conter ou não conter $a_{k+1}$

Portanto, podemos formar $2\cdot2^{k}=2^{k+1}$ subconjuntos, ou seja, o conjunto das partes de $\text{A}$ tem $2^{k+1}$ elementos, como queríamos demonstrar.