Yaogan MENSAH

Logique, Ensembles et Relations

Document de base
Version 2.0 (2019)
Table des matières

1 Logique et Raisonnement 2
1.1 Assertion et prédicat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Les connecteurs logiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.1 La négation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.2 La conjonction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.3 La disjonction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.4 L’implication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.5 L’équivalence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3 Tautologie et incompatibilité . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4 Equivalence logique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.5 Les quantificateurs mathématiques . . . . . . . . . . . . . . . . . . . . . . 7
1.6 Différents modes de démonstration . . . . . . . . . . . . . . . . . . . . . . 9
1.6.1 Raisonnement par hypothèse auxiliaire . . . . . . . . . . . . . . . . 9
1.6.2 Raisonnement par l’absurde . . . . . . . . . . . . . . . . . . . . . . 9
1.6.3 Raisonnement par contraposition . . . . . . . . . . . . . . . . . . . 9
1.6.4 Raisonnement par contre-exemple . . . . . . . . . . . . . . . . . . . 10
1.6.5 Raisonnement par récurrence . . . . . . . . . . . . . . . . . . . . . 10

2 Ensembles, Applications et Relations 11

2.1 Ensembles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.2.1 Définitions et exemples . . . . . . . . . . . . . . . . . . . . . . . . . 14

2
Logique, Ensembles et Relations 1

2.2.2 Composition des applications . . . . . . . . . . . . . . . . . . . . . 16

2.2.3 Applications particulières . . . . . . . . . . . . . . . . . . . . . . . 16
2.2.4 Images directes, images réciproques . . . . . . . . . . . . . . . . . 17
2.3 Relations binaires dans un ensemble . . . . . . . . . . . . . . . . . . . . . . 18
2.3.1 Définitions et Exemples . . . . . . . . . . . . . . . . . . . . . . . . 18
2.3.2 Relations d’équivalence . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.3.3 Relations d’ordre . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.4 Analyse combinatoire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.4.1 Ensembles finis, cardinaux . . . . . . . . . . . . . . . . . . . . . . . 22
2.4.2 Ensembles dénombrables . . . . . . . . . . . . . . . . . . . . . . . . 23
Chapitre 1

Logique et Raisonnement

1.1 Assertion et prédicat

Définition 1.1 Une assertion (ou proposition) est un énoncé auquel on peut attribuer la
valeur de vérité vrai (V) ou faux (F), mais jamais les deux à la fois.

Exemples 1.2 1. L’énoncé ”Lomé est la capitale du Togo” est vrai (V).
2. L’énoncé ”2,5 est un entier naturel” est faux (F).
3. L’énoncé ”Koffi est mortel” est vrai (V).
4. L’énoncé ” 19 est un multiple de 2” est faux (F).

Définition 1.3 Un prédicat est un énoncé contenant des lettres appelées variables et
qui est tel que quand on remplace ces variables par des éléments donnés on obtient une
assertion.

Exemples 1.4 1. L’énoncé P (n) : ”n est un multiple de 2” est un prédicat car il de-
vient une assertion quand on donne une valeur à n.
P (10) est une assertion vraie mais P (11) est une assertion fausse.
2. L’énoncé suivant P (x, A) : ” x ∈ A” est un prédicat à deux variables.
√
P (1, N) est une assertion vraie par contre P ( 2, Q) est une assertion fausse.

2
Logique, Ensembles et Relations 3

1.2 Les connecteurs logiques

A partir d’assertions existantes il est possible de construire de nouvelles assertions
appelées assertions composées. Ceci se fait via les connecteurs logiques.

1.2.1 La négation
Définition 1.5 La négation d’une assertion P est l’assertion, notée ¬P ou nonP , qui
est vraie lorsque P est fausse et fausse lorsque P est vraie

On résume ceci dans le tableau suivant appelé table de vérité :

P ¬P
V F
F V

Exemples 1.6 1. L’assertion P : ” 24 est un multiple de 2 ” a pour négation l’asser-

tion ¬P : ”24 n’est pas un multiple de 2”.
2. Le prédicat ”x ∈ A” a pour négation le prédicat ”x 6∈ A.”.

1.2.2 La conjonction
Définition 1.7 La conjonction des assertions P et Q notée P ∧ Q est l’assertion qui est
vraie lorsque P et Q sont simultanément vraies et fausse dans tous les autres cas.

