Exercício 5 Dado um conjunto , indica-se com o conjunto cujos elementos são os subconjuntos de . Em outras palavras, afirmar que é o mesmo que dizer .
(a) Seja , determine .
(b) Se o conjunto possui elementos, mostre, por indução, que o conjunto possui elementos.
Passo 1
O enunciado define como o conjunto de todos os subconjuntos de . Na parte (a) temos e precisamos listar todos os seus subconjuntos. Na parte (b) queremos provar por indução em que
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êmx são exatamente os elementos de P(Y), ou seja 2^n.
Os subconjuntos de X que contêmx 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.