Opération sur des correspondances - Définition
La liste des auteurs de cet article est disponible ici.
Composition des correspondances
Définitions
Le couple composé à partir de deux couples dont la seconde composante du premier est égale à la première composante du second, est le couple dont la première composante est la première composante du premier couple, et la seconde composante la seconde composante du second couple. En d’autres termes :
Le graphe composé de deux graphes est le graphe dont les couples sont tous les couples composés obtenus à partir d’un couple du second graphe et d’un couple du premier graphe.
-
La correspondance composée de deux correspondances est la correspondance dont :
- - l’ensemble de départ est celui de la seconde correspondance,
- - l’ensemble d’arrivée celui de la première correspondance,
- - et le graphe le composé des deux graphes.
En d’autres termes, si
-
Propriétés
- La composée de deux correspondances est vide si :
- - l'une des deux correspondances est vide;
- - ou, plus généralement, si l'ensemble d'arrivée de la seconde correspondance n'a pas d'élément commun avec l'ensemble de départ de la première correspondance, c'est-à-dire si :
-
- Inversement, la composée de deux correspondances est pleine [ssi] les deux correspondances sont pleines et si l'ensemble de départ de la première correspondance se confond avec l'ensemble d'arrivée de la seconde correspondance.
- Il est possible de montrer que, dans la classe des correspondances, la relation «
-
-
-
- En revanche, elle n’est pas commutative, et il est donc vital de respecter l’ordre des compositions! En effet, dans la plupart des cas :
-
-
Composition et Identités
Pour toute correspondance
En d’autres termes, les Identités apparaissent comme des « éléments neutres » pour la composition des correspondances. Plus précisément :
- - Id E est neutre à gauche pour les correspondances dont l’ensemble de départ est E ;
- - Id F est neutre à droite pour les correspondances dont l’ensemble d’arrivée est F ;
En particulier, pour toute Identité : Id E
Composition et Réciproque
La composée d’une correspondance par sa réciproque est une relation binaire interne:
-
Plus précisément, cette relation est la relation binaire dans E définie par :
- « x et y sont en relation si et seulement s’ils ont une image commune par
Cette relation est évidemment symétrique et transitive, mais elle n'est réflexive, et donc une relation d'équivalence , que si
Comme toute relation réflexive, elle contient alors l’identité de E :
-
Nous avons l’inclusion inverse ssi
De la même manière, la composée de la réciproque d’une correspondance par celle-ci est la relation binaire dans F définie par :
- « x et y sont en relation si et seulement s’ils ont un antécédent commun par
Cette relation est une relation d'équivalence ssi
-
Cette fois, l’inclusion inverse est obtenue ssi
En résumé, la correspondance réciproque joue le rôle de « symétrique » pour la composition (d’où sa notation). Mais nous n'avons :
-
que si
Réciproque d'une composée
La correspondance réciproque de la composée de deux correspondances est, à l'ordre près, la composée des réciproques de ces deux correspondances :
![[ \mathfrak{C}_2 \circ \mathfrak{C}_1 ]^{-1} = ( F_2 , E_1 , [ G_2 \circ G_1 ]^{-1} ) = ( F_2 , E_1 , G_1^{-1} \circ G_2^{-1} ) = \mathfrak{C}_1^{-1} \circ \mathfrak{C}_2^{-1} \,](https://static.techno-science.net/illustrationWebp/Definitions/autres/d/d69e13d5e22827f6a8382e865e502e47_33bfa09e2ce4d0a2f0d06554cf95f8a9.png)
Puissances de composition
Si
-
- avec
- avec
Plus généralement :
-
- avec
-
- avec
Autres cas de composition importants
- La composée de deux correspondances fonctionnelles est fonctionnelle. Par conséquent, la composée de deux fonctions est encore une fonction.
- La composée de deux correspondances applicatives est applicative. En particulier, la composée de deux applications est encore une application.
- La composée de deux correspondances injectives est injective. En particulier, la composée de deux injections est encore une injection.
- La composée de deux correspondances surjectives est surjective. En particulier, la composée de deux surjections est encore une surjection, et la composée de deux bijections est encore une bijection.
- La composée de deux relations binaires internes est encore une relation binaire interne.
