Graphe d'une relation

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 ensemble ( on dit aussi « 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 « Cécile connaît David »... On peut donc voir une relation comme des fils reliant divers éléments d’un ensemble.

Ce concept peut être généralisé en établissant des liens entre des éléments d’ensembles distincts.

Graphe et correspondance

Le lien entre deux éléments peut s’exprimer de manière plus formelle par un « couple ». Un couple, noté entre parenthèses, est constitué de deux éléments mis dans un ordre particulier. Les correspondances, ou relations générales peuvent ainsi être considérées en première approche comme des ensembles de couples, c’est-à-dire des graphes orientés. 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 savoir quels sont les couples d'éléments qu'elle ne lie pas. Cela revient à préciser dans quel produit cartésien s’inscrit la correspondance.

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.

Pour illustrer ces idées, considérons par exemple l’ensemble P suivant de personnes :

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

Définissons-y naïvement la relation aime par la seule donnée de son graphe :

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

Pour la relation aime, si « Alice aime Bernard », alors le couple ( Alice, Bernard ) fait partie de l’ensemble aime.

L’ensemble aime est un sous-ensemble de P × P. Nous constatons que :

la relation aime est une relation binaire dans P ;
la relation aime est réflexive, puisque toutes les personnes considérées s’aiment elles-mêmes.

Remarquons au passage que l’ordre dans le couple a de l’importance. Si « Alice aime Bernard », la réciproque n’est pas forcément vraie, et d’ailleurs ici ( Bernard , Alice ) n’appartient pas à aime.

Ajoutons une personne à P. L’ensemble des personnes devient :

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

aime est encore un sous-ensemble de Q × Q, mais la relation aime n’est plus réflexive : la simple 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 \times P ,\ \mathrm{aime} ) \quad \mathrm{et} \quad ( Q \times Q ,\ \mathrm{aime} ) \,$ ,

ou, ce qui revient en pratique au même :

$( P ,\ P ,\ \mathrm{aime} ) \quad \mathrm{et} \quad ( Q ,\ Q ,\ \mathrm{aime} ) \,$ .

Cette façon de procéder comporte toutefois encore un défaut : elle ne permet pas de généraliser les relations aux classes propres, 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 la classe 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 ,\ \mathrm{aime} ) \quad \mathrm{et} \quad \dot\cup ( Q ,\ Q ,\ \mathrm{aime} ) \,$ ,

mais encore notées cependant par abus d’écriture :

