Prove que não existe uma função bijetiva entre o conjunto das sequências crescentes \left(n_{1}<n_{2}<n_{3}<\cdots\right) de números naturais e o próprio conjunto dos naturais.
Passo 1
O enunciado pede para provar que não existe bijeção entre o conjunto das sequências estritamente crescentes de naturais
S=\{(n_1<n_2<n_3<\cdots)\mid n_i\in\mathbb{N}\}
e o conjunto dos naturais \mathbb{N}.
Informações dadas (o que o problema especifica):
Cada elemento de S é uma sequência infinita de naturais com n_1<n_2<n_3<\cdots.
A tarefa é mostrar que não existe uma função bijetiva f:\mathbb{N}\to S.
Passo 2
Ideia geral (em palavras simples): vou mostrar que [S) tem “mais” elementos que \mathbb{N}, isto é, S é incontável. Para isso vou relacionar S com o conjunto das sequências binárias (sequências de zeros e uns) e usar o argumento diagonal de Cantor para obter uma contradição caso alguém tentasse enumerar todas as sequências.
Primeiro, transformo cada sequência estritamente crescente em uma sequência binária (função característica): para cada sequência a=(n_1<n_2<\cdots)\in S defino a sua função característica \chi_a:\mathbb{N}\to\{0,1\} por
Assim cada a\in S\] corresponde a uma sequência binária infinita com infinitamente muitos \(1s (porque a sequência é infinita). Denotemos por T o conjunto dessas sequências binárias que têm infinitamente muitos 1s:
T=\{\chi:\mathbb{N}\to\{0,1\}\mid \chi\text{ tem infinitely many }1\}.
A passagem a\mapsto\chi_a é uma bijeção entre S e T. Portanto provar que S é incontável é equivalente a provar que T é incontável.]
Passo 3
Lembrando um fato-chave (explicado devagar): o conjunto [B) de todas as sequências binárias (ou seja, todas as funções \beta:\mathbb{N}\to\{0,1\}, sem restrição) é incontável. A prova clássica é o argumento diagonal de Cantor — vou reavaliar isso passo a passo.
Suponha, por contradição, que B seja enumerável. Então existe uma lista
que contém todas as sequências binárias, onde \beta^{(i)}=(\beta^{(i)}_1,\beta^{(i)}_2,\beta^{(i)}_3,\dots) e \beta^{(i)}_j\in\{0,1\} é o j-ésimo termo da i-ésima sequência.
Agora constrói-se uma nova sequência \gamma=(\gamma_1,\gamma_2,\gamma_3,\dots) definindo, para cada k\in\mathbb{N},
Ou seja, \gamma_k\] é o complemento do elemento na posição diagonal \(\beta^{(k)}_k. Por construção \gamma difere de \beta^{(k)} na coordenada k, para todo k. Logo \gamma não coincide com nenhuma \beta^{(k)} da lista — contradição com a suposição de que a lista enumerava todas as sequências binárias. Portanto B não é enumerável (é incontável).]
Passo 4
Agora preciso relacionar B (todas as sequências binárias) com T (as sequências binárias com infinitos 1s). Mostrarei que há uma injeção de B em T. Isso implicará que T também é incontável (uma imagem injetiva de um conjunto incontável tem pelo menos a mesma cardinalidade).
Defina a aplicação g:B\to T que pega uma sequência binária arbitrária \beta=(\beta_1,\beta_2,\beta_3,\dots) e constrói a sequência g(\beta)=\chi=(\chi_1,\chi_2,\chi_3,\dots) por
\chi_{2n-1}=1,\qquad \chi_{2n}=\beta_n\quad\text{para todo }n\in\mathbb{N}.
Ou seja, intercalo um 1 nas posições ímpares e coloco \beta_n nas posições pares. Por exemplo, se \beta=(0,1,0,0,\dots) então
g(\beta)=(1,0,1,1,1,0,1,0,\dots).
Propriedades importantes:
Para qualquer \beta fixo, g(\beta) tem muitos 1s: todas as posições ímpares são 1, logo g(\beta) tem infinitamente muitos 1s; portanto g(\beta)\in T.
g é injetora: se g(\beta)=g(\beta') então olhando às posições pares obtemos \beta_n=\beta'_n para todo n, logo \beta=\beta'.
Como g injeta B em T e já provamos que B é incontável, segue que T é incontável.
Passo 5
Voltando à bijeção inicial entre S e T: como T é incontável, S é incontável. Um conjunto incontável não pode ser posto em bijeção com \mathbb{N} (pois \mathbb{N} é enumerável). Logo não existe bijeção f:\mathbb{N}\to S.
Passo 6
Resumo em palavras amigáveis: cada sequência estritamente crescente corresponde a uma sequência binária com infinitos 1s. Há tantas sequências binárias (é o mesmo tipo de infinito que o conjunto das partes de \mathbb{N}) que não dá para listá‑las uma a uma. Como dá para transformar qualquer sequência binária numa com infinitos 1s (intercalando 1s), conclui‑se que também não é possível listar todas as sequências crescentes. Portanto não existe bijeção entre S e \mathbb{N}.
Resposta
Não existe bijeção entre S e \mathbb{N}: o conjunto das sequências estritamente crescentes de naturais é incontável (não enumerável), logo não pode ser colocado em bijeção com \mathbb{N}.