Exercice 24

Fixons $k \in \mathbb{N}$ et notons $I_{k} = [\![0\,;k]\!]$, qui a $k + 1$ éléments.

• Si $g(n) \leqslant k$, alors $f(n) \leqslant g(n) \leqslant k$ : on a $g^{-1}(I_{k}) \subset f^{-1}(I_{k})$.

• L'application $f$ étant injective, elle induit une bijection de $f^{-1}(I_{k})$ sur son image, qui est une partie de $I_{k}$. D'après les lemmes 3 et 2 du cours, cette image est finie avec au plus $k + 1$ éléments, donc $f^{-1}(I_{k})$ aussi.

• La partie $g^{-1}(I_{k})$ de $f^{-1}(I_{k})$ est donc finie. Chacun des entiers $0$, …, $k$ a un antécédent par $g$, par exemple le plus petit, et ces antécédents sont distincts : ils forment une partie de $g^{-1}(I_{k})$ à $k + 1$ éléments, et le lemme 3 donne $\mathrm{card}\big(g^{-1}(I_{k})\big) \geqslant k + 1$.

Ainsi $g^{-1}(I_{k})$ est une partie de $f^{-1}(I_{k})$ qui a au moins autant d'éléments que lui. D'après le cas d'égalité du lemme 3 : $$f^{-1}(I_{k}) = g^{-1}(I_{k}).$$ Soit enfin $n \in \mathbb{N}$ et $k = f(n)$. Alors $n \in f^{-1}(I_{k}) = g^{-1}(I_{k})$, donc $g(n) \leqslant k = f(n)$. Avec l'hypothèse $f(n) \leqslant g(n)$, on conclut. $$\boxed{f = g}$$ Attention : sans l'injectivité de $f$, le résultat tombe. Avec $f$ nulle et $g = \mathrm{id}_{\mathbb{N}}$, on a bien $f \leqslant g$, $g$ surjective, et $f \neq g$.