Le prédicat

Définition

Une proposition est un énoncé qui est vrai ou faux : « 7 est premier » est vrai, « 8 est premier » est faux.

Un prédicat n'a pas cette propriété. « $x$x est premier » n'est ni vrai ni faux : il dépend de $x$x. C'est un énoncé à trou, qui rend une valeur de vérité une fois le trou rempli.

Variable libre, variable liée

Tant que la variable reste libre, l'énoncé n'a pas de valeur de vérité. Deux opérations la ferment :

Une variable quantifiée est dite liée. Un énoncé sans variable libre est une proposition — il a une valeur de vérité, et une seule.

L'ordre des quantificateurs

Deux quantificateurs de nature différente ne commutent pas. Sur les entiers, avec $S(x, y)$S(x,y) pour « $y$y est plus grand que $x$x » :

$\forall x\, \exists y,\ S(x, y) \quad \text{est vrai}$∀x∃y, S(x,y)est vrai

$\exists y\, \forall x,\ S(x, y) \quad \text{est faux}$∃y∀x, S(x,y)est faux

Le premier dit : pour chaque entier, il en existe un plus grand — et le $y$y peut dépendre du $x$x. Le second dit : il existe un entier plus grand que tous — un plus grand entier, qui n'existe pas.

Les mêmes symboles, dans l'ordre inverse, énoncent une vérité et une fausseté. C'est le même mécanisme qui rend la définition de la limite non commutative.

Nier un énoncé quantifié

La négation traverse les quantificateurs en les échangeant :

$\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)

Nier « tous sont premiers » ne donne pas « aucun n'est premier », mais « il en existe un qui ne l'est pas ». Un seul contre-exemple suffit à réfuter un universel ; réfuter un existentiel demande de balayer tout le domaine.

Le domaine fait partie de l'énoncé

Un prédicat ne se juge que sur un domaine déclaré. « $\exists x,\ x^2 = 2$∃x, x2=2 » est faux sur $\mathbb{Q}$Q et vrai sur $\mathbb{R}$R : la formule n'a pas changé, l'univers si.

Omettre le domaine, c'est laisser l'énoncé indéterminé — non pas ambigu sur son sens, mais dépourvu de valeur de vérité.

Résumé

Un prédicat devient une proposition quand ses variables sont fixées ou quantifiées sur un domaine déclaré.