(ITA-SP) Seja U um conjunto não vazio com
elementos,
. Seja
um subconjunto de
com a seguinte propriedade:
Se A, B
, então A
ou B
.
Então, o número máximo de elementos que
pode ter é:
a)
b)
, se
for par, e
se
for ímpar
c)
d)
Se A, B
Então, o número máximo de elementos que
a)
b)
c)
d)
Passo 1
O enunciado diz que
é um conjunto com
e que
é tal que, para quaisquer
, ou
ou
. Isso significa que
é uma cadeia (totalmente ordenada por inclusão) no reticulado
. Vamos usar o fato de que esse reticulado é graduado dos níveis
a
, de modo que uma cadeia estrita só pode aumentar a cardinalidade em pelo menos 1 a cada passo.
Passo 2
Em toda cadeia estrita
os conjuntos são todos distintos, logo as cardinalidades satisfazem
Como cada
é inteiro entre
e
, o maior comprimento possível dessa cadeia estrita é quando ela passa por todos os valores de
até
, o que dá
Portanto qualquer cadeia em
tem no máximo
elementos.
Passo 3
Para ver que
é atingido, escolha uma enumeração dos elementos de
, digamos
, e defina a cadeia
Ela tem exatamente
conjuntos e satisfaz a condição de inclusão.
Resposta
A cardinalidade máxima de
é
.