Exercices corrigés : fonctions injectives, surjectives et bijectives (201-N11)

a) Les fonctions sont (1) et (4). La relation (2) échoue sur l'EXISTENCE : l'élément 2 n'a aucune flèche qui en part, donc $f(2)$ ne désigne rien et l'écriture elle-même perd son sens. La relation (3) échoue sur l'UNICITÉ : deux flèches partent de 1, vers $a$ et vers $b$, donc $f(1)$ désignerait deux objets à la fois. Le test se lit d'un coup d'oeil sur un diagramme sagittal : il faut EXACTEMENT UNE flèche au départ de CHAQUE élément de gauche. Ni zéro, ni deux. Rien n'est exigé à l'arrivée en revanche : un élément de $B$ peut recevoir zéro, une ou dix flèches sans qu'on quitte le cadre des fonctions. C'est précisément cette dissymétrie entre le départ et l'arrivée qui produira l'injectivité et la surjectivité dans les exercices suivants.

b) $f(1) = a$, $f(2) = b$, $f(3) = b$. L'ensemble image est $f(A) = \{a, b\}$, de cardinal 2. On ne l'écrit pas $\{a, b, b\}$ : un ensemble ne compte pas les répétitions, et c'est exactement pour cela que le cardinal de l'image peut être strictement plus petit que celui du départ. Ici $\lvert f(A) \rvert = 2 < 3 = \lvert A \rvert$. La perte d'un élément est le signe visible que deux flèches arrivent au même endroit.

c) Oui, la relation (4) est une fonction : chacun des trois éléments de $A$ a exactement une flèche, et rien n'interdit qu'elles aboutissent toutes au même point. C'est la fonction constante de valeur $c$. Son ensemble image est $f(A) = \{c\}$, de cardinal 1. L'erreur classique consiste à la rejeter en disant que $c$ reçoit trois flèches : cette condition n'existe pas. Elle coûte la question entière alors qu'il suffisait de relire la définition.

d) Deux éléments de $A$ peuvent parfaitement avoir la même image, la relation (4) en donne l'exemple extrême. C'est même exactement le défaut qu'on appellera la non-injectivité. En revanche deux éléments de $B$ ne peuvent jamais avoir le même antécédent : cela voudrait dire qu'un élément de $A$ possède deux images, ce que l'unicité interdit. Retenez la formulation dissymétrique : une fonction a le droit d'ÉCRASER, elle n'a pas le droit de SE DÉDOUBLER.

e) Une fonction de $A$ vers $B$ contient exactement $\lvert A \rvert = 3$ couples, un par élément du départ, jamais un de plus ni un de moins. Le produit cartésien $A \times B$, lui, compte $3 \times 3 = 9$ couples, et il possède $2^{9} = 512$ parties, donc il existe 512 relations de $A$ vers $B$. Les fonctions sont donc une minorité étroite parmi les relations, $3^{3} = 27$ sur 512, soit environ 5,3 pour cent. Ce comptage se reverra à l'exercice 7, où il servira à compter les injections et les bijections.

a) $f(E) = \{a, b, c\}$, de cardinal 3. L'élément $d$ n'a aucun antécédent : aucune flèche ne lui arrive, on dit qu'il n'est pas ATTEINT. L'ensemble image est donc une partie stricte de $F$, et c'est exactement ce qui fera dire à l'exercice 3 que $f$ n'est pas surjective. Le réflexe à prendre : l'image n'est pas l'arrivée, c'est la partie de l'arrivée réellement utilisée, et les deux coïncident seulement dans le cas surjectif.

b) $f(P) = \{f(1), f(3), f(4)\} = \{a, a, b\} = \{a, b\}$, de cardinal 2 alors que $\lvert P \rvert = 3$. $f(P') = \{f(2), f(5)\} = \{c\}$, de cardinal 1 alors que $\lvert P' \rvert = 2$. La règle générale est $\lvert f(P) \rvert \le \lvert P \rvert$, avec égalité exactement quand $f$ ne confond aucun élément de $P$. Une image ne grandit jamais : c'est le premier résultat de cardinalité du chapitre, et c'est de lui que sortira l'inégalité $\lvert A \rvert \le \lvert B \rvert$ associée à une injection.

c) $f^{-1}(\{a\}) = \{1, 3, 6\}$, les trois éléments dont l'image vaut $a$. $f^{-1}(\{c\}) = \{2, 5\}$. $f^{-1}(\{d\}) = \varnothing$ : aucun antécédent, et l'ensemble vide est une réponse parfaitement légitime, pas un échec de calcul. Enfin $f^{-1}(\{a,b\}) = \{1,3,6\} \cup \{4\} = \{1,3,4,6\}$. Le piège classique consiste à répondre un ÉLÉMENT quand $f^{-1}$ rend un ENSEMBLE : $f^{-1}(\{b\})$ vaut $\{4\}$ et non $4$, et la distinction est celle que le chapitre des ensembles faisait déjà entre $3$ et $\{3\}$.

