seja um conjunto A com n elementos. O conjunto P(A) tem 2^n elementos.
Prove pelo principio da inducao finita.
Se A � um conjunto |A| = 1, temos A = {a} e P(A) = {�, {a}}
|P(A)| = 2^1.
suponha que para 1 <= |A| <= n tenhamos |P(A)| = 2^|A|
se |A| = n+1 ent�o podemos expressar A = A' Uni�o {x}, com |A'| = n
|P(A')| = 2^n por hip�tese de indu��o.
Note que nenhum conjunto de P(A') cont�m x. Para montarmos o conjunto das
partes de A, devemos incluir os conjuntos que cont�m x. Um subconjunto de A
que contenha x necessariamente cont�m um subconjunto de A' (que pode ser
vazio).
mais formalmente:
B = {S Uni�o {x} : S pertence a P(A')}
P(A) = P(A') Uni�o B
como os conjuntos P(A') e B s�o disjuntos, temos
|P(A)| = |P(A')| + |B| = 2 |P(A')| = 2^(n+1)
e o resultado segue por indu��o para todo n >= 1.
voc� consegue ver porque |B| = |P(A')| ?
[ ]'s
=========================================================================
Instru��es para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================
