03 · Applications : injection, surjection, bijection¶
Intuition
Trois questions, trois mots.
- Injective : deux entrées différentes donnent-elles toujours des sorties différentes ? Rien n'est écrasé.
- Surjective : toute sortie possible est-elle effectivement atteinte ? Rien n'est oublié.
- Bijective : les deux à la fois. Chaque sortie est atteinte exactement une fois — on peut faire le chemin inverse.
L'image la plus fidèle est celle d'un vestiaire. Chaque manteau reçoit un numéro. Injectif = deux manteaux n'ont jamais le même numéro. Surjectif = aucun numéro n'est inutilisé. Bijectif = on peut retrouver le manteau à partir du numéro, et le numéro à partir du manteau.
1. Application, image, antécédent¶
Une application \(f\) de \(E\) dans \(F\) associe à chaque élément de \(E\) un et un seul élément de \(F\).
- \(E\) est l'ensemble de départ, \(F\) l'ensemble d'arrivée ;
- \(f(x)\) est l'image de \(x\) ;
- si \(y = f(x)\), alors \(x\) est un antécédent de \(y\).
Ensemble d'arrivée ≠ ensemble des images
L'ensemble d'arrivée \(F\) est déclaré ; l'image de \(f\), notée \(f(E) = \{f(x) \mid x\in E\}\), est ce qui est effectivement atteint. On a toujours \(f(E)\subset F\), mais pas forcément l'égalité.
Pour \(f:\mathbb{R}\to\mathbb{R},\ x\mapsto x^2\) : l'arrivée est \(\mathbb{R}\), l'image est \(\mathbb{R}^+\).
Changer l'ensemble d'arrivée change la surjectivité sans changer la formule. C'est le point que les étudiants ratent le plus souvent.
1.1 Image directe et image réciproque¶
La notation \(f^{-1}(B)\) ne suppose pas que \(f\) soit bijective
\(f^{-1}(B)\) est l'image réciproque d'une partie : c'est l'ensemble des antécédents des éléments de \(B\). Cette notation a un sens pour n'importe quelle application.
Elle est à distinguer de \(f^{-1}\) l'application réciproque, qui n'existe que si \(f\) est bijective. Le contexte tranche : \(f^{-1}(\{3\})\) est un ensemble, \(f^{-1}(3)\) un élément — et le second n'a de sens que pour une bijection.
2. Injectivité¶
Définition
\(f : E\to F\) est injective si
ou, de façon équivalente (contraposée),
Autrement dit : tout élément de \(F\) a au plus un antécédent.
Comment le démontrer
On part de \(f(x_1) = f(x_2)\), on calcule, et on aboutit à \(x_1 = x_2\). C'est le seul schéma, et il ne varie pas.
Comment le réfuter : exhiber deux éléments distincts de même image. Un seul contre-exemple suffit.
Exemples.
| Application | Injective ? | Justification |
|---|---|---|
| \(\mathbb{R}\to\mathbb{R},\ x\mapsto 3x+1\) | Oui | \(3x_1+1 = 3x_2+1 \implies x_1=x_2\) |
| \(\mathbb{R}\to\mathbb{R},\ x\mapsto x^2\) | Non | \(f(-2) = f(2) = 4\) |
| \(\mathbb{R}^+\to\mathbb{R},\ x\mapsto x^2\) | Oui | Sur les positifs, \(x_1^2=x_2^2 \implies x_1=x_2\) |
| \(\mathbb{R}\to\mathbb{R},\ x\mapsto x^3\) | Oui | La fonction cube est strictement croissante |
Critère utile
Une fonction strictement monotone sur un intervalle y est injective. La réciproque est fausse en général, mais vraie pour les fonctions continues — résultat qu'on démontrera au chapitre Analyse 02.
3. Surjectivité¶
Définition
\(f : E\to F\) est surjective si
Autrement dit : tout élément de \(F\) a au moins un antécédent, soit \(f(E) = F\).
Comment le démontrer
On prend \(y\in F\) quelconque, et on construit explicitement un \(x\) tel que \(f(x)=y\) — généralement en résolvant l'équation \(f(x)=y\) d'inconnue \(x\).
Comment le réfuter : exhiber un \(y\in F\) sans antécédent.
Exemples.
| Application | Surjective ? | Justification |
|---|---|---|
| \(\mathbb{R}\to\mathbb{R},\ x\mapsto 3x+1\) | Oui | \(x = \frac{y-1}{3}\) convient |
| \(\mathbb{R}\to\mathbb{R},\ x\mapsto x^2\) | Non | \(y=-1\) n'a pas d'antécédent |
| \(\mathbb{R}\to\mathbb{R}^+,\ x\mapsto x^2\) | Oui | \(x=\sqrt y\) convient |
| \(\mathbb{N}\to\mathbb{N},\ n\mapsto n+1\) | Non | \(0\) n'a pas d'antécédent |
4. Bijectivité¶
Définition
\(f\) est bijective si elle est injective et surjective, c'est-à-dire
(« il existe un unique \(x\) »).
4.1 Application réciproque¶
Si \(f : E\to F\) est bijective, on définit \(f^{-1} : F\to E\) par
Elle vérifie
où \(\operatorname{id}\) est l'application identité, \(x\mapsto x\).
Critère pratique de bijectivité
S'il existe \(g : F\to E\) telle que \(g\circ f = \operatorname{id}_E\) et \(f\circ g = \operatorname{id}_F\), alors \(f\) est bijective et \(g = f^{-1}\).
En pratique, c'est souvent le moyen le plus rapide : on devine la réciproque et on vérifie les deux compositions, plutôt que de prouver séparément injectivité et surjectivité.
4.2 Méthode de référence¶
Pour montrer que \(f\) est bijective et trouver \(f^{-1}\), on résout l'équation \(f(x) = y\) d'inconnue \(x\).
- Si elle admet une solution unique pour chaque \(y\) : \(f\) est bijective, et l'expression trouvée est \(f^{-1}(y)\).
- Si elle admet parfois plusieurs solutions : non injective.
- Si elle n'en admet parfois aucune : non surjective.
Exemple. \(f:\mathbb{R}\setminus\{2\}\to\mathbb{R}\setminus\{1\}\), \(f(x) = \frac{x+3}{x-2}\).
Pour tout \(y \neq 1\), il existe un unique \(x\) (et \(x\neq2\) car \(\frac{2y+3}{y-1} = 2\) donnerait \(2y+3 = 2y-2\), impossible). Donc \(f\) est bijective, et
5. Composition¶
Propriétés de transmission
| Si… | alors \(g\circ f\) est… |
|---|---|
| \(f\) et \(g\) injectives | injective |
| \(f\) et \(g\) surjectives | surjective |
| \(f\) et \(g\) bijectives | bijective, et \((g\circ f)^{-1} = f^{-1}\circ g^{-1}\) |
L'ordre s'inverse dans la réciproque
\((g\circ f)^{-1} = f^{-1}\circ g^{-1}\), pas \(g^{-1}\circ f^{-1}\).
Image concrète : pour défaire « mettre les chaussettes puis les chaussures », il faut « enlever les chaussures puis les chaussettes ». On défait dans l'ordre inverse.
On retrouvera exactement cette règle pour l'inverse d'un produit de matrices au chapitre 08 : \((\mathbf{AB})^{-1} = \mathbf{B}^{-1}\mathbf{A}^{-1}\).
Résultats partiels utiles (démontrés en exercice) :
- si \(g\circ f\) est injective, alors \(f\) est injective ;
- si \(g\circ f\) est surjective, alors \(g\) est surjective.
6. Cardinaux et applications entre ensembles finis¶
C'est le pont vers la combinatoire.
Théorème
Soient \(E\) et \(F\) finis, \(|E| = n\), \(|F| = p\).
- S'il existe une injection \(E\to F\), alors \(n \leqslant p\).
- S'il existe une surjection \(E\to F\), alors \(n \geqslant p\).
- S'il existe une bijection \(E\to F\), alors \(n = p\).
Contraposée de la première : si \(n > p\), aucune application \(E\to F\) n'est injective. C'est le principe des tiroirs : ranger \(n\) objets dans \(p < n\) tiroirs force au moins un tiroir à contenir deux objets.
Théorème (cas \(|E| = |F|\) fini)
Si \(E\) et \(F\) sont finis de même cardinal, alors pour \(f:E\to F\) :
Ce théorème est FAUX en dimension infinie
\(f:\mathbb{N}\to\mathbb{N},\ n\mapsto n+1\) est injective mais pas surjective (\(0\) n'a pas d'antécédent), et pourtant départ et arrivée ont « le même nombre » d'éléments.
C'est la propriété qui définit les ensembles infinis, et c'est le paradoxe de l'hôtel de Hilbert : un hôtel plein à infinité de chambres peut accueillir un client de plus en décalant tout le monde d'une chambre.
Exemples traités¶
Exemple 1 — Étude complète
Étudier \(f : \mathbb{R}\to\mathbb{R},\ x\mapsto x^2-4x+3\).
Injectivité. \(f(x_1)=f(x_2)\) donne \(x_1^2-4x_1 = x_2^2-4x_2\), soit \((x_1-x_2)(x_1+x_2) = 4(x_1-x_2)\), soit \((x_1-x_2)(x_1+x_2-4) = 0\).
Donc \(x_1 = x_2\) ou \(x_1+x_2 = 4\). La seconde possibilité donne des contre-exemples : \(f(0) = 3 = f(4)\). Non injective.
Surjectivité. Forme canonique : \(f(x) = (x-2)^2 - 1 \geqslant -1\). La valeur \(y = -2\) n'a donc pas d'antécédent. Non surjective.
Restriction. Sur \([2;+\infty[ \to [-1;+\infty[\), l'application devient bijective, de réciproque \(y \mapsto 2+\sqrt{y+1}\).
La leçon
Une même formule change de statut selon le départ et l'arrivée. Une question « \(f\) est-elle bijective ? » sans préciser les ensembles n'a pas de réponse.
Exemple 2 — Suites et injectivité
Soit \(f:\mathbb{N}\to\mathbb{N}\) définie par \(f(n) = 2n\).
Injective : \(2n_1 = 2n_2 \implies n_1 = n_2\) ✓
Non surjective : \(3\) n'a pas d'antécédent (il faudrait \(n = 1{,}5\)).
En revanche, \(f:\mathbb{N}\to 2\mathbb{N}\) (les entiers pairs) est bijective. On en déduit que \(\mathbb{N}\) et l'ensemble des entiers pairs ont le même cardinal infini — bien que le second soit une partie stricte du premier.
Exemple 3 — Composition
Soient \(f(x) = 2x+1\) et \(g(x) = x^2\), de \(\mathbb{R}\) dans \(\mathbb{R}\).
- \(g\circ f (x) = (2x+1)^2\) : non injective (\(x=0\) et \(x=-1\) donnent 1).
- \(f\circ g(x) = 2x^2+1\) : non injective non plus, et non surjective (image \(= [1;+\infty[\)).
Pourtant \(f\) est bijective. Cela illustre qu'une composée peut perdre les propriétés d'un de ses facteurs : ici c'est \(g\) qui les détruit.
Exemple 4 — Le principe des tiroirs
Montrer que parmi 13 personnes, deux sont nées le même mois.
Considérons \(f:\{\text{les }13\text{ personnes}\}\to\{\text{les }12\text{ mois}\}\) associant à chacun son mois de naissance.
Comme \(13 > 12\), \(f\) ne peut pas être injective. Il existe donc deux personnes distinctes ayant la même image, c'est-à-dire le même mois de naissance. \(\blacksquare\)
Remarque. La preuve ne dit pas lesquelles. C'est une preuve d'existence non constructive — distinction importante, notamment quand on programme.
Erreurs fréquentes¶
| Erreur | Correction |
|---|---|
| « \(x\mapsto x^2\) n'est pas injective » sans préciser le départ | Sur \(\mathbb{R}^+\) elle l'est |
| Confondre \(f^{-1}(B)\) et \(f^{-1}\) | La première existe toujours |
| \((g\circ f)^{-1} = g^{-1}\circ f^{-1}\) | L'ordre s'inverse |
| « injective = surjective » en général | Vrai seulement si \(\lvert E\rvert=\lvert F\rvert\) fini |
| Prouver la surjectivité sans construire l'antécédent | Il faut exhiber \(x\) |
Exercices¶
★ Exercice 1. Pour chacune, dire si elle est injective, surjective, bijective — en justifiant.
a) \(f:\mathbb{R}\to\mathbb{R},\ x\mapsto 5x-2\) b) \(g:\mathbb{R}\to\mathbb{R},\ x\mapsto x^3\) c) \(h:\mathbb{Z}\to\mathbb{Z},\ n\mapsto 2n\) d) \(k:\mathbb{R}\to\mathbb{R},\ x\mapsto \lvert x\rvert\)
★ Exercice 2. Soit \(f:\mathbb{R}\to\mathbb{R},\ x\mapsto 4x+7\). Montrer qu'elle est bijective et déterminer \(f^{-1}\).
★★ Exercice 3. Soit \(f:\mathbb{R}\setminus\{3\}\to\mathbb{R}\setminus\{2\}\) définie par \(f(x) = \dfrac{2x+1}{x-3}\).
a) Vérifier que \(f\) est bien définie et à valeurs dans l'arrivée annoncée. b) Montrer que \(f\) est bijective et calculer \(f^{-1}\).
★★ Exercice 4. Soit \(f:\mathbb{N}\to\mathbb{N}\) définie par
\(f\) est-elle injective ? surjective ?
★★ Exercice 5. Soit \(E\) un ensemble et \(A\subset E\) fixé. On définit \(\varphi : \mathcal{P}(E)\to\mathcal{P}(E)\) par \(\varphi(X) = X\Delta A\).
Montrer que \(\varphi\) est bijective et déterminer sa réciproque.
★★★ Exercice 6. Soient \(f:E\to F\) et \(g:F\to G\).
a) Montrer que si \(g\circ f\) est injective, alors \(f\) est injective. b) Montrer que si \(g\circ f\) est surjective, alors \(g\) est surjective. c) Donner un exemple où \(g\circ f\) est bijective sans que \(f\) ni \(g\) ne le soient.
★★★ Exercice 7. Soit \(f : E\to F\) et \(A, B \subset E\).
a) Montrer que \(f(A\cup B) = f(A)\cup f(B)\). b) Montrer que \(f(A\cap B)\subset f(A)\cap f(B)\). c) Donner un contre-exemple montrant que l'inclusion de b) peut être stricte. d) Montrer que l'égalité en b) a lieu pour toutes parties \(A,B\) si et seulement si \(f\) est injective.
★★★ Exercice 8. Construire explicitement une bijection entre :
a) \(\mathbb{N}\) et \(\mathbb{Z}\) b) \([0;1]\) et \([a;b]\) avec \(a<b\) c) \(\mathbb{N}\times\mathbb{N}\) et \(\mathbb{N}\)
Pour c), utilisez le parcours en diagonale — c'est la fonction de couplage de Cantor.
★★★★ Exercice 9. Montrer que parmi \(n+1\) entiers choisis dans \(\{1,2,\dots,2n\}\), il en existe toujours deux dont l'un divise l'autre.
Indication : à chaque entier \(m\), associez le plus grand diviseur impair de \(m\). Combien de valeurs cette quantité peut-elle prendre ?
★★★★ Exercice 10 — lien informatique. Une fonction de hachage \(h : \mathcal{C}\to\{0,\dots,m-1\}\) envoie un ensemble de clés \(\mathcal{C}\) vers \(m\) empreintes.
a) Traduire « \(h\) est sans collision sur \(\mathcal{C}\) » en termes d'injectivité. b) Une fonction de hachage parfaite pour \(\mathcal{C}\) est une \(h\) injective sur \(\mathcal{C}\). Montrer qu'elle ne peut exister que si \(\lvert\mathcal{C}\rvert \leqslant m\). c) Une fonction de hachage cryptographique doit être « résistante à la préimage » : étant donné \(y\), il doit être difficile de trouver \(x\) tel que \(h(x)=y\). Cette propriété est-elle contradictoire avec la surjectivité ? Expliquer la différence entre « exister » et « être calculable ». d) SHA-256 produit 256 bits à partir d'entrées de taille arbitraire. Combien d'antécédents une empreinte donnée admet-elle « en moyenne » si l'on se restreint aux entrées de 512 bits ?
Corrigés¶
Corrigé — Exercice 1
a) Injective : \(5x_1-2 = 5x_2-2 \implies x_1 = x_2\) ✓ Surjective : pour \(y\) donné, \(x = \frac{y+2}{5}\) convient ✓ Bijective.
b) \(x\mapsto x^3\) est strictement croissante sur \(\mathbb{R}\) donc injective ; et tout réel admet une racine cubique réelle, donc surjective. Bijective, de réciproque \(y\mapsto \sqrt[3]{y}\).
c) Injective : \(2n_1 = 2n_2\implies n_1=n_2\) ✓ Non surjective : \(1\) n'a pas d'antécédent dans \(\mathbb{Z}\).
d) Ni l'une ni l'autre. Non injective : \(k(-1)=k(1)=1\). Non surjective : \(-1\) n'a pas d'antécédent.
Corrigé — Exercice 2
Résolvons \(4x+7 = y\) : \(x = \dfrac{y-7}{4}\).
Pour chaque \(y\in\mathbb{R}\), il existe un unique \(x\). Donc \(f\) est bijective et
Vérification. \(f^{-1}(f(x)) = \frac{4x+7-7}{4} = x\) ✓ et \(f(f^{-1}(y)) = 4\cdot\frac{y-7}{4}+7 = y\) ✓
Corrigé — Exercice 3
a) \(f\) est définie pour \(x \neq 3\) ✓. Montrons que \(f(x) \neq 2\) :
impossible. Donc \(f(x)\neq2\) pour tout \(x\) du domaine ✓
b) Résolvons \(y = \dfrac{2x+1}{x-3}\) :
Pour \(y\neq2\), cette expression est définie et donne un unique \(x\). Reste à vérifier \(x\neq3\) :
impossible ✓
Donc \(f\) est bijective et \(f^{-1}(y) = \dfrac{3y+1}{y-2}\).
Remarque
\(f\) et \(f^{-1}\) ont la même forme, avec les rôles de 2 et 3 échangés. Ce n'est pas un accident : les homographies \(x\mapsto\frac{ax+b}{cx+d}\) forment un groupe isomorphe aux matrices \(2\times2\) inversibles modulo les scalaires, et l'inverse de \(\begin{pmatrix}2&1\\1&-3\end{pmatrix}\) est proportionnelle à \(\begin{pmatrix}-3&-1\\-1&2\end{pmatrix}\) — d'où l'échange.
Corrigé — Exercice 4
Non injective. \(f(2) = 1\) et \(f(1) = 2\)… essayons mieux : \(f(4) = 2\) et \(f(1) = 2\). Deux antécédents pour 2. ✗
Surjective ? Soit \(y\in\mathbb{N}\). L'entier \(2y\) est pair et \(f(2y) = y\) ✓ Donc surjective.
Ce que cela illustre
\(f\) est surjective sans être injective, sur un ensemble infini. Sur un ensemble fini de même cardinal au départ et à l'arrivée, ce serait impossible.
Corrigé — Exercice 5
Montrons que \(\varphi\circ\varphi = \operatorname{id}\).
en utilisant l'associativité de \(\Delta\) (démontrée à l'exercice 6 du chapitre 02) et le fait que \(A\Delta A = \varnothing\).
Donc \(\varphi\) est sa propre réciproque : \(\varphi^{-1} = \varphi\). En particulier elle est bijective. \(\blacksquare\)
Une application vérifiant \(\varphi\circ\varphi = \operatorname{id}\) s'appelle
une involution. En bits, \(\varphi\) est simplement x ^ a : appliquer
deux fois le même XOR restitue la valeur d'origine — c'est le principe du
chiffrement de Vernam.
Corrigé — Exercice 6
a) Soient \(x_1, x_2\in E\) tels que \(f(x_1) = f(x_2)\). En appliquant \(g\) : \(g(f(x_1)) = g(f(x_2))\), c'est-à-dire \((g\circ f)(x_1) = (g\circ f)(x_2)\). Comme \(g\circ f\) est injective, \(x_1 = x_2\). Donc \(f\) est injective. \(\blacksquare\)
b) Soit \(z\in G\). Comme \(g\circ f\) est surjective, il existe \(x\in E\) tel que \(g(f(x)) = z\). Posons \(y = f(x) \in F\) : alors \(g(y) = z\). Donc \(g\) est surjective. \(\blacksquare\)
c) Prenons \(E = \{1\}\), \(F = \{a,b\}\), \(G = \{\alpha\}\).
- \(f : 1\mapsto a\) — injective mais non surjective (\(b\) n'est pas atteint) ;
- \(g : a\mapsto\alpha,\ b\mapsto\alpha\) — surjective mais non injective ;
- \(g\circ f : 1\mapsto\alpha\) — bijective (\(E\) et \(G\) ont un élément).
La règle générale
La composée « hérite » de l'injectivité du premier et de la surjectivité du second. Réciproquement, \(g\circ f\) injective n'informe que sur \(f\), et surjective que sur \(g\).
Corrigé — Exercice 7
a) \(\subset\). Soit \(y\in f(A\cup B)\) : il existe \(x\in A\cup B\) avec \(y=f(x)\). Si \(x\in A\), alors \(y\in f(A)\) ; si \(x\in B\), alors \(y\in f(B)\). Dans les deux cas \(y\in f(A)\cup f(B)\).
\(\supset\). Si \(y\in f(A)\), il existe \(x\in A\subset A\cup B\) avec \(f(x)=y\), donc \(y\in f(A\cup B)\). Idem pour \(f(B)\). \(\blacksquare\)
b) Soit \(y\in f(A\cap B)\) : il existe \(x\in A\cap B\) avec \(f(x)=y\). Comme \(x\in A\), \(y\in f(A)\) ; comme \(x\in B\), \(y\in f(B)\). Donc \(y\in f(A)\cap f(B)\). \(\blacksquare\)
c) \(f:\mathbb{R}\to\mathbb{R},\ x\mapsto x^2\), \(A = \{-1\}\), \(B=\{1\}\).
\(A\cap B = \varnothing\), donc \(f(A\cap B) = \varnothing\). Mais \(f(A) = f(B) = \{1\}\), donc \(f(A)\cap f(B) = \{1\}\).
L'inclusion est stricte.
d) Sens \(\impliedby\). Supposons \(f\) injective et soit \(y\in f(A)\cap f(B)\). Il existe \(a\in A\) et \(b\in B\) avec \(f(a)=f(b)=y\). Par injectivité \(a = b\), donc cet élément est dans \(A\cap B\), donc \(y\in f(A\cap B)\).
Sens \(\implies\). Par contraposée. Supposons \(f\) non injective : il existe \(x_1\neq x_2\) avec \(f(x_1)=f(x_2)=y\). Prenons \(A = \{x_1\}\), \(B=\{x_2\}\). Alors \(f(A\cap B) = f(\varnothing) = \varnothing\), tandis que \(f(A)\cap f(B) = \{y\} \neq\varnothing\). L'égalité échoue. \(\blacksquare\)
À retenir
L'image directe « respecte » la réunion mais pas l'intersection. L'image réciproque, elle, respecte tout — réunion, intersection et complémentaire. C'est pourquoi on préfère travailler avec \(f^{-1}\) en topologie et en théorie de la mesure, et pourquoi la définition d'une variable aléatoire s'écrit avec des images réciproques.
Corrigé — Exercice 8
a) \(\mathbb{N}\to\mathbb{Z}\). On alterne :
Les images sont \(0, -1, 1, -2, 2, -3, 3,\dots\) pour \(n = 0,1,2,3,4,5,6,\dots\)
Injective : les pairs donnent les positifs, les impairs les strictement négatifs — les deux familles sont disjointes, et chacune est injective. Surjective : \(k \geqslant 0\) est atteint par \(n=2k\) ; \(k<0\) par \(n = -2k-1\). ✓
b) \([0;1]\to[a;b]\). L'application affine
est bijective, de réciproque \(\psi^{-1}(x) = \dfrac{x-a}{b-a}\).
Vérification : \(\psi(0)=a\), \(\psi(1)=b\), et \(\psi\) est strictement croissante puisque \(b-a>0\) ✓
c) \(\mathbb{N}\times\mathbb{N}\to\mathbb{N}\). Fonction de couplage de Cantor :
Principe. On énumère les couples par diagonales : d'abord ceux avec \(m+n=0\), puis \(m+n=1\), etc. Avant la diagonale \(d = m+n\), il y a \(0+1+\dots+d = \frac{d(d+1)}{2}\) couples ; à l'intérieur de la diagonale, on se repère par \(n\).
Premiers termes : \(\pi(0,0)=0\), \(\pi(1,0)=1\), \(\pi(0,1)=2\), \(\pi(2,0)=3\), \(\pi(1,1)=4\), \(\pi(0,2)=5\)… tous les entiers sont atteints exactement une fois.
Conséquence
\(\mathbb{N}\times\mathbb{N}\) a le même cardinal que \(\mathbb{N}\) — on dit que c'est un ensemble dénombrable. Par le même argument, \(\mathbb{Q}\) est dénombrable. En revanche \(\mathbb{R}\) ne l'est pas : c'est le théorème de Cantor, démontré par l'argument diagonal.
Corrigé — Exercice 9
Tout entier \(m \geqslant 1\) s'écrit de façon unique \(m = 2^k \cdot q\) avec \(q\) impair — on extrait toutes les puissances de 2.
Considérons l'application
où \(q(m)\) est le plus grand diviseur impair de \(m\). L'arrivée est bien l'ensemble des impairs de \([\![1;2n]\!]\), qui compte exactement \(n\) éléments.
Comme \(n+1 > n\), \(\varphi\) n'est pas injective (principe des tiroirs) : il existe deux entiers choisis distincts \(m_1 \neq m_2\) avec \(q(m_1) = q(m_2) = q\).
Alors \(m_1 = 2^{k_1}q\) et \(m_2 = 2^{k_2}q\) avec \(k_1 \neq k_2\) (sinon \(m_1 = m_2\)). Si \(k_1 < k_2\), alors
donc \(m_1\) divise \(m_2\). \(\blacksquare\)
Vérification que le résultat est optimal : avec seulement \(n\) entiers, on peut échouer — prenez \(\{n+1, n+2, \dots, 2n\}\). Aucun n'en divise un autre, car le double du plus petit, \(2(n+1)\), dépasse déjà \(2n\).
Corrigé — Exercice 10
a) « Sans collision sur \(\mathcal{C}\) » signifie exactement que \(h\) restreinte à \(\mathcal{C}\) est injective.
b) Une injection de \(\mathcal{C}\) vers un ensemble de cardinal \(m\) impose \(\lvert\mathcal{C}\rvert \leqslant m\) (théorème du cours). C'est le principe des tiroirs : plus de clés que d'empreintes force une collision. \(\blacksquare\)
c) Non, ce n'est pas contradictoire. Ce sont deux affirmations de nature différente :
- la surjectivité est une affirmation d'existence : pour tout \(y\), il existe \(x\) ;
- la résistance à la préimage est une affirmation de complexité algorithmique : trouver ce \(x\) demande, au mieux connu, de l'ordre de \(2^{256}\) opérations.
Une fonction peut parfaitement être surjective — donc chaque empreinte a des antécédents, en quantité astronomique — et néanmoins impossible à inverser en pratique. C'est même le cas idéal recherché.
C'est la distinction entre « existe » et « est calculable en temps raisonnable », qui est le cœur de la théorie de la complexité vue en troisième année dans le module COAL35.
d) L'ensemble des entrées de 512 bits a pour cardinal \(2^{512}\) ; l'ensemble des empreintes a pour cardinal \(2^{256}\). Si les empreintes se répartissent uniformément, chaque empreinte admet en moyenne
antécédents parmi les entrées de 512 bits.
Autrement dit, les collisions ne sont pas seulement possibles : elles sont massivement majoritaires. La sécurité de SHA-256 ne repose donc pas sur leur absence, mais sur l'impossibilité pratique d'en exhiber une.
Chapitre suivant : Combinatoire.