Seja X \subset \mathbb{N} um subconjunto infinito. Prove que existe uma única bijeção crescente f: \mathbb{N} \rightarrow X.

Passo 1

O enunciado dá um conjunto X\subset\mathbb{N} que é infinito. O que ele pede é provar duas coisas:
  • Existência: mostrar que existe uma função f:\mathbb{N}\to X que é bijetora e crescente.
  • Unicidade: mostrar que essa função crescente e bijetora é única.
Informações relevantes dadas:
  • X é um subconjunto de \mathbb{N}.
  • X é infinito (ou seja, não é finito).

Passo 2

Vamos lembrar dois fatos básicos que vamos usar (explicando o porquê deles serem verdadeiros):
  1. Princípio da boa ordenação de \mathbb{N}: todo subconjunto não vazio de \mathbb{N} tem um elemento mínimo. Isso significa que, se A\subset\mathbb{N} e A\neq\varnothing, então existe \min A\in A. Intuição: \mathbb{N} começa em 1 (ou 0, conforme convenção) e os números naturais são “discretos para cima”, logo sempre há um menor elemento.
  2. Se X\subset\mathbb{N} é infinito e F\subset\mathbb{N} é finito, então X\setminus F\neq\varnothing. Em particular, remover um número finito de elementos de um conjunto infinito não o esgota. Prova curta: se X\setminus F=\varnothing então X\subset F e então X seria finito, contradizendo a hipótese.
Esses dois fatos justificam que, ao retirar um número finito de elementos de X, ainda sobra pelo menos um elemento e podemos aplicar \min ao conjunto remanescente.

Passo 3

Construção da função f (existência): vamos definir f por recorrência, escolhendo sempre o menor elemento disponível em X.
  • Defina \,f(1)=\min X\,. Pelo princípio da boa ordenação, \min X existe porque X é não vazio (é infinito).
  • Suponha que f(1),f(2),\dots,f(n) já foram definidos e são distintos. Considere o conjunto remanescente
X_n:=X\setminus\{f(1),f(2),\dots,f(n)\}.
Como \{f(1),\dots,f(n)\} é finito e X é infinito, temos X_n\neq\varnothing. Então, por boa ordenação, \min X_n existe. Defina
f(n+1):=\min X_n.
Dessa forma f está definida para todo n\in\mathbb{N}.
Esta definição dá uma sequência (f(n))_{n\ge1} cujo termo f(n) é, em palavras, o n-ésimo menor elemento de X.

Passo 4

Prova de que f é estritamente crescente: quero mostrar que, para todo n,
f(n+1)>f(n).
Pelo modo de construção, f(n+1)=\min\bigl(X\setminus\{f(1),\dots,f(n)\}\bigr). Em particular, todos os elementos f(1),\dots,f(n) são menores ou iguais a f(n), e como f(n+1) é mínimo do conjunto remanescente, não pode ser igual a nenhum dos f(k) com k\le n. 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 f(n+1)>f(n). Formalizando por indução simples: f(1)<f(2) por construção; se f(1)<\cdots<f(n) então f(n+1), sendo o mínimo dos elementos não escolhidos, tem que ser maior que f(n). Portanto a sequência é estritamente crescente.

Passo 5

Prova de injetividade (já quase óbvia): como f é estritamente crescente, se m\neq n então f(m)\neq f(n). Assim f é injetora.
Explicação didática: funções crescentes estritas em \mathbb{N} não podem colapsar dois índices distintos no mesmo valor, porque isso violaria a ordem.

Passo 6

Prova de que a imagem de f é todo X (surjetividade): pela construção, os elementos \{f(1),f(2),\dots\} são exatamente os elementos de X listados em ordem crescente. Vou transformar isso em prova rigorosa.
Defina Y:=\{f(n):n\in\mathbb{N}\}. Pelas definições, Y\subset X. Queremos mostrar X\subset Y. Tome x\in X. Considere o conjunto
A:=\{n\in\mathbb{N}:f(n)\le x\}.
Esse conjunto é não vazio porque f(1)=\min X\le x. Se A fosse finito, então teria um máximo m. Como a sequência f(n) é estritamente crescente, teríamos f(m)\le x < f(m+1). Mas f(m+1) foi construído como o menor elemento de X\setminus\{f(1),\dots,f(m)\}. Se x\in X e x não pertence a \{f(1),\dots,f(m)\} (hipótese que estamos testando: suponha x\notin Y), então x pertence ao conjunto remanescente e, por minimalidade, deveríamos ter f(m+1)\le x, contradizendo f(m+1)>x. Portanto não pode ser que A seja finito sob a hipótese x\notin Y. Logo A é infinito, o que significa que existem índices n com f(n)=x (pois a sequência não pode crescer indefinidamente mantendo-se ≤ x sem atingir x). Assim x\in Y. Conclusão: X\subset Y, logo Y=X e f é sobrejetora.
Comentário mais intuitivo: pela construção escolhemos sempre o menor elemento restante; assim cada elemento de X 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 f:\mathbb{N}\to X construída é injetora (Passo 5), sobrejetora (Passo 6) e estritamente crescente (Passo 4). Portanto f é uma bijeção crescente de \mathbb{N} sobre X.
Observação prática: podemos dizer em palavras finais que f(n) é o n-ésimo menor elemento de X; essa é uma descrição explícita e prática para usar numa prova ou num exercício.

Passo 8

Prova de unicidade: suponha que g:\mathbb{N}\to X seja outra bijeção crescente. Vou mostrar por indução que, para todo n, g(n)=f(n).
  • Caso base n=1: como g é crescente, temos g(1)=\min X (senão, se g(1)>\min X então \min X estaria em algum g(k) com k>1, contradizendo a monotonia g(k)>g(1)). Logo g(1)=f(1).
  • Passo indutivo: suponha g(k)=f(k) para todos k\le n. Considere g(n+1). Os valores g(1),\dots,g(n) coincidem com f(1),\dots,f(n). Como g é crescente, g(n+1) é o menor elemento de X que é maior que g(n)=f(n); mas isso coincide exatamente com a definição de f(n+1) (o menor elemento de X\setminus\{f(1),\dots,f(n)\}). Então g(n+1)=f(n+1). Assim a igualdade se mantém para todo n.
Portanto qualquer bijeção crescente g coincide com f termo a termo, o que mostra a unicidade.

Resposta

A função f:\mathbb{N}\to X existe e é única; ela é dada por f(n)= o n-ésimo menor elemento de X (isto é, f(1)=\min X e f(n+1)=\min\bigl(X\setminus\{f(1),\dots,f(n)\}\bigr) para todo n).

Exercícios relacionados