Indicando com
o número de elementos do conjunto finito
, prove que:
Se
são finitos e
, então
é finito e
Se
Passo 1
O que o enunciado dá e o que pede (vou reescrever de forma precisa): são dados dois conjuntos
e
tais que
-
e são finitos; -
(ou seja, são disjuntos).
O que se pede provar:
- Que
é finito; - Que
.
Vou anotar também os números de elementos (que existem porque os conjuntos são finitos):
- Seja
. - Seja
.
Passo 2
Lembrando a definição de “conjunto finito” e de bijeção (explicação didática):
- Dizer que um conjunto
é finito significa que existe um inteiro positivo e uma bijeção entre e o conjunto . Uma bijeção é uma função que é ao mesmo tempo injetora (valores distintos no domínio vão para valores distintos na imagem) e sobrejetora (todo elemento do contradomínio tem alguma pré-imagem). - Assim, para
finito existe uma bijeção . Para finito existe uma bijeção .
Essa é a maneira padrão de “enumerar” os elementos de um conjunto finito: listarelementos como , e elementos como .
Passo 3
Construção das enumerações (pequena aula prática):
- Como
é finito com , escolhemos e fixamos uma bijeção
Isto significa que os elementos de
são
todos distintos e que não há outros.
- Como
é finito com , escolhemos e fixamos uma bijeção
Os elementos de
são
.
Passo 4
Definição da função que vai unir as enumerações (ideia central):
- Vamos definir uma função
Essa é uma definição natural: os primeiros
; os próximos
índices correspondem aos elementos de
.]
Passo 5
Provar que
é injetora (passo técnico e importante):
- Tome
tais que . Queremos mostrar . - Caso 1: Se
e , então e . Como é injetora, implica . - Caso 2: Se
e , então e . Como é injetora, implica , i.e. . - Caso 3: Se
e (ou simetricamente e ), então e . Mas pelos dados , então não pode ser igual a . Portanto esse caso não pode ocorrer quando . - Conclusão: nos três casos,
implica . Logo é injetora.
Passo 6
Provar que
é sobrejetora:
- Tome um elemento
. Então ou . - Se
, como é sobrejetora existe tal que . Pela definição de temos . - Se
, como é sobrejetora existe tal que . Pela definição de temos . - Em ambos os casos encontramos um índice em
cujo valor por é . Logo é sobrejetora.
Passo 7
Concluir que
é bijeção e interpretar o resultado:
- Como mostramos que
é injetora e sobrejetora, é bijeção entre e . - Isto implica que
é finito (pois é bijetável com ) e que
- Lembrando que
e , obtemos a igualdade desejada.
Passo 8
Comentário final, intuitivo e motivador:
- Intuitivamente, como
e não têm elementos em comum, para contar os elementos do conjunto unido basta contar os de e os de separadamente e somar. A prova formal que fizemos mostra isso construindo uma enumeração explícita sem repetições. - Bom trabalho por chegar até aqui — essa construção de “colar” duas enumerações é uma técnica que aparece muito; guarda ela na mochila para a prova!