(07) Mostrar que para todo conjunto finito A, vale o seguinte:
n(P(A))=2^n(A)
Solução: Seja A um conjunto com N elementos (ou seja n(A)=N ).
Primeiro método: Consideremos B um subconjunto arbitrário (qualquer) de A.
Perceba o seguinte:
Dizer quantos elementos tem o conjunto P(A) é a mesma coisa que dizer quantos subconjutos B posso formar com os N elementos de A.
Assim, para todo elemento x de A temos as seguintes duas opções:
  • x in B ou
  • x notin B
Isto é, para cada elemento de A tenho duas possibilidades. Como tenho N elementos em total, pelo principio multiplicativo da contagem (eventos separados ou isolados) tenho que a quantidade de subconjuntos que posso formar com N elementos é:
underbrace2 cdot 2 cdot 2 cdots 2 cdot 2N termos =2^N
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.
  • vdots
  • Com k-1 elementos: a1, a2, a3, cdots, ak-2, ak-1,a1, a3, a4, cdots, ak-1, ak, cdots, a2, a3, a4, cdots, ak-1, ak.
  • Com k elementos: a1, a2, a3, cdots, ak-1, ak.
Agora, consideremos o conjunto A cupx por extensão:
A cupx=a1, a2, a3, cdots, ak, x
Temos que, os subconjuntos de A cupx são:
  • Com 0 elementos: emptyset.
  • Com 1 elemento: a1,a2,a3, cdots,ak-1,ak,x.
  • Com 2 elementos: a1, a2,a1, a3,a2, a3, cdots,ak-1, ak,a1, x,a2, x,a3, x, cdots,ak-1, x,ak, x.
  • vdots
  • Com k-1 elementos: a1, a2, a3, cdots, ak-3, ak-2, ak-1,a1, a3, a4, cdots, ak-2, ak-1, ak, cdots,a2, a3, a4, cdots, ak-1, ak,a1, a2, a3, cdots, ak-2, x,a1, a3, a4, cdots, ak-3, ak-2, x, cdots,a2, a3, a4, cdots, ak-3, ak-2, x.
  • Com k elementos: a1, a2, a3, cdots, ak-2, ak-1, ak,a1, a2, a3, cdots, ak-2, ak-1, x, a1, a3, a4, cdots, ak-1, ak, x, cdots,a2, a3, a4, cdots, ak-1, ak, x.
  • 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
nl(P(A')r) ;=;2^k + 2^k ;=;2cdot2^k ;=;2^k+1 ;=;2^,n(A')

Resposta

n(P(A)) = 2^,n(A)

Exercícios relacionados