(07) Mostrar que para todo conjunto finito , vale o seguinte:
Solução: Seja um conjunto com elementos (ou seja ).
Primeiro método: Consideremos um subconjunto arbitrário (qualquer) de .
Perceba o seguinte:
Dizer quantos elementos tem o conjunto é a mesma coisa que dizer quantos subconjutos posso formar com os elementos de .
Assim, para todo elemento de temos as seguintes duas opções:
ou
Isto é, para cada elemento de tenho duas possibilidades. Como tenho elementos em total, pelo principio multiplicativo da contagem (eventos separados ou isolados) tenho que a quantidade de subconjuntos que posso formar com elementos é:
Portanto n(P(A))=2^n(A).
(b) Segundo método: Usando o principio de indução matemática (veremos isso nos números naturais).
i. Caso Base ou Inicial: N=0, isto é A=emptyset. Sabemos que P(A)=emptyset, logo
n(P(A))=1=2^0=2^N
Isto é, a propriedade cumpre-se para o caso base.
ii. Hipótese indutiva: Suponhamos que para N=k a propriedade é verdade, isto é:
n(A)=k e n(P(A))=2^k
iii. Caso seguinte da hipótese indutiva: Consideremos agora o conjunto A cupx, isto é um conjunto com mais um elemento do conjunto A.
Vamos ver que tem-se uma relação entre o conjunto de partes de A(P(A)) e o conjunto de partes de A cupx(P(A cupx)).
Consideremos o conjunto A por extensão:
A=a1, a2, a3, cdots, ak-1, ak
Os subconjuntos de A são:
Com 0 elementos: emptyset.
Com 1 elemento: a1,a2,a3, cdots,ak-1,ak.
Com 2 elementos: a1, a2,a1, a3,a2, a3, cdots,ak-1, ak.
Com k+1 elementos: a1, a2, a3, cdots, ak-1, ak, x.
Se olhamos o que esta de azul, podemos identificar os mesmos subconjuntos de A. Pela hipótese indutiva sabemos que temos 2^k subconjuntos azuis.
Se olhamos o que está de vermelho, podemos identificar os mesmos subconjuntos de A só que adicionando o elemento x no final, isto é, temos a mesma quantidade de subconjuntos que na parte azul.
Portanto:
n(P(A cupx))=2^k+2^k=2 cdot 2^k=2^k+1=2^n(A cupx)
Isto é, a propriedade cumpre-se para o caso N=k+1.
Pelo Principio de Indução Matemática, a propriedade vale para qualquer N. Assim fica provado que:
n(P(A))=2^n(A)
Passo 1
O enunciado pede para provar que, para qualquer conjunto finito A, o número de seus subconjuntos (isto é, a cardinalidade de P(A)) satisfaz
n(P(A)) ;=; 2^,n(A)
O conteúdo envolve contagem combinatória (princípio multiplicativo) e prova por indução em n(A).
Passo 2
Método combinatorial: seja A um conjunto com n(A)=N elementos. Para formar um subconjunto Bsubseteq A, cada elemento de A tem duas escolhas: estar em B ou não estar em B. Pelo princípio multiplicativo, o total de escolhas é
underbrace2times 2 times cdots times 2N fatores ;=;2^N
Logo
n(P(A)) = 2^N = 2^,n(A)
Passo 3
Prova por indução em N=n(A).
Caso base (N=0): se A=emptyset então
P(A)=emptyset
tem exatamente um elemento, isto é,
n(P(A))=1=2^0=2^n(A)
Passo 4
Hipótese de indução: suponha que, sempre que um conjunto A tem n(A)=k, valha
n(P(A)) = 2^k
Passo 5
Passo indutivo (kto k+1): seja A com k elementos e escolha um novo elemento xnotin A. Então A' = Acupx tem k+1 elementos. Cada subconjunto de A' ou não contém x (são exatamente os subconjuntos de A, em número 2^k pela hipótese) ou contém x (são todos os subconjuntos de A com x adicionado, também 2^k desses). Logo