O predicado

Definição

Uma proposição é um enunciado que é verdadeiro ou falso: «7 é primo» é verdadeiro, «8 é primo» é falso.

Um predicado não tem essa propriedade. «$x$x é primo» não é nem verdadeiro nem falso: depende de $x$x. É um enunciado com um buraco, que devolve um valor de verdade uma vez preenchido o buraco.

Variável livre, variável ligada

Enquanto a variável permanecer livre, o enunciado não tem valor de verdade. Duas operações a fecham:

Uma variável quantificada diz-se ligada. Um enunciado sem variável livre é uma proposição — tem um valor de verdade, e um só.

A ordem dos quantificadores

Dois quantificadores de natureza diferente não comutam. Sobre os inteiros, com $S(x, y)$S(x,y) para «$y$y é maior que $x$x»:

$\forall x\, \exists y,\ S(x, y) \quad \text{é verdadeiro}$∀x∃y, S(x,y)eˊ verdadeiro

$\exists y\, \forall x,\ S(x, y) \quad \text{é falso}$∃y∀x, S(x,y)eˊ falso

O primeiro diz: para cada inteiro existe um maior — e o $y$y pode depender do $x$x. O segundo diz: existe um inteiro maior que todos — um maior inteiro, que não existe.

Os mesmos símbolos, em ordem inversa, enunciam uma verdade e uma falsidade. É o mesmo mecanismo que torna não comutativa a definição do limite.

Negar um enunciado quantificado

A negação atravessa os quantificadores trocando-os:

$\neg\,\forall x,\ P(x) \iff \exists x,\ \neg P(x)$¬∀x, P(x)⟺∃x, ¬P(x)

$\neg\,\exists x,\ P(x) \iff \forall x,\ \neg P(x)$¬∃x, P(x)⟺∀x, ¬P(x)

Negar «todos são primos» não dá «nenhum é primo», mas «existe um que não é». Um único contraexemplo refuta um universal; refutar um existencial exige varrer todo o domínio.

O domínio faz parte do enunciado

Um predicado só se julga sobre um domínio declarado. «$\exists x,\ x^2 = 2$∃x, x2=2» é falso sobre $\mathbb{Q}$Q e verdadeiro sobre $\mathbb{R}$R: a fórmula não mudou, o universo sim.

Omitir o domínio é deixar o enunciado indeterminado — não ambíguo quanto ao sentido, mas desprovido de valor de verdade.

Resumo

Um predicado torna-se proposição quando suas variáveis são fixadas ou quantificadas sobre um domínio declarado.