Page d'accueil	encyclopedie-enligne.com en page d'accueil
Liste Articles: [0-A] [A-C] [C-F] [F-J] [J-M] [M-P] [P-S] [S-Z] \| Liste Catégories \| Une page au hasard \| Pages liées

Correspondances et Relations

En algèbre abstraite, la notion de relation est une abstraction de notions telles que l'égalité, l'ordre alphabétique, ou la comparaison.

Informellement, une relation sur un ensemble est une proposition qui lie un certain nombre d'éléments. Sur un ensemble constitué de personnes, par exemple, on pourrait définir une relation « Alice aime Bernard », ou « Cecile connaît David »... On peut donc voir une relation comme des fils reliant divers éléments d'un ensemble.

La notion de correspondance généralise celle de relation en établissant des liens entre des éléments d'ensembles distincts.

Sommaire

1 Notion de correspondance

1.1 Notion de relation
1.2 Définitions
1.3 Exemples de correspondances. Cas particuliers importants
1.4 Représentation des correspondances

2 Opérations sur les correspondances

2.1 Egalité de deux correspondances
2.2 Correspondances et opérations ensemblistes
2.3 Comparaison de deux correspondances
2.4 Restrictions et extensions d'une correspondance

3 Propriétés des correspondances

3.1 Images et antécédents
3.2 Correspondance réciproque
3.3 Fonctions, applications et bijections
3.4 Composition des correspondances

4 Tableau récapitulatif

5 Voir aussi

Notion de correspondance

Notion de relation

Plus formellement, le lien entre deux éléments peut s'exprimer sous forme d'un « couple ». Un couple, noté entre parenthèses, est constitué de deux éléments mis dans un ordre particulier. Les correspondances et les relations peuvent ainsi être considérées en première approche comme des ensembles de couples, c'est-à-dire des graphes. Mais cela ne suffit pas toujours: les propriétés des correspondances dépendent autant des absences de liens entre éléments que de leur existence. En d'autres termes, la donnée du graphe d'une correspondance ne suffit pas à définir complètement celle-ci ; il faut aussi connaître les couples d'éléments non-liés. Cela revient à préciser dans quel produit cartésien s'inscrit la correspondance. ( Rappel : le produit cartésien de deux ensembles E et F, noté E×F, est l'ensemble de tous les couples dont le premier élément vient de E et le second de F ).

Néanmoins, il demeure possible, le plus souvent, de confondre une correspondance avec son graphe, du moment qu'il n'y a pas d'ambiguïté sur le produit cartésien dans lequel elle s'inscrit. Par exemple, considérons un ensemble de personnes :

$P = \{ Alice, Bernard \}\,$

Et posons :

$aime = \{( Alice, Bernard ),( Alice, Alice ),( Bernard, Bernard )\}\,$

Pour la relation aime, si « Alice aime Bernard », alors le couple ( Alice, Bernard ) fait partie de l'ensemble aime, ce que l'on note :

$(\mathrm{ Alice, Bernard}) \in aime$

L'ensemble aime est un sous-ensemble de $P \times P$ . La relation aime est réflexive (voir « Relation binaire »).

On note au passage que l'ordre dans le couple a de l'importance, car si « Alice aime Bernard », le contraire n'est pas forcément vrai, puisque nous avons ici :

$( \mathrm{ Bernard, Alice}) \notin aime$

Considérons à présent:

$Q = \{ Alice, Bernard, Christian \,\}$

aime est aussi un sous-ensemble de $Q \times Q$ , mais la relation aime n'est plus réflexive : la présence de Christian a modifié la relation, même si aucun lien n'a été rajouté.

En fait, la relation aime dans Q doit être distinguée de la relation aime dans P, même si elles ont toutes deux le même graphe. Pour y parvenir, l'idée la plus simple est de considérer qu'une relation comporte non seulement un graphe, mais aussi le produit cartésien dans lequel il s'inscrit : si aime désigne toujours le graphe, les relations deviennent alors ( P×P , aime ) et ( Q×Q , aime ) ou, ce qui revient en pratique au même, ( P , P , aime ) et ( Q , Q , aime ).

Cette façon de procéder comporte toutefois un défaut : elle ne permet pas de définir des relations dans les univers, puisque les éléments de n-uplets doivent être des ensembles. Cela pose problème avec la relation d'équipotence par exemple, qui est à la base de la définition des cardinaux, et qui est censée être définie dans l'univers de tous les ensembles.

