Exercício 5 Dado um conjunto X, indica-se com P(X) o conjunto cujos elementos são os subconjuntos de X. Em outras palavras, afirmar que A in P(X) é o mesmo que dizer A subset X.
(a) Seja X=a, b, c, determine P(X).
(b) Se o conjunto X possui n elementos, mostre, por indução, que o conjunto P(X) possui 2^n elementos.

Passo 1

O enunciado define P(X) como o conjunto de todos os subconjuntos de X. Na parte (a) temos X=a,b,c e precisamos listar todos os seus subconjuntos. Na parte (b) queremos provar por indução em n=lvert Xrvert que
llvert P(X)rrvert = 2^n

Passo 2

Para X=a,b,c, todo subconjunto de X é ou vazio, ou tem um elemento, ou dois, ou os três. Logo
P(X) =lemptyset,a,b,c,a,b,a,c,b,c,a,b,cr

Passo 3

Base da indução ( n=0). Se X=emptyset, então os únicos subconjunto de X são emptyset e portanto
P(X)=emptyset,
logo lvertP(X)rvert=1=2^0. A propriedade vale para n=0.

Passo 4

Passo indutivo. Suponha que todo conjunto com n elementos tenha 2^n subconjuntos. Seja agora X um conjunto com n+1 elementos; escolha um elemento xin X e defina Y = Xsetminusx, que tem n elementos.
  • Os subconjuntos de X que não contêm x são exatamente os elementos de P(Y), ou seja 2^n.
  • Os subconjuntos de X que contêm x são da forma Scupx com Ssubset Y, e também há 2^n deles.
    Portanto
llvertP(X)rrvert =2^n + 2^n =2^n+1

Resposta

(a) P(X)=emptyset,a,b,c,a,b,a,c,b,c,a,b,c
(b) Por indução em n, conclui-se que llvertP(X)rrvert=2^n.

Exercícios relacionados