P Q P∧ Q
V V V
V F F
F V F
F F F

Exemples 1.8 Considérons les deux propositions P et Q suivantes :

P :”10 est divisible par 2” et Q :”10 est divisible par 3”. La proposition P ∧ Q est fausse.
4 Yaogan MENSAH

1.2.3 La disjonction
Définition 1.9 La disjonction des assertions P et Q notée P ∨ Q est l’assertion qui est
vraie lorsque l’une au moins des deux assertions P et Q est vraie et fausse lorsque les
deux sont fausses.

P Q P∨ Q
V V V
V F V
F V V
F F F

Exemples 1.10 Considérons les deux assertions P et Q suivantes :

P : ”10 est divisible par 2” et Q : ”10 est divisible par 3”. L’assertion P ∨ Q est vraie.

1.2.4 L’implication
Définition 1.11 Soient P et Q des assertions. L’assertion ”P ⇒ Q”, appelée implica-
tion de P vers Q, est une assertion qui est fausse lorsque P est vraie et Q fausse et est
vraie dans tous les autres cas.

P Q P⇒ Q
V V V
V F F
F V V
F F V

Remarques 1.12 1. Dans P ⇒ Q, P est une condition suffisante pour Q et Q est

une condition nécessaire pour P .
2. Q ⇒ P s’appelle l’implication réciproque de P ⇒ Q.
3. ¬Q ⇒ ¬P s’appelle la contraposée de P ⇒ Q.
Logique, Ensembles et Relations 5

Exemples 1.13 Soient les propositions : P :”il pleut.” et Q : ”Je me mets à l’abri.” On
a
P ⇒ Q : ”S’il pleut alors je me mets à l’abri.”.
Q ⇒ P :”Si je me mets à l’abri alors il pleut.”
¬Q ⇒ ¬P : ”Si je ne me mets pas à l’abri alors il ne pleut pas.”

1.2.5 L’équivalence
Définition 1.14 Soient P et Q deux assertions. L’assertion ”P ⇔ Q”, appelée équivalence
de P et de Q, est une assertion qui
– est vraie lorsque P et Q sont simultanément vraies ou fausses,
– est fausse dans tous les autres cas.

P Q P⇔Q
V V V
V F F
F V F
F F V

1.3 Tautologie et incompatibilité

Définition 1.15 Une assertion composée qui est vraie quelles que soient les valeurs de
vérité des assertions qui la composent est appelée une tautologie.

Exemples 1.16 1. (P ∨ ¬P )
2. (P ∧ (P ⇒ Q)) ⇒ Q

Définition 1.17 On dit que deux assertions sont incompatibles si leur conjonction est
fausse.

Exemples 1.18 1. Les prédicats P et ¬P sont incompatibles.

2. Les prédicats ”x ≤ 1” et ”x ≥ 2” sont incompatibles.
6 Yaogan MENSAH

1.4 Equivalence logique

Définition 1.19 Soient R1 et R2 des prédicats composés. On dit que R1 et R2 sont
logiquement équivalents si R1 est vrai lorsque R2 est vrai et R1 est faux lorsque R2 est
faux. Cela revient au même de dire que R1 et R2 ont la même table de vérité et on note
R1 ≡ R2 . Dans le cas contraire on note R1 6≡ R2 .

Exemples 1.20 1. ¬(¬P ) ≡ P

2. P ∧ Q ≡ Q ∧ P

3. P ∨ Q ≡ Q ∨ P

4. (P ∧ Q) ∧ R ≡ P ∧ (Q ∧ R)

5. (P ∨ Q) ∨ R ≡ P ∨ (Q ∨ R)

6. P ∧ (P ∨ Q) ≡ P

7. P ⇔ Q ≡ Q ⇔ P

8. (¬P ⇒ Q) ∧ (¬P ⇒ ¬Q) ≡ P

Cette équivalence est à la base du raisonnement par l’absurde.

9. ¬(P ∨ Q) ≡ ¬P ∧ ¬Q

10. ¬(P ∧ Q) ≡ ¬P ∨ ¬Q
(9. et 10. sont les lois de Morgan pour les prédicats)

11. P ∨ (Q ∧ R) ≡ (P ∨ Q) ∧ (P ∨ R)

12. P ∧ (Q ∨ R) ≡ (P ∧ Q) ∨ (P ∧ R)

