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 P é 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 P seja finito, digamos
P = p1, p2, dots, pn
Considere o número
N = p1 cdot p2 cdots pn + 1
Note que N>1 e, ao dividir N por qualquer pi, o resto é 1. Logo, nenhum dos pi divide N. Mas todo inteiro maior que 1 tem algum divisor primo, então existe um primo q que divide N e, por consequência, qnotinp1,dots,pn. Isso contradiz a hipótese de que P era finito. Portanto P é infinito.

Passo 3

Para mostrar que P é enumerável, vamos construí-la como uma sequência crescente. Defina
p1 = 2,
que é o menor primo.

Passo 4

Suponha definidos p1,p2,dots,pk. Considere o conjunto
,qinPmid q>pk
Como já provamos que P é infinito, esse conjunto não está vazio. Defina
pk+1 = min,qinPmid q>pk
Assim obtemos uma sequência (pk)k>=1 de primos estritamente crescente.

Passo 5

A definição recursiva acima constrói uma função
fcolon Nlongrightarrow P, f(k)=pk,
que é bijetiva (cada primo aparece exatamente uma vez e não sobra nenhum). Logo P é enumerável.

Resposta

O conjunto dos números primos P é infinito e enumerável.

Exercícios relacionados