logo

Opération sur des correspondances


Opération sur des correspondances : encyclopédie mathématiques

wikipediaCet article est issu de l'encyclopédie libre Wikipedia.
Vous pouvez consulter l'article ici ainsi que son historique.
Les textes et les images sont disponibles sous les termes de la Licence de documentation libre GNU.

Une opération sur des correspondances permet de créer de nouvelles correspondances.

Sommaire

[modifier] Correspondances et opérations ensemblistes

Les opérations purement ensemblistes sur les correspondances n’offrent aucun intérêt. Par exemple, la réunion ensembliste de deux correspondances n’est pas en général une correspondance.

En revanche, il est possible de dĂ©finir des correspondances dont le graphe est le rĂ©sultat d’opĂ©rations ensemblistes sur d’autres graphes :

[modifier] Réunion

La rĂ©union relationnelle de deux correspondances  \mathfrak{C}_1 et  \mathfrak{C}_2 , notĂ©e :

«  \mathfrak{C}_1  \widehat \cup \, \mathfrak{C}_2 »   ( lire « C1 union C2 Â» )

est la correspondance dont :

- l’ensemble de départ est la réunion des ensembles de départ des deux correspondances,
- l’ensemble d’arrivée est la réunion de leurs ensembles d’arrivée,
- et le graphe est la réunion de leurs graphes.

En d’autres termes, si  \mathfrak{C}_1 = ( E_1 , F_1 , G_1 ) et si  \mathfrak{C}_2 = ( E_2 , F_2 , G_2 ) , alors :

 \mathfrak{C}_1  \widehat \cup \, \mathfrak{C}_2 = ( E_1 \cup E_2 , F_1 \cup F_2 , G_1 \cup G_2 )

[modifier] Intersection

L’intersection relationnelle de deux correspondances  \mathfrak{C}_1 et  \mathfrak{C}_2 , notĂ©e :

«  \mathfrak{C}_1  \widehat \cap \, \mathfrak{C}_2 »   ( lire « C1 inter C2 Â» )

est la correspondance dont :

- l’ensemble de départ est l’intersection des ensembles de départ des deux correspondances,
- l’ensemble d’arrivée est l’intersection de leurs ensembles d’arrivée,
- et le graphe est l’intersection de leurs graphes.

En d’autres termes, si  \mathfrak{C}_1 = ( E_1 , F_1 , G_1 ) et si  \mathfrak{C}_2 = ( E_2 , F_2 , G_2 ) , alors :

 \mathfrak{C}_1  \widehat \cap \, \mathfrak{C}_2 = ( E_1 \cap E_2 , F_1 \cap F_2 , G_1 \cap G_2 )

[modifier] Différence

La diffĂ©rence relationnelle de deux correspondances  \mathfrak{C}_1 et  \mathfrak{C}_2 , notĂ©e :

«  \mathfrak{C}_1  \widehat \setminus \, \mathfrak{C}_2 »   ( lire « C1 moins C2 Â» )

est la correspondance dont :

- l’ensemble de départ est l’ensemble de départ de la première correspondance,
- l’ensemble d’arrivée est l’ensemble d’arrivée de cette correspondance,
- et le graphe est la différence des graphes des deux correspondances.

En d’autres termes, si  \mathfrak{C}_1 = ( E_1 , F_1 , G_1 ) et si  \mathfrak{C}_2 = ( E_2 , F_2 , G_2 ) , alors :

 \mathfrak{C}_1  \widehat \setminus \, \mathfrak{C}_2 = ( E_1 , F_1 , G_1 \backslash G_2 )

[modifier] Différence symétrique

La diffĂ©rence symĂ©trique relationnelle de deux correspondances  \mathfrak{C}_1 et  \mathfrak{C}_2 , notĂ©e :

«  \mathfrak{C}_1  \widehat \Delta \, \mathfrak{C}_2 »   ( lire « C1 delta C2 Â» )

est la correspondance dont :

- l’ensemble de départ est la réunion des ensembles de départ des deux correspondances,
- l’ensemble d’arrivée est la réunion de leurs ensembles d’arrivée,
- et le graphe est la différence symétrique de leurs graphes.

En d’autres termes, si  \mathfrak{C}_1 = ( E_1 , F_1 , G_1 ) et si  \mathfrak{C}_2 = ( E_2 , F_2 , G_2 ) , alors :

 \mathfrak{C}_1  \widehat \Delta \, \mathfrak{C}_2 = ( E_1 \cup E_2 , F_1 \cup F_2 , G_1 \Delta G_2 )

