Composition des relations - Composition of relations

Dans les mathématiques des relations binaires , la composition des relations est la formation d'une nouvelle relation binaire R  ; S à partir de deux relations binaires données R et S . Dans le calcul des relations , la composition des relations est appelée multiplication relative , et son résultat est appelé produit relatif . La composition de fonctions est le cas particulier de composition de relations où toutes les relations impliquées sont des fonctions .

Les mots oncle et tante indiquent une relation composée : pour qu'une personne soit un oncle, il faut qu'elle soit le frère d'un parent (ou une sœur pour une tante). En logique algébrique, il est dit que la relation d'Oncle ( xUz ) est la composition de relations "est un frère de" ( xBy ) et "est un parent de" ( yPz ).

${\displaystyle U=BP\quad \equiv \quad xByPz\iff xUz.}$

À partir d' Augustus De Morgan , la forme traditionnelle de raisonnement par syllogisme a été subsumée par les expressions logiques relationnelles et leur composition.

Définition

Si et sont deux relations binaires, alors leur composition est la relation ${\displaystyle R\subseteq X\times Y}$${\displaystyle S\subseteq Y\times Z}$${\displaystyle R;S}$

${\displaystyle R;S=\{(x,z)\in X\times Z\mid \existe y\in Y:(x,y)\in R\land (y,z)\in S\}. }$

