Chapitre I

Introduction à la théorie des ensembles

I.1 Notions sur les ensembles

I.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 I.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 I.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 I.3. Les langages de programmation actuels exigent que certaines variables soient décla-
ré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.

I.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 I. I NTRODUCTION À LA THÉORIE DES ENSEMBLES 6

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 I.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.

I.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 I.4. L’ensembe {Pierre ; Paul ; Marie ; Julie ; Karim} se représente par :

Julie Pierre
×
×
Karim
×
Marie
×
Paul
×

I.2 Sous-ensembles
I.2.1 Inclusion
Définition I.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 I.2. Pour tout ensemble A on a ∅ ⊆ A et A ⊆ A.

Exemple I.5. On a {1, 2} ⊆ {1, 2, 3}.
N Z Q R C.
Bien sûr on a ⊆ ⊆ ⊆ ⊆

Définition I.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.

I.2.2 Ensemble des parties

Définition I.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 I.6. Si A = {1, 2, 3} alors P ( A) = {∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}.
 7 I.3. Opérations sur les ensembles

Remarque I.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.

I.3 Opérations sur les ensembles

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

I.3.1 Union et Intersection

Définition I.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 I.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 I.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 I.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 I.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 )

I.3.2 Différence et complémentaire

Définition I.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 I.7 (Différence symétrique). La différence symétrique entre les ensembles A et B est l’en-
semble 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 I.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.
 Chapitre I. I NTRODUCTION À LA THÉORIE DES ENSEMBLES 8

Remarque I.4. Il faut obligatoirement se placer dans un ensemble de référence pour définir la com-
plémentation.
Proposition I.4 Propriétés de la complémentation
La complémentation a plusieurs propriétés :
Involution : A = A
Loi de Morgan : A ∩ B = A ∪ B et A ∪ B = A ∩ B

A B

Ω
n D Diff
io iff éren
ct ér ce sy
on
Uni r se 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 I.1 – Exemples de constructions d’ensembles à partir des ensembles A et B contenus dans
l’univers Ω

I.3.3 Produit cartésien

Définition I.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 I.5. Le couple ( a, b) n’est pas un ensemble.

Si a 6= b alors ( a, b) est distinct de (b, a).
Exemple I.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 .
 Chapitre II
Notions sur les langages

II.1 Exemples de problèmes

La notion de langage est utilisée pour modéliser différents problèmes où l’information est sto-
ckée sous une forme de chaîne de caractères. Voici quelques exemples :
— Langage naturel : chaque mot est formé par un ensemble de lettres concaténées. L’ensemble
des mots forme un dictionnaire. Puis ces mots sont organisés pour former des phrases. Dans
ce cas, une structure apparaît qui est régie par la grammaire de la langue utilisé.
— Stocker de l’information sur un disque dur : toute information stockée sur un disque dur
est codée par une succession de bits (0 ou 1), que ce soit du texte, image, musique... On
peut se demander s’il est possible de compresser cette information, c’est-à-dire trouver une
fonction qui a un chaîne de {0, 1} renvoie de manière bijective une chaîne plus courte.
— Recherche de chaîne de caractères dans un texte.
— Compilation : un programme est une suite de caractères. Un compilateur s’intéresse essen-
tiellement aux deux choses suivantes :
— Analyse lexicale : on cherche les éléments de bases qui structurent le programme (If, For,
While, affectation...).
— Analyse syntaxique : on vérifie que les expressions sont correctes (ex : var + var ∗ var va
être interprété comme var + (var ∗ var )).
— Bio-informatique : l’ADN code l’information génétique à l’aide de 4 bases azotées : adénine
(A), cytosine (C), guanine (G) ou thymine (T).

II.2 Mots sur un alphabet fini

II.2.1 Un peu de vocabulaire
Alphabet Un alphabet A est un ensemble fini dont les éléments sont appelés des lettres.
Exemple II.1. 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.