[modifier] Complémentaire

La correspondance complĂ©mentaire relationnelle d’une correspondance  \mathfrak{C} , notĂ©e :

«  \overline{\mathfrak{C}}  Â»   ( lire « C barre Â» )

est la correspondance dont :

- l’ensemble de départ est celui de  \mathfrak{C} ,
- l’ensemble d’arrivée est celui de  \mathfrak{C} ,
- et le graphe est le complémentaire de celui de  \mathfrak{C} dans le produit cartésien des ensembles de départ et d’arrivée.

En d’autres termes, si  \mathfrak{C} = ( E , F , G ) , alors :

 \overline{\mathfrak{C}} = ( E , F , (E \times F) \setminus G )

Par exemple, la correspondance complĂ©mentaire d’une correspondance vide est une correspondance pleine, et vice versa car :  \overline{\overline{\mathfrak{C}}} = \mathfrak{C} \,.

Il ne faut pas confondre les correspondances complémentaires et réciproques. Ainsi, la réciproque d’une correspondance vide est elle-même vide, alors que sa complémentaire est une correspondance pleine.

[modifier] Remarque importante

En pratique, quand nous rencontrerons une opĂ©ration ensembliste sur des correspondances, il s’agira en fait d’un abus de langage : par exemple, l’intersection «  \mathfrak{C}_1 \cap \, \mathfrak{C}_2  Â» dĂ©signera en fait l’intersection relationnelle «  \mathfrak{C}_1  \widehat \cap \, \mathfrak{C}_2  Â» . Cet abus de langage est sans consĂ©quence puisque les vĂ©ritables opĂ©rations ensemblistes sur les correspondances n’offrent pas d’intĂ©rĂŞt. De plus, il rejoint et renforce celui consistant Ă  confondre les correspondances avec leur graphe.

[modifier] Comparaison de correspondances

L’abus de langage prĂ©cĂ©dent s’étend Ă  l'inclusion des correspondances : nous dĂ©finissons l'inclusion relationnelle de deux correspondances par l’inclusion de leurs ensembles de dĂ©part, d’arrivĂ©e et graphes respectifs.

En d’autres termes, si  \mathfrak{C}_1 = ( E_1 , F_1 , G_1 ) et si  \mathfrak{C}_2 = ( E_2 , F_2 , G_2 ) , alors :

 ( \mathfrak{C}_1 \widehat \subseteq \mathfrak{C}_2 ) \Leftrightarrow ( E_1 \subseteq E_2 \wedge F_1 \subseteq F_2 \wedge G_1 \subseteq G_2 ) .

LĂ  encore, en pratique, nous parlons d'« inclusion Â» au lieu d'« inclusion relationnelle Â» et nous notons «  \subseteq  Â» au lieu de «  \widehat \subseteq  Â».

[modifier] Restrictions et extensions d’une correspondance

La restriction d’une correspondance à des parties de ses ensembles de départ et d’arrivée est la correspondance dont les ensembles de départ et d’arrivée sont ces parties, et le graphe l’intersection du graphe initial avec le produit cartésien de ces parties.

En d’autres termes, si  \mathfrak{C} = ( E , F , G ) , et si E' et F' sont deux sous-ensembles de E et de F respectivement, alors :

 \mathfrak{C}|_{E'}^{F'} = ( E' , F' , ( E' \times F' ) \cap G ) .

Il est Ă©quivalent d’écrire :

- la correspondance  \mathfrak{C}_1 est incluse dans la correspondance  \mathfrak{C}_2 ;
- la correspondance  \mathfrak{C}_1 est une restriction de la correspondance  \mathfrak{C}_2 ;
- la correspondance  \mathfrak{C}_2 est une extension de la correspondance  \mathfrak{C}_1 .

Si pour deux sous-ensembles donnés des ensembles de départ et d’arrivée d’une correspondance, la restriction obtenue est unique; en revanche, pour deux sur-ensembles donnés des mêmes ensembles de départ et d’arrivée, il est possible a priori de construire plusieurs extensions distinctes, suivant que l’on choisit d’ajouter ou non tel ou tel couple dans le graphe.

[modifier] Composition des correspondances