$( P ,\ P ,\ \mathrm{aime} ) \quad \mathrm{et} \quad ( Q ,\ Q ,\ \mathrm{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éfinition formelle

Notes préliminaires

Pour alléger l’écriture, nous noterons à partir d’ici les sommes disjointes comme des n-uplets.
Les définitions suivantes demeurent ainsi valides si on y remplace les ensembles par des classes même propres.

Définition

Une correspondance, ou relation générale, est la somme disjointe de trois ensembles dont le dernier est une partie du produit cartésien du premier par le deuxième.

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 $\mathfrak{C}$ est égale au triplet (généralisé) ( E, F, G ), où G est une partie de E×F, produit cartésien de E par F.

En langage formel:

$\forall\ E\ ,\ \forall\ F\ [\ \mathfrak{C}\ correspondance\ de\ E\ dans\ F\ ]\ \Leftrightarrow\ [\ \exists\ G\ ,\ G \subseteq E \times F\ \wedge\ \mathfrak{C} = ( E, F, G )\ ]\ \,$

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

Remarque : 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.

Égalité de deux correspondances

D’après leur définition, 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₁ , F₁ , G₁ ) et si $\mathfrak{C}_2$ = ( E₂ , F₂ , G₂ ) , alors :

$( \mathfrak{C}_1 = \mathfrak{C}_2 ) \Leftrightarrow [ ( E_1 = E_2 ) \wedge ( F_1 = F_2 ) \wedge ( G_1 = G_2 ) ] \,$ .

Exemples et cas particuliers importants

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. Elle est donc de la forme ( E, F, Ø ).

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. Elle est donc de la forme ( E, F, E×F ).

La relation dans E dont le graphe est la diagonale de E est appelée identité de E, et notée habituellement « $Id_E \,$ ». Elle est donc égale à ( E, E, $Δ$ E ).

L'ensemble de départ d'une correspondance peut être le produit cartésien de deux ensembles ou plus : ainsi, l'addition des nombres réels est une correspondance de IR × IR dans IR. Il semble évident que l'addition comporte deux arguments; mais en fait, le nombre d'arguments d'une correspondance dépend du point de vue adopté et n'en est donc pas une propriété intrinsèque: ainsi, on peut considérer que l'addition a un seul argument, le couple formé par les deux nombres additionnés !

Représentation des correspondances

Il existe trois types de représentation d’une correspondance :

Exemple de représentation sagittale.

sagittale, qui dérive des diagrammes de Venn pour les ensembles, où les ensembles de départ et d’arrivée sont représentés par deux « patatoïdes » côte à côte, les éléments par des points à l’intérieur des patatoïdes, et les couples du graphe par des flèches reliant les premières composantes aux secondes ;
tabulaire ou matricielle, sous forme d’un tableau à deux entrées, avec en première colonne la liste des éléments de l’ensemble de départ et en première ligne celle des éléments de l’ensemble d’arrivée. Les couples sont représentés par des croix dans les cases à l’intersection de la ligne de la première composante et de la colonne de la seconde composante ;

*Exemple de représentation matricielle*.
.	Bernard	Antoine	Paul	Charles
Lucie	X	X	X	.
Béatrice	.	X	.	.
Delphine	.	.	.	.
Alice	X	.	X	.

Exemple de représentation graphique.

graphique, avec un axe horizontal dont les points représentent les éléments de l’ensemble de départ, et un axe vertical dont les points représentent les éléments de l’ensemble d’arrivée. Les couples sont représentés par les points à l’intersection de la ligne verticale coupant l’axe horizontal à l’emplacement de la première composante, et de la ligne horizontale coupant l’axe vertical à l’emplacement de la seconde composante. Traditionnellement, le nuage des points du graphe se situe au-dessus et à droite des axes.

Les deux dernières représentations obligent par nature à ordonner les éléments des ensembles de départ et d'arrivée. Si ces ensembles sont déjà ordonnés, on respecte leur ordre, sinon n'importe quel ordre peut être choisi, il n'est pas significatif pour la correspondance elle-même. Dans tous les cas, la diagonale principale de la représentation désigne l'ensemble des couples du produit cartésien de l'ensemble de départ par l'ensemble d'arrivée dont les deux composantes ont le même numéro d'ordre. Si les ensembles de départ et d'arrivée sont un même ensemble E, le même ordre est habituellement utilisé pour les éléments de départ et d'arrivée; la diagonale principale de la représentation se confond alors avec la diagonale de E, c'est-à-dire le graphe de l'identité de E.

Relations n-aires

Notion d'arité

L'ensemble de départ d'une correspondance peut être un produit cartésien. Le graphe d'une telle correspondance n'est plus un ensemble de couples, mais plutôt de n-uplets. La correspondance est alors dite relation d'arité n ou relation n-aire, c'est-à-dire :

binaire, si n = 2 (correspondances de A dans B);
ternaire, si n = 3 (correspondances de A×B dans C);
quaternaire, si n = 4 (correspondances de A×B×C dans D);
quinaire, si n = 5 (correspondances de A×B×C×D dans E);
...

Toutefois, ainsi que nous l'avons vu dans l'exemple de l'addition, cette définition de l'arité est ambiguë : le nombre d'arguments de la correspondance peut varier suivant le point de vue que l'on adopte; son arité aussi, par conséquence. L'arité définie ci-dessus n'est donc pas une propriété intrinsèque des correspondances, et ne permet pas de les classer. Ainsi, plutôt que d'écrire que telle correspondance est n-aire, ce qui suggère qu'il s'agit là d'une propriété propre à cette correspondance, peut-être vaudrait-il mieux écrire par exemple que la correspondance est vue comme n-aire.

Par ailleurs, dans la plupart des cas, il est possible de définir une arité intrinsèque à la correspondance. Pour cela, l'idée initiale est de remarquer que seul l'ensemble de départ est susceptible d'être décomposé en produit cartésien; l'ensemble d'arrivée, même s'il est effectivement un produit cartésien, est toujours considéré en bloc, et peut ainsi être pris comme référence; le nombre de fois où il apparait en facteur cartésien de l'ensemble de départ détermine alors l'arité. Si nous reprenons l'exemple de l'addition dans IR :

l'ensemble d'arrivée (l'ensemble de référence) est l'ensemble IR des réels,
l'ensemble de départ en est le carré cartésien, IR × IR;
le graphe de l'addition est ainsi constitué de triplets de réels,
et l'addition est donc une relation intrinsèquement ternaire (mais il demeure possible de la voir comme binaire...)

Relations internes, externes et scalaires

En pratique, la plupart des correspondances intéressantes peuvent être rangées dans deux grandes classes:

d'une part, celle des correspondances où n'intervient en fait qu'un seul ensemble de base A, qui se confond alors avec l'ensemble d'arrivée; l'ensemble de départ est alors une puissance cartésienne de cet ensemble A. Ces correspondances sont appelées :

« relations n-aires INTERNES à l'ensemble A »,
ou « relations n-aires dans A »,
ou encore « relations n-aires sur A ».

Ce sont en fait les correspondances de A^n-1 dans A, donc de la forme ( A×A×...×A, A, $Γ$ ).

d'autre part, celle, dérivée de la précédente, où, à côté de l'ensemble de base A et de ses puissances cartésiennes, intervient un ensemble S de scalaires dits aussi opérateurs; toutefois, on ne retient en fait dans cette classe que les correspondances conformes aux trois cas de figure suivants :

¤ les correspondances appelées :

« relations n-aires EXTERNES A GAUCHE à l'ensemble A depuis un ensemble S »,
ou « relations n-aires externes à l'ensemble A depuis un ensemble S à gauche »,
ou encore « relations n-aires dans A à opérateurs à gauche dans S ».
ou encore « relations n-aires sur A à scalaires à gauche dans S ».

Ce sont en fait les correspondances de S×A^n-2 dans A, donc de la forme ( S×A×A×...×A, A, $Γ$ ).

¤ les correspondances appelées :

« relations n-aires EXTERNES A DROITE à l'ensemble A depuis un ensemble S »,
ou « relations n-aires externes à l'ensemble A depuis un ensemble S à droite »,
ou encore « relations n-aires dans A à opérateurs à droite dans S ».
ou encore « relations n-aires sur A à scalaires à droite dans S ».

Ce sont en fait les correspondances de A^n-2×S dans A, donc de la forme ( A×A×...×A×S, A, $Γ$ ).

¤ les correspondances appelées :

« relations n-aires SCALAIRES dans A à valeurs dans S »,
ou « relations n-aires scalaires de A vers S ».

Ce sont en fait les correspondances de A^n-1 dans S, donc de la forme ( A×A×...×A, S, $Γ$ ).

Pour que ces définitions soient cohérentes, S ne doit pas être un produit cartésien où A figure ( le cas S = A est toutefois toléré par abus de langage : une relation interne est alors vue comme une relation externe dans A à opérateurs dans A lui-même ).

Les correspondances de S dans A où S n'est ni A, ni un produit cartésien comportant A ne relèvent pas de ces définitions, mais peuvent être vues comme relations externes dans A au cas limite où n = 2. S est alors l'ensemble des opérateurs ( sans préciser à gauche ou à droite, les deux se confondant ).

A part ce cas, s’il n’est pas précisé si une relation externe est à gauche ou à droite, et si le contexte ne permet pas de lever l’ambiguïté, alors elle est à gauche. De même, s’il n’est pas précisé si une relation est interne, externe ou générale, et si le contexte ne permet pas de lever l’ambiguïté, alors elle est interne. Pour parler des relations au sens général du terme, il vaudra mieux préciser relation générale, ou employer le terme de correspondance.

Classement suivant l'arité intrinsèque

D'après ce qui précède, une relation a toujours une arité intrinsèque au moins égale à 2. Nous pouvons ainsi distinguer :

Les relations binaires, d'arité 2 ; en particulier :

une relation binaire 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 c'est une correspondance de E dans E, c'est-à-dire si :

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

une relation binaire externe, est une correspondance d’un ensemble S dans un ensemble E, où S n’est pas un produit cartésien dont E soit une composante; en d’autres termes, si E et S sont deux ensembles, $\mathfrak{R}$ est une relation binaire externe de S dans E si et seulement si :

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

Les relations ternaires, d'arité 3 ; en particulier :

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 à gauche (resp. à droite) 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 (resp. de l'ensemble d'arrivée par un ensemble S de scalaires); en d’autres termes, si E et S sont deux ensembles :, $\mathfrak{R}$ est une relation ternaire externe dans E à opérateurs dans S :

- à gauche si et seulement si : $\exists\ G\ ,\ ( \mathfrak{R} = ( S \times E , E , G \, ) ) \wedge ( G \subseteq S \times E^{\, 2 } \, ) \,$

- à droite si et seulement si : $\exists\ G\ ,\ ( \mathfrak{R} = ( E \times S , E , G \, ) ) \wedge ( G \subseteq E \times S \times E \, ) \,$

une relation ternaire scalaire est une correspondance dont l'ensemble de départ est un carré cartésien et l'ensemble d'arrivée joue le rôle d'un ensemble de scalaires; en d'autres termes, si E et S sont deux ensembles, $\mathfrak{R}$ est une relation ternaire scalaire dans E à valeurs dans S si et seulement si :

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

Encore une fois, l’ensemble S ci-dessus ne doit pas être un produit cartésien dont l’ensemble d’arrivée E soit une composante.

En pratique, on considère rarement des relations d'arité supérieure, car elles peuvent toujours se décomposer en relations binaires ou ternaires.

Exemples

L’égalité et l’inclusion sont des relations binaires dans la classe des ensembles.

La réunion, l’intersection, la différence et la différence symétrique sont des relations ternaires internes dans la classe des ensembles.

Si A, B et C sont trois ensembles disjoints deux à deux, et dont aucun n'est un produit cartésien comportant l'un des deux autres en facteur :

toute relation de A dans A est binaire interne ;
toute relation de A dans B est binaire externe ;
toute relation de A x A dans A est ternaire interne ;
toute relation de A x A dans B est ternaire scalaire ;
toute relation de A x B dans A est ternaire externe à droite ;
toute relation de A x B dans B est ternaire externe à gauche ;
et enfin, toute relation de A x B dans C est binaire externe ( pour l'arité intrinsèque, la référence est l'ensemble d'arrivée ! ).

Fonctions

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

« y correspond à x par $\mathfrak{C}$ » peut se noter :

« ( x , y ) ∈ G( $\mathfrak{C}$ ) » (notation ensembliste)
« ( x , y ) $\mathfrak{C}$ » (notation relationnelle postfixée)
« $\mathfrak{C}$ ( x , y ) » (notation relationnelle préfixée)
« x $\mathfrak{C}$ y » (notation relationnelle infixée)

Cette dernière notation est, sauf cas particulier, la plus pratique et par conséquent la plus utilisée.

L' ensemble-image d'une correspondance, noté habituellement « $Im\mathfrak{C}$ », est l'ensemble formé par les images de tous les éléments de l’ensemble de départ de cette correspondance. Un abus de langage courant consiste à qualifier cet ensemble d'« image » de la correspondance, mais cela peut entraîner une confusion dans le cas où la correspondance est elle-même élément d’un autre ensemble, à partir duquel une autre correspondance est bâtie.

Symétriquement, l’ ensemble-antécédent d’une correspondance, noté habituellement « $Ant\mathfrak{C}$ », est l'ensemble formé par les antécédents de tous les éléments de l’ensemble d’arrivée de cette correspondance. L’ensemble-antécédent est parfois qualifié par abus de langage d'« antécédent » ou de « préimage » de la correspondance, mais, comme dans le paragraphe précédent, cela peut entraîner des confusions dans certains cas particuliers. L’ensemble-antécédent peut aussi être nommé « domaine de définition » de la correspondance, et il est alors noté « $Dom\mathfrak{C}$ » ou « $D\mathfrak{C}$ », mais cette dernière appellation est plutôt réservée aux fonctions (voir ci-après).

Fonctions, applications et bijections

Propriétés liées au nombre de correspondants

Une correspondance peut présenter quatre propriétés fondamentales liées au nombre d'antécédents ou d'images associés à chaque élément. Ces propriétés sont analogues entre elles, mais indépendantes les unes des autres.

Ainsi, une correspondance peut être :

fonctionnelle : tout élément de l'ensemble de départ a au plus une image :

$\forall\, ( x , y_1 , y_2 ) \in E \times F^{\, 2} , ( x \,\mathfrak{C}\, y_1 \wedge x \,\mathfrak{C}\, y_2 ) \Rightarrow ( y_1 = y_2 )$

applicative : tout élément de l'ensemble de départ a au moins une image :

$\forall\, x \in E , \exists\, y \in F \ / \ x \,\mathfrak{C}\, y \,$

injective : tout élément de l'ensemble d'arrivée a au plus un antécédent :

$\forall\, ( x_1 , x_2 , y ) \in E^{\, 2} \times F , ( x_1 \,\mathfrak{C}\, y \wedge x_2 \,\mathfrak{C}\, y ) \Rightarrow ( x_1 = x_2 ) \,$

surjective : tout élément de l'ensemble d'arrivée a au moins un antécédent :

$\forall\, y \in F , \exists\, x \in E \ / \ x \,\mathfrak{C}\, y \,$ .

Note : sur ces appellations, voir la page de discussion associée à l'article (onglet « discussion » en haut de l'article).

Définitions équivalentes: Une correspondance est applicative si et seulement si son ensemble-antécédent se confond avec son ensemble de départ, c'est-à-dire si : $\ Ant\mathfrak{C} = E$ .; Une correspondance est surjective si et seulement si son ensemble-image se confond avec son ensemble d'arrivée, c'est-à-dire si : $\ Im\mathfrak{C} = F$ .

Propriétés dérivées

En combinant ces quatre propriétés de base, nous obtenons a priori 16 sortes de correspondances, mais seules 9 d'entre elles ont un qualificatif. 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 élément de l'ensemble de départ
	injective	surjective	bijective	... un antécédent par élément de l'ensemble d'arrivée
	bifonctionnelle	biapplicative	biunivoque	... une image par élément de départ et un antécédent par élément d'arrivée

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. Chaque élément de départ a au plus une image. On peut donc parler de son image sans ambiguïté, et la désigner par un symbole, d'habitude « R( x ) » si la fonction est notée « R ». Cela permet de remplacer la notation relationnelle « x R y » par la notation fonctionnelle « y = R( x ) » plus pratique ;

Une application est une fonction applicative. C’est donc aussi une correspondance fonctionnelle et applicative, c’est-à-dire une correspondance univoque. Comme elle est applicative, son domaine de définition se confond avec son ensemble de départ ;

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. Comme elle est surjective, son image n'est autre que l'ensemble d'arrivée tout entier ;

Une bijection est une application bijective. C’est donc une correspondance fonctionnelle, applicative, injective et surjective, c’est-à-dire une correspondance biunivoque.

Attention !: Une correspondance applicative (respectivement injective, surjective, bijective) n’est pas en général une application (respectivement une injection, une surjection, une bijection).; De même, une fonction injective (respectivement surjective, bijective) n’est pas en général une injection (respectivement une surjection, une bijection).

Correspondance réciproque

Les notions d’image et d’antécédent sont duales. Échanger leur rôle revient à échanger entre elles les composantes de chaque couple du graphe, donc à remplacer chaque couple ( x , y ) par son couple réciproque ( y , x ).

Le graphe réciproque d’un graphe $G$ , noté « $G - 1$ », est le graphe résultant d’un tel échange :

$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} = \left( F , E , G^{-1} \right)$

La réciproque de la réciproque d’une correspondance n’est autre que cette correspondance :

$\left( \mathfrak{C}^{-1} \right)^{-1} = \mathfrak{C}$

Il suffit de lire le tableau des combinaisons des propriétés de base des correspondances (voir plus haut), en échangeant le rôle des images et des antécédents, pour obtenir les propriétés des réciproques. Ainsi :

La réciproque d’une fonction est une correspondance injective. 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, c'est-à-dire d'une correspondance univoque, est une correspondance bijective. Inversement, pour que la réciproque d’une correspondance soit une application, il faut et il suffit que cette correspondance soit 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 ;
Enfin, la réciproque d’une bijection, c'est-à-dire d'une correspondance biunivoque, est une bijection.

La représentation d'une correspondance réciproque se déduit simplement de celle de la correspondance de départ:

pour une représentation sagittale, en changeant le sens des flèches;
pour une représentation matricielle, en échangeant lignes et colonnes et en prenant la matrice symétrique par rapport à la diagonale principale;
pour une représentation graphique, en échangeant les axes et en prenant le symétrique du graphique par rapport à la diagonale principale.

Classement des correspondances

*Tableau récapitulatif des principaux croisements entre relations et fonctions*
Correspondances	Fonctions	Applications	Bijections
Relations binaires internes	Opérations unaires	Transformations	Permutations (**)
Relations ternaires internes	Opérations binaires internes	Lois (binaires) internes	(***)
Relations ternaires externes (*)	Opérations binaires externes (*)	Lois (binaires) externes (*)	.
Relations ternaires scalaires	Opérations binaires scalaires	Lois (binaires) scalaires	.

Remarques: (*) A gauche ou à droite.; (**) Dans un ensemble fini ou dénombrable.; (***) 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.

Nous retrouvons dans ce tableau les deux familles de notions définies plus haut, relations et fonctions, et leurs combinaisons :

Une transformation dans un ensemble est une application de cet ensemble dans lui-même, donc une relation binaire dans cet ensemble ; les transformations sont parfois qualifiées de lois unaires ;
Une permutation dans un ensemble fini ou dénombrable est une bijection de cet ensemble dans lui-même, donc une relation binaire dans cet ensemble. C’est donc un cas particulier de transformation ;
Une opération est une correspondance qui est à la fois une relation interne, externe ou scalaire, et une fonction ; l'arité d'une opération est usuellement définie comme son nombre d'opérandes, mais d'une part, elle diffère alors d'une unité de l'arité des relations (l'une comptabilise l'ensemble d'arrivée, l'autre pas) et, d'autre part, là encore, le nombre d'opérandes est une question de point de vue sur l'opération, pas quelque chose qui lui est propre ;
Une loi de composition (appellation souvent abrégée en loi) est une correspondance qui est à la fois une relation interne, externe ou scalaire, et une application. Les lois sont donc des opérations particulières.

Ainsi, par exemple, les « quatre opérations » de notre enfance (addition, soustraction, multiplication et division) sont effectivement des opérations internes dans IN, ensemble des entiers naturels, mais seules l’addition et la multiplication y sont des lois de composition.

Voir aussi

Portail de la logique
Portail des mathématiques

Ce document provient de « Correspondance et relation ».

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

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Graphe d'une relation de Wikipédia en français (auteurs)

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

Regardez d'autres dictionnaires:

Graphe d'une chaîne de Markov — et classification des états Le graphe d une chaîne de Markov et la classification des états sont des notions de la théorie des graphes utilisées en calcul des probabilités. Sommaire 1 Graphe d une chaîne de Markov 2 Classification des états … Wikipédia en Français
Graphe D'une Fonction — Pour les articles homonymes, voir graphe. Graphe d une fonction … Wikipédia en Français
Graphe d'une chaîne de Markov et classification des états — Le graphe d une chaîne de Markov et la classification des états sont des notions de la théorie des graphes utilisées en calcul des probabilités. Sommaire 1 Graphe d une chaîne de Markov 2 Classification des états 3 Lexi … Wikipédia en Français
Graphe d'une fonction — Pour les articles homonymes, voir graphe. Graphe d une fonction … Wikipédia en Français
graphe — [ graf ] n. m. • 1926; du gr. graphein « écrire » ♦ Math., log. Ensemble des couples d éléments vérifiant une relation donnée. Diagramme représentant le graphe d une relation. Théorie des graphes. Représentation graphique d une fonction. ● graphe … Encyclopédie Universelle
Relation binaire — En mathématiques, une relation binaire entre deux ensembles E et F (ou simplement relation entre E et F) est caractérisée par un sous ensemble du produit cartésien E × F, soit une collection de couples dont la première composante est dans E et la … Wikipédia en Français
Relation antisymétrique — Relation binaire Une relation binaire est un concept mathématique qui systématise des notions comme « ... est supérieur ou égal à ... » en arithmétique, ou « ... est élément de l’ensemble ... » en théorie des ensembles. C’est… … Wikipédia en Français
Graphe Conceptuel — Un graphe conceptuel est un outil symbolique utilisé dans la théorie des graphes conceptuels. Développée par Sowa (1984), cette théorie est un formalisme général de représentation de connaissances fondé sur la logique ; elle s inscrit dans… … Wikipédia en Français
Graphe De Sowa — Graphe conceptuel Un graphe conceptuel est un outil symbolique utilisé dans la théorie des graphes conceptuels. Développée par Sowa (1984), cette théorie est un formalisme général de représentation de connaissances fondé sur la logique ;… … Wikipédia en Français
Graphe de Sowa — Graphe conceptuel Un graphe conceptuel est un outil symbolique utilisé dans la théorie des graphes conceptuels. Développée par Sowa (1984), cette théorie est un formalisme général de représentation de connaissances fondé sur la logique ;… … Wikipédia en Français

Dictionnaires et Encyclopédies sur 'Academic'

Graphe d'une relation

Correspondance et relation

Sommaire

Graphe et correspondance