Logique et Théorie des Ensembles

11 novembre 2022
 Table des matières

1 Logique des propositions 2

1.1 Propositions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Syntaxe et sémantique de la logique propositionnelle . . . . . . . . . . . . . 3
1.2.1 Syntaxe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.2 Sémantique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Les connecteurs logiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3.1 Opérateurs booléens unaires . . . . . . . . . . . . . . . . . . . . . . 4
1.3.2 Opérateurs booléens binaires . . . . . . . . . . . . . . . . . . . . . . 4
1.4 Consistance et validité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.5 Quelques propriétés des connecteurs . . . . . . . . . . . . . . . . . . . . . . 7
1.5.1 Négation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.5.2 Equivalence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.5.3 La disjonction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.5.4 La conjonction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.5.5 Relations entre ∧ et ∨ . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.5.6 L’implication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.5.7 Autres relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.6 Formes normales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.7 Formalisation de textes en logique propositionnelle . . . . . . . . . . . . . . 11

2 Logique des prédicats 12

2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2 Les quantificateurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2.1 Le quantificateur existentiel . . . . . . . . . . . . . . . . . . . . . . 13
2.2.2 Le quantificateur universel . . . . . . . . . . . . . . . . . . . . . . . 14
2.3 Quelques règles sur les quantificateurs . . . . . . . . . . . . . . . . . . . . . 15
2.4 Variables libres, variables liées . . . . . . . . . . . . . . . . . . . . . . . . . 17

3 Quelques méthodes de raisonnement 19

3.1 Les méthodes directes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

Logique et Théorie des Ensembles Raymond HOUNNONKPE©MI-ENS 2023

TABLE DES MATIÈRES 1

3.1.1 Démonstration directe de p ⇒ q . . . . . . . . . . . . . . . . . . . . 19

3.1.2 Démonstration directe de p ∧ q . . . . . . . . . . . . . . . . . . . . . 19
3.1.3 Démonstration directe de p ∨ q . . . . . . . . . . . . . . . . . . . . . 20
3.1.4 Montrer une équivalence . . . . . . . . . . . . . . . . . . . . . . . . 20
3.1.5 Preuve de ∃x ∈ E, P (x) . . . . . . . . . . . . . . . . . . . . . . . . 20
3.1.6 Preuve de ∀x ∈ E, P (x) . . . . . . . . . . . . . . . . . . . . . . . . 21
3.1.7 Raisonnement par l’utilisation d’un contre exemple . . . . . . . . . . 21
3.2 Les méthodes indirectes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.2.1 Raisonnement par contraposition . . . . . . . . . . . . . . . . . . . . 21
3.2.2 Raisonnement par l’absurde . . . . . . . . . . . . . . . . . . . . . . 22
3.2.3 Raisonnement par disjonction de cas . . . . . . . . . . . . . . . . . . 22
3.2.4 Raisonnement par analyse-synthèse . . . . . . . . . . . . . . . . . . 22
3.2.5 Raisonnement par induction mathématique (récurrence) . . . . . . . 23

4 Théorie des ensembles 25

4.1 Notion d’ensemble . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.1.1 L’axiome d’extensionnalité . . . . . . . . . . . . . . . . . . . . . . . 26
4.1.2 L’axiome de sélection. . . . . . . . . . . . . . . . . . . . . . . . . . 26
4.1.3 Axiome d’existence du vide . . . . . . . . . . . . . . . . . . . . . . 26
4.1.4 Sous-ensemble . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
4.2 Opérations de base sur les ensembles . . . . . . . . . . . . . . . . . . . . . . 27
4.2.1 Complémentaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
4.2.2 Intersection, union et différence symétrique . . . . . . . . . . . . . . 28
4.3 Produit cartésien d’ensembles . . . . . . . . . . . . . . . . . . . . . . . . . 29
4.4 Ensembles équipotents, finis, dénombrables . . . . . . . . . . . . . . . . . . 30
4.5 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4.6 Relations binaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
4.6.1 Relation d’équivalence . . . . . . . . . . . . . . . . . . . . . . . . . 34
4.6.2 Relation d’ordre . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

Bibliographie 37
 C HAPITRE UN

L OGIQUE DES PROPOSITIONS

Dans la logique propositionnelle, on étudie les relations entre des énoncés,

que l’on va appeler propositions ou encore des formules. Ces relations peuvent
être exprimées par l’intermédiaire de connecteurs logiques qui permettent,
par composition, de construire des formules syntaxiquement correctes. On
trouve principalement : la conjonction, la disjonction (inclusive), l’implica-
tion, l’équivalence et la négation. Le calcul propositionnel permet :
- de modéliser les connaissances et les raisonnements
- d’établir des déductions qui permettent d’aboutir à des conclusions.

1.1 Propositions

Définition 1.1. Une proposition (ou assertion, ou formule, ou encore expres-

sion booléenne) est un énoncé déclaratif dont on peut dire s’il est vrai (valeur
V ou 1) ou s’il est faux (valeur F ou 0), indépendamment de tout contexte de
lieu, de temps, ou de personne qui le prononce. De plus, un énoncé qui est à
la fois vrai et faux n’est pas une proposition.
La vérité ou la fausseté d’une assertion est sa valeur de vérité.
Exemple 1.1. i) Natitingou est dans le département de l’Atacora.
ii) Le lion est un oiseau.
√
iii) 2 est un nombre rationnel.
iv) Si le lion est un oiseau alors Natitingou est dans le département de
l’Atacora.
√
v) Natitingou est dans le département de l’Atacora ou 2 est un nombre
rationnel.

Logique et Théorie des Ensembles Raymond HOUNNONKPE©MI-ENS 2023

 3

On distingue deux sortes de formules (assertions) : les formules atomiques

(elles sont indécomposables et n’admettent pas de constituants qui soient en-
core des assertions) et les formules composées (obtenues à partir de plusieurs
formules atomiques et des opérateurs (connecteurs) logiques).

Exemple 1.2. Classer les propositions de l’exemple 1.1 en formules atomiques

et composées.

1.2 Syntaxe et sémantique de la logique propositionnelle

1.2.1 Syntaxe

S’intéresser à la syntaxe de la logique propositionnelle, c’est considérer les

formules qui sont bien écrites. Pour cela, on se donne un alphabet, c’est-à-dire
un ensemble de symboles, avec :
— un ensemble V = {p, q, r, ...} fini ou dénombrable de lettres appelées
variables propositionnelles. Il s’agit des propositions atomiques.
— les constantes booléennes Vrai et faux.
— un ensemble (fini) de connecteurs logiques encore appelés opérateurs
logiques ou opérateurs booléens : ils permettent de créer de nouvelles
assertions à partir de la donnée d’une ou de plusieurs assertions.
— les parenthèses (). Ces dernières sont indispensables pour imposer des
priorités. par ailleurs, on convient que si p est une assertion alors (p) est
aussi une assertion.

1.2.2 Sémantique

S’intéresser à la sémantique de la logique propositionnelle, c’est déterminer

la valeur de vérité d’un énoncé, c’est-à-dire d’une formule, dans le cadre d’un
de ses états possibles. On parle de l’interprétation d’une formule : il s’agit
plus concrètement d’affecter une valeur vrai ou faux à chacune des variables
propositionnelles qui la compose. Pour une formule à n variables, il y a 2n
états possibles.
 4

1.3 Les connecteurs logiques

Si p et q sont deux assertions, à l’aide des connecteurs logiques, nous allons

définir de nouvelles assertions à partir de p et q. On distingue les opérateurs
booléens unaires prenant un seul argument (au nombre de 4) et les opérateurs
booléens binaires prenant deux arguments (au nombre de 16). Nous ne présen-
terons que les plus utilisés.

1.3.1 Opérateurs booléens unaires

La plus connue est la négation notée ¬. La négation d’une assertion p est

l’assertion notée ¬p qui :
- est vraie lorsque p a la valeur Faux,
- a la valeur Faux lorsque p est vraie.

