Démonstration. Fixons F et p = Card F. Nous allons effectuer une récurrence sur n = Card E. Soit (Pn ) l’assertion suivante : le nombre d’applications d’un ensemble à n éléments vers un ensemble à p éléments est p n .
- Initialisation. Pour n = 1, une application de E dans F est définie par l’image de l’unique élément de E. Il y a p = Card F choix possibles et donc p 1 applications distinctes. Ainsi P1 est vraie.
- Hérédité. Fixons n > 1 et supposons que Pn est vraie. Soit E un ensemble à n + 1 éléments. On choisit et fixe a ∈ E ; soit alors E 0 = E \ {a} qui a bien n éléments. Le nombre d’applications de E 0 vers F est p n , par l’hypothèse de récurrence (Pn ). Pour chaque application f : E 0 → F on peut la prolonger en une application f : E → F en choisissant l’image de a. On a p choix pour l’image de a et donc p n × p choix pour les applications de E vers F. Ainsi Pn+1 est vérifiée.
- Conclusion. Par le principe de récurrence Pn est vraie, pour tout n > 1.
Pour télécharger ( smpc1 et svt 1 et smai1 ... )
👍 Série