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
com
elementos possui
subconjuntos (que é a cardinalidade do conjunto
).
Passo 1
O enunciado nos pede para provar, usando o princípio da multiplicação, que um conjunto
com
elementos tem exatamente
subconjuntos, isto é,
. Vamos modelar a escolha de um subconjunto como uma sequência de
etapas independentes (incluir ou não cada elemento).
Passo 2
Para cada elemento
fazemos uma “escolha” binária:
– Se , então incluímos
no subconjunto;
– Se , então não incluímos
.
Assim cada subconjunto corresponde a uma sequência com
.
– Se
– Se
Assim cada subconjunto corresponde a uma sequência
Passo 3
Em cada uma das
etapas há exatamente 2 possibilidades (
ou
) e as decisões são independentes. Pelo princípio da multiplicação, o número total de sequências possíveis é
Passo 4
Existe uma bijeção entre o conjunto de todas as sequências
e
, pois cada sequência indica exatamente quais elementos de
estão presentes. Portanto