Exemple 1.3. Donner la négation de chacune des propositions de l’exemple

1.1.

Une théorie est dite contradictoire si elle contient une assertion à la fois
vraie et fausse.

1.3.2 Opérateurs booléens binaires

Parmi les connecteurs logiques binaires les plus utilisés, on peut citer :
1. la conjonction (et) notée ∧
2. la disjonction (ou) notée ∨
3. l’implication notée ⇒
4. l’équivalence notée ⇔

Remarque 1.4. Le tableau ci-après rend compte des règles de préséance entre
les connecteurs logiques usuels : l’ordre étant décroissant de gauche à droite,
les connecteurs situés dans la même case ont la même priorité, de même qu’un
opérateur et sa négation : ¬ ∧, ∨ ⇒, ⇐ ⇔, ≡
 5

La conjonction

Le connecteur logique ET ( la conjonction) porte sur deux assertions. L’as-

sertion p et q notée p ∧ q a la valeur Vrai lorsque les deux assertions p et q ont
simultanément la valeur Vrai et la valeur Faux dans tous les autres cas.

Exemple 1.5. Donner la valeur de vérité de chacune des assertions suivantes.

(A) 136784512795 est un nombre premier et 6 divise 136784512795.
(B) 136784512791 est un nombre premier et 6 divise 136784512791.
√ √ √
(C) Natitingou est dans le département du Zou et ( 3 + 6 < 2 + 5).
(D) p ∧ (¬p), où p est une assertion quelconque.
32
(E) 3 est impair et (e10 < 1032 ).

La disjonction

Etant données deux assertions p et q on a une assertion notée p ∨ q et se lit

p ou q. L’assertion p ∨ q a la valeur Faux lorsque les deux assertions p et q ont
simultanément la valeur Faux et la valeur Vrai dans tous les autres cas.

Exemple 1.6. Donner la valeur de vérité de chacune des assertions suivantes.

• (3 < 7) ou π est un nombre rationnel.
• Natitingou est dans le département de l’Atacora ou
√ √ √
( 3 + 6 < 2 + 5).
• p ∨ (¬p), où p est une assertion quelconque.
• 3 est impair ou (eπ < e4 ).

L’implication

Le connecteur logique Si ... alors ( l’implication) porte sur deux assertions.

L’assertion : Si p alors q notée p ⇒ q a la valeur de vérité Faux si et seulement
si l’on a simultanément l’assertion p vraie et l’assertion q fausse.

Remarque 1.7. • Dans p ⇒ q, l’assertion p s’appelle l’antécédent et q le

conséquent.
• Si p ⇒ q est vraie, on dit que p est une condition suffisante pour q et
que q est une condition nécessaire pour p.
 6

• Si p ⇒ q est vraie, on dit que p est une condition plus forte que q (ou un
renforcement de q) et que q est une condition plus faible que p (ou un
affaiblissement de p).

Exemple 1.8. Donner la valeur de vérité de chacune des assertions suivantes.

• Si (3 < 7) alors π est un nombre rationnel.
• Si Natitingou est dans le département de l’Atacora alors (1 < 2).
• p ⇒ p, où p est une assertion quelconque.
• Si 3 est impair alors le nombre e est irrationnel.

L’équivalence

Le connecteur logique si et seulement si ( équivalence) porte sur deux

assertions. L’assertion : p si et seulement si q notée p ⇔ q est vraie lorsque p
et q sont simultanément vraies ou simultanément fausses et fausse dans tous
les autres cas.

Exemple 1.9. 1. Donner la valeur de vérité de chacune des assertions sui-

vantes.
• (3 < 7) si et seulement si π est un nombre rationnel.
• Natitingou est dans le département du Borgou si et seulement si (2 < 1).
• p ⇔ (¬p), où p est une assertion quelconque.
• 3 est impair si et seulement si le nombre e est irrationnel.
2. Etablir la table de vérité de chacune des formules ci-dessous :
(A) : p ⇒ (q ∧ r)
(B) : [(p ⇔ q) ⇒ r] ⇒ [(¬p ∨ q) ⇒ r]

1.4 Consistance et validité

Définition 1.2. Soit A une formule propositionnelle.

• On appelle modèle de A une interprétation pour laquelle la formule
est vraie. Par exemple (p, f aux), (r, vrai), (s, f aux) est un modèle de
(p ⇒ (r ∧ s)).
• A est satisfaite dans un état si elle a la valeur de vrai dans cet état.
 7

• A est satisfaisable (ou satisfiable ou encore consistante) si A a au moins

un modèle c’est-à-dire s’il y a au moins un état dans lequel elle est
satisfaite.
• A est valide, ou A est une tautologie si elle est satisfaite dans tous les
états.
• A est insatisfaisable ou inconsistante si A n’est pas satisfaisable.
• A est simplement consistante ou contingente si A est consistante mais
non valide.
Remarque 1.10. Une formule A est valide si et seulement si sa négation ¬A
est insatisfaisable.
Exercice 1.11. On considère la formule :
(A) : [(p ∨ q) ⇒ ¬r] ⇒ [(p ∧ q) ⇒ r]
1. Dresser la table de vérité de A.
2. (A) est-elle une formule valide ?
3. (A) est-elle satisfiable ? Si oui préciser tous les modèles pour (A).

1.5 Quelques propriétés des connecteurs

1.5.1 Négation

1. ¬¬p ≡ p (double négation)

2. ¬f aux ≡ vrai

1.5.2 Equivalence

1. (p ⇔ (q ⇔ r)) ≡ ((p ⇔ q) ⇔ r) (associativité)

2. (p ⇔ q) ≡ (q ⇔ p) (symétrie)
3. (p ⇔ q) (reflexivité de ⇔ )
4. (p ⇔ vrai) ≡ p (élément neutre de ⇔ )
5. ¬(p ⇔ q) ≡ (¬p ⇔ q) (distribution de ¬ sur ⇔ )
6. (p ̸≡ q) ≡ ¬(p ≡ q)
7. (¬p ⇔ q) ≡ (p ⇔ ¬q)
8. (¬p ⇔ p) ≡ f aux
 8

1.5.3 La disjonction

1. p ∨ q ≡ q ∨ p (commutativité de ∨)
2. p ∨ (q ∨ r) ≡ (p ∨ q) ∨ r (associativité de ∨)
3. p ∨ p ≡ p (idempotence de ∨)
4. (p ∨ (q ⇔ r)) ≡ ((p ∨ q) ⇔ (p ∨ r))) (distributivité de ∨ sur ⇔ )
5. (p ∨ ¬p) ≡ vrai (Tiers exclu)
6. p ∨ vrai ≡ vrai (absorption)
7. p ∨ f aux ≡ p (élément neutre de ∨)

1.5.4 La conjonction

1. p ∧ q ≡ q ∧ p (commutativité de ∧)
2. p ∧ (q ∧ r) ≡ (p ∧ q) ∧ r (associativité de ∧)
3. p ∧ p ≡ p (idempotence de ∧)
4. (p ∨ (q ⇔ r)) ≡ ((p ∨ q) ⇔ (p ∨ r))) (distributivité de ∨ sur ⇔ )
5. (p ∧ ¬p) ≡ f aux (contadiction)
6. p ∧ f aux ≡ f aux (absorption)
7. p ∧ vrai ≡ p (élément neutre de ∧)
8. p ∧ (q ∧ r) ≡ (p ∧ q) ∧ (p ∧ r) (distributivité de ∧ sur ∧ )
9. (p ∧ q) ≡ (p ⇔ q ⇔ p ∨ q) (règle d’or)

1.5.5 Relations entre ∧ et ∨

1. p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) (distributivité de ∨ sur ∧ )
2. p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) (distributivité de ∧ sur ∨ )
3. ¬(p ∧ q) ≡ ¬p ∨ ¬q (De Morgan)
4. ¬(p ∨ q) ≡ ¬p ∧ ¬q (De Morgan)

1.5.6 L’implication

1. (p ⇒ q) ≡ ¬p ∨ q (définition de ⇒)
2. p ⇒ q ≡ [(p ∨ q) ⇔ q]
3. p ⇒ q ≡ [p ∧ q ⇔ p]
4. (p ⇒ q) ≡ (¬q ⇒ ¬p) (contraposition)
 9

5. (p ⇒ (q ⇔ r)) ≡ ((p ⇒ q) ⇔ (p ⇒ r)) (distributivité de ⇒ sur ⇔ )

6. (p ∧ q ⇒ r) ≡ (p ⇒ (q ⇒ r)) (transfert)
7. p ∧ (p ⇒ q) ≡ p ∧ q
8. p ∧ (q ⇒ p) ≡ p
9. p ∨ (q ⇒ p) ≡ q ⇒ p
10. (p ∨ q ⇒ p ∧ q) ≡ (p ⇔ q)

1.5.7 Autres relations

Affaiblissement, renforcement

1. p⇒p∨q
2. p∧q ⇒p
3. p∧q ⇒p∨q
4. p ∨ (q ∧ r) ⇒ p ∨ q
5. p ∧ q ⇒ p ∧ (q ∨ r)

Modus ponens

p ∧ (p ⇒ q) ⇒ q

Modus tollens

¬q ∧ (p ⇒ q) ⇒ ¬p

Formes d’analyse par cas

1. (p ⇒ r) ∧ (q ⇒ r) ≡ (p ∨ q ⇒ r)
2. (p ⇒ r) ∧ (¬p ⇒ r) ≡ r
Exercice 1.12. 1. Montrer que :
a. p ∧ (p ⇔ q) ≡ p ∧ q
b. (p ∧ q) ⇔ (p ∧ ¬q) ≡ ¬p
c. [(p ⇒ q) ∧ (q ⇒ r)] ⇒ (p ⇒ r)
d. [(p ⇔ q) ∧ (q ⇒ r)] ⇒ (p ⇒ r)
2. a. Dresser la table de vérité de la formule :
(A) : [(p ∧ q) ∨ (p ⇒ r)] ⇒ (¬p ∨ (q ⇒ r))
 10

b. (A) est-elle une formule valide ?

c. (A) est-elle satisfiable ? Si oui préciser tous les modèles pour (A).
3. Donner la forme arborescente des formules suivantes :
(B) : (p ⇒ q) ⇔ (¬q ∧ (p ∨ r)) et (C) : p ⇒ (q ∨ (r ∧ ¬p))

1.6 Formes normales

Nous introduisons maintenant la notion de formes normales. Mettre une

formule en forme normale consiste à transformer la formule en une formule
équivalente ayant des propriétés structurelles. Par exemple, la forme normale
disjonctive permet de mettre en évidence les modèles et la forme normale
conjonctive exhibe les contre-modèles. La définition de forme normale néces-
site l’introduction des concepts de littéral et clause.
Définition 1.3. • Un littéral est une formule atomique ou la négation d’une
formule atomique.
• Une clause est une formule propositionnelle qui n’utilise que des litté-
raux et la disjonction.
• Une conjonction élémentaire ou monôme est une formule proposition-
nelle qui n’utilise que des littéraux et la conjonction.
Définition 1.4. On appelle forme normale disjonctive d’une formule donnée
la formule équivalente à cette formule et mise sous forme d’une disjonction de
conjonctions élémentaires.
Exercice 1.13. Mettre sous forme normale disjonctive les formules suivantes :
(A) : (a ⇒ b) ∧ (c ∨ (a ∧ d)).
(B) : (p ⇒ (q ⇒ r)) ⇒ (p ∧ q ⇒ r).
Définition 1.5. On appelle forme normale conjonctive d’une formule donnée
la formule équivalente à cette formule et mise sous forme d’une conjonction
de clauses.
Exemple 1.14. Mettre sous forme normale conjonctive les formules suivantes :
(A) : (a ⇒ b) ∧ (c ∨ (a ∧ d)).
(B) : (p ⇒ (q ⇒ r)) ⇒ (p ∧ q ⇒ r).
(C) : ((p ∨ q ∨ r) ∧ (q ⇒ p)) ⇒ (¬q ⇒ r)
 11

1.7 Formalisation de textes en logique propositionnelle

Considérons les arguments suivants :

Si Didier est l’auteur de ce bruit, il est stupide ou bien dépourvu de principes.
Didier n’est ni stupide ni dépourvu de principes. Donc Didier n’est pas l’au-
teur de ce bruit.
Pour nous convaincre de la validité de ce raisonnement, on le décompose
comme suit en posant :
d : Didier est l’auteur de ce bruit
s : Didier est stupide
p : Didier est dépourvu de principes
1. Formaliser l’argument ci-dessus à l’aide des variables d, s et p.
2. Dire si ce raisonnement est valide ou non.

Exercice 1.15. On considère les prémisses suivantes :

a. Si Pierre est grand ou bien Marie est la sœur de Jean, alors Jean n’est
pas le fils de Pierre .
b. Si Pierre n’est pas grand, alors Jean est le fils de Pierre.
c. Si Jean est le fils de Pierre alors Marie est la sœur de Jean.
1. Traduire en logique des assertions chacune des prémisses ci-dessus. On uti-
lisera les variables suivantes : p : Pierre est grand, q : Jean est le fils de Pierre
et r : Marie est la sœur de Jean.
2. Des prémissess ci-dessus, lesquelles des conclusions suivantes sont cor-
rectes ? Justifier.
(A) Si Marie est la sœur de Jean alors Pierre est grand ou Jean n’est pas
le fils de Pierre.
(B) Marie est la sœur de Jean ou Pierre est grand.
3. Nier (donner le négation de) la conclusion (A) .
 C HAPITRE DEUX

L OGIQUE DES PRÉDICATS

2.1 Introduction

Dans la logique des propositions on considère une proposition comme un

tout, représenté par une variable, dont on ne détaille pas le contenu. On ne
s’intéresse qu’à la vérité ou à la fausseté d’une proposition. La logique propo-
sitionnelle n’est pas assez expressive pour nous permettre d’exprimer toutes
les propositions qui nous intéressent en mathématiques comme celles-ci par
exemple : Il y a un entier naturel plus petit que tous les autres ; Tous les
nombres réels ne sont pas des rationnels. La logique des prédicats, également
appelée logique du premier ordre, regarde les propositions de plus près. En
logique des prédicats les variables représentent non pas des propositions mais
des objets sur lesquels portent les prédicats. Etant donné un ensemble E, un
prédicat de variable x ∈ E est une application définie sur une partie D(E)
(ensemble de définition de P ) et dont les valeurs sont des assertions. On dit
aussi que c’est une fonction assertionnelle. Le nombre de variable d’un pré-
dicat est son arité. Comme dans le cas de la logique propositionnelle, à partir
d’un ou de plusieurs prédicats on peut créer de nouveaux prédicats grâce aux
connecteurs logiques.

2.2 Les quantificateurs

Définition 2.1. Un quantificateur est un connecteur logique binaire pour le-

quel les propriétés d’associativité, de commutativité et d’existence d’élément
neutre sont satisfaites.

Logique et Théorie des Ensembles Raymond HOUNNONKPE©MI-ENS 2023

 13

Remarque 2.1. L’un des rôles des quantificateurs est de transformer les pré-
dicats en assertions. Par exemple, soit P le prédicat d’arité 1 défini sur R par
P (x) : x2 + x − 1 < 0.
L’expression ” x2 + x − 1 < 0 ” n’est pas une assertion car sa valeur de vérité
dépend du réel choisi. On a P (0) qui est une assertion vraie tandis que P (1)
est une assertion fausse.
Par contre l’énoncé : Pour tout réel x, x2 + x − 1 < 0 est une assertion qui
est d’ailleurs fausse.
Si le prédicat comporte plusieurs variables, il faut que toutes les variables
soient liées par des quantificateurs pour que ce prédicat devienne une asser-
tion. Par exemple l’énoncé : Pour tout réel x, x2 y + x − 1 < 0 n’est pas une
assertion.
Les quantificateurs les plus utilisés sont :
• Le quantificateur existentiel ∃
• Le quantificateur universel ∀.

2.2.1 Le quantificateur existentiel

Définition 2.2. Le quantificateur existentiel exprime le fait qu’au moins un

des éléments d’un ensemble d’objets sur lequel s’exprime un prédicat vérifie
ce prédicat. Soit P un prédicat de variable x ∈ E. On écrit :

∃x ∈ E, P (x)

pour exprimer que l’assertion P (x) a la valeur Vrai pour au moins un élé-
ment x appartenant à E. Le symbole ∃ est appelé quantificateur existentiel.
Il correspond à la disjonction (le connecteur logique ∨) qui est associatif,
commutatif et admet Faux pour élément neutre.
Remarque 2.2. On écrit :
∃!x ∈ E, P (x)
pour exprimer que l’assertion P (x) a la valeur Vrai pour un et un seul élément
x appartenant à E.
Exemple 2.3. Donner la valeur de vérité des assertions suivantes :
 14

1.
∃n ∈ N, (n est pair) ∧ (n est impair).
2.
∃x ∈ R, x3 − 2x + 1 = 0.
3. p
∗
∃n ∈ N , n2 + 1 ∈ N.
4.
∃n ∈ N, (n2 est pair) ∧ (n est impair).
5.
∃!x ∈ R, ex − x − 1 = 0.

2.2.2 Le quantificateur universel

Définition 2.3. Le quantificateur universel exprime le fait que tous les élé-
ments d’un ensemble d’objets sur lequel s’exprime un prédicat vérifient ce
prédicat. Soit P un prédicat de variable x ∈ E. On écrit :

∀x ∈ E, P (x)

pour exprimer que l’assertion P (x) a la valeur Vrai pour tout élément x ap-
partenant à E. Le symbole ∀ est appelé quantificateur universel. Il correspond
à la conjonction (le connecteur logique ∧) qui est associatif, commutatif et ad-
met Vrai pour élément neutre.
Exemple 2.4. Donner la valeur de vérité des assertions suivantes :
1.
∀n ∈ N, (n est pair) ∨ (n est impair).
2.
∀x ∈ R, x3 − 2x + 1 < 0.
3. p
∀n ∈ N∗ , n2 + 2 ∈
/ N.
4.
∀n ∈ N, (n2 est pair) ∨ (n est impair).
 15

5.
∀x ∈ R, |x|−1 ≤ |x − 1|.

Exercice

I. Écrire les assertions suivantes à l’aide des quantificateurs :

1. Tout entier est pair ou impair.
2. Il y a un entier naturel plus grand que tous les autres.
3. Tout entier naturel plus grand que 1 admet au moins un diviseur premier.
4. Soit f : I −→ R une fonction numérique réelle définie sur I.
a) f est une fonction constante
b) f est majorée
c) L’équation f (x) = 0 admet une unique solution.
5. Toutes les voitures rapides sont rouges.
6. Il existe un mouton écossais dont au moins un côté est noir.
II. Soit (un )n∈N une suite de nombres réels. Traduire en langage courant (le
français ) les énoncés :
1. ∃n ∈ N, un ̸= 0
2. ∀n ∈ N, un = 1 ou un < 0
3. (∀n ∈ N, un = 1) ou (∀n ∈ N, un < 0)
4. ∀A > 0, ∃NA ∈ N, ∀n ≥ NA , un > A.

2.3 Quelques règles sur les quantificateurs

• Soit P un prédicat de variable x ∈ E, on a :

(∀x ∈ E, P (x)) ⇒ (∃x ∈ E, P (x))

C’est une conséquence directe de la définition de ces deux quantifica-

teurs.
• Soit P et Q deux prédicats dépendant d’une variable x ∈ E, on a :

∀x ∈ E, (P (x) ∧ Q(x)) ≡ (∀x ∈ E, P (x)) ∧ (∀x ∈ E, Q(x)).

∃x ∈ E, (P (x) ∨ Q(x)) ≡ (∃x ∈ E, P (x)) ∨ (∃x ∈ E, Q(x)).

 16

Par contre les assertions

∀x ∈ E, (P (x) ∨ Q(x))

et (∀x ∈ E, P (x)) ∨ (∀x ∈ E, Q(x))

ne sont pas équivalentes. Il en est de même des assertions

∃x ∈ E, (P (x) ∧ Q(x))

et (∃x ∈ E, P (x)) ∧ (∃x ∈ E, Q(x)).

• Soit P un prédicat à deux variables x ∈ E, y ∈ F on a :

(∀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))

On peut donc permuter l’ordre de deux quantificateurs de même nature
qui se suivent et dont les domaines sont indépendantes des variables de
quantification. Par contre, en règle générale, on ne peut pas permuter
l’ordre de deux quantificateurs de natures différentes qui se suivent. On
a cependant l’implication

(∃x ∈ E, ∀y ∈ F, P (x, y)) ⇒ (∀y ∈ F, ∃x ∈ E, P (x, y))

qui est vraie.

• Soit P et Q deux prédicats dépendant d’une variable x ∈ E, on a :

(∀x ∈ E, (P (x) ⇒ Q(x))) ⇒ [(∀x ∈ E, P (x)) ⇒ (∀x ∈ E, Q(x))],

(∀x ∈ E, (P (x) ⇒ Q(x))) ⇒ [(∃x ∈ E, P (x)) ⇒ (∃x ∈ E, Q(x))].

• Soit P un prédicat de variable x ∈ E, on a :

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

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

Ce sont les généralisations des lois de De Morgan.
 17

Exercice 2.5. Enoncer la négation des assertions suivantes :

1. Tout triangle rectangle possède un angle droit.
2. Dans toutes les prisons tous les détenus détestent tous les gardiens.

Exercice 2.6. Donner la valeur de vérité de chacune des assertions suivantes

puis écrire sa négation :
1. ∀x ∈ R, ∀y ∈ R, xy > 9 ⇒ (x > 3 et y > 3)
2. ∀x ∈ N, ∀y ∈ N, xy > 2 ⇒ (x > 1 ou y > 1)
3. ∀y ∈ R, ∃x ∈ R, y < x
4. ∃x ∈ R, ∀y ∈ R, y < x
5. ∀x ∈ R, ∀ϵ > 0, ((|x|< ϵ) ⇒ (x = 0))
6. ∀x ∈ R, ((∀ϵ > 0, |x|< ϵ) ⇒ (x = 0)).

2.4 Variables libres, variables liées

Les occurrences d’une variable dans une expression sont dites libres ou
liées, selon le principe suivant :
- toutes les occurrences d’une variable dans une expression E sans quantifica-
teur sont libres
- si x a une occurrence libre dans E, alors cette occurence est liée dans ∀x, E
et dans ∃x, E.

Exemple 2.7. Considérons :

E : (∀n ∈ N, ∃x ∈ R, nx2 < x) ∨ (x < 2)

Les deux occurrences de la variable x dans nx2 < x sont dans la portée (le
champ) de ∃x ∈ R ; elles sont donc liées à la quantification ∃x ∈ R. De même
la seule occurrence de la variable n dans nx2 < x est liée à la quantification
∀n ∈ N. Par contre l’occurrence de la variable x dans (x < 2) n’est pas sous
l’influence de la quantification ∃x ∈ R. C’est une occurrence libre.

Définition 2.4. - Une variable est dite libre (resp. liée) dans une expression si
au moins une de ses occurrences est libre (resp. liée) dans la dite expression.
- Une formule dont toutes les variables sont liées est une formule fermée.
 18

Remarque 2.8. • Une variable qui n’est pas libre dans une expression
n’est pas forcément liée dans la dite expression(prendre l’exemple d’une
variable n’ayant aucune occurrence dans l’expression).
• Une variable peut être à la fois libre et liée. C’est le cas de la variable
x dans l’exemple 2.7.

