M ATHÉMATIQUES DISCRÈTES

(adapté de)
Mathieu S ABLIK
 Table des matières

I Elé ments de logique 3

I.1 Faire des mathématiques... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
I.2 Un peu de vocabulaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
I.3 Calcul propositionnel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
I.3.1 Négation, “et”, “ou” . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
I.3.2 Equivalence et implication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
I.3.3 Règles de calcul . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
I.4 Quantificateurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
I.4.1 Prédicats et quantificateurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
I.4.2 Calculs avec un quatificateurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
I.4.3 Calculs avec plusieurs quantificateurs . . . . . . . . . . . . . . . . . . . . . . . 9
I.5 Raisonnements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
I.5.1 Raisonnement déductif . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
I.5.2 Raisonnement par contraposée . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
I.5.3 Raisonnement par l’absurde (ou tiers exclu) . . . . . . . . . . . . . . . . . . . 10
I.5.4 Equivalences et conditions né cessaires/suffisantes . . . . . . . . . . . . . . . 11

II Introduction à la théorie des ensembles 13

II.1 Notions sur les ensembles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
II.1.1 Construction par extension et compréhension . . . . . . . . . . . . . . . . . . 13
II.1.2 Principales règles de fonctionnement . . . . . . . . . . . . . . . . . . . . . . . 13
II.1.3 Représentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
II.2 Sous-ensembles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
II.2.1 Inclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
II.2.2 Ensemble des parties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
II.3 Opérations sur les ensembles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
II.3.1 Union et Intersection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
II.3.2 Différence et complémentaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
II.3.3 Produit cartésien . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
II.4 Exemple : l’ensemble des mots sur un alphabet fini . . . . . . . . . . . . . . . . . . . 16

III Fonctions et applications 19

III.1 Premières notions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
III.1.1 Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
III.1.2 Modes de représentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
III.1.3 Composition d’applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
III.1.4 Applications particulières . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
III.2 Propriétés des applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
III.2.1 Injection et surjection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
III.2.2 Bijection et application réciproque . . . . . . . . . . . . . . . . . . . . . . . . . 24
TABLE DES M ATIÈRES 2

IV Cardinalité 27
IV.1 Cardinalité des ensembles finis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
IV.1.1 Ensembles de même cardinalité . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
IV.1.2 Cardinal d’un ensemble fini . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
IV.1.3 Principe des tiroirs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
IV.2 Dénombrement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
IV.2.1 Dénombrement et opération sur les ensembles . . . . . . . . . . . . . . . . . . 29
IV.2.2 Arrangements et combinaisons . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
IV.3 Cas des ensembles infinis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
IV.3.1 Définition et premiers exemples d’ensembles dénombrables . . . . . . . . . . 35
IV.3.2 Critères de dénombrabilité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
IV.3.3 Ensembles non dénombrables . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
IV.3.4 Théorème de Cantor-Schröder-Bernstein . . . . . . . . . . . . . . . . . . . . . 37

V Relations sur les ensembles 39

V.1 Vocabulaire des relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
V.1.1 Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
V.1.2 Modes de représentations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
V.1.3 Quelques notions proches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
V.2 Propriétés sur les relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
V.3 Relations d’équivalence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
V.3.1 Définition et exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
V.3.2 Classes d’équivalence et partition . . . . . . . . . . . . . . . . . . . . . . . . . 43
V.3.3 Ensemble quotient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

VI Relations d’ordre 45
VI.1 Premières notions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
VI.1.1 Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
VI.1.2 Exemples de relations d’ordre classiques . . . . . . . . . . . . . . . . . . . . . 45
VI.1.3 Mode de représentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
VI.1.4 Fonctions croissantes et décroissantes . . . . . . . . . . . . . . . . . . . . . . . 46
VI.2 Bornes d’un ensemble . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
VI.3 Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
VI.3.1 Ordre bien fondé . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
VI.3.2 Application à l’étude de la terminaison d’algorithme . . . . . . . . . . . . . . 48
VI.3.3 N
et le principe de récurrence . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
VI.3.4 Principe d’induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
VI.3.5 Définition inductive . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
 Chapitre I
Elé ments de logique

L’objet de ce chapitre et de mettre en lumière les opérations logiques à l’œuvre dans tout rai-
sonnement mathématique. Il pourra sembler abstrait ou formel dans un premier temps, par oppo-
sition à la logique qui semble ne devoir relever que du seul bon sens. Pour autant, il est tout à fait
fondamental puisqu’il est au cœur même de toute activité mathématique.
Aussi, s’efforcer de formaliser ses propres raisonnements pour les voir s’articuler en fonctions
des principes fondamentaux de ce chapitre est essentiel : cela devient rapidement un confort de
pensée, et la rigueur mathématique se transforme alors en un outil pour explorer l’intuition.

I.1 Faire des mathématiques...

Pour faire des mathématiques, on a besoin :
— de vérités de départ, ou axiomes : ce sont des affirmations réputées vraies qu’on ne cherche
pas à justifier.
— de règles de logique pour transformer et combiner des énoncés afin d’en obtenir de nou-
veaux, c’est la notion de démonstration.
Un théorème est donc un énoncé relié par des déductions logiques aux axiomes de départ.
Remarque I.1. Contrairement à une idée reçue, les mathématiques n’ont donc pas pour objet d’éta-
blir des vérités absolues, ce qui serait vain. Les “vérités” obtenues ne le sont que relativement
aux axiomes choisis au départ, qui ne manquent pas d’être discutables et discutés. Ainsi plus que
“vrai”, le discours mathématique se doit avant tout d’être cohérent.
Remarque I.2. On pense souvent que prouver un énoncé sert exclusivement à s’assurer de sa véra-
cité. De ce point de vue, il peut sembler fastidieux de donner une preuve formelle à des énoncés
dont personne ne doute, soit parce qu’ils sont “trop simples”, soit parce qu’ils sont suffisamment
anciens et célèbres pour qu’on n’en doute plus...
Mais prouver un énoncé va bien au-delà : c’est avant tout un moyen de le comprendre. Tant
qu’on n’arrive pas à en établir une preuve formelle, c’est que quelque chose reste mal compris, et
achever la preuve aura alors à coup sûr quelque chose à nous apprendre.

I.2 Un peu de vocabulaire

Axiome : C’est un énoncé supposé vrai a priori, que l’on ne cherche pas à démontrer.
Par exemple, Euclide a donné des axiomes qui permettent de faire de la géométrie (dite
géométrie euclidienne). Sans jamais définir ce qu’est une droite ou un point, il décrit les
relations qu’entretiennent ces deux types d’objets : par deux points distincts il passe une et
une seule droite, etc...
 TABLE DES M ATIÈRES 4

De même, Peano a donné des axiomes qui permettent de travailler avec les entiers natu-
rels : ils ne définissent pas ce qu’est un entier, mais comment ils se comportent (successeur,
principe de récurrence, etc...)
Proposition : (ou affirmation ou assertion) c’est un énoncé, syntaxiquement correct, mais qui peut
être vrai ou faux. Par exemple “le carré de tout nombre réel est positif”, ou “tout entier est
pair”...
Théorème : C’est une proposition dont on a démontré la véracité, c’est à dire qu’on l’a reliée par
une suite d’opération logiques aux axiomes.
Corolaire : Un corolaire d’un théorème, c’est un autre théorème qui est une conséquence facile du
premier.
Lemme : C’est un théorème qui sert à démontrer un théorème plus important.
Conjecture : C’est une proposition, dont on pense qu’elle est vraie, mais pour laquelle on n’a pas
encore trouvé de preuve.
Définition : C’est un énoncé dans lequel on décrit les particularités d’objets particuliers, auxquels
on donne un nom.
Par exemple, parmi les nombre entiers naturels, on définit les nombres premiers comme étant
ceux qui n’ont pas d’autre diviseur que 1 et eux-mêmes.
Comme une définition fournit la liste des propriétés particulières que doivent avoir a priori
tous les objets répondant à cette définition, ces propriétés particulières sont parfois appelées
abusivement “axiomes”.
Remarque I.3. Dans un cours de mathématiques, il est très courant d’employer le terme proposi-
tion dans un autre sens que celui donné ci-dessus. En effet, on l’emploie comme un synonyme de
théorème (avec souvent la nuance qu’une proposition est un théorème que l’on juge moins impor-
tant que d’autres résultats du cours qui eux sont qualifiés de théorèmes). Dans ce chapitre, nous
utiliserons le terme proposition seulement dans le sens d’assertion.

I.3 Calcul propositionnel

On rappelle qu’une proposition est un énoncé qui est soit vrai, soit faux. On peut combiner des
propositions pour en fabriquer de nouvelles : c’est l’objet de ce paragraphe.

I.3.1 Négation, “et”, “ou”

La négation d’une proposition P est la proposition qui est fausse si P est vraie, et vraie si P est
fausse. On la note non(P), P ou encore ¬ P.
On dresse la table de vérité de P :
P P
V F
F V
Remarque I.4. Attention, derrière cette évidente simplicité se cachent de nombreuses sources d’er-
reur. Beaucoup sont induites par les sous entendus de la langue courante. Par exemple, la négation
de “cet objet est blanc” n’est pas “cet objet est noir”, mais les même phénomènes peuvent se pré-
senter en mathématiques : dire qu’une fonction n’est pas la fonction nulle ne signifie pas que cette
fonction ne s’annule jamais, etc...
Soient P et Q deux propositions.
— La proposition “P et Q”, qu’on note aussi P ∧ Q, est la proposition qui est vraie si et P et Q
sont toutes les deux vraies, et fausse sinon :
P Q P∧Q
V V V
F V F
V F F
F F F
 5 Table des Matières

— La proposition “P ou Q”, qu’on note aussi P ∨ Q, est la proposition qui est vraie si au moins
une des deux propositions P ou Q est vraie, et fausse sinon :

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

Remarque I.5. On peut noter qu’il existe de subtiles différences entre les opérations logiques for-
melles, et celles utilisées dans le langage courant. Par exemple, le “et” français sous entend une
chronologie : “éplucher les légumes et les couper en rondelles” ne prend pas le même temps que
“couper les légumes en rondelles et les éplucher”.
Cet exemple a peu d’incidence, mais comme on l’a vu avec la négation, il existe de nombreux
autres sous entendus ou ambiguités dans la langue courante qui ne sont pas bienvenus dans un
raisonnement logique. C’est précisément le rôle du langage formel de séparer le discours mathé-
matique de la langue courante, et on prendra soin de ne jamais mélanger les deux.
®
P
Remarque I.6. En plus de P ∧ Q, P et Q se note aussi .
Q
Cette dernière notation (avec l’accolade) est notamment celle qui est tradionnellement utilisée
dans le cadre d’un système d’équations.

I.3.2 Equivalence et implication

Soient P et Q deux propositions. La proposition “P ⇔ Q” est vraie si P et Q sont toutes les
deux vraies, ou toutes les deux fausses.

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

L’équivalence joue donc parmi les propositions le rôle de l’égalité parmi les nombres : les ex-
pressions 3 + 2 et 5 sont distinctes, et pourtant 3 + 2 = 5. De même, si x, y sont des réels, les expres-
sions x2 + y2 = 0 et x = y = 0 sont distinctes, et pourtant équivalentes : x2 + y2 = 0 ⇔ x = y = 0.

Soient P et Q deux propositions. La proposition “P ⇒ Q” est vraie si P et Q sont toutes les

deux vraies, ou si P est fausse.
P Q P⇒Q
V V V
F V V
V F F
F F V

“P ⇒ Q” signifie donc “Si P est vraie, alors Q est vraie”.

Remarque I.7. Il peut sembler étonnant que “P ⇒ Q” soit vraie lorsque P est fausse. C’est souvent
parcequ’on confond “⇒” et “donc”. “P ⇒ Q” signifie très précisément que “si P est vrai, alors Q
aussi”. En particulier si P est fausse, on n’a aucune contrainte sur Q, et l’affirmation n’est jamais
mise en défaut !
L’exemple suivant est éclairant. On considère des nombres entiers a, b, c et d. On appelons P la
proposition “a = b et c = d” et Q la proposition “a + c = b + d”. Alors P ⇒ Q est vraie. Examinons
quelques cas qui peuvent arriver selon les valeurs de a, b, c et d.
TABLE DES M ATIÈRES 6

valeurs de a, b, c, d P Q
a=b=c=d=1 V V
a = b = c = 1, d = 2 F F
a = d = 1, b = c = 2 F V
Bien entendu, il n’est pas possible de donner des valeurs à a, b, c et d de sorte que P soit vraie et Q
soit fausse !
Remarque I.8. Insistons sur la différence entre “⇒” et “donc”. “Si j’ai la jambe cassée, je ne peux
pas courir le 100m” est très différent de “J’ai la jambe cassée, donc je ne peux pas courir le 100m”.
Dans le premier cas, je peux avoir la jambe cassée, ou pas. Dans le second, j’ai effectivement la
jambe cassée.
Les deux sens sont très différents, et on a besoin de pouvoir distinguer les deux sans ambi-
guité : c’est le rôle du symbole “⇒”. Il ne faut donc en aucun cas l’utiliser comme une abréviation
ou synonyme de “donc”, puisqu’on ne disposerait plus alors de moyen d’exprimer la relation
d’implication.
Par exemple, le raisonnement par récurrence peut se formaliser sous la forme :
®
∀n ∈ N, Pn .
P0
∀n ∈ N, (Pn ⇒ Pn+1 )
⇒

L’écriture Pn ⇒ Pn+1 ne signifie en aucune façon que Pn est vraie, mais seulement que s’il se trouve
qu’elle l’est, alors Pn+1 l’est aussi.
Théorème I.1
La relation d’implication peut s’exprimer à l’aide des opérations déjà vues :


(P ⇒ Q) ⇔ P ou Q

Démonstration : Écrivons les tables de vérité de ces deux expressions :

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

Les quatrième et cinquième colonne de cette table sont les mêmes : cela montre l’équivalence des
propositions “P ou Q” d’une part et “P ⇒ Q” d’autre part.

Corollaire I.2
Etant données deux propositions P et Q, on a


(P ⇒ Q) ⇔ P et Q

Démonstration : Comme précédemment, il suffit d’écrire les tables de vérité de ces deux expressions, et
de constater qu’elles sont les mêmes.

Théorème I.3
Etant données deux propositions P et Q, on a


(P ⇒ Q) ⇔ Q⇒P

On dit que ces deux formulations sont la contraposée l’une de l’autre.

 7 Table des Matières

Démonstration : Comme précédemment, il suffit d’écrire les tables de vérité de ces deux expressions, et
de constater qu’elles sont les mêmes.

Ainsi, pour montrer que P ⇒ Q est vraie :

— On suppose que P est vraie, et on montre alors que Q est vraie,
— ou bien, on suppose que Q est fausse, et on montre que P est fausse.
Pour montrer que P ⇒ Q n’est pas vraie :
— On montre que P est vraie et que Q est fausse.

I.3.3 Règles de calcul

On a les relations suivantes, qu’on montrera en dressant les tables de vérités :

i) P ⇔ P
ii) (P et Q) ⇔ (Q et P) (P ou Q) ⇔ (Q ou P)
iii) (P et P) ⇔ P (P ou P) ⇔ P
iv) (P et Q) et R ⇔ P et (Q et R) (P ou Q) ou R ⇔ P ou (Q ou R)
v) (P et Q) ou R ⇔ (P ou R) et (Q ou R) (P ou Q) et R ⇔ (P et R) ou (Q et R)
vi) (P et Q) ⇔ P ou Q (P ou Q) ⇔ P et Q

(On exprime parfois ces propriétés en disant que (i) “ non ” est involutive, (ii) “ et ” et “ ou ” sont
commutatives, (iv) “ et ” et “ ou ” sont associatives, (v) “ et ” et “ ou ” sont distributives l’une par
rapport à l’autre. Les expressions (vi) de la négation de “ et ” et “ ou ” sont parfois appellées lois
de Morgan.)
Autre fait important, l’implication est transitive :
Ä ä
(P ⇒ Q) et (Q ⇒ R) ⇒ (P ⇒ R)

Enfin :
(P ⇔ Q) ⇔ (P ⇒ Q et Q ⇒ P)
ce qui signifie que pour montrer une équivalence, on peut montrer séparément les implications
dans chaque sens. On dit qu’on sépare conditions nécessaire et condition suffisante :
— P ⇒ Q signifie que Q est une condition nécessaire pour que P soit vraie.
— Q ⇒ P signifie que Q est une condition suffisante pour que P soit vraie.
Quand P ⇔ Q, on dit que Q est une condition nécessaire et suffisante (parfois abrégé en CNS) pour
que P soit vraie.

