NOTES DE COURS POUR LE COURS

MATHÉMATIQUES DISCRÈTES
MAT1500

ABRAHAM BROER

Références
[R] Kenneth H. Rosen, Mathématiques discrètes, Édition révisée Chenelière McGraw-Hill, 2002.

1. But à long terme : Développer un bon sens critique

Même si vous voulez devenir un actuaire ou un statisticien, il faut bien comprendre comment les
mathématiques fonctionnes. Il ne faut pas penser qu’il est possible de bien utiliser les mathématiques
sans en avoir une comprehension qui est fonctionnelle. Chaque résultat en mathématiques vient avec
une preuve ou au moins une explication pourquoi le résultat soit vrai. Pas seulement le Comment
compte mais aussi le Pourquoi, c.-à-d. la comprehension.
I faut aussi comprendre pourquoi on passe du concret à l’abstraction, et comment. Oui, les
exemples soi-mêmes resteront toujours importants ; mais aussi la réflection sur ce qui est en commun
dans beaucoup de problèmes. Dans la vraie vie on le fait tout le temps aussi, mais souvent seulement
implicitement. Il faut développer la capacité de observer qu’un genre de solution, naturelle pour
un genre de problèmes, peut s’appliquer aussi à d’autres problèmes qui ne semblent pas du tout
semblables.
C’est ça que nous voulons commencer de faire ce trimestre : nous allons moins insister sur le
Comment et plus insister sur le Pourquoi ; on va essayer de développer votre sens critique et votre
comprehension de certains abstractions.
Dans le cours de MAT1600 on commence à montrer encore une fois comment résoudre un système
d’équations linéaires, ce qui est très pratique dans beaucoup de situations déjà. Mais après on donne
des abstractions moins et moins évidentes, par exemples les opérateurs linéaires et les vecteurs
propres. En MAT1400 on commence à expliquer, encore une fois, c’est quoi un "dérivé" et un
"intégral", et puis calculer des exemples. Mais ici aussi, les preuves et les abstractions seront de plus
en plus importantes.
C’est naturel de penser : "Calcul et algèbre linéaire ? J’ai vu tout ça déjà au cégep ; et l’abstrac-
tion : ça ne m’intéresse pas trop et me semble inutile pour un actuaire, statisticien, ou économe. Je
serai déjà content si je saurai comment calculer quelque chose de pratique. Si le prof me dit que je
le fait correctement, ça me suffit."
Certainement, les enseignants ne sont pas d’accord. Il faut développer un bon sens critique, si on
le veut ou pas. Et ça commence par vouloir comprendre au fond les subtilités des Pourquoi et de
saisir l’abstraction. Idéalement il faut résoudre les exercices soi-même ou sinon avec peu d’aide. Et

Date: 11 janvier 2017.

1
2 ABRAHAM BROER

de développer vite le réflexe que si on fait une erreur (ce qui arrivera souvent et est normal !), d’aller
chercher soi-même l’erreur dans l’argument. Ça prendra possiblement des heures de votre temps,
mais c’est normal et cela arrive tout le temps, même aux meilleurs mathématiciens au monde.
Une remarque sur ce sujet : selon les normes de l’université, pour bien réussir un cours de 4
crédits, comme MAT1500, il faut dépenser 3 ∗ 4 = 12 heures de votre temps et votre concentration
en moyenne par semaine sur la matière de ce cours ! Un effort cégepien ne suffira plus.
Le processus d’apprentissage est lent, ça prend du temps et un effort soutenu. Mais c’est certain
que si vous réussissez votre baccalauréat en mathématiques avec une moyenne raisonnable vous
aurez développé déjà très considérablement votre esprit critique. Les diplômés d’un baccalauréat
en mathématiques ont la réputation enviable d’être capable de bien analyser et de résoudre des
problèmes de façon efficace.
Comprendre plus ou moins ne suffit plus dans le monde : pas en mathématiques, ni dans le
monde de la haute finance, de l’assurance, de la technologie, et cetera. Mais si vous avez un bon
sens critique en mathématique, très probablement vous avez aussi un bon sens critique dans d’autres
domaines scientifiques. Malheureusement pas nécessairement dans tous les situations sociales (en
questions d’amour par exemple), car la "logique" utilisée dans une situation sociale est différente. Il
faut travailler sur l’esprit critique sociale aussi : mais les cours de mathématiques ne vont pas aider
grandement.
De MAT1400 et MAT1600 vous connaissez déjà plus ou moins la matière ; donc c’est le moment
pour vous d’habituer à faire de plus d’attention aux définitions, contre-exemples et preuves et abs-
tractions. Ça va vous aider grandement dans les cours d’analyse mathématique abstraite MAT1000
et MAT2050, qui posent beaucoup de problèmes aux étudiants qui ne sont pas suffisamment (ma-
thématiquement) adulte.

Exemple 1.1. On a une collection de sept objets, dont deux d’une couleur et les cinq autres d’une
autre couleur. Question : En combien de façons différents peut-on en choisir trois ?
Vous donnez peut-être tout de suite une réponse, en utilisant une formule que vous connaissez !
Mais ce sera trop vite répondu. Car il manque d’information, ou de l’information restée implicite.
Qu’est-ce que veut dire "différents". L’ordre du choix importe ? Choisir avec remise ? Dans les
vrai vie on peut toujours distinguer des objets, mais ce n’est pas ça ce qui importe. Est-ce qu’on
veut distinguer tous les sept objets ? Ou veut-on que tous les objets sont considérés comme distincts.
Ou veut-on que la seule distinction entre ces objets est la couleur. Sans préciser on ne peut pas
répondre (correctement ni incorrectement), car la réponse dépend de ces conditions.
(1, 3, 4, 7·6·5 3
3·2·1 , 7 · 6 · 5, 7 , . . . sont tous des réponses correctes, mais dépendant de ce qu’on veut dire
avec "différents". Pouvez vous trouvez des conditions qui correspondent à ces solutions ? Et autres
réponses raisonnables ?)

