Exercício 2. (Apostol seção 13.4 exercícios 5, 6, 7 e 8) Seja S um conjunto.
a) Dado A=a subset S, mostre que B=emptyset, S,a,a^c é a menor álgebra Booleana que contém A.
b) Dados A1=a1 e A2=a2, qual é a menor álgebra Booleana que contém A1 e A2 ?
c) Dados A1=a1, A2=a2 e A3=a3, qual é a menor álgebra Booleana que contém A1, A2 e A3 ?
d) Dados A1=a1, ldots Ak=ak, mostre que a menor álgebra Booleana que contém todos estes conjuntos tem 2^k+1 elementos se S tem mais do que k elementos, e tem 2^k elementos se S tem exatamente n elementos.

Passo 1

O enunciado pede a construção da menor álgebra Booleana em S que contém certos subconjuntos pontuais.
Uma álgebra Booleana em S é uma coleção Asubseteq P(S) fechada sob complemento (relativo a S) e uniões finitas (e, portanto, interseções finitas).
Para achar a álgebra gerada por conjuntos A1,dots,An, usamos o método dos átomos: formamos todas as interseções
capi=1^n Bi,
onde cada Bi é Ai ou Ai^c. Essas interseções particionam S em peças mínimas (átomos), e a álgebra gerada é o conjunto de todas as uniões desses átomos.

Passo 2

(a) Para A=a, proponho
B=emptyset,;S,;a,;a^c
  1. Verifico que B é álgebra:
    • Complemento de emptyset é S, de S é emptyset, de a é a^c e vice-versa.
    • Uniões: acupa^c=S, uniões com emptyset ou S mantêm-se em B.
  2. Minimalidade: se A é qualquer álgebra contendo a, então por fechamento deve conter emptyset (união vazia), S (complemento de emptyset) e a^c (complemento de a). Logo BsubseteqA.

Passo 3

(b) Para A1=a1 e A2=a2, listo as interseções
Bij=B1cap B2, B1inA1,A1^c,;B2inA2,A2^c
Elas são:
A1cap A2=emptyset, A1cap A2^c=a1, A1^ccap A2=a2, A1^ccap A2^c=Ssetminusa1,a2
Os três últimos são os átomos não vazios. A menor álgebra é o conjunto de todas as uniões desses três átomos, ou seja 2^3=8 conjuntos.

Passo 4

(c) Para A1,A2,A3, fazemos as 2^3=8 interseções
capi=1^3 Bi, BiinAi,Ai^c. Dessas, só são não-vazias as que contêm exatamente um Ai (dando ai) e a que contém todos os Ai^c (dando Ssetminusa1,a2,a3). Portanto há 4 átomos, e a álgebra gerada tem 2^4=16 uniões.

Passo 5

(d) Em geral, para Ai=ai, i=1,dots,k, formam-se 2^k interseções
capi=1^k Bi com BiinAi,Ai^c.
  • Se Ssetminusa1,dots,akneqemptyset, as únicas interseções não-vazias são cada ai (quando escolhemos Ai e os outros Aj^c) e Ssetminusa1,dots,ak (quando todos são Ai^c). São k+1 átomos, gerando 2^k+1 uniões.
  • Se S=a1,dots,ak, então Ssetminusa1,dots,ak=emptyset e restam só k átomos, gerando 2^k uniões.

Resposta

a) emptyset,S,a,a^c.
b) Álgebra das uniões dos átomos a1,a2,Ssetminusa1,a2, total de 8 conjuntos.
c) Álgebra das uniões dos átomos a1,a2,a3,Ssetminusa1,a2,a3, total de 16 conjuntos.
d) Com k singletons, se lvert Srvert>k então a menor álgebra tem 2^k+1 elementos; se S=a1,dots,ak tem 2^k elementos.

Exercícios relacionados