Proposition 2.1. Soit Q un prédicat dépendant d’une variable x ∈ E ̸= ∅ et

P un prédicat. Si la variable x n’est pas libre dans P , on a :

P ∨ (∃x ∈ E, Q(x)) ≡ (∃x ∈ E, P ∨ Q(x))

P ∨ (∀x ∈ E, Q(x)) ≡ (∀x ∈ E, P ∨ Q(x))

P ∧ (∃x ∈ E, Q(x)) ≡ (∃x ∈ E, P ∧ Q(x))
P ∧ (∀x ∈ E, Q(x)) ≡ (∀x ∈ E, P ∧ Q(x))
 C HAPITRE TROIS

Q UELQUES MÉTHODES DE
RAISONNEMENT

Une démonstration (on dit aussi une preuve) consiste à déduire qu’un énoncé
est vrai en utilisant un raisonnement logique (règles d’inférence) reposant sur
des axiomes (énoncés considérés vrais sans démonstration) ou sur des théo-
rèmes déjà démontrés.
Ce chapitre présente quelques techniques de démonstration. Le contexte per-
mettra de sélectionner la technique la mieux appropriée.-

3.1 Les méthodes directes

3.1.1 Démonstration directe de p ⇒ q

On veut montrer que p ⇒ q est vraie. On suppose que p est vrai et l’on
démontre (en se basant sur des définitions, des axiomes, des théorèmes déjà
démontrés et des règles d’inférence), qu’il s’en suit forcément que q est aussi
vrai.
Exemple 3.1. Montrer que si n est un entier impair alors n2 est aussi un entier
impair.
Exemple 3.2. Montrer que si x est un nombre réel tel que x2 < 1
alors x > −1.

3.1.2 Démonstration directe de p ∧ q

Pour démontrer p ∧ q, on montre p et on montre q.

Logique et Théorie des Ensembles Raymond HOUNNONKPE©MI-ENS 2023

 20

x+|x|
Exemple 3.3. Soit x un réel. Démontrer que : x ≤ 2 ≤ |x|

3.1.3 Démonstration directe de p ∨ q

Pour établir p ∨ q, on peut montrer que l’une des deux assertions p ou q est
vraie.
On peut également montrer que si l’une des deux propositions est fausse, alors
l’autre est vraie. Autrement dit, on montre l’une des deux implications sui-
vantes : ¬p ⇒ q ou ¬q ⇒ p.
En pratique, on utilise la deuxième méthode sauf si l’une des deux proposi-
tions est vérifiée de manière évidente

Exemple 3.4. Soit x un entier relatif. Montrer que (x est impair ou x2 est
pair).

3.1.4 Montrer une équivalence

Pour démontrer une équivalence p ⇔ q, on montre que les deux implica-

tions p ⇒ q et q ⇒ p sont vraies.

Remarque 3.5. Pour montrer que des assertions p1 , p2 , ..., pn sont deux à deux
équivalentes, on peut montrer :

(p1 ⇒ p2 ) ∧ (p2 ⇒ p3 ) ∧ ... ∧ (pn−1 ⇒ pn ) ∧ (pn ⇒ p1 ).

Exemple 3.6. Soit x un nombre réel. Montrer que (0 < x < 1) ⇔ (x2 < x)

3.1.5 Preuve de ∃x ∈ E, P (x)

Il suffit de trouver un élément x0 de l’ensemble E tel qu’on a P (x0 ). Mais

pour beaucoup de problèmes de ce type il est souvent difficile d’exhiber un
tel élément. Certains théorèmes de la théorie concernée permettent parfois de
conclure.
√ √
Exemple 3.7. Démontrer que : ∃x ∈ R, x2 + x − 1 = x.
√ √ √
Exemple 3.8. Démontrer que : ∃x ∈ R, x3 + 2x2 − 3x − 2 5 = 0.
 21

3.1.6 Preuve de ∀x ∈ E, P (x)

Pour donner une preuve directe de ∀x ∈ E, P (x), on commence par prendre

dans E un élément x quelconque mais fixé et on montre qu’on a P (x).

Remarque 3.9. Pour donner une preuve directe de ∀x ∈ E, P (x) ⇒ Q(x),

On suppose que x est un élément arbitraire de E tel que P (x) est vrai. On
démontre qu’il s’en suit forcément que Q(x) est vrai aussi.

Exemple 3.10. Démontrer que : ∀(x, y) ∈ R2 , |xy|≤ 21 (x2 + y 2 )

3.1.7 Raisonnement par l’utilisation d’un contre exemple

Si l’on veut montrer qu’une assertion du type : ∀x ∈ E, P (x) est vraie,

alors pour chaque x de E, il faut montrer que P (x) est vraie. Par contre, pour
montrer que cette affirmation est fausse, il suffit de trouver un x de E tel que
P (x) soit fausse. Trouver un x, c’est trouver un contre-exemple à l’assertion
∀x ∈ E, P (x).

Exemple 3.11. Démontrer que l’assertion suivante est fausse :

Tout entier positif est somme de trois carrés d’entiers.

Exemple 3.12. Soient (un )n∈N et (vn )n∈N deux suites qui n’admettent pas de
limite, alors la suite (un vn )n∈N n’admet pas de limite. Cette affirmation est-elle
vraie ?

3.2 Les méthodes indirectes

3.2.1 Raisonnement par contraposition

Le raisonnement par contraposée permet de démontrer qu’une implication

du type :p ⇒ q est vrai. Ce raisonnement est basé sur l’équivalence entre
l’assertion p ⇒ q et l’assertion ¬q ⇒ ¬p. Donc si l’on souhaite montrer
l’assertion p ⇒ q, on montre en faite que si ¬q est vraie alors ¬p est vraie.

Exemple 3.13. Montrer que si n2 est un entier impair alors n est aussi un
entier impair.
 22

3.2.2 Raisonnement par l’absurde

Pour établir qu’un énoncé p est vrai, on suppose que p est faux et l’on
montre que cela entraîne une contradiction. Ainsi, p doit être vrai. C’est une
conséquence de la règle logique :
(¬p ⇒ f aux) ≡ p.
√
Exemple 3.14. Démontrer que 3 n’est pas un nombre rationnel.

3.2.3 Raisonnement par disjonction de cas

On sépare les données en différentes classes possibles selon leur compor-

tement (en d’autres termes, on étudie tout les cas possibles). C’est un raison-
nement courant en arithmétique.
n(n+1)
Exemple 3.15. Démontrer que pour tout entier n, 2 est un entier.
Exemple 3.16. Soit a, b, c trois réels. Notons max(a, b) le maximum entre les
deux réels a et b.
Montrer que si a < c et b < c alors max(a, b) < c.

3.2.4 Raisonnement par analyse-synthèse

le raisonnement par analyse-synthèse est une méthode de détermination de

l’ensemble des solutions d’un problème et de rédaction d’une démonstration
de cette résolution. Un raisonnement par analyse-synthèse se déroule en deux
étapes :
1. L’analyse : On raisonne sur une hypothétique solution au problème et on
accumule des déductions de propriétés qu’elle doit vérifier, du seul fait qu’elle
est solution ;
2. La synthèse : On examine tous les objets vérifiant les conditions néces-
saires précédemment accumulées (ce sont les seuls candidats pouvant être des
solutions) et on détermine, parmi eux, lesquels sont réellement des solutions.
Exemple 3.17. Déterminer toutes les applications f définies sur R satisfai-
sant :
∀x ∈ R, f (x) + xf (1 − x) = 1 + x.
 23

3.2.5 Raisonnement par induction mathématique (récurrence)

Le principe de récurrence permet de montrer qu’une assertion

de la forme : ∀n ≥ n0 , P (n), dépendante de n est vraie pour tout n entier
naturel supérieur ou égal à n0 . La démonstration se déroule en 3 étapes :
Initialisation : On prouve que P (n0 ) est vraie.
Hérédité : On suppose n ≥ n0 donné avec P (n) vrai et on démontre que
l’assertion P (n + 1) est vrai.
Conclusion : on rappelle que par le principe de récurrence, P (n) est vrai pour
tout n entier naturel supérieur ou égal à n0 .