Une solution (déjà entrevue dans l'article « Produit cartésien ») consiste à remplacer les triplets précédents par des sommes disjointes : les deux relations précédentes seront alors définies comme $\dot \cup ( P , P , aime )$ et $\dot \cup ( Q , Q , aime )$ , toujours notées cependant par abus d'écriture $( P , P , aime ) \,$ et $( Q , Q , aime ) \,$ .

Remarque : le cheminement ci-dessus est caractéristique de la démarche des mathématiciens lorsqu'ils élaborent une définition : ils partent d'une première approche simple, qu'ils améliorent ensuite en la compliquant pour éliminer des contradictions internes ou prendre en compte certains cas particuliers, puis qu'ils généralisent au maximum.

Définitions

Notes préliminaires :

- ce qui suit demeure valide si on y remplace les ensembles par des classes ou des univers.

- pour alléger l'écriture, nous noterons à partir d'ici les sommes disjointes comme des n-uplets.

Une correspondance est la somme disjointe de trois ensembles dont le troisième est une partie du produit cartésien des deux premiers.

Plus précisément, si E et F sont deux ensembles, alors $\mathfrak{C}$ est une correspondance de E dans F si et seulement si :

$\exists\ G \ / \ ( \mathfrak{C} = (E, F, G) ) \wedge ( G \subseteq E \times F )$

E est l'ensemble de départ de la correspondance, F son ensemble d'arrivée et G son graphe.

En pratique, on confondra une correspondance avec son graphe s'il n'y a pas d'ambiguïté sur les ensembles de départ et d'arrivée.

Une relation est alors une correspondance dont l'ensemble de départ est égal à l'ensemble d'arrivée ou, plus généralement, au produit cartésien de celui-ci par un autre ensemble ; en d'autres termes, l'ensemble de départ d'une relation est

- soit une puissance cartésienne de l'ensemble d'arrivée (relations internes),

- soit le produit cartésien d'un ensemble dit de scalaires par une telle puissance (relations externes);

Plus précisément, si E et S sont deux ensembles :

- $\mathfrak{R}$ est une relation interne dans E si et seulement si :

$\exists\ G \ , \exists n \in \mathbb{N} \ / \ ( n \geq 2 ) \wedge ( \mathfrak{R} = ( E^{n-1} , E , G ) ) \wedge ( G \subseteq E^n )$

- $\mathfrak{R}$ est une relation externe de S dans E si et seulement si :

$\exists\ G \ , \exists n \in \mathbb{N} \ / \ ( n \geq 3 ) \wedge ( \mathfrak{R} = ( S \times E^{n-2} , E , G ) ) \wedge ( G \subseteq S \times E^{n-1} )$

n est appelé arité de la relation qui est alors dite n-aire. Ainsi :

- une relation binaire, d'arité 2 , nécessairement interne, est une correspondance dont les ensembles de départ et d'arrivée sont les mêmes. En d'autres termes, si E est un ensemble, $\mathfrak{R}$ est une relation binaire dans E si et seulement si :

$\exists\ G\ /\ (\mathfrak{R} = (E, E, G))\wedge(G \subseteq E\times E)$

- une relation ternaire interne est une correspondance dont l'ensemble de départ est le carré cartésien de l'ensemble d'arrivée; en d'autres termes, si E est un ensemble, $\mathfrak{R}$ est une relation ternaire interne dans E si et seulement si :

$\exists\ G\ /\ (\mathfrak{R} = (E\times E, E, G))\wedge(G \subseteq E^3)$

- une relation ternaire externe est une correspondance dont l'ensemble de départ est le produit cartésien d'un ensemble S de scalaires par l'ensemble d'arrivée; en d'autres termes, si E et S sont deux ensembles, $\mathfrak{R}$ est une relation ternaire externe de S dans E si et seulement si :

$\exists\ G\ /\ (\mathfrak{R} = (S\times E, E, G))\wedge(G \subseteq S\times E^2)$

Exemples de correspondances. Cas particuliers importants

L'égalité et l'inclusion sont des relations binaires dans l'univers des ensembles.
La réunion, l'intersection, la différence et la différence symétrique sont des relations ternaires internes dans l'univers des ensembles.
Etudier quels sont les sports pratiqués par les français revient à établir une correspondance de l'ensemble des français dans l'ensemble des sports possibles.
Si E = { a, b, c, d } , F = { 1, 2, 3 } et si G = { ( a, 1 ), ( b, 2), ( b, 3), (c, 3) }, alors ( E, F, G ) est une correspondance de E dans F.
Une correspondance est vide si et seulement si son graphe est égal à l'ensemble vide.
Une correspondance est pleine si et seulement si son graphe est égal au produit cartésien des ensembles de départ et d'arrivée tout entier.
La relation binaire dans E dont le graphe est la diagonale de E est appelée identité de E.

Représentation des correspondances

Opérations sur les correspondances

Egalité de deux correspondances

Deux correspondances sont égales si et seulement si elles ont mêmes ensembles de départ et d'arrivée et même graphe.

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 = \mathfrak{C}_2 ) \Leftrightarrow ( E_1 = E_2 \wedge F_1 = F_2 \wedge G_1 = G_2 )$ .

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.

Par contre, il est possible de définir des correspondances dont le graphe est le résultat d'opérations ensemblistes sur d'autres graphes :

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

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

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

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

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

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

Il faut noter que si pour deux sous-ensembles donnés des ensembles de départ et d'arrivée d'une correspondance, la restriction obtenue est unique, par contre, 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.

Propriétés des correspondances

Images et antécédents

Si $\mathfrak{C}$ est une correspondance, avec $\mathfrak{C} = ( E , F , G )$ , alors les affirmations suivantes sont équivalentes :

- y correspond à x par $\mathfrak{C}$ ;

