Indicando com
o número de elementos do conjunto finito
, prove que:
Se
é finito e
, então
Se
Passo 1
O que o enunciado nos dá e o que pede:
- É dado que
é um conjunto finito. - É dado que
. - A notação
significa o número de elementos do conjunto finito . - O enunciado pede para provar a igualdade
Vou listar claramente as informações relevantes:
é um subconjunto de
(portanto todos os elementos de
estão em
), e
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
em duas partes disjuntas — os elementos que estão em
e os que estão em
— 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
é 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
para algum inteiro . Isso significa que existe uma enumeração dos elementos de , isto é, uma bijeção . - Se
, então os elementos de aparecem entre os elementos listados por . Para construir uma enumeração de basta selecionar, na ordem em que aparecem em , os índices cujo elemento pertence a . Como há no máximo desses índices, obtemos uma bijeção de para para algum . - Conclusão:
é um inteiro , logo é finito. Em particular, também é subconjunto de um conjunto finito, e portanto é finito.
Esta é uma justificativa direta e construtiva: partir de uma enumeração de
obtém-se enumeração de qualquer subconjunto.
Passo 4
Lema útil: se
Prova do lema (construtiva):
- Seja
e . Então existem bijeções
e . - Como
e são disjuntos, posso definir uma função por - A função
porque toda imagem de
e está em e juntas cobrem . É injetora porque nenhuma imagem de coincide com imagem de (disjunção), e dentro de e dentro de as funções eram bijetoras. Logo é bijeção entre e . - Portanto
.
Isto formaliza a intuição de "contar primeiro os dee depois os de ".]
Passo 5
Aplicando o lema ao nosso problema:
- Observa-se que
é a união disjunta de e . De fato, por definição de diferença, e (todo elemento de ou está em ou não). - Já provamos que
e são finitos (Passo 3). Então pelo lema do Passo 4 vale
Passo 6
Rearranjando a igualdade do passo anterior obtemos exatamente o que queríamos:
Isso conclui a demonstração. Se quiser, pense num exemplo concreto para fixar a ideia: se
e
, então
,
e
tem
.