Re: [obm-l] 2^n ? pq ?

["Domingos Jr." <dopikas@xxxxxxxxxx>]

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
=========================================================================