13. P ⇒ Q ≡ (¬P ∨ Q)

14. ¬(P ⇒ Q) ≡ (P ∧ ¬Q)

15. P ⇒ Q ≡ ¬Q ⇒ ¬P

16. P ⇔ Q ≡ (P ⇒ Q) ∧ (Q ⇒ P )
Logique, Ensembles et Relations 7

1.5 Les quantificateurs mathématiques

À partir d’un prédicat P (x) défini sur un ensemble E, on construit de nouvelles as-
sertions dites assertions quantifiées en utilisant les quantificateurs ” quel que soit” et ”il
existe”.

Définition 1.21 Le quantificateur ”quel que soit”, noté ∀, permet de définir l’assertion
quantifiée ” ∀x ∈ E, P (x) ” qui est vraie si pour tous les éléments x de E, l’assertion
P (x) est vraie.

Exemples 1.22 1. ”∀x ∈ [−3, 1], x2 + 2x − 3 ≤ 0” est vraie.

2. ”∀n ∈ N, n(n − 3) > 0” est fausse.

Définition 1.23 Le quantificateur ”il existe”, noté ∃, permet de définir l’assertion quan-
tifiée ” ∃ x ∈ E, P (x) ” qui est vraie si on peut trouver (au moins) un élément x de E
pour lequel l’assertion P (x) est vraie.

Remarques 1.24 1. S’il en existe un et un seul, on pourra écrire

∃ !x ∈ E, P (x).

2. Si ”∀x ∈ E, P (x)” est vraie alors ”∃ x ∈ E, P (x)” est vraie.

Exemples 1.25 1. ”∃ x ∈ R, x2 = 4” est vraie.

2. ”∃ !x ∈ R, ln(x2 ) = 1” est fausse.

Proposition 1.26 Soit P (x) un prédicat. On a :

1. ¬(∀x ∈ E, P (x)) ≡ ∃ x ∈ E, ¬(P (x)).
2. ¬(∃x ∈ E, P (x)) ≡ ∀ x ∈ E, ¬(P (x)).

Exemples 1.27 ¬(∀x ∈ E, P (x) ⇒ Q(x)) ≡ ∃ x ∈ E, P (x) ∧ ¬(Q(x)).

Définition 1.28 Soit P (x, y) un prédicat à deux variables avec x ∈ E et y ∈ F .

8 Yaogan MENSAH

1. L’assertion quantifiée
∀x ∈ E, ∀y ∈ F, P (x, y)

est vraie lorsque pour chaque élément x de E et chaque élément y de F , P (x, y) est
vraie.

2. L’assertion quantifiée
∃x ∈ E, ∃y ∈ F, P (x, y)

est vraie lorsqu’il existe un élément x de E et un élément y de F tels que P (x, y)

est vraie.

