Seja
um subconjunto infinito. Prove que existe uma única bijeção crescente
.
Passo 1
O enunciado dá um conjunto
que é infinito. O que ele pede é provar duas coisas:
- Existência: mostrar que existe uma função
que é bijetora e crescente. - Unicidade: mostrar que essa função crescente e bijetora é única.
Informações relevantes dadas:
-
é um subconjunto de . -
é infinito (ou seja, não é finito).
Passo 2
Vamos lembrar dois fatos básicos que vamos usar (explicando o porquê deles serem verdadeiros):
-
Princípio da boa ordenação de
: todo subconjunto não vazio de tem um elemento mínimo. Isso significa que, se e , então existe . Intuição: começa em (ou , conforme convenção) e os números naturais são “discretos para cima”, logo sempre há um menor elemento. -
Se
é infinito e é finito, então . Em particular, remover um número finito de elementos de um conjunto infinito não o esgota. Prova curta: se então e então seria finito, contradizendo a hipótese.
Esses dois fatos justificam que, ao retirar um número finito de elementos de
, ainda sobra pelo menos um elemento e podemos aplicar
ao conjunto remanescente.
Passo 3
Construção da função
(existência): vamos definir
por recorrência, escolhendo sempre o menor elemento disponível em
.
- Defina
. Pelo princípio da boa ordenação, existe porque é não vazio (é infinito). - Suponha que
já foram definidos e são distintos. Considere o conjunto remanescente
Como
é finito e
é infinito, temos
. Então, por boa ordenação,
existe. Defina
Dessa forma
está definida para todo
.
Esta definição dá uma sequência
cujo termo
é, em palavras, o
-ésimo menor elemento de
.
Passo 4
Prova de que
é estritamente crescente: quero mostrar que, para todo
,
Pelo modo de construção,
. Em particular, todos os elementos
são menores ou iguais a
, e como
é mínimo do conjunto remanescente, não pode ser igual a nenhum dos
com
. Além disso, nenhum elemento remanescente pode ser menor que algum dos já retirados (porque então esse menor já teria sido escolhido antes). Logo necessariamente
. Formalizando por indução simples:
por construção; se
então
, sendo o mínimo dos elementos não escolhidos, tem que ser maior que
. Portanto a sequência é estritamente crescente.
Passo 5
Prova de injetividade (já quase óbvia): como
é estritamente crescente, se
então
. Assim
é injetora.
Explicação didática: funções crescentes estritas em
não podem colapsar dois índices distintos no mesmo valor, porque isso violaria a ordem.
Passo 6
Prova de que a imagem de
é todo
(surjetividade): pela construção, os elementos
são exatamente os elementos de
listados em ordem crescente. Vou transformar isso em prova rigorosa.
Defina
. Pelas definições,
. Queremos mostrar
. Tome
. Considere o conjunto
Esse conjunto é não vazio porque
. Se
fosse finito, então teria um máximo
. Como a sequência
é estritamente crescente, teríamos
. Mas
foi construído como o menor elemento de
. Se
e
não pertence a
(hipótese que estamos testando: suponha
), então
pertence ao conjunto remanescente e, por minimalidade, deveríamos ter
, contradizendo
. Portanto não pode ser que
seja finito sob a hipótese
. Logo
é infinito, o que significa que existem índices
com
(pois a sequência não pode crescer indefinidamente mantendo-se ≤
sem atingir
). Assim
. Conclusão:
, logo
e
é sobrejetora.
Comentário mais intuitivo: pela construção escolhemos sempre o menor elemento restante; assim cada elemento de
acabará sendo escolhido numa etapa finita — o elemento é o seu próprio “posto” na ordenação crescente.
Passo 7
Conclusão da existência: a função
construída é injetora (Passo 5), sobrejetora (Passo 6) e estritamente crescente (Passo 4). Portanto
é uma bijeção crescente de
sobre
.
Observação prática: podemos dizer em palavras finais que
é o
-ésimo menor elemento de
; essa é uma descrição explícita e prática para usar numa prova ou num exercício.
Passo 8
Prova de unicidade: suponha que
seja outra bijeção crescente. Vou mostrar por indução que, para todo
,
.
-
Caso base
: como é crescente, temos (senão, se então estaria em algum com , contradizendo a monotonia ). Logo . -
Passo indutivo: suponha
para todos . Considere . Os valores coincidem com . Como é crescente, é o menor elemento de que é maior que ; mas isso coincide exatamente com a definição de (o menor elemento de ). Então . Assim a igualdade se mantém para todo .
Portanto qualquer bijeção crescente
coincide com
termo a termo, o que mostra a unicidade.
Resposta
A função
existe e é única; ela é dada por
o
-ésimo menor elemento de
(isto é,
e
para todo
).