1.1. Le cours MAT1500, les mathématiques discrètes. Le cours de mathématiques discrètes

n’est pas une version approfondie d’un cours suivi par tout le monde au collège. Ce sera un peu
de nouveau pour vous. Mais de l’autre côté : la matière n’est pas nouvelle du tout. On a rencontré
déjà les concepts, mais souvent seulement d’une façon implicite.
 MAT1500 3

Sans doute vous avez déjà rencontré les ensembles, leurs éléments, et leurs sous-ensembles. Puis
les applications (ou fonctions) d’un ensemble dans un autre ensemble. Mais quand-même, nous
allons en discuter au début.
Pour donner, ou critiquer, des arguments mathématiques il faut avoir un certain idée de quel
genre d’arguments est acceptable, et de quel genre d’arguments ne l’est pas. On va expliciter les
règles de la logique sous-jacentes. Aussi la rédaction d’une preuve d’une proposition mathématique
utilise des règles de la logique. Par exemple, une preuve par contradiction , souvent utilisé par les
anciens Grecques comme Plato et Euclide, c’est quoi et est-ce que c’est une preuve valide ?
Il y a une méthode de preuve qui utilise de l’induction ("C’est vrai si on prend n = 1, n = 2 et
n = 3 ..., donc c’est vrai pour tout n."), est-ce que c’est acceptable ? Oui, une version d’induction
est acceptée (d’autres ne le sont pas). L’induction mathématique est basée sur les propriétés des
nombres entiers. Nous allons rendre explicit ces propriétés élémentaires. Vous "connaissez" déjà la
plupart de ces propriétés, mais il s’agit ici aussi de fournir les preuves.
Après nous allons compter le nombre d’éléments de certains ensembles, comme dans la théorie
des probabilités. On va établir plusieurs principes de comptage de base. Et appliquer ces principes
dans les situations concrètes, et faire reconnaître quel principe s’applique. Car la différence est
subtile à saisir pour un débutant avec un sens critique encore faible. On va expliquer pourquoi
deux problèmes qui semblent différent à la première vue peuvent avoir la même réponse (avec la
notion de bijection). Si on comprend seulement plus ou moins la théorie, on va facilement faire des
erreurs, et pire, insister qu’on avait raison (plus ou moins).

2. Ensembles

2.1. Ensembles et éléments. 1 Ensembles et leurs éléments sont une modélisation mathématique
de l’idée de collections de différents objets de la vraie vie. Un ensemble E est une collection d’objets,
appelé les éléments de E. On écrit
x ∈ E,
si x est un élément de E et x 6∈ E sinon.
Si un ensemble E a seulement un nombre fini n d’éléments différents, on dit que c’est un ensemble
fini et n est la taille ou la cardinalité de E. On écrit
|E| = n (ou aussi comme #E = n).
Si l’ensemble E n’a pas un nombre fini d’éléments on écrit #E = ∞.
Notation : Soient e1 , e2 , . . . , en les éléments différents de E, alors on écrit
E = {e1 , e2 , . . . , en }
(on écrit une liste de tous les éléments entre deux accolades).
Par exemple, l’ensemble "Chiffres" des chiffres décimales :
Chiffres := {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}.
Commentaire : on a utilisé le symbole ":=" ici pour indiquer "que la partie à la droite de := est
la définition de la partie à la gauche".

1. Voir aussi [R, §1.4].

4 ABRAHAM BROER

Ou l’ensemble des lettres dans l’alphabet français

Alphabet := {a, b, c, d, . . . , x, y, z}.
On utilise ". . ." s’il est clair au lecteur ce qu’il devrait écrire pour compléter.

Définition 2.1. Deux ensembles E1 et E2 sont considérés comme égaux si les deux ensembles ont
les mêmes éléments. On écrit E1 = E2 . Ou en autres mots : on a E1 = E2 par définition si pour
chaque objet x on a x ∈ E1 si et seulement si x ∈ E2 .

Par exemple si E1 := {1, 2, 3} et E2 = {3, 2, 1}, alors E1 = E2 , c’est à dire E1 et E2 sont deux
noms pour ce même ensemble de trois éléments. Donc le même ensemble peut avoir plusieurs noms.
Aussi un même objet peut porter plusieurs noms.
Mais {1, 2, 3} =
6 {a, b, c}, parce que 1 ∈ {1, 2, 3}, mais 1 6= {a, b, c}. Il y a beaucoup d’ensembles
de trois éléments.
Un ensemble sans élément s’appelé un ensemble vide. Voici un premier résultat avec preuve, de
quelque chose fort évidente !

Proposition 2.1. Il existe un seul ensemble vide.

Démonstration. Définissons V := {}, un ensemble avez zero elements ! Donc au moins un ensemble
vide existe !
Supposons V1 est aussi un ensemble vide et x un objet quelconque. Alors on n’a jamais x ∈ V et
on n’a jamais x ∈ V1 , parce que V et V1 n’ont pas d’élément. En particulier :
L’objet x est un élément de V si et seulement si x est un élément de V1 . Donc par définition
d’égalité d’ensembles on conclut que V = V1 . Donc il existe seulement un seul ensemble vide. 
Nous adoptons la notation suivante pour l’ensemble vide : ∅ := {}.

2.1.1. On répète que

{0, 1, 2, 3, 4, 5, 6, 7, 8, 9} = {4, 3, 2, 1, 0, 9, 5, 6, 7, 8};
car l’ordre de l’énumération des éléments n’importe pas. Normalement on fait une énumération des
éléments sans répétition, mais on a le droit de répéter dans une liste définissant un ensemble un
même élément plusieurs fois, mais ça reste le même ensemble.
Et ça est souvent très pratique !
Par exemple
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9} = {0, 1, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 6, 7, 8, 9}.
a exactement dix éléments différents.

Remarque. Dans les mathématiques on utilise surtout des ensembles. Mais de temps en temps on
utilise aussi le concept de "ensemble-avec-multiplicités", appelé multi-ensemble. C’est comme un
ensemble, mais chaque élément vient avec une multiplicité fixée. Par exemple {a, b, b, c, c, c, c} =
{a1 , b2 , c4 } représente un multi-ensemble basé sur l’ensemble {a,b,c}, où par exemple c apparaît
avec la multiplicité 4, ou l’élément c "apparaît" exactement quatre fois dans ce multi-ensemble.
Supposons qu’on a une boîte qui contient 7 objets ; un de type a, deux de type b et quatre de
type c. L’ensemble des types différents est {a, b, c}. Si on ne veut pas distinguer deux objets du
 MAT1500 5

même type (même si on peut distinguer !), on va modéliser par le multi-ensemble {a1 , b2 , c4 }. Par
contre si on veut (et si on peut) différencier les deux objets de type b, disons b1 et b2 , et les quatre
objets de type c, disons c1 , c2 , c3 , c4 on peut modéliser par l’ensemble (ordinaire) de sept éléments
{a, b1 , b2 , c1 , c2 , c3 , c4 }.
Ça dépend du problème qu’on veut résoudre quel ensemble (ou multi-ensemble) on utilise :

{a, b, c}, {a1 , b2 , c4 } ou {a, b1 , b2 , c1 , c2 , c3 , c4 }?!

Ça dépend !
On discutera les multi-ensembles un peu plus tard, car ils sont utiles pour certains problèmes de
comptage. Pour le moment il suffit de savoir que le concept de élément-répété existe dans les multi-
ensembles, mais pas dans les ensembles : dans un ensemble le même élément apparaît exactement
une fois.

2.2. Sous-ensembles. La définition de sous-ensemble.

Définition 2.2. Soient F et E deux ensembles. Si chaque élément de F est aussi un élément de
E, on dit que F est un sous-ensemble de E, et on écrit F ⊆ E.

Un deuxième résultat évident, aussi avec preuve. On a F ⊆ E et E ⊆ F si et seulement si

E=F :

Proposition 2.2 (Sandwich). Soient F et E deux sous-ensembles d’un ensemble U . Si F ⊆ E ⊆ F

alors F = E.

Démonstration. Supposons F et E sont deux sous-ensembles d’un ensemble U tels que F ⊆ E et

E ⊆ F.
Supposons par contre que F 6= E. Par la définition d’égalité d’ensemble ça implique que ce n’est
pas vrai que pour chaque objet x qu’on a x ∈ F si et seulement si x ∈ F . Donc
(i) il existe un e ∈ E tel que e 6∈ F ou
(ii) il existe un f ∈ F tel que f 6∈ E.
Mais le cas (i) est impossible, parce que on suppose E ⊆ F (ce qui veut dire par définition de
sous-ensemble que pour chaque e ∈ E on a e ∈ F ). Et le cas (ii) est aussi impossible, car F ⊆ E.
Donc ce n’est pas vrai que F 6= E.
Il suit que nécessairement F = E. Ce qui était à montrer. 

C’est une preuve valide, mais il y en a d’autres qui sont valides aussi. C’est une question de goût.
Mais n’importe, vous devez être capable de valider cette preuve, même si vous ne l’aimez pas !
Une autre preuve plus directe, qui est aussi valide (mais, en fait les deux preuves sont logiquement
équivalentes comme nous allons voir plus tard) :

Démonstration. Supposons F et E sont deux sous-ensembles d’un ensemble U tels que (i) F ⊆ E
et (ii) E ⊆ F . Par définition de sous-ensembles on obtient
(i) Si x ∈ F alors aussi x ∈ E ;
(ii)Si x ∈ E alors aussi x ∈ F .
Sous ces hypothèses nous voulons montrer que E = F .
6 ABRAHAM BROER

Soit x un objet. Il faut montrer que x ∈ E si et seulement si x ∈ F . En effet, si x ∈ E alors

par l’hypothèse (ii) on a aussi x ∈ F ; en autres mots x ∈ E seulement si x ∈ F . Et si x ∈ F alors
par l’hypothèse (i) on a aussi x ∈ E ; en autre mots x ∈ E si x ∈ F . En combinant, x ∈ E si et
seulement si x ∈ F .
Il suit que F = E, ce qui était à montrer. 

2.3. Définir des sous-ensembles par des propriétés de ces éléments. Soit E un ensemble
et P une propriété qu’un élément de E peut avoir ou pas. Alors
{e ∈ E; e a propriété P } ou {e ∈ E| e a propriété P }
est par définition le sous-ensemble de E des éléments e de E qui ont la propriété P . Il faut que ce
soit claire : chaque e ∈ E a cette propriété, ou ne l’a pas. Pas de zone grise.
Disons E l’ensemble de tous les femmes étudiantes à l’université de Montréal et P la propriété
d’être née avant le 1 janvier 1990. Alors {e ∈ E; e a propriété P } est l’ensemble des femmes étu-
diantes à l’Université de Montréal nées avant le 1 janvier 1990.

Remarque. Dans la vrai vie on utilise seulement une notion d’appartenir à une collection. Aux
mathématiques on utilise deux notions. L’un est "être élément de", et l’autre est "être sous-ensemble
de". Soit a ∈ A un élément. Alors le sous-ensemble de A qui contient seulement a, {a}, est un sous-
ensemble de A et n’est pas un élement de A. Nous distinguons entre a ∈ A et {a} ⊂ A, mais dans la
vraie vie on pense peut-être : "C’est la même chose, non ?". En effet, NON, pas en mathématiques.
Et c’est bon comme ça, ça évitera beaucoup de confusion plus tard ! Il faut s’habituer à cette
distinction tout de suite.

Remarque. Dans la réalité pas chaque "sous-collection" est tout de suite un sous-ensemble, car la
définition d’appartenance pourrait être trop vague. Par exemple, considérons la collection P des
personnes et la "sous-collection" A des adultes. Et prenons une personne, disons Adrien. Alors
Adrien ∈ P . Il devrait avoir deux possibilités seulement : soit Adrien∈ A soit Adrien 6∈ A (pas
les deux simultanément). Mais ce n’est pas clair : oui, il est adulte physiquement, mais non, il
n’est pas adulte mentalement. Qu’est-ce qu’on décide ? Il faut avoir un critère strict. Il ne faut
pas avoir de zone grise pour définir les (sous-)ensembles ou les éléments. Si vous voulez modéliser
des (sous-)collections par la théorie mathématique des (sous-)ensembles il faut être précis dans vos
définitions.

Remarque. Nous avons défini l’alphabet français comme

Alphabet := {a, b, c, d, . . . , x, y, z}.
C’est clair j’espère ? Mais .... Il y a beaucoup de symboles semblables, mais légèrement différents :
a, a, a, a, a, A, A, A, A, ...
Nous avons fait une abstraction sophistiquée dans la vraie vie : nous considérons que tous ces
symboles représentent le même élément a ∈ Alphabet, sans répétition. L’élément a ∈ Alphabet est
vraiment "une classe d’équivalence de symboles" similaires d’un certain façon (en langue mathéma-
tique encore à expliquer).
C’est une des abstractions que font les humains intuitivement. Philosophiquement ce n’est pas
si facile notre définition de l’ensemble Alphabet. La réalité est souvent dur à comprendre de façon
 MAT1500 7

précise, car il y a tellement beaucoup d’abstractions non-explicites et des sous-entendus ! Les ma-
thématiques sont beaucoup plus simples, car les règles sont plus claires. Ce qui est difficile est de
décider de comment utiliser les mathématiques dans les problèmes de la vraie vie.

2.4. Définitions de union, intersection, différence et complément. 2

Soient E et F deux sous-ensembles d’un ensemble U . L’intersection E ∩ F est le sous-ensemble
de U des éléments u ∈ U qui sont simultanément éléments de E et de F . Deux ensembles sont
disjoints si leur intersection est l’ensemble vide.
L’union E ∪ F est l’ensemble des éléments u ∈ U qui sont éléments de E ou de F (c’est permis
d’être élément des deux simultanément aussi).
Souvent on s’imagine implicitement un (très grand) ensemble U (l’ensemble universel pour la
discussion) contenant comme éléments tous les objects on peut imaginer ou construire. On imagine
que chaque ensemble est sous-ensemble de cet ensemble universel. Dans ce cas on définit E ∪ F
comme réunion dans cet ensemble U .
La différence de E et F , notée E − F (où E\F ) est l’ensemble de tous les éléments de E qui ne
sont pas élément de F . Si E ⊆ F est un sous-ensemble, alors on définit le complément E = F − E
(ce qui dépend de F ), est l’ensemble de tous les éléments de F qui ne sont pas élément de E. Alors
E = E.
Par exemple :

{1, 2, 3, 4, 5} ∩ {4, 5, 6, 7} = {4, 5}, {1, 2, 3, 4, 5} − {4, 5, 6, 7} = {1, 2, 3}

et
{1, 2, 3, 4, 5} ∪ {4, 5, 6, 7} = {1, 2, 3, 4, 5, 4, 5, 6, 7} = {1, 2, 3, 4, 5, 6, 7}.
Il y a quelques propriétés, pour la plupart évidentes.

Proposition 2.3. Soient A, B et C trois sous-ensembles de l’ensemble U .

(i) A ∪ ∅ = A ; A ∩ U = A ("Identité") ;
(ii) A ∪ U = U ; A ∩ ∅ = ∅ ("Domination") ;
(iii) A ∪ A = A = A ∩ A ("Idempotence") ;
(iv) (A) = A ("Complémentarité") ;
(v) A ∩ B = B ∩ A ; A ∪ B = B ∪ A ("Commutativité") ;
(vi) A ∪ (B ∪ C) = (A ∪ B) ∪ C ; A ∩ (B ∩ C) = (A ∩ B) ∩ C ("Associativité") ;
(vii) A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) ; A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) ("Distributivité") ;
(viii) (A ∩ B) = A ∪ B, (A ∪ B) = A ∩ B ("Lois de De Morgan").

