PETIT PRÉCIS DE LOGIQUE ÉLÉMENTAIRE

Henri Cohen

J’ai pour but ici de rappeler un certain nombre de notions de logique qui doivent, non pas être seulement assimilées par un élève de Licence de Mathématiques, mais totalement absorbées au point que cela devienne un réflexe. Plus peut-être qu’un cours, il ne serait pas inutile de s’imprégner totalement pendant plusieurs jours de ce qui suit, en l’appliquant à des exemples concrets, et d’y revenir par la suite.

Tout d’abord une mise en garde. Il est inutile et même tout à fait néfaste d’écrire quelque chose que vous ne comprenez pas. Ce n’est pas des maths, ce n’est pas du français, ca ne sert à rien, et vous ne trompez pas le prof. Alors ne vous trompez pas vous-même!

1. Les opérateurs logiques et la langue française.

Les mots suivants sont couramment utilisés en mathématiques pour décrire une démonstration : “ou”, “et”, “donc”, “implique”, “alors”, “équivaut”, “si et seulement si”, “condition nécessaire”, “condition suffisante”, “réciproquement”, “il existe”, “quel que soit”, etc...

Il faut absolument apprendre à se servir correctement de ces notions. En particulier, il faut comprendre que ces notions ont un sens mathématique parfaitement précis, qui n’est pas toujours le sens de la langue parlée courante. Puisque ce sont des objets mathématiques, ils obéissent à des axiomes qu’il faut se graver dans l’esprit. Il est absolument indispensable d’oublier que ces mots ont une signification dans la langue courante, et de s’imprégner de leur sens mathématique.

La signification précise des mots utilisés est une convention, à accepter sans discuter comme n’importe quelle règle du jeu. La raison pour laquelle il a été nécéssaire historiquement de changer légèrement la signification des mots du langage courant, est que celui-ci n’est pas assez précis. Il a donc été indispensable de “rigidifier” leur signification en mathématiques.

Outre l’explication de ces mots, voir aussi à la fin l’interprétation ensembliste des symboles logiques.

1.1. Le “ou” mathématique.

C’est une source de confusion. En effet, lorsque qu’en maths on dit que “P ou Q” est vraie (où P et Q sont deux affirmations), cela signifie que soit P, soit Q est vraie, et peut-être aussi les deux à la fois. Ce n’est pas un “ou exclusif”, qui exclut le cas où P et Q seraient toutes deux vraies, alors que dans la langue courante c’est plutôt ce dernier sens qui prévaut. En d’autres termes “P ou Q” signifie que ou bien P est vraie et Q est fausse, ou bien Q est vraie et P est fausse, ou bien P et Q sont toutes deux vraies.

Exercice : Soit x ∈ ℝ. Est-il vrai que x > 0 ou x < 1 ?

1.2. Le “et” mathématique.

Ceci pose en général moins de problèmes puisqu’en accord avec le langage. On dit que “P et Q” est vraie si la propriété P est vraie et la propriété Q est vraie.

Une petite difficulté apparait si on veut dire que “P et Q” n’est pas vraie. Si on regarde la définition, ceci signifie que P est fausse ou Q est fausse, avec le sens mathématique du “ou” ci-dessus.

En notant “\overline{P} ” la négation logique de P (\overline{P} se lit “non P ”) on a l’identité logique

(\overline{P et Q}) = (\overline{P} ou \overline{Q}) .

Si l’on y réfléchit, on a d’ailleurs l’identité symétrique

(\overline{P ou Q}) = (\overline{P} et \overline{Q}) .

En effet, ceci signifie que pour que “P ou Q” soit fausse, il faut et il suffit que P soit fausse et que Q soit fausse. Relisez la phrase précédente et regardez à quel point le langage courant nous conduit à des imprécisions : j’ai bien mis pour que “P ou Q” soit fausse entre guillemets. Si j’avais omis les guillemets, cela aurait signifié pour que P ou Q soit fausse, c’est à dire P fausse OU Q fausse alors qu’en fait c’est ET. Cette ambiguité disparait dans la formulation logique puisque le recouvre toute l’affirmation “P ou Q”, ce qui joue un peu le rôle des guillemets.

Les trois choses essentielles à retenir des paragraphes 1.1. et 1.2 sont, d’une part le fait que le “ou” mathématique est un ou inclusif, et donc différent de la langue courante, et d’autre part les deux formules logiques de négation du “ou” et du “et”.

Exercice : quelle est la négation de “x > 0 et x ≤ 1” ? Décrire le sous-ensemble de ℝ correspondant.

Exercice : quelle est la négation de “x > 2 ou x ≤ 1” ? Décrire le sous-ensemble de ℝ correspondant.

1.3. Le “non” mathématique

Il n’y a ici que peu de risque de confusion. Lorsque l’on dit que \overline{P} est vraie, cela signifie que P est fausse et réciproquement, ce qui est assez en accord avec le langage courant. La seule formule logique ou le “non” intervient seul (nous avons déjà vu qu’il intervenait beaucoup en compagnie de “et” et de “ou”) est

\overline{\overline{P}} = P

ce qui signifie que la négation de la négation d’une affirmation P est P elle-même. Cela peut sembler une banalité, mais c’est le principe du “tiers exclu” (une affirmation est soit vraie soit fausse), qui est parfois refusé par certains philosophes et même de rares mathématiciens. C’est aussi implicitement la base du raisonnement par l’absurde.

1.4. Les mots “implique”, “alors”, “donc”, etc....

Si je vous demandais la définition de “P implique Q” (ou “P ⟹ Q” en écriture logique), il y a de bonnes chances que vous me répondiez que “P ⟹ Q” est vraie si P est vraie et Q est vraie, ou même que vous me disiez (ce qui est tout à fait compréhensible vu l’utilisation dans le langage courant) que c’est une primitive de l’esprit humain, comme “ou” et “et”.

Tout ceci est erroné : “P ⟹ Q” a une signification bien précise. En termes logiques on a

(P ⟹ Q) = (\overline{P} ou Q) = (\overline{P et \overline{Q}}) .

Avant de discuter de ceci, noter que la deuxième égalité provient de l’action de la négation sur le “ou” décrite au paragraphe précédent.

La première égalité logique signifie dans le langage courant que “P implique Q” est vraie soit si P est fausse, soit si Q est vraie (soit les deux, comme d’habitude : le “soit” est ici un synonyme de “ou”). Cela peut sembler bizarre que quelque chose de faux puisse impliquer quelque chose de vrai, mais il en est ainsi.

La deuxième égalité logique rend ceci plus aisé à comprendre : elle dit en langage courant que “P implique Q” est fausse seulement quand P est vraie et Q est fausse, ce qui est bien en accord avec l’intuition : une propriété vraie ne peut pas impliquer une propriété fausse.

L’oubli du fait que “P implique Q” soit vraie aussi quand P est fausse conduit a une erreur fréquente qu’il faut éviter à tout prix : celle de confondre “P implique Q” avec “P et Q”. Effectivement, si l’on acceptait pas qu’une propriété fausse puisse entrainer une propriété vraie, cette confusion serait légitime. Relisez bien ceci pour ne pas faire cette erreur.

En utilisant uniquement la première égalité logique on obtient

(\overline{Q} ⟹ \overline{P}) = (Q ou \overline{P}) = (\overline{P} ou Q) = (P ⟹ Q)

et donc la propriété “\overline{Q} ⟹ \overline{P} ” équivaut à “P ⟹ Q”. C’est ce que l’on désigne sous le nom de “contraposée”. Vous voyez qu’en termes de logique cela se démontre de manière élégante.

Exercice : quel est la négation de “P ⟹ \overline{Q}” ?

Venons en maintenant à d’autres expressions souvent utilisées dans un sens semblable.

Quand on écrit “Puisque P on a Q” on veut dire “P implique Q”. Ceci est à nouveau différent du langage courant : en effet, l’expression “Puisque P ” sousentend que P est vraie. Or en maths rien n’est moins sûr. Par exemple on peut être au milieu d’une démonstration par l’absurde, où on veut démontrer que P est fausse, donc on suppose que P est vraie, mais ce n’est pas nécessairement le cas.

Vous pouvez donc utiliser cette expression en toute confiance, à condition de vous rappeller qu’elle ne signifie PAS que P est vraie, mais simplement que P ⟹ Q.

De la même manière, les expressions “Si P alors Q”, “De P on déduit que Q”, “P donc Q” sont synonymes de “P implique Q”.

Quand on écrit “P est une condition nécessaire pour que Q” signifie que “Q implique P ” (et PAS le contraire, réfléchissez!).

De même quand on écrit “P est une condition suffisante pour que Q”, cela signifie que “P implique Q”.

Résumé : 1) Le syllogisme, dit encore modus ponens : si “P implique Q” est vraie et si P est vraie, alors Q est vraie. C’est la base du raisonnement mathématique.

2) Si “P implique Q” est fausse, alors P est vraie et Q est fausse.

3) Si P est fausse, alors “P implique Q” est toujours vraie.

1.5. Les expressions “équivaut”, “si et seulement si”, “CNS”, ...

C’est nettement plus simple. On dit que “P est équivalent à Q” si “P implique Q et Q implique P ”. En termes logiques,

(P ⟺ Q) = ((P ⟹ Q) et (Q ⟹ P)) .

Exercice : en remplacant les signes ⟹ par leurs expressions en termes de , “ou” et “et”, donner d’autres expressions pour “P ⟺ Q”.

En langage courant, “P ⟺ Q” est vraie si P et Q sont soit toutes deux vraies, soit toutes deux fausses.

Exercice : remettre en symboles logiques la phrase ci-dessus et retrouver ainsi les résultats de l’exercice précédent.

Les étudiants sont très forts pour le raisonnement par équivalence, justement parce que celui-ci est simple et peut être remonté dans l’autre sens. Toutefois il faut prendre garde à ne pas en abuser, car très souvent par paresse on écrit dans une suite d’équivalences “P ⟺ Q” alors que l’on a seulement vérifié que P ⟹ Q et pas l’implication réciproque, ce qui conduit bien sûr à des conclusions fausses.

Expressions synonymes de “P équivaut à Q” :

“P si et seulement si Q”, “P est une condition nécéssaire et suffisante (CNS en abrégé) pour Q”.

Enfin, lorsqu’on démontre que “P équivaut à Q”, on montre d’abord par exemple que “P implique Q”. Puis, l’on aborde la deuxième partie de la démonstration en écrivant “Réciproquement, montrons que Q implique P.” C’est l’utilisation normale du mot “réciproquement”.

2. Les opérateurs ∃, ∀ et la langue française.

Nous abordons maintenant un domaine au moins aussi important que le précédent, mais qui est parsemé de beaucoup plus d’embûches : l’emploi correct de “il existe” (symbole ∃) et “pour tout” (symbole “ ∀”). Je ne peux qu’insister à nouveau sur la nécessité de lire et relire ce paragraphe jusqu’à ce qu’aucune erreur ne soit plus possible.

2.1. Variables muettes et variables non muettes

Jusqu’à présent, le type de logique que nous avons considéré est fort simple (bien qu’il soit indispensable de faire attention à la signification précise des mots). C’est ce qu’on appelle le “calcul propositionnel”. En effet, ce que j’ai constamment appelé “affirmation” s’appelle en fait dans le langage des logiciens une “proposition”. La simplicité de ce que nous avons vu tient au fait que nous n’avons pas utilisé de variables. Rappelez vous vos premières frayeurs quand, après avoir bien assimilé les règles opératoires sur les nombres (3·4 = 12), on vous a introduit des “variables” et écrit des choses comme z = x · y ou (x + y)^{2} = x^{2} + 2xy + y^{2}. C’est à la fois un outil puissant et indispensable, mais qu’il faut aussi apprendre à manipuler correctement. Il en va de même en logique.

La première chose, indispensable, à comprendre est la notion de variable muette. Vous connaissez déjà ceci sans peut-être vous en rendre compte. Quand vous écrivez

I = ∫_{0}^{1} x^{2} dx

le nom de la variable x n’a pas d’existence propre. On pourrait tout aussi bien écrire

I = ∫_{0}^{1} y^{2} dy

ou même

I = ∫_{0}^{1} ♡^{2} d♡ !

Considérons l’exemple suivant.

J = ∫_{0}^{1}(x + t)^{2} dx .

Ici, x est toujours une variable muette (c’est la variable d’intégration), mais t n’est pas une variable muette. En particulier, il est illégal de changer t en y (par exemple), et il est tout aussi illégal de changer x en t (il faut utiliser des symboles différents pour les variables muettes et non muettes). En fait, il serait plus correct d’écrire la formule ci-dessus sous la forme

J(t) = ∫_{0}^{1}(x + t)^{2} dx

pour bien marquer le fait que t est une variable non muette. De la même manière, dans la formule

K(x) = ∫_{0}^{x} t^{2} dt

la variable t est muette, et la variable x ne l’est pas, ce qui explique que nous notons ceci K(x) et pas seulement K.

Revenons à la logique. On n’y utilise essentiellement que deux symboles ayant un rapport avec les variables : le symbole ∃ et le symbole ∀, que nous examinerons en détail dans les paragraphes suivants. Notons dès à présent la chose suivante. Lorsqu’on écrit

∃x P (x),  ou encore  ∀x P (x) ,

la variable x utilisée est une variable muette. Par exemple, de manière analogue à l’exemple de l’intégrale ci-dessus, on a les égalités logiques

∃x P (x) = ∃y P (y) = ∃♡ P (♡)

et de même avec ∀. Bien sûr l’affirmation P peut dépendre de plus d’une variable, et dans ce cas, comme pour l’intégrale, le ∃ ou le ∀ rend muette sa propre variable, mais laisse les autres non muettes. Par exemple dans ∃x P (x, y), x est une variable muette et y une variable non muette. Dans

∀x ∃y P (x, y, z)

les variables x et y sont toutes deux muettes, et z ne l’est pas.

En dehors de la distinction, essentielle, entre variables muettes ou non, un autre piège dans lequel il ne faut pas tomber est le suivant. Dans toute affirmation utilisant ∃ ou ∀, il faut utiliser un nom de variable qui est un symbole unique et PAS une formule (ce symbole devenant bien sûr une variable muette). Par exemple il est absolument interdit d’écrire

∃x + y P (x + y)

car x + y n’est pas un symbole unique, c’est une expression. Symbole unique ne signifie pas forcément que la variable s’écrive avec un seul caractère. Il est tout à fait légal d’écrire

∀x_{1} P (x_{1}) ,

ou même

∃toto P (toto)

(bien que l’on évite ce dernier type de nom en général).

Vous reconnaitrez certainement que la règle que je viens d’énoncer est la même que celle utilisée pour l’affectation à une variable en informatique. On peut écrire x := 3 + 4 mais certainement pas x + y := 3 + 4.

Une dernière mise en garde à propos de l’utilisation de noms de variables ayant plusieurs caractères. Le nom x_{1} est sans ambiguité, et toto aussi, bien que très lourd. Par contre, il est fortement déconseillé (lire : absolument interdit, bien que non illégal) d’utiliser un nom tel que xy. En effet cela prêterait trop à confusion avec le produit des variables x et y, qu’une autre convention conduit à écrire sans symbole opératoire (on pourrait écrire x · y pour distinguer le produit de x par y de la variable xy, mais ce serait quand même beaucoup trop dangereux).

2.2. Portée de ∀ et ∃

Une remarque importante doit d’abord être faite. Dire que pour toute valeur de x l’affirmation P (x) est vraie est un énoncé beaucoup trop vaste. En effet, ceci signifierait que x peut prendre comme valeur n’importe quel objet mathématique, donc être aussi bien un nombre réel, une matrice, un espace vectoriel, une fonction ou n’importe quoi d’autre. Ce n’est jamais ce qu’on veut dire quand on écrit ∀x P (x).

Prenons un exemple. Si j’écris

∀x (x^{2} + 1 ≠ 0) ,

à priori ceci vous parait vrai. En y réfléchissant a deux fois, ceci n’est vrai que si l’on restreint par exemple x aux nombres réels ou à ses sous-ensembles. C’est faux sur les complexes. Ce que l’on veut donc dire par l’affirmation ci-dessus est

∀x (x ∈ ℝ ⟹ x^{2} + 1 ≠ 0)

ce qu’on abrège en

∀x ∈ ℝ (x^{2} + 1 ≠ 0) .

Cette affirmation est effectivement vraie. Rien ne m’empêche d’écrire

∀x ∈ ℂ (x^{2} + 1 ≠ 0) ,

et cette affirmation est fausse.

On voit donc qu’il n’existe pas un unique symbole ∀, mais en fait un par ensemble : le symbole véritablement utile est ∀x ∈ E pour un certain ensemble E. Noter que c’est la variable x (et non la variable E) qui est muette.

Bien sûr tout ceci est également vrai pour le symbole ∃ : on écrit

∃x ∈ E .

Les symboles ∀ (ou ∀x ∈ E) et ∃ (ou ∃x ∈ E) s’appellent des quantificateurs.

Exercice : écrire avec des quantificateurs, et en précisant bien l’ensemble E de référence, “un carré est toujours positif”.

Exercice : montrer que ∀x ∈ ∅ P (x) est une affirmation vraie (quelle que soit la porposition P (x)), et que ∃x ∈ ∅ P (x) est une affirmation fausse.

2.3. Le symbole ∀ et “quel que soit”

Une fois l’obstacle de la compréhension de la notion de variable muette levé, la signification d’une expression du type

∀x P (x)

(que l’on lit “quel que soit x, P (x)”) ou de ∀x ∈ E P (x) est assez bien comprise en général.

Elle signifie que pour toute valeur donnée à x, l’affirmation P (x) est vraie. Si x_{1}, …, sont les valeurs que peuvent prendre x, cela équivaut à une espèce d’expression logique infinie

P (x_{1}) et P (x_{2}) et ⋯

Ceci n’est mis que pour la compréhension, mais ce type de symbolisme infini n’est PAS accepté en logique, c’est justement la raison d’être des symboles ∀ et ∃.

Le problème principal qui se pose n’est pas au niveau de la compréhension mais de la rédaction. Il est trop fréquent de voir des raisonnements mathématiques peut-être corrects être complètement détruits à la base par la quasi-inexistence de quantificateurs ou de leurs équivalents en français. Personne ne vous en voudra, bien au contraire, si vous écrivez “Pour tout x appartenant à E on a P (x)” plutôt que ∀x ∈ E P (x). Ce qui est grave c’est de ne rien mettre du tout et d’écrire “P (x)” ou “on a P (x)”. Ca veut dire quoi ? que pour tout x, P (x) est vraie ? alors dites-le. Ou bien peut-être qu’il existe un x tel que P (x) soit vraie ? à nouveau dites le.

Regardez par exemple l’affirmation ci-dessus sans quantificateurs :

x^{2} + 1 ≠ 0 .

Ceci vous parait-il correct ? A ce stade, j’espère bien que non. On ne sait pas si l’on veut dire ∀x x^{2} + 1 ≠ 0 ou autre chose. Tout ce qui prête à confusion est à proscrire.

2.4. Le symbole ∃ et “il existe”

Comme vous le savez, l’expression ∃x P (x) se lit “il existe x, P (x)”. Elle signifie qu’il existe une valeur de x telle que l’affirmation P (x) soit vraie. Si x_{1}, …, sont les valeurs que peuvent prendre x, cela équivaut à une espèce d’expression logique infinie

P (x_{1}) ou P (x_{2}) ou ⋯

ou je n’écris à nouveau ceci que pour l’intuition. Comme pour ∀, on a toujours un ensemble de référence E et on écrit plutôt habituellement ∃x ∈ E, P (x).

Comme il a déjà longuement été expliqué, la variable x dans une telle expression est muette, et donc on a l’égalité logique

( ∃x ∈ E P (x)) = ( ∃y ∈ E P (y)) .

Le piège majeur du quantificateur ∃ est de transformer la variable muette en une variable non muette. Considérons le bout de raisonnement suivant :

∃x ∈ ℝ x^{2} = 3. On a donc (x + 1)^{2} = x^{2} + 2x + 1 = 4 + 2x, d’où...

ou en français :

Il existe x appartenant à ℝ tel que x^{2} = 3. On a donc (x + 1)^{2} =...

Ceci vous paraît-il correct ? Réflechissez un peu avant de passer à la suite. Demandez-vous surtout si vous écrivez comme cela.

Il est clair que si je pose la question c’est qu’il y a un problème, et effectivement la plupart des étudiants écrivent comme cela. Malheureusement, cela prête tellement à confusion que l’on peut considérer cela comme une erreur.

En effet, lorsque vous écrivez ∃x ∈ ℝ..., vous avez immédiatement transformé x en une variable muette. Or quand vous écrivez après une expression telle que (x + 1)^{2}, x n’est plus muette, d’où source d’erreurs.

La rédaction correcte du bout de raisonnement ci-dessus est un peu plus longue, mais c’est la seule qui évite de tomber dans les pièges :

∃x ∈ ℝ x^{2} = 3. Soit donc a un élément de ℝ tel que a^{2} = 3 (ou plus brièvement “soit donc a un tel x”). On a donc (a + 1)^{2} = a^{2} + 2a + 1 = 4 + 2a, d’où...

L’utilisation d’une autre variable a qui n’est pas muette sauve la situation. Observez également le rôle important joué par le verbe “soit”.

Il est également fortement déconseillé d’utiliser une variable non muette comme variable muette. Peu de gens écriraient ∃π ∈ ℝ, π^{2} = 3 car π est implicitement utilisé comme variable non muette lorsque l’on travaille sur ℝ. L’écriture ci-dessus serait par contre tout à fait acceptable dans un contexte où les réels n’interviennent essentiellement pas. Par exemple, si R est un anneau et 𝔭 un idéal, vous pouvez tout à fait écrire

𝔭 principal ⟺ ∃π ∈ R, 𝔭 = πR

car il est clair d’après le contexte que le π dont on parle n’est pas 3.14....

Comme autre exemple, il ne faut pas écrire ∃i ∈ ℂ, i^{2} = 3 bien que cela soit parfaitement légal. En effet, d’après le contexte, la variable i est implicitement comprise comme une racine carrée de −1, et est donc une variable non muette, alors que le ∃i la rend muette. Par contre, il est raisonnable d’écrire ∃i ∈ ℤ, i(i+1)/2 = 3.

On peut résumer ce qui précède comme suit :

a) Toujours expliciter les quantificateurs.

b) Ne jamais utiliser le même nom de variable pour une variable muette et non muette. En particulier, dans le cas de ∃, prendre la peine d’introduire une autre variable comme dans l’exemple ci-dessus.

c) Dépendant du contexte, ne pas utiliser des variables telles que π, i, etc...

2.5 Ordre d’écriture des quantificateurs

Une autre erreur commune d’utilisation des identificateurs concerne leur placement, soit dans l’énoncé mathématique, soit dans la phrase française correspondante. Considérons l’affirmation suivante :

x^{2} ≥ 0, ∀x ∈ ℝ .

Cette affirmation peut sembler raisonnable, et pourtant elle viole un certain nombre de règles d’utilisation des quantificateurs. En mathématiques, les énoncés se lisent de gauche à droite. Donc on commence par lire “x^{2} ≥ 0”. La variable x n’est PAS précédée d’un quantificateur ou d’un autre symbole la rendant muette, et donc ce n’est pas une variable muette. Par contre, le ∀x ∈ ℝ donne à x le statut de variable muette, et nous avons vu qu’il est interdit d’utiliser un même nom de variable pour une variable muette et non muette. On pourrait donc écrire x^{2} ≥ 0, ∀y ∈ ℝ pour éviter cela, mais il devient encore plus clair avec ceci que cela ne veut rien dire. L’énoncé ci-dessus est donc incorrect. La règle absolue qui ne souffre aucune exception est qu’il faut placer les quantificateurs AVANT l’énoncé correspondant (cela vaut aussi bien pour ∃ que pour ∀). L’affirmation ci-dessus doit donc s’écrire

∀x ∈ ℝ, x^{2} ≥ 0 .

Exercice : est-il correct (d’un point de vue syntaxique) d’écrire ∀x ∈ ℂ, x^{2} +1 ≠ 0 ? L’affirmation est elle vraie ?

Une fois que vous vous êtes bien convaincus que les quantificateurs doivent se placer avant les propositions à quantifier (ce qui est contraire au langage courant qui permet de dire “il a fait beau tous les jours de cette semaine” alors que mathématiquement il faudrait dire “tous les jours de cette semaine il a fait beau”), il faut également remarquer que les quantificateurs ∀ et ∃ ne commutent pas. Par contre, les quantificateurs ∀ commutent entre eux, et de même les quantificateurs ∃ commutent entre eux.

Voyons quelques exemples. L’affirmation

∀x ∈ ℝ ∀y ∈ ℝ, x^{2} + y^{2} ≥ 0

est équivalente à

∀y ∈ ℝ ∀x ∈ ℝ, x^{2} + y^{2} ≥ 0

(commutation des ∀).

De manière analogue, l’affirmation

∃x ∈ ℤ ∃y ∈ ℤ, x^{2} + y^{2} = 34

est équivalente à

∃x ∈ ℤ ∃y ∈ ℤ, x^{2} + y^{2} = 34

(commutation des ∃). Noter que pour ces exemples j’ai donné des affirmations vraies, mais l’équivalence des énoncés est indépendant de leur véracité. En d’autres termes, ils sont soit vrais tous les deux, soit faux tous les deux.

Par contre, et c’est l’un des pièges principaux à éviter, les affirmations

∀x ∈ ℂ ∃y ∈ ℂ, x^{2} + y^{2} ≠ 0

∃y ∈ ℂ ∀x ∈ ℂ, x^{2} + y^{2} ≠ 0

ne sont PAS équivalentes à priori, puisque les quantificateurs ∀ et ∃ ne commutent pas. Et de fait, la première affirmation est vraie, et la deuxième est fausse (Exercice : démontrez le). J’utilise à dessein les mots “à priori” car les affirmations sont parfois équivalentes. Par exemple (exercice), montrer que si on remplace ℂ par ℝ, les deux affirmations sont vraies, et donc équivalentes.

La non commutativité de ∀ et ∃ est une raison supplémentaire de placer les quantificateurs avant la proposition à quantifier.

Un exemple particulièrement spectaculaire de la non commutativité des quantificateurs concerne la définition de la convergence uniforme d’une suite de fonctions (à ne lire que par les étudiants ayant cette notion au programme). L’écriture en termes de quantificateurs de l’affirmation “la suite de fonctions f_{n}(x) converge sur E vers la fonction f(x)” est la suivante :

