Correspondance et relation

En algèbre abstraite, la notion 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 « Cecile connaît David »... On peut donc voir une relation comme des fils reliant divers éléments d’un ensemble.

Cette notion peut être généralisée 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. 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 = \{ Alice, Bernard \}\,$

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

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

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 = \{ Alice, Bernard, 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 , aime ) \quad et \quad ( Q \times Q , aime ) \,$ ,

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

$( P , P , aime ) \quad et \quad ( Q , Q , aime ) \,$ .

Cette façon de procéder comporte toutefois encore 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 ) \quad et \quad \dot\cup ( Q , Q , aime ) \,$ ,

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

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

Notes préliminaires

Les définitions suivantes demeurent valides 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.

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 :

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

Egalité 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.

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 dans E dont le graphe est la diagonale de E est appelée identité de E, et notée habituellement « $Id_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 $\mathbb{R} \times \mathbb{R} \,$ dans $\mathbb{R} \,$ . 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 :

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;

Image manquante
Relationbinaire.png
exemple de représentation sagittale

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	.

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.

Opérations sur les correspondances

Voir l’article « Opération sur des correspondances »

Types de relations

Relations internes et externes

Une relation interne ou relation dans un ensemble ou relation sur un ensemble est une correspondance dont l’ensemble de départ est une puissance cartésienne de l’ensemble d’arrivée.

Une relation externe est une correspondance dont l’ensemble de départ est le produit cartésien d’un ensemble dit de scalaires ou d’opérateurs par une puissance cartésienne de l’ensemble d’arrivée.

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

- $\mathfrak{R}$ est une relation dans E, donc interne ssi :

$\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 sur E à opérateurs à gauche dans S, donc externe à gauche ssi:

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

- $\mathfrak{R}$ est une relation sur E à opérateurs à droite dans S, donc externe à droite ssi:

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

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

Les correspondances de S dans E où S n'est ni E, ni un produit cartésien comportant E ne relèvent pas de ces définitions, mais peuvent être vues comme relations externes dans E 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.

Arité d’une relation

Le nombre n intervenant dans les définitions précédentes est appelé arité de la relation. Celle-ci est dite n-aire; ainsi :

une relation binaire interne, d’arité 2 , 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 ssi 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, encore d'arité 2, 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 ssi :

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

une relation ternaire interne, d'arité 3, 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 ssi :

$\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 ssi : $\exists\ G\ /\ ( \mathfrak{R} = ( S \times E , E , G \, ) ) \wedge ( G \subseteq S \times E^{\, 2 } \, ) \,$

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

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

Une relation scalaire est une correspondance d'un ensemble E² dans un ensemble S ; c'est donc une relation binaire externe dont l'ensemble de départ est un carré cartésien.

Notion de fonction

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 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. Il est noté habituellement « $Im\mathfrak{C}$ ». 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. Il est noté habituellement « $Ant\mathfrak{C}$ ». L’ensemble-antécédent est aussi nommé « domaine de définition » de la correspondance, et alors noté « $Dom\mathfrak{C}$ » ou « $D\mathfrak{C}$ », mais cette dernière appellation est plutôt réservée aux fonctions (voir plus loin).

Correspondance réciproque

Nous pouvons remarquer que les notions d’image et d’antécédent sont duales. Echanger 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} = ( F , E , G^{-1} )$

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

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

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

Fonctions, applications et bijections

Propriétés de base

Une correspondance peut avoir quatre propriétés de base indépendantes les unes des autres ; elle 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 ) \,$

ou 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 \,$ .

Notes:

une correspondance est applicative si et seulement si : $\ Ant\mathfrak{C} = E$ ;

une correspondance est surjective si et seulement si : $\ Im\mathfrak{C} = F$ .

Définitions

En combinant ces quatre propriétés de base, nous obtenons a priori seize types de correspondances, mais seules neuf 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 ;
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;

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

Réciproques

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; 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;

- et enfin, la réciproque d’une bijection, c'est-à-dire d'une correspondance biunivoque, est une bijection.

Principales sortes de correspondances

Tableau récapitulatif des croisements entre relations et fonctions
Correspondances	Relations binaires internes	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	(**)	.

Remarques :

(*) à gauche ou à droite

(**) 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;

- une permutation dans un ensemble est une bijection d’un 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 ternaire et une fonction;

- une loi de composition ( appellation souvent abrégée en loi ) est une correspondance qui est à la fois une relation ternaire et une application; les lois sont donc des opérations particulières.

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