Exemples 1.29 1. L’assertion ”∀n ∈ N, ∀x ∈ [0, +∞[, 1 + nx ≤ (1 + x)n ” est vraie.

2. L’assertion ”∃x ∈ R, ∃y ∈ R, x + y = 5” est vraie.

Remarques 1.30 On peut combiner des quantificateurs de natures différentes. Par exemple,
l’énoncé ” tout nombre complexe possède une racine carrée” s’écrit sous la forme :

∀z ∈ C, ∃u ∈ C, u2 = z.

Mais on prendra soin de respecter les règles suivantes :

1. On peut permuter deux quantificateurs identiques.

(∀x ∈ E, ∀y ∈ F, P (x, y)) ≡ (∀y ∈ F, ∀x ∈ E, P (x, y)) .

(∃x ∈ E, ∃y ∈ F, P (x, y)) ≡ (∃y ∈ F, ∃x ∈ E, P (x, y)) .

2. Ne jamais permuter deux quantificateurs différents.

(∃x ∈ E, ∀y ∈ F, P (x, y)) 6≡ (∀y ∈ F, ∃x ∈ E, P (x, y)) .

Exemples 1.31 L’assertion quantifiée ” ∀x ∈ R, ∃y ∈ R, x+y = 0” est vraie. Par contre,

l’assertion ” ∃y ∈ R, ∀x ∈ R, x + y = 0” est fausse.
Logique, Ensembles et Relations 9

1.6 Différents modes de démonstration

1.6.1 Raisonnement par hypothèse auxiliaire

1. But : montrer qu’un énoncé Q est vrai.
2. Principe : il s’appuie sur la tautologie :

(P ∧ (P ⇒ Q)) ⇒ Q.

Ainsi si P est vrai et si l’implication P ⇒ Q est vraie alors Q est vrai.

3. Méthodologie : On montre que l’énoncé P est vrai et on en déduit que Q est vrai.

1.6.2 Raisonnement par l’absurde

1. But : montrer qu’un énoncé P est vrai.
2. Principe : il s’appuie sur la tautologie :

(¬P ⇒ Q) ∧ (¬P ⇒ ¬Q) ≡ P.

Un raisonnement par l’absurde consiste à montrer que ¬P entraı̂ne un énoncé Q et

sa négation ¬Q.
3. Méthodologie : On suppose que l’énoncé ¬P est vrai et on recherche une contradic-
tion.
a b
Exercice. Soit a, b ≥ 0. Montrer que si = alors a = b.
1+b 1+a

1.6.3 Raisonnement par contraposition

1. But : montrer l’implication P ⇒ Q.
2. Principe : il s’appuie sur l’équivalence logique :

P ⇒ Q ≡ ¬Q ⇒ ¬P.

Ainsi, au lieu de montrer P ⇒ Q, on montre sa contraposée ¬Q ⇒ ¬P .

10 Yaogan MENSAH

3. Méthodologie : On fait l’hypothèse que ¬Q est vrai et on montre que cela entraı̂ne
¬P .

Exercice. Montrer que si n2 est pair alors n est pair.

1.6.4 Raisonnement par contre-exemple

1. But : il sert à montrer qu’un énoncé de la forme

∀x ∈ E, P (x)

est faux.
2. Principe : il s’appuie sur l’équivalence logique :

¬(∀x ∈ E, P (x)) ≡ ∃x ∈ E, ¬(P (x)).

3. Méthodologie : On cherche à exhiber un élément x de E qui ne vérifie pas P (x).

Exercice. Est-ce que tout entier positif est la somme de trois carrés ?

1.6.5 Raisonnement par récurrence

1. But : montrer qu’un énoncé de la forme

pour tout entier naturel n ≥ n0 , P (n).

2. Principe : Si P (n0 ) ∧ (P (n) ⇒ P (n + 1)) alors ∀n ≥ n0 , P (n).

3. Méthodologie : On vérifie que P (n0 ) est vrai, on suppose ensuite P (n) et on montre
que cela entraı̂ne P (n + 1). Et enfin on conclut ∀n ≥ n0 , P (n).

Exercice. Montrer que ∀n ∈ N, 2n > n.

Chapitre 2

Ensembles, Applications et Relations

2.1 Ensembles
Intuitivement, un ensemble est une collection d’objets appelés éléments de l’ensemble.
Nous admettons qu’il existe un ensemble noté ∅, appelé ensemble vide , qui ne contient
aucun élément. Si E est un ensemble et P (x) une propriété vérifiée par certains éléments
x de E, l’ensemble de ces éléments est noté {x ∈ E : P (x)}.

Définition 2.1 On dit que l’ensemble E est inclus ou est contenu dans l’ensemble F si
tout élément de E est élément de F . On dit aussi que E est une partie ou un sous-ensemble
de F . On écrit E ⊂ F ou F ⊃ E.

(E ⊂ F ) ⇔ (∀x, x ∈ E ⇒ x ∈ F ).

On vérifie que quel que soit l’ensemble E, on a E ⊂ E. Si (E ⊂ F et F ⊂ G) alors

E ⊂ G.

Définition 2.2 On dit que l’ensemble E est égal à l’ensemble F , et on écrit E = F , si

E ⊂ F et F ⊂ E.

11
12 Yaogan MENSAH

Etant donné un ensemble E, on désigne par P(E) l’ensemble des parties de E, y compris
l’ensemble vide et l’ensemble E lui-même.

A ∈ P(E) ⇔ A ⊂ E.

Définition 2.3 Soient A et B des ensembles. L’ensemble {x : x ∈ A et x ∈

/ B} s’appelle
différence de A et B et se note A \ B.

Définition 2.4 Soient E un ensemble et A une partie de E. On appelle complémentaire

de A dans E, et on note E \ A ou CEA , l’ensemble des éléments de E qui n’appartiennent
pas à A.

CEA = {x ∈ E : x 6∈ A}.
A)
(CE
Proposition 2.5 1. CE = A; CEE = ∅; CE∅ = E.
2. Soit A, B ∈ P(E)
A ⊂ B ⇒ CEB ⊂ CEA .

Définition 2.6 On appelle intersection de deux ensembles E et F , et on note E ∩ F ,

l’ensemble des éléments qui appartiennent à la fois à E et à F .

E ∩ F = {x : x ∈ E et x ∈ F }.

Si E ∩ F = ∅, on dit que E et F sont disjoints.

Définition 2.7 On appelle réunion de deux ensembles E et F , et on note E ∪ F , l’en-

semble des éléments qui appartiennent à E ou à F .

E ∪ F = {x : x ∈ E ou x ∈ F }.

Proposition 2.8 1. E ∩ ∅ = ∅, E ∪ ∅ = E.
Logique, Ensembles et Relations 13

2. E ∪ F = ∅ ⇒ E = ∅ et F = ∅.
3. associativité

(A ∪ B) ∪ C = A ∪ (B ∪ C), (A ∩ B) ∩ C = A ∩ (B ∩ C).

4. commutativité
A ∪ B = B ∪ A, A ∩ B = B ∩ A.

5. distributivité
A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C),

A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C).

