Prove que o conjunto P dos números primos é infinito e enumerável.
Passo 1
Resumindo, queremos provar duas coisas: que o conjunto dos números primos
é infinito e que ele pode ser listado em sequência (isto é, é enumerável). Para isso, vamos usar o argumento clássico de Euclides para infinitude e, em seguida, construir explicitamente uma enumeração dos primos.
Passo 2
Suponha, por absurdo, que
seja finito, digamos
Considere o número
Note que
e, ao dividir
por qualquer
, o resto é
. Logo, nenhum dos
divide
. Mas todo inteiro maior que
tem algum divisor primo, então existe um primo
que divide
e, por consequência,
. Isso contradiz a hipótese de que
era finito. Portanto
é infinito.
Passo 3
Para mostrar que
é enumerável, vamos construí-la como uma sequência crescente. Defina
que é o menor primo.
Passo 4
Suponha definidos
. Considere o conjunto
Como já provamos que
é infinito, esse conjunto não está vazio. Defina
Assim obtemos uma sequência
de primos estritamente crescente.
Passo 5
A definição recursiva acima constrói uma função
que é bijetiva (cada primo aparece exatamente uma vez e não sobra nenhum). Logo
é enumerável.
Resposta
O conjunto dos números primos
é infinito e enumerável.