Quantificateurs et négation des propositions

Beaucoup d'énoncés mathématiques portent sur toute une collection d'objets, plutôt que sur un seul élément isolé. Pour cela, on utilise deux quantificateurs fondamentaux.

Le quantificateur universel, noté $\forall$, affirme qu'une propriété est vraie pour chaque élément d'un ensemble, sans aucune exception. Le quantificateur existentiel, noté $\exists$, affirme qu'au moins un élément vérifie la propriété : il n'exige ni unicité, ni universalité.

L'ordre des quantificateurs compte énormément, et c'est une source d'erreurs fréquente. L'énoncé $\forall x,\; \exists y,\; P(x, y)$ n'a pas le même sens que $\exists y,\; \forall x,\; P(x, y)$ : dans le premier cas, $y$ peut dépendre de $x$ ; dans le second, un seul et même $y$ doit convenir pour tous les $x$.

La négation d'une proposition quantifiée obéit à une règle précise, à mémoriser parfaitement :

$$\neg\bigl(\forall x,\; P(x)\bigr) \iff \exists x,\; \neg P(x)$$

$$\neg\bigl(\exists x,\; P(x)\bigr) \iff \forall x,\; \neg P(x)$$

Autrement dit, il suffit de trouver un seul contre-exemple pour réfuter entièrement un énoncé universel. Symétriquement, pour montrer qu'aucun élément ne vérifie une propriété, il faut la réfuter pour chacun d'eux, sans exception.

Cette règle s'applique aussi en cascade sur des quantificateurs multiples : on les inverse un par un, dans l'ordre d'apparition, en niant à chaque étape la propriété qui suit immédiatement :

$$\neg\bigl(\forall x,\; \exists y,\; P(x,y)\bigr) \iff \exists x,\; \neg\bigl(\exists y,\; P(x,y)\bigr) \iff \exists x,\; \forall y,\; \neg P(x,y)$$

C'est une compétence essentielle pour rédiger des démonstrations rigoureuses, en particulier lorsqu'il s'agit de démontrer qu'une propriété est fausse : on cherche alors précisément la proposition niée, puis on construit ou on exhibe l'objet qui la satisfait.