(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:
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
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: