Injection, surjection, bijection

Une application f d'un ensemble E vers un ensemble F associe à chaque élément x de E exactement un élément f(x) de F, appelé son image. Elle est injective si deux éléments différents ont toujours des images différentes, surjective si tout élément de F est l'image d'au moins un élément de E, et bijective si elle est les deux à la fois. Ces trois mots reviennent dans chaque sujet d'E3, et ils expliquent des choses très concrètes : pourquoi un chiffrement se déchiffre, pourquoi une fonction de hachage a des collisions, pourquoi une clé primaire identifie une ligne.

Application, image, antécédent

On note f : E → F une application de E (l'ensemble de départ) vers F (l'ensemble d'arrivée), et x ↦ f(x) la règle qui donne l'image de x.

f(x) est l'image de x par f. Elle est unique.
Si f(x) = y, x est un antécédent de y. Un élément de F peut avoir zéro, un ou plusieurs antécédents.

Une application est une relation particulière de E vers F : une partie de E × F, l'ensemble des couples (x ; f(x)), qu'on appelle son graphe. Ce qui la distingue d'une relation quelconque : de chaque élément de E part exactement une flèche.

Certains ouvrages appellent fonction une correspondance où chaque élément de E a au plus une image (certains éléments peuvent ne pas en avoir) et réservent le mot application au cas où chaque élément en a exactement une. Les sujets du BTS parlent d'applications.

Exemples en informatique.

strlen (ou len en Python), qui associe à chaque chaîne sa longueur, est une application de l'ensemble des chaînes vers ℕ.
Dans une table employe dont la colonne id_service est une clé étrangère NOT NULL, l'association « employé ↦ son service » est une application de l'ensemble des employés vers l'ensemble des services : chaque employé a exactement un service.
La conversion d'un octet en entier, de {0 ; 1}⁸ vers {0 ; … ; 255}, est une application.
« Utilisateur ↦ ses ressources accessibles » n'est pas une application vers l'ensemble des ressources : Ana accède à deux ressources. C'est une relation (chapitre 4).

Image directe et image réciproque

Soit f : E → F, A une partie de E et B une partie de F.

L'image directe de A, notée f(A), est l'ensemble des images des éléments de A : f(A) = {f(x) | x ∈ A}. C'est une partie de F.
L'image réciproque de B, notée f⁻¹(B), est l'ensemble des éléments de E dont l'image est dans B : f⁻¹(B) = {x ∈ E | f(x) ∈ B}. C'est une partie de E.

L'ensemble f(E), toutes les images, s'appelle l'image de f.

Exemple corrigé. E = {1 ; 2 ; 3 ; 4 ; 5}, F = {a ; b ; c ; d}, et f est définie par : f(1) = a, f(2) = b, f(3) = a, f(4) = c, f(5) = c.

f({1 ; 3}) = {a} : 1 et 3 ont la même image, qui ne compte qu'une fois.
f({2 ; 4}) = {b ; c}.
f(E) = {a ; b ; c} : d n'est l'image d'aucun élément.
f⁻¹({a ; b}) = {1 ; 2 ; 3} : ce sont les éléments dont l'image est a ou b.
f⁻¹({c}) = {4 ; 5}.
f⁻¹({d}) = ∅ : d n'a pas d'antécédent.

En SQL, l'image réciproque est une simple sélection. Avec l'application « employé ↦ service », l'image réciproque de {service 2} est l'ensemble des employés du service 2 : SELECT * FROM employe WHERE id_service = 2. L'image f(E) est l'ensemble des services qui ont au moins un employé : SELECT DISTINCT id_service FROM employe.

Injection

Démontrer qu'une application est injective. On suppose f(x) = f(x′) et on en déduit x = x′.

f : ℝ → ℝ, f(x) = 3x − 7. Soient x, x′ ∈ ℝ tels que f(x) = f(x′). Alors 3x − 7 = 3x′ − 7, donc 3x = 3x′, donc x = x′. f est injective.

Démontrer qu'une application n'est pas injective. On exhibe deux éléments différents qui ont la même image.

g : ℝ → ℝ, g(x) = x². g(−2) = g(2) = 4 avec −2 ≠ 2 : g n'est pas injective.

En informatique, l'injectivité garantit qu'on ne perd pas d'information :

une clé primaire est une colonne dont l'application « ligne ↦ valeur de la clé » est injective : deux lignes différentes n'ont jamais la même clé ;
une compression sans perte (ZIP, PNG) doit être injective, sinon deux fichiers différents donneraient la même archive et on ne saurait pas lequel restituer ;
un codage de caractères (ASCII, UTF-8) est injectif : deux caractères différents ont des codes différents.

Surjection

Démontrer qu'une application est surjective. On prend un y quelconque de F et on trouve un antécédent, en général en résolvant l'équation f(x) = y.

f : ℝ → ℝ, f(x) = 3x − 7. Soit y ∈ ℝ. f(x) = y ⟺ 3x − 7 = y ⟺ x = (y + 7) / 3, qui est un réel. Tout y a un antécédent : f est surjective.

Démontrer qu'une application n'est pas surjective. On exhibe un élément de F sans antécédent.

g : ℝ → ℝ, g(x) = x². −1 n'a pas d'antécédent, car un carré n'est jamais négatif : g n'est pas surjective.

La surjectivité dépend de l'ensemble d'arrivée : g(x) = x² vue comme application de ℝ vers [0 ; +∞[ est surjective. C'est pour cela qu'on précise toujours E et F.

En SQL, l'application « employé ↦ service » est surjective si chaque service a au moins un employé. Les services sans antécédent se trouvent avec un LEFT JOIN et un test IS NULL (jointures externes) : tester la surjectivité, c'est chercher les éléments de F sans antécédent.

Bijection

Lire un diagramme sagittal : on compte les flèches qui partent de E (une seule par élément pour une application), puis celles qui arrivent dans F.

f : E → F	Flèches qui arrivent sur chaque élément de F	Antécédents de chaque y ∈ F
Injective	0 ou 1	au plus un
Surjective	1 ou plus	au moins un
Bijective	exactement 1	exactement un

Une application peut n'être ni injective ni surjective : c'est le cas de l'exemple f(1) = a, f(2) = b, f(3) = a, f(4) = c, f(5) = c (a a deux antécédents, d n'en a aucun).

Exemples sur les nombres.

Application	Injective	Surjective	Pourquoi
ℕ → ℕ, n ↦ 2n	Oui	Non	2n = 2n′ donne n = n′ ; 3 n'a pas d'antécédent
ℤ → ℕ, x ↦ \|x\|	Non	Oui	\|−1\| = \|1\| ; tout n ∈ ℕ est l'image de n
ℤ → ℤ, x ↦ x + 3	Oui	Oui	L'antécédent de y est y − 3
ℝ → ℝ, x ↦ x²	Non	Non	(−2)² = 2² ; −1 n'a pas d'antécédent
[0 ; +∞[ → [0 ; +∞[, x ↦ x²	Oui	Oui	L'antécédent de y est √y

Le cas des ensembles finis : compter suffit souvent

Si E et F sont finis, le nombre de flèches donne des conditions nécessaires :

si f est injective, les card(E) images sont toutes différentes, donc card(E) ≤ card(F) ;
si f est surjective, il faut au moins card(F) éléments au départ, donc card(E) ≥ card(F) ;
si f est bijective, card(E) = card(F).

Et quand card(E) = card(F), les trois propriétés se confondent : une application injective est aussi surjective, et inversement. Pour montrer qu'une application entre deux ensembles de même cardinal est bijective, il suffit donc de vérifier qu'elle est injective.

Application réciproque d'une bijection

Si f : E → F est bijective, chaque y de F a exactement un antécédent. On définit ainsi l'application réciproque f⁻¹ : F → E, qui associe à y son unique antécédent :

f⁻¹(y) = x si et seulement si f(x) = y.

Pour la calculer, on résout f(x) = y en exprimant x en fonction de y.

Exemple. f : ℝ → ℝ, f(x) = 3x − 7 est bijective (injective et surjective, démontré plus haut). En résolvant y = 3x − 7, on trouve x = (y + 7) / 3 : f⁻¹(y) = (y + 7) / 3. Vérification : f⁻¹(f(2)) = f⁻¹(−1) = (−1 + 7) / 3 = 2.

Seule une bijection a une réciproque. Une application non injective ne peut pas « revenir en arrière » : de l'image 4, impossible de savoir si on venait de 2 ou de −2.

Application au chiffrement affine

Le chiffrement affine remplace chaque lettre, numérotée de 0 (A) à 25 (Z), par la lettre de numéro y = (ax + b) mod 26. C'est une application de E = {0 ; 1 ; … ; 25} vers E. Pour qu'on puisse déchiffrer, elle doit être bijective.

Avec a = 3 et b = 5. f(x) = (3x + 5) mod 26.

B (1) donne 3 × 1 + 5 = 8, soit I.
T (19) donne 3 × 19 + 5 = 62 ≡ 10 [26], soit K.
S (18) donne 3 × 18 + 5 = 59 ≡ 7 [26], soit H.

« BTS » se chiffre « IKH ». Pour déchiffrer, on cherche la réciproque : y ≡ 3x + 5 [26] donne 3x ≡ y − 5 [26]. Comme 3 × 9 = 27 ≡ 1 [26], 9 est l'inverse de 3 modulo 26 : on multiplie par 9, x ≡ 9(y − 5) ≡ 9y − 45 ≡ 9y + 7 [26]. Contrôle : I (8) donne 9 × 8 + 7 = 79 ≡ 1 [26], soit B.

Avec a = 2. f(x) = 2x mod 26 n'est pas injective : f(0) = 0 et f(13) = 26 ≡ 0 [26]. A et N se chiffrent pareil, et un message chiffré ne se déchiffre plus. La clé a doit être première avec 26 (pas de diviseur commun avec 26 autre que 1) : 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23 ou 25. Les congruences sont expliquées dans le cours d'arithmétique ; ici, on a trouvé l'inverse de 3 en cherchant le nombre k tel que 3k ≡ 1 [26], soit k = 9. Le même cours détaille le calcul d'un inverse modulaire et le chiffrement affine complet.

Composée de deux applications

Soient f : E → F et g : F → G. La composée g∘f (lue « g rond f ») est l'application de E vers G qui applique d'abord f, puis g :

(g∘f)(x) = g(f(x))

Exemple sur les réels. f(x) = x + 1 et g(x) = 2x.

(g∘f)(x) = g(x + 1) = 2(x + 1) = 2x + 2, donc (g∘f)(3) = 8.
(f∘g)(x) = f(2x) = 2x + 1, donc (f∘g)(3) = 7.

Exemple sur des ensembles finis, comme dans les QCM d'E3. E = {1 ; 2 ; 3}, F = {a ; b ; c}, G = {x ; y}. f(1) = b, f(2) = a, f(3) = b ; g(a) = y, g(b) = x, g(c) = y.

(g∘f)(1) = g(f(1)) = g(b) = x
(g∘f)(2) = g(a) = y
(g∘f)(3) = g(b) = x

Sur deux diagrammes sagittaux, on suit la flèche de f, puis la flèche de g qui part de l'élément atteint. C'est le type de question posé dans le QCM du sujet E3 de 2026, qui demandait l'image d'un élément par g∘f (corrigé).

(g∘f)(1) = g(f(1)) = g(b) = x : on suit la flèche de f, puis celle de g.

Propriétés utiles.

La composée de deux injections est injective ; de deux surjections, surjective ; de deux bijections, bijective.
Si f est bijective, f⁻¹∘f est l'identité de E (x ↦ x) et f∘f⁻¹ l'identité de F : déchiffrer un message chiffré redonne le message.
En programmation, composer, c'est enchaîner : trim(strtolower($saisie)) en PHP est la composée « mettre en minuscules, puis retirer les espaces ». Un pipeline Unix cut … | sort | uniq est une composée de trois traitements.

Exercices

Exercice 1 sur 5 Reconnaître une application Réussi À revoir

Pour chaque correspondance de E vers F, dis si c'est une application ; si oui, si elle est injective, surjective, bijective.

E = {1 ; 2 ; 3 ; 4}, F = {a ; b ; c ; d} : 1 → b, 2 → d, 3 → a, 4 → c.
E = {1 ; 2 ; 3 ; 4}, F = {a ; b ; c ; d} : 1 → a, 2 → a, 3 → b, 4 → c.
E = {1 ; 2 ; 3 ; 4}, F = {a ; b ; c ; d} : 1 → a, 1 → b, 2 → c, 3 → d, 4 → d.
E = {1 ; 2 ; 3}, F = {a ; b ; c ; d} : 1 → a, 2 → c, 3 → d.