∀ε > 0 ∀x ∈ E ∃N ∈ ℕ ∀n ≥ N, |f_{n}(x) − f(x)| < ε .

Bien entendu les deux premiers quantificateurs, et eux seulement, peuvent être permutés puisque ce sont tous deux des quantificateurs ∀. (Si je voulais couper les cheveux en quatre, je dirais que l’énoncé ci-dessus n’est pas assez précis : il est sous-entendu que ε ∈ ℝ et que n est un entier positif.)

Par ailleurs, l’écriture en termes de quantificateurs de l’affirmation “la suite de fonctions f_{n}(x) converge uniformément sur E vers la fonction f(x)” est la suivante :

∀ε > 0 ∃N ∈ ℕ ∀x ∈ E ∀n ≥ N, |f_{n}(x) − f(x)| < ε .

On voit que, en échangeant les quantificateurs ∀x ∈ E avec ∃N ∈ N, on obtient une notion différente.

Exercice : soit P (x, y) une proposition qui dépend de deux variables x et y. Montrer que, bien que l’on ait pas commutativité des quantificateurs, on a quand même l’implication

∃y ∀x P (x, y) ⟹ ∀x ∃y P (x, y) .

Notons enfin le comportement les quantificateurs par négation. On a

\overline{∀x ∈ E, P (x)} = ∃x ∈ E, \overline{P (x)}

et symétriquement

\overline{∃x ∈ E, P (x)} = ∀x ∈ E, \overline{P (x)} .

Par exemple, l’affirmation “la suite de fonctions f_{n}(x) ne converge pas uniformément sur E vers la fonction f(x)” est la suivante :

∃ε > 0 ∀N ∈ ℕ ∃x ∈ E ∃n ≥ N, |f_{n}(x) − f(x)| ≥ ε .

Noter que l’on échange les ∀ et ∃, et que l’on prend la négation de l’affirmation principale, mais qu’on ne touche pas aux ensembles de définition, qui sont respectivement ε ∈ {x ∈ ℝ, x > 0}, N ∈ ℕ, x ∈ E et n ∈ {x ∈ ℕ, x ≥ N}. En effet, puisque ∀x ∈ E, P (x) est une abbréviation de ∀x, x ∈ E ⟹ P (x), les règles de négation de l’implication vues ci-dessus nous disent que

( \overline{∀x ∈ E, P (x)}) = ( ∃x, x ∈ E et \overline{P (x)}) = ( ∃x ∈ E, \overline{P (x)}) .

De même pour ∃.

On peut résumer ce qui précède comme suit :

a) Toujours placer les quantificateurs avant la proposition à quantifier.

b) Les quantificateurs ∀ commutent entre eux, et de même les ∃ commutent entre eux, mais les quantificateurs ∀ ne commutent pas avec les ∃.

3. Interprétation ensembliste

Toutes les notions logiques que nous avons expliquées ont un analogue ensembliste, et ce n’est pas un hasard. De la même manière que nous devons préciser la portée des quantificateurs, nous devons avoir un ensemble de référence E, et toutes les propositions concerneront des parties de E.

Soit P_{A} la propriété “appartient à A” (pour une partie A de E) et P_{B} la propriété “appartient à B”.

Alors \overline{P_{A}} est la propriété “appartient à ∁_{E}A, complémentaire de A dans E”, “P_{A} ou P_{B}” est la propriété “appartient à A ∪ B”, “P_{A} et P_{B}” est la propriété “appartient à A ∩ B”.

D’autre part, si P (x) est la propriété “appartient à A_{x}” (pour des parties A_{x} de E), où x parcourt un ensemble d’indices X, alors “ ∀x ∈ XP (x)” est la propriété “appartient à ⋂_{x∈X} A_{x}” et “ ∃x ∈ XP (x)” est la propriété “appartient à ⋃_{x∈X} A_{x}”.