(07) Mostrar que para todo conjunto finito
A , vale o seguinte:
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:
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
Isto é, a propriedade cumpre-se para o caso base.
ii. Hipótese indutiva: Suponhamos que para
N=k a propriedade é verdade, isto é:
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: