Skład relacji - Composition of relations

W matematyce w stosunkach binarnych The kompozycja stosunków jest formowanie powiązanie binarne R  ; S z dwóch danych relacji binarnych R i S . W rachunku relacji złożenie relacji nazywa się mnożeniem względnym , a jego wynik iloczynem względnym . Składanie funkcji jest szczególnym przypadkiem składania relacji, gdzie wszystkie zaangażowane relacje są funkcjami .

Słowa wujek i ciotka wskazują na złożoną relację: aby osoba była wujkiem, musi być bratem rodzica (lub siostrą dla ciotki). W logice algebraicznej mówi się, że relacja wuja ( xUz ) jest złożeniem relacji „jest bratem” ( xBy ) i „jest rodzicem” ( yPz ).

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

Począwszy od Augusta De Morgana tradycyjna forma rozumowania przez sylogizm została podporządkowana relacyjnym wyrażeniom logicznym i ich kompozycji.

Definicja

Jeśli i są dwiema relacjami binarnymi, to ich złożeniem jest relacja ${\ Displaystyle R \ podseteq X \ razy Y}$${\ Displaystyle S \ podseteq Y \ razy Z}$${\ Displaystyle R; S}$

${\ Displaystyle R; S = \ {(x, z) \ w X \ razy Z \ mid \ istnieje r \ w Y: (x, y) \ w R \ ziemi (y, z) \ w S \}. }$

Innymi słowy, jest zdefiniowany przez regułę, która mówi wtedy i tylko wtedy, gdy istnieje element taki, że (tj. i ). ${\ Displaystyle R; S \ podseteq X \ razy Z}$${\ Displaystyle (x, z) \ w R; S}$${\ Displaystyle y \ w Y}$${\displaystyle x\,R\,y\,S\,z}$${\ Displaystyle (x, y) \ w R}$${\ Displaystyle (y, z) \ w S}$

Odmiany notacyjne

Średnik jako notacja infiksowa do tworzenia relacji pochodzi z podręcznika Ernsta Schrodera z 1895 roku. Gunther Schmidt ponowił użycie średnika, szczególnie w Matematyce relacyjnej (2011). Użycie średnika jest zbieżne z notacją dla kompozycji funkcji stosowaną (głównie przez informatyków) w teorii kategorii , jak również z notacją dynamicznej koniunkcji w dynamicznej semantyce językowej .

Małe kółko zostało użyte do zapisu infiksowego kompozycji relacji przez Johna M. Howiego w jego książkach dotyczących półgrup relacji. Jednak małe kółko jest powszechnie używane do reprezentowania kompozycji funkcji, która odwraca sekwencję tekstu od sekwencji operacji. Małe kółko było używane na wstępnych stronach Graphs and Relations, dopóki nie zostało porzucone na rzecz zestawienia (brak notacji infiksowej). Zestawienie jest powszechnie używane w algebrze do oznaczenia mnożenia, więc może również oznaczać mnożenie względne. ${\ Displaystyle (R\circ S)}$ ${\ Displaystyle g (f (x)) = (g \ circ f) (x)}$ ${\ Displaystyle (RS)}$

Dalej z notacją koła można używać indeksów dolnych. Niektórzy autorzy wolą pisać i wyraźnie, gdy jest to konieczne, w zależności od tego, czy w lewo lub w prawo relacja jest pierwszy zastosowane. Kolejną odmianą spotykaną w informatyce jest notacja Z : jest używana do oznaczenia tradycyjnej (prawej) kompozycji, ale ⨾ (otwarty gruby średnik z punktem kodowym Unicode +2A3E ) oznacza lewą kompozycję. ${\displaystyle \circ _{l}}$${\displaystyle \circ _{r}}$${\displaystyle \circ}$

Relacje binarne są czasami traktowane jako morfizmy w kategorii Rel, która ma zbiory jako obiekty. W Rel złożenie morfizmów jest dokładnie złożeniem relacji, jak zdefiniowano powyżej. Kategoria Zestaw zestawów jest podkategorią Rel, która ma te same obiekty, ale mniej morfizmów. ${\ Displaystyle R \ podseteq X \ razy Y}$${\ Displaystyle R \ dwukropek X \ do Y}$

Nieruchomości

• Kompozycja relacji jest asocjacyjna :${\ Displaystyle R; (S; T) = (R; S); T.}$
• Odwrotna zależność od R  ; S jest ( R  , S ) ^t = S ^{, T}  ; R ^T . Ta właściwość sprawia, że ​​zbiór wszystkich relacji binarnych w zbiorze jest półgrupą z inwolucją .
• Złożenie funkcji (częściowych) (tzn. relacji funkcjonalnych) jest znowu funkcją (częściową).
• Jeśli R i S są iniektywne , to R  ; S jest injektywny, co odwrotnie implikuje tylko injektywność R .
• Jeśli R i S są surjektywne , to R  ; S jest suriektywna, co odwrotnie implikuje tylko suriektywizm S .
• Zbiór relacji binarnych na zbiorze X (tzn. relacje od X do X ) wraz ze złożeniem relacji (lewej lub prawej) tworzy monoid z zerem, gdzie odwzorowanie tożsamości na X jest elementem neutralnym , a zbiór pusty jest zerem element .

Kompozycja pod względem macierzy

Skończone relacje binarne są reprezentowane przez macierze logiczne . Wpisy tych macierzy mają wartość zero lub jeden, w zależności od tego, czy reprezentowana relacja jest fałszem czy prawdą dla wiersza i kolumny odpowiadających porównywanym obiektom. Praca z takimi macierzami obejmuje arytmetykę Boole'a z 1 + 1 = 1 i 1 × 1 = 1. Wpis w iloczynu macierzy dwóch macierzy logicznych będzie wynosił 1, wtedy tylko wtedy, gdy pomnożony wiersz i kolumna mają odpowiadającą 1. Zatem logiczną macierz kompozycji relacji można znaleźć, obliczając iloczyn macierzy macierzy reprezentujących czynniki kompozycji. „Macierze stanowią metodę obliczania wniosków tradycyjnie wyciąganych za pomocą hipotetycznych sylogizmów i sorytów”.

Relacje heterogeniczne

Rozważ heterogeniczną relację R ⊆ A × B ; tj. gdzie A i B są odrębnymi zbiorami. Następnie stosując złożenie relacji R z jej odwrotnością R ^T , zachodzą jednorodne relacje RR ^T (na A ) i R ^T R (na B ).

Jeśli ∀ x ∈ A ∃ y ∈ B xRy (czyli R jest relacją (lewo-)całkowitą ), to ∀ x xRR ^T x tak, że RR ^T jest relacją zwrotną lub I ⊆ RR ^T gdzie I jest relacją identyczności { x I x  : x ∈ A }. Podobnie, jeśli R jest relacją surjektywną, to

R ^T R ⊇ I = { x I x  : x ∈ B }. W takim przypadku R ⊆ RR ^T R . Włączenie przeciwne występuje dla relacji dwufunkcyjnej .

Kompozycja służy do wyodrębnienia relacji typu Ferrera, które spełniają${\ Displaystyle {\ bar {R}} ^ {\ textsf {T}} R}$${\ Displaystyle R {\ bar {R}} ^ {\ textsf {T}} R = R.}$

Przykład

Niech = {Francja, Niemcy, Włochy, Szwajcaria} i B = {francuski, niemiecki, włoski} z relacji R podanych przez ARB gdy b jest język narodowy z . Ponieważ zarówno A, jak i B są skończone, R może być reprezentowane przez macierz logiczną , przy założeniu, że wiersze (od góry do dołu) i kolumny (od lewej do prawej) są uporządkowane alfabetycznie:

${\ Displaystyle {\ zacząć {pmatrix} 1&0&0\\0&1&0\\0&0&1\\1&1&1\koniec {pmatrix}}.}$

W odwrotny stosunek R ^T odpowiada do transpozycji matrycy i kompozycji stosunek odpowiada na iloczyn macierzy , gdy realizowany jest przez sumowanie alternatywa . Okazuje się, że macierz 3×3 zawiera 1 na każdej pozycji, podczas gdy iloczyn macierzy odwróconej oblicza się jako: ${\ Displaystyle R ^ {\ textsf {T}}; R}$ ${\ Displaystyle R ^ {\ textsf {T}} R}$${\ Displaystyle R ^ {\ textsf {T}} R}$

${\ Displaystyle RR ^ {\ textsf {T}} = {\ zacząć {pmatrix} 1 i 0 i 0 i 1 \ \ 0 i 1 i 0 i 1 \ \ 0 i 0 i 1 i 1 \ \ 1 i 1 i 1 i 1 \ koniec {pmatrix}}.}$

Ta macierz jest symetryczna i reprezentuje jednorodną relację na A .

Odpowiednio, jest to relacja uniwersalna na B , stąd dowolne dwa języki dzielą naród, w którym oba są używane (w rzeczywistości: Szwajcaria). Odwrotnie, na pytanie, czy dwa dane narody mają wspólny język, można odpowiedzieć za pomocą . ${\ Displaystyle R ^ {\ textsf {T}}; R}$${\ Displaystyle R; R ^ {\ textsf {T}}}$

Zasady Schrödera

Dla danego zbioru V zbiór wszystkich relacji binarnych na V tworzy siatkę Boole'a uporządkowaną przez inkluzję (⊆). Przypomnijmy, że dopełnienie odwraca inkluzję: W rachunku relacji często przedstawia się dopełnienie zbioru za pomocą overbara:${\ Displaystyle A \ podzbiór B \ implikuje B ^ {\ uzupełnienie} \ podzbiór A ^ {\ uzupełnienie}.}$${\ Displaystyle {\ bar {A}} = A ^ {\ uzupełnienie}.}$

Jeśli S jest relacją binarną, niech reprezentuje relację odwrotną , zwaną także transpozycją . Wtedy zasady Schrödera są ${\ Displaystyle S ^ {\ textsf {T}}}$

${\ Displaystyle QR \ podseteq S \ quad \ równoważny \ quad Q ^ {\ textsf {T}}} \ bar {S}} \ podseteq {\ bar {R}} \ quad \ równoważny \ quad {\ bar {S} }R^{\textsf {T}}\subseteq {\bar {Q}}.}$

Werbalnie jedną równoważność można uzyskać z innej: wybierz pierwszy lub drugi czynnik i przetransponuj go; następnie uzupełnij pozostałe dwie relacje i permutuj je.

Chociaż ta transformacja włączenia kompozycji relacji została szczegółowo opisana przez Ernsta Schrödera , w rzeczywistości Augustus De Morgan po raz pierwszy wyartykułował tę transformację jako Twierdzenie K w 1860 roku.

${\ Displaystyle LM \ subseteq N \ implikuje {\ bar {N}} M ^ {\ textsf {T}} \ subseteq {\ bar {L}}.}$

Za pomocą reguł Schrödera i komplementacji można znaleźć nieznaną relację X w inkluzjach relacji, takich jak

${\ Displaystyle RX \ podseteq S \ quad {\ tekst {i}} \ quad XR \ podseteq S.}$

Na przykład, zgodnie z regułą Schrödera i dopełnieniem daje to, co nazywamy lewą resztą S przez R . ${\ Displaystyle RX \ subseteq S \ implikuje R ^ {\ textsf {T}} {\ bar {S}} \ subseteq {\ bar {X}}}$${\ Displaystyle X \ subseteq {\ overline {R ^ {\ textsf {T}}} \ bar {S}}}}}$

Iloraz

Tak jak składanie relacji jest rodzajem mnożenia, w wyniku którego powstaje iloczyn, tak niektóre kompozycje porównują się do dzielenia i dają iloraz. Przedstawiono tu trzy ilorazy: lewą resztę, prawą resztę i iloraz symetryczny. Lewa reszta dwóch relacji jest definiowana przy założeniu, że mają one tę samą domenę (źródło), a prawa reszta zakłada tę samą kodziedzinę (zakres, cel). Symetryczny iloraz zakłada, że ​​dwie relacje mają wspólną domenę i współdziedzinę.

Definicje:

• Pozostała część: ${\ Displaystyle A \ ukośnik odwrotny B \ mathrel {: =} {\ overline {A ^ {\ textsf {T}} {\ bar {B}}}}}$
• Prawo resztkowe: ${\ Displaystyle D / C \ mathrel {: =} {\ overline {{\ bar {D}} C ^ {\ textsf {T}}}}}$
• Iloraz symetryczny: ${\ Displaystyle \ operatorname {syq} (E, F) \ mathrel {: =} {\ overline {E ^ {\ textsf {T}}} \ bar {F}}}} \ cap {\ overline {{\ bar {E}}^{\textsf {T}}F}}}$

Używając reguł Schrödera, AX ⊆ B jest równoważne X ⊆ A B . Zatem lewa reszta jest największą relacją spełniającą AX ⊆ B . Podobnie, włączenie YC ⊆ D jest równoważne Y ⊆ D / C , a prawa reszta jest największą relacją spełniającą YC ⊆ D . ${\displaystyle \backslash}$

Można ćwiczyć logikę reszt w Sudoku .

Dołącz: inna forma kompozycji

Wprowadzono operator widełek (<), aby połączyć dwie relacje c : H → A i d : H → B w c (<) d : H → A × B . Konstrukcja opiera się na rzutach a : A × B → A i b : A × B → B , rozumianych jako relacje, co oznacza, że ​​istnieją przeciwne relacje a ^T i b ^T . Następnie widły z C i D podaje się

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

Inną formą kompozycji stosunkach, które stosuje się do ogólnych n stosunków -Miejsce dla n ≥ 2 jest dołączyć działanie relacyjnej Algebra . Zwykłe złożenie dwóch relacji binarnych, jak tutaj zdefiniowano, można uzyskać, biorąc ich sprzężenie, prowadzące do relacji trójskładnikowej, po której następuje projekcja, która usuwa środkowy składnik. Na przykład w języku zapytań SQL istnieje operacja Join (SQL) .

Zobacz też

• Demoniczna kompozycja
• Przyjaciel przyjaciela

Uwagi

Bibliografia

• M. Kilp, U. Knauer, AV Mikhalev (2000) Monoidy, akty i kategorie z zastosowaniami do produktów i wykresów wieńców , De Gruyter Expositions in Mathematics vol. 29, Walter de Gruyter , ISBN  3-11-015248-7 .