Démonstration. La vérité de la plupart des propositions est facile à vérifier. Nous avons fait ainsi
en classe. Essayons encore une fois de vous convaincre de cela.
(vii) On veut montrer que A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C).
Soit u ∈ U tel que u ∈ A ∩ (B ∪ C). Alors par définition de l’intersection nécessairement u ∈ A
et u ∈ (B ∪ C). Alors par définition de l’union u ∈ B ou u ∈ C (ou possiblement u est dans tous
les deux). Donc (u ∈ A et u ∈ B) ou (u ∈ A et u ∈ C). Donc u ∈ A ∩ B ou u ∈ A ∩ C. Donc

2. Voir aussi [R, §1.5 ]

8 ABRAHAM BROER

u ∈ (A∩B)∪(A∩C). Donc chaque élément u de A∩(B ∪C) est aussi un élément de (A∩B)∪(A∩C).
Nous avons donc montré que A ∩ (B ∪ C) est un sous-ensemble de (A ∩ B) ∪ (A ∩ C).
Soit maintenant u ∈ U tel que u ∈ (A ∩ B) ∪ (A ∩ C). Par définition de ∪ ça veut dire que
u ∈ (A ∩ B) ou u ∈ (A ∩ C) (ou dans tous les deux). Mais u ∈ (A ∩ B) veut dire que u ∈ A et
u ∈ B. Et u ∈ (A ∩ C) veut dire que u ∈ A et u ∈ C. Il suit que certainement u ∈ A mais aussi
que u ∈ B ou u ∈ C, i.e., u ∈ B ∪ C. Donc u ∈ A ∩ (B ∪ C) et nous avons montré que chaque
élément de (A ∩ B) ∪ (A ∩ C) est aussi un élément de A ∩ (B ∪ C). Donc nous avons montré que
(A ∩ B) ∪ (A ∩ C) est un sous-ensemble de A ∩ (B ∪ C).
En utilisant la proposition du sandwich, prop. 2.2, on conclut : (A ∩ B) ∪ (A ∩ C) = A ∩ (B ∪ C).
Montrer (viii) est un exercice aux tp. 

