Sejam
e
subconjuntos de um conjunto
. Prove que:
Estas leis de distributividade e leis de Morgan podem ser generalizadas. Seja
uma família de subconjuntos de
. Prove que:
;
Estas leis de distributividade e leis de Morgan podem ser generalizadas. Seja
Passo 1
O enunciado pede para provar a igualdade entre dois conjuntos:
Informações dadas:
é um subconjunto de
e
é uma família (possivelmente infinita) de subconjuntos de
. Não há outras hipóteses ocultas; a missão é demonstrar que os dois conjuntos acima são iguais.
Passo 2
Vou lembrar a definição elementar de união e interseção, pois vamos usá‑las passo a passo.
-
Definição de união:
se, e só se, ou . -
Definição de interseção finita/generalizada:
se, e só se, para todo vale . Escrevemos isso como .
Essas definições são o “manual” que usamos para comparar conjuntos mostrando inclusão por elemento.
Passo 3
Provar igualdade entre dois conjuntos costuma ser feito mostrando duas inclusões: primeiro
e depois
. Começo mostrando
Seja
um elemento arbitrário tal que
Pelo significado da união, isso quer dizer que ou
ou
. Vou tratar as duas possibilidades.
Passo 4
Caso 1:
. Então, para qualquer
,
implica imediatamente
(porque estar em
basta para pertencer à união
). Como isso vale para todo
, temos
ou seja
. Portanto, na situação
concluímos a inclusão desejada para esse
.
Passo 5
Caso 2:
. Pela definição de interseção, isso significa que
. Para cada
, ter
implica
. Assim novamente
, o que dá
.
Juntando os dois casos (pois a hipótese inicial era a disjunção dos casos), qualquer
que está no lado esquerdo também está no lado direito. Logo provamos
Passo 6
Agora provamos a inclusão oposta:
Seja
tal que
Pela definição de interseção, isso significa que para todo
vale
. Em linguagem lógica:
Passo 7
Para concluir, consideramos duas possibilidades:
-
Se
, então imediatamente e estamos feitos. -
Se
, então a afirmação só pode ser verdadeira se, para cada , for verdade a disjuntiva pela primeira parte, isto é . Portanto, nesse caso obtemos , o que significa . Assim também neste subcaso (porque está na segunda alternativa da união).
Como cobri ambas as possibilidades (
e
), para qualquer
no lado esquerdo concluímos que
também pertence ao lado direito. Logo a inclusão oposta está provada.
Passo 8
Tendo mostrado as duas inclusões
concluímos que os dois conjuntos são iguais.
(Dica rápida: essa prova é um “element chase” padrão — pega um elemento genérico e usa as definições de união/interseção. É a maneira mais direta que funciona bem em provas de prova escritas e em provas de concurso/prova de faculdade.)