Mots sur un alphabet fini Un mot est une suite finie d’éléments de A on le note u = u1 u2 . . . un
et n est la longueur du mot u, notée |u|. Le mot vide est noté ε.
On note A∗ l’ensemble des mots sur A et A+ l’ensemble des mots sans le mot vide.

Opérations sur les mots 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 = u1 u2 . . . u|u| v1 v2 . . . v|v| .
 Chapitre II. N OTIONS SUR LES LANGAGES 10

Pour n ∈ N
on définit par récurrence la puissance d’un mot par u0 = ε et un+1 = u.un pour
n∈ . N
On dit que v est un préfixe de u s’il existe un mot w tel que u = v.w et v est un suffixe de u s’il
existe un mot w tel que u = w.v.

Distance sur les mots On peut définir différentes distances sur les mots. On s’intéressera ici à
la distance édition définie comme étant le plus petit nombre d’opérations d’édition élémentaires
nécessaires pour transformer le mot u en le mot v. Les opérations d’édition élémentaires sont la
suppression ou l’insertion d’un symbole.
De multiples variantes de cette notion de distance ont été proposées, qui utilisent des en-
sembles d’opérations différents et/ou considèrent des poids variables pour les différentes opé-
rations. Pour prendre un exemple réel, si l’on souhaite réaliser une application qui « corrige » les
fautes de frappe au clavier, il est utile de considérer des poids qui rendent d’autant plus proches
des séquences qu’elles ne diffèrent que par des touches voisines sur le clavier, permettant d’inté-
grer une modélisation des confusions de touches les plus probables.
L’utilitaire Unix diff implante une forme de calcul de distances. Cet utilitaire permet de com-
parer deux fichiers et d’imprimer sur la sortie standard toutes les différences entre leurs contenus
respectifs.

II.2.2 Propriété d’équidivisibilité

Lemme II.1 Lemme de Levi

Soient u, v, z, t des mots sur l’alphabet A tels que uv = zt. Alors il existe un mot w ∈ A∗ tel
qu’un des deux cas suivant est vérifié :
— ou bien u = zw et t = wy si |u| ≥ |z|,
— ou bien z = uw et v = wt si |u| ≤ |z|.

Démonstration : On considère que uv = zt = a1 a2 . . . an où les ak sont des lettres de A. Soit i l’entier tel
que u = a1 a2 . . . ai et v = ai+1 . . . an . De même soit j l’entier tel que z = a1 a2 . . . a j et t = a j+1 . . . an .
Si |u| ≥ |z|, alors i ≥ j et on a u = zw et t = wv avec w = a j+1 . . . ai .
Si au contraire |u| ≤ |z|, alors i ≤ j et on a z = uw et v = wt avec w = ai+1 . . . a j .

Graphiquement cela signifie que l’on a une des deux décompositions suivantes :

u v u v
w ou bien w
z t z t

Exemple II.2. Soient u = anti, v = constitutionnellement, z = anticonstitutionnel, t = lement quatre

mots. Comme anti.constitutionnellement = anticonstitutionnel.lement, et que de plus | anti | ≤
| anticonstitutionnel | alors il existe le mot w = constitutionnel tel que anticonstitutionnel = anti.constitutionnel
et constitutionnellement = constitutionnel.lement.
Une conséquence importante : si on applique le Lemme de Levi avec u = z, on a w = e et donc
v = t. On en déduit que si uv = ut alors v = t, autrement dit, on peut simplifier à gauche. De
même, on peut simplifier à droite une équation sur les mots.

Proposition II.2
Soient u, v, z et t ∈ A∗ . Si uv = ut alors v = t.
De même si uv = zv alors u = z.
 11 II.3. Langage