2.5. Constructions d’ensembles à partir d’ensembles donnés. Nous pouvons construire

beaucoup d’autres ensembles à partir des ensembles déjà donnés. La possibilité de faire des construc-
tions est la raison pourquoi les ensembles sont tellement important : on peut construire presque
n’importe quoi en mathématique en commençant disons avec les nombres naturels.

Définition 2.3. Soit E un ensemble. L’ensemble des sous-ensembles (ou la puissance) d’un en-
semble E est noté P (E) 3.

Donc un élément de P (E) est par définition un sous-ensemble de E. Vous comprenez ?

On va voir que pour chaque ensemble E on a |P (E)| = 2|E| ; en particulier |P (∅)| = 1 (=exercice
de compréhension).

Exemple 2.1. Si E = {a, b, c}, alors P (E) = {{}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}. Il faut
bien comprendre : on peut maintenant considérer {a, b} comme sous-ensemble de E, mais aussi
comme élément de P (E). Et {{a, b}} comme sous-ensemble de P (E) et comme élément de P (P (E)).
La réunion E ∪ P (E) a 11 éléments différents :

E ∪ P (E) = {a, b, c, {}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}.

C’est comme ça ; dans la théorie d’ensembles on a décidé de voir a et {a} comme deux éléments
différents de E ∪ P (E). Et
E ∩ P (E) = ∅.
En particulier :
E ∩ P (E) 6= {∅}
(vous comprenez la différence ? !).

Remarque. En pratique on voudrait peut-être de temps en temps "identifier a avec {a}". C’est
possible de faire ainsi avec une construction dans la théorie d’ensembles en utilisant la notion de
"relation d’équivalence" et "classe d’équivalence", ce qui viendra plus tard. La théorie d’ensembles
nous force d’être précis. Si vous voulez "identifier a avec {a}" vous devez le dire, car ce n’est pas
automatique (c.a.d. il faut définir une relation d’équivalence, et prendre les classes d’équivalence
pour construire un nouveau ensemble, et tout ce tralala).

3. Voir aussi [R, p. 38].

 MAT1500 9

Définition 2.4. Soient E et F deux ensembles. Le produit cartésien de E et F noté E × F est

l’ensemble de tous les couples ordonnées (e, f ) où e ∈ E et b ∈ F 4 :

E × F = {(e, f ); e ∈ E et f ∈ F }.

Par exemple, si E = {1, 2, 3} et F = {1, 2} alors

E × F = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 1), (3, 2)}

a 3 × 2 = 6 éléments En particulier (2, 3) 6∈ E × F .

L’exemple R × R est le plan ordinaire R2 .

Remarque. Si E et F sont des ensembles finis, alors

|E × F | = |E| × |F |.

(Vous voyez pour quoi ?)

Exemple 2.2. Beaucoup de situations dans la vraie vie sont (implicitement) de ce type. Par exemple,
un packet de 52 cartes de jeu.

Valeurs := {2, 3, 4, 5, 6, 7, 8, 9, 10, V, D, R, A}

(V= valet, D=dame, R=roy, A=as).

Enseignes := {♥, ♣, ♦, ♠}
♥ = coeur (hearts), ♣ = trèfle (clubs),♦ = carreau (diamonds), ♠ = pique (spades).
Essentiellement :
Jeu de Cartes = Valeurs × Enseignes.
Exemple : 2♥ et A♣ sont deux éléments de Jeu de Cartes.

Exemple 2.3. On peut répéter et obtenir le produit cartésien de trois (ou plus) d’ensembles. Par
exemple, soit

Heures := {00, 01, 02, . . . , 23},

Minutes := {00, 01, 02, . . . , 59},
Secondes := {00, 01, 02, . . . , 59}.

Et
Montre := Heures × Minutes × Secondes.
Par exemple (10h : 35m : 29s) ∈ Montre.

Exemple 2.4. Soient E et F deux ensembles. On pourrait aussi considérer l’ensemble de tous les
ensembles {e, f } où e ∈ E et b ∈ F . Dans se cas {e, f } = {f, e} et on obtient quelque chose
essentiellement différente de E × F , si E ∩ F 6= ∅, mais beaucoup moins utile que le produit
cartésien.

4. Voir aussi [R, p. 39]

10 ABRAHAM BROER

Par exemple, si E = {1, 2, 3} et F = {1, 2} alors on obtiendrais par définition.

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

si on enlève les répétitions il reste 5 éléments !

Vous comprenez la différence avec E × F ?

Définition 2.5. Soit E un ensemble et n > 0 un entier. On définit E n comme l’ensemble des
suites ordonnées (e1 , e2 , . . . , en ) d’éléments de E de longueur n.

Ici : l’ordre des coefficients importe, et des répétitions sont permises ! Par exemple, (1, 2, 2) ∈ N3
et (1, 2, 2) 6= (2, 1, 2) 6= (1, 2).
(Comparez avez les sous-ensembles de N définis par ces suites {1, 2, 2} ⊆ N et {1, 2, 2} =
{2, 1, 2} = {1, 2}.)
Exemples :

{0, 1}3 = {(0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1)}

and
{a, b, c}2 = {(a, a), (a, b), (a, c), (b, a), (b, b), (b, c), (c, a), (c, b), (c, c)}.

Remarque. Si E est un ensemble fini et n > 0 un entier. Alors

|E n | = |E|n .

Vous voyez pourquoi ?

