Quantificateur (logique)

Mathématiques

Cette déclaration est infiniment longue :

1 - 2 = 1 + 1, et 2 - 2 = 2 + 2, et 3 - 2 = 3 + 3, ..., et 100 - 2 = 100 + 100, et ..., etc.

C'est un problème pour les langues formelles, car une déclaration formelle doit être d'une longueur limitée. Ces problèmes peuvent être évités en utilisant une quantification universelle. On obtient ainsi la déclaration compacte suivante :

Pour chaque nombre naturel n, n - 2 = n + n.

De la même manière, nous pouvons raccourcir une séquence infinie de déclarations jointes par ou :

1 est égal à 5 + 5, ou 2 est égal à 5 + 5, ou 3 est égal à 5 + 5, ... ou 100 est égal à 5 + 5, ou ..., etc.

qui peut être réécrite en utilisant la quantification existentielle :

Pour au moins un nombre naturel n, n est égal à 5+5.

Notation

Les deux quantificateurs les plus utilisés sont le quantificateur universel et le quantificateur d'existence.

Le quantificateur universel est utilisé pour affirmer que pour les éléments d'un ensemble, les éléments correspondent tous à certains critères. Habituellement, cette déclaration "pour tous les éléments" est raccourcie en un "A" retourné, qui est "∀".

Le quantificateur existentiel est utilisé pour affirmer que pour les éléments d'un ensemble, il existe au moins un élément qui correspond à certains critères. Habituellement, cette déclaration "il existe un élément" est raccourcie par un "E" renversé, qui est "∃".

Nous pouvons réécrire un exemple de déclaration en anglais avec des symboles, des prédicats représentant des critères et des quantificateurs. L'exemple est "Chacun des amis de Peter aime soit danser, soit aller à la plage". Soit X l'ensemble de tous les amis de Peter. Soit P(x) le prédicat "x aime danser". Soit Q(x) le prédicat "x aime aller à la plage". Nous pouvons réécrire l'exemple en utilisant la notation formelle suivante : ∀ x ∈ X , P ( x ) ∨ Q ( x ) {\displaystyle \forall {x}{\in }X,P(x)\lor Q(x)} . La déclaration peut être lue comme suit : "pour chaque x qui est membre de X, P s'applique à x ou Q s'applique à x".

Il existe d'autres façons d'utiliser les quantificateurs dans le langage formel. Chacun des énoncés suivants dit la même chose que ∃ x ∈ X , P ( x ) {\displaystyle \existe {x}{\in }X,P(x)} :

• ∃ x P {\displaystyle \existe {x}P}
• ( ∃ x ) P {\displaystyle (\exists {x})P}
• ( ∃ x . P ) {\displaystyle (\exists x\ .\ P)}
• ∃ x ⋅ P {\displaystyle \existe x\ \cdot \ P}
• ( ∃ x : P ) {\displaystyle (\exists x:P)}
• ∃ x ∈ X P {\displaystyle \existe {x}{\in }X\,P}
• ∃ x : X P {\displaystyle \existe \,x{:}X\,P}

Il existe quelques autres façons de représenter le quantificateur universel :

• ( x ) P {\displaystyle (x)\,P}
• ⋀ x P {\displaystyle \bigwedge _{x}P}

Plusieurs déclarations ci-dessus incluent explicitement X, l'ensemble des éléments auxquels le quantificateur s'applique. Cet ensemble d'éléments est également connu sous le nom de gamme de quantification, ou l'univers du discours. Certaines des déclarations ci-dessus ne comprennent pas un tel ensemble. Dans ce cas, l'ensemble devra être spécifié avant la déclaration. Par exemple, "x est une pomme" doit être indiqué avant ∃ x P ( x ) {\displaystyle \exists {x}P(x)} . Dans ce cas, nous déclarons qu'au moins une pomme correspond au prédicat P.