II.3 Langage
II.3.1 Définition et exemples de langages
Un langage L sur un alphabet fini A est un ensemble de mots définis sur A autrement dit
L ⊆ A∗ .
Exemple II.3. Exemples de langages sur B = {0, 1} :
— ∅ 6= {ε} ;
— B∗ = {ε, 0, 1, 00, 01, 10, 11, 000, 001, . . .} ;
— B+ = {0, 1, 00, 01, 10, 11, 000, 001, . . .} ;
— tout ensemble fini de mots ;
— { 0n : n ∈ } ; N
— {0n 1m : n, m ∈ } ; N
— { 0n 1n : n ∈ } ; N
N
— {0 p : p ∈ nombre premier} ;
— {u ∈ B∗ : u est le codage en binaire d’un nombre premier} ;
— {u ∈ B∗ : u est un palindrome} ;
— {u ∈ B∗ : u est un code html certifié} 6= {u ∈ A∗ : u est un code html bien interprété par Firefox} ;
— {u ∈ B∗ : u est le codage en MP3 de votre chanson préférée} ;
— {u ∈ B∗ : u est le codage en assembleur d’un programme qui s’arrête sur l’entrée vide} ;
— ...

II.3.2 Opérations sur les langages

Soient L, L1 et L2 des langages sur un alphabet fini A. On peut définir différentes opérations
sur les langages :
— Union : L1 ∪ L2 langage comportant des mots de L1 ou de L2 ;
— Intersection : L1 ∩ L2 langage comportant des mots de L1 et de L2 ;
— Compémentaire : L langage comportant des mots de A∗ qui ne sont pas dans L ;
— Concaténation : L1 .L2 langage comportant les mots formés en concaténant un mot L1 à un
mot de L2
L1 .L2 = {u1 .u2 : u1 ∈ L1 et u2 ∈ L2 };
— Puissance : On définit par récurrence la puissance nème de L, notée Ln par

L0 = {ε} et Ln+1 = L.Ln .

Attention, il ne faut pas confondre, on a Ln = {u ∈ A∗ : il existe u1 , u2 , . . . , un ∈ L tel que u =

N
u1 .u2 . · · · .un } qui en général est différent de {un : n ∈ }.
— Fermeture de Kleene : On définit

L∗ =
[ [
Ln et L+ = Ln .
n ≥0 n >0

Exemple II.4. Considérons les langages L1 = { a}, L2 = { ab, ba} et L3 = {e, a} on a :

— L1 ∪ L2 = { ab, ba, a}, L2 ∪ L3 = { ab, ba, a, e} et L1 ∪ L3 = { a, e} ;
— L1 ∩ L2 = ∅, L2 ∩ L3 = ∅ et L1 ∩ L3 = { a} ;
— L1 .L2 = { aab, aba}, L1 .L3 = { a, aa} et L2 .L3 = { ab, aba, ba, baa} ;
N
— pour n ∈ , on a L1n = { an tel que n ∈ } ; N
— on a abbaab ∈ L2∗ car abbaab = ab.ba.ab et ab ∈ L2 et ba ∈ L2 ;
— on a abbab ∈ / L2∗ car un mot de L2∗ est de longueur paire.

II.3.3 Equations sur les langages

Proposition II.3 Le lemme d’Arden

Soient M et N deux langages sur A tels que ε ∈ / M. L’équation sur les langages X =
M.X ∪ N où X est le langage inconnu, admet pour unique solution M∗ .N .
Chapitre II. N OTIONS SUR LES LANGAGES 12
 Chapitre III
Fonctions et applications

La notion d’application permet d’associer à chaque élément d’un ensemble un élément d’un
autre ensemble. En informatique, on a souvent de cette notion pour passer d’un objet à sa représen-
tation, pour traduire une représentation vers une autre, comme support de preuves de propriétés
de programmes, etc...

III.1 Premières notions

III.1.1 Définition
Définition III.1 (Fonction). Soient E et F deux ensembles. Une fonction f : E → F (de E dans F) est
définie par un sous-ensemble de G f ⊆ E × F tel que pour tout x ∈ E, il existe au plus un y ∈ F tel
que ( x, y) ∈ G f . Quand il existe, on note cet élément par f ( x ). L’élément x est alors l’antécedent de
y et y est l’image de x. On note aussi f : x 7−→ y le fait que f associe l’élément y comme image de
x.
Exemple III.1. Soit E = {1, 2, 3, 4} et F = { a, b, c}.
On définit la fonction f par le graphe :

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

Autrement dit
f :E −→ F
1 7−→ a
2 7−→ c
4 7−→ a
On dit que a est l’image de 1 par f ou bien que 1 est un antécédent de a par f .
Par contre l’ensemble H = {(1, a), (2, c), (4, a)} ⊆ E × F n’est pas le graphe d’une fonction.
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) = {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 }
 Chapitre III. F ONCTIONS ET APPLICATIONS 14

Définition III.3 (Domaine de définition, Image). Le domaine de définition d’une fonction f : E → F,

noté Dom( f ) est l’ensemble des éléments de x ∈ E qui ont une image par f . Autrement dit :

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

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) = {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), (4, a)} ⊆ E × F.
On a :
— f ({1}) = { a}, f ({1, 4}) = { a}, f ({3}) = ∅ et f ({1, 2, 3}) = { a, c} ;
— f −1 ({ a}) = {1, 4}, f −1 ({ a, c}) = {1, 2, 4}, f −1 (∅) = ∅ et f −1 ({b}) = ∅ ;
— le domaine de la fonction f est Dom( f ) = { a, c} ;
— l’image de la fonction f est Im( f ) = {1, 2, 4}.

