Seção 3: Espaços Amostrais Finitos. Métodos de Enumeração. Questão 14.

Use o princípio da multiplicação para provar que o conjunto X=x1, x2, ldots, xn com n elementos possui 2^n subconjuntos (que é a cardinalidade do conjunto P(X) ).

Passo 1

O enunciado nos pede para provar, usando o princípio da multiplicação, que um conjunto X=x1,x2,dots,xn com n elementos tem exatamente 2^n subconjuntos, isto é, lvert P(X)rvert=2^n. Vamos modelar a escolha de um subconjunto como uma sequência de n etapas independentes (incluir ou não cada elemento).

Passo 2

Para cada elemento xiin X fazemos uma “escolha” binária:
– Se de<ai=1, então incluímos xi no subconjunto;
– Se de<ai=0, então não incluímos xi.
Assim cada subconjunto corresponde a uma sequência (de<a1,de<a2,dots,de<an) com de<aiin0,1.

Passo 3

Em cada uma das n etapas há exatamente 2 possibilidades ( 0 ou 1) e as decisões são independentes. Pelo princípio da multiplicação, o número total de sequências possíveis é
2 times 2 times cdots times 2 = 2^n

Passo 4

Existe uma bijeção entre o conjunto de todas as sequências 0,1^n e P(X), pois cada sequência indica exatamente quais elementos de X estão presentes. Portanto
lvert P(X)rvert = 2^n

Resposta

lvert P(X)rvert = 2^n

Exercícios relacionados