I.4 Quantificateurs
I.4.1 Prédicats et quantificateurs
Définition I.1. Un prédicat P(x) sur un ensemble E est une proposition dont la valeur de vérité
dépend d’un élément x de E.

Par exemple, la proposition P(n) :“l’entier n est pair” dépend d’un entier. C’est un prédicat sur
les entiers. Si n = 2 (ou 4, 6, 218, ...) alors P(n) est vraie, si n = 3 alors P(n) est fausse.
En pratique, étant donné un prédicat P(x) dépendant d’un élément x de E, il y a deux situations
extrêmes qui sont utiles à considérer :
— celle où P(x) est toujours vrai, peu importe l’élément x de E considéré
— celle où P(x) n’est vrai pour aucun élément x de E : notons que sa négation signifie qu’il
existe (au moins) un élément x de pour lequel P(x) est vrai.
Cela conduit à introduire le formalisme suivant.
La proposition “pour tout x de E, P(x) est vraie” s’écrit en langage formel :

∀ x ∈ E, P(x).
TABLE DES M ATIÈRES 8

La proposition “il existe au moins un x de E pour lequel P(x) est vraie” s’écrit en langage
formel :
∃ x ∈ E, P(x).
La proposition “il existe un unique x de E pour lequel P(x) est vraie” s’écrit en langage formel :

∃!x ∈ E, P(x).

Remarque I.9. Contrairement aux apparences, la proposition “∀ x ∈ E, P(x)”, ne dépend pas d’un
élément x de E, puisqu’ils sont tous testés. On dit que dans cette écriture, x est une variable muette.
En particulier, on peut changer ce symbole par n’importe quoi d’autre sans changer le sens de
l’affirmation :
(∀ x ∈ E, P(x)) ⇔ (∀y ∈ E, P(y)).

