Questão 2 a) Se X e Y são conjuntos finitos e disjuntos, com \operatorname{card}(X)=m e \operatorname{card}(Y)=n, mostre que X \cup Y é finito e
\operatorname{card}(X \cup Y)=m+n .
b) Sejam X_{1}, X_{2}, \ldots, X_{k} conjuntos finitos , dois a dois disjuntos, com card \left(X_{i}\right)=m_{i}, com 1 \leq i \leq k. Mostre que \bigcup_{i=1}^{k} X_{i} é finito e
\operatorname{card}\left(\bigcup_{i=1}^{k} X_{i}\right)=m_{1}+m_{2}+\cdots+m_{k} .
c) Se X e Y são conjuntos finitos, mostre que X \cup Y é finito e
\operatorname{card}(X \cup Y)=\operatorname{card}(X)+\operatorname{card}(Y)-\operatorname{card}(X \cap Y) .
d) Se X, Y e Z são finitos, com base no item (c), mostre que X \cup Y \cup Z é finito e determine uma fórmula para card (X \cup Y \cup Z).
e) Sejam X_{1}, X_{2}, \ldots, X_{k} conjuntos finitos (não necessariamente disjuntos) com m_{1}, m_{2}, \ldots, m_{k} elementos, respectivamente. Mostre que \bigcup_{i=1}^{k} Y_{i} é finito e possui no máximo m_{1}+m_{2}+\cdots+m_{k} elementos .

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: X e Y são conjuntos finitos e disjuntos; \operatorname{card}(X)=m e \operatorname{card}(Y)=n. Pedem: mostrar que X\cup Y é finito e provar que
\operatorname{card}(X\cup Y)=m+n.
  • (b) Dados: X_{1},X_{2},\ldots,X_{k} são conjuntos finitos, dois a dois disjuntos, e \operatorname{card}(X_i)=m_i para 1\le i\le k. Pedem: mostrar que \bigcup_{i=1}^k X_i é finito e provar que
\operatorname{card}\!\left(\bigcup_{i=1}^{k} X_{i}\right)=m_1+m_2+\cdots+m_k.
  • (c) Dados: X e Y são conjuntos finitos (agora não necessariamente disjuntos). Pedem: mostrar que X\cup Y é finito e provar que
\operatorname{card}(X\cup Y)=\operatorname{card}(X)+\operatorname{card}(Y)-\operatorname{card}(X\cap Y).
  • (d) Dados: X,Y,Z são finitos. Pedem: usando (c), mostrar que X\cup Y\cup Z é finito e determinar uma fórmula para \operatorname{card}(X\cup Y\cup Z).
  • (e) Dados: X_1,\dots,X_k são conjuntos finitos (não necessariamente disjuntos), com \operatorname{card}(X_i)=m_i. Pedem: mostrar que \bigcup_{i=1}^k X_i é finito e que ele tem no máximo m_1+\cdots+m_k 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 A é finito se existe uma bijeção entre A e o conjunto \{1,2,\dots,n\} para algum inteiro n\ge 0. Nesse caso dizemos \operatorname{card}(A)=n.
  • Bijeção significa uma função que é injetora (elementos diferentes em A vão para valores diferentes) e sobrejetora (todos os valores de \{1,\dots,n\} são atingidos).
  • Se dois conjuntos são disjuntos, então não têm elemento em comum: X\cap Y=\varnothing.
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 \operatorname{card}(X\cup Y)=m+n, assumindo X e Y finitos e disjuntos.
  1. Como X é finito com \operatorname{card}(X)=m, existe uma bijeção
f:X\to\{1,2,\dots,m\}.
Como Y é finito com \operatorname{card}(Y)=n, existe uma bijeção
g:Y\to\{1,2,\dots,n\}.
  1. Como X e Y são disjuntos, podemos definir uma função h do conjunto união para \{1,2,\dots,m+n\} que enumera primeiro os elementos de X e depois os de Y. Escrevo h explicitamente:
h(u)=\begin{cases} f(u), & \text{se }u\in X,\\[4pt] m+g(u), & \text{se }u\in Y. \end{cases}
Essa definição faz sentido e não tem ambiguidade porque (X\cap Y=\varnothing].
  1. Verificar que h é bijeção:
  • Injetividade: se h(u_1)=h(u_2), existem casos:
    • Se ambos u_1,u_2\in X, então f(u_1)=f(u_2) e como f é injetora, u_1=u_2.
    • Se ambos u_1,u_2\in Y, então m+g(u_1)=m+g(u_2) e, subtraindo m, g(u_1)=g(u_2) e u_1=u_2.
    • Não pode ocorrer um em X e outro em Y com mesma imagem, porque imagens de elementos de X estão em \{1,\dots,m\} enquanto imagens de elementos de Y pela definição estão em \{m+1,\dots,m+n\}, conjuntos disjuntos.
      Logo h é injetora.
  • Sobrejetividade: dado qualquer t\in\{1,\dots,m+n\}, se 1\le t\le m então existe x\in X com f(x)=t e então h(x)=t; se m+1\le t\le m+n então t-m\in\{1,\dots,n\} e existe y\in Y com g(y)=t-m, portanto h(y)=t. Logo h alcança todo \{1,\dots,m+n\}.
  1. Conclusão: h é bijeção X\cup Y\to\{1,\dots,m+n\}. Portanto X\cup Y é finito e