Définition III.4 (Egalité). Deux fonctions f : E → F et g : E → F sont égales si G f = Gg ou de

manière équivalente si Dom( f ) = Dom( g) et f ( x ) = g( x ) pour tout x ∈ Dom( f ).

Définition III.5 (Application). Une application de E dans F est une fonction de E dans F telle que
Dom( f ) = E . On note F E l’ensemble des applications de E dans F.

Exemple III.3. Soit E = {1, 2, 3, 4}, E0 = {1, 2, 4} et F = { a, b, c}.

Le graphe G = {(1, a), (2, c), (4, a)} ⊆ E × F définit une fonction de E dans F mais pas une
application.
Par contre G définit une application de E0 dans F.

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

Un autre exemple est le code ASCII qui permet d’associer à chaque entier entre 0 et 127 un
caractère :
15 III.1. Premières notions

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.
 Chapitre III. F ONCTIONS ET APPLICATIONS 16

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 de fonction et d’applications

Définition III.6 (Composition). On considère les fonctions f : E → F et g : F → G. On définit la
fonction 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 s’il existe.
Le domaine de définition de g ◦ f est donné par :
Dom( g ◦ f ) = { x ∈ Dom( f ) : f ( x ) ∈ Dom( g)}
Attention, en général, on considère la composée d’applications pour s’abstraire des contraintes
de domaines de définition.
Exemple III.4. 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
β
d × 4
× × ×
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
 17 III.2. Propriétés sur les fonctions

Remarque III.1. 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 ).
Remarque III.2. Attention 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 singuliè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 , . . . , a k ) 7−→ ai

III.2 Propriétés sur les fonctions

III.2.1 Injection et surjection
Définition III.10 (Fonction injective). Une fonction est injective si tout élément de l’espace d’arri-
vée admet au plus un antécédent.

Définition III.11 (Fonction surjective). Une fonction est surjective si chaque élément de l’espace
d’arrivée admet au moins un antécédent.
Autrement dit, si f : E → F est une fonction alors Im( f ) = f ( E) = F.

III.2.2 Bijection et application réciproque

Définition III.12 (Application bijective). Une application qui est à la fois injective et surjective est
bijective.

Attention, en général, la notion de bijection est utilisé pour les applications.

Proposition III.2
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 .