Exercício 14: Sejam
, prove que
.
Passo 1
O enunciado pede para provar a versão finita da Lei de De Morgan em teoria de conjuntos, ou seja, mostrar que para quaisquer conjuntos
e todo
vale
Vamos usar prova por indução em
.
Passo 2
Base
. Queremos provar
Pela definição de complemento e união, um elemento
pertence ao lado esquerdo se, e somente se, não pertence à união, isto é,
Mas “
” equivale a “
”. Logo
o que mostra a base.
Passo 3
Hipótese de indução. Suponha que para algum
já esteja provado que
Passo 4
Passo indutivo (
). Considere
Aplicando a Lei de De Morgan para dois conjuntos (caso ) com
e
, obtemos
Aplicando a Lei de De Morgan para dois conjuntos (caso
Pela hipótese de indução substituímos
por
, obtendo
Assim, a propriedade vale para
.
Passo 5
Por indução em
, concluímos que para todo