Exercice :
Soit \( f \text{ une application de } \mathbb{N} \text{ vers } \mathbb{N} \).
On suppose que \( f \) est surjective et vérifie : \( \forall n \in \mathbb{ N}, \quad f(n) \geq n \).
Montrer que \( f=id_{\mathbb{N}} \)
Corrigé :
Montrons par récurrence forte que \(\forall n \in \mathbb{N},\ f(n)=n\).
Initialisation :
Pour \(n=0\).
Puisque \(f\) est surjective, il existe \(k \in \mathbb{N}\) tel que \(f(k)=0\).
On sait que \(f(k)\geq k\).
Donc \(0\geq k\).
Puisque \(k\in\mathbb{N}\), on obtient \(k=0\).
Ainsi, \(f(0)=0\).
Hérédité :
Soit \(n\in\mathbb{N}\).
On suppose que\[\forall k\in\{0,1,\ldots,n\},\quad f(k)=k.\]
Montrons que \(f(n+1)=n+1\).
On suppose par l'absurde que \(f(n+1)\neq n+1\).
Puisque \(f(n+1)\geq n+1\), alors \(f(n+1)\geq n+2\).
Comme \(f\) est surjective, il existe \(k\in\mathbb{N}\) tel que \(f(k)=n+1\).
On a \(f(k)\geq k\), donc \(n+1\geq k\).
De plus, puisque \(f(n+1)\neq n+1\), alors \(k\neq n+1\).
Donc \(k\in\{0,1,\ldots,n\}\).
Par hypothèse de récurrence, \(f(k)=k\).
Ainsi, \(n+1=k\leq n\), ce qui est absurde.
Donc \(f(n+1)=n+1\).
Conclusion :
Par le principe de récurrence forte, on a :\[\forall n\in\mathbb{N},\quad f(n)=n.\]
Autrement dit, \(f=\operatorname{id}_{\mathbb{N}}\).