Questão 25 Seja
, o conjunto de todos os polinômios com coeficientes inteiros e de grau menor ou igual a
. Mostre que
é enumerável.
Passo 1
O enunciado dá o conjunto
: todos os polinômios com coeficientes inteiros e de grau menor ou igual a
, para um
fixo. A pergunta é: mostrar que
é enumerável.
Informações relevantes que temos:
- Um elemento de
tem a forma com cada coeficiente . -
é fixo (um natural), então todo polinômio tem exatamente 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
. Em prática, para conjuntos infinitos como o nosso, costuma-se mostrar que existe uma bijeção entre o conjunto e
(ou uma injeção recíproca com
e uma sobrejeção, etc.). Vou construir um argumento que exibe explicitamente como listar todos os elementos de
.
Passo 3
Observação chave (representação por coeficientes). Cada polinômio
corresponde de maneira única ao tuplo dos seus coeficientes:
Essa correspondência é bijetiva porque os coeficientes de um polinômio são únicos: dada uma sequência
há exatamente um polinômio com esses coeficientes, e coeficientes iguais correspondem ao mesmo polinômio. Portanto
Logo, para provar que
é enumerável basta mostrar que
é enumerável (contável). Vou provar isso em etapas mais básicas: primeiro que
é enumerável; depois que produto finito de conjuntos enumeráveis é enumerável.
Passo 4
Mostrar que
é enumerável. Uma enumeração clássica e simples de
(isto é, uma bijeção
) é:
Em palavras:
— assim cada inteiro aparece exatamente uma vez. Isso mostra que existe bijeção entre
e
, então
é enumerável.
Passo 5
Produto de dois conjuntos enumeráveis é enumerável. Vou explicar a ideia com
(o caso
fica análogo usando a bijeção de
com
). Podemos listar os pares
percorrendo as diagonais:
Esse procedimento dá uma enumeração de todos os pares: cada par aparece em algum momento (na diagonal
constante), portanto
é enumerável. Formalmente, existe uma bijeção (por exemplo a função de Cantor ou a enumeração por soma das coordenadas) entre
e
.
Passo 6
Indução para produto finito. Sabendo que
é enumerável, consegue-se provar por indução que
é enumerável para todo
. O passo indutivo usa que
e o produto de dois conjuntos enumeráveis é enumerável. Assim
é enumerável.
Passo 7
Transferindo para
. Já vimos que
é enumerável, então existe bijeção
. Aplicando
coordenada a coordenada obtemos uma bijeção
Como
é enumerável (Passo 7), e há bijeção entre
e
, concluímos que
é enumerável.
Passo 8
Combinação das partes: lembrando do Passo 3,
é bijetível com
. Pelo Passo 8,
é enumerável. Portanto
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
por exemplo, os polinômios
podem ser listados assim: comece por
, depois
. A ideia é sempre a mesma: reduzir ao produto finito de conjuntos enumeráveis.