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).
Definir g:\mathbb{Z}\to\mathbb{N} por
g(z)= \begin{cases} 0, & \text{se } z=0,\\[4pt] 2z, & \text{se } z>0,\\[6pt] -2z-1, & \text{se } z<0. \end{cases}
Explicaçã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 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.
  1. Se z=0: g(0)=0 por definição e f(g(0))=f(0)=0=z.
  2. 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.
  3. 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.
  1. Se n=0: f(0)=0 e g(f(0))=g(0)=0=n.
  2. 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.
  3. 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}ééí
que é bijeção, portanto \mathbb{Z} é enumerável.]

Exercícios relacionados