ITA 2006 - Conjuntos

Seja U um conjunto não vazio com n elementos, n ≥ 1. Seja S um subconjunto de P(U) com a seguinte propriedade: Se A, B ∈ S, então A ⊂ B ou B ⊂ A. Então, o número máximo de elementos que S pode ter é
a) 2ⁿ⁻¹
b) n/2, se n for par, e (n + 1)/2 se n for ímpar
c) n + 1
d) 2ⁿ-1
e) 2ⁿ⁻¹+1

Amigos, já postaram essa questão no fórum anteriormente, mas eu não consegui compreender a resolução. Poderiam me dar uma ajuda?

Olá,

Supondo inicialmente U={1}
temos que as partes de U será:

P(U)={O,{1}}

Repare que S={O,{1}} , pois supondo A=O e B={1} , O está contido em {1}.
Portanto , para esse caso o número máximo de elementos que S pode ter é 2.


Supondo U={1,2}

Temos que as partes de U será:
P(U)={0,{1},{2},{1,2}}

Repare que S={O,{1},{1,2}} , pois é a condição com o máximo números de elementos , pois O está contido em {1} , {1}, por sua vez , está contido em {1,2}.Por ser uma relação de transitividade , 0 está contido em {1,2}.

Para o caso genérico de U={1,2,3,..., n } , teremos para P(U)={O,{1},{2},...,{1,2},{1,3},...{1,2,3},...,{1,2,3,..., n }}.
Fica fácil de perceber que S={0,{1},{1,2},{1,2,3},...,{1,2,3,...,n}} é o caso com o maior número de elementos de S , sendo este n+1.


Ps= 'O' significa conjunto vazio.

Boa noite amigos e amigas do fórum!
Perdão por reviver o tópico, mas não entendi a resolução feita... Quem puder explica-la novamente, obrigado desde já!!

Tome um conjunto Genérico como U= {1,2,3,4}, os subconjuntos podem ser {1}, {1,2}, {2} ... e mais 13 outros pela forma 2ⁿ , porém isso não condiz com a questão, pois no caso ''Se A, B ∈ S, então A ⊂ B ou B ⊂ A.'' Sendo assim o  subconjunto {1} e o {2} não favorecem a esse requisito de estar contido ou conter o outro.


S não poderia ser {Ø,{1},{1,2},{2}...} por exemplo, pois {1} não contém nem está contido em {2}, e para a fórmula de S na questão isso teria que ser respeitado.

Assim S ficaria com {Ø,{1},{1,2},{1,2,3},{1,2,3,4}} para ter o máximo de subconjuntos prevalecendo aquele requisito.


Tomando U com 1 elemento, S ficará com 2 elementos, para U com 2 elementos, S ficará com 3, e assim por diante até U ter n elementos, S terá n+1 elementos,