Enuncie precisamente cada proposição abaixo, incluindo quantificadores, domínio das variáveis e dê uma prova (completa) por contradição:
Prove que existem infinitos números primos.
Prove que existem infinitos números primos.
Passo 1
O enunciado pede para formular com precisão lógica (quantificadores e domínio) a proposição “existem infinitos números primos” e, em seguida, provar essa proposição por contradição. O conteúdo é teoria dos números elementar: definição de número primo e argumento clássico de Euclides.
Passo 2
Proposição a ser demonstrada (em linguagem de lógica de primeira ordem):
Aqui tomamos
e “
é primo” significa que
e seus únicos divisores positivos são
e
.
Passo 3
Iniciamos a prova por contradição. Suponha o contrário da proposição, isto é, suponha que não existam infinitos primos. Em termos lógicos:
Ou seja, existe um inteiro
tal que todo primo
satisfaz
. Isto significa que há apenas um conjunto finito de primos: seja
a lista completa de todos os números primos.
Passo 4
Construa o número
Observações:
.
, logo
tem pelo menos um divisor primo
.
. Como
divide o produto
, se
fosse igual a algum
teríamos
e também
. Então
dividiria a diferença
o que é impossível, pois nenhum primo divide
.
Logo não pode coincidir com nenhum dos
. Mas isso contradiz a hipótese de que
era a lista completa de primos.
Logo
Passo 5
Chegamos a uma contradição. Portanto a suposição inicial (de que há apenas finitos primos) é falsa. Concluímos que a proposição
é verdadeira, ou seja, existem infinitos números primos.
Resposta
Prova por contradição usando o número
, obtendo um primo novo, o que contradiz a finitude dos primos.