6. idempotence
A ∪ A = A, A ∩ A = A.

Théorème 2.9 (Lois de de Morgan )

(A∩B) (A∪B)
CE = CEA ∪ CEB , CE = CEA ∩ CEB .

Définition 2.10 Soient E et F deux ensembles. On appelle produit cartésien de E et

F , et on note E × F , l’ensemble des couples (x, y) tels que x ∈ E et y ∈ F .

E × F = {(x, y) : x ∈ E et y ∈ F }.

Proposition 2.11 Soient A,B,C,D des ensembles.

1.
A ⊂ C et B ⊂ D ⇒ A × B ⊂ C × D.

2.
A × (B ∪ C) = (A × B) ∪ (A × C).

A × (B ∩ C) = (A × B) ∩ (A × C).
14 Yaogan MENSAH

3.
A × B = ∅ ⇔ A = ∅ ou B = ∅.

Le produit cartésien E × E se note E 2 . On appelle diagonale de E 2 l’ensemble

∆ = {(x, x) : x ∈ E}.

Plus généralement, le produit cartésien de n ensembles E1 , . . . , En , noté

n
Y
E1 × · · · × En ou Ei ,
i=1

est l’ensemble des n-uples (x1 , . . . , xn ) tels que xi ∈ Ei , i = 1, . . . , n.

Si Ei = E ∀i, on note E n au lieu de E × · · · × E. Par exemple R × R × R se note R3 .

Définition 2.12 On appelle partition d’un ensemble non vide E une famille (Ai )i∈I de
parties de E (indexée par I) telles que
1. ∀i ∈ I, Ai 6= ∅,
2. ∀i, j ∈ I, (i 6= j ⇒ Ai ∩ Aj = ∅),
S
3. Ai = E.
i∈I

Exemples 2.13 Soit A une partie propre non vide de E. Alors A et CEA forment une
partition de E.

2.2 Applications

2.2.1 Définitions et exemples

Définition 2.14 Soient E et F deux ensembles. On appelle fonction f de E vers F toute
relation qui associe à chaque élément de E au plus un élément de F .
f
On note f : E → F ou E → F . Si l’élément x de E est associé à l’élément y de F , on
dit que x est un antécédent de y et y est l’image de x. On écrit y = f (x). L’ensemble des
éléments de E ayant une image par f est appelé ensemble de définition de f et noté Df .

Df = {x ∈ E : ∃y ∈ F, y = f (x)}.
Logique, Ensembles et Relations 15

L’ensemble Γ = {(x, f (x)) ∈ E × F : x ∈ Df } est appelé le graphe de f .

Définition 2.15 Une fonction f : E → F est appelée application si son ensemble de

définition est E.

L’ensemble des applications de E vers F est souvent noté F E .

Exemples 2.16 1. La fonction

f : R −→ R
1
x 7−→ x−2

n’est pas une application car Df 6= R.