d) Les quatre ensembles sont $\{1,3,6\}$, $\{4\}$, $\{2,5\}$ et $\varnothing$. Leur réunion vaut bien $\{1,2,3,4,5,6\} = E$, puisque tout élément a une image et figure donc dans exactement une de ces parties, et le total des cardinaux donne $3+1+2+0 = 6$. Ils sont deux à deux disjoints, car un élément ne peut pas avoir deux images. On retrouve donc une PARTITION de $E$, aux parties vides près : ce sont les classes de la relation d'équivalence avoir la même image, étudiée au chapitre des relations. Chaque ensemble $f^{-1}(\{y\})$ s'appelle une FIBRE de $f$ au-dessus de $y$, et le mot servira tel quel à l'exercice 9 sur le hachage.

e) Non, et c'est le contresens le plus fréquent du chapitre. L'écriture $f^{-1}(Q)$, avec un ENSEMBLE entre les parenthèses, est définie pour toute fonction sans exception : elle désigne une partie du départ, obtenue en remontant les flèches. La FONCTION réciproque $f^{-1} : F \to E$, elle, n'existe que si $f$ est bijective, et notre $f$ ne l'est pas du tout, puisque $d$ n'a aucun antécédent et $a$ en a trois. Deux notations identiques, deux objets différents : l'une prend un ensemble et rend un ensemble, l'autre prendrait un élément et rendrait un élément. Confondre les deux fait écrire $f^{-1}(a) = 1$, ce qui ne veut rien dire ici et coûte tous les points de la question.

a) Case (1) : chaque élément de $B$ reçoit au plus une flèche, mais $d$ n'en reçoit aucune, donc la fonction est INJECTIVE SEULEMENT. Case (2) : les trois éléments de $B$ sont atteints, mais $a$ reçoit deux flèches, celles de 1 et de 2, donc SURJECTIVE SEULEMENT. Case (3) : chaque élément de $B$ reçoit exactement une flèche, donc BIJECTIVE. Case (4) : $a$ en reçoit deux et $b$ aucune, donc AUCUNE DES TROIS. Le comptage des flèches reçues est le seul geste à retenir pour un ensemble fini : au plus une donne l'injectivité, au moins une la surjectivité, exactement une la bijectivité. Les flèches PARTIES, elles, ne se comptent pas : elles ont déjà servi à décider que l'objet est une fonction.

b) De $\mathbb{R}$ dans $\mathbb{R}$ : pas injective, car $f(-2) = f(2) = 4$ avec $-2 \ne 2$, et un seul contre-exemple suffit ; pas surjective non plus, car $-1$ n'a aucun antécédent, un carré de réel n'étant jamais négatif. De $\mathbb{R}^{+}$ dans $\mathbb{R}$ : elle devient INJECTIVE, car si $a$ et $b$ sont positifs et $a^{2} = b^{2}$ alors $a = b$, le candidat $-b$ ayant été éliminé par le départ ; elle reste non surjective, l'arrivée n'ayant pas bougé et $-1$ n'étant toujours pas atteint.

c) De $\mathbb{R}$ dans $\mathbb{R}^{+}$ : elle devient SURJECTIVE, car tout $y \ge 0$ possède l'antécédent $\sqrt{y}$, et même deux dès que $y > 0$ ; elle reste non injective, le départ n'ayant pas bougé et $-2$ et $2$ ayant toujours la même image. De $\mathbb{R}^{+}$ dans $\mathbb{R}^{+}$ : les deux corrections se cumulent, la fonction est BIJECTIVE, et sa réciproque est la racine carrée. On a donc obtenu les quatre natures possibles avec UNE SEULE règle de calcul, sans jamais écrire un signe différent.

d) De $\mathbb{Z}$ dans $\mathbb{N}$ : ni l'une ni l'autre. Pas injective, car $(-3)^{2} = 3^{2} = 9$. Pas surjective non plus, et c'est le piège de la question : l'arrivée $\mathbb{N}$ a l'air taillée sur mesure, puisque les carrés d'entiers sont bien des entiers naturels, mais 2, 3, 5, 6 et 7 ne sont les carrés d'aucun entier. Sur les 26 entiers de 0 à 25, seuls 6 sont des carrés parfaits et 20 ne le sont pas. L'ensemble image est l'ensemble des carrés parfaits, partie très mince de $\mathbb{N}$. Retenez que rétrécir l'arrivée ne suffit pas : il faut la rétrécir JUSQU'À l'image exacte.

e) On n'a modifié que le départ et l'arrivée. La règle $x \mapsto x^{2}$ n'a pas bougé. La consigne de lecture qui en découle est le fil de toute la série : REGARDER LE DÉPART ET L'ARRIVÉE AVANT DE RÉPONDRE. Un énoncé qui demande si le carré est injectif sans préciser les deux ensembles n'est pas une question difficile, c'est une question mal posée. Le mécanisme précis vaut la peine d'être mémorisé : rétrécir le DÉPART ne peut qu'aider l'injectivité et ne rend jamais surjectif ; rétrécir l'ARRIVÉE ne peut qu'aider la surjectivité et ne change jamais l'injectivité.

a) Soient $a$ et $b$ deux réels tels que $f(a) = f(b)$. Alors $3a - 7 = 3b - 7$, donc $3a = 3b$ en ajoutant 7 aux deux membres, donc $a = b$ en divisant par 3, ce qui est licite puisque $3 \ne 0$. Deux éléments de même image sont donc égaux : $f$ est injective. La rédaction commence par SOIENT et se termine par la conclusion demandée, en une chaîne d'implications, sans un seul exemple numérique. Un étudiant qui vérifie sur trois valeurs ne démontre rien, il teste, et cela vaut zéro sur la question.

b) Soit $y$ un réel quelconque. On cherche $x$ tel que $3x - 7 = y$, soit $3x = y + 7$, soit $x = \frac{y+7}{3}$. Ce nombre est bien un réel, quel que soit $y$, puisque la division par 3 est toujours possible. Vérification obligatoire : $f\left(\frac{y+7}{3}\right) = 3 \cdot \frac{y+7}{3} - 7 = y + 7 - 7 = y$. Donc tout réel a un antécédent et $f$ est surjective. Sur $y = 5$ : $x = \frac{12}{3} = 4$, et $f(4) = 12 - 7 = 5$. La fonction est donc bijective, ce qui était prévisible : une fonction affine de coefficient directeur non nul, de $\mathbb{R}$ dans $\mathbb{R}$, l'est toujours.

c) $g(0) = 1$ et $g(4) = 16 - 16 + 1 = 1$. Donc $g(0) = g(4)$ avec $0 \ne 4$ : $g$ n'est pas injective. Un seul contre-exemple suffit, parce que l'injectivité affirme quelque chose pour TOUS les couples, et que la négation d'un énoncé universel est l'existence d'UN cas fautif. On trouve ce couple sans tâtonner, en remarquant que le trinôme a son sommet en $x = 2$ et que deux points symétriques par rapport à cet axe ont la même image ; $0$ et $4$ sont à distance 2 de part et d'autre. Écrire seulement que le trinôme n'est pas monotone ne réfute rien : il faut produire les deux valeurs et leur image commune.

d) De $\mathbb{Z}$ dans $\mathbb{Z}$ : injective, car $2a = 2b$ donne $a = b$ ; pas surjective, car 3 est impair et aucun entier $n$ ne vérifie $2n = 3$. De $\mathbb{Z}$ dans $2\mathbb{Z}$ : la règle et le départ sont inchangés, donc l'injectivité reste acquise sans rien redémontrer, et la surjectivité devient vraie puisque tout entier pair s'écrit $2k$ avec $k$ entier, ce $k$ étant l'antécédent cherché. La fonction est donc BIJECTIVE de $\mathbb{Z}$ sur $2\mathbb{Z}$. C'est le fil de l'exercice 3 appliqué une fois de plus, et cette bijection reviendra à l'exercice 10, où elle dira quelque chose de surprenant sur les cardinaux infinis.

e) L'injectivité est une propriété UNIVERSELLE : pour tous $a$ et $b$, si $f(a) = f(b)$ alors $a = b$. La surjectivité est une EXISTENCE : pour tout $y$, il EXISTE $x$ tel que $f(x) = y$, et la rédaction doit produire ce $x$, pas seulement affirmer qu'il existe. La réfutation est le seul des trois gestes qui se contente d'un exemple, et c'est parce qu'elle nie un énoncé universel. Le tableau à retenir tient en trois lignes : pour ÉTABLIR un énoncé universel il faut une preuve générale ; pour le DÉTRUIRE il suffit d'un exemple ; pour ÉTABLIR une existence, un exemple suffit au contraire, ici l'antécédent fabriqué en b).

