Opération sur des correspondances

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

Cet 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.

Aller à : Navigation, Rechercher

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 \hat \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 \hat \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 \hat \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 \hat \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 \hat \backslash \, \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 \hat \backslash \, \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 \hat \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 \hat \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 :

« $\bar \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 :

$\bar \mathfrak{C} = ( E , F , E \times F - G )$

Par exemple, la correspondance complémentaire d’une correspondance vide est une correspondance pleine, et vice versa car : $\overline{ \bar \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 \hat \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 \hat \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 « $\hat \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 :

$E_2 \cap F_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_E \circ \mathfrak{C} = \mathfrak{C}$ et d’autre part : $\mathfrak{C} \circ Id_F = \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 à 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 $\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.