Une relation binaire ou un mappage multivalué entre éléments de deux ensembles qui associe des éléments sans exiger l'unicité d'une application ; formellement un sous-ensemble R ⊆ A × B ou une règle qui affecte à chaque a ∈ A un sous-ensemble R(a) ⊆ B.

Principe

Décrire les connexions par les appariements autorisés plutôt que par une affectation à valeur unique : l'appartenance aux paires ordonnées détermine la relation et ses opérations algébriques (composition, inverse, restriction).

Démonstration

Soient A des personnes et B des numéros de téléphone ; la correspondance R ⊆ A × B relie une personne à tous les numéros qu'elle utilise, donc R(a) est l'ensemble des numéros de cette personne. La composition de R avec une relation S des numéros vers des opérateurs indique quels opérateurs sont utilisés par quelles personnes.

Mauvaise application

Considérer une correspondance générale comme une fonction en supposant que chaque a ∈ A possède au plus un b ∈ B ; cela conduit à des erreurs sur l'inversibilité, l'unicité ou la résolution des appariements.

Conséquence

Modélise naturellement les relations plusieurs-à-plusieurs ; permet des opérations comme la relation inverse et la composition relationnelle, et peut représenter des contraintes fondamentalement nondéterministes.

Inversion

La notion inverse est une fonction à valeur unique ou une bijection : restreindre une correspondance au graphe d'une fonction ou choisir un représentant unique par a la transforme en fonction.

Limite

S'applique à tous ensembles A et B et n'exige pas de structure algébrique ; sont exclues les situations qui requièrent l'unicité (fonctions), les probabilités directionnelles ou les mesures sauf si l'on ajoute une structure.

Tension sémantique

Se heurte à la notion de fonction : les deux mettent en relation domaine et codomaine, mais la fonction impose l'unicité tandis que la correspondance autorise la multiplicité et la nondétermination.

Synthèse

La correspondance est la notion générale d'appariement d'éléments entre ensembles par l'appartenance à des paires ordonnées ou par l'affectation d'ensembles de cibles ; elle généralise les fonctions et utilise l'algèbre relationnelle (inverse, composition) pour exprimer des connexions nondéterministes ou plusieurs-à-plusieurs.