En d'autres termes, est défini par la règle qui dit si et seulement s'il existe un élément tel que (c'est -à- dire et ). ${\displaystyle R;S\subseteq X\times Z}$${\style d'affichage (x,z)\dans R;S}$${\displaystyle y\in Y}$${\style d'affichage x\,R\,y\,S\,z}$${\style d'affichage (x,y)\dans R}$${\style d'affichage (y,z)\dans S}$

Variations de notation

Le point-virgule comme notation infixe pour la composition des relations remonte au manuel d' Ernst Schroder de 1895. Gunther Schmidt a renouvelé l'utilisation du point-virgule, en particulier dans Relational Mathematics (2011). L'utilisation du point-virgule coïncide avec la notation pour la composition de fonctions utilisée (principalement par les informaticiens) dans la théorie des catégories , ainsi que la notation pour la conjonction dynamique au sein de la sémantique dynamique linguistique .

Un petit cercle a été utilisé pour la notation infixe de la composition des relations par John M. Howie dans ses livres sur les semi - groupes de relations. Cependant, le petit cercle est largement utilisé pour représenter la composition de fonctions qui inverse la séquence de texte de la séquence d'opérations. Le petit cercle a été utilisé dans les pages d'introduction de Graphs and Relations jusqu'à ce qu'il soit abandonné au profit de la juxtaposition (pas de notation infixe). La juxtaposition est couramment utilisée en algèbre pour signifier la multiplication, elle peut aussi signifier la multiplication relative. ${\style d'affichage (R\circ S)}$ ${\style d'affichage g(f(x))=(g\circ f)(x)}$ ${\style d'affichage (RS)}$

De plus, avec la notation circulaire, des indices peuvent être utilisés. Certains auteurs préfèrent écrire et explicitement quand c'est nécessaire, selon que la relation de gauche ou de droite est la première appliquée. Une autre variation rencontrée en informatique est la notation Z : est utilisée pour désigner la composition traditionnelle (à droite), mais ⨾ (un gros point-virgule ouvert avec le point de code Unicode +2A3E ) désigne la composition à gauche. ${\displaystyle \circ _{l}}$${\displaystyle \circ _{r}}$${\style d'affichage \circ }$

Les relations binaires sont parfois considérées comme les morphismes d'une catégorie Rel qui a les ensembles comme objets. En Rel , la composition de morphismes est exactement la composition de relations telle que définie ci-dessus. La catégorie Ensemble d'ensembles est une sous-catégorie de Rel qui a les mêmes objets mais moins de morphismes. ${\displaystyle R\subseteq X\times Y}$${\displaystyle R\colon X\à Y}$

Propriétés

• La composition des relations est associative :${\displaystyle R;(S;T)=(R;S);T.}$
• La relation inverse de R  ; S est ( R  ; S ) ^T = S ^T  ; R ^T . Cette propriété fait de l'ensemble de toutes les relations binaires sur un ensemble un semi - groupe avec involution .
• La composition de fonctions (partielles) (c'est-à-dire de relations fonctionnelles) est à nouveau une fonction (partielle).
• Si R et S sont injectifs , alors R  ; S est injectif, ce qui n'implique à l'inverse que l'injectivité de R .
• Si R et S sont surjectifs , alors R  ; S est surjectif, ce qui n'implique à l'inverse que la surjectivité de S .
• L'ensemble des relations binaires sur un ensemble X (c'est-à-dire les relations de X à X ) avec la composition des relations (gauche ou droite) forme un monoïde avec zéro, où la carte d'identité sur X est l' élément neutre et l'ensemble vide est le zéro élément .

Composition en termes de matrices

Les relations binaires finies sont représentées par des matrices logiques . Les entrées de ces matrices sont soit zéro, soit un, selon que la relation représentée est fausse ou vraie pour la ligne et la colonne correspondant aux objets comparés. Travailler avec de telles matrices implique l'arithmétique booléenne avec 1 + 1 = 1 et 1 × 1 = 1. Une entrée dans le produit matriciel de deux matrices logiques sera 1, alors, seulement si la ligne et la colonne multipliées ont un correspondant 1. Ainsi la matrice logique d'une composition de relations peut être trouvée en calculant le produit matriciel des matrices représentant les facteurs de la composition. "Les matrices constituent une méthode de calcul des conclusions traditionnellement tirées au moyen de syllogismes et sorites hypothétiques."

Relations hétérogènes

Considérons une relation hétérogène R ⊆ A × B ; c'est-à-dire où A et B sont des ensembles distincts. Alors en utilisant la composition de la relation R avec sa réciproque R ^T , il existe des relations homogènes RR ^T (sur A ) et R ^T R (sur B ).

Si ∀ x ∈ A ∃ y ∈ B xRy (c'est-à-dire que R est une relation (gauche-)totale ), alors ∀ x xRR ^T x de sorte que RR ^T est une relation réflexive ou I ⊆ RR ^T où I est la relation d'identité { x I x  : x ∈ A }. De même, si R est une relation surjective alors

R ^T R I = { x I x  : x ∈ B }. Dans ce cas , R ⊆ RR ^T R . L'inclusion inverse se produit pour une relation difonctionnelle .

La composition permet de distinguer des relations de type Ferrer, qui satisfont${\displaystyle {\bar {R}}^{\textsf {T}}R}$${\displaystyle R{\bar {R}}^{\textsf {T}}R=R.}$

Exemple

Soit A = { France, Allemagne, Italie, Suisse } et B = { Français, Allemand, Italien } avec la relation R donnée par aRb lorsque b est une langue nationale de a . Puisque A et B sont tous deux finis, R peut être représenté par une matrice logique , en supposant que les lignes (de haut en bas) et les colonnes (de gauche à droite) sont classées par ordre alphabétique :

${\displaystyle {\begin{pmatrix}1&0&0\\0&1&0\\0&0&1\\1&1&1\end{pmatrix}}.}$

La relation inverse R ^T correspond à la matrice transposée , et la relation composition correspond au produit matriciel lorsque la sommation est mise en œuvre par disjonction logique . Il s'avère que la matrice 3 × 3 contient un 1 à chaque position, tandis que le produit matriciel inversé se calcule comme suit : ${\displaystyle R^{\textsf {T}};R}$ ${\displaystyle R^{\textsf {T}}R}$${\displaystyle R^{\textsf {T}}R}$

${\displaystyle RR^{\textsf {T}}={\begin{pmatrix}1&0&0&1\\0&1&0&1\\0&0&1&1\\1&1&1&1\end{pmatrix}}.}$

Cette matrice est symétrique, et représente une relation homogène sur A .

En conséquence, est la relation universelle sur B , donc deux langues partagent une nation où elles sont toutes deux parlées (en fait: la Suisse). Vice versa, la question de savoir si deux nations données partagent une langue peut être répondue en utilisant . ${\displaystyle R^{\textsf {T}};R}$${\displaystyle R;R^{\textsf {T}}}$

Règles de Schröder

Pour un ensemble donné V , la collection de toutes les relations binaires sur V forme un treillis booléen ordonné par inclusion (⊆). Rappelons que la complémentation inverse l'inclusion : Dans le calcul des relations, il est courant de représenter le complément d'un ensemble par une barre supérieure :${\displaystyle A\sous-ensemble B\implique B^{\complément }\sous-ensemble A^{\complément }.}$${\displaystyle {\bar {A}}=A^{\complément }.}$

Si S est une relation binaire, représentons la relation inverse , aussi appelée la transposée . Alors les règles de Schröder sont ${\displaystyle S^{\textsf {T}}}$

${\displaystyle QR\subseteq S\quad \equiv \quad Q^{\textsf {T}}{\bar {S}}\subseteq {\bar {R}}\quad \equiv \quad {\bar {S} }R^{\textsf {T}}\subseteq {\bar {Q}}.}$

Verbalement, une équivalence peut être obtenue à partir d'une autre : sélectionner le premier ou le deuxième facteur et le transposer ; puis compléter les deux autres relations et les permuter.

Bien que cette transformation d'une inclusion d'une composition de relations ait été détaillée par Ernst Schröder , en fait Augustus De Morgan a d' abord articulé la transformation en tant que théorème K en 1860. Il a écrit

${\displaystyle LM\subseteq N\implies {\bar {N}}M^{\textsf {T}}\subseteq {\bar {L}}.}$

Avec les règles de Schröder et la complémentation, on peut résoudre une relation inconnue X dans des inclusions relationnelles telles que

${\displaystyle RX\subseteq S\quad {\text{and}}\quad XR\subseteq S.}$

Par exemple, par la règle de Schröder et la complémentation donne ce qui est appelé le résidu gauche de S par R . ${\displaystyle RX\subseteq S\implique R^{\textsf {T}}{\bar {S}}\subseteq {\bar {X}},}$${\displaystyle X\subseteq {\overline {R^{\textsf {T}}{\bar {S}}}},}$

Quotients

Tout comme la composition des relations est un type de multiplication aboutissant à un produit, certaines compositions se comparent à la division et produisent des quotients. Trois quotients sont présentés ici : résiduel gauche, résiduel droit et quotient symétrique. Le résidu de gauche de deux relations est défini en supposant qu'elles ont le même domaine (source), et le résidu de droite suppose le même codomaine (plage, cible). Le quotient symétrique suppose que deux relations partagent un domaine et un codomaine.

Définitions :

• Résidu restant : ${\displaystyle A\backslash B\mathrel {:=} {\overline {A^{\textsf {T}}{\bar {B}}}}}$
• Résidu droit : ${\displaystyle D/C\mathrel {:=} {\overline {{\bar {D}}C^{\textsf {T}}}}}$
• Quotient symétrique : ${\displaystyle \operatorname {syq} (E,F)\mathrel {:=} {\overline {E^{\textsf {T}}{\bar {F}}}}\cap {\overline {{\bar {E}}^{\textsf {T}}F}}}$

En utilisant les règles de Schröder, AX ⊆ B est équivalent à X ⊆ A B . Ainsi, le résidu gauche est la plus grande relation satisfaisant AX ⊆ B . De même, l'inclusion YC ⊆ D est équivalent à Y ⊆ D / C , et le droit résiduel est la plus grande relation avec la satisfaction YC ⊆ D . ${\style d'affichage \ barre oblique inverse }$

On peut pratiquer la logique des résidus avec Sudoku .

Join : une autre forme de composition

Un opérateur fourche (<) a été introduit pour fusionner deux relations c : H → A et d : H → B en c (<) d : H → A × B . La construction dépend des projections a : A × B → A et b : A × B → B , entendues comme relations, c'est-à-dire qu'il existe des relations inverses a ^T et b ^T . Alors la fourchette de c et d est donnée par

${\displaystyle c(<)d\mathrel {:=} c;a^{\textsf {T}}\cap \ d;b^{\textsf {T}}.}$

Une autre forme de composition de relations, qui s'applique aux relations générales n- places pour n 2, est l' opération de jointure de l' algèbre relationnelle . La composition habituelle de deux relations binaires telles que définies ici peut être obtenue en prenant leur jointure, conduisant à une relation ternaire, suivie d'une projection qui supprime la composante médiane. Par exemple, dans le langage de requête SQL, il existe l'opération Join (SQL) .

Voir également

• Composition démoniaque
• L'ami d'un ami

Remarques

Les références

• M. Kilp, U. Knauer, AV Mikhalev (2000) Monoids, Acts and Categories with Applications to Wreath Products and Graphs , De Gruyter Expositions in Mathematics vol. 29, Walter de Gruyter , ISBN  3-11-015248-7 .