Opération sur des correspondances

Opération sur des correspondances

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

Sommaire

Correspondances et opérations ensemblistes

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

En revanche, il est possible de définir des correspondances dont le graphe est le résultat dopérations ensemblistes sur dautres graphes :

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 :

- lensemble de départ est la réunion des ensembles de départ des deux correspondances,
- lensemble darrivée est la réunion de leurs ensembles darrivée,
- et le graphe est la réunion de leurs graphes.

En dautres 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 )

Intersection

Lintersection 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 :

- lensemble de départ est lintersection des ensembles de départ des deux correspondances,
- lensemble darrivée est lintersection de leurs ensembles darrivée,
- et le graphe est lintersection de leurs graphes.

En dautres 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 )

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 :

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

En dautres 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 )

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 :

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

En dautres 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 )

Complémentaire

La correspondance complémentaire relationnelle dune correspondance  \mathfrak{C} , notée :

« Erreur math (La conversion en PNG a échoué ; vérifiez linstallation de latex et dvipng (ou dvips + gs + convert)): \bar \mathfrak{C}
»   ( lire « C barre » ) 

est la correspondance dont :

- lensemble de départ est celui de  \mathfrak{C} ,
- lensemble darrivé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 darrivée.

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

Erreur math (La conversion en PNG a échoué ; vérifiez linstallation de latex et dvipng (ou dvips + gs + convert)): \bar \mathfrak{C} = ( E , F , E \times F - G )


Par exemple, la correspondance complémentaire dune correspondance vide est une correspondance pleine, et vice versa car : Erreur math (La conversion en PNG a échoué ; vérifiez linstallation de latex et dvipng (ou dvips + gs + convert)): \overline{ \bar \mathfrak{C} } = \mathfrak{C} \, .

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

Remarque importante

En pratique, quand nous rencontrerons une opération ensembliste sur des correspondances, il sagira en fait dun abus de langage : par exemple, lintersection «  \mathfrak{C}_1 \cap \, \mathfrak{C}_2  » désignera en fait lintersection 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 noffrent pas dintérêt. De plus, il rejoint et renforce celui consistant à confondre les correspondances avec leur graphe.

Comparaison de correspondances

Labus de langage précédent sétend à l'inclusion des correspondances : nous définissons l'inclusion relationnelle de deux correspondances par linclusion de leurs ensembles de départ, darrivée et graphes respectifs.

En dautres 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 ) .

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

Restrictions et extensions dune correspondance

La restriction dune correspondance à des parties de ses ensembles de départ et darrivée est la correspondance dont les ensembles de départ et darrivée sont ces parties, et le graphe lintersection du graphe initial avec le produit cartésien de ces parties.

En dautres 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 darrivée dune correspondance, la restriction obtenue est unique; en revanche, pour deux sur-ensembles donnés des mêmes ensembles de départ et darrivée, il est possible a priori de construire plusieurs extensions distinctes, suivant que lon choisit dajouter ou non tel ou tel couple dans le graphe.

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 dautres 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 dun couple du second graphe et dun 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 :

- lensemble de départ est celui de la seconde correspondance,
- lensemble darrivée celui de la première correspondance,
- et le graphe le composé des deux graphes.

En dautres 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 ) .

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.
 \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 nest pas commutative, et il est donc vital de respecter lordre des compositions! En effet, dans la plupart des cas :
 \mathfrak{C}_2 \circ \mathfrak{C}_1 \ne \mathfrak{C}_1 \circ \mathfrak{C}_2 .

Composition et Identités

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

En dautres 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 lensemble de départ est E ;
- Id F est neutre à droite pour les correspondances dont lensemble darrivée est F ;

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

Composition et Réciproque

La composée dune 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 sils 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 lidentité de E :

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

Nous avons linclusion inverse ssi  \mathfrak{C} est injective.

De la même manière, la composée de la réciproque dune correspondance par celle-ci est la relation binaire dans F définie par :

« x et y sont en relation si et seulement sils 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, linclusion 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 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.

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} \,

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 \ \} \,

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.

Voir aussi


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Opération sur des correspondances de Wikipédia en français (auteurs)

Игры ⚽ Нужен реферат?

Regardez d'autres dictionnaires:

  • Operation sur des correspondances — Opération sur des correspondances Une opération sur des correspondances permet de créer de nouvelles correspondances. Sommaire 1 Correspondances et opérations ensemblistes 1.1 Réunion 1.2 Intersection …   Wikipédia en Français

  • Correspondances et Relations — Correspondance et relation En algèbre générale (ou abstraite), le concept de correspondance, ou de relation, est une abstraction de notions telles que l’égalité, l’ordre alphabétique, ou la comparaison. De manière informelle, une relation dans un …   Wikipédia en Français

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français

  • Liste des articles de mathematiques — Projet:Mathématiques/Liste des articles de mathématiques Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou probabilités et statistiques via l un des trois bandeaux suivants  …   Wikipédia en Français

  • Ligne des Coteaux — Ligne 2 du tramway d Île de France Tramway T2 Tram Val de Seine Réseau Tramway d Île de France Année d’ouverture 1997 Dernière extension 21  …   Wikipédia en Français

  • Meudon-sur-Seine (station tramway de Paris) — Ligne 2 du tramway d Île de France Tramway T2 Tram Val de Seine Réseau Tramway d Île de France Année d’ouverture 1997 Dernière extension 21  …   Wikipédia en Français

  • Meudon-sur-seine (station tramway de paris) — Ligne 2 du tramway d Île de France Tramway T2 Tram Val de Seine Réseau Tramway d Île de France Année d’ouverture 1997 Dernière extension 21  …   Wikipédia en Français

  • Langage des oiseaux — Langue des oiseaux La langue des oiseaux est une langue fictive et secrète qui consiste à donner un sens autre à des mots ou à une phrase, soit par un jeu de sonorités, soit par des jeux de mots (verlan, anagrammes, fragments de mots…), soit… …   Wikipédia en Français

  • Langue des oiseaux — La langue des oiseaux est une langue secrète qui consiste à donner un sens autre à des mots ou à une phrase, soit par un jeu de sonorités, soit par des jeux de mots (verlan, anagrammes, fragments de mots…), soit enfin par le recours à la… …   Wikipédia en Français

  • Analyse des données — L’analyse des données est un domaine des statistiques qui se préoccupe de la description de données conjointes. On cherche par ces méthodes à donner les liens pouvant exister entre les différentes données et à en tirer une information statistique …   Wikipédia en Français

Share the article and excerpts

Direct link
https://fr-academic.com/dic.nsf/frwiki/1266898 Do a right-click on the link above
and select “Copy Link”