Les applications : composer, inverser, factoriser, compter
Une application f de E dans F associe à chaque élément de E un et un seul élément de F. La première page a présenté le vocabulaire : image, antécédent, injection, surjection, bijection. Cette deuxième page montre ce que l'on fait avec les applications. On les enchaîne, on cherche à les défaire d'un côté ou de l'autre, on les décompose en trois étapes élémentaires et on les compte. Puis on regarde ce que devient une application quand on l'itère sur un ensemble fini, et pourquoi les applications forment elles-mêmes un ensemble.
Vue d'ensemble
Rappel des trois qualités possibles d'une application f : E → F :
| Qualité | Définition | Ce qui la caractérise |
|---|---|---|
| injective | deux éléments distincts ont des images distinctes | elle a un inverse à gauche : g ∘ f = idE |
| surjective | tout élément de F a au moins un antécédent | elle a un inverse à droite : f ∘ g = idF |
| bijective | les deux à la fois | elle a un inverse des deux côtés, unique : f−1 |
Composer deux applications
Faire f, puis g : la composée g ∘ f va directement de E à G.
Si f : E → F et g : F → G, la composée g ∘ f envoie x sur g(f(x)). On lit de droite à gauche : d'abord f, puis g. La composition est associative, mais pas commutative : f ∘ g n'a souvent même pas de sens. Les qualités se transmettent en partie. Si g ∘ f est injective, alors f l'est forcément : deux éléments confondus par f resteraient confondus par g. Si g ∘ f est surjective, alors g l'est forcément. Les réciproques sont fausses, et la page en cherche les contre-exemples.
Défaire une application : inverses à gauche et à droite
Une injection se défait par la gauche, une surjection par la droite.
Si f est injective, on peut revenir en arrière : chaque élément atteint a un unique antécédent. Une application g : F → E qui renvoie f(x) sur x, et envoie n'importe où les éléments non atteints, vérifie g ∘ f = idE : c'est un inverse à gauche (une rétraction). Si f est surjective, on peut choisir pour chaque y de F un antécédent g(y) : alors f ∘ g = idF, c'est un inverse à droite (une section). Ce choix est facile pour un ensemble fini. Pour un ensemble infini, il demande l'axiome du choix. La page énumère toutes les applications de F dans E et compte combien sont des inverses.
La factorisation canonique
Toute application est une surjection, suivie d'une bijection, suivie d'une injection.
Déclarons équivalents deux éléments de E qui ont la même image : x ~ x′ ⟺ f(x) = f(x′). C'est une relation d'équivalence, et ses classes sont les « fibres » f−1({y}). On obtient f = i ∘ b ∘ s. La surjection s envoie x sur sa classe. La bijection b envoie chaque classe sur l'image commune de ses éléments. L'injection i plonge l'image Im f dans F. C'est la forme ensembliste du théorème d'isomorphisme, qu'on retrouve en algèbre (G/ker f ≅ Im f) et en algèbre linéaire (théorème du rang).
Compter les applications
kⁿ applications, dont un nombre précis d'injections, de surjections et de bijections.
D'un ensemble à n éléments vers un ensemble à k éléments, il y a kn applications : chaque élément de départ choisit librement son image. Les injections sont au nombre de k(k − 1)⋯(k − n + 1) : chaque élément choisit une image encore libre. Les surjections sont plus délicates. Il y en a k!·S(n, k), où S(n, k), le nombre de Stirling de deuxième espèce, compte les façons de découper n éléments en k paquets non vides. C'est la factorisation canonique qui le dit : une surjection, c'est une partition en k classes, plus une bijection des classes vers l'arrivée. Pour n = k, injections, surjections et bijections coïncident : il y en a n!.
Signature : itérer une application, décomposer une permutation, curryfier
Une application d'un ensemble fini dans lui-même finit toujours par tourner en rond.
Pour f : E → E avec E fini, partons d'un élément et appliquons f encore et encore : comme E est fini, on finit par retomber sur un élément déjà vu, puis on tourne en boucle. Le dessin de toutes les flèches x → f(x) est fait de cycles sur lesquels se greffent des arbres. Les éléments situés sur un cycle sont dits cycliques. Pour une application tirée au hasard parmi les nⁿ possibles, leur nombre moyen vaut exactement Σ n!/((n − k)!·nk), soit environ √(πn/2). Ce phénomène est à la base de la méthode rho de Pollard pour factoriser les entiers.
Une bijection de E dans lui-même s'appelle une permutation. Son graphe n'a plus d'arbres, seulement des cycles disjoints : chaque élément revient à lui-même. Si les cycles ont pour longueurs ℓ₁, ℓ₂, …, la permutation revient à l'identité au bout de ppcm(ℓ₁, ℓ₂, …) itérations, son ordre. Une permutation de 30 éléments peut ainsi avoir un ordre de plusieurs milliers. La page itère la permutation jusqu'au retour à l'identité et compare avec le PPCM.
L'ensemble des applications de E dans F se note FE, et il a |F||E| éléments : la notation est faite pour cela. Deux bijections célèbres en découlent. D'abord, une partie A de E correspond à sa fonction indicatrice, de E dans {0, 1} : P(E) est en bijection avec {0, 1}E, d'où ses 2|E| éléments. Ensuite, une application de deux variables, de A × B dans C, est la même chose qu'une application qui à chaque a associe une application de B dans C : CA×B ≅ (CB)A. Les informaticiens appellent cela la curryfication, du nom du logicien Haskell Curry. C'est la règle des exposants (cb)a = cab, réalisée comme une bijection.
Une brève histoire
En résumé
Composer
g ∘ f injective ⇒ f injective ; g ∘ f surjective ⇒ g surjective. Les réciproques sont fausses.
Défaire
Injective ⟺ inverse à gauche ; surjective ⟺ inverse à droite (par choix) ; bijective ⟺ inverse unique des deux côtés.
Décomposer et compter
f = injection ∘ bijection ∘ surjection ; kⁿ applications, k!·S(n,k) surjections, et FE est lui-même un ensemble.
Pour aller plus loin
Le cas infini. Toute surjection a un inverse à droite : cet énoncé équivaut à l'axiome du choix. Pour les injections, en revanche, aucun axiome supplémentaire n'est nécessaire (dès que E n'est pas vide).
Catégories. Dans une catégorie, on remplace « injective » et « surjective » par « monomorphisme » et « épimorphisme », définis uniquement par la composition : f est un monomorphisme si f ∘ g = f ∘ h entraîne g = h. Pour les ensembles, les deux notions coïncident.
Liens. Les applications (première page), les relations binaires, la cardinalité et le dénombrement, l'équipotence et les ensembles infinis, les groupes de permutations.