Exemple 3.18. Montrer par récurrence que : ∀n ∈ N, 7 divise 32n+1 + 2n+2 .

Il existe des variantes importantes du théorème de récurrence. Citons en

deux :

Récurrence double

Soit Pn un prédicat sur N . On suppose qu’il existe un entier n0 tel que :

— Pn0 et Pn0 +1 sont vrais
— ∀n ≥ n0 , [Pn et Pn+1 ] ⇒ Pn+2
alors Pn est vrai pour tout n ≥ n0 .

Récurrence forte

Soit Pn un prédicat sur N . On suppose qu’il existe un entier n0 tel que :

— Pn0 est vrai
— ∀n ≥ n0 , [∀k ∈ {n0 , nn0 +1 , ..., n}, Pk ] ⇒ Pn+1
alors Pn est vrai pour tout n ≥ n0 .

Exemple 3.19. 1. Soit (un )n∈N la suite donnée par :



 u0 = 1
u1 = 2
 u2
∀n ≥ 0, un+2 = un+1

n
 24

Prouver que : ∀n ∈ N, un = 2n .
2. On définit une suite réelle (un )n∈N par : u0 = 0, u1 = 3 et
n
∗ 2X
∀n ∈ N , un+1 = uk .
n
k=0

Montrer que : ∀n ∈ N, un = 3n.

Exemple 3.20. On définit une suite réelle (un )n∈N par : u0 = 1 et

n
X
∀n ∈ N, un+1 = uk .
k=0

Montrer que : ∀n ∈ N∗ , un = 2n−1 .

 C HAPITRE QUATRE

T HÉORIE DES ENSEMBLES

4.1 Notion d’ensemble

La notion d’ensemble est l’une des notions fondamentales et des plus fré-
quemment employées en mathématiques. Dans tous les domaines des ma-
thématiques il est question d’ensembles, ainsi par exemple l’ensemble des
entiers positifs, l’ensemble des nombres complexes, l’ensemble des points
d’un cercle, l’ensemble des fonctions continues, l’ensemble des fonctions in-
tégrables, etc.
L’objet de la théorie des ensembles est l’étude des propriétés des ensembles
du point de vue le plus général ; la généralité est un aspect essentiel de la
théorie des ensembles. En géométrie, on considère des ensembles dont les
éléments sont des points, en arithmétique, des ensembles dont les éléments
sont des nombres, dans le calcul des variations, des ensembles de fonctions ou
de courbes ; mais dans la théorie des ensembles, on s’occupe des propriétés
générales des ensembles indépendamment de la nature des éléments qui les
constituent.
La théorie des ensembles est généralement considérée comme fondamen-
tale ; ses objets, les ensembles, sont donc non pas définis, mais caractérisés
par leurs propriétés de base, appelées axiomes de la théorie des ensembles.
Intuitivement, un ensemble est une collection d’objets.
La théorie des ensembles repose sur deux sortes de prédicats à deux va-
riables (relations) : la relation d’appartenance ∈ et la relation d’égalité =. Ces
deux relations sont assujetties à un certains nombres d’axiomes qui permettent
de construire des ensembles et des relations de plus en plus complexes.

Logique et Théorie des Ensembles Raymond HOUNNONKPE©MI-ENS 2023

 26

4.1.1 L’axiome d’extensionnalité

Le principal concept de la théorie des ensembles est celui d’appartenance ;

comme les ensembles, ce concept n’est pas défini, mais caractérisé par ses
propriétés. Il intervient dans la proposition "x appartient à E " ou "x est élé-
ment de E", notée (x ∈ E), qui intuitivement signifie que parmi les objets
dont l’ensemble E est la collection, il y a l’objet x. La négation de la pro-
position (x ∈ E) est notée (x ∈ / E). L’axiome d’extensionnalité affirme
qu’un ensemble est complètement déterminé par la donnée de ses éléments.
Il s’énonce :
Deux ensembles sont égaux si et seulement s’ils ont les mêmes éléments.
Il affirme que la notion d’ensemble ne comporte pas autre chose que ce qui est
spécifié par la donnée des éléments. Il en résulte qu’étant donnés n objets ma-
thématiques x1 , x2 , ..., xn il existe un ensemble et un seul E dont les éléments
sont exactement les objets x1 , x2 , ..., xn . On écrit :

E = {x1 , x2 , ..., xn }

4.1.2 L’axiome de sélection.

Cet axiome sert à rendre légitime un mode de définition d’un ensemble B,

à partir d’un autre ensemble A et d’un énoncé conditionnel S(x). Cet axiome,
aussi appelé axiome de compréhension, s’énonce :
Si A est un ensemble, et S(x) un énoncé conditionnel, il existe un ensemble
B dont les éléments sont exactement les éléments x de A pour lesquel S(x)
est vraie. Cet ensemble est noté {x ∈ A, S(x)}.

4.1.3 Axiome d’existence du vide

Il existe un ensemble noté ∅ tel que l’assertion x ∈ ∅ soit fausse quel

que soit l’objet mathématique x.
L’ensemble ∅ est appelé l’ensemble vide.
 27

4.1.4 Sous-ensemble

Si tous les éléments d’un ensemble A sont aussi des éléments d’un en-
semble E, on dit que A est un sous-ensemble de E, et on écrit :

A ⊂ E.

On dit aussi que A est une partie de E. Ainsi on a :

(A ⊂ E) ⇔ (∀x ∈ A, x ∈ E).

L’ensemble de toutes les parties d’un ensemble E est aussi un ensemble noté
P(E). On a :
(A ∈ P(E)) ⇔ (A ⊂ E).
L’inclusion d’ensembles possède les propriétés suivantes.

Proposition 4.1. Soit E un ensemble et A, B et C des parties de E.

i) ∅ ⊂ E
ii) A ⊂ A
iii) (A = B) ⇔ (A ⊂ B) ∧ (B ⊂ A)
iv) (A ⊂ B) ∧ (B ⊂ C) ⇒ (A ⊂ C)
v) Si A ⊂ B alors P(A) ⊂ P(B).

4.2 Opérations de base sur les ensembles

4.2.1 Complémentaire

Soit E un ensemble et A une partie de E. Le complémentaire de A dans E

(noté CE A ou A ou Ac ou encore E\A) est le sous-ensemble de E constitué
des éléments qui n’appartiennent pas à A.

Exemple 4.1. Si E = {0; 1; 2; 3; 4; 5; 6; 7} et A = {0; 1; 3; 4}, on a :

Ac = {2; 5; 6; 7}

Proposition 4.2. Soit E un ensemble et A, B des parties de E.

i) CE ∅ = E
 28

ii) CE E = ∅
iii) CE (CE A) = A
iv) (A ⊂ B) ⇒ (CE B ⊂ CE A).

4.2.2 Intersection, union et différence symétrique

Intersection d’ensembles

On entend par intersection (ou produit ensembliste) de deux ensembles A

et B la partie commune de ces ensembles, c’est-à-dire l’ensemble qui contient
les éléments appartenant simultanément à A et à B, et seulement ceux-là. On
note l’intersection des ensembles A et B par A ∩ B. Si A et B sont des parties
d’un ensemble E, on a :

A ∩ B = {x ∈ E, (x ∈ A) ∧ (x ∈ B)}.

On a A ∩ B = B ∩ A.

Union d’ensembles

On entend par réunion (ou somme ensembliste) de deux ensembles A et B

l’ensemble constitué de tous les éléments de A et de tous les éléments de B et
qui ne contient pas d’autres éléments. On note la réunion de deux ensembles
A et B par A ∪ B. Si A et B sont des parties d’un ensemble E, on a :

A ∪ B = {x ∈ E, (x ∈ A) ∨ (x ∈ B)}.

Remarquons que A ∪ B = B ∪ A.

Différence symétrique