Formellement, c’est la même chose pour l’affirmation “∃ x ∈ E, P(x)”. Cependant, il arrive par
commodité que lorsqu’on utilise une telle affirmation, alors dans la suite le symbole x désigne un
élément qui satisfait P(x).
√
Exemple : ∀ x ∈ [0, +∞[, ∃!y x ∈ [0, +∞[, x = y2x . On note x ce réel y x .

Concrètement :
— Pour montrer une proposition de la forme “∀ x ∈ E, P(x)”, on fixe un élément x de E (quel-
conque), et on montre que P(x) est vraie pour cet élément là .
— Pour montrer une proposition de la forme “∃ x ∈ E, P(x)”, le plus souvent on donne expli-
citement un x qui convient.
Exemple I.1. A titre d’exemple, montrons que

∀e > 0, ∃ρ ∈ Q, ρ ∈]0, e[

Ce qu’on veut montrer commence par “∀e > 0, ...”, on commence donc par se donner un e > 0
quelconque, ce qui peut s’écrire :
Soit e > 0 donné quelconque.
Q
Ce qu’il faut montrer pour cet e commence pas ∃ρ ∈ , .... On cherche donc un rationnel
explicite ρ qui satisfait la condition voulue, à savoir 0 < ρ < e. Par exemple on peut chercher une
N
solution de la forme 10−k . Pour k ∈ , on a

10−k < e ⇔ ln(10−k ) < ln(e)

⇔ −k ln(10) < ln(e)
− ln(e)
⇔k>
ln(10)
− ln(e)
ö ù
En particulier, k = + 1 (où b...c désigne la partie entière) convient !
ln(10)

Soit δ = 10−k avec k = −ln(10)

ln(e)
+ 1. Alors δ ∈ Q, δ > 0, et comme k > − ln(e)
ö ù
ln(10) , on a
−k ln(10) < ln(e) et finalement δ < e. On a donc δ ∈]0, e[.
Malheureusement, on voit que “Soit” apparaît deux fois dans cette rédaction dans des sens dras-
tiquement opposés : dans le premier cas, on fixe un réel e sur lequel on s’interdit toute restriction,
alors que dans le second, on prend l’initiative, purement arbitraire, de s’intéresser à un réel parti-
culier.
Pour éliminer cette ambigüité de “Soit”, on préfèrera adopter une rédaction alternative, où les
formes passives et actives ainsi que l’acteur principal sont explicités. Par exemple

M’est donné e un réel de ]0,

ö 1[. ù
Je pose δ = 10 avec k = −ln(10)
− k ln(e)
+ 1. Alors [...], et donc δ ∈]0, e[.
 9 Table des Matières

I.4.2 Calculs avec un quatificateurs

On montre facilement les liens suivants entre quantificateurs et négation :

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

Exemple : Bien identifier les nuances entre les quatre notions suivantes qui sont toutes diffé-
rentes :
— Dire qu’une fonction f : R → R est la fonction nulle s’écrit : ∀x ∈ R, f (x) = 0.
— Dire qu’une fonction f : R → R n’est pas la fonction nulle s’écrit : ∃x ∈ R, f (x) 6= 0.
— Dire qu’une fonction f : R → R s’annule s’écrit : ∃x ∈ R, f (x) = 0.
— Dire qu’une fonction f : R → R ne s’annule pas s’écrit : ∀x ∈ R, f (x) 6= 0.
On montre également les liens suivants entre quantificateurs et les connecteurs “et” et “ou” :
Å ã




(1) ∀ x ∈ E, P(x) et Q(x) ⇔ ∀ x ∈ E, P(x) et ∀ x ∈ E, Q(x)

⇐
Å ã



(2) ∀ x ∈ E, P(x) ou Q(x) ∀ x ∈ E, P(x) ou ∀ x ∈ E, Q(x)
6⇒

⇒
Å ã



(3) ∃ x ∈ E, P(x) et Q(x) ∃ x ∈ E, P(x) et ∃ x ∈ E, Q(x)
6⇐
Å ã




(4) ∃ x ∈ E, P(x) ou Q(x) ⇔ ∃ x ∈ E, P(x) ou ∃ x ∈ E, Q(x)

Dans (2), la proposition de gauche signifie que pour chaque x, P(x) ou Q(x) est vraie, mais il peut
y avoir des éléments x pour lesquels c’est P(x) qui est vraie, et d’autres pour lesquels c’est Q(x)
La proposition de droite par contre affirme que P(x) est toujours vraie ou Q(x) est toujours
vraie.
Z
A titre d’exemple, considérons E = , P(n) :”n est pair” et Q(n) :”n est impair”. Alors il est
vrai que chaque entier est pair ou impair, mais il est faux que tous les entiers sont pairs ou tous les
entiers sont impairs.
Dans (3) la proposition de gauche affirme qu’il y a au moins un élément x qui satisfait à la fois
P(x) et Q(x), alors que celle de droite affirme qu’il y a au moins un élément x qui satisfait P(x) et
un élément x 0 qui satisfait Q(x 0 ), mais ce ne sont pas nécessairement les mêmes.
R R
Par exemple, la proposition “il existe x ∈ tel que sin x = 0 et il existe x ∈ tel que cos x = 0”
R
est vraie (puisque sin 0 = 0 et cos π2 = 0). Mais la proposition “il existe x ∈ tel que sin x = 0 et
R
cos x = 0” est fausse (puisque la relation sin2 x + cos2 x = 1 est vraie pour tout x ∈ , et que par
conséquent les fonctions sin et cos ne peuvent pas s’annuler sur un même réel x).

I.4.3 Calculs avec plusieurs quantificateurs

Considérons un prédicat P(x, y) qui dépend de deux éléments. On a alors :

∀ x ∈ E, ∀y ∈ E, P(x, y) ⇔ ∀y ∈ E, ∀ x ∈ E, P(x, y)
∃ x ∈ E, ∃y ∈ E, P(x, y) ⇔ ∃y ∈ E, ∃ x ∈ E, P(x, y)

Par contre, les affirmations ∀ x ∈ E, ∃y ∈ E, P(x, y) et ∃y ∈ E, ∀ x ∈ E, P(x, y) sont très différentes.

Dans le premier, pour chaque x on peut trouver un y qui vérifie P(x, y), et ce y peut changer quand
on change de x. Dans le second cas, le même y doit convenir pour tous les x en même temps. On a
donc :
⇐
∀ x ∈ E, ∃y ∈ E, P(x, y) ∃y ∈ E, ∀ x ∈ E, P(x, y)
6⇒
 TABLE DES M ATIÈRES 10

Exemple I.2. Dire qu’une fonction f : R → R est constante s’écrit

∃c ∈ R, ∀ x ∈ R, f (x) = c.

Par contre, l’affirmation

∀ x ∈ R, ∃c ∈ R, f (x) = c
est vérifiée pour quelque soit la fonction f (il suffit de prendre c = f (x)).
Remarque I.10. Pour éviter toute confusion, on note souvent en indice les variables dont dépendent
les choix : ici, on pourrait noter

∀ x ∈ R, ∃c x ∈ R, f (x) = c x

pour insister sur le fait qu’on s’autorise à changer c x en fonction de x.

I.5 Raisonnements
I.5.1 Raisonnement déductif
Le raisonnement déductif est le suivant :
Si P et P ⇒ Q sont vraies, alors Q est vraie.
Remarque I.11. C’est le raisonnement le plus utilisé. Le plus souvent l’affirmation de P ⇒ Q est
suffisamment évidente pour être sous entendue. On se contente alors d’écrire “P, donc Q”.
Par exemple, le fragment de raisonnement “n est divisible par 4 donc n est divisible par 2”,
utilise de façon sous entendue que “être divisible par 4 implique être divisible par 2”.
En pratique, dans une raisonnement déductif, on utilise la transitivité de “⇒” pour enchainer
des étapes élémentaires :
®
P vraie
⇒ Pk vraie .
P ⇒ P1 ⇒ P2 ⇒ · · · ⇒ Pk

I.5.2 Raisonnement par contraposée

On l’a vu précédemment, l’implication P ⇒ Q est équivalente à sa contraposée Q ⇒ P.
En pratique, cela nous offre toujours deux options lorsqu’on souhaite démontrer une implica-
tion : soit on démontre l’implication directe, soit on démontre sa contraposée. On fait le choix qui
nous semble le plus commode !
Exemple I.3. Soient a ∈ N, b ∈ N. Montrons que
ab impair ⇒ (a impair et b impair)

en démontrant la contrapposée

(a pair ou b pair) ⇒ ab pair .

En effet, si a = 2a0 , alors ab = (2a0 )b = 2(a0 b) est pair. De même si b = 2b0 , alors ab = a(2b0 ) = 2(ab0 )
est pair.

I.5.3 Raisonnement par l’absurde (ou tiers exclu)

Le raisonnement par l’absurde est le suivant :
Si P implique une affirmation fausse, alors P est vraie.
 11 Table des Matières

√ √
Exemple I.4. Montrons que 2 est irrationnel. Pour cela, supposons √ par l’absurde que 2 soir
rationnel : cela signifie qu’il existe a ∈ N
et b ∈ N
r {0} tels que 2 = ba . De plus, quitte à
a
simplifier le numérateur et le dénominateur de b par un facteur commun, on peut supposer que a
et b sont premiers entre eux (c’est-à-dire que 1 est le seul diviseur commun à a et b).
√
Puisque 2 = ba , on obtient en élevant au carré que 2b2 = a2 . En particulier, 2 divise a2 (ce que
N
l’on note 2| a2 ). Par conséquent 1 on obtient que 2| a. Cela signifie qu’il existe a0 ∈ tel que a = 2a0 .
On en déduit que 2b2 = (2a0 )2 = 4a02 , et donc que 2a02 = b2 . En particulier 2|b2 , et donc 2|b. Donc
2 est un diviseur comme à a et b, ce qui contredit le fait que a et b sont premiers entre eux.
√
On peut donc conclure que 2 est irrationnel.

I.5.4 Equivalences et conditions né cessaires/suffisantes

Pour montrer une équivalence P ⇔ Q, on peut soit raisonner par équivalences successives :

P ⇔ P1
⇔ P2
..
.
⇔Q

ce qui montre que P ⇔ Q par tranistivité de l’équivalence.

Le plus souvent cependant, on montrera P ⇔ Q en séparant les deux implications, c’est à
dire en montrant P ⇒ Q, et Q ⇒ P séparément.
On dit qu’on sépare condition nécessaire et condition suffisante.
Remarque I.12. Raisonner par équivalence est souvent plus compact. Par contre, c’est aussi plus dé-
licat et contraignant tant sur le plan des arguments utilisables que de la rédaction (on doit conser-
ver des équivalences à chaque étape, l’introduction de notations ou de choix intermédiaires est
mal aisée, etc...). La séparation des conditions nécessaires et suffisantes est donc toujours plus
confortable.
Cette façon de procéder se retrouve dans quantité de raisonnements faisant appel de façon
implicite à une équivalence. Par exemple, pour montrer l’égalité entre deux sous ensembles d’un
ensemble E, on peut procéder par équivalences successives :
Soit x ∈ E. On a : (nota : on ne suppose pas que x ∈ A ! !)

x ∈ A ⇔ ...
⇔ ...
⇔x∈B

Donc A = B.
Ou bien raisonner par double inclusion :
— M’est donné x ∈ A. Alors [. . . ] et donc x ∈ B. Donc A ⊆ B.
— M’est donné y ∈ B. Alors [. . . ] et donc y ∈ A. Donc B ⊆ A.
Ainsi, A = B.
1. Ce fait non trivial est une conséquence du Lemme de Gauss que l’on verra dans le chapitre sur l’arithmétique dans
Z. On peut aussi le voir comme une conséquence de l’unicité de la décomposition d’un entier en facteurs premiers. 2Dé-
montrons la contraposée (en admettant l’unicité de la décomposition d’un entier en facteurs premiers) : 2 6 | a ⇒ 2 6 | a . Si
2 6 | a, alors 2 n’apparaît pas dans la décomposition en facteurs premiers de a. En élevant au carré tous les facteurs de la
décomposition en facteurs premiers de a, on obtient une décomposition en facteurs premiers de a2 , qui est LA décomposi-
tion en facteurs premiers de a2 (par unicité de la dćomposition). Donc 2 n’apparaît pas dans la décomposition en facteurs
premiers de a2 . En particulier, 2 6 | a.
TABLE DES M ATIÈRES 12

De la même manière, déterminer les solutions x d’un problème P(x), revient à déterminer l’en-
semble S des x pour lesquels P(x) est vraie.
On peut raisonner par équivalence :
Soit x ∈ E (nota : on ne suppose pas que x vérifie P(x) ! !).
On a :

P(x) ⇔ [. . . ]
⇔ x ∈ { x1 , . . . , x n }

Donc l’ensemble des x vérifiant P(x) est { x1 , . . . , xn }.

ou bien par “analyse/synthèse” :
— Soit x une solution (c’est à dire un élément tel que P(x) soit vraie).
Alors [. . . ], et donc x ∈ { x1 , . . . , xn }.
— Reciproquement, si x ∈ { x1 , . . . , xn }, alors [. . . ] et donc P(x) est vraie.
Finalement, l’ensemble des x vérifiant P(x) est { x1 , . . . , xn }.
√
Exemple : Dé terminer l”ensemble S de tous les ré els x ≤ 2 tels que x = 2 − x.
Voici deux solutions possibles :
• Par conditions né cessaire et suffisante :

— Soit x une solution. Alors x2 = 2 − x, donc x2 + x − 2 = 0, donc x ∈ {1, −2}.

Donc S ⊆ {1, −2}.
— Ré ciproquement : √
— Pour x = −2, on √ a 2 − x = 2 6= x, donc −2 n’est pas solution.
— Pour x = 1, on a 2 − x = 1 = x, donc 1 est solution.
Donc S = {1}.
• Par é quivalences :
Soit x ∈] − ∞, 2]. On a :

√
®
x2 = 2 − x
x= 2−x ⇔
x≥0
®
x2 + x − 2 = 0
⇔
x≥0
®
x ∈ {1, −2}
⇔
x≥0
⇔x=1

Donc S = {1}.
 Chapitre II
Introduction à la théorie des ensembles

II.1 Notions sur les ensembles

II.1.1 Construction par extension et compréhension
Intuitivement, un ensemble est une collection d’objets deux à deux distincts appelés éléments.
On peut définir un ensemble de deux manières :
— en extension : on donne la liste exhaustive des éléments qui y figurent ;
— en compréhension : on donne les propriétés que doivent posséder les éléments de l’ensemble.
Exemple II.1. Voilà quelques exemples d’ensembles d’élèves :
— {Pierre ; Paul ; Marie}, on donne les trois éléments qui définissent l’ensemble ;
— {élèves de la classe qui ont les yeux bleus} ;
— {élèves qui viennent en cours en pyjama}, mais cet ensemble est certainement vide !
Exemple II.2. Dans votre scolarité vous avez rencontré certains ensembles classiques de nombres :
— N = {0, 1, 2, 3, . . .} est l’ensemble des nombres naturels ;
N
— ∗ = {1, 2, 3, . . .} est l’ensemble des nombres naturels non nul ;
— Z = {. . . , −3, −2, −1, 0, 1, 2, 3, . . .} est l’ensemble des nombres entiers ;
— Q Z N
= { p/q : p ∈ et q ∈ avec q 6= 0} ;
— R l’ensemble des nombres réels ;
— C l’ensemble des nombres complexes.
Exemple II.3. Les langages de programmation actuels exigent que certaines variables soient dé-
clarées avec un certain type de données. Un type de données est un ensemble d’objets associés à
une liste d’opérations standards effectuées sur ces objets. Définir le type d’une variable équivaut à
déclarer l’ensemble des valeurs possibles et autorisées pour cette variable.
Dans la sémantique de Python vous avez dû rencontrer :
— le type bool s’interprète comme l’ensemble {Vrai, Faux },
— le type int s’interprète comme l’ensemble des entiers
— le type float s’interprète comme l’ensemble des nombres à virgule flottante
— le type str s’interprète comme l’ensemble des chaînes de caractères
— le type list s’interprète comme l’ensemble des listes de longueur variable.

II.1.2 Principales règles de fonctionnement

On admettra l’existence d’ensembles. Sans rentrer dans l’axiomatique, la notion d’ensemble
satisfait un certain nombre de règles de fonctionnement, en voici les principales :
Relation d’appartenance Il faut pouvoir dire si un objet est dans l’ensemble. On note x ∈ A l’élé-
ment x est dans l’ensemble A.
 Chapitre II. I NTRODUCTION À LA THÉORIE DES ENSEMBLES 14

Objets distincts On peut distinguer deux éléments entre eux et un ensemble ne peut pas contenir
deux fois le même objet.
Ensemble vide Il existe un ensemble qui ne contient aucun élément, c’est l’ensemble vide et on le
note ∅ ou {}.
Paradoxe de Russell Un ensemble peut être élément d’un autre ensemble mais pas de lui même.
Remarque II.1. Cette dernière règle peut ne pas sembler naturelle. A la naissance de la théorie
des ensembles, les mathématiciens ne voyaient pas d’objection à envisager un ensemble dont les
éléments seraient tous les ensembles : l’ensemble des ensembles. Russell leur opposa le paradoxe
suivant :
Supposons que l’ensemble de tous les ensembles existe, et notons-le E. On considère l’ensemble
A = {x ∈ E : x ∈ / x } . Comme E contient tous les ensembles, A appartient à E. Est-ce que A
appartient à A ?
— si A ∈ A alors par définition de A, on a A ∈ / A,
— si A ∈ / A alors par définition de A, on a A ∈ A.

II.1.3 Représentation
On peut représenter les ensembles à l’aide d’un diagramme de Venn, ce sont les fameux dia-
grammes “patates”.
Exemple II.4. L’ensembe {Pierre ; Paul ; Marie ; Julie ; Karim} se représente par :

Julie Pierre
×
×
Karim
×
Marie
×
Paul
×

II.2 Sous-ensembles
II.2.1 Inclusion
Définition II.1 (Sous-ensembles). L’ensemble A est un sous-ensemble de B si tous les éléments de
A sont des éléments de B (autrement dit x ∈ A =⇒ x ∈ B). On dit aussi que A est inclus dans B,
on le note A ⊆ B.
Remarque II.2. Pour tout ensemble A on a ∅ ⊆ A et A ⊆ A.
Exemple II.5. On a {1, 2} ⊆ {1, 2, 3}.
N Z Q R C
Bien sûr on a ⊆ ⊆ ⊆ ⊆ .
Définition II.2 (Egalité d’ensembles). Deux ensembles sont égaux si et seulement si ils ont les
mêmes éléments, autrement dit si A ⊆ B et B ⊆ A.

II.2.2 Ensemble des parties

Définition II.3 (Ensemble des parties). Soit A un ensemble, l’ensemble des parties de A, noté P (A),
est l’ensemble des sous-ensembles de A.
On remarque que l’on a toujours ∅ ∈ P (A) car ∅ ⊆ A et A ∈ P (A) car A ⊆ A.
Exemple II.6. Si A = {1, 2, 3} alors P (A) = {∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}.
Remarque II.3. On a P (∅) = {∅} et P (P (∅)) = {∅, {∅}}. La notation ∅ décrit un ensemble qui ne
contient rien alors que {∅} décrit un ensemble contenant un élément, l’ensemble vide. Un tiroir
contenant un sac vide ({∅}) n’est pas vide et contient bien un objet.
 15 II.3. Opérations sur les ensembles

II.3 Opérations sur les ensembles

On présente ici des opérations sur les ensembles qui permettent de construire de nouveaux
ensembles.

II.3.1 Union et Intersection

Définition II.4 (Union). L’union des ensembles A et B est l’ensemble des éléments qui sont élé-
ments de A ou de B. On le note A ∪ B.
Proposition II.1 Propriétés de la réunion
La réunion admet certaines propriétés :
Idempotence : A ∪ A = A
Commutativité : A ∪ B = B ∪ A
Associativité : A ∪ (B ∪ C) = (A ∪ B) ∪ C
Elément neutre : A ∪ ∅ = A

Définition II.5 (Intersection). L’intersection des ensembles A et B est l’ensemble des éléments com-
muns à A et à B. On le note A ∩ B.
On dit que deux ensembles sont disjoints (ou incompatibles) si A ∩ B = ∅.
Proposition II.2 Propriétés de l’intersection
L’intersection admet certaines propriétés :
Idempotence : A ∩ A = A
Commutativité : A ∩ B = B ∩ A
Associativité : A ∩ (B ∩ C) = (A ∩ B) ∩ C
Elément neutre : si l’on se place dans un ensemble Ω appelé univers et que A est un sous-
ensemble de Ω alors A ∩ Ω = A

Proposition II.3 Propriétés de distributivité

On a les distributivités suivantes entre l’union et l’intersection :
de ∪ sur ∩ : A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
de ∩ sur ∪ : A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)

II.3.2 Différence et complémentaire

Définition II.6 (Différence). La différence de l’ensemble A par l’ensemble B est l’ensemble des
éléments qui sont dans A mais pas dans B, on le note A r B.

Définition II.7 (Différence symétrique). La différence symétrique entre les ensembles A et B est
l’ensemble des éléments qui sont dans A ou B mais pas dans les deux, on le note

A∆B = (A ∪ B) r (A ∩ B).

Définition II.8 (Complémentaire). On se fixe un ensemble Ω appelé univers. Pour A ⊆ Ω, on

définit le complémentaire de A par rapport à Ω comme l’ensemble des éléments de Ω qui ne sont
pas éléments de A, on le note A = Ω r A lorsqu’il n’y a pas d’ambiguïtés.

Remarque II.4. Il faut obligatoirement se placer dans un ensemble de référence pour définir la
complémentation.
Proposition II.4 Propriétés de la complémentation
La complémentation a plusieurs propriétés :
 Chapitre II. I NTRODUCTION À LA THÉORIE DES ENSEMBLES 16

Involution : A = A
Loi de Morgan : A ∩ B = A ∪ B et A ∪ B = A ∩ B

A B

Ω
n D Diff
iff éren
on ctio ér ce sy
Uni rs
e en mét
riqu
te ce e
In

A∪B A∩B ArB A∆B

Passage au complémentaire

A∪B A∩B ArB A∆B

F IGURE II.1 – Exemples de constructions d’ensembles à partir des ensembles A et B contenus dans
l’univers Ω

II.3.3 Produit cartésien

Définition II.9 (Produit cartésien). Le produit cartésien des ensembles A et B (dans cet ordre) est
l’ensemble des couples (a, b) où a ∈ A et b ∈ B, on le note A × B.
Le produit cartésien des ensembles A1 , A2 , . . . , Ak (dans cet ordre) est l’ensemble des k-uplets
(a1 , . . . , ak ) où ai ∈ Ai pour tout i ∈ {1, . . . , k}, on le note A1 × · · · × Ak .
Si A1 = · · · = Ak on note Ak l’ensemble des k-uplets formés par les éléments de A.
Remarque II.5. Le couple (a, b) n’est pas un ensemble.
Si a 6= b alors (a, b) est distinct de (b, a).
Exemple II.7. Le système de codage informatique des couleurs RGB, (de l’anglais ”Red, Green,
Blue”) reconstitue une couleur par synthèse additive à partir de trois couleurs primaires (rouge,
vert et bleu), formant sur l’écran une mosaïque trop petite pour être aperçue. Ainsi pour chacune
des trois couleurs primaires, on donne une valeur s’exprimant dans un intervalle entre 0 et 255.
D’un point de vue informatique, une couleur est donc un élément de [0; 255] × [0; 255] × [0; 255] =
[0; 255]3 .

II.4 Exemple : l’ensemble des mots sur un alphabet fini

Un alphabet A est un ensemble fini dont les éléments sont appelés des lettres.
Exemple II.8. B = {0, 1} est l’alphabet binaire, A = { a, b, c} est un alphabet à trois lettres, B =
{ a, . . . , z} un alphabet à 26 lettres . On peut considérer n’importe quel ensemble fini, par exemple
C = {hello, word} est un alphabet à deux lettres.
17 II.4. Exemple : l’ensemble des mots sur un alphabet fini

Un mot (défini sur A) est une suite finie d’éléments de A. On le note u = u1 u2 . . . un où ui ∈ A

pour tout i ∈ {1, . . . , n}. Dans ce cas, n est la longueur du mot u, notée |u|.
Le mot vide est noté ε : c’est le (seul) mot de longueur nulle.
On note A∗ l’ensemble des mots sur A et A+ = A∗ r {ε} désigne l’ensemble des mots qui ne
sont pas le mot vide.
Soient u et v deux mots de A∗ . On définit la concaténation w = u · v comme le mot de longueur
|u| + |v| tel que
w = u · v = u1 u2 . . . u | u | v1 v2 . . . v | v | .
Pour n ∈ N on définit par récurrence la puissance d’un mot par
u0 = ε et un+1 = [Link] pour n ∈ N.

On dit que v est un préfixe de u s’il existe un mot w tel que u = v · w. On dit que v est un suffixe
de u s’il existe un mot w tel que u = w · v.
Un langage L sur un alphabet fini A est un ensemble de mots définis sur A, autrement dit L est
une partie de A∗ : L ⊆ A∗ .
Chapitre II. I NTRODUCTION À LA THÉORIE DES ENSEMBLES 18
 Chapitre III
Fonctions et applications

La notion d’application permet d’associer à chaque élément d’un ensemble un élément d’un
R R
autre ensemble. Il y a bien sûr l’exemple d’applications de dans , mais il ne faut pas s’y limiter :
les applications peuvent être définies sur toute sortes d’ensembles, et permettent d’étudier les
objets sous toutes sortes d’aspects.
Par exemple, on peut s’intéresser aux suites réelles, et plus particulièrement à leur premier
terme. Cela revient à considérer l’application qui à une suite u = (un )n∈N associe son premier
terme u0 est faite pour ça :
N →
R R
.
(un )n∈N 7→ u0

III.1 Premières notions

III.1.1 Définition
Définition III.1 (Fonction). Soient E et F deux ensembles. Une application f : E → F (de E dans F)
est un objet qui à chaque élément x de E associe un élément de F qu’on note f (x).
On dit que E est l’ensemble de départ de f et que F est l’ensemble de d’arrivée de f
On dit que f (x) est l’image de x par f .
Si y est un élément de F, les éléments x de E tel que f (x) = y, s’il en existe sont les antécédents
de y par f .
On note :
f : E → F, x 7→ f (x)
ou
f :E → F
.
x 7→ f (x)
Remarque III.1. Formellement, une application est en fait définie par son graphe. Un graphe est un
sous ensemble G ⊆ E × F tel que ∀ x ∈ E, ∃!y ∈ F, (x, y) ∈ G. L’application associée est alors celle
qui à x associe y.
Remarque III.2. On souhaite parfois regarder des applications “qui ne sont pas définies partout”.
R
Par exemple, l’application x 7→ 1/ x n’est pas définie sur tout , mais seulement sur \ {0}. OnR
parle alors de fonction : une fonction sur E est une application définie sur un sous ensemble de E.
Ce sous-ensemble s’appelle le domaine de définition de f .
Exemple III.1. Soit E = {1, 2, 3, 4} et F = { a, b, c}.
On définit l’application f par le graphe :

G f = {(1, a), (2, c), (3, a), (4, a)} ⊆ E × F

Chapitre III. F ONCTIONS ET APPLICATIONS 20

Autrement dit
f :E −→ F
1 7−→ a
2 7−→ c
3 7−→ a
4 7−→ a
On dit que a est l’image de 1 par f . Les éléments 1, 3, 4 sont les antécédents de a par f . L’élément
b n’a pas d’antécédent par f .

Définition III.2 (Ensemble image et préimage). Etant donné A ⊆ E et B ⊆ F, on définit

— l’image de A par f :

f (A) = { f (x), x ∈ A}
= {y ∈ F : il existe x ∈ E tel que f (x) = y}
= {y ∈ F : il existe x ∈ E tel que (x, y) ∈ G f };

— la préimage de B par f :

f −1 (B) = { x ∈ E : il existe y ∈ F tel que f (x) = y}

= { x ∈ E : il existe y ∈ F tel que (x, y) ∈ G f }.

Par définition, on voit que f (A) ⊆ F et f −1 (B) ⊆ E.

Remarque III.3. Attention, la notation f −1 (B) est trompeuse : elle pourrait faire croire qu’on suppose
que f est bijective (voir plus loin) et qu’on utilise l’application réciproque de f . Ce n’est bien sûr
pas le cas, et l’image réciproque d’un sous ensemble de F est bien définie, que f soit bijective ou
non !
Pour éviter cette ambiguïté, on pourra utiliser une notation alternative, à savoir : fˆ(A) pour
l’image directe d’une partie A ⊆ E , et fˇ(B) pour l’image réciproque d’une partie B ⊆ F.
Cela permet d’expliciter deux nouvelles applications induite par la donnée d’une application
f :E→F:

P (E) → P (F) P (F) → P (E)

fˆ : et fˇ :
A 7→ fˆ(A) = { f (x), x ∈ A} B 7→ fˇ(B) = { x ∈ E : f (x) ∈ B}

Définition III.3 (Image d’une application). L’ensemble image d’une fonction f : E → F, noté Im( f )
est l’ensemble des éléments de y ∈ E qui ont un antécédent par f . Autrement dit :

Im( f ) = f (E)
= { f (x), x ∈ F }
= {y ∈ F : il existe x ∈ E tel que f (x) = y}

Exemple III.2. Soit E = {1, 2, 3, 4} et F = { a, b, c}. On considère la fonction f définit par le graphe
G f = {(1, a), (2, c), (3, a), (4, a)} ⊆ E × F.
On a :
— f ({1}) = { a}, f ({1, 4}) = { a}, et f ({1, 2, 3}) = { a, c} ;
— f −1 ({ a}) = {1, 3, 4}, f −1 ({ a, c}) = {1, 2, 3, 4}, f −1 (∅) = ∅ et f −1 ({b}) = ∅ ;
— l’image de l’application f est Im( f ) = { a, c}.

Définition III.4 (Egalité). Deux applications f : E → F et g : E → F sont égales si ∀ x ∈ E, f (x) =

g(x).

Exemple III.3. R R R
— L’application f : → , x 7→ sin x et l’application g : [0, +∞[→ , x 7→ sin x
ne sont pas égales (puisqu’elles n’ont pas le même ensemble de départ).
R R R R
— L’application f : → , x 7→ sin2 x + cos2 x et l’application g : → , x 7→ 1 sont égales
R
puisque : ∀ x ∈ , sin2 x + cos2 x = 1.
 21 III.1. Premières notions

N N
— L’application f : → , n 7→ n2 2n + 3 et l’application g : N → N, n 7→ n(n+1)(n
3
+2)
ne sont
pas égales puisque f (1) = 5 6= 2 = g(1).

Définition III.5. Si E et F sont des ensembles, la collection des applications de E vers F forment
un ensemble : l’ensemble de fonctions de E vers F que l’on note

F (E, F) ou F E .

Exemple III.4. La notation RN désigne l’ensemble des applications de N dans R, autrement dit
l’ensemble des suites réeles.

III.1.2 Modes de représentation

On donne ici différents moyens pour représenter une fonction f : E → F.

Table de valeur Pour chaque élément de E on donne l’élément de F associé. Si E est fini on peut
représenter cela sous forme de tableau.

x 0 1 2 3 4 5 6 7 8 9
f(x) aa nj zj nk za az aa aa zz ju

Diagramme de Venn Parfois il est plus visuel de montrer les différents liens sur un diagramme
de Venn.

1
×
e b 2
× × ×
a
d × 4
× ×
c
× 3
×

E
F

Formule algébrique Lorsque l’ensemble E est infini, on ne peut pas stocker toutes les valeurs,
on peut définir la fonction par une formule :

f : R −→ R
x 7−→ 3x2 + 2x − 5

Courbe On peut aussi représenter la fonction sous forme de courbe qui à chaque point de l’abs-
cisse fait correspondre un élément de l’ordonnée. Autrement dit, les points de la courbe représen-
tative de f sont précisément les points dont les coordonnées sont dans le graphe G f de f .
 Chapitre III. F ONCTIONS ET APPLICATIONS 22

2
0 5 10 15 20

Algorithme On peut aussi définir une fonction f : E → F par un algorithme qui prend en
argument un élément de E et lorsqu’il s’arrête, il renvoie un élément de F. Le domaine de définition
est l’ensemble des valeurs pour lesquelles l’algorithme s’arrête.

III.1.3 Composition d’applications

Définition III.6 (Composition). On considère des aplications f : E → F et g : F → G. On définit
l’application composée de f par g, notée g ◦ f : E → G, définie par g ◦ f (x) = g( f (x)). On applique f
à l’argument x, puis on applique g au résultat.

Exemple III.5. Soient E = {α, β, γ}, F = { a, b, c, d, e} et G = {1, 2, 3, 4}, on définit f : E → F et

g : F → G par :
f : E −→ F g: F −→ G
α 7−→ b a 7−→ 2
β 7−→ a b 7−→ 1
γ 7−→ d c 7−→ 4
d 7−→ 3
e 7−→ 1
La représentation avec le diagramme de Venn donne :

1
×
e
α × b
× × 2
a ×
β × 4
× d ×
× c
× 3
γ ×
×

f g
E F G
g◦ f

Ainsi la fonction f ◦ g : E −→ G donne les associations suivantes :

α 7−→ 1 β 7−→ 2 γ 7−→ 3

Remarque III.4. Au milieu du XXème siècle, quelques mathématiciens trouvèrent que la notation
g ◦ f portait à confusion et décidèrent d’utiliser une notation post-fixée : x f pour f (x) et x f g pour
g ◦ f (x).
 23 III.1. Premières notions

Remarque III.5. Attention :

— La notation f ◦ g n’a de sens que si l’ensemble d’arrivée de l’application f est aussi l’en-
semble de départ de la fonction g.
— Même lorsque f ◦ g et g ◦ f sont bien définies, en général f ◦ g 6= g ◦ f .
Proposition III.1 Associativité de la composée
Soient f : E → F, g : F → G et h : G → H trois applications. Alors on a h ◦ (g ◦ f ) = (h ◦ g) ◦ f
et cette application se note h ◦ g ◦ f .

Démonstration : Par définition de la composition d’applications, il vient h ◦ (g ◦ f )(x) = h(g ◦ f (x)) =

h(g( f (x))) et (h ◦ g) ◦ f (x) = h ◦ g( f (x)) = h(g( f (x))) pour tout x ∈ E d’où l’égalité recherchée.

III.1.4 Applications particulières

Définition III.7 (Identité). Etant donné un ensemble A, la fonction identité est l’application définie
par
Id A : A −→ A
x 7−→ x
Définition III.8 (Injection canonique). Soit A ⊆ B, l’injection canonique est l’application définie par
f : A −→ B
x 7−→ x
Définition III.9 (Projection canonique). Soit A1 × · · · × Ak le produit cartésien de k ensemble, la
projection canonique suivant la ième coordonnée pour i ∈ {1, . . . , k} est l’application définie par
πi : A1 × · · · × A k −→ Ai
(a1 , . . . , ak ) 7−→ ai

Fonctions caractéristiques
Définition III.10. Soit Ω un ensemble. Pour tout A ⊆ Ω, on définit la fonction caractéristique de
l’ensemble A par
1 A : Ω −→ {0, 1}
®
1 si x ∈ A
x 7−→
0 si x ∈
/A
La fonction caractéristique d’un ensemble permet de définir un ensemble de manière fonction-
nelle. Ainsi, on a :
A = { x ∈ Ω : 1 A (x) = 1}
Proposition III.2 Propriétés des fonctions caractéristiques
Soient A, B ∈ P (Ω), pour tout x ∈ Ω, on a :
1. 1 A∩ B (x) = 1 A (x) × 1 B (x)
2. 1 A∪ B (x) = 1 A (x) + 1 B (x) − 1 A∩ B (x) = 1 A (x) + 1 B (x) − 1 A (x) × 1 B (x)
3. 1 A (x) = 1 − 1 A (x)

Exemple III.6. A l’aide des fonctions caractéristiques on peut retrouver les formules classiques, par
exemple pour tout x ∈ Ω, on a :
1 A∪ B (x) = 1 − (1 A (x) + 1 B (x) − 1 A∩ B (x))
= 1 − 1 A (x) − 1 B (x) + 1 A (x)1 B (x)
= (1 − 1 A (x))(1 − 1 B (x))
= 1 A (x)1 B (x)
= 1 A∩ B (x)
 Chapitre III. F ONCTIONS ET APPLICATIONS 24

Comme l’égalité est vraie pour tout x ∈ Ω, on en déduit que A ∪ B = A ∩ B.

III.2 Propriétés des applications

III.2.1 Injection et surjection
Définition III.11 (Fonction injective). Une application est injective si tout élément de l’espace d’ar-
rivée admet au plus un antécédent, ce qui se traduit par :

∀ x, x 0 ∈ E f (x) = f (x 0 ) ⇒ x = x 0

Définition III.12 (Fonction surjective). Une fonction est surjective si chaque élément de l’espace
d’arrivée admet au moins un antécédent :

∀y ∈ F, ∃ x ∈ E, f (x) = y.

Autrement dit, f est surjective si Im( f ) = F.

III.2.2 Bijection et application réciproque

Définition III.13 (Application bijective). Une application qui est à la fois injective et surjective est
bijective. Autrement dit, f est bijective si

∀y ∈ F, ∃!x ∈ E, f (x) = y.
Proposition III.3
L’application f : E → F est bijective si et seulement si il existe une application g : F → E
telle que f ◦ g = IdF et g ◦ f = IdE .
Si f est bijective, l’application g est unique, c’est l’ application réciproque de l’application f ,
notée f −1 .

Démonstration : Si f : E → F est bijective alors à chaque élément x ∈ E correspond un et un seul élément

y ∈ F, c’est la définition de l’application. De même, à chaque élément y ∈ F correspond un élément
x ∈ E (c’est la surjectivité), et cet élément est unique (c’est l’injectivité). Cela permet de définir une
fonction g : F → E qui vérifie

x = g(y) si et seulement si f (x) = y.

On en déduit que f ◦ g = IdF et g ◦ f = IdE .

Montrons qu’une telle application est unique. Soit h : F → E telle que f ◦ h = IdF et h ◦ f = IdE .
On a f ◦ h(y) = f ◦ g(y) = IdF (y) pour tout y ∈ F, par injectivité de f , on en déduit que h(y) = g(y).
Les fonctions g et h sont donc égales.
Supposons maintenant qu’il existe une fonction g : F → E telle que f ◦ g = IdF et g ◦ f = IdE et
montrons que f est bijective :
— Soient x1 , x2 ∈ E tels que f (x1 ) = f (x2 ), on a donc g( f (x1 )) = g( f (x2 )) et comme g ◦ f = IdE on en
déduit que x1 = x2 et donc que f est injective.
— Soient y ∈ F, on a y = IdF (y) = f (g(y)). Ainsi, g(y) est une préimage de y par f , on en déduit que
f est surjective.
f est injective et surjective, on en déduit que f est bijective.

En pratique, pour montrer qu’un application f : E → F est bijective, on peut :

— soit montrer que f est injective et que f est surjective,
— soit “deviner” une fonction g : F → E telle que f ◦ g = IdF et g ◦ f = IdE . Concernant la
rédaction, on définit d’abord g, et on vérifie ensuite que que f ◦ g = IdF et g ◦ f = IdE . On
conclut alors que d’une part que f est bijective, et que d’autre part f −1 = g.
Exemple III.7. Montrons que l’application de Q dans Q définie par f : x 7−→ 2x est une bijection.
1er point de vue : L’application f est :
25 III.2. Propriétés des applications

Q y
— surjective car pour tout y ∈ on a 2 ∈ et f ( 2 ) = y ; Q y

Q
— injective car si x, y ∈ vérifient f (x) = f (y) alors 2x = 2y autrement dit x = y.
Elle est donc bijective.
2d point de vue : Soit g : Q Q
→ , x 7→ 2x . Alors pour tout x ∈ , g( f (x)) = g(2x) = Q 2x
2 = x et
f (g(x)) = f 2 = 2 2 = x. Donc f est donc bijective et f −1 = g.
x x

Proposition III.4
Soient f : E → F et g : F → G deux bijections. La composée g ◦ f est bijective et

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

Démonstration : On a :

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

De même, on a :

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

On en déduit que g ◦ f est bijective et par unicité de l’application réciproque, on a (g ◦ f )−1 =

f −1 ◦ g −1 .

Exemple III.8. Z Z
— L’application f : → définie par f (n) = n + 1 est bijective : son application
Z Z
réciproque est l’application g : → définie par g(n) = n − 1.
N N
— L’application f : → définie par f (n) = n + 1 est injective, mais pas surjective. En effet,
si f (n) = f (m), alors n + 1 = m + 1 et donc n = m. Par contre, 0 n’a pas d’antécédent par f
N
car ∀n ∈ , f (n) ≥ 1.
N N
— L’application f : → ∗ définie par f (n) = n + 1 est bijective.
Comme on le voit, être ou non injectif ou surjectif dépend fortement du choix des ensembles
de départ et d’arrivée.
Remarque III.6. On peut toujours rendre une application surjective en réduisant son ensemble d’ar-
rivée. Soit f : E → F une application. Alors l’application

E → Im( f )
f˜ :
x 7→ f (x)

est surjective. Deplus, si on note i l’injection canonique de Im f dans F, on a f = i ◦ f˜.

Exemple III.9. On considère l’ensemble U = N des suites à valeurs réelles. On note Sg l’applica-
R
tion :
U → U
Sg :
u = (un )n∈N 7→ v = (vn )n∈N où vn = un+1


Ainsi : Sg (u0 , u1 , u2 , ...) = (u1 , u2 , u3 , ...). Alors :
— Sg n’est pas injective : par exemple (1, 0, 0, 0....) et (2, 0, 0, 0, ...) ont la mê me image par Sg .
— Sg est surjective : soit v = (v0 , v1 , v2 , ...) une suite donnée. Alors en posant u = (0, v0 , v1 , v2 , ...)
on a Sg (u) = v. Donc Sg est surjective.
De mê me, on note Sd l’application :

U → U
®
Sd : 0 si n = 0
u = (un )n∈N 7→ v = (vn )n∈N où vn =
u n −1 si n > 0.


Ainsi : Sd (u0 , u1 , u2 , ...) = (0, u0 , u1 , u2 , ...). Alors :
Chapitre III. F ONCTIONS ET APPLICATIONS 26

— Sd est injective : si u = (u0 , u1 , u2 , ...) et u0 = (u00 , u10 , u20 , ...) sont deux suites donné es telles
que Sd (u) = Sd (u0 ), alors (0, u0 , u1 , u2 , ...) = (0, u00 , u10 , u20 , ...). Ainsi,


 0=0
u0 = u00





u = u 0

1 1
u = u 0


 2 2
u3 = u30






...

donc u = u0 .
— Sd n’est pas surjective : par exemple, la suite v = (1, 0, 0, 0, ...) n’a pas d’anté cé dent puisque
pour toute suite u ∈ U , le premier terme de Sd (u) est 0.
Remarquons enfin que Sg ◦ Sd = IdU , alors que Sd ◦ Sg est l’application qui remplace le premier
terme d’une suite par 0.
 Chapitre IV
Cardinalité

En informatique, la résolution algorithmique de nombreux problèmes consiste en l’énuméra-

tion exhaustive de ses possibilités pour ensuite décider pour chacune si elle est solution ou non au
problème. Il est parfois bon d’évaluer le nombre de possibilités afin d’évaluer le temps d’exécution
de l’algorithme.

IV.1 Cardinalité des ensembles finis

IV.1.1 Ensembles de même cardinalité
Considérons les ensembles E = { a, b, c, d} et F = {1, 2, 3}. Il est possible de définir une applica-
tion surjective de E sur F, mais pas d’application injective. Il est possible de définir une application
injective de F sur E, mais pas d’application surjective. En fait, il n’y a pas assez d’éléments dans F
(ou trop peu dans E). Le cardinal d’un ensemble précise la notion de nombre d’éléments.
Définition IV.1 (Ensemble de même cardinal). Deux ensembles (fini ou non) sont équipotents ou
de même cardinal s’il existe une bijection entre eux.
Remarque IV.1. Par abus de langage on dit qu’il existe une surjection (respectivement une injection,
une bijection) s’il existe une application surjective (respectivement une application injective, une
application bijective).

IV.1.2 Cardinal d’un ensemble fini

Lemme IV.1
Soient n et k deux entiers naturels.
— S’il existe une application injective de {1, . . . , n} dans {1, . . . , k} alors n ≤ k.
— S’il existe une application surjective de {1, . . . , n} dans {1, . . . , k} alors n ≥ k.
— S’il existe une application bijection de {1, . . . , n} dans {1, . . . , k} alors n = k.

N N
Démonstration : Montrons par récurrence sur n ∈ ∗ la propriété Pn : pour tout k ∈ , s’il existe une
application injective de {1, . . . , n} dans {1, . . . , k} alors n ≤ k.
Clairement cette propriété est vraie pour P1 car il n’y a pas d’application d’un ensemble non vide
dans un ensemble vide.
Supposons que Pn est vérifiée et montrons que Pn+1 est aussi vérifiée. Soit f : {1, . . . , n + 1} →
{1, . . . , k} une injection. Pour tout x ∈ {1, . . . , n}, on a f (x) 6= f (n + 1) car f est une injection. On a
deux cas possibles :
— Si f (x) < f (n + 1) pour tout x ∈ {1, . . . , n} alors f (x) ∈ {1, . . . , k − 1} car f (x) ≤ f (n + 1) − 1 ≤
k − 1. En utilisant l’hypothèse de récurrence, on en déduit que n ≤ k − 1 et donc n + 1 ≤ k.
 Chapitre IV. C ARDINALITÉ 28

— Sinon, on considère x0 ∈ {1, . . . , n} tel que f (x0 ) > f (x) pour tout x ∈ {1, . . . , n + 1} r { x0 }. On
définit la fonction g : {1, . . . , n + 1} → {1, . . . , k} telle que g(x) = f (x) pour tout x ∈ {1, . . . , n +
1} r { x0 , n + 1}, g(x0 ) = f (n + 1) et g(n + 1) = f (x0 ). Comme f est une injection, les éléments de
{1, . . . , n + 1} n’ont pas deux images identiques par g donc g est injective. De plus g(x) < g(n + 1)
pour tout x ∈ {1, . . . , n}, en réalisant le même raisonnement que le point précédent, on en déduit
que n + 1 ≤ k.
Par récurrence la propriété Pn est vérifiée pour tout n ∈ N ce qui montre le premier point du
lemme.

Le deuxième point se montre de la même manière.

Si f : {1, . . . , n} → {1, . . . , k} est bijective, elle est injective d’où n ≤ k, et elle est surjective d’où
n ≥ k. On en déduit que n = k.

Si on a une bijection f : E → {1, . . . , n} et une bijection g : E → {1, . . . , m} alors g ◦ f −1 réalise

une bijection de {1, . . . , n} dans {1, . . . , m}. On en déduit que n = m ce qui nous permet de définir
le cardinal d’un ensemble fini.

Définition IV.2 (Cardinal d’un ensemble fini). Un ensemble E est fini s’il est vide ou s’il existe
N
n ∈ ∗ tel que E est en bijection avec {1, . . . , n}. Cet entier est unique, il est appelé le cardinal de
E. On le note Card (E). Si E est vide, on pose Card (E) = 0.

Remarque IV.2. Le cardinal d’un ensemble fini correspond à l’idée naturelle du nombre d’éléments
d’un ensemble.
Proposition IV.2
Soient E et F deux ensembles finis. On a :
— Il existe une application injective de E dans F si et seulement si Card (E) ≤ Card (F).
— Il existe une application surjective de E dans F si et seulement si Card (E) ≥ Card (F).
— Il existe une application bijective de E dans F si et seulement si Card (E) = Card (F).

Démonstration : Soient g : E → {1, . . . , Card (E)} et h : F → {1, . . . , Card (F)} deux bijections définissant
le cardinal de E et F.
Montrons le premier point. Soit f : E → F une injection, h ◦ f ◦ g−1 est une injection de {1, . . . , Card (E)}
dans {1, . . . , Card (F)}, donc Card (E) ≤ Card (F). Réciproquement, supposons que Card (E) ≤ Card (F).
On définit ϕ = h−1 ◦ i ◦ f où i : x 7→ x est l’injection canonique de {1, . . . , Card (E)} dans {1, . . . , Card (F)}.
L’application ϕ est une injection de E dans F.
Montrons le deuxième point. Soit f : E → F une surjection, h ◦ f ◦ g−1 est une surjection de
{1, . . . , Card (E)} dans {1, . . . , Card (F)}, donc Card (E) ≥ Card (F). Réciproquement, supposons que
Card (E) ≥ Card (F). On définit ϕ = h−1 ◦ s ◦ f où s : {1, . . . , Card (E)} → {1, . . . , Card (F)} est définie
par s(x) = x si x ∈ {1, . . . , Card (F)} et s(x) = 1 si x ∈ {Card (F) + 1, . . . , Card (E)}. L’application s est
surjective et donc ϕ est une surjection de E dans F.
Pour le dernier point, on considère une bijection f : E → F. Alors h ◦ f ◦ g−1 est une bijection
de {1, . . . , Card (E)} dans {1, . . . , Card (F)}, on en déduit que Card (E) = Card (F). Réciproquement,
supposons que Card (E) = Card (F) = n et considérons deux bijections g : E → {1, . . . , n} et h : F →
{1, . . . , n}. On en déduit que h−1 ◦ g est une bijection de E dans F.

IV.1.3 Principe des tiroirs

La contraposée du premier point de la proposition IV.2 établit un principe naturel très utilisé
en combinatoire appelé "principe des tiroirs" : si on doit ranger plus de paires de chaussettes qu’on
a de tiroirs, alors forcément un tiroir recevra au moins deux paires. Formellement cela se traduit
par la proposition suivante.
Proposition IV.3 Principe des tiroirs
Soient E et F deux ensembles finis non vides et f : E → F une application. Si Card (E) >
Card (F) alors il existe x1 , x2 ∈ E tels que f (x1 ) = f (x2 ).
 29 IV.2. Dénombrement

Démonstration : On peut faire une preuve directe de ce résultat. Comme E est fini on note E = { x1 , . . . , xCard(E) }.
Soit f : E → F et supposons que f (xi ) 6= f (x j ) si i 6= j. On en déduit que f (x1 ), . . . , f (xCard(E) ) sont tous
distincts et sont des éléments de F ainsi Card (E) ≤ Card (F). On en déduit que si Card (E) > Card (F)
alors au moins deux éléments de E ont la même image.

Exemple IV.1. Il y a au moins deux personnes à Paris qui ont exactement le même nombre de
cheveux. Le nombre moyen de cheveux chez un humain est de 150000 donc raisonnablement,
personne n’en a plus d’un million. Or il y a plus d’un million d’habitants à Paris, donc au moins
deux habitants ont le même nombre de cheveux.
Il est possible d’étendre le principe des tiroirs.
Proposition IV.4
Soient E et F deux ensembles finis non vides et f : E → F une application. Si Card (E) >
N
k Card (F) avec k ∈ ∗ alors il existe une valeur de f qui est répétée au moins k + 1 fois.

Démonstration : Si chaque valeur de f est répétée au plus k fois alors E contient au plus k Card (F) élé-
ments. Ainsi si Card (E) > k Card (F), une valeur de f est répétée au moins k + 1 fois.

Exemple IV.2. Voyons combien de noms différents doivent apparaître dans l’annuaire pour qu’au
moins cinq noms commencent et terminent par la même lettre. Soient E l’ensemble des noms et
F l’ensemble des paires de lettres qu’il est possible de constituer avec un alphabet de 26 lettres.
Clairement Card (F) = 26 × 26 = 676. On considère la fonction f : E → F qui renvoie pour
chaque nom la paire de lettre correspondant aux premières et dernières lettre du nom (par exemple
f (maurice) = (m, e)). Pour avoir cinq noms qui commence par la même lettre et termine par la
même lettre il faut que Card (E) > 4 Card (F) = 4 × 676 = 2704. Ainsi il faut que l’annuaire
contienne au moins 2705 noms.
Exemple IV.3. Montrons que dans tout groupe de six personnes, trois se connaissent mutuellement
ou trois ne se sont jamais vues. Considérons x une personne, E l’ensemble des cinq autres per-
sonnes et B = {0, 1}. Prenons la fonction f : E → B tel que f (a) = 1 si a ∈ E connaît x et 0 sinon.
Comme Card (E) > 2 Card (B), soit trois personnes connaissent x, soit il ne connaissent pas x.
Supposons que a, b et c connaissent x. Si deux d’entre eux se connaissent, avec x on a trouvé
trois personnes qui se connaissent mutuellement. Sinon a, b et c ne se connaissent pas.
Le même type de raisonnement fonctionne si a, b et c ne connaissent pas x.

IV.2 Dénombrement
On cherche le cardinal d’un ensemble fini, c’est à dire à dénombrer le nombre d’éléments de
cet ensemble. Dans votre scolarité en informatique vous utiliserez la notion de dénombrement au
moins dans les deux cas de figures suivants :
— dénombrer le nombre de cas à analyser par un algorithme en vu d’étudier sa complexité ;
— lorsqu’on tire au hasard un élément dans un univers finis Ω de manière équiprobable (c’est
à dire que chaque élément à la même probabilité d’être tiré), la probabilité que cet élément
soit dans l’ensemble A ⊆ Ω est
Card (A)
P(A) = .
Card (Ω)

IV.2.1 Dénombrement et opération sur les ensembles

On répertorie ici les principes de bases pour dénombrer un ensemble. Cela revient à décompo-
ser l’ensemble considéré en ensembles plus simples à l’aide des opérations sur les ensembles.

Union et intersection
Si A et B sont deux ensembles disjoints, c’est à dire A ∩ B = ∅, on a :
Card (A ∪ B) = Card (A) + Card (B) .
Chapitre IV. C ARDINALITÉ 30

Si (Ai )i∈ I est une famille d’ensembles disjoints indexée par I, on a :

!
= ∑ Card (Ai ) .
[
Card Ai
i∈ I i∈ I

Lorsque A et B sont deux ensembles quelconques, on cherche à écrire l’union comme une union
disjointe d’ensembles. Ainsi A ∪ B = (A r B) ∪ (B r A) ∪ (A ∩ B) et l’union est disjointe ainsi

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

On a aussi A = (A r B) ∪ (A ∩ B) et B = (B r A) ∪ (A ∩ B) et les deux unions sont disjointes.

On en déduit que Card (A) = Card (A r B) + Card (A ∩ B) et Card (A ∪ B) = Card (B r A) +
Card (A ∩ B). On en déduit que

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

Sur le diagramme de Venn cela donne :

Lorsqu’on fait l’opération Card (A) +

Card (B), les éléments e et f sont comp-
×h tés deux fois.
×d Pour compter le nombre d’éléments
×c
dans A ∪ B, on doit donc retrancher
×f Card (A ∩ B) à Card (A) + Card (B).
A B ×g
×b ×e
×a

Lorsqu’on fait l’opération Card (A) +

Card (B) + Card (C), les éléments a, f , i et
×h l sont comptés deux fois et l’élément e est
×d compté trois fois.
×c
Lorsqu’on fait l’opération Card (A ∩ B) +
×f Card (B ∩ C) + Card (C ∩ A), les éléments
A B ×g
a, f , i et l sont comptés une fois et l’élé-
×b ×e ment e est compté trois fois.
Ainsi dans l’expression
×i ×a
×l Card (A) + Card (B) + Card (C)




− Card (A ∩ B) + Card (B ∩ C) + Card (C ∩ A)
×j C ×k l’élément e n’est pas comptabilisé, il
faut donc rajouter à cet somme la
×m
quantité Card (A ∩ B ∩ C) pour obtenir
Card (A ∪ B ∪ C).

On a donc la proposition suivante.

Proposition IV.5

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

Card (A ∪ B ∪ C) = Card (A) + Card (B) + Card (C) − Card (A ∩ B) − Card (A ∩ C)
−Card (B ∩ C) + Card (A ∩ B ∩ C)
31 IV.2. Dénombrement

Remarque IV.3. Cela correspond au principe de l’addition : si on cherche à dénombrer un événe-

ment où l’on s’est ramené à considérer un cas ou bien un autre ou bien un autre, etc..., cela revient
à dénombrer une union de sous-ensembles, ce qui revient à effectuer la somme des cardinaux de
chaque sous-ensemble éventuellement en réajustant les intersections.
Remarque IV.4. Il existe une formule générale (non exigible) pour une union finie d’ensembles
(Ai )i∈{1,...,n} :
! !
n n
∑ (−1)i+1 ∑
[ \
Card Ai = Card Ai
i =1 i =1 I ⊆{1,...,n} avec Card(I)=i i∈ I

Exemple IV.4 (Nombre de carrés). On cherche à compter le nombre de carrés dans la figure ci
dessous :

On note A1 , A2 , A3 et A4 les ensembles de carrés dont les côtés sont respectivement 1, 2, 3 et

4. L’ensemble des carrés peut donc s’écrire comme une union disjointe : A = A1 ∪ A2 ∪ A3 ∪ A4 .
Donc Card (A) = 16 + 9 + 4 + 1 = 30.

Produit cartésien
Soient A et B deux ensembles finis. L’ensemble A × B correspond aux couples d’éléments (a, b)
où a ∈ A et b ∈ B. Ainsi on a Card (A) possibilités pour choisir le premier éléments et une fois
que l’on a choisi un élément de A, il y a Card (B) possibilités pour choisir b ∈ B. On en déduit que
A × B contient Card (A) × Card (B) éléments. On peut représenter les différents choix à l’aide d’un
arbre comme sur la figure IV.1.

A = { a1 , a2 , a3 , a4 }

a1 a2 a3 a4 B = {b1 , b2 , b3 }

Card (A × B) = 4 × 3 = 12

(a1 , b1 ) (a1 , b2 ) (a1 , b3 ) (a2 , b1 ) (a2 , b2 ) (a2 , b3 ) (a3 , b1 ) (a3 , b2 ) (a3 , b3 ) (a4 , b1 ) (a4 , b2 ) (a4 , b3 )

F IGURE IV.1 – Représentation sous forme d’arbre du produit cartésien de deux ensembles finis.

Ce raisonnement se généralise facilement au cas où on fait un produit cartésien d’une famille

finie d’ensembles finis.
Proposition IV.6
Soient A et B deux ensembles finis, on a :

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

Et plus généralement, si (Ai )i∈{1,...,n} est une famille finie d’ensembles finis alors :

Card (A1 × · · · × An ) = Card (A1 ) × · · · × Card (An )

Remarque IV.5. Cela correspond au principe de la multiplication : si on cherche à dénombrer un

événement où l’on s’est ramené à considérer un cas pris dans un ensemble, puis un autre dans un
autre ensemble, puis un autre, etc..., on effectue le produit des cardinaux de chaque ensemble.
 Chapitre IV. C ARDINALITÉ 32

Exemple IV.5 (Nombre de mots). On considère un alphabet A de cardinal Card (A) = m, on sou-
haite compter le nombre de mots de longueur n noté An (par exemple pour connaitre le nombre
de mots de passe possibles).
Si A = { a, b} et n = 4, le nombre de mots de longueur 4 qui peuvent être composés à partir
des lettres a et b est 24 = 16, on peut les énumérer :
aaaa, aaab, aaba, aabb, abaa, abab, abba, abbb, baaa, baab, baba, babb, bbaa, bbab, bbba, bbbb

Exemple IV.6 (Nombre de noms de variables BASIC). Les noms des variables du langage BASIC se
définissent ainsi :
<Lettre>::= A|B|... |Z
<Digit> ::= 0|1|... |9
<Var> ::= <Lettre> | <Lettre><Digit>
Ainsi une variable est une lettre ou bien une lettre composée d’un digit. Le nombre de variables
est donc :

Card (<Var>) = Card (<Lettre>|) + Card (<Lettre>) .Card (<Digit>) = 26 + (26 ∗ 10) = 286

Passage au complémentaire

Ä äle complémentaire d’un ensemble. Par exemple, si A ⊆ Ω

Parfois il est plus facile de dénombrer
et que l’on connaît Card (Ω) et Card A , alors Ω est une union disjointe de A et A, on en déduit
Ä ä
que Card (Ω) = Card (A) + Card A . Ainsi on a
Ä ä
Card (A) = Card (Ω) − Card A

IV.2.2 Arrangements et combinaisons

On peut aussi utiliser les formules classiques d’arrangements et de combinaisons. Avant d’uti-
liser les différentes formules, il est commode de se poser les questions suivantes :
— Quel est le nombre n d’objets de référence ?
— Quel est le nombre p d’objets concernés (p ≤ n) par la situation considérée ?
— Les p objets sont-ils considérés en “vrac” (sans ordre, tirage simultané), ou sont ils classés
d’une certaine façon (avec ordre, tirage successif) ?

Arrangement

Proposition IV.7
Permutation de n éléments : c’est le nombre de façon de ranger n objets dans l’ordre.

n! = n × (n − 1) × (n − 2) × · · · × 2 × 1

Démonstration : Le nombre de permutations de n éléments peut être calculé de la façon suivante : il y a n

places possibles pour un premier élément, n − 1 pour un deuxième élément, ..., et il ne restera qu’une
place pour le dernier élément restant. On remarque facilement alors qu’il y a n × (n − 1) × (n − 2) ×
· · · × 2 × 1 permutations possibles. On note n × (n − 1) × (n − 2) × · · · × 2 × 1 = n! et par convention,
0! = 1.

Exemple IV.7. Voici les 4! = 24 permutations de quatre éléments distinct a, b, c et d :

abcd abdc acbd acdb adbc adcb

bacd badc bcad bcda bdac bdca
cabd cadb cbad cdba cdab cdba
dabc dacb dbac dbca dcab dcba
33 IV.2. Dénombrement

Exemple IV.8. De combien de façons pouvez-vous ranger 10 livres sur une étagère ?

10! = 3628800

De combien de façons peut-on mélanger un jeu de 36 cartes ?

36! = 3, 72.1041
Proposition IV.8
Arrangements de p éléments parmi n sans répétition : c’est le nombre de listes de p élé-
ments parmi n, les éléments sont donc ordonnés dans la liste.

p n!
An = n × (n − 1) × (n − 2) × · · · × (n − p + 1) =
(n − p)!

Démonstration : Le premier élément peut être choisi de n façons différents, le deuxième peut prendre
n − 1 valeurs, le troisième n − 2 valeurs et le p-ième élément n − p + 1 valeurs. D’où :
p n!
An = n × (n − 1) × (n − 2) × · · · × (n − p + 1) =
(n − p)!

Exemple IV.9. Les A34 = 4 × 3 × 32 = 24 arrangements de 3 éléments choisis parmi a, b, c, d :

abc abd acb acd adb adc

bac bad bca bcd bda bdc
cab cad cba cdb cda cdb
dab dac dba dbc dca dcb

Exemple IV.10. Après les prolongations d’un match de football, l’entraîneur doit choisir les 5 tireurs
de penaltys parmi les onze joueurs et l’ordre de passage. Combien de choix a-t-il ?

A511 = 11 × 10 × 9 × 8 × 7 = 55440

Exemple IV.11. Le bingo est un jeu où les nombres tirés sont annoncés les uns à la suite des autres.
S’il y a 90 numéros en tout dans un sac, combien de suites différentes peut-on former avec les 10
premiers numéros tirés ?
A10
90 ' 2, 076.10
19

Proposition IV.9
Arrangement de p éléments parmi n avec répétition : c’est le nombre de listes de p élé-
ments parmi n, mais on s’autorise des répétitions éventuelles des éléments. Les éléments sont
ordonnés dans la liste.
np

Démonstration : Le premier élément peut être choisi de n façons différents, le deuxième d n façons, le
troisième n valeurs... Il y a donc n p possibilités.

Exemple IV.12. Les 32 = 9 arrangements avec répétitions de 2 éléments choisis parmi a, b, c :

aa ab ac ba bb bc ca cb cc

Exemple IV.13. Combien de numéros de téléphone composés de 7 chiffres existe-t-il ?

107

On a 6 clochettes produisant chacune un son différent des autres. On veut faire une mélodie de
10 notes avec ces clochettes. Combien de possibilités a-t-on ?

610 = 60466176
Chapitre IV. C ARDINALITÉ 34

Proposition IV.10
Soient E et F deux ensembles finis, le cardinal de l’ensemble des applications de E dans F,
noté F E , est : Ä ä
Card F E = Card (F)Card(E)

Démonstration : Pour définir une fonction de E dans F, il faut associé à chaque élément de E un élément
de F. Pour chaque élément de E on a donc Card (F) possibilités.

Combinaison

Proposition IV.11
Combinaisons de p éléments parmi n sans répétition : c’est le nombre de sous-ensembles
de p éléments dans un ensemble contenant n éléments, les éléments ne sont donc pas ordonnés.

p n!
Cn =
p!(n − p)!

p
Démonstration : Le nombre de combinaisons de p éléments choisis parmi n est noté Cn . Si l’on permute
les éléments de chaque combinaison simple, on obtient tous les arrangements simples. Il y a donc p!
p p
fois plus d’arrangements que de combinaisons, ce qui s’écrit An = p!Cn . Le nombre de combinaisons
de p éléments choisis parmi n est donc :
p
p An n!
Cn = =
p! p!(n − p)!

3!
Exemple IV.14. Les C32 = 2!1! = 3 combinaisons de 2 éléments choisis parmi a, b, c :
ab ac bc
Proposition IV.12
Quelques formules :
n− p p
Cn = Cn

p +1 p p +1
Cn+1 = Cn + Cn

n
(a + b)n = ∑ Cnk ak bn−k (formule du binôme)
i =0

Proposition IV.13
Combinaisons de p éléments parmi n avec répétition : c’est le nombre de listes non or-
données, avec répétition éventuelle, de p éléments dans un ensemble contenant n éléments, les
éléments ne sont donc pas ordonnés.

p p (n + p − 1)!
Kn = Cn+ p−1 =
p!(n − 1)!

(4+2−1)! 5×4
Exemple IV.15. Les K42 = C42+2−1 = (4−1)!2! = 2 = 10 combinaisons avec répétitions de 2 lettres
choisies parmi a, b, c, d sont :
aa ab ac ad bb bc bd cc cd dd
Exemple IV.16. Combien y a-t-il de dominos avec 10 symboles différents ?
2 2 11! 11 × 10
K10 = C10 +2−1 = = = 55
9!.2! 2
 35 IV.3. Cas des ensembles infinis

IV.3 Cas des ensembles infinis

IV.3.1 Définition et premiers exemples d’ensembles dénombrables
Définition IV.3 (Ensemble dénombrable). Un ensemble est dénombrable s’il est fini ou s’il est en
bijection . N
Exemple IV.17. Voilà quelques exemples d’ensembles dénombrables :
— Nr {0} est dénombrable par la bijection

f : N −→ N r {0} .
n 7−→ n+1

N
— l’ensemble des nombres pairs, noté 2 , est dénombrable par la bijection

f : N −→ 2N
.
n 7−→ 2n

— l’ensemble des nombres impairs, noté 2 N + 1, est dénombrable par la bijection

f : N −→ 2N + 1
.
n 7−→ 2n + 1

— l’ensemble des entiers relatifs Z est dénombrable par la bijection

f : N −→ Z
2n 7−→ −n .
2n + 1 7−→ n + 1

— l’ensemble N2 est dénombrable par la bijection

f : N2 −→ N
.
(p, q) 7−→ 2 p (2q + 1) − 1

On peut aussi considérer la bijection dite fonction de couplage de Cantor :

q

N2 N
4 10 16 23 31 40

3 6 11 17 24 32 f : −→
p + q −1 (p+q)(p+q+1)
2 3 7 12 18 25 (p, q) 7−→ p + ∑ i =0 (i + 1) = p + 2
1 1 4 8 13 19

0 0 2 5 9 14

0 1 2 3 4 p

— Par récurrence sur l’entier k ∈ N∗ , on montre que Nk est dénombrable.

Proposition IV.14
Tout sous-ensemble X ⊆ N est dénombrable.
Démonstration : Si X est fini, c’est terminé. Supposons que X est infini. On définit par récurrence une
N
application ϕ : → X de la manière suivante :

ϕ(0) = min{ x ∈ X } et ϕ(n + 1) = min{ x ∈ X : x > ϕ(n)} pour n ≥ 1.

On vérifie que ϕ est une bijection de N sur X

 Chapitre IV. C ARDINALITÉ 36

IV.3.2 Critères de dénombrabilité

Proposition IV.15
Il existe une application f : X → N qui est injective si et seulement si X est dénombrable.
Démonstration : Supposons que X est infini, autrement c’est terminé.
Si f : X → N
est injective alors X est en bijection avec f (X), qui est un sous-ensemble infini de
N. D’après la proposition IV.14, f (X) est dénombrable, comme f (X) est infini, il existe une bijection
N
h : f (X) → . Dans ce cas, h ◦ f réalise une bijection de X sur . N
La réciproque découle de la définition de la dénombrabilité.

Exemple IV.18 (Applications). Cette proposition est très commode pour montrer qu’un ensemble
est dénombrable :
— Un sous-ensemble d’un ensemble dénombrable est dénombrable.
N
— 2 est dénombrable car l’application suivante est injective :

f : N2 −→ N
.
(p, q) 7−→ 2 p 3q

— Nk est dénombrable, on considère k nombres premiers distincts p1 , . . . , pk et on vérifie que

l’application suivante est injective :

f : Nk −→ Na a .
(a1 , . . . , ak ) 7−→ p11 p2a2 . . . pkk

Proposition IV.16
Un produit fini d’ensembles dénombrables est dénombrable.

Démonstration : Soient X1 , . . . , Xk des ensembles dénombrables et pour tout i ∈ {1, . . . , k} on considère

une application injective f i : Xi → . N
N
Comme k est infini et dénombrable, il existe donc une bijection h : k → . On définit : N N
ϕ: X1 × · · · × X k −→ N
(x1 , . . . , xk ) 7−→ h( f 1 (x1 ), . . . , f k (xk ))

Si h( f 1 (x1 ), . . . , f k (xk )) = h( f 1 (x10 ), . . . , f k (xk0 )) pour (x1 , . . . , xk ), (x10 , . . . , xk0 ) ∈ X1 × · · · × Xk alors ( f 1 (x1 ), . . . , f k (xk )) =
( f 1 (x10 ), . . . , f k (xk0 )) par injectivité de h et (x1 , . . . , xk ) = (x10 , . . . , xk0 ) par injectivité de chaque f i . On en
déduit que ϕ est injective donc X1 × · · · × Xk est dénombrable.

Proposition IV.17
Il existe une application f : N → X qui est surjective si et seulement si X est dénombrable.
Démonstration : Supposons X infini autrement c’est terminé. Par hypothèse, il existe une application
N
f : → X qui est surjective. Pour tout x ∈ X , définissons g(x) = min{y ∈ : f (y) = x }. On vérifie N
N
que g : X → est injective et on en déduit que X est dénombrable.

Exemple IV.19 (Dénombrabilité de Q). L’ensemble Q est dénombrable. On considère l’application :

f : Z × N −→ Q
p .
(p, q) 7−→ q +1

Cette application est surjective et en composant avec une bijection de N sur Z × N on obtient une
surjection de sur . N Q
Proposition IV.18
Une réunion dénombrable d’ensembles dénombrables est dénombrable.
 37 IV.3. Cas des ensembles infinis

Démonstration : Soit I un ensemble dénombrable et (Xi )i∈ I une famille d’ensembles dénombrables in-
N
dexées par I. Pour chaque i ∈ I, il existe une application injective f i : Xi → . On définit l’ensemble

N
[
Y= {(i, f i (x)) : x ∈ Xi } ⊆ I ×
i∈ I

N
L’ensemble I × est dénombrable, donc Y est dénombrable. Pour tout (i, y) ∈ Y, on définit ϕ(i, y)
la préimage de y par f i qui est défini de manière unique par injectivité de f i .
L’application ϕ : Y → i∈ I Xi est surjective et Y est dénombrable, donc i∈ I Xi est dénombrable.
S S

IV.3.3 Ensembles non dénombrables

Il existe des ensembles qui ne sont pas dénombrables. L’exemple le plus simple est l’ensemble
N N
des parties de noté P ( ). En fait, on peut démontrer le théorème suivant qui est un peu plus
général :
Théorème IV.19 (Cantor 1981)
Soient E un ensemble. Il n’existe pas d’application bijective de E dans P (E).

Démonstration : Supposons qu’il existe une bijection f : E −→ P (E) et posons

A = {x ∈ E : x ∈
/ f (x)}

Puisque A ⊆ E, il existe x0 tel que f (x0 ) = A, on a donc deux cas possible :

— si x0 ∈ A, par définition x0 ∈
/ f (x0 ) = A ce qui est impossible ;
— si x0 ∈
/ A, par définition x0 ∈ f (x0 ) = A, on aboutit aussi à une contradiction.
L’hypothèse de départ était absurde, il n’existe donc pas de telle bijection.

Un autre argument utilisé en informatique théorique permet de montrer que [0, 1[ n’est pas
dénombrable. C’est l’argument diagonal de Cantor.
Théorème IV.20 (Argument diagonal de Cantor)
L’ensemble [0, 1[ n’est pas dénombrable.

Démonstration : Supposons que [0, 1[ soit dénombrable alors il existe une suite de réels (xi )i∈N telle
N
que [0, 1[= { xi : i ∈ }. Chaque réel xi admet une écriture décimale xi = 0, xi0 xi1 xi2 xi3 . . . avec
j
xi ∈ {0, 1, . . . , 9} pour j ∈ N.
N
Considérons une suite d’entiers yi ∈ {0, 1, . . . , 8} telle que yi 6= xii pour tout i ∈ . Alors le réel
N
y = 0, y1 y2 y3 · · · ∈ [0, 1[ est différent du réel xi pour tout i ∈ car il diffère pour la ième décimal. On
en déduit une contradiction.

R
On en déduit que n’est pas dénombrable. De plus l’ensemble des nombres réels irrationnels,
R Q
c’est à dire r , n’est pas dénombrable. En effet, si tel n’était pas le cas, = ( r ) ∪ serait R R Q Q
dénombrable.

IV.3.4 Théorème de Cantor-Schröder-Bernstein

Pour deux ensembles finis E et F, s’il existe une application injective de E dans F et une appli-
cation injective de F dans E alors on a respectivement Card (E) ≤ Card (F) et Card (F) ≤ Card (E).
On a donc Card (F) = Card (E), c’est à dire que E et F sont en bijection. En fait ce phénomène se
généralise à des ensembles infinis, c’est le théorème de Cantor-Schröder-Bernstein et on verra la
démonstration plus tard.
Théorème IV.21 (Théorème de Cantor-Schröder-Bernstein)
S’il existe une application injective de A vers B et une application injective de B vers A,
alors il existe une application bijection de A vers B.
Chapitre IV. C ARDINALITÉ 38

Exemple IV.20. Ce théorème est très utile pour montrer que deux ensembles sont équipotent. On
R N
peut montrer que [0, 1], ]0, 1[, ]0, 1[2 , et P ( ) sont équipotents deux à deux. Par exemple pour
N
montrer que P ( ) et [0, 1] sont en bijection, on montre que les deux fonctions suivantes sont des
injections :

f : P (N) −→ [0, 1] g: [0, 1] −→ P (N)

A 7−→ ∑n∈ A 3−n x = 0, x0 x1 x2 x3 x4 . . . 7−→ {i ∈ N si xi = 1}
 Chapitre V
Relations sur les ensembles

V.1 Vocabulaire des relations

V.1.1 Définition
Définition V.1 (Relation binaire). Une relation binaire R d’un ensemble E vers un ensemble F est
définie par une partie GR ⊆ E × F. Si (x, y) ∈ GR , on dit que x est en relation avec y et l’on note
x Ry (notation infixe) ou R(x, y) ou R x y (notations préfixes). L’ensemble E est appelé ensemble de
départ, l’ensemble F est l’ensemble d’arrivée et la partie GR de E × F est appelé le graphe de la relation.
Quand une relation binaire est définie d’un ensemble E vers lui-même (autrement dit E = F
dans la définition précédente, donc définie par une partie GR de E2 ), on dit que c’est une relation
interne sur E, ou simplement relation sur E.
Exemple V.1. Soient A = { a, b, c, d, e} l’ensemble des élèves et B = { Math, In f o, Ang, Phys} l’en-
semble des cours. L’ensemble A × B correspond aux couples possibles d’étudiants et cours. On
peut définir les relations suivantes :
— la relation R qui décrit si un étudiant suit le cours régulièrement défini par

GR = {(a, Math), (a, Phys), (b, In f o), (c, Ang), (d, Ang), (e, Math), (e, Ang)}

— la relation S définit par GS = {(a, Math), (c, Math), (d, Ang)} qui décrit si un étudiant pré-
sent à un intérêt personnel pour la matière (éventuellement il peut présenter un intérêt pour
la matière mais ne va pas souvent en cours).

V.1.2 Modes de représentations

Il existe différentes manières de représenter une relation d’un ensemble E vers un ensemble F.

Diagramme cartésien et matrice de relation Un diagramme cartésien est un tableau où les lignes
désignent les éléments de E et les colonnes les éléments de F. Les couples en relations sont marqués
par le symbole V. On peut aussi représenter la relation par une matrice en remplaçant les espaces
vides par 0 et les espaces marqués par 1.

R Math Phys Ang In f o S Math Phys Ang In f o

a V V a V
b V b
c V c
d V d V V
e V V e
 Chapitre V. R ELATIONS SUR LES ENSEMBLES 40

Diagramme sagittal Par un graphique où les éléments de E sont situés à gauche, les éléments de
F sont situé à droite et les éléments en relation sont reliés par une arête. On appelle cela un graphe
biparti.

a
In f o
b
Ang
c
Phys
d
Math
e

Graphe orienté Lorsque on a une relation interne sur un ensemble fini, on dessine un graphe
orienté où les sommets sont les éléments et on a un arc allant d’un sommet a à un sommet b si a est
en relation avec b.
Par exemple la relation interne sur {1, 2, 3, 4} définit par {(2; 1); (2; 2); (3; 1); (1; 4); (4; 3)} est re-
présentée par :

2 3 4

Remarques sur ces représentations Lorsqu’on représente une relation entre l’ensemble E et l’en-
semble F, tous les liens entre les éléments de E et F sont représentés et peuvent être reconstitués.
Cependant, dans les représentations précédentes les choix sont arbitraires :
— Diagramme sagittal : où placer les sommets et quelle forme donner aux flèches ?
— Diagramme cartésien et matrice : quel ordre de parcours faut il donner aux éléments ?
De manière générale établir l’égalité entre deux relations est un problème difficile et il n’y a pas
d’algorithme performant pour décider ce problème.

V.1.3 Quelques notions proches

Relation fonctionnelle Une fonction f : E → F associe a chaque élément de E au plus un élément
de F. On peut alors définir la relation R f définie par le graphe

GR f = {(x, f (x)) : x ∈ E} ⊆ E × F.

Réciproquement, pour une relation R telle que pour tout x ∈ E il y a au plus un y ∈ F vérifiant
x Ry alors on peut lui associer une fonction f telle que f (x) = y si et seulement si x Ry. On dit que
R est une relation fonctionnelle.

Relation n-aire Etant donné n ensembles E1 , E2 , . . . , En , une relation n-aire R est définie par un
sous ensemble GR ⊆ E1 × E2 × · · · × En .
Si n = 2, on retrouve la notion de relation binaire, si n = 3 on dit que l’on a une relation
ternaire... La notion de relation n-aire est au centre des bases de données qui cherchent à mettre en
relation différentes données.
 41 V.2. Propriétés sur les relations

V.2 Propriétés sur les relations

On s’intéresse principalement aux relations internes, c’est à dire définies sur un seul ensemble.
On représentera donc cette relation soit avec une matrice carrée, soit avec un graphe orienté. Dans
cette section on définit des propriétés sur les relations.

Reflexivité Une relation R est réflexive si pour tout x ∈ E on a

x R x.

Il est possible de repérer la réflexivité sur les modes de représentations :

— Diagramme cartésien : la diagonale doit être notée.
— Diagramme sagittal : chaque sommet admet une boucle.

3 2
1 2 3
1 V V V
2 V V
1 3 V

Exemple V.2. Quel que soit l’ensemble, la relation d’égalité = est réflexive. Sur N, la relation ≤ est
réflexive, mais < n’est pas réflexive.
l
Exemple V.3. Sur l’ensemble des mots A∗ , on considère la relation ≡ définit par
l
u ≡ v si et seulement si u et v ont même longueur.
l l l
Par exemple grand ≡ petit et grand ≡ grand mais grand 6≡ grande.
l
La relation ≡ est réflexive.

Symétrie Une relation R est symétrique si pour tout x, y ∈ E on a

x Ry si et seulement si yR x.

Il est possible de repérer la réflexivité sur les modes de représentations :

— Diagramme cartésien : symétrie par rapport à la diagonale.
— Diagramme sagittal : quand une flèche va de a vers b, il y a aussi une flèche de b vers a.

3 2
1 2 3
1 V V
2 V
1 3 V

Exemple V.4. Quel que soit l’ensemble, la relation d’égalité = est symétrique. Sur N, la relation ≤
est n’est pas symétrique.
l
La relation ≡ sur A∗ est symétrique.

Transitivité Une relation R est transitive si pour tout x, y, z ∈ E on a

x Ry et yRz implique que x Rz.

Il est possible de repérer la réflexivité sur les modes de représentations :

— Diagramme sagittal : tout chemin qui part d’un sommet s et va à un sommet s0 en suivant
la direction des flèches admet un raccourci, c’est à dire un chemin de longueur un.
 Chapitre V. R ELATIONS SUR LES ENSEMBLES 42

1 3 4
1 2 3 4
1 V
2 V V V V
3
2
4 V

Example : Quel que soit l’ensemble, la relation d’égalité = est transitive.

N
Sur , la relation ≤ est transitive.
l
La relation ≡ sur A∗ est transitive.
La relation "est le père de" n’est pas transitive : on ne peut pas à la fois être grand père et père.

Antisymétie Une relation R est antisymétrique si pour tout x, y ∈ E on a

x Ry et yR x implique que x = y.

1 3 4
1 2 3 4
1 V
2 V V
3 V V
2
4 V V

Example : Sur N, la relation ≤ est antisymétrique.

l
La relation ≡ sur A∗ n’est pas antisymétrique.

V.3 Relations d’équivalence

L’égalité est réflexive, symétrique et transitive. Dans ce chapitre, on veut généraliser la notion
d’égalité en considérant que deux éléments sont identiques s’ils vérifient une propriété donnée :
c’est la notion d’équivalence.

V.3.1 Définition et exemples

La relation d’équivalence est une abstraction de la notion d’égalité, elle permet de lier entre
eux des éléments qui partagent un ou plusieurs attributs communs.

Définition V.2. Une relation binaire définie sur un unique ensemble E est une relation d’équivalence
si elle est réflexive, symétrique et transitive.

Z
Exemple V.5. Par définition, pour x, y ∈ , on note x ≡ y[mod n], lire x est congru à y modulo n, si
Z
et seulement s’il existe k ∈ tel que x − y = kn. On a défini une relation d’équivalence sur car Z
on peut vérifier :
— Réflexivité : x ≡ x[mod n] car x − x = 0.n et 0 ∈ . Z
Z
— Symétrie : si x ≡ y[mod n] alors il existe k ∈ tel que x − y = k.n, on a donc y − x = −k.n
Z
et −k ∈ d’où y ≡ x[mod n].
Z
— Transitivité : si x ≡ y[mod n] et y ≡ z[mod n] alors il existe k, k0 ∈ tels que x − y = k.n et
y − z = k0 .n. Ainsi x − z = x − y + y − z = (k + k0 ).n. On en déduit que x ≡ z[mod n]
Exemple V.6. Voici quelques exemples de relations d’équivalence :
— Sur l’ensemble des personnes, la relation "a le même âge que" est une relation d’équivalence.
Des personnes liées appartiennent à la même tranche d’âge.
— Sur l’ensemble des triangles, la relation "a les mêmes angles que" est une relation d’équiva-
lence. Des triangles liés par cette relation sont dits semblables.
 43 V.3. Relations d’équivalence

R
— La relation R définie sur r {0} par x Ry si et seulement si xy > 0 est une relation d’équi-
valence. Deux réels liés par cette relation ont le même signe.
On pourra vérifier que ce sont bien des relations d’équivalence.
Remarque V.1. Si R est une relation d’équivalence, on dit que x est équivalent à y si aRb. La relation
étant symétrique, on a aussi b est équivalent à a. On dit que a et b sont équivalents.

V.3.2 Classes d’équivalence et partition

Définition V.3. Soit R une relation d’équivalence sur un ensemble E. La classe d’équivalence d’un
élément x, noté Cl(x), est l’ensemble des éléments de E qui sont en relation avec x. Autrement dit

Cl(x) = {y ∈ E : x Ry}.

Parfois la classe d’équivalence de x est aussi notée ẋ.

Proposition V.1
Une classe d’équivalence n’est jamais vide.

Démonstration : La classe d’un élément contient toujours au moins cet élément par réflexivité de la rela-
tion d’équivalence.

Proposition V.2
L’intersection de deux classes d’équivalence distinctes est vide.

Démonstration : Soit R une relation d’équivalence sur un ensemble E, on considère deux éléments x, y ∈
E et leurs classes d’équivalence Cl(x) et Cl(y).
Supposons qu’il existe z ∈ Cl(x) ∩ Cl(y), on a donc x Rz et yRz. Par symétrie, on a zRy. Ainsi
x Rz et zRy par transitivité on en déduit que x Ry et par réflexivité yR x.
Pour tout t ∈ Cl(y), on a yRt donc par transitivité x Rt d’ou t ∈ Cl(x). Autrement dit Cl(y) ⊆
Cl(x).
De même, pour tout t ∈ Cl(x), on a x Rt donc par transitivité yRt d’ou t ∈ Cl(y). Autrement dit
Cl(x) ⊆ Cl(y).
On en déduit que Cl(x) = Cl(y). Ainsi si deux classes sont distinctes alors l’intersection est vide.

Définition V.4. Soit E un ensemble, la famille d’ensembles (Ai )i∈ I indexée par I est une partition
si :
— l’union des (Ai )i∈ I est égale à E, c’est à dire E = ∪i∈ I Ai ,
— deux éléments de (Ai )i∈ I distincts sont disjoints, c’est à dire que si i 6= j alors Ai ∩ A j = ∅.

Théorème V.3
Etant donné une relation d’équivalence sur un ensemble, les classes d’équivalences forment
une partition.

Démonstration : Les classes sont des parties de E. De plus la classe d’un élément contient cet élément.
L’union des classes d’équivalence est donc E.
Si l’on choisi deux classes distinctes (i.e. Cl(x) 6= Cl(y)) alors leur intersection est vide d’après la
proposition précédente.

Exemple V.7. Considérons la relation d’équivalence correspondant à la congruence modulo 3. On

a trois classes d’équivalence :
— Cl(0) = {. . . , −6, −3, 0, 3, 6, 9, 12, . . .} ;
— Cl(1) = {. . . , −5, −2, 1, 4, 7, 10, 13, . . .} ;
— Cl(2) = {. . . , −4, −1, 2, 5, 8, 11, 14, . . .}.
 Chapitre V. R ELATIONS SUR LES ENSEMBLES 44

V.3.3 Ensemble quotient

Définition V.5. Soit E un ensemble munit d’une relation d’équivalence R. L’ensemble quotient est
l’ensemble des classes d’équivalence de tous les éléments de E. On le note E/R.
Proposition V.4
Etant donné une relation d’équivalence R sur E, la fonction suivante est surjective :

f : E −→ E/R
x 7−→ Cl(x)

Parfois, pour parler aisément d’une classe, on choisit un de ses éléments qui représente cette
classe. Cet élément, surmonté d’un point, sert à représenter la classe en question.
Exemple V.8 (Congruence modulo 4). On considère Z muni de la relation d’équivalence x ≡
Z Z
y[mod 4]. On choisit pour représentants les entiers 0, 1, 2 et 3. L’ensemble-quotient est /4 =
{0̇, 1̇, 2̇, 3̇}.
 Chapitre VI
Relations d’ordre

Dans ce chapitre on va définir la notion de relation d’ordre sur un ensemble qui permet de
mettre en place une hiérarchie sur E par une relation de précédence : l’élément a est en relation
avec b si a précède b dans la hiérarchie.

VI.1 Premières notions

VI.1.1 Définition
Définition VI.1. Une relation binaire  sur un ensemble E est une relation d’ordre si elle est ré-
flexive, transitive et antisymétrique. Autrement dit :
 réflexive : Pour tout x ∈ E on a x  x .
 transitive : Pour tout x, y, z ∈ E, si x  y et y  z alors x  z.
 antisymétrique : Pour tout x, y ∈ E, si x  y et y  x alors x = y.

Définition VI.2. Un ordre est total si pour tous éléments x, y ∈ E on a x  y ou y  x. Un ordre

est dit partiel pour souligner qu’on n’a pas forcément cette propriété.

Si x  y, on dit que x est un minorant de y et que y est un majorant de x.

VI.1.2 Exemples de relations d’ordre classiques

Ordres sur les nombres
N ZQ R
— Les relations ≤ et ≥ sont des relations d’ordre total sur qui s’étendent à , ou .
N ZQ R
— Les relations < et > ne sont pas des relations d’ordre sur (respectivement , ou ), ce
sont des relations d’ordre strictes.
N
— Sur ∗ la relation a divise b, notée a|b, est une relation d’ordre mais n’est pas total. On
N
rappelle que a divise b s’il existe k ∈ ∗ tel que b = a k, par exemple 3|57.

Ordres sur les parties d’un ensemble Soit E un ensemble l’inclusion, notée ⊆, est une relation
d’ordre sur l’ensemble des parties P (E) qui n’est pas totale.

Ordres sur les mots Soit A un alphabet. Il existe différentes notions pour ordonner l’ensemble
des mots A∗ :
— La relation u est préfixe de v, notée u <perd v et définit par il existe un mot w ∈ A∗ tel que
v = u.w, est une relation d’ordre qui n’est pas total
 Chapitre VI. R ELATIONS D ’ ORDRE 46

— Soit  un ordre total sur A, on définit l’ordre lexicographique sur A∗ par

u ≤lex v ⇐⇒ (u préfixe de v) ou (∃m ∈ N tel que u1 . . . um = v1 . . . vm et um+1 ≤ vm+1 )

C’est une relation d’ordre total sur A∗ . On a par exemple a ≤lex fa, poule ≤lex poulet,
avion ≤lex train, livraison ≤lex livre, foot ≤lex fort.

VI.1.3 Mode de représentation

Voilà le diagramme sagittal d’un ordre sur un ensemble à trois éléments :

3 2
1 2 3
1 V V V
2 V V
1 3 V

Pour simplifier la lecture du diagramme, on supprime les boucles dues à la réflexivité et les
flèches déductibles par transitivité :

1 2 3

L’idée est de représenter les sommets du diagramme et tracer seulement les flèches correspon-
dant aux successeurs immédiats. On dit que y est un successeur immédiat de x si x  y, x 6= y et
il n’existe pas de z tel que x  z  y.
L’élément x minore y, (x  y) si et seulement si on peut passer du point qui représente x au
point qui représente y en suivant les flèches du diagramme de Hasse. Le diagramme de Hasse
d’un ordre total est une chaîne.

Example : Le diagramme de Hasse pour l’ordre ⊆ sur E = {1, 2, 3} est :

{1, 2, 3}

{1, 2} {1, 3} {2, 3}

{1} {2} {3}

VI.1.4 Fonctions croissantes et décroissantes

Définition VI.3. Soient A et B deux ensembles munis respectivement des relations d’ordre  A et
 B et f : A −→ B une application. On dit que
— f est croissante si x  A y alors f (x)  B f (y).
— f est décroissante si x  A y alors f (y)  B f (x).
— f est strictement croissante si x  A y et x 6= y alors f (x)  B f (y) et f (x) 6= f (y).
— f est strictement décroissante si x  A y et x 6= y alors f (y)  B f (x) et f (x) 6= f (y).
Proposition VI.1
Soit A et B deux ensembles munis respectivement des relations d’ordre  A et  B tel que
 A est total. Une application f : A → B strictement croissante ou strictement décroissante est
injective.
 47 VI.2. Bornes d’un ensemble

VI.2 Bornes d’un ensemble

Soit A une partie d’un ensemble ordonné E par la relation d’ordre .

Définition VI.4. Un élément minimal de A est un élément de A qui n’admet pas d’élément plus
petit dans A.
On appelle minorant de A tout élément de E qui est plus petit que n’importe lequel des éléments
de A. Autrement dit :

x minorant de A ⇐⇒ pour tout y ∈ A on a x  y

Par la propriété d’antisymétrie, A admet au plus un seul minorant dans A, c’est le plus petit
élément de A, s’il existe on le note min(A).
On appelle borne inférieure le plus grand des minorants, on le note inf(A). Autrement dit


pour tout y ∈ A on a x  y
 (x est un minorant)
x borne inférieure de A ⇐⇒ et

pour tout z minorant A on a z  x (x est le plus grand des minorants)


Définition VI.5. Un élément maximal de A est un élément de A qui n’admet pas d’élément plus
grand dans A.
On appelle majorant de A tout élément de E qui est plus grand que n’importe lequel des élé-
ments de A. Autrement dit :

x majorant de A ⇐⇒ pour tout y ∈ A on a y  x

Par la propriété d’antisymétrie, A admet au plus un seul majorant dans A, c’est le plus grand
élément de A.
On appelle borne supérieur le plus petit des majorant, on le note sup(A). Autrement dit


pour tout y ∈ A on a y  x
 (x est un majorant)
x borne supérieur de A ⇐⇒ et

pour tout z majorant de A on a x  y (x est le plus petit des majorants)


Exemple VI.1. Le diagramme de Hasse pour l’ordre ⊆ sur E = {1, 2, 3} est :

{1, 2, 3}

{1, 2} {1, 3} {2, 3}

{1} {2} {3}

Considérons les ensembles suivants :

A= {{1}, {1, 2}, {1, 3}}

B= {{2}, {3}, {2, 3}}
C = A ∪ B = {{1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}}
 Chapitre VI. R ELATIONS D ’ ORDRE 48

On a

A B C
Eléments minimaux {1} {2}, {3} {1}, {2}, {3}
Eléments maximaux {1, 2}, {1, 3} {2, 3} {1, 2}, {1, 3}, {2, 3}
Plus petit élément {1} non existant non existant
Plus grand élément non existant {2, 3} non existant
Borne inférieure {1} ∅ ∅
Borne supérieure {1, 2, 3} non existant {1, 2, 3}

Exemple VI.2. L’intervalle I = [0, 1[ sous ensemble de R

muni de la relation d’ordre classique
≤ n’admet pas d’élément maximaux, admet un plus petit élément min(I) = 0, admet une borne
supérieur sup(I) = 1 et admet une borne inférieure inf(I) = 0.

VI.3 Induction
VI.3.1 Ordre bien fondé
Définition VI.6. Un ensemble ordonné (E, ) est bien fondé s’il n’existe pas de suite infinie stricte-
ment décroissante d’éléments de E.

De manière équivalente, un ensemble bien fondé peut se définir de la manière suivante :

Théorème VI.2
Un ensemble ordonné (E, ) est bien fondé si et seulement si toute partie non vide admet
au moins un élément minimal.

N
Exemple VI.3. L’ordre usuel ≤ sur est bien fondé mais il ne l’est pas sur , Z R, [0, 1].
N
L’ordre | sur \ {0, 1} défini par "a|b ⇐⇒ a divise b" est bien fondé.
N
L’ordre lexicographique sur 2 est bien fondé. Il est défini par

(a, b)  (c, d) ⇐⇒; (a < c ou (a = c et b ≤ d))

Soit A un alphabet contenant au moins deux lettres, <perd est bien fondé mais pas ≤lex .

VI.3.2 Application à l’étude de la terminaison d’algorithme

On dit qu’un programme P termine sur l’entrée x si le calcul de P(x) nécessite un nombre fini
d’étapes. Il est indécidable de savoir si un programme termine sur une entrée donnée, c’est à dire il
n’existe pas de programme qui prend en entrée le code d’un programme P et le code d’une entrée
x et répond oui si P(x) s’arrête. Autrement dit il n’existe pas de méthodes qui fonctionne à tout les
coup pour prouver la terminaison d’un algorithme. La notion d’ordre bien fondé fonctionne assez
souvent.

Cas des algorithmes itératifs : les variants de boucles

Définition VI.7. Etant donné (E, ) un ordre bien fondé, un variant de boucle est une fonction
de l’ensemble des états du programme dans E strictement décroissant à chaque passage dans la
boucle.
Proposition VI.3
Si une boucle admet un variant alors elle termine.

Exemple VI.4. Considérons l’algorithme d’Euclide (algorithme 1), la fonction (a, b) → b est un
variant de boucle donc l’algorithme termine.
 49 VI.3. Induction

Algorithm 1: Algorithme d’euclide

N
Data: (x, y) ∈ 2
Result: le pgcd de x et y

a ← x;
b ← y;
while b 6= 0 do
tmp ← a;
a ← b;
b ← tmp[mod b];

Cas des algorithmes récursifs

On considère une fonction f définit de manière récursive. Si les appels successifs de f ne s’ar-
rête pas, on pourrait construire une suite infinie strictement décroissante.
Proposition VI.4
Soit f une fonction récursive définit sur un ensemble ordonné (E, ) bien fondé. Si f est
défini sur les éléments minimaux et si pour tout x ∈ E non minimal, le définition de f (x) ne
fait appel à des valeurs f (y) pour y  x avec x 6= y alors f est bien définit.

Exemple VI.5. On considère la fonction fact définie par :

— fact(0) = 1 ;
— fact(n + 1) = (n + 1) ∗ fact(n).
N
Elle est bien définie car ( , ≤) est bien fondé, fact est définie sur l’élément minimal 0 et l’appel
de fact sur un élément non minimal fait appel à des éléments plus petit.
N
Exemple VI.6. On considère la fonction f définie sur \ {0, 1} par :
— f (p) = 1 si p premier ;
— f (n) = f (a) + f (b) si n = ab et a 6= 1 et b 6= 1.
N
Elle est bien définie car ( \ {0, 1}, |) est bien fondé, f est définie sur les éléments minimaux (les
nombres premiers) et l’appel de fact sur un élément non minimal fait appel à des éléments plus
petit.

VI.3.3 N et le principe de récurrence

N
L’ensemble ( , ≤) est bien fondé.
Théorème VI.5 Principe de récurrence
Soit P une propriété dépendant d’un élément n de N. Si les deux hypothèses suivantes sont
vérifiées
Initialisation : P(0) est vraie,
Héridité : si pour tout n ∈ N on a la propriété suivante :
"P(n) est vraie =⇒ P(n + 1) est vraie"
alors pour tout n ∈ N, la propriété P(n) est vraie.
Démonstration : On raisonne par l’absurde : supposons que les hypothèses du théorème sont vraies mais
que la conclusion est fausse.
N N N
Soit X = {n ∈ , P(n) est fausse}. L’ensemble X est une partie non vide de , comme ( , ≤) est
bien fondé, X admet un plus petit élément noté n0 .
Comme P(0) est vraie, on a n0 > 0 donc n0 − 1 est un entier positif ou nul, autrement dit n0 − 1 ∈
N
. P(n0 − 1) est vraie car n0 − 1 ∈/ X. Par hypothèse P(n0 − 1) =⇒ P(n0 ) donc P(n0 ) est vraie ce qui
est contradictoire avec le fait que n0 ∈ X.
Chapitre VI. R ELATIONS D ’ ORDRE 50

Exemple VI.7. On cherche à démontrer par récurrence la propriété P(n) définie par :
n
∑ (2i + 1) = (n + 1)2
i =0

Initialisation : Pour n = 0, on a ∑0i=0 (2i + 1) = 1 = (0 + 1)2 donc P(0) est vérifiée.

Héridité : On suppose que pour n ∈ N
la propriété P(n) est vraie, c’est à dire ∑in=0 (2i + 1) =
2
(n + 1) . Montrons que P(n + 1) est vérifiée :

n +1 n
∑ (2i + 1) = 2(n + 1) + 1 + ∑ (2i + 1)
i =0 i =0
= 2(n + 1) + 1 + (n + 1)2 (par hypothèse de récurrence)
= (n + 1)2 + 2(n + 1) + 12
= ((n + 1) + 1)2
n +1
∑ (2i + 1) = (n + 2)2
i =0

Par le principe de récurrence on en déduit que pour tout n ∈ N on a ∑in=0 (2i + 1) = (n + 1)2 .
Le principe de récurrence peut être généralisé en considérant que dans la deuxième hypothèse
la propriété est vraie pour tout k ≤ n.
Corollaire VI.6 Principe de récurrence généralisée
Soit P une propriété dépendant d’un élément n de N. Si les deux hypothèses suivantes sont
vérifiées
Initialisation : P(0) est vraie.
Héridité : si pour tout n ∈ N on a la propriété suivante :
"P(k) est vraie pour tout k ≤ n =⇒ P(n + 1) est vraie"
Alors pour tout n ∈ N, la propriété P(n) est vraie.
Démonstration : On applique le principe de récurrence du théorème VI.5 à la propriété Q tel que pour
N
n ∈ , Q(n) est vraie si P(k) est vraie pour tout k ≤ n.

Exemple VI.8. Démontrons que pour deux mots u, v ∈ A∗ tels que uv = vu alors u et v sont des
puissances d’un même mot w. On note P(n) la propriété suivante :

(|uv| = n et uv = vu) ⇐⇒ ∃w ∈ A∗ , ∃ p, q ∈ N tels que u = w p et v = wq )

On va montrer que P(n) est vraie par récurrence généralisée :
Initialisation : Pour n = 0, on a u = v = ε donc P(0) est vraie.
Héridité : On suppose que P(k) est vraie pour tout k ≤ n, c’est à dire que si |uv| = k ≤ n et
N
uv = vu alors il existe w ∈ A∗ et p, q ∈ tels que u = w p et v = wq .
Prenons u et v dans A∗ tels que |uv| = n + 1 et uv = vu. Sans perte de généralité, on suppose
que |u| ≥ |v|. Le mot v est un préfixe de u donc il existe un mot t ∈ A∗ tel que u = vt.
L’égalité u.v = v.u s’écrit vt.v = [Link] donc en simplifiant par v on a tv = vt. On a deux cas :
— Si |v| = 0 alors v = ε = u0 et u = u1 .
— Si |v| ≥ 1 alors |vt| = |u| < |uv| = n + 1, par l’hypothèse de récurrence il existe w ∈ A∗
N
et p, q ∈ tels que v = w p et t = wq . On a alors v = w p et u = vt = w p wq = w p+q .
N
Par le principe de récurrence généralisée, la propriété P(n) est vraie pour tout n ∈ donc pour
deux mots u, v ∈ A∗ tels que uv = vu alors u et v sont des puissances d’un même mot w.
 51 VI.3. Induction

VI.3.4 Principe d’induction

On souhaite généraliser le principe de récurrence à des ensembles ordonnés bien fondés.
Théorème VI.7
Soit  un ordre bien fondé sur un ensemble E. Soit P une propriété dépendante d’un élé-
ment x de E. Si les deux hypothèses suivantes sont vérifiées
Initialisation : P(x) est vraie pour tout élément minimal x de E.
Héridité : Si pour tout x ∈ E qui n’est pas minimal on a la propriété suivante :
"P(y) est vraie pour tout y  x avec y 6= x =⇒ P(x) est vraie"
Alors pour tout x ∈ E, la propriété P(x) est vraie.

Démonstration : On raisonne par l’absurde : supposons que les hypothèse du théorème sont vraies mais
que la conclusion est fausse.
Soit X = { x ∈ E, P(x) est fausse}. L’ensemble X est une partie non vide de E, comme (E, ) est
bien fondé, X admet un plus petit élément noté x0 .
Comme P est vraie pour tout élément minimal de E, l’élément x0 n’est pas minimal. Pour tout
y ∈ E tel que y  x0 et y 6= x0 , la propriété P(y) est vraie car x0 minimal dans X et donc y ∈
/ X . Par
hypothèse d’hérédité P(x0 ) est vraie ce qui est contradictoire avec le fait que x0 ∈ X.

N
Exemple VI.9. Montrons par induction que tout entier n ∈ \ {0, 1} la propriété P(n) suivante est
vérifiée : "n s’écrit comme un produit de nombre premier".
N
L’ensemble E = \ {0, 1} muni de l’ordre divise, noté |, est bien fondé et les éléments mini-
maux sont les nombres premiers.
Initialisation : Pour tout nombre premier x ∈ E la propriété P(x) est vraie.
Héridité : Soit x ∈ E qui n’est pas minimal on suppose que pour tout y ∈ E tel que tel que y divise
x et y 6= x la propriété P(y) est vraie. Montrons que P(x) est vraie.
Comme x n’est pas minimal, x n’est pas premier donc il existe x1 , x2 ∈ E tel que x = x1 × x2 .
On a x 6= x1 et x 6= x2 , et x1 divise x et x2 divise x. Par hypothèse d’hérédité x1 et x2
s’écrivent comme produit de nombre premiers donc x = x1 × x2 s’écrit aussi comme produit
de nombres premiers.

VI.3.5 Définition inductive

Définition inductive d’un ensemble
Définition VI.8. Soit E un ensemble. Une définition inductive d’un sous-ensemble X de E consiste
à la donnée :
— d’un sous-ensemble B de E appelé base,
— d’un ensemble K d’opérations ϕ : Er ϕ −→ E où r ϕ est l’arité de ϕ.
L’ensemble X est alors défini comme le plus petit (pour l’inclusion) ensemble vérifiant les as-
sertions suivantes :
Base : B ⊆ X,
Induction : pour tout ϕ ∈ K et pour tous x1 , x2 , . . . , xr ϕ ∈ X on a ϕ(x1 , x2 , . . . , xr ϕ ) ∈ X.
On dit que X est la fermeture inductive de B par K.

Exemple VI.10. Quelques ensembles définis inductivement :

— L’ensemble des entiers naturels est défini par :
Base : B = {0},
Induction :
succ : −→ N N .
n 7−→ n+1
— L’ensemble des entiers pairs est défini par :
Base : B = {0},
Chapitre VI. R ELATIONS D ’ ORDRE 52

Induction :
ϕ: N−→ N .
n 7−→ n+2
— L’ensemble des entiers impairs est défini par :
Base : B = {1},
Induction :
ϕ: N−→ N .
n 7−→ n+2
— L’ensemble des mots binaires est défini par :
Base : B = {ε},
ϕ0 : A∗ −→ A∗ ϕ : A∗ −→ A∗
Induction : et 1 .
u 7−→ 0u u 7−→ 1u
— ∗
L’ensemble des mots de {0, 1} qui contiennent autant de 0 que de 1 est défini par :
Base : B = {ε},
ψ1 : A∗ × A∗ −→ A∗ ψ : A∗ × A∗ −→ A∗
Induction : et 2 .
(u, v) 7−→ 0u1v (u, v) 7−→ 1u0v
— L’ensemble des mots de Dyck ∆ ⊆ {0, 1}∗ est défini par :
Base : B = {ε},
ψ : A∗ × A∗ −→ A∗
Induction : .
(u, v) 7−→ 0u1v

Preuve par induction

Le principe d’induction permet de démontrer des propriétés sur des ensembles définis induc-
tivement.
Théorème VI.8
Soit X ⊆ E la fermeture inductive de B par K. Soit P une propriété définie sur X. Pour
montrer que pour tout x ∈ X la propriété P(x) est vraie, il suffit de montrer que :
Base : Pour tout x ∈ B, on a P(x) vraie.
Induction Pour tout ϕ ∈ K d’arité r ϕ et tous x1 , x2 , . . . , xr ϕ alors on a

P(x1 ), P(x2 ), . . . , P(xr ϕ ) vraies =⇒ P(ϕ(x1 , x2 , . . . , xr ϕ )) vraie

Exemple VI.11. On considère l’ensemble des mots de Dyck ∆ ⊆ {0, 1}∗ défini par :
Base : B = {ε},
ψ : A∗ × A∗ −→ A∗
Induction : .
(u, v) 7−→ 0u1v
On veut montrer par induction que tout mot w ∈ ∆ vérifie la propriété P(w) : "w a autant de 0
que de 1 et tout préfixe de w a plus de 0 que de 1".
Base : ε vérifie la propriété demandée,
Induction : Soient u, v ∈ ∆ tels que P(u) et P(v) soient vérifiées. On note w = ψ(u, v) = 0u1v.
Comme u et v ont autant de 0 et de 1, il en est de même pour w. Soit t un préfixe de w. Il y
a deux cas :
— Si |t| ≤ 1 + |u| alors t est un préfixe de 0u. Il s’écrit t = 0t0 où t0 est un préfixe de u.
Comme les préfixes de u ont plus de 0 que de 1, on en déduit que t a plus de 0 que de 1.
— Si |t| > 1 + |u| alors t s’écrit t = 0u1t0 où t0 est un préfixe de v. Comme les préfixes de v
ont plus de 0 que de 1, on en déduit que t a plus de 0 que de 1.

Définition inductive d’une fonction

Lorsqu’un ensemble X est défini inductivement de telle sorte que chaque élément se décom-
pose de manière unique, il est possible de définir une fonction sur cette ensemble. Cela est très
utile pour programmer récursivement des fonctions.
Définition VI.9. Soit X ⊆ E la fermeture inductive de B par K. On dit que X est librement engendré
si pour tout x ∈ X on a x ∈ B ou bien il existe une unique règle ϕ ∈ K d’arisé r ϕ et un unique
k-uplet (x1 , . . . , xr ϕ ) tels que x = ϕ(x1 , . . . , xr ϕ ).
53 VI.3. Induction

Définition VI.10. Soient Y un ensemble et X un sous-ensemble de E défini par :

— une base B ⊆ E,
— un ensemble K d’opérations ϕ : Er ϕ −→ E où r ϕ est l’arité de ϕ.
Une fonction f : X → Y est définie inductivement par la donnée de :
Base : f (b) pour tout b ∈ B,
Induction : Pour tout ϕ ∈ K et pour tous x1 , x2 , . . . , xr ϕ ∈ X la valeur de f (ϕ(x1 , x2 , . . . , xr ϕ )) se
définit à partir de f (x1 ), f (x2 ), . . . , f (xr ϕ ).

Exemple VI.12. Quelques fonctions définies inductivement :

N
— La factorielle d’un entier n ∈ se définit par :
Base : 0! = 1,
Induction : (n + 1)! = (n + 1) × n!.
— L’exposant d’un réel an se définit pour n ∈ par : N
Base : a0 = 1,
Induction : an+1 = a × an .
N
— La longueur l : A∗ → d’un mot binaire u ∈ A∗ est défini inductivement par
Base : l(ε) = 0 ;
Induction : Pour u ∈ A∗ , on a l(ϕ0 (u)) = l(0u) = 1 + l(u) et l(ϕ1 (u)) = l(1u) = 1 + l(u).

Langages rationnels
Définition VI.11. On définit inductivement les langages rationnels R at ⊆ P (A∗ ) par :
Base : ∅ ∈ R at, {ε} ∈ R at et { a} ∈ R at pour tout a ∈ A ;
Induction : Si L et L0 sont des langages rationnels alors :
— L ∪ L0 ∈ R at,
— L.L0 ∈ R at,
— L∗ ∈ R at.

Exemple VI.13. Voilà quelques exemples de langages rationnels :

— tous les langages finis sont rationnels et en particulier A ;
— A∗ est rationnel ;
— A + = A.A ∗ ;
— le langage des mots sur A = {0, 1} qui contient au moins une fois le mot 111 est rationnel
car il s’écrit A∗ .{111}.A∗ ;
— le langage des mots sur A = {0, 1} qui contient un nombre pair de fois la lettre 1 est ration-
nel car il s’écrit ({b}∗ .{ a}.{b}∗ .{ a}.{b}∗ )∗ ;
Les langages rationnels constituent un outil pour décrire des langages simples (rationnels). Ces
formules sont par exemple utilisées pour effectuer des recherche des occurrences d’un motif. On
notera deux applications concrètes notables :
— Sous UNIX, il existe par exemple un utilitaire grep qui permet de rechercher les occur-
rences d’un motif dans un fichier texte. La commande suivante imprime sur la sortie stan-
dard toutes les lignes du fichier ‘[Link]’ contenant au moins une occurrence du mot
graphe :
> grep ’graphe’ [Link]
Il est possible de faire des recherches de répétition (e+) ...
— L’analyse lexicale se trouve tout au début de la chaîne de compilation. C’est la tâche consis-
tant à décomposer une chaîne de caractères en lexèmes, qui vont ensuite être analysés par
l’analyseur syntaxique qui va ensuite les interpréter.