Se A \subset \mathbb{N} é tal que A \subset I_{n} para algum n \in \mathbb{N}, use o Princípio da Boa Ordem dos \mathbb{N} para definir uma bijeção de A sobre algum I_{k}, \operatorname{com} k \in \mathbb{N}.

Passo 1

O enunciado dá que A\subset\mathbb{N} e que existe n\in\mathbb{N} tal que A\subset I_{n}. Vou tomar a convenção usual
I_{n}=\{1,2,\dots,n\}.
O que se pede: construir, usando o Princípio da Boa Ordem dos \mathbb{N}, uma bijeção de A sobre algum I_{k} com k\in\mathbb{N}. Em outras palavras, mostrar que existe k (o número de elementos de A) e dar uma bijeção explícita f\colon A\to I_{k}.

Passo 2

Primeiro caso fácil: A=\varnothing. Nesse caso toma-se k=0 e convém definir I_{0}=\varnothing. A função vazia
f\colon \varnothing\to\varnothing
é bijetora (trivialmente injetiva e sobrejetiva). Assim o enunciado está satisfeito quando A=\varnothing.

Passo 3

Agora suponho A\neq\varnothing. Pelo Princípio da Boa Ordem dos \mathbb{N} toda subconjunto não vazio de \mathbb{N} tem um menor elemento. Como A\subset\mathbb{N} e A\neq\varnothing, existe
a_{1}=\min A.
Defino A_{1}=A\setminus\{a_{1}\}. Se A_{1}=\varnothing parei; caso contrário, aplico novamente o Princípio da Boa Ordem a A_{1} para obter
a_{2}=\min A_{1}.
Repetindo o procedimento (remove-se o menor elemento obtido e, se o restante não é vazio, toma-se seu mínimo) obtém-se uma sequência de elementos distintos
a_{1}<a_{2}<\cdots
porque em cada passo se tira o menor elemento remanescente.

Passo 4

É preciso mostrar que esse processo termina em número finito de passos. Como A\subset I_{n}=\{1,\dots,n\}, não pode haver mais que n elementos em A. Portanto o procedimento de remover mínimos produz uma seqüência finita
a_{1}<a_{2}<\cdots<a_{k},
para algum k\le n, tal que
A=\{a_{1},a_{2},\dots,a_{k}\}.
Ou seja, A foi enumerado em ordem crescente e k é exatamente o número de elementos de A, isto é k=|A|\in\mathbb{N}.

Passo 5

Com a enumeração ordenada em mãos, defino a função
f\colon A\to I_{k}
por
f(a_{i})=i\qquad\text{para }i=1,\dots,k.
Agora verifico que f é bijetora:
  • Injetividade: se f(a_{i})=f(a_{j}) então i=j, logo a_{i}=a_{j}. Assim f é injetiva.
  • Sobrejetividade: para qualquer i\in I_{k}=\{1,\dots,k\} existe a_{i}\in A e f(a_{i})=i. Logo f é sobrejetiva.
Portanto f é bijeção entre A e I_{k}.

Passo 6

Resumo final do procedimento (para usar na prova): se A=\varnothing tomar k=0 e a bijeção é a função vazia \varnothing\to\varnothing. Se A\neq\varnothing, usar o Princípio da Boa Ordem para extrair sucessivamente os mínimos e obter a enumeração a_{1}<\cdots<a_{k} de A; então definir f(a_{i})=i. Essa f é bijetora e k=|A|\le n.

Resposta

Se A=\varnothing então k=0 e a bijeção é a função vazia \varnothing\to\varnothing.
Se A\neq\varnothing, seja a_{1}<a_{2}<\cdots<a_{k} a enumeração crescente de A obtida aplicando sucessivamente o Princípio da Boa Ordem; então a bijeção é
f\colon A\to I_{k},\qquad f(a_{i})=i\quad(i=1,\dots,k).

Exercícios relacionados