La différence symétrique de deux ensembles A et B d’un ensemble E est

l’ensemble noté A∆B défini par :

A∆B = (A\B) ∪ (B\A)

où A\B = A ∩ CE B.
L’intersection et la réunion d’ensembles vérifient les propriétés suivantes.
 29

Proposition 4.3. Soit E un ensemble et A, B et C des parties de E.

• A ⊂ A ∪ B et B ⊂ A ∪ B
• A ∩ B ⊂ A et A ∩ B ⊂ B
• A ∩ CE A = ∅ et A ∪ CE A = E
• (A ∩ B) ∩ C = A ∩ (B ∩ C)
• (A ∪ B) ∪ C = A ∪ (B ∪ C)
• ((A ⊂ B) ∧ (A ⊂ C)) ⇔ (A ⊂ B ∩ C)
• ((A ⊂ C) ∧ (B ⊂ C)) ⇔ (A ∪ B ⊂ C)

Exercice 4.2. Soit E un ensemble et A, B et C des parties de E.

Montrer que :
a. CE (A ∪ B) = (CE A) ∩ (CE B)
b. CE (A ∩ B) = (CE A) ∪ (CE B)
c. A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
d. A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
e. A∆B = A∆B
f. A∆B = A∆B = A∆B.

4.3 Produit cartésien d’ensembles

Le produit cartésien de deux ensembles A et B est l’ensemble (noté A × B)

de tous les couples (x, y), avec x élément de A et y élément de B. Autrement
formulé, on a
A × B = {(x, y)|x ∈ A et y ∈ B}.
Rappelons que deux couples (a, b) et (c, d) sont égaux, si et seulement si on a
les deux égalités a = c et b = d.
Plus généralement, on définit le produit cartésien des ensembles A1 , ..., An par

A1 × A2 × ... × An = {(x1 , ..., xn )|xi ∈ Ai ; 1 ≤ i ≤ n}.

Lorsque Ai = A, pour tous les i, on obtient la puissance cartésienne n-ième,

An = A
| × A {z
× ... × A}
n fois
 30

Les éléments de An sont les n-uplets (x1 , ..., xn ), d’éléments de A. En particu-

lier, pour A = R et n ≥ 1 ; on obtient l’ensemble Rn qui est constitué de tous
les n-uplets (x1 , ..., xn ) de réels.

Remarque 4.3. ((A × B) = ∅) ⇔ ((A = ∅) ∨ (B = ∅))

4.4 Ensembles équipotents, finis, dénombrables

Définition 4.1. • Un ensemble A est fini s’il est vide ou s’il est en bijection
avec le sous-ensemble {1, 2, ..., n} de N. L’entier n est le cardinal de A
et on le note Card(A). On convient que Card(∅) = 0. Un ensemble qui
n’est pas fini est dit infini.
• Un ensemble A est dénombrable s’il est en bijection avec N (ou plus
généralement une partie infinie de N).
• Un ensemble A est au plus dénombrable s’il est soit fini soit dénom-
brable.
• Deux ensembles A et B sont équipotents s’il existe une bijection de A
sur B.

Propriété 4.4. Soit A et B deux ensembles finis alors :

1. A ∪ B est fini et

Card(A ∪ B) = Card(A) + Card(B) − Card(A ∩ B)

2. A × B est fini et

Card(A × B) = Card(A) × Card(B)

3. P(A) est fini et

Card(P(A)) = 2Card(A)
4. Le nombre d’application de A à valeurs dans B est [Card(B)]Card(A) .

Exercice 4.5. Justifier que N, Z et Q sont dénombrables mais que R n’est pas
dénombrable.

Proposition 4.4. Soit E et F deux ensembles et f : E −→ F une application.

 31

i. Si E est fini et f est surjective alors F est fini et Card(F ) ≤ Card(E)

avec égalité si et seulement si f est une bijection.
ii. Si F est fini et f est injective alors E est fini et Card(E) ≤ Card(EF )
avec égalité si et seulement si f est une bijection.
La proposition suivante résume quelques propriétés essentielles des en-
sembles dénombrables.
Proposition 4.5. i) Toute partie d’un ensemble dénombrable est au plus
dénombrable.
ii) Tout produit cartésien fini (en nombre de facteurs) d’ensembles dénom-
brables est dénombrale.
iii) Soit E un ensemble dénombrable et f : E −→ F une application
surjective. Alors F est au plus dénombrable.
Nous achevons cette section avec deux résultats fondamentaux : le théo-
rème de Cantor-Berstein et le théorème de Cantor.
Théorème 4.6. (Cantor-Berstein ) Soient A et B deux ensembles. On suppose
qu’il existe une application injective de A vers B et une application injective
de B vers A. Alors A et B sont en bijection.
Exercice 4.7. En utilisant le théorème de Cantor-Berstein, montrer que N2 est
en bijection avec N.
Théorème 4.8. (Cantor) Il n’existe pas d’application surjective d’un ensemble
E sur l’ensemble P(E) de ses parties.
Exercice 4.9. 1. Justifier que l’ensemble P(N) n’est pas dénombrable.
2. En déduire que l’ensemble {0, 1}N des applications de N dans {0, 1} n’est
pas dénombrable.

4.5 Applications

Définition 4.2. On considère deux ensembles E et F .

Une application f : E −→ F est une correspondance qui à tout élément
x ∈ E associe un unique élément noté f (x) de l’ensemble F .
 32

Remarque 4.10. On définit plus formellement une application f : E −→ F

par son graphe. C’est une partie G ⊂ E × F vérifiant la propriété :

∀x ∈ E, ∃!y ∈ F, (x, y) ∈ G.

On dit que cet unique élément y = f (x) est l’image de l’élément x par l’ap-
plication f .

Parmi les propriétés particulières des applications, l’injectivité et la surjec-

tivité sont très certainement des notions importantes.
Une application f : A −→ B est dite
• injective si et seulement si pour chaque élément y de B, il existe au plus
un élément x de A tel que f (x) = y. Autrement dit

∀x ∈ A, ∀y ∈ A, (f (x) = f (y)) ⇒ (x = y)

• surjective si et seulement si pour chaque élément y de B, il existe au

moins un élément x de A tel que f (x) = y. Autrement dit

∀y ∈ B, ∃x ∈ A, y = f (x).

• bijective si elle est à la fois injective et surjective. Autrement dit

∀y ∈ B, ∃!x ∈ A, y = f (x).

Ainsi à tout y ∈ B on associe un unique x ∈ A noté f −1 (y). On définit

ainsi une application f −1 de B dans A appelée bijection réciproque de
f et qui vérifie

f ◦ f −1 = IdF et f −1 ◦ f = IdE .

Exercice 4.11. Soit A = {(x, y) ∈ R2 , x ≤ y} et B = {(s, p) ∈ R2 , 4p ≤ s2 }.

Justifier que l’application

f : A −→ B
(x, y) 7−→ (x + y, xy)

est bijective.
 33

Proposition 4.6. On considère deux applications f : E −→ F et