\operatorname{card}(X\cup Y)=m+n.
Um comentário prático: essa construção é a versão rigorosa de “contar todos os de X (m) e depois contar todos os de Y (n)”, que só funciona sem sobreposição porque X e Y são disjuntos.]

Passo 4

Prova do item (b) por indução. Objetivo: provar que se X_1,\dots,X_k são finitos, dois a dois disjuntos, com \operatorname{card}(X_i)=m_i, então \bigcup_{i=1}^k X_i é finito e
\operatorname{card}\!\left(\bigcup_{i=1}^{k} X_{i}\right)=\sum_{i=1}^k m_i.
  1. Caso base k=1: óbvio, \operatorname{card}(X_1)=m_1.
  2. Passo indutivo: suponha a afirmação verdadeira para k conjuntos disjuntos; isto é, suponha que para X_1,\dots,X_k disjuntos e finitos valha
\operatorname{card}\!\left(\bigcup_{i=1}^{k} X_{i}\right)=m_1+\cdots+m_k.
Considere agora X_1,\dots,X_k,X_{k+1} disjuntos, com \operatorname{card}(X_{k+1})=m_{k+1}. Pelas hipóteses de disjunção, \bigcup_{i=1}^{k} X_i e X_{k+1} 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
\operatorname{card}\!\left(\bigcup_{i=1}^{k+1} X_i\right) = \operatorname{card}\!\left(\bigcup_{i=1}^{k} X_i\right)+\operatorname{card}(X_{k+1}).
Pela hipótese indutiva isso é
m_1+\cdots+m_k+m_{k+1}.
  1. Conclusão por indução: a fórmula vale para todo k\ge 1. Além disso, como soma de inteiros finitos, \bigcup_{i=1}^k X_i é 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 X e Y,
\operatorname{card}(X\cup Y)=\operatorname{card}(X)+\operatorname{card}(Y)-\operatorname{card}(X\cap Y).
  1. Observe a decomposição em partes disjuntas (essa é a ideia chave): os conjuntos
X\setminus Y,\qquad Y\setminus X,\qquad X\cap Y
são disjuntos dois a dois, e sua união é exatamente X\cup Y. Em palavras: qualquer elemento de X\cup Y ou está só em X (isto é, em X\setminus Y), ou está só em Y (em Y\setminus X), ou está em ambos (em X\cap Y).
  1. Como X e Y são finitos, os subconjuntos X\setminus Y, Y\setminus X e X\cap Y também são finitos. Pela parte (b) (aplicada a três conjuntos disjuntos), a cardinalidade da união é soma das cardinalidades:
\operatorname{card}(X\cup Y)=\operatorname{card}(X\setminus Y)+\operatorname{card}(Y\setminus X)+\operatorname{card}(X\cap Y).
  1. Agora escrevemos \operatorname{card}(X) e \operatorname{card}(Y) em termos dessas partes:
\operatorname{card}(X)=\operatorname{card}(X\setminus Y)+\operatorname{card}(X\cap Y),
\operatorname{card}(Y)=\operatorname{card}(Y\setminus X)+\operatorname{card}(X\cap Y).
  1. Somando as duas últimas igualdades:
\operatorname{card}(X)+\operatorname{card}(Y) = \operatorname{card}(X\setminus Y)+\operatorname{card}(Y\setminus X)+2\operatorname{card}(X\cap Y).
  1. Subtraindo \operatorname{card}(X\cap Y) de ambos os lados e usando a expressão do passo 2, obtemos:
\operatorname{card}(X)+\operatorname{card}(Y)-\operatorname{card}(X\cap Y) = \operatorname{card}(X\setminus Y)+\operatorname{card}(Y\setminus X)+\operatorname{card}(X\cap Y) = \operatorname{card}(X\cup Y).
  1. Conclusão: X\cup Y é finito (soma e diferença de inteiros finitos) e satisfaz a fórmula desejada:
\operatorname{card}(X\cup Y)=\operatorname{card}(X)+\operatorname{card}(Y)-\operatorname{card}(X\cap Y).
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 X\cup Y\cup Z é finito e obter fórmula para \operatorname{card}(X\cup Y\cup Z).
Método prático: aplicar a fórmula do item (c) duas vezes. Primeiro aplico (c) a X e Y, depois uno o resultado com Z.
  1. Aplicando (c) a X e Y, tenho
