Licence de mathématiques Bernhard Haak
Quantificateurs
Soit E un ensemble et pour x ∈ E soit P (x) une proposition qui porte sur des propriétés
de x. Elle peut être vraie ou fausse. On utilise deux quantificateurs, ∀ = “pour tout” et
∃ = “il existe”, ensemble avec leur négations.
Un “pour tout” est faux, ssi il existe au moins une exception.
Un “il existe” est faux, ssi le contraire est vrai “pour tout” x.
Exercice 1 Vrai ou faux? & preuve ou contre-exemple!
a) ∀x ∈ Z : 2|x ⇒ 4|x.
b) ∀x ∈ Z : 4|x ⇒ 2|x.
c) ∀x ∈ Z : x < −2.
d) ∃x ∈ Z : x < −2.
Chaı̂nes de quantificateurs
On peut poser plusieurs quantificateurs dans une proposition. Il sont à lire de gauche
a droite. Quand un ∃ apparaı̂t dans une chaı̂ne de quantificateurs, l’objet “qui existe”
(ou pas) dépend de tout ce qui précède: dans
∀x ∈ E∃y ∈ E : ∀z ∈ E : P (x, y, z)
le y dépend du choix de x, mais pas de z. Règles:
∀x ∈ X∀y ∈ Y : P (x, y) et ∀y ∈ Y ∀x ∈ X : P (x, y)
sont des assertions équivalentes. De même
∃x ∈ X∃y ∈ Y : P (x, y) et ∃y ∈ Y ∃x ∈ X : P (x, y).
Bref: “des quantificateurs égaux commutent”. Qu’en est il pour des quantificateurs “mix-
tes”? Considérez
(1)∀y ∈ Y ∃x ∈ X : P (x, y) versus (2)∃x ∈ X∀y ∈ Y : P (x, y)
Exercice 2 Est-ce que (1) ⇒ (2) ou (2) ⇒ (1) sont vraies? Ou aucune? Ou les
deux? Prouvez le!
Pour illustration non-mathématique, essayez avec X = les êtres humains, Y = le temps,
et P (x, t) = “le humain x commet une erreur au moment (temps) t”.
Exercice 3 Traduire en “prose” et déterminer si la proposition est vraie ou fausse
a) ∀x ∈ R∀y ∈ R : x − y = y − x
b) ∀x ∈ R∀y ∈ R : xy = yx
c) ∃x ∈ R∃y ∈ R : x2 + y 2 = 1
d) ∀x ∈ Z∃y ∈ Z : x + y = 1
e) ∃x ∈ Z∀y ∈ Z : x + y = 1
On voit que “l’ordre compte” dans les deux derniers, ils ne commutent pas.
Exercice 4 “Téléphone arabe”: mettez vous 3 ou à 5 étudiants en cercle; chacun
écrit en cachette une proposition en utilisant 2-4 quantificateurs. Faites tourner les
papiers dans le sens trigonométrique : votre voisin de droite doit alors ré-écrire votre
proposition en prose, et vous faites de même avec la proposition de votre voisin de
gauche. Puis chacun(e) plie le papier pour cacher les formules, laissant visible que la
phrase “en prose”. Faites tourner les papiers à nouveau dans le même sens: chaqun(e) a
alors seulement une phrase “ en prose “ – et doit la retraduire en quantificateurs. Puis
on plie pour cacher la version “en prose”. Continuez jusqu’à ce votre papier revienne
vers vous: déplier alors et comparer. Y a t il des erreurs? Où? Pourquoi?
Négations de propositions en quantificateurs
La négation se déroule “mécaniquement”. Soit donné une chaı̂ne de quantificateurs avec
Qi ∈ {∃, ∀}
Q1 x1 ∈ E1 , . . . Qn xn ∈ En : P (x1 , . . . , xn )
alors la négation sera
Q{1 x1 ∈ E1 , . . . 6 Q{n xn ∈ En : ¬P (x1 , . . . , xn )
où ∃{ = ∀ et réciproquement ∀{ = ∃. Exemple: f est continue sur R si (déf)
∀x ∈ R∀ε > 0∃δ > 0 : ∀y ∈ R |x − y| < δ ⇒ |f (x) − f (y)| < ε
La fonction est donc(!) discontinue si
∃x ∈ R∃ε > 0∀δ > 0 : ∃y ∈ R |x − y| < δ et|f (x) − f (y)| ≥ ε
car la négation de A ⇒ B est “ A et ¬B “.
Quantificateurs cachés
La phrase “Si x < 0 alors f (x) > 0” est une abréviation pour
∀x ∈ R : x < 0 ⇒ f (x) > 0
Il est utile de formuler (au moins dans sa tête) toute phrase de ce type avec des quan-
tificateurs explicites.
Exercice 5 Écrire en quantificateurs “ si m < n sont nombres naturels (positifs)
alors il existe un nombre rationnel r tel que n1 < r < m1 “.
Quantificateurs et ensembles
Souvent des quantificateurs apparaissent dans des ensembles. Par exemple
C = {n ∈ N : n est un carré}
D’abord “est un carré” est un quantificateur caché! Plus formellement, on donc
C = {n ∈ N : ∃k ∈ Z : n = k 2 }.
On peut “sortir” le quantificateur d’une telle définition, selon la règle
∀ ←→ intersection et ∃ ←→ union
Ainsi, [ [
C= {n ∈ N : n = k 2 } = {k 2 }.
k∈Z k
De la même façon
P ={n ∈ N : n n’est pas un carré}
={n ∈ N : ¬(∃k ∈ Z : n = k 2 )}
={n ∈ N : ∀k ∈ Z : n 6= k 2 }
\
= {n ∈ N : n 6= k 2 }
k
Illustrer les ensembles Ak = {n ∈ N : n 6= k 2 } pour k = 1, 2, 3.
Quantificateurs et sup/inf
Exercice 6 Soit A ⊂ R. Montrer que sup(A) ≤ a ssi ∀x ∈ A : x ≤ a. Que signifie
sup(A) ≥ b ? Ou sup(A) > b ?
Exercice 7 Soit A ⊂ R. Montrer que inf(A) ≤ a ssi ∀ε > 0∃x ∈ A : x < a + ε. Que
signifie inf(A) ≥ b ? Ou inf(A) > b?
Exemple. Soit f : R → R une fonction et B(x, δ) = (x − δ, x + δ) la “boule” autour de
x de rayon δ.
C = {x ∈ R : inf{sup{|f (y) − f (z)| : y, z ∈ B(x, δ)} : δ > 0} = 0}
Ouff! On a des quantificateurs cachés. D’abord, grâce a la positivité de |f (x) − f (y)|,
on peut écrire
C = {x ∈ R : inf{sup{|f (y) − f (z)| : y, z ∈ B(x, δ)} : δ > 0} ≤ 0}
Puis, il suit que
C = {x ∈ R : ∀ε > 0 : ∃δ > 0 : sup{|f (y) − f (z)| : y, z ∈ B(x, δ)} ≤ ε}
= {x ∈ R : ∀ε > 0 : ∃δ > 0 : ∀y, z ∈ B(x, δ) : |f (y) − f (z)| :≤ ε}
\
= {x ∈ R : ∃δ > 0 : ∀y, z ∈ B(x, δ) : |f (y) − f (z)| :≤ ε}
ε>0
\[
= {x ∈ R : ∀y, z ∈ B(x, δ) : |f (y) − f (z)| :≤ ε}.
ε>0 δ>0
En fait, C est l’ensemble des points de continuité de f . Mais le but ici est de manipuler
des expressions correctement.