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.

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):
\forall n\in\mathbb{N},\;\exists p\in\mathbb{N}\;\bigl(\text{\(p\) é primo}\;\wedge\;p>n\bigr).é
Aqui tomamos \mathbb{N}=\{1,2,3,\dots\} e “ p é primo” significa que p>1 e seus únicos divisores positivos são 1 e p.

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:
\neg\bigl(\forall n \in \mathbb{N},\,\exists p \in \mathbb{N}\;(p\text{ é primo}\wedge p>n)\bigr)é \nequivale a
\exists N \in \mathbb{N} \quad \forall p \in \mathbb{N},\;\bigl(p\text{ é primo}\bigr)\;\Longrightarrow\;p \le N.é
Ou seja, existe um inteiro N tal que todo primo p satisfaz p \le N. Isto significa que há apenas um conjunto finito de primos: seja
\{p_1,p_2,\dots,p_k\}
a lista completa de todos os números primos.

Passo 4

Construa o número
Q = p_1\cdot p_2\cdots p_k + 1.
Observações:
1. Q > 1, logo Q tem pelo menos um divisor primo r.
2. Como r divide o produto p_1\cdots p_k, se r fosse igual a algum p_i teríamos r\mid\bigl(p_1\cdots p_k\bigr) e também r\mid Q. Então r dividiria a diferença
Q - (p_1\cdots p_k) = 1,
o que é impossível, pois nenhum primo divide 1.
Logo r não pode coincidir com nenhum dos p_i. Mas isso contradiz a hipótese de que \{p_1,\dots,p_k\} era a lista completa de primos.

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
\forall n\in\mathbb{N},\;\exists p\in\mathbb{N}\;\bigl(p\text{ é primo}\wedge p>n\bigr)é
é verdadeira, ou seja, existem infinitos números primos.

Resposta

\forall n\in\mathbb{N},\;\exists p\in\mathbb{N}\;\bigl(p\text{ é primo}\wedge p>n\bigr).é
Prova por contradição usando o número Q=p_1\cdots p_k+1, obtendo um primo novo, o que contradiz a finitude dos primos.

Exercícios relacionados