L'utilisation de quantificateurs ne nécessite pas formellement l'utilisation du symbole x. Le symbole x a été utilisé tout au long de cet article, mais n'importe quel symbole peut être utilisé, comme y. Veillez à ne pas faire référence à deux choses différentes avec le même symbole lorsque vous choisissez des symboles.

Nesting

Il est important de mettre les quantificateurs dans le bon ordre. Voici un exemple de phrase anglaise montrant comment le sens change avec l'ordre :

Pour chaque nombre naturel n, il existe un nombre naturel s tel que s = n2.

Cette affirmation est vraie. Elle affirme que tout nombre naturel a un carré. Cependant, si nous inversons l'ordre des quantificateurs :

Il existe un nombre naturel s, tel que pour chaque nombre naturel n, s = n2.

Cette déclaration est fausse. Elle prétend qu'il existe un nombre naturel s qui est le carré de chaque nombre naturel.

Dans certaines circonstances, le fait de changer l'ordre des quantificateurs ne change pas le sens de la déclaration. Par exemple, le fait de changer l'ordre des quantificateurs ne change pas le sens de la déclaration :

Il existe un nombre naturel x, et il existe un nombre naturel y tel que x = y2.

Autres quantificateurs

Il existe également des quantificateurs moins courants utilisés par les mathématiciens.

Un exemple est le quantificateur de solution. Il est utilisé pour indiquer quels éléments résolvent une équation particulière. Le quantificateur de solution est représenté par un § (signe de section). Par exemple, l'énoncé suivant affirme que les carrés de 0, 1 et 2 sont plus petits que 4 : [ § n ∈ N n 2 ≤ 4 ] = { 0 , 1 , 2 } {\displaystyle \left[\S n\in \mathbb {N} \quad n^{2}\leq 4\right]=\left\{0,1,2\right\}

D'autres quantificateurs le sont :

• Il existe de nombreux éléments tels que...
• Il y a peu d'éléments tels que...
• Il existe une infinité d'éléments tels que...
• Pour tous les éléments, mais finiment nombreux... (parfois exprimé comme "pour presque tous les éléments...").
• Il existe d'innombrables éléments tels que...
• Pour tous les éléments, mais de façon non négligeable...

Histoire

La logique des termes a été développée par Aristote. Il s'agissait d'une forme précoce de logique, qui comprenait la quantification. L'utilisation de la quantification était plus proche de celle du langage naturel. Cela signifie que les énoncés en logique terminologique avec quantificateurs étaient moins adaptés à l'analyse formelle. La logique terminologique comprenait des quantificateurs pour Tous, Quelques-uns et Non (aucun) au 4ème siècle avant JC.

En 1879, Gottlob Frege a créé une notation pour la quantification universelle. Contrairement à aujourd'hui, il représenterait une quantification universelle en écrivant une variable sur une fossette, en ligne droite par ailleurs. Frege n'a pas créé de notation pour la quantification existentielle. Il a plutôt combiné la quantification universelle et un certain nombre de négations pour faire une déclaration équivalente. L'utilisation de la quantification par Frege n'était pas très connue avant les Principes de mathématiques de Bertrand Russell en 1903.

En 1885, Charles Sanders Peirce et son élève Oscar Howard Mitchell ont également créé une notation pour les quantificateurs universels et existentiels. Ils ont écrit _Πx et _Σx où nous écrivons maintenant ∀x et ∃x. La notation de Pierce a été utilisée par de nombreux mathématiciens jusque dans les années 1950.

En 1897, William Ernest Johnson et Giuseppe Peano ont créé une autre notation pour la quantification universelle et existentielle. Ils ont été influencés par la précédente notation de quantification de Pierce. Johnson et Peano ont utilisé le simple (x) pour la quantification universelle, et ∃x pour la quantification existentielle. L'influence de Peano sur les mathématiques a permis de diffuser cette notation dans toute l'Europe.

En 1935, Gerhard Gentzen a créé le symbole ∀ pour la quantification universelle. Il n'a été largement utilisé que dans les années 1960.

Pages connexes

• Logique