g : F −→ G. On a les propriétés suivantes :
1. f, g injectives ⇒ g ◦ f injective.
2. f, g surjectives ⇒ g ◦ f surjective.
3. g ◦ f injective ⇒ f injective.
4. g ◦ f surjective ⇒ g surjective.
5. f, g bijectives ⇒ g ◦ f bijective et on a (g ◦ f )−1 = f −1 ◦ g −1 .
Exercice 4.12. Soient f : E −→ F et g : F −→ E deux applications telles
que g ◦ f = IdE et f ◦ g = IdF . Montrer que f est bijective et que g = f −1 .
Définition 4.3. (Image directe et image réciproque) Soit f : E −→ F.
• Si A ⊂ E, l’image directe de la partie A par l’application f est le
sous-ensemble de F noté f (A) et défini par
f (A) = {y ∈ F |∃x ∈ A, y = f (x)}.
• Si B ⊂ F , l’image réciproque de la partie B par l’application f est le
sous-ensemble de E noté f −1 (B) et défini par
f −1 (B) = {x ∈ E|f (x) ∈ B}
Exercice 4.13. Soit f : E −→ F une application, A ⊂ E et B ⊂ F .
1. Montrer que A ⊂ f −1 (f (A)) et que f (f −1 (B)) ⊂ B.
2. Montrer que si f est injective alors A = f −1 (f (A)).
3. Montrer que si f est surjective alors B = f (f −1 (B)).
Proposition 4.7. Soit f : E −→ F une application. Soit (Ai )i∈I une famille
de parties de E et (Bi )i∈J une famille de parties de F . On a :
1. [  [
f Ai = f (Ai )
i∈I i∈I
2. \  \
f Ai ⊂ f (Ai )
i∈I i∈I
3. [  [
f −1 Bi = f −1 (Bi )
i∈J i∈J
 34

3. \  \
−1
f Bi = f −1 (Bi )
i∈J i∈J

4.6 Relations binaires

Définition 4.4. Soient E et F deux ensembles. Une relation binaire R de E

vers F est un prédicat à deux variables (x, y) ∈ E × F . Autrement dit, une
relation binaire de E vers F est une propriété que chaque couple (x, y) ∈
E × F est susceptible d’avoir ou non. Si (x, y) ∈ E × F est tel que R(x, y)
est vrai, on écrit xRy et on dit que x est en relation avec y. Le graphe de la
relation est l’ensemble
Γ = {(x, y) ∈ E × F, R(x, y)}.

Une relation binaire sur E est une relation binaire de E vers E.

Exemple 4.14. 1. Sur tout ensemble E l’égalité (=) sur E est une relation
binaire. Son graphe est Γ = {(x, x)|x ∈ E}, la diagonale de l’ensemble E.
2. Si X est un ensemble, l’inclusion (⊂) est une relation binaire sur l’ensemble
E = P(X) des parties de X.
Définition 4.5. (Propriétés d’une relation binaire sur un ensemble.)
Soit R une relation binaire sur un ensemble E.
— R est réflexive si pour tout x ∈ E , on a xRx ;
— R est symétrique si pour tout x, y ∈ E , on a (xRy) ⇒ (yRx) ;
— R est antisymétrique si pour tout x, y ∈ E, (xRy et yRx) ⇒ x = y ;
— R est transitive si pour tout x, y, z ∈ E, (xRy et yRz) ⇒ (xRz).
Exercice 4.15.
Préciser les propriétés des relations binaires définies dans l’exemple 4.14.

4.6.1 Relation d’équivalence

Définition 4.6. Une relation d’équivalence sur un ensemble E est une relation
binaire définie sur E qui est réflexive, symétrique et transitive.
 35

Exemple 4.16. 1. Le parallélisme est une relation d’équivalence sur l’en-

semble des droites du plan.
2. Soient E et F deux ensembles, et f une application de E dans F . La rela-
tion sur E définie par aRb ⇔ f (a) = f (b) est une relation d’équivalence sur
E.
Définition 4.7. Soit R une relation d’équivalence sur un ensemble E et x ∈ E.
La classe (d’équivalence) de x est
x = {y ∈ E, xRy}.
Deux éléments appartenant à la même classe sont dits équivalents. L’ensemble
des classes d’équivalence noté E/R est appelé ensemble quotient. L’applica-
tion
p : E −→ E/R
x 7−→ x
est appelée application quotient ou surjection canonique.
Exercice 4.17. Soit R une relation d’équivalence sur un ensemble E et soient
x, y ∈ E. Montrer que les propositions suivantes sont équivalentes :
p1 : xRy
p2 : x = y
p3 : x et y ne sont pas disjoints.
Théorème 4.18. Soit R une relation d’équivalence sur un ensemble non vide
E. L’ensemble des classes d’équivalence suivant R forme une partition de E.
Réciproquement, toute partition (Ai )i∈I d’un ensemble non vide E induit une
relation d’équivalence dont les classes d’équivalence sont les ensembles Ai .
Proposition 4.8. Soit f : E −→ F une application et R une relation d’équi-
valence sur E. Soit p : E −→ E/R. Alors il existe une application
f : E/R −→ F telle que f = f ◦ p si et seulement si f est compatible avec
R (c’est-à-dire ∀(a, b) ∈ E 2 , aRb ⇔ f (a) = f (b)). Dans ce cas un tel f est
uniquement déterminé par f : si x ∈ E/R, on a f (x) = f (x) et on dit que
f passe au quotient à R et que f est déduite de f par passage au quotient
modulo R.
 36

4.6.2 Relation d’ordre

Définition 4.8. Une relation d’ordre sur un ensemble E est une relation bi-
naire définie sur E qui est réflexive, antisymétrique et transitive. Le couple
(E, R) est appelé ensemble ordonné.
Exemple 4.19. 1. Sur l’ensemble R, la relation usuelle ≤ est une relation
d’ordre.
2. Si X est un ensemble, l’inclusion (⊂) est une relation d’ordre sur l’en-
semble E = P(X) des parties de X.
Remarque 4.20. Pour désigner une relation d’ordre on utilisera souvent le
symbole ≤.
Définition 4.9. Un ensemble ordonné (E, ≤) est dit totalement ordonné (ou
que l’ordre est total) si deux éléménts quelconques de E sont comparables,
c’est-à-dire,
∀(x, y) ∈ E 2 , (x ≤ y) ∨ (x ≤ y).
Si l’ordre n’est pas total, on dit qu’il est partiel.
Exercice 4.21. Pour chacune des relations d’ordre de l’exemple 4.19, dire si
l’ordre est total ou partiel.
Définition 4.10. Soit (E, ≤) un ensemble ordonné et A ⊂ E.
— Un élément M ∈ E (resp. m ∈ E) est majorant (resp. minorant) de A
si, pour chaque x ∈ A, on a x ≤ M (resp. m ≤ x). Si A a au moins un
minorant (resp. un majorant), on dit que A est minoré (resp. majoré).
— Un élément β ∈ E (resp. α ∈ E) est le plus grand élément (resp. plus
petit élément) de A si, β ∈ A et β est un majorant de A (resp. α ∈ A et
α est un minorant de A).
— Un élément M ∈ A (resp. m ∈ A) est maximal (resp. minimal) dans A
si, pour chaque x ∈ A, M ≤ x entraîne M = x (resp.x ≤ m entraîne
m = x).
— Un élément µ ∈ E (resp. ν ∈ E) est borne supérieure (resp. borne
inférieure) de A si l’ensemble des majorants de A admet µ comme plus
petit élément (resp. l’ensemble des minorants de A admet ν comme plus
grand élément).
 37

— L’ensemble (E, ≤) est bien ordonné si tout sous-ensemble non vide de

E admet un plus petit élément. L’ordre d’un ensemble bien ordonné est
dit un bon ordre.

Remarque 4.22. Si un ensemble (E, ≤) est bien ordonné alors il est totale-
ment.

Exercice 4.23. On considère la relation de divisibilité dans N∗ .

Soit A = {2, 4, 5, 8, 13}.
1. A est-il majoré ? minoré ?
2. Préciser s’ils existent le plus petit élément et le plus grand élément de A.
3. Préciser les éléments minimaux et maximaux dans A.

Théorème 4.24. Toute partie non vide de N∗ admet un plus petit élément (pour
l’ordre usuel ≤).

Nous finissons ce chapitre par deux théorèmes importants de la théorie

des ensembles qui ont diverses applications (en algèbre et en topologie par
exemple).

Théorème 4.25. (Théorème de Zermelo) Tout ensemble peut être muni d’une
relation de bon ordre.

Théorème 4.26. (Théorème de Zorn) Soit (E, ≤) un ensemble ordonné tel

que toute partie T de E qui est totalement ordonnée admet un majorant (on
dit parfois que E est inductif). Alors E admet un élément maximal.
 Bibliographie

Logique et Théorie des Ensembles Raymond HOUNNONKPE©MI-ENS 2023