Indicando com \operatorname{card}(X) o número de elementos do conjunto finito X, prove que:
Se X é finito e Y \subset X, então
\operatorname{card}(X-Y)=\operatorname{card}(X)-\operatorname{card}(Y)

Passo 1

O que o enunciado nos dá e o que pede:
  • É dado que X é um conjunto finito.
  • É dado que Y\subset X.
  • A notação \operatorname{card}(Z) significa o número de elementos do conjunto finito Z.
  • O enunciado pede para provar a igualdade
\operatorname{card}(X-Y)=\operatorname{card}(X)-\operatorname{card}(Y).
Vou listar claramente as informações relevantes: Y é um subconjunto de X (portanto todos os elementos de Y estão em X), e X tem um número finito de elementos. Ainda não estou resolvendo: só identifiquei o que foi dado e o que preciso mostrar.

Passo 2

Ideia geral da prova (sem detalhes ainda): separar X em duas partes disjuntas — os elementos que estão em Y e os que estão em X-Y — e usar que, para conjuntos finitos disjuntos, o número de elementos da união é a soma dos números de elementos. Para que isso seja legítimo preciso garantir duas coisas: (i) que X-Y é finito, e (ii) provar (ou justificar) o fato simples sobre união disjunta de conjuntos finitos. Vou tratar disso nos próximos passos.

Passo 3

Mostrando que todo subconjunto de um conjunto finito é finito (justificativa):
  • Suponha que \operatorname{card}(X)=n para algum inteiro n\ge 0. Isso significa que existe uma enumeração dos elementos de X, isto é, uma bijeção f:\{1,2,\dots,n\}\to X.
  • Se Y\subset X, então os elementos de Y aparecem entre os n elementos listados por f. Para construir uma enumeração de Y basta selecionar, na ordem em que aparecem em f, os índices cujo elemento pertence a Y. Como há no máximo n desses índices, obtemos uma bijeção de \{1,2,\dots,m\} para Y para algum m\le n.
  • Conclusão: \operatorname{card}(Y) é um inteiro m\le n, logo Y é finito. Em particular, X-Y\subset X também é subconjunto de um conjunto finito, e portanto X-Y é finito.
Esta é uma justificativa direta e construtiva: partir de uma enumeração de X obtém-se enumeração de qualquer subconjunto.

Passo 4

Lema útil: se A\) e \(B\) são conjuntos finitos e disjuntos (isto é, \(A\cap B=\varnothing\)), então \[\operatorname{card}(A\cup B)=\operatorname{card}(A)+\operatorname{card}(B).
Prova do lema (construtiva):
  • Seja \operatorname{card}(A)=m e \operatorname{card}(B)=n. Então existem bijeções
    \varphi:\{1,\dots,m\}\to A e \psi:\{1,\dots,n\}\to B.
  • Como A e B são disjuntos, posso definir uma função h:\{1,\dots,m+n\}\to A\cup B por h(k)=\begin{cases} \varphi(k), & \text{se }1\le k\le m,\\[4pt] \psi(k-m), & \text{se }m+1\le k\le m+n. \end{cases}
  • A função h\] é sobrejetora em \(A\cup B porque toda imagem de \varphi e \psi está em A\cup B e juntas cobrem A\cup B. É injetora porque nenhuma imagem de \varphi coincide com imagem de \psi (disjunção), e dentro de \varphi e dentro de \psi as funções eram bijetoras. Logo h é bijeção entre \{1,\dots,m+n\} e A\cup B.
  • Portanto \operatorname{card}(A\cup B)=m+n=\operatorname{card}(A)+\operatorname{card}(B).
    Isto formaliza a intuição de "contar primeiro os de A e depois os de B".]

Passo 5

Aplicando o lema ao nosso problema:
  • Observa-se que X é a união disjunta de Y e X-Y. De fato, Y\cap (X-Y)=\varnothing por definição de diferença, e Y\cup (X-Y)=X (todo elemento de X ou está em Y ou não).
  • Já provamos que Y e X-Y são finitos (Passo 3). Então pelo lema do Passo 4 vale \operatorname{card}(X)=\operatorname{card}\bigl(Y\cup (X-Y)\bigr)=\operatorname{card}(Y)+\operatorname{card}(X-Y).

Passo 6

Rearranjando a igualdade do passo anterior obtemos exatamente o que queríamos:
\operatorname{card}(X-Y)=\operatorname{card}(X)-\operatorname{card}(Y).
Isso conclui a demonstração. Se quiser, pense num exemplo concreto para fixar a ideia: se X=\{a,b,c,d\} e Y=\{a,c\}, então \operatorname{card}(X)=4, \operatorname{card}(Y)=2 e X-Y=\{b,d\} tem \operatorname{card}(X-Y)=2=4-2.

Resposta

\operatorname{card}(X-Y)=\operatorname{card}(X)-\operatorname{card}(Y)

Exercícios relacionados