\operatorname{card}(X\cup Y)=\operatorname{card}(X)+\operatorname{card}(Y)-\operatorname{card}(X\cap Y).
  1. Agora aplico (c) a (X\cup Y) e Z:
\operatorname{card}\big((X\cup Y)\cup Z\big) = \operatorname{card}(X\cup Y)+\operatorname{card}(Z)-\operatorname{card}\big((X\cup Y)\cap Z\big).
Note que (X\cup Y)\cap Z=(X\cap Z)\cup(Y\cap Z).
  1. Substituindo a expressão de \operatorname{card}(X\cup Y) do passo 1:
\operatorname{card}(X\cup Y\cup Z) = \operatorname{card}(X)+\operatorname{card}(Y)-\operatorname{card}(X\cap Y) +\operatorname{card}(Z)-\operatorname{card}\big((X\cap Z)\cup(Y\cap Z)\big).
  1. Aplicando (c) à união (X\cap Z)\cup(Y\cap Z):
\operatorname{card}\big((X\cap Z)\cup(Y\cap Z)\big) = \operatorname{card}(X\cap Z)+\operatorname{card}(Y\cap Z)-\operatorname{card}(X\cap Y\cap Z).
  1. 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:
\operatorname{card}(X\cup Y\cup Z) = \operatorname{card}(X)+\operatorname{card}(Y)+\operatorname{card}(Z) -\operatorname{card}(X\cap Y)-\operatorname{card}(X\cap Z)-\operatorname{card}(Y\cap Z) +\operatorname{card}(X\cap Y\cap Z).
  1. Como soma e diferenças de inteiros finitos, X\cup Y\cup Z é finito.
Comentário: também é possível provar particionando X\cup Y\cup Z 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 X_1,\dots,X_k finitos (não necessariamente disjuntos) com \operatorname{card}(X_i)=m_i, mostrar que \bigcup_{i=1}^k X_i é finito e
\operatorname{card}\!\left(\bigcup_{i=1}^k X_i\right)\le m_1+\cdots+m_k.
Demonstração usando a união disjunta com índices (construção clara e comum):
  1. Considere o conjunto “união disjunta indexada”
D=\{(i,x)\mid 1\le i\le k,\\ x\in X_i\}.
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 x sejam iguais — por isso D é uma versão disjunta dos X_i.
  1. Há uma bijeção evidente entre D e a união disjunta formal (ou, alternativamente, D é uma união disjunta dos conjuntos \{i\}\times X_i). Pela parte (b), como cada \{i\}\times X_i tem \operatorname{card}(X_i)=m_i elementos, tem-se
\operatorname{card}(D)=\sum_{i=1}^k m_i.
  1. Defina a projeção sobre o segundo componente
p:D\to\bigcup_{i=1}^k X_i,\qquad p(i,x)=x.
Essa projeção é sobrejetora: para todo x\in\bigcup_{i=1}^k X_i existe algum índice i com x\in X_i, e então (i,x)\in D e p(i,x)=x.
  1. Como existe uma função sobrejetora p:D\to\bigcup_{i=1}^k X_i, a cardinalidade do conjunto imagem satisfaz
\operatorname{card}\!\left(\bigcup_{i=1}^k X_i\right)\le \operatorname{card}(D).
Isto é uma consequência geral: se há uma função sobrejetora de um conjunto finito A para B, então \operatorname{card}(B)\le\operatorname{card}(A).
  1. Combinando com passo 2:
\operatorname{card}\!\left(\bigcup_{i=1}^k X_i\right)\le \sum_{i=1}^k m_i.
E como o lado direito é finito, a união é finita.
Intuição: se você simplesmente “colocar” os elementos de cada X_i numa lista marcada pelo índice, terá exatamente \sum m_i pares; projetando-os tirando o índice pode haver colisões (elementos iguais em diferentes X_i), por isso o número na união pode ser menor, nunca maior.

Resposta

(a) \operatorname{card}(X\cup Y)=m+n.
(b) \operatorname{card}\!\left(\bigcup_{i=1}^{k} X_{i}\right)=m_{1}+m_{2}+\cdots+m_{k}.
(c) \operatorname{card}(X\cup Y)=\operatorname{card}(X)+\operatorname{card}(Y)-\operatorname{card}(X\cap Y).
(d) \displaystyle \operatorname{card}(X\cup Y\cup Z)=\operatorname{card}(X)+\operatorname{card}(Y)+\operatorname{card}(Z)-\operatorname{card}(X\cap Y)-\operatorname{card}(X\cap Z)-\operatorname{card}(Y\cap Z)+\operatorname{card}(X\cap Y\cap Z).
(e) \displaystyle \operatorname{card}\!\left(\bigcup_{i=1}^k X_i\right)\le m_1+m_2+\cdots+m_k.

Exercícios relacionados