- ( x , y ) appartient à G ;

- y est image de x par $\mathfrak{C}$ ;

- x est antécédent de y par $\mathfrak{C}$ .

Le terme de « préimage » est parfois employé à la place de celui d'« antécédent ».

L'ensemble formé par les images de tous les éléments de l'ensemble de départ d'une correspondance est appelé ensemble-image de cette correspondance. Un abus de langage courant consiste à appeler cet ensemble « image » de la correspondance, mais cela peut entraîner une confusion si la correspondance est elle-même élément d'un ensemble à partir duquel une autre correspondance est bâtie.

Symétriquement, l'ensemble formé par les antécédents de tous les éléments de l'ensemble d'arrivée d'une correspondance est appelé ensemble-antécédent de cette correspondance. L'ensemble-antécédent est aussi nommé « domaine de définition » de la correspondance.

Correspondance réciproque

Le graphe réciproque d'un graphe , noté « », est le graphe obtenu en échangeant dans chaque couple du graphe la première composante avec la seconde :

$G^{-1} = \{ ( y, x ) | ( x, y ) \in G \}$

La correspondance réciproque d'une correspondance est la correspondance obtenue en échangeant les ensembles de départ et d'arrivée et en remplaçant le graphe par son graphe réciproque.

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

$\mathfrak{C}^{-1} = ( F , E , G^{-1} )$

Fonctions, applications et bijections

Les correspondances peuvent avoir quatre propriétés de base indépendantes les unes des autres : elles peuvent être fonctionnelles, applicatives, injectives ou surjectives, ce qui donne a priori seize types de correspondances, mais seules certaines d'entre elles ont un nom; il est possible de résumer ces propriétés et leur définition dans le tableau suivant :

Propriété :	au plus ...	au moins ...	exactement ...
Correspondance :	fonctionnelle	applicative	univoque	... une image par antécédent
Correspondance :	injective	surjective	bijective	... un antécédent par image
Correspondance :	bifonctionnelle	biapplicative	biunivoque	... 1 image / antécédent et 1 antécédent / image

Seules certaines des combinaisons des quatre propriétés de base ont reçu un nom, en raison de leur importance pratique :

une fonction est une correspondance fonctionnelle; cette propriété est importante car elle permet d'utiliser la notation fonctionnelle « y = f( x) » au lieu des notations relationnelles infixée « x R y » ou préfixée « R x y » , ou de la notation ensembliste « (x, y) ∈ G » ;
une application est une fonction applicative ; c'est donc aussi une correspondance fonctionnelle et applicative, c'est-à-dire une correspondance univoque ;
une injection est une application injective; c'est donc une correspondance fonctionnelle, applicative et injective, c'est-à-dire une correspondance applicative et bifonctionnelle;
une surjection est une application surjective; c'est donc une correspondance fonctionnelle, applicative et surjective, c'est-à-dire une fonction biapplicative;
une bijection est une application bijective; c'est donc une correspondance fonctionnelle, applicative, injective et surjective, c'est-à-dire une correspondance biunivoque;

Une correspondance applicative (respectivement injective, surjective, bijective) n'est pas en général une application (respectivement une injection, une surjection, une bijection);

Une fonction injective ( respectivement surjective, bijective) n'est pas en général une injection (respectivement une surjection, une bijection);

La réciproque d'une correspondance inverse le rôle des images et des antécédents (rappel : si x R y , alors y est une image de x par R et x est un antécédent de y par R); par conséquent (cela se lit directement sur le tableau ci-dessus) :

- la réciproque d'une fonction est une correspondance injective, et, inversement, pour que la réciproque d'une correspondance soit une fonction, il faut et il suffit que cette correspondance soit injective;

- la réciproque d'une correspondance applicative est surjective, et vice-versa;

- la réciproque d'une application est une correspondance bijective;

- la réciproque d'une correspondance bifonctionnelle, c'est-à-dire d'une fonction injective, est une correspondance bifonctionnelle, c'est-à-dire une fonction injective;

- la réciproque d'une correspondance biapplicative est elle-même biapplicative;

- et enfin, la réciproque d'une bijection est une bijection.

Composition des correspondances

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, y) | \ \exists z \ / (( x, z) \in G_1 ) \wedge (( z, y) \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 )$ .

Tableau récapitulatif

Principales familles de correspondances
Correspondances	Relations binaires	Relations ternaires internes	Relations ternaires externes
Fonctions	.	Opérations internes	Opérations externes
Applications	Transformations	Lois (de composition) internes	Lois (de composition) externes
Bijections	Permutations	.	.

Notes :

- les relations ternaires internes ne peuvent être des bijections que si le cardinal de leur ensemble d'arrivée est infini ou égal à 0 ou à 1 ;

- les quatre opérations de notre enfance (+, -, x, :) sont effectivement des opérations internes dans $\mathbb{N}$ , et seules l'addition et la multiplication y sont des lois de composition.

Voir aussi

Catégories: Théorie des ensembles | Algèbre

This site support the Wikimedia Foundation. This Article originally from Wikipedia. All text is available under the terms of the