1. (ITA/2006) Seja U um conjunto não vazio com n elementos, \mathrm{n} \geq 1. Seja S um subconjunto de \mathrm{P}(\mathrm{U}) com a seguinte propriedade:
\text { Se } A, B \in S \text {, então } A \subset B \text { ou } B \subset A \text {. }ã
Então, o número máximo de elementos que S pode ter é
a) 2^{n-1}
b) \mathrm{n} / 2, se \mathbf{n} for par, e ( \mathrm{n}+1 )/2 se \mathbf{n} for ímpar
c) n+1
d) 2^{\mathrm{n}}-1
e) 2^{\mathrm{n}-1}+1

Passo 1

O enunciado diz que U é um conjunto com n elementos e que S\subseteq\mathcal{P}(U) satisfaz: para quaisquer A,B\in S, ou A\subset B ou B\subset A. Ou seja, S é uma cadeia (totalmente ordenada por inclusão) no reticulado de subconjuntos de U. Vamos ver qual é o tamanho máximo de uma cadeia em \mathcal{P}(U).

Passo 2

Em qualquer cadeia por inclusão, os conjuntos têm cardinais estritamente crescentes (não pode haver dois com o mesmo número de elementos, pois aí nem um conteria o outro propriamente). Como os cardinais possíveis vão de 0 até n, há no máximo uma escolha para cada valor de cardinalidade. Logo,
|S|\;\le\;n+1.

Passo 3

Para mostrar que n+1 é atingível, basta tomar uma cadeia que passe por todos os cardinais de 0 a n. Por exemplo, fixe uma enumeração de U=\{u_1,\dots,u_n\} e defina
S=\bigl\{\emptyset,\{u_1\},\{u_1,u_2\},\dots,\{u_1,u_2,\dots,u_n\}\bigr\}.
Essa família tem exatamente n+1 conjuntos, todos comparáveis por inclusão.

Resposta

c) n+1

Exercícios relacionados