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é pour-tout (symbole ∀), affirme qu'une propriété est vraie pour chaque élément d'un ensemble, sans aucune exception possible. Le quantificateur existentiel, noté il-existe (symbole ∃), affirme qu'au moins un élément de l'ensemble 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é « pour tout x, il existe y tel que... » n'a pas le même sens que « il existe y tel que, pour tout x... » : 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 sans exception. Confondre ces deux formulations est une erreur classique, souvent lourde de conséquences dans une démonstration.

La négation d'une proposition quantifiée obéit à une règle précise, que tu dois mémoriser parfaitement : nier « pour tout x, P(x) » revient à affirmer « il existe x tel que NON P(x) ». Autrement dit, il suffit de trouver un seul contre-exemple pour réfuter entièrement un énoncé universel. Symétriquement, nier « il existe x, P(x) » revient à affirmer « pour tout x, NON P(x) » : pour montrer qu'aucun élément ne vérifie une propriété, il faut la réfuter pour chacun d'entre eux, sans exception.

Cette règle de négation 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. 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 vraiment.

NON (pour-tout x, P(x))   <=>   il-existe x, NON P(x)
NON (il-existe x, P(x))   <=>   pour-tout x, NON P(x)

(exemple à deux quantificateurs)
NON (pour-tout x, il-existe y, P(x,y))
   <=> il-existe x, NON (il-existe y, P(x,y))
   <=> il-existe x, pour-tout y, NON P(x,y)