Exercício 18. Seja
um conjunto finito com
elementos. Mostre que:
(a) O conjunto das partes de
tem
elementos.
(b) O número de relações em
é
.
(a) O conjunto das partes de
(b) O número de relações em
Passo 1
O enunciado pede para mostrar duas coisas sobre um conjunto finito
com
elementos:
a) que o conjunto das partes de , denotado por
, tem
elementos;
b) que o número de relações em (não-vazias) é
.
O conteúdo envolvido é combinatória de conjuntos e a ideia de cardinalidade de produto cartesiano.
a) que o conjunto das partes de
b) que o número de relações em
O conteúdo envolvido é combinatória de conjuntos e a ideia de cardinalidade de produto cartesiano.
Passo 2
Para (a), note que cada subconjunto
pode ser descrito pela decisão, para cada elemento
, de incluí-lo ou não em
. Como há
elementos e cada um gera duas escolhas (incluir/excluir), o número total de subconjuntos é
Passo 3
Para (b), lembramos que uma relação em
é exatamente um subconjunto de
. Primeiro,
Logo, o número de todos os subconjuntos de
é
. Se quisermos contar apenas as relações não-vazias, subtraímos a possibilidade do subconjunto vazio e obtemos
Resposta
(a)
(b)
(b)