a) $f(1) = a$ puis $g(a) = x$, donc $(g \circ f)(1) = x$. De même $(g \circ f)(2) = g(b) = y$ et $(g \circ f)(3) = g(c) = z$. Les trois images sont distinctes, donc $g \circ f$ est injective, et elles épuisent $C = \{x,y,z\}$, donc elle est surjective : $g \circ f$ est BIJECTIVE. Le calcul se fait toujours dans cet ordre, en suivant les flèches ; écrire $(f \circ g)(1)$ n'aurait ici aucun sens, $g$ ne partant pas de $A$.

b) $f$ n'est PAS surjective : $d$ ne reçoit aucune flèche venant de $A$. $g$ n'est PAS injective : $b$ et $d$ ont la même image $y$. Et pourtant la composée est bijective. L'idée que la composée hérite des défauts est donc fausse, et cette figure en est le contre-exemple complet : une fonction qui n'atteint pas tout, suivie d'une fonction qui confond deux éléments, peut donner une bijection, parce que la confusion de $g$ porte précisément sur l'élément $d$ que $f$ n'atteignait pas. Ce qui se transmet, ce sont les QUALITÉS, et encore pas dans les deux sens, comme le montrent les questions d) et e).

c) INJECTIVITÉ. Soient $a_1$ et $a_2$ dans $A$ avec $(g \circ f)(a_1) = (g \circ f)(a_2)$, c'est-à-dire $g(f(a_1)) = g(f(a_2))$. Comme $g$ est injective, $f(a_1) = f(a_2)$. Comme $f$ est injective, $a_1 = a_2$. Donc $g \circ f$ est injective. SURJECTIVITÉ. Soit $c$ dans $C$. Comme $g$ est surjective, il existe $b$ dans $B$ avec $g(b) = c$. Comme $f$ est surjective, il existe $a$ dans $A$ avec $f(a) = b$. Alors $(g \circ f)(a) = g(b) = c$. Donc $g \circ f$ est surjective. Remarquez la différence de mouvement : la preuve d'injectivité DÉPILE, elle part d'une égalité et retire les fonctions une à une ; la preuve de surjectivité CONSTRUIT, elle part de l'arrivée et remonte jusqu'au départ. Mélanger les deux mouvements produit une rédaction qui ne démontre rien.

d) Supposons $g \circ f$ injective et soient $a_1, a_2$ avec $f(a_1) = f(a_2)$. En appliquant $g$ aux deux membres, $g(f(a_1)) = g(f(a_2))$, donc $(g \circ f)(a_1) = (g \circ f)(a_2)$, donc $a_1 = a_2$ par injectivité de la composée. Donc $f$ est injective. La figure montre bien que $g$ peut échouer : $g \circ f$ y est injective et pourtant $g(b) = g(d) = y$. La raison tient en une phrase : la composée ne voit de $g$ que sa restriction à $f(A) = \{a,b,c\}$, et $d$ lui est invisible. Retenez la dissymétrie : d'une composée injective, seule la PREMIÈRE fonction hérite.

e) Supposons $g \circ f$ surjective et soit $c$ dans $C$. Il existe $a$ dans $A$ avec $g(f(a)) = c$. Alors l'élément $b = f(a)$ de $B$ vérifie $g(b) = c$, donc $c$ a un antécédent par $g$ : $g$ est surjective. La figure le confirme et montre que $f$, elle, peut échouer : $g \circ f$ y est surjective alors que $f$ rate $d$. C'est la dissymétrie symétrique de la précédente : d'une composée surjective, seule la SECONDE fonction hérite. Les deux résultats se résument d'une phrase, et c'est la forme à mémoriser : l'injectivité remonte vers l'entrée, la surjectivité descend vers la sortie.

a) La table donne $c(A)=C$, $c(B)=E$, $c(C)=A$, $c(D)=B$, $c(E)=D$. Les cinq images sont $C$, $E$, $A$, $B$ et $D$ : elles sont deux à deux distinctes, donc $c$ est injective, et elles épuisent $\Sigma$, donc $c$ est surjective. C'est une bijection. Comme départ et arrivée ont ici le même cardinal fini, une seule des deux vérifications aurait suffi, résultat démontré à l'exercice 7. Il existe $5^{5} = 3\,125$ fonctions de $\Sigma$ dans $\Sigma$, dont $5! = 120$ bijections, soit $3{,}84$ pour cent. Autrement dit, plus de 96 fonctions sur 100 sont inutilisables comme chiffrement, et il ne suffit donc pas de tirer une table au hasard.