[modifier] 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 :

 \forall x, \forall y, \forall z, ( x, y) \circ ( y, z) = (x, z)

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.

 G_2 \circ G_1 = \{ ( x, z ) | \ \exists y \ / (( x, y ) \in G_1 ) \wedge (( y, z ) \in G_2 ) \} .

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  \mathfrak{C}_1 = ( E_1 , F_1 , G_1 ) et si  \mathfrak{C}_2 = ( E_2 , F_2 , G_2 ) , alors :

 \mathfrak{C}_2 \circ \mathfrak{C}_1 = ( E_1 , F_2 , G_2 \circ G_1 ) .

[modifier] 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 :
 F_2 \cap E_1 = \varnothing \,
  • 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 « Â­ \circ \, Â» est une loi de composition interne associative :
 \forall \mathfrak{C}_1 , \forall \mathfrak{C}_2 , \forall \mathfrak{C}_3 , ( \mathfrak{C}_1 \circ \mathfrak{C}_2 ) \circ \mathfrak{C}_3 = \mathfrak{C}_1 \circ ( \mathfrak{C}_2 \circ \mathfrak{C}_3 ) .
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 :
 \mathfrak{C}_2 \circ \mathfrak{C}_1 \ne \mathfrak{C}_1 \circ \mathfrak{C}_2 .

[modifier] Composition et Identités

Pour toute correspondance  \mathfrak{C} = ( E , F , G ) , nous avons d’une part :  Id_F \circ \mathfrak{C} = \mathfrak{C}   et d’autre part :    \mathfrak{C} \circ Id_E = \mathfrak{C} .

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 Ă  droite pour les correspondances dont l’ensemble de dĂ©part est E ;
- Id F est neutre Ă  gauche pour les correspondances dont l’ensemble d’arrivĂ©e est F ;

En particulier, pour toute IdentitĂ© : Id E  \circ Id E = Id E.

[modifier] Composition et Réciproque

La composée d’une correspondance par sa réciproque est une relation binaire interne:

 \mathfrak{C}^{-1} \circ \mathfrak{C} = ( E , E , G^{-1} \circ G ) .

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  \mathfrak{C}  Â».

Cette relation est évidemment symétrique et transitive, mais elle n'est réflexive, et donc une relation d'équivalence , que si  \mathfrak{C} est applicative.

Comme toute relation rĂ©flexive, elle contient alors l’identitĂ© de E :

 G^{-1} \circ G \supseteq \Delta E , ou encore :  \mathfrak{C}^{-1} \circ \mathfrak{C} \supseteq Id_E \,.

Nous avons l’inclusion inverse ssi  \mathfrak{C} est injective.

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  \mathfrak{C}  Â».

Cette relation est une relation d'Ă©quivalence ssi  \mathfrak{C} est surjective. Nous avons alors :

 \mathfrak{C} \circ \mathfrak{C}^{-1} = ( F , F , G \circ G^{-1} ) \supseteq Id_F .

Cette fois, l’inclusion inverse est obtenue ssi  \mathfrak{C} est fonctionnelle.

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 :

 \mathfrak{C}^{-1} \circ \mathfrak{C} = Id_E \,   et    \mathfrak{C} \circ \mathfrak{C}^{-1} = Id_F \,

que si  \mathfrak{C} est une bijection.

[modifier] 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} \,

[modifier] Puissances de composition

Si  \mathfrak{C} = ( E , F , G ) , alors :

 \mathfrak{C} \circ \mathfrak{C} = \mathfrak{C}^{\cdot 2} = ( E , F , G \circ G ) \,
avec  G \circ G = \{ ( x , z ) \in E \times F \ |\ \exists\ y \in E \cap F /\ ( x , y ) \in G \ \and\ ( y , z ) \in G \ \} \,

Plus gĂ©nĂ©ralement :

 \mathfrak{C}^{\cdot n} = \mathfrak{C} \circ \mathfrak{C} ... \circ \mathfrak{C} = ( E , F , G^{\cdot n} ) \,
avec  G^{\cdot n} = \{ ( x_1 , x_n ) \in E \times F \ |\ \exists\ ( x_2 , ... , x_{n-1} ) \in ( E \cap F )^{n-2} /\ \,
 ( x_1 , x_2 ) \in G \ \and\ ( x_2 , x_3 ) \in G \ ... \and\ ( x_{n-1} , x_n ) \in G \ \} \,

[modifier] 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.

[modifier] Voir aussi

wikipediaCet article est issu de l'encyclopédie libre Wikipedia.
Vous pouvez consulter l'article ici ainsi que son historique.
Les textes et les images sont disponibles sous les termes de la Licence de documentation libre GNU.


maths haut de pagehaut Retrouvez cette page sur ilemaths l'île des mathématiques
© Tom_Pascal & Océane 2012