2. La fonction
g : R −→ R
x 7−→ sin x
est une application car Dg = R.
3. L’application
E −→ E
x 7−→ x
est appelée application identique ou identité de E. Elle est souvent notée IdE ou
1E .
4. Soit A une partie d’un ensemble E. On appelle fonction caractéristique de A l’ap-
plication χA définie de E vers {0, 1} par
(
1 si x ∈ A
χA (x) =
0 si x 6∈ A.

5. Les applications
pr1 : E × F −→ E
(x, y) 7−→ x
et
pr2 : E × F −→ F
(x, y) 7−→ y
sont respectivement appelées première projection et deuxième projection.
16 Yaogan MENSAH

Définition 2.17 Soient f : E → F et g : E 0 → F 0 deux applications. On dit que f égale

g et on note f = g si

E = E 0 , F = F 0 et ∀x ∈ E, f (x) = g(x).

2.2.2 Composition des applications

Soient E, F et G des ensembles, f : E → F , g : F → G des applications. L’application

E → G
x 7→ g(f (x))

s’appelle l’application composée de f par g et se note g ◦ f .

En général on a g ◦ f 6= f ◦ g. Cependant :

Proposition 2.18 Soient les applications f : E → F , g : F → G et h : G → H. On a

h ◦ (g ◦ f ) = (h ◦ g) ◦ f.

On dit que la loi ◦ est associative. L’application h ◦ (g ◦ f ) est simplement notée h ◦ g ◦ f .

2.2.3 Applications particulières

Définition 2.19 Soient E et F deux ensembles et f : E → F une application.
1. On dit que f est injective (ou est une injection) si pour tous x, y ∈ E,

f (x) = f (y) ⇒ x = y.

2. On dit que f est surjective (ou est une surjection) si pour tout y ∈ F , il existe x ∈ E
tel que y = f (x).
3. On dit que f est bijective (ou est une bijection ) si elle est à la fois injective et
surjective i.e pour tout y ∈ F , il existe un unique x ∈ E tel que y = f (x).
Logique, Ensembles et Relations 17

Soit f : E → F une bijection. L’application f −1 : F → E qui à chaque élément y de

F associe l’unique élément x de E tel que y = f (x) est une bijection. Elle est appelée
application réciproque de f . On a

(f −1 )−1 = f, f −1 ◦ f = IdE , f ◦ f −1 = IdF .

Proposition 2.20 Si f : E → F et g : F → G sont injectives (resp. surjectives, resp.

bijectives ) alors il en est de même de g ◦ f . De plus dans le dernier cas, on a

(g ◦ f )−1 = f −1 ◦ g −1 .

2.2.4 Images directes, images réciproques

Définition 2.21 Soit f : E → F une application, A une partie de E et B une partie de
F.
1. L’ image directe ou simplement l’image de A par f , notée f (A) est l’ensemble des
images des éléments de A par f .

f (A) = {f (x) : x ∈ A}.

2. L’ image réciproque de B par f , notée f −1 (B), est l’ensemble des éléments de E

qui ont leurs images dans B.

f −1 (B) = {x ∈ E : f (x) ∈ B}.

Proposition 2.22 Soit f : E → F une application, A, A0 deux parties de E, B, B 0 deux

parties de F .
1. Si A ⊂ A0 alors f (A) ⊂ f (A0 ).
2.
f (A ∪ A0 ) = f (A) ∪ f (A0 ).

f (A ∩ A0 ) ⊂ f (A) ∩ f (A0 ).

3. Si B ⊂ B 0 alors f −1 (B) ⊂ f −1 (B 0 ).
18 Yaogan MENSAH

4.
f −1 (B ∪ B 0 ) = f −1 (B) ∪ f −1 (B 0 ).

f −1 (B ∩ B 0 ) = f −1 (B) ∩ f −1 (B 0 ).
f −1 (B)
f −1 (CFB ) = CE .

2.3 Relations binaires dans un ensemble

2.3.1 Définitions et Exemples

Définition 2.23 Soit E un ensemble. On appelle relation binaire sur E tout couple R =
(E, Γ) où Γ est une partie de E × E appelée graphe de R.

Si (x, y) ∈ Γ, on dit que x est en relation avec y et on note xRy.

Exemples 2.24 Dans P(E) la relation R définie par ARB ⇔ A ⊂ B est une relation
binaire.

Définition 2.25 Soit E un ensemble et R une relation binaire sur E. On dit que R est :
– réflexive si
∀x ∈ E, xRx.

– symétrique si
∀x, y ∈ E, xRy ⇒ yRx.

– antisymétrique si
∀x, y ∈ E, xRy et yRx ⇒ x = y.

– transitive si
∀x, y, z ∈ E, xRy et yRz ⇒ xRz.

Exemples 2.26 1. La relation d’égalité est une relation réflexive, symétrique, anti-
symétrique et transitive.
2. Dans P(E), la relation d’inclusion est réflexive, antisymétrique et transitive.
Logique, Ensembles et Relations 19

3. Dans Z∗ , la relation de divisibilité définie par

xRy ⇔ x divise y

est réflexive et transitive. Elle n’est ni symétrique ni antisymétrique.

2.3.2 Relations d’équivalence

Définition 2.27 On appelle relation d’équivalence sur E toute relation binaire sur E qui
est à la fois réflexive, symétrique et transitive.

Une telle relation R peut se noter xRy ou x ≡ y (mod R) et on lit ”x est équivalent à y
modulo R”.
La classe d’équivalence d’un élément x de E constituée des éléments y de E qui sont
équivalents à x est notée cl(x) ou x ou ẋ. L’ensemble de toutes les classes d’équivalence
s’appelle l’ensemble quotient de E par R et se note E/R. Tout élément d’une classe
d’équivalence est appelé représentant de cette classe.
L’application
E → E/R
x 7→ x
est surjective ; elle est appelée surjection canonique.

Exemples 2.28 Soit p un entier ≥ 1. Dans Z la relation

xRy ⇔ p divise x − y

est une relation d’équivalence. La classe de l’entier n est l’ensemble

{. . . , n − 2p, n − p, n, n + p, n + 2p, . . .}.

On l’appelle classe de congruence de n modulo p. L’ensemble quotient E/R se note ici

Z/pZ.

Proposition 2.29 Soit R une relation d’équivalence sur E. L’ensemble des classes d’équivalence
modulo R forme une partition de E. Réciproquement, toute partition de E définit une re-
lation d’équivalence dont les classes sont les éléments de la partition donnée.
20 Yaogan MENSAH

Proposition 2.30 (Décomposition canonique) Soit f : E → F une application.

1. La relation binaire R définie sur E par

xRy ⇔ f (x) = f (y)

est une relation d’équivalence dans E dite associée à f .

2. Il existe une application bijective unique f : E/R → f (E) telle que

f =i◦f ◦s

où s est la surjection canonique et i l’injection canonique. Cela revient à dire que
le diagramme suivant est commutatif.

La bijection f est appelée l’application déduite de f par passage au quotient.

2.3.3 Relations d’ordre

Définition 2.31 On appelle relation d’ordre sur E toute relation binaire sur E qui est
réflexive, antisymétrique et transitive.

Une relation d’ordre est souvent notée ≤ et le couple (E, ≤) est appelé ensemble ordonné.
Dans un ensemble ordonné, deux éléments x et y sont dits comparables si x ≤ y ou y ≤ x.
Si deux éléments quelconques de E sont comparables, on dit que l’ordre est total ou que le
couple (E, ≤) est totalement ordonné. Dans le cas contraire on dit que l’ordre est partiel
ou que le couple (E, ≤) est partiellement ordonné.

Exemples 2.32 1. Dans N, Z, Q et R, l’ordre usuel est un ordre total.

2. Soit E un ensemble. La relation d’inclusion est une relation d’ordre partiel sur
P(E).
3. Dans N, la relation de divisibilité est une relation d’ordre partiel.

Définition 2.33 Soit (E, ≤) un ensemble ordonné. S’il existe a ∈ E tel que

∀x ∈ E, a ≤ x ⇒ x = a(resp.∀x ∈ E, x ≤ a ⇒ x = a)

on dit que a est un élément maximal (resp. minimal) de E.

Logique, Ensembles et Relations 21

Exemples 2.34 1. Dans (N\{1}, |), les éléments minimaux sont les nombres premiers.
Dans (N, |), 0 est le seul élément maximal.
2. Dans (P(E)\{∅}, ⊂), les éléments minimaux sont les parties réduites à un élément.
3. Dans (R, ≤), il n’y a ni élément maximal ni élément minimal.

Définition 2.35 Soit (E, ≤) un ensemble ordonné. S’il existe un élément a ∈ E tel que
∀x ∈ E, x ≤ a (resp. a ≤ x) cet élément est unique ; on l’appelle le plus grand (resp. le
plus petit) élément de E, on le note max(E) (resp. min(E)).

Remarques 2.36 Si (E, ≤) admet un plus grand élément a alors a est l’unique élément
maximal de (E, ≤).

Exemples 2.37 1. Dans (P(E), ⊂), ∅ est le plus petit élément, E est le plus grand
élément.
2. (N, |), 0 est le plus grand élément ; 1 est le plus petit élément. Par contre dans (N, ≤),
0 est le plus petit élément, il n’y a pas de plus grand élément.

Définition 2.38 Soit (E, ≤) un ensemble ordonné et A une partie de E. S’il existe un
élément m ∈ E tel que
∀x ∈ A, x ≤ m (resp. m ≤ x)

on dit que A est majoré (resp. minoré) et que m est un majorant (resp. minorant) de A
dans E.
Une partie bornée est une partie à la fois majorée et minorée.

Définition 2.39 Soit (E, ≤) un ensemble ordonné et A une partie de E. Si l’ensemble

des majorants (resp. minorants) de A admet un plus petit (resp. plus grand) élément,
cet élément est appelé borne supérieure (resp. borne inférieure) de A et se note sup(A)
(resp. inf(A)).

Exemples 2.40 Dans (R, ≤), la partie A = {x ∈ R : 0 ≤ x < 1} admet 0 pour borne
inférieure et 1 pour borne supérieure.
22 Yaogan MENSAH

2.4 Analyse combinatoire

2.4.1 Ensembles finis, cardinaux

Définition 2.41 Deux ensembles sont dits équipotents s’il existe une bijection de l’un
sur l’autre.

On vérifie, grâce aux propriétés des bijections que l’ équipotence est une relation
réflexive, symétrique et transitive entre ensembles. Cependant ce n’est pas une relation
binaire sur un ensemble ; on ne parlera donc pas de relation d’équivalence.

Définition 2.42 Un ensemble E est dit fini s’il est vide ou s’il est équipotent à Nn :=
{1, ..., n} pour un certain entier n ≥ 1 donné.

L’entier n est appelé cardinal de E et on note Card(E) = n. On pose par définition

Card(∅) = 0.

Définition 2.43 Un ensemble est dit infini s’il n’est pas fini.

Proposition 2.44 1. Toute partie F d’un ensemble fini E est fini et Card(F ) ≤
Card(E).
2. l’intersection d’une famille (finie ou infinie) d’ensembles finis est finie.
3. Soient E un ensemble fini et f : E → F une application. Alors f (E) est un ensemble
fini et Card(f (E)) ≤ Card(E), avec égalité ssi f est une injection.
4. Soient un ensemble fini et f : E → F une surjection. Alors F est fini et Card(F ) ≤
Card(E), avec égalité ssi f est une bijection.
5. Soit f : E → F une injection. Si f (E) est fini alors E est fini et Card(E) =
Card(f (E)).

On en déduit le théorème suivant.

Logique, Ensembles et Relations 23

Théorème 2.45 Soient E et F deux ensembles finis, de même cardinal, et f : E → F

une application. Alors les affirmations suivantes sont équivalentes :

1. f est injective
2. f est surjective
3. f est bijective.

2.4.2 Ensembles dénombrables

Définition 2.46 Un ensemble E est dit dénombrable s’il est équipotent à N.

On montre que les ensembles suivants sont dénombrables : Z, Q. Par contre R n’est
pas dénombrable.

Proposition 2.47 Toute partie d’un ensemble dénombrable est finie ou dénombrable.
(On dit qu’elle est au plus dénombrable.)
Bibliographie

[1] A. Boussari, Cours de MTH 104, (Communication personnelle), (2009).

[2] E. Lehman, Mathématiques pour l’étudiant de première année, Belin, (1984)
[3] J.-M. Monier, Analyse 1, Série ”J’intègre”, 3e édition, Dunod, (1999).
[4] X. Oudot, Analyse première année, Belin, (1998)
[5] S. Touré, Algèbre , Universités francophones, Edicef, (1991)
[6] W. F. Trench, Introduction to real analysis, Open Textbook Initiative, (2013)

24