b) On renverse chaque flèche. $c(C)=A$ donne $c^{-1}(A)=C$ ; $c(D)=B$ donne $c^{-1}(B)=D$ ; $c(A)=C$ donne $c^{-1}(C)=A$ ; $c(E)=D$ donne $c^{-1}(D)=E$ ; $c(B)=E$ donne $c^{-1}(E)=B$. Le déchiffrement de EDBCA se fait lettre par lettre : $E \to B$, $D \to E$, $B \to D$, $C \to A$, $A \to C$, soit BEDAC. Vérification dans l'autre sens : $c$ appliquée à BEDAC redonne bien $E$, $D$, $B$, $C$, $A$. Le piège est de lire la table dans le mauvais sens, ce qui donne un texte sans aucun sens sans qu'aucune erreur de calcul soit visible : le contrôle par rechiffrement est donc obligatoire.

c) $c(B) = E$ et $c^{-1}(E) = B$ : la première égalité est vérifiée. $c^{-1}(B) = D$ et $c(D) = B$ : la seconde aussi. On exige les deux parce qu'elles ne disent pas la même chose. L'égalité $c^{-1} \circ c = \mathrm{id}_{\Sigma}$ dit qu'on retrouve toujours le message de DÉPART, ce qui correspond à l'injectivité de $c$ ; l'égalité $c \circ c^{-1} = \mathrm{id}_{\Sigma}$ dit que toute lettre chiffrée possible provient bien d'une lettre claire, ce qui correspond à la surjectivité. Une fonction qui ne vérifie qu'une des deux possède seulement un inverse à gauche ou un inverse à droite, jamais une réciproque, et sur un ensemble infini les deux situations existent vraiment, comme l'exercice 10 le montrera.

d) On applique $c$ puis $d$ : $A \to C \to D$, $B \to E \to A$, $C \to A \to B$, $D \to B \to C$, $E \to D \to E$. La table de $d \circ c$ est donc $A \to D$, $B \to A$, $C \to B$, $D \to C$, $E \to E$, et ses cinq images sont distinctes : c'est une bijection, comme le garantissait le résultat de l'exercice 5 sur la composée de deux bijections. Sa réciproque est $(d \circ c)^{-1} = c^{-1} \circ d^{-1}$, et l'ordre s'inverse : pour défaire deux opérations enchaînées, on défait d'abord la DERNIÈRE faite. Écrire $d^{-1} \circ c^{-1}$ est l'erreur classique, et elle se détecte tout de suite : cette composée ne part même pas du bon ensemble dans le cas général où les trois ensembles diffèrent.

e) La fonction $e$ n'est pas injective : $A$ et $B$ ont la même image $A$, $C$ et $D$ ont la même image $C$. Pour obtenir AAAAA, chacune des cinq positions doit contenir une lettre d'image $A$, donc $A$ ou $B$ : cela fait $2^{5} = 32$ messages clairs différents qui donnent le même chiffré. Le déchiffrement est donc impossible, non par manque d'astuce mais par principe : $e$ n'étant pas injective n'a pas de réciproque, et le destinataire devant choisir entre 32 messages n'a aucun moyen de trancher. C'est exactement l'argument que le chapitre des techniques de démonstration emploie contre le compresseur sans perte universel, et c'est ici la même propriété, lue sur la fonction plutôt que sur un comptage.

a) FONCTIONS : chaque élément de $A$ choisit librement son image parmi les 5 de $B$, indépendamment des autres, donc $5^{3} = 125$ par le principe multiplicatif. INJECTIONS : les images doivent être deux à deux distinctes, donc le premier élément a 5 choix, le deuxième 4, le troisième 3, soit $5 \times 4 \times 3 = 60$. On reconnaît l'arrangement $\frac{5!}{2!} = 60$ de la série de dénombrement : compter les injections de $A$ dans $B$, c'est exactement compter les mots de 3 lettres distinctes sur un alphabet de 5. BIJECTIONS : aucune, soit 0, puisqu'une bijection exigerait $3 = 5$. La formule générale à retenir : $\lvert B \rvert^{\lvert A \rvert}$ fonctions et $\frac{\lvert B \rvert!}{(\lvert B \rvert - \lvert A \rvert)!}$ injections.