quantification - logic -
Un quantificateur porte sur une variable : l'universel affirme qu'une propriété vaut pour toutes les valeurs admises, tandis que l'existentiel affirme qu'elle vaut pour au moins une, et l'existence unique pour une seule. L'interprétation exige donc de fixer l'univers du discours. Lorsque plusieurs quantificateurs se succèdent, leur ordre peut changer le sens de la proposition.
Contents
What you will learn
- Lire les symboles ∀, ∃ et ∃! sans ambiguïté.
- Distinguer preuve universelle, contre-exemple et témoin existentiel.
- Repérer l'effet de l'univers du discours, de la portée et de l'ordre des quantificateurs.
In plain terms
Prenons trois cartes numérotées 1, 2 et 3. Dire « chaque carte porte un nombre inférieur à 4 » oblige à vérifier les trois cartes. Dire « une carte porte un nombre pair » demande seulement d'en trouver une : la carte 2 suffit.
La quantification logique distingue précisément ces deux exigences. « Pour tout » affirme qu'une propriété vaut pour chaque valeur autorisée ; « il existe » affirme qu'au moins une valeur la vérifie. Les valeurs autorisées forment l'univers du discours, qu'il faut connaître avant de juger la phrase.
Definition
La quantification logique transforme une propriété dépendant d'une variable en proposition susceptible d'être vraie ou fausse. On fixe d'abord un univers du discours, noté U, qui rassemble les valeurs admises. On note ensuite P(x) la propriété examinée pour une valeur x de cet univers.
Le quantificateur universel, lu « pour tout », exige que P(x) soit vraie pour chaque x de U : . Le quantificateur existentiel, lu « il existe », exige au moins un témoin dans U : . L'écriture « il existe un unique », symbolisée par , ajoute que ce témoin est le seul.
Avec plusieurs variables, chaque quantificateur lie la variable placée dans sa portée. L'ordre fait partie de l'énoncé : affirmer que chaque x possède un y adapté ne signifie pas qu'un même y convient à tous les x. Les symboles ∃ et ∀ sont respectivement attribués à Peano en 1897 et à Gerhard Gentzen en 1935.
A step-by-step example
L'univers U contient exactement les entiers 1, 2 et 3. Deux propriétés sont testées : P(x) signifie « x est inférieur à 4 » et Q(x) signifie « x est pair ». La figure matérialise les vérifications et le témoin retenu.
1. Pour la propriété P, on vérifie successivement 1 < 4, 2 < 4 et 3 < 4. Les trois comparaisons sont vraies.
2. Le quantificateur universel est donc satisfait : . Aucun élément de U ne fournit de contre-exemple.
3. Pour la propriété Q, le nombre 2 est pair. Ce seul témoin suffit à valider .
4. Le contrôle consiste à relire l'univers. Les nombres 1 et 3 ne sont pas pairs : 2 est donc non seulement un témoin, mais l'unique témoin dans U. L'unicité disparaîtrait si l'univers contenait aussi 4.
In practice
Pour établir une affirmation universelle sur un ensemble fini, on contrôle chaque valeur. Pour la réfuter, une autre stratégie suffit : chercher un seul contre-exemple. Dans U = {1, 2, 3}, aucune valeur ne contredit « x < 4 ».
Pour établir une affirmation existentielle, on présente un témoin et on vérifie la propriété annoncée. Énumérer tout l'univers est inutile dès qu'un témoin est trouvé. Pour réfuter l'affirmation, il faut au contraire exclure chaque valeur possible.
Avant toute vérification, on écrit l'univers et on repère la portée de chaque quantificateur. Cette lecture évite de traiter comme identiques deux phrases qui emploient les mêmes variables dans un ordre différent.
Not to be confused with
Quantificateur et connecteur logique. Un quantificateur porte sur les valeurs d'une variable ; un connecteur relie des propositions. Dans « pour tout x, P(x) et Q(x) », « pour tout » quantifie x tandis que « et » relie P(x) à Q(x).
Variable liée et variable libre. Une occurrence est liée lorsqu'elle se trouve dans la portée d'un quantificateur qui nomme cette variable. Dans « il existe x tel que P(x, y) », x est liée, mais y reste libre si aucun autre quantificateur ne porte sur elle.
Limits and pitfalls
Univers omis. Le symptôme est une phrase dont la vérité change selon les valeurs admises. « Il existe un nombre pair supérieur à 3 » est fausse dans {1, 2, 3}, mais vraie dans {1, 2, 3, 4}. Il faut donc fixer l'univers avant de conclure.
Quantificateurs permutés. Sur les entiers, « pour tout x, il existe y supérieur à x » est vraie, car y peut dépendre de x. « Il existe y tel que, pour tout x, y soit supérieur à x » est fausse : aucun entier ne dépasse tous les entiers. Il faut conserver l'ordre et identifier les dépendances.
Portée ambiguë. Si la ponctuation ou les parenthèses ne montrent pas jusqu'où agit un quantificateur, une même ligne peut recevoir plusieurs lectures. Il faut délimiter explicitement la proposition quantifiée avant d'en chercher la valeur de vérité.
Univers vide. Les présentations usuelles de la logique du premier ordre imposent un univers non vide. Dans un cadre qui autorise l'ensemble vide, une affirmation universelle y est vraie sans témoin, tandis qu'une affirmation existentielle y est fausse. La convention du cadre doit être annoncée.
Further reading
L'article Giuseppe Peano et le formalisme replace l'introduction du symbole existentiel dans le développement du langage mathématique formel.
La note de lecture La théorie des ensembles pour tous prolonge la réflexion sur les ensembles qui peuvent servir d'univers du discours.
Explore mathematics differently
Discover our magazines, podcasts and games to explore mathematics differently.
See our offers