2.6. Fonctions. Dans les mathématiques modernes les fonctions entre les ensembles sont au moins
aussi importantes que les ensembles soi-mêmes, sinon plus importantes !

Définition 2.6. Soient A et B deux ensembles. Une fonction F de A dans B,

F : A → B,

est l’affectation d’exactement un élément de B, noté F (a) ∈ B, attribué par F à a ∈ A, et ça pour

chaque a ∈ A. 5

On dit aussi "application" à la place de "fonction".

Définition 2.7. Soit F : A → B une fonction.

(i) Alors A est appelé le domaine de F , et B le codomaine de F .
(ii) Soit a ∈ A et posons b := F (a) ∈ B. Alors b est appelé "l’image de a par F " et a est "une
préimage de b".
(iii) Le sous-ensemble de B formé des images des éléments de A est appelé l’image (ou la portée)
de F , Im F .

Donc F est une règle que définit pour chaque a ∈ A une (seule !) image dans B. Mais pas chaque
b a une préimage, et il peut exister plusieurs préimages pour un b ∈ B donné ou aucune.

5. Voir [R, p. 54].

 MAT1500 11

On peut définir une fonction par un formule. Vous avez l’habitude. Par exemple la fonction :
F : N → N, F (m) = m2 + 1.
On peut aussi définir une fonction F "élément par élément" : Par exemple, on définit la fonction
F : Chiffres → Alphabet,
par F (0) = a, F (1) = b, F (2) = a, F (3) = z, F (4) = y, F (5) = c, F (6) = a, F (7) = x, F (8) =
t, F (9) = o. Nous allons une notation plus claire et plus compacte, mais qui donne la même infor-
mation : !
0 1 2 3 4 5 6 7 8 9
F =
a b a z y c a x t o
Ici, la première ligne donne une liste de tous les éléments du domaine de la fonction. La deuxième
ligne donne les images correspondantes.
Remarquez :
!
0 1 2 3 4 5 6 7 8 9
F =
a b a z y c a x t o
!
9 1 2 3 4 5 6 7 8 0
=
o b a z y c a x t a
Tous les éléments de Chiffres apparaissent dans la première ligne, mais pas tous les éléments de
Alphabet dans la deuxième. Et {2, 6, 0} est le sous-ensemble de tous les préimages de a : F (2) =
F (6) = F (0) = a. Mais q n’a aucun préimage.
Permis ? Permis !

2.7. Composition de fonctions. Si le codomaine d’une fonction est égal au domaine d’une autre
fonction, on peut composer ces deux fonctions.

Définition 2.8. Soit F : A → B et G : B → C deux fonctions.

Alors la composition est la fonction
G◦F :A→C
définie par
(G ◦ F )(a) = G(F (a)).

Donc G ◦ F est d’abord appliquer F et puis appliquer G !

Exemple 2.5. Soit A = {a, b, c}, B = {1, 2, 3, 4}, C = N. Et F : A → B donnée par

!
a b c
F := ;
3 2 4
G : B → C donnée par !
1 2 3 4
G := .
13 23 33 4344
Alors G ◦ F : {a, b, c} → N : !
a b c
G◦F =
33 23 4344
12 ABRAHAM BROER

Par exemple
(G ◦ F )(c) = G(F (c)) = G(4) = 4344.

Exemple 2.6. Soit F : N → N, F (n) = n2 + 1 et G : N → N, G(n) = n3 + n. Alors F ◦ G : N → N

et G ◦ F : N → N sont données par :
(F ◦ G)(n) = F (G(n)) = F (n3 + n) = (n3 + n)2 + 1
et
G ◦ F (n) = G(F (n)) = G(n2 + 1) = (n2 + 1)3 + (n2 + 1).

Exercice 2.1. Soient F1 : A → B, F2 : B → C et F3 : C → D trois fonctions. Montrer que

F3 ◦ (F2 ◦ F1 ) = (F3 ◦ F2 ) ◦ F1 comme fonctions de A dans D.

2.8. Quelques exemples de fonctions.

Exemple 2.7. Est-ce que

m(m + 1)(m + 5)
F : N → N, F (m) =
3
m(m+1)(m+5)
est une fonction ? On a des doutes, car 3 semble être une fraction, et pas un nombre
naturel. Mais nous allons montrer que le numérateur de cette fraction est toujours divisible par 3,
donc après division il reste un nombre naturel, comme on voulait. Donc c’est une fonction.
m(m+1)(m+5)
Lemme 2.1. Si m ∈ N alors F (m) = 3 ∈ N.

Démonstration. Soit m ∈ N. Il y a trois cas possibles : existe un nombre naturel a tel que (i)
m = 3a ou (ii) m = 3a + 1 ou (iii) m = 3a + 2.
En cas (i) : on a
3a(3a + 1)(3a + 5)
F (m) = F (3a) = = a(3a + 1)(3a + 5) ∈ N;
3
en cas (ii) on a
(3a + 1)(3a + 2)(3a + 6)
F (m) = F (3a + 1) = = (3a + 1)(3a + 2)(a + 2) ∈ N;
3
et en cas (iii) on a
(3a + 2)(3a + 3)(3a + 7)
F (m) = F (3a + 2) = = (3a + 2)(a + 1)(3a + 7) ∈ N.
3
Dans tous les cas F (m) ∈ N. 

Exemple 2.8. Soit A un ensemble. La fonction identité est la fonction 1A : A → A où

1A (a) = a
pour chaque a ∈ A.
Soit A ⊆ B un sous-ensemble. La fonction inclusion est la fonction ι : A → B :
ι(a) = a
pour chaque a ∈ A.
Si
A = {a, 1, ♥, π, ∅}, B = {a, b, c, 1, 2, 3, ♥, ♣, π, ∅, }
 MAT1500 13

alors !
a 1 ♥ π ∅
1A =
a 1 ♥ π ∅
et !
a 1 ♥ π ∅
ιA = .
a 1 ♥ π ∅
La différence entre 1A et ι est le codomaine (mais la portée et la formule sont les mêmes).

