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
2 Restrictions et extensions d’une correspondance
3 Composition des correspondances
4 Voir aussi

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 :

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 )$

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 )$

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 )$

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 )$

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.

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.

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$ ».

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.

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 :

$\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 )$ .

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

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.

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.

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

Correspondance et relation

Portail des mathématiques

Ce document provient de « Op%C3%A9ration sur des correspondances ».

Catégorie : Théorie des ensembles

Wikimedia Foundation. 2010.

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

Игры ⚽ Поможем решить контрольную работу

Regardez d'autres dictionnaires:

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 1.3 … 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

Dictionnaires et Encyclopédies sur 'Academic'

Operation sur des correspondances

Opération sur des correspondances

Sommaire

Correspondances et opérations ensemblistes

Réunion

Intersection

Différence

Différence symétrique

Complémentaire

Remarque importante

Comparaison de correspondances

Restrictions et extensions d’une correspondance

Composition des correspondances

Définitions

Propriétés

Composition et Identités

Composition et Réciproque

Réciproque d'une composée

Puissances de composition

Autres cas de composition importants

Voir aussi

Regardez d'autres dictionnaires:

Share the article and excerpts

Dictionnaires et Encyclopédies sur 'Academic'

Wikipédia en Français

Operation sur des correspondances

Opération sur des correspondances

Sommaire

Correspondances et opérations ensemblistes

Réunion

Intersection

Différence

Différence symétrique

Complémentaire

Remarque importante

Comparaison de correspondances

Restrictions et extensions d’une correspondance

Composition des correspondances

Définitions

Propriétés

Composition et Identités

Composition et Réciproque

Réciproque d'une composée

Puissances de composition

Autres cas de composition importants

Voir aussi

Regardez d'autres dictionnaires:

Share the article and excerpts

Direct link