Questão 2 a) Se
e
são conjuntos finitos e disjuntos, com
, mostre que
é finito e
b) Sejam
conjuntos finitos , dois a dois disjuntos, com card
, com
. Mostre que
é finito e
c) Se
e
são conjuntos finitos, mostre que
é finito e
d) Se
e
são finitos, com base no item (c), mostre que
é finito e determine uma fórmula para card
.
e) Sejam
conjuntos finitos (não necessariamente disjuntos) com
elementos, respectivamente. Mostre que
é finito e possui no máximo
elementos .
e) Sejam
Passo 1
O enunciado apresenta cinco itens (a)–(e). Vou listar claramente o que cada item pede e quais são os dados fornecidos:
- (a) Dados:
e são conjuntos finitos e disjuntos; e . Pedem: mostrar que é finito e provar que
- (b) Dados:
são conjuntos finitos, dois a dois disjuntos, e para . Pedem: mostrar que é finito e provar que
- (c) Dados:
e são conjuntos finitos (agora não necessariamente disjuntos). Pedem: mostrar que é finito e provar que
-
(d) Dados:
são finitos. Pedem: usando (c), mostrar que é finito e determinar uma fórmula para . -
(e) Dados:
são conjuntos finitos (não necessariamente disjuntos), com . Pedem: mostrar que é finito e que ele tem no máximo elementos.
Enquanto resolvo, vou usar explicitamente os dados acima quando necessário.
Passo 2
Relembrando conceitos básicos (miniaula curta e necessária):
- Um conjunto
é finito se existe uma bijeção entre e o conjunto para algum inteiro . Nesse caso dizemos . - Bijeção significa uma função que é injetora (elementos diferentes em
vão para valores diferentes) e sobrejetora (todos os valores de são atingidos). - Se dois conjuntos são disjuntos, então não têm elemento em comum:
.
Esses conceitos são suficientes para construir provas formais de contagem usando funções explícitas (construção de bijeções) ou decomposição em partes disjuntas.
Passo 3
Prova do item (a). Objetivo: provar que [X\cup Y) é finito e
, assumindo
e
finitos e disjuntos.
- Como
é finito com , existe uma bijeção
Como
é finito com
, existe uma bijeção
- Como
e são disjuntos, podemos definir uma função do conjunto união para que enumera primeiro os elementos de e depois os de . Escrevo explicitamente:
Essa definição faz sentido e não tem ambiguidade porque (X\cap Y=\varnothing].
- Verificar que
é bijeção:
- Injetividade: se
, existem casos: - Se ambos
, então e como é injetora, . - Se ambos
, então e, subtraindo , e . - Não pode ocorrer um em
e outro em com mesma imagem, porque imagens de elementos de estão em enquanto imagens de elementos de pela definição estão em , conjuntos disjuntos.
Logoé injetora.
- Se ambos
- Sobrejetividade: dado qualquer
, se então existe com e então ; se então e existe com , portanto . Logo alcança todo .
- Conclusão:
é bijeção . Portanto é finito e
Um comentário prático: essa construção é a versão rigorosa de “contar todos os de
(m) e depois contar todos os de
(n)”, que só funciona sem sobreposição porque
e
são disjuntos.]
Passo 4
Prova do item (b) por indução. Objetivo: provar que se
são finitos, dois a dois disjuntos, com
, então
é finito e
-
Caso base
: óbvio, . -
Passo indutivo: suponha a afirmação verdadeira para
conjuntos disjuntos; isto é, suponha que para disjuntos e finitos valha
Considere agora
disjuntos, com
. Pelas hipóteses de disjunção,
e
são disjuntos. Aplicando o resultado do item (a) a esses dois conjuntos (o que é válido porque ambos são finitos e disjuntos), obtemos
Pela hipótese indutiva isso é
- Conclusão por indução: a fórmula vale para todo
. Além disso, como soma de inteiros finitos, é finito.
Essencialmente estamos generalizando a contagem “um por um” usando a disjunção para evitar dupla contagem.
Passo 5
Prova do item (c). Objetivo: provar que para quaisquer conjuntos finitos
e
,
- Observe a decomposição em partes disjuntas (essa é a ideia chave): os conjuntos
são disjuntos dois a dois, e sua união é exatamente
. Em palavras: qualquer elemento de
ou está só em
(isto é, em
), ou está só em
(em
), ou está em ambos (em
).
- Como
e são finitos, os subconjuntos , e também são finitos. Pela parte (b) (aplicada a três conjuntos disjuntos), a cardinalidade da união é soma das cardinalidades:
- Agora escrevemos
e em termos dessas partes:
- Somando as duas últimas igualdades:
- Subtraindo
de ambos os lados e usando a expressão do passo 2, obtemos:
- Conclusão:
é finito (soma e diferença de inteiros finitos) e satisfaz a fórmula desejada:
Intuição: soma-se o que há em cada conjunto e subtrai-se o que foi contado duas vezes (a interseção).
Passo 6
Prova do item (d). Objetivo: mostrar que
é finito e obter fórmula para
.
Método prático: aplicar a fórmula do item (c) duas vezes. Primeiro aplico (c) a
e
, depois uno o resultado com
.
- Aplicando (c) a
e , tenho
- Agora aplico (c) a
e :
Note que
.
- Substituindo a expressão de
do passo 1:
- Aplicando (c) à união
:
- Substituindo na fórmula do passo 3 e simplificando os sinais, obtemos a fórmula clássica da inclusão-exclusão para três conjuntos:
- Como soma e diferenças de inteiros finitos,
é finito.
Comentário: também é possível provar particionando
em 7 partes disjuntas (cada ponto pertence a uma única combinação de pertencimentos) e somar suas cardinalidades; o resultado é o mesmo.
Passo 7
Prova do item (e). Objetivo: para conjuntos
finitos (não necessariamente disjuntos) com
, mostrar que
é finito e
Demonstração usando a união disjunta com índices (construção clara e comum):
- Considere o conjunto “união disjunta indexada”
Neste conjunto cada elemento é um par que contém o índice do conjunto e o elemento concreto, então pares com índices diferentes são sempre distintos mesmo que os elementos
sejam iguais — por isso
é uma versão disjunta dos
.
- Há uma bijeção evidente entre
e a união disjunta formal (ou, alternativamente, é uma união disjunta dos conjuntos ). Pela parte (b), como cada tem elementos, tem-se
- Defina a projeção sobre o segundo componente
Essa projeção é sobrejetora: para todo
existe algum índice
com
, e então
e
.
- Como existe uma função sobrejetora
, a cardinalidade do conjunto imagem satisfaz
Isto é uma consequência geral: se há uma função sobrejetora de um conjunto finito
para
, então
.
- Combinando com passo 2:
E como o lado direito é finito, a união é finita.
Intuição: se você simplesmente “colocar” os elementos de cada
numa lista marcada pelo índice, terá exatamente
pares; projetando-os tirando o índice pode haver colisões (elementos iguais em diferentes
), por isso o número na união pode ser menor, nunca maior.
Resposta
(a)
.
(b) .
(c) .
(d)
(e)
(b)
(c)
(d)
(e)