Remarque. Soit F : A → B et G : D → C deux fonctions et B ⊂ D. On peut quand-même définir

la composition, en utlisant ι : B → D, comme la composition G ◦ (ι ◦ F ). Est-ce que c’est ça qu’on
voudrait Oui.

2.9. L’ensemble des fonctions entre deux ensembles. Soient A et B deux ensembles. Nous
notons
Fonctions(A, B) (ou aussi B A ),
pour l’ensemble de toutes les fonctions différentes de A dans B. Donc un élément de Fonctions(A, B) =
B A est par définition une fonction de A dans B.
Exemple :
! ! ! ! !
1 2 1 2 1 2 1 2 1 2
Fonctions({1, 2}, {a, b, c}) = {F1 = , F2 = , F3 = F4 = , F5 = ,
a a a b a c b a b b
! ! ! !
1 2 1 2 1 2 1 2
F6 = , F7 = , F8 = , F9 = }
b c c a c b c c
Remarque. Si A et B sont deux ensembles finis, alors
|Fonctions(A, B)| = |B A | = |B||A| .
Vous voyez pourquoi ? Ça devrait expliquer l’alternatif de notation un peu étrange :
Fonctions(A, B) = B A .

2.10. Injectivité, surjectivité et bijectivité. Une fonction peut avoir des propriétés. Les sui-
vantes sont les plus importantes.

Définition 2.9. Soit F : A → B une fonction. On dit que

(i) F est injective si F (a1 ) = F (a2 ) seulement si a1 = a2 .
(ii) F est surjective si chaque élément de B est l’image d’un élément de A.
(iii) F est bijective si chaque élément de B est l’image d’un seul élément de A.

Conclusion : F est bijective si et seulement si F est injective et surjective. Par exemple, la

fonction inclusion ι est injective, et la fonction identité 1A est bijective.

Proposition 2.4. Soit la fonction F : A → B donnée par la notation "deux-lignes" (sans répétitions
dans la première ligne), disons
!
a1 a2 a3 . . . an
F = .
f1 f2 f3 . . . fn
14 ABRAHAM BROER

Alors la fonction est

(i) injective si et seulement si chaque élément de B se trouve au maximum une fois sur la 2-ième
ligne ;
(ii) surjective si et seulement si chaque élément de B se trouve au minimum une fois sur la
2-ième ligne ;
(iii) bijective si et seulement si chaque élément de B se trouve exactement une fois sur la 2-ième
ligne.

Démonstration. (i) Supposons que chaque élément de B se trouve au maximum une fois sur la
deuxième ligne. Montrons par une preuve directe que F est injective .
Soient a et a0 des éléments de A tels que b = F (a) = F (a0 ). Ces deux éléments a et a0 se
trouvent sur la première ligne, c’est à dire ils existent i et j tels que a = ai et a0 = aj et donc
F (a) = F (ai ) = fi , F (a0 ) = f (aj ) = fj . Nous avons que b = fi = fj . Mais b se trouve au maximum
une fois sur la 2-ième ligne. Ça veut dire i = j et donc a = ai = aj = a0 . Alors nous avons montré
que F est injective (si chaque élément de B se trouve au maximum une fois sur la deuxième ligne).
Supposons F est injective. Nous allons montrer par une preuve indirecte que chaque élément de
B se trouve au maximum une fois sur la deuxième ligne.
Supposons b ∈ B se trouve au moins deux fois sur la 2-ième ligne, disons à positions i et j (i 6= j).
Donc b = fi = fj . Mais fi = F (ai ) et fj = F (aj ), alors F (ai ) = F (aj ) et ai 6= aj . Donc F n’est pas
injective. On conclut la preuve indirecte que si F est injective alors chaque élément de B se trouve
au maximum une fois sur la deuxième ligne.
Ça finit la preuve de (i).
(ii) et (iii) : exercices. 

2.11. Taille et bijectivité.

Exemple 2.9. Soit A := {a, b, c} et B := {1,

! 2, 3, 4}.
a b c
F1 : A → B définie par F1 := est injective,
3 2 1
!
1 2 3 4
F2 : B → A définie par F2 := est surjective. Il n’existe pas de fonction de A
a b c a
dans B qui est surjective et il n’existe pas de fonction de B dans A qui est injective. Vous voyez
pourquoi ?

Cet exemple est motivation pour la proposition suivante et sa preuve.

Proposition 2.5. Soient A et B deux ensembles finis.

(i) Il existe une fonction injective F : A → B si et seulement |A| ≤ |B|.
(ii) Il existe une fonction surjective F : A → B si et seulement si |A| ≥ |B|.
(iii) Il existe une fonction bijective F : A → B si et seulement si |A| = |B|.

Démonstration. Avant de commencer les preuves, fixons une suite ordonnée sans répétitions des
éléments de A, disons
A = {a1 , a2 , . . . , an }
où n = |A|. Il y a beaucoup de façons, mais fixons une manière.
 MAT1500 15

Et fixons aussi une suite ordonnée sans répétitions des éléments de B, disons

B = {b1 , b2 , . . . , bm }

où m = |B|.
(i) Supposons il existe une fonction injective F : A → B. Nous voulons montrer |A| ≤ |B|.
Montrons d’abord par une preuve par l’absurde que dans la suite ordonnée (F (a1 ), F (a2 ), . . . , F (an ))
il n’y a pas de répétition.
Sinon, il y a i 6= j tels que F (ai ) = F (aj ). Par la définition d’injectivité il suit que ai = aj .
Mais dans la suite choisie des ak ’s il n’y a pas de répétions. Donc i = j. et au même temps i 6= j.
Ce qui est absurde. Donc en effet, dans la suite ordonnée (F (a1 ), F (a2 ), . . . , F (an )) il n’y a pas de
répétitions.
Il suit que le sous-ensemble

