Prove que \mathbb{Z} é enumerável. Para isso mostre que existe uma bijeção f: \mathbb{N} \rightarrow \mathbb{Z}.
Passo 1
O que o enunciado pede e o que vamos usar.
O enunciado pede para provar que \mathbb{Z} é enumerável, ou seja, que existe uma bijeção f:\mathbb{N}\to\mathbb{Z}.
Vou adotar a convenção usual aqui: \mathbb{N}=\{0,1,2,\dots\}.
Objetivo concreto: construir uma função explícita f:\mathbb{N}\to\mathbb{Z} e provar que ela é bijetora (injeta e sobrejeta).
Plano intuitivo (só para entender a construção): listar os inteiros na ordem 0,-1,1,-2,2,-3,3,\dots. A partir dessa lista dá para definir f de modo que f(0)=0, f(1)=-1, f(2)=1, f(3)=-2, etc.
Passo 2
Definição explícita da função [f) e explicação da construção.
A função f:\mathbb{N}\to\mathbb{Z} é dada por
f(n)= \begin{cases} 0, & \text{se } n=0,\\[4pt] \dfrac{n}{2}, & \text{se } n\ge 2 \text{ e } n \text{ é par},\\[6pt] -\dfrac{n+1}{2}, & \text{se } n \text{ é ímpar}. \end{cases}
Explicando em palavras:
f(0)=0\].
- Se \(n é par e n\ge2, escrevemos n=2k com k\ge1 e então f(n)=k. Isso coloca os inteiros positivos nas posições pares de \mathbb{N}: f(2)=1,f(4)=2,\dots.
- Se n é ímpar, escrevemos n=2k-1 com k\ge1 (ou usar a fórmula acima) e então f(n)=-k. Isso coloca os inteiros negativos nas posições ímpares: f(1)=-1,f(3)=-2,\dots.
Exemplos para fixar:
f(0)=0.
f(1)=-\dfrac{1+1}{2}=-1.
f(2)=\dfrac{2}{2}=1.
f(3)=-\dfrac{3+1}{2}=-2.
f(4)=\dfrac{4}{2}=2.
A sequência de valores é 0,-1,1,-2,2,-3,3,\dots, que cobre todos os inteiros visualmente.]
Passo 3
Construção do inverso candidate [g:\mathbb{Z}\to\mathbb{N}) (ideia: mostrar que f tem inverso é a maneira mais direta de provar bijeção).
Para z>0\] queremos \(g(z) ser o índice n par que produz z, então g(z)=2z porque f(2z)=z pela definição de f.
Para z<0, se z=-k com k\ge1, queremos g(z)= índice ímpar 2k-1. Calculando em termos de z dá g(z)=-2z-1 (pois z=-k\Rightarrow -2z-1=2k-1).
Para z=0 escolhemos g(0)=0.
Exemplos:
g(1)=2, g(2)=4.
g(-1)=-2(-1)-1=1, g(-2)=-2(-2)-1=3.]
Passo 4
Provar que f\bigl(g(z)\bigr)=z para todo z\in\mathbb{Z} (ou seja, f\circ g=\mathrm{id}_{\mathbb{Z}}).
Considerar os três casos para z.
Se z=0: g(0)=0 por definição e f(g(0))=f(0)=0=z.
Se z>0: então g(z)=2z (um número par \ge2). Pela definição de f para pares, f(2z)=\dfrac{2z}{2}=z. Logo f(g(z))=z.
Se z<0: escreva z=-k com k\ge1. Então g(z)=-2z-1=-2(-k)-1=2k-1, que é ímpar. Pela definição de f para ímpares, f(2k-1)=-\dfrac{(2k-1)+1}{2}=-\dfrac{2k}{2}=-k=z. Logo f(g(z))=z.
Assim, para todo z\in\mathbb{Z} tem-se f(g(z))=z.
Passo 5
Provar que g\bigl(f(n)\bigr)=n para todo n\in\mathbb{N} (ou seja, g\circ f=\mathrm{id}_{\mathbb{N}}).
Considerar os casos para n.
Se n=0: f(0)=0 e g(f(0))=g(0)=0=n.
Se n\ge2 é par: escreva n=2k com k\ge1. Então f(n)=f(2k)=\dfrac{2k}{2}=k (um inteiro positivo). Aplicando g temos g(f(n))=g(k)=2k=n.
Se n é ímpar: escreva n=2k-1 com k\ge1. Então f(n)=f(2k-1)=-\dfrac{(2k-1)+1}{2}=-k. Aplicando g para este inteiro negativo:
g(f(n))=g(-k)=-2(-k)-1=2k-1=n.
Portanto g(f(n))=n em todos os casos.
Passo 6
Concluir que f é bijetora e interpretar o resultado.
Das Passo 4 e Passo 5 temos f\circ g=\mathrm{id}_{\mathbb{Z}} e g\circ f=\mathrm{id}_{\mathbb{N}}. Isso mostra que g é a função inversa de f.
Uma função que possui inversa é, por definição, bijetora (injectiva e sobrejetiva).
Logo f é bijeção de \mathbb{N} sobre \mathbb{Z}. Portanto \mathbb{Z} é enumerável (contável) — conseguimos listar todos os inteiros em uma sequência indexada por \mathbb{N}.
Bom trabalho! Essa é uma construção padrão: intercala zero, negativos e positivos. Serve sempre que precisar enumerar \mathbb{Z}.
Resposta
f:\mathbb{N}\to\mathbb{Z},\qquad f(n)= \begin{cases} 0, & \text{se } n=0,\\[4pt] \dfrac{n}{2}, & \text{se } n\ge 2 \text{ e } n \text{ é par},\\[6pt] -\dfrac{n+1}{2}, & \text{se } n \text{ é ímpar}, \end{cases}ééí