Exercício 03: Sejam
subconjuntos de
e define-se a sequência
da seguinte forma:
Mostre que a sequência
é uma partição de
Passo 1
O enunciado dá: sejam
subconjuntos de
e define-se a sequência
por
O que o problema pede: mostrar que a família
é uma partição de
Lista das informações relevantes que temos agora:
- Para cada
está dada a fórmula explícita de . - Queremos provar duas coisas (definição de partição — ver passo seguinte): (i) os
são dois a dois disjuntos; (ii) a união de todos os é exatamente .
Passo 2
Primeiro vamos lembrar, de modo claro e prático, o que significa “ser uma partição” (essa é a teoria mínima que precisamos).
- Uma família de conjuntos
é uma partição de um conjunto se: - Cada
está contido em . - Os
são dois a dois disjuntos: sempre que . - A união de todos os
é : .
- Cada
- Observação prática: às vezes alguns
podem ser vazios; nesse caso costumamos descartar os vazios e dizer que os não vazios formam a partição. Aqui vamos mostrar as propriedades (2) e (3); a inclusão em virá automaticamente porque cada .
Plano de ataque (sem resolver ainda): provar (A)
e
para
; (B)
. Vou executar isso passo a passo, explicando cada argumento.
Passo 3
Mostrando que cada
está contido em
(fato trivial, mas útil).
- Pela definição, para
temos . Logo imediatamente
já que
e, para
,
é interseção cujo primeiro fator é
. Assim
(união de subconjuntos é subconjunto da união).
Passo 4
Mostrando que os
são dois a dois disjuntos (prova por contradição simples).
- Pegue
e com . Vou mostrar que . - Suponha, para contradizer, que exista
tal que . - Como
, temos . - Porém, pela definição de
(com ), temos ou seja, todo satisfaz para cada . Em particular, como , devemos ter . - Logo
e simultaneamente, o que é impossível. - Conclusão: não existe tal
, portanto sempre que . Assim os são dois a dois disjuntos.
Passo 5
Mostrando que a união dos
é igual à união dos
.
Fazemos isso em duas inclusões:
Fazemos isso em duas inclusões:
- Já mostramos em um passo anterior que
porque cada
.
- Agora a inclusão contrária
.
- Seja
. Então existe ao menos um índice tal que . - Considere o conjunto de índices
Esse conjunto não é vazio (pois pertence a algum ). Pelo princípio bem conhecido dos naturais (bem-ordenamento de ), todo subconjunto não vazio de tem um menor elemento. Logo existe . - Por definição de
temos e, para todo , . Isso significa exatamente que - Portanto
. - Como
foi um elemento arbitrário de , concluímos .
Juntando as duas inclusões obtemos a igualdade
Passo 6
Observações finais para fechar o raciocínio (didático e prático).
- Já mostramos que (i) os
são dois a dois disjuntos e (ii) sua união é . Além disso cada . Esses são exatamente os ingredientes para dizer que a família é uma partição de . - Nota prática: alguns
podem ser vazios (por exemplo, se então ). Nesse caso normalmente descartamos os vazios e os não vazios formam a partição. Mas a afirmação essencial do enunciado (união = e disjunção par a par) permanece válida.