Sea S un conjunto finito con n elmentos (|S|=n) entonces |P(S)|=2ⁿ
DEMOSTRACIÓN:
Caso n=0
Sea S el conjunto vacío, entonces |S|=0 y P(S)={φ}
Supongamos cierto si |S|=m y m es menor o igual que n, entonces |P(S)|=$2^{m}$
Sea |S' |=n+1
S' = {$a_0,a_1,...,a_{n-1},a_n$}
Por tanto
S' = {$a_0,a_1,...,a_{n-1}$} U {$a_n$}
Sea S = {$a_0,a_1,...,a_{n-1}$}
entonces
S' = S $\bigcup$ {$a^n$}
Tenemos que
P(S' ) = P(S $\bigcup${$a_n$}) = P(S) $\bigcup${P' $\bigcup${$a_n$} / P' $\in$P(S)}
Dado que ambos conjuntos son disjuntos tenemos que:
|P(S' )| = |P(S) $\bigcup$ {P' $\bigcup$ {$a_n$} / P' $\in$P(S)}| = |P(S)| + |{P' $\bigcup$ {$a_n$} / P'$\in$P(S)}| =$2^n$+$2^n$ =$2^{n+1}$