Im(F ) = {F (a1 ), F (a2 ), . . . , F (an )} ⊆ B

a n = |A| éléments différents. Et le fait que Im(F ) ⊆ B implique que |A| = | Im(F )| ≤ |B|.
Nous venons de montrer que s’il existe une fonction injective F : A → B alors |A| ≤ |B|..
Deuxième partie de la preuve de (i). Supposons |A| ≤ |B|. Il faut montrer qu’il existe une fonction
injective F : A → B.
Définition d’une telle fonction, à l’aide de nos deux suites ordonnées choisies :

F (ai ) := bi

pour chaque 1 ≤ i ≤ n = |A|. Ou en notation "deux-lignes"

!
a1 a2 . . . a n
F := .
b1 b2 . . . bn

Ça fait du sens, car n ≤ m = |B| ! C’est une fonction injective, car la deuxième ligne il n’y a
pas de répétitions, prop. 2.4(ii). Donc en effet si |A| ≤ |B|, alors il existe une fonction injective
F : A → B.
La preuve de (i) est complète.
(iii) Si on a montré (i) et (ii), alors (iii) en suit tout de suite.
La preuve de (ii) est une exercice. 

C’est surtout (iii) qui sera utilisé.

Remarque. On dit que deux ensembles, fini ou pas, A et B sont de même cardinalité s’il existe une
bijection de A dans B, voir [R, p.71]. Par la proposition, si les deux ensembles sont finis, alors ils
sont de même cardinalité si et seulement si |A| = |B|.
Si un ensemble A et l’ensemble N sont de même cardinalité on dit que A est dénombrable.
L’ensemble des nombres entiers, l’ensemble des fractions et l’ensemble des nombres premiers sont
tous dénombrable. Mais l’ensemble des nombres réels n’est pas dénombrable.
16 ABRAHAM BROER

2.12. Fonction inverse.

Théorème 2.1. Soit F : A → B une fonction. Alors F est bijective si et seulement si il existe une
fonction G : B → A telle que F ◦ G = 1B et G ◦ F = 1A .

Dans cette situation cette fonction G est unique, appelée la fonction inverse et notée

G = F −1 .

En fait, parce que F est bijective, pour chaque b ∈ B il existe un unique a ∈ A tel que F (a) = b.
Alors F −1 (b) = a. Une fonction inverse existe seulement si la fonction est bijective.

Démonstration. (Supposons F : A → B est bijective. Définition d’une fonction G : B → A : Soit

b ∈ B, il existe un unique a ∈ A tel que F (a) = b. Posons G(b):=a. Pour chaque a ∈ A on a :

(G ◦ F )(a) = G(F (a)) = G(b) = a.

Donc G ◦ F = 1A . Et pour chaque b ∈ B :

(F ◦ G)(b) = F (G(b)) = F (a) = b.

Donc F ◦ G = 1B .
De l’autre côté, supposons qu’il existe une fonction G : B → A telle que F ◦G = 1B et G◦F = 1A .
Soit b ∈ B. Définissons a := G(b) ∈ A. Alors

F (a) = F (G(b)) = (F ◦ G)(b) = 1B (b) = b.

Donc a est un préimage de b pour F . Nous avons montré que F est surjective.
Supposons a1 , a2 ∈ A tels que F (a1 ) = F (a2 ). Donc

a1 = 1A (a1 ) = (G ◦ F )(a1 ) = G(F (a1 )) = G(F (a2 )) = (G ◦ F )(a2 ) = a2 .

Donc F est aussi injective. On conclut la preuve, car une fonction surjective et injective est auto-
matiquement bijective. 

Preuve du commentaire après le théorème. Supposons F : A → B est injective. Supposons G :

B → A et G0 : B → A telles que G ◦ F = 1A et aussi G0 ◦ F = 1A . Soit b ∈ B. Parce que F est
bijective il existe un a ∈ A tel que F (a) = b. Alors

G(b) = G(F (a)) = (G ◦ F )(a) = 1A (a) = (G0 ◦ F )(a) = G0 (F (a)) = G0 (b

Donc pour chaque b ∈ B on a G(b) = G0 (b), c.-à-d., G = G0 . 

Exemple 2.10. Soit R>0 l’ensemble des nombres réels strictement positifs.
L’application exp : R → R>0 est bijectif. Sa fonction inverse est ln : R>0 → R.

Exemple 2.11. Nous donnons un exemple d’une fonction bijective un peu plus compliqué à com-
prendre, mais la preuve n’est pas difficile.

Théorème 2.2. Soient A et B deux ensembles non-vides. Supposons n = |A| est fini. Il existe une
fonction bijective φ : Fonctions(A, B) → B n .

Ce théorème explique :
 MAT1500 17

Corollaire 2.1. Soient A et B deux ensembles finis non-vides. Posons n = |A|. On a

|Fonctions(A, B)| = |B n |.

Le corollaire est une conséquence directe du théorème et prop.2.5(iii).

Démonstration. Fixons une liste ordonnée des éléments de A, sans répétitions, disons A = {a1 , a2 , . . . , an }.
Posons φ : Fonctions(A, B) → B n par
!!
a1 a2 a3 . . . an
φ F = := (b1 , b2 , b3 , . . . , bn ) ∈ B n .
b1 b2 b3 . . . bn
La fonction inverse de φ est la fonction ψ : B n → Fonctions(A, B)
!
a1 a2 a3 . . . an
ψ((b1 , b2 , . . . , bn )) := F =
b1 b2 b3 . . . bn
Vous comprenez ces notations et pourquoi ψ est en effet l’inverse de φ ? Sinon, essayer de comprendre
mot par mot, et compléter les détails. 
122 ABRAHAM BROER

Département de mathématiques et de statistique, Université de Montréal, C.P. 6128, succursale

Centre-ville, Montréal (Québec), Canada H3C 3J7
E-mail address: [email protected]