Exercício 18. Seja A um conjunto finito com n elementos. Mostre que:
(a) O conjunto das partes de A tem 2^n elementos.
(b) O número de relações em A é 2^n^2-1.

Passo 1

O enunciado pede para mostrar duas coisas sobre um conjunto finito A com n elementos:
a) que o conjunto das partes de A, denotado por P(A), tem 2^n elementos;
b) que o número de relações em A (não-vazias) é 2^n^2-1.
O conteúdo envolvido é combinatória de conjuntos e a ideia de cardinalidade de produto cartesiano.

Passo 2

Para (a), note que cada subconjunto Bsubseteq A pode ser descrito pela decisão, para cada elemento xin A, de incluí-lo ou não em B. Como há n elementos e cada um gera duas escolhas (incluir/excluir), o número total de subconjuntos é
| P(A)| = 2 times 2 times cdots times 2 = 2^n

Passo 3

Para (b), lembramos que uma relação em A é exatamente um subconjunto de Atimes A. Primeiro,
|Atimes A| = ncdot n = n^2
Logo, o número de todos os subconjuntos de Atimes A é 2^n^2. Se quisermos contar apenas as relações não-vazias, subtraímos a possibilidade do subconjunto vazio e obtemos
2^n^2 - 1

Resposta

(a) 2^n
(b) 2^n^2-1

Exercícios relacionados