Questão 25 Seja \mathcal{P}_{n}(\mathbb{Z}), o conjunto de todos os polinômios com coeficientes inteiros e de grau menor ou igual a n. Mostre que \mathcal{P}_{n}(\mathbb{Z}) é enumerável.

Passo 1

O enunciado dá o conjunto \mathcal{P}_{n}(\mathbb{Z}): todos os polinômios com coeficientes inteiros e de grau menor ou igual a n, para um n fixo. A pergunta é: mostrar que \mathcal{P}_{n}(\mathbb{Z}) é enumerável.
Informações relevantes que temos:
  • Um elemento de \mathcal{P}_{n}(\mathbb{Z}) tem a forma \;p(x)=a_0+a_1x+\cdots+a_nx^n\; com cada coeficiente a_i\in\mathbb{Z}.
  • n é fixo (um natural), então todo polinômio tem exatamente n+1 coeficientes (alguns podendo ser zero).
  • Precisa-se provar que existe uma enumeração (i.e., que o conjunto é contável).

Passo 2

Primeiro vamos lembrar com clareza o que significa “enumerável” neste contexto. Vou usar a definição usual: um conjunto é enumerável se ele é finito ou equiparável a \mathbb{N}. Em prática, para conjuntos infinitos como o nosso, costuma-se mostrar que existe uma bijeção entre o conjunto e \mathbb{N} (ou uma injeção recíproca com \mathbb{N} e uma sobrejeção, etc.). Vou construir um argumento que exibe explicitamente como listar todos os elementos de \mathcal{P}_{n}(\mathbb{Z}).

Passo 3

Observação chave (representação por coeficientes). Cada polinômio p\in\mathcal{P}_{n}(\mathbb{Z}) corresponde de maneira única ao tuplo dos seus coeficientes:
p(x)=a_0+a_1x+\cdots+a_nx^n \longleftrightarrow (a_0,a_1,\dots,a_n)\in\mathbb{Z}^{\,n+1}.
Essa correspondência é bijetiva porque os coeficientes de um polinômio são únicos: dada uma sequência (a_0,\dots,a_n) há exatamente um polinômio com esses coeficientes, e coeficientes iguais correspondem ao mesmo polinômio. Portanto
\mathcal{P}_{n}(\mathbb{Z}) \text{ é equiparável a } \mathbb{Z}^{\,n+1}.éá
Logo, para provar que \mathcal{P}_{n}(\mathbb{Z}) é enumerável basta mostrar que \mathbb{Z}^{\,n+1} é enumerável (contável). Vou provar isso em etapas mais básicas: primeiro que \mathbb{Z} é enumerável; depois que produto finito de conjuntos enumeráveis é enumerável.

Passo 4

Mostrar que \mathbb{Z} é enumerável. Uma enumeração clássica e simples de \mathbb{Z} (isto é, uma bijeção f:\mathbb{N}\to\mathbb{Z}) é:
f(0)=0,\qquad f(2k-1)=k,\qquad f(2k)=-k\quad\text{para }k\ge 1.
Em palavras: 0,1,-1,2,-2,3,-3,\dots — assim cada inteiro aparece exatamente uma vez. Isso mostra que existe bijeção entre \mathbb{N} e \mathbb{Z}, então \mathbb{Z} é enumerável.

Passo 5

Produto de dois conjuntos enumeráveis é enumerável. Vou explicar a ideia com \mathbb{N}\times\mathbb{N} (o caso \mathbb{Z}\times\mathbb{Z} fica análogo usando a bijeção de \mathbb{Z} com \mathbb{N}). Podemos listar os pares (i,j)\in\mathbb{N}\times\mathbb{N} percorrendo as diagonais:
(0,0),\\ (0,1),(1,0),\\ (0,2),(1,1),(2,0),\\ (0,3),(1,2),(2,1),(3,0),\dots
Esse procedimento dá uma enumeração de todos os pares: cada par aparece em algum momento (na diagonal i+j= constante), portanto \mathbb{N}\times\mathbb{N} é enumerável. Formalmente, existe uma bijeção (por exemplo a função de Cantor ou a enumeração por soma das coordenadas) entre \mathbb{N} e \mathbb{N}\times\mathbb{N}.

Passo 6

Indução para produto finito. Sabendo que \mathbb{N}\times\mathbb{N} é enumerável, consegue-se provar por indução que \mathbb{N}^{\,k} é enumerável para todo k\in\mathbb{N}. O passo indutivo usa que \mathbb{N}^{\,k+1} \cong \mathbb{N}^{\,k}\times\mathbb{N} e o produto de dois conjuntos enumeráveis é enumerável. Assim \mathbb{N}^{\,n+1} é enumerável.

Passo 7

Transferindo para \mathbb{Z}^{\,n+1}. Já vimos que \mathbb{Z} é enumerável, então existe bijeção g:\mathbb{N}\to\mathbb{Z}. Aplicando g coordenada a coordenada obtemos uma bijeção
g^{\,n+1}:\mathbb{N}^{\,n+1}\to\mathbb{Z}^{\,n+1}, \qquad g^{\,n+1}(t_0,\dots,t_n)=(g(t_0),\dots,g(t_n)).
Como \mathbb{N}^{\,n+1} é enumerável (Passo 7), e há bijeção entre \mathbb{N}^{\,n+1} e \mathbb{Z}^{\,n+1}, concluímos que \mathbb{Z}^{\,n+1} é enumerável.

Passo 8

Combinação das partes: lembrando do Passo 3, \mathcal{P}_{n}(\mathbb{Z}) é bijetível com \mathbb{Z}^{\,n+1}. Pelo Passo 8, \mathbb{Z}^{\,n+1} é enumerável. Portanto \mathcal{P}_{n}(\mathbb{Z}) também é enumerável.
Observação prática (para a prova): uma forma de imaginar a enumeração é primeiro enumerar todos os tuplos de coeficientes com soma absoluta pequena e ir aumentando essa soma — isso gera uma lista que passa por todo polinômio eventualmente. Para n=1 por exemplo, os polinômios a_0+a_1x podem ser listados assim: comece por (0,0), depois (0,1),(1,0),(0,-1),(-1,0),(1,1),(1,-1),\dots. A ideia é sempre a mesma: reduzir ao produto finito de conjuntos enumeráveis.

Resposta

\mathcal{P}_{n}(\mathbb{Z}) é enumerável.

Exercícios relacionados