(ITA-SP) Seja U um conjunto não vazio com n elementos, n >= 1. Seja S um subconjunto de mathscrP(U) com a seguinte propriedade:
Se A, B in S, então A subset B ou B subset A.
Então, o número máximo de elementos que S pode ter é:
a) 2^n-1
b) n2, se n for par, e (n+1)2 se n for ímpar
c) n+1
d) 2^n-1+1

Passo 1

O enunciado diz que U é um conjunto com lvert Urvert = n e que Ssubsetmathscr P(U) é tal que, para quaisquer A,Bin S, ou Asubset B ou Bsubset A. Isso significa que S é uma cadeia (totalmente ordenada por inclusão) no reticulado l(mathscr P(U),subsetr). Vamos usar o fato de que esse reticulado é graduado dos níveis 0 a n, de modo que uma cadeia estrita só pode aumentar a cardinalidade em pelo menos 1 a cada passo.

Passo 2

Em toda cadeia estrita
A0subset A1subset cdotssubset Ak
os conjuntos são todos distintos, logo as cardinalidades satisfazem
|A0|<|A1|<cdots<|Ak|
Como cada |Ai| é inteiro entre 0 e n, o maior comprimento possível dessa cadeia estrita é quando ela passa por todos os valores de 0 até n, o que dá
k+1<= n+1
Portanto qualquer cadeia em mathscr P(U) tem no máximo n+1 elementos.

Passo 3

Para ver que n+1 é atingido, escolha uma enumeração dos elementos de U, digamos U=u1,dots,un, e defina a cadeia
emptyset, u1, u1,u2, dots, u1,u2,dots,un
Ela tem exatamente n+1 conjuntos e satisfaz a condição de inclusão.

Resposta

A cardinalidade máxima de S é n+1.

Exercícios de Livros Relacionados