Složení vztahů - Composition of relations

V matematika z binární vztahy, kompoziční vztahy je koncept formování nového vztahu R ; S ze dvou daných vztahů R a S. Složení vztahů se nazývá relativní násobení^[1] v počet vztahů. Složení je pak relativní produkt^[2]:40 faktorových vztahů. Složení funkcí je zvláštní případ složení vztahů.

Slova strýc a teta uveďte složený vztah: aby člověk mohl být strýcem, musí být bratrem rodiče (nebo sestrou pro tetu). v algebraická logika říká se, že vztah strýce ( xUz ) je složení vztahů „je bratr“ ( xBy ) a „je rodičem“ ( yPz ).

${displaystyle U = BPquad equiv quad xByPziff xUz.}$

Počínaje Augustus De Morgan,^[3] tradiční forma uvažování sylogismus byl subsumován relačními logickými výrazy a jejich složením.^[4]

Definice

Li ${displaystyle Rsubseteq X je Y}$ a ${displaystyle Ssubseteq Y imes Z}$ jsou dva binární vztahy, tedy jejich složení ${displaystyle R; S}$ je vztah

${displaystyle R; S = {(x, z) v X imes Zmid existuje yin Y: (x, y) v Rlandu (y, z) v S}.}$

Jinými slovy, ${displaystyle R; Ssubseteq X imes Z}$ je definováno pravidlem, které říká ${displaystyle (x, z) v R; S}$ právě tehdy, když existuje prvek ${displaystyle yin Y}$ takhle ${displaystyle x, R, y, S, z}$ (tj. ${displaystyle (x, y) v R}$ a ${displaystyle (y, z) v S}$).^[5]:13

Varianty notací

Středník jako infixová notace pro složení vztahů sahá až do Ernst Schroder učebnice z roku 1895.^[6] Gunther Schmidt obnovil používání středníku, zejména v Relační matematika (2011).^[2]:40[7] Použití středníku shoduje se s poznámkou pro funkční složení používanou (většinou počítačovými vědci) v teorie kategorií,^[8] stejně jako notace pro dynamickou spojku v rámci lingvistické dynamická sémantika.^[9]

Malý kruh ${displaystyle (Rcirc S)}$ byl použit pro infixovou notaci složení vztahů pomocí John M. Howie ve svých knihách zvažuje poloskupiny vztahů.^[10] Malý kruh je však široce používán k reprezentaci složení funkcí ${displaystyle g (f (x)) = (gcirc f) (x)}$ který obrátí textová sekvence z provozní sekvence. Malý kruh byl použit na úvodních stránkách Grafy a vztahy^[5]:18 dokud to nebylo upuštěno ve prospěch juxtapozice (bez infixové notace). Juxtapozice ${displaystyle (RS)}$ se běžně používá v algebře k označení násobení, takže také může znamenat relativní násobení.

Dále se zápisem kruhu lze použít dolní indexy. Někteří autoři^[11] raději psát ${displaystyle circ _ {l}}$ a ${displaystyle circ _ {r}}$ výslovně v případě potřeby, v závislosti na tom, zda je použit levý nebo pravý vztah. Další variací, se kterou se informatika setkala, je Z notace: ${displaystyle circ}$ se používá k označení tradiční (pravé) kompozice, ale ⨾ (tlustý otevřený středník s kódovým bodem Unicode U + 2A3E) označuje levou kompozici.^[12][13]

Binární vztahy ${displaystyle Rsubseteq X je Y}$ jsou někdy považovány za morfismy ${displaystyle Rcolon X o Y}$ v kategorie Rel který má sady jako objekty. v Rel, složení morfismů je přesně složení vztahů, jak je definováno výše. Kategorie Soubor sad je podkategorií Rel který má stejné objekty, ale méně morfismů.

Vlastnosti

• Složení vztahů je asociativní: ${displaystyle R; (S; T) = (R; S); T.}$
• The konverzní vztah z R ; S je (R ; S)^T = S^T ; R^T. Tato vlastnost činí sadu všech binárních relací v sadě a poloskupina s involucí.
• Složení (částečné) funkce (tj. funkční vztahy) je opět (částečná) funkce.
• Li R a S jsou injekční, pak R ; S je injektivní, což naopak znamená pouze injektivitu R.
• Li R a S jsou surjektivní, pak R ; S je surjektivní, což naopak znamená pouze surjektivitu S.
• Sada binárních vztahů na množině X (tj. vztahy z X na X) společně s (levou nebo pravou) relační kompozicí tvoří a monoidní s nulou, kde je mapa identity zapnutá X je neutrální prvek a prázdná sada je nulový prvek.

Složení, pokud jde o matice

Konečné binární vztahy jsou reprezentovány logické matice. Položky těchto matic jsou buď nula, nebo jedna, v závislosti na tom, zda je reprezentovaný vztah nepravdivý nebo pravdivý pro řádek a sloupec odpovídající srovnávaným objektům. Práce s takovými maticemi zahrnuje logickou aritmetiku s 1 + 1 = 1 a 1 × 1 = 1. Záznam v maticový produkt ze dvou logických matic bude 1, pak pouze v případě, že vynásobený řádek a sloupec mají odpovídající 1. Logickou matici složení vztahů lze tedy najít výpočtem maticového součinu matic představujících faktory složení. "Matice představují metodu pro výpočetní závěry tradičně vyvozované pomocí hypotetických sylogismů a soritů. “^[14]

Heterogenní vztahy

Zvažte heterogenní vztah R ⊆ A × B. Pak pomocí složení relace R s jeho konverzovat R^T, existují homogenní vztahy R R^T (na A) a R^T R (na B).

Pokud ∀X ∈ A ∃y ∈ B xRy (R je celkový vztah ), pak ∀X xRR^TX aby R R^T je reflexivní vztah nebo já ⊆ R R^T kde I je vztah identity {XJáX : X ∈ A}. Podobně, pokud R je surjektivní vztah pak

R^T R ⊇ I = {XJáX : X ∈ B}. V tomto případě R ⊆ R R^T R. K opačnému zařazení dochází u a funkční vztah.

Kompozice ${displaystyle {ar {R}} ^ {T} R}$ se používá k rozlišení vztahů Ferrerova typu, které uspokojují ${displaystyle R {ar {R}} ^ {T} R = R.}$

Příklad

Složení R s R^T vytváří vztah s tímto grafem, Švýcarsko je připojeno k ostatním zemím (smyčky nejsou zobrazeny).

Nechat A = {Francie, Německo, Itálie, Švýcarsko} a B = {Francouzština, němčina, italština} se vztahem R dána aRb když b je národní jazyk z A. The logická matice pro R darováno

${displaystyle {egin {pmatrix} 1 & 0 & 0 0 & 1 & 0 0 & 0 & 1 1 & 1 & 1end {pmatrix}}.}$ Za použití konverzní vztah R^T, lze odpovědět na dvě otázky: „Existuje překladač?“ má odpověď ${displaystyle R ^ {T} R = B je B,}$ the univerzální vztah na B. Mezinárodní otázka: „Mluví mým jazykem?“ odpovídá ${displaystyle RR ^ {T} = {egin {pmatrix} 1 & 0 & 0 & 1 0 & 1 & 0 & 1 0 & 0 & 1 & 1 1 & 1 & 1 & 1end {pmatrix}}.}$ Tato symetrická matice, představující homogenní vztah na A, je spojen s hvězdný graf S₃ rozšířen o a smyčka v každém uzlu.

Schröder vládne

Pro danou sadu PROTI, sbírka všech binární vztahy na PROTI tvoří a Booleova mříž objednáno někým zařazení (⊆). Odvolej to doplňování obrací zařazení:${displaystyle Asubset Bimplies B ^ {doplněk} subseteq A ^ {doplněk}.}$ V počet vztahů^[15] je běžné reprezentovat doplněk sady pomocí overbaru: ${displaystyle {ar {A}} = A ^ {doplněk}.}$

Li S je binární relace, ať ${displaystyle S ^ {T}}$ představují konverzní vztah, také nazývaný přemístit. Pak jsou Schröderova pravidla

${displaystyle QRsubseteq Družstvo ekviv quad Q ^ {T} {ar {S}} subseteq {ar {R}} quad ekviv quad {ar {S}} R ^ {T} subseteq {ar {Q}}.}$

Verbálně lze jednu ekvivalenci získat od jiné: vyberte první nebo druhý faktor a proveďte jej; pak doplňte další dva vztahy a permutujte je.^[5]:15–19

Ačkoli tuto transformaci zahrnutí složení vztahů podrobně popsal Ernst Schröder, ve skutečnosti Augustus De Morgan poprvé artikuloval transformaci jako Věta K v roce 1860.^[4] Napsal

${displaystyle LMsubseteq Nimplies {ar {N}} M ^ {T} subseteq {ar {L}}.}$^[16]

Schröderovými pravidly a doplňováním lze vyřešit neznámý vztah X ve vztahu inkluze jako

${displaystyle RXsubseteq Squad {ext {a}} quad XRsubseteq S.}$

Například podle Schröderova pravidla ${displaystyle RXsubseteq Zjednodušuje R ^ {T} {ar {S}} subseteq {ar {X}},}$ a doplnění dává ${displaystyle Xsubseteq {overline {R ^ {T} {ar {S}}}},}$ který se nazývá zbylý zbytek S od R .

Kvocienty

Stejně jako je složení vztahů druhem násobení, jehož výsledkem je produkt, tak se některé kompozice srovnávají s dělením a vytvářejí kvocienty. Zde jsou vystaveny tři kvocienty: levý zbytkový, pravý zbytkový a symetrický kvocient. Levý zbytek dvou vztahů je definován za předpokladu, že mají stejnou doménu (zdroj), a pravý zbytek předpokládá stejnou doménu (rozsah, cíl). Symetrický kvocient předpokládá, že dva vztahy sdílejí doménu a doménu.

Definice:

• Zbývající zbytky: ${displaystyle A ackslash B = {overline {A ^ {T} {ar {B}}}}}$
• Pravý zbytek: ${displaystyle D / C = {overline {{ar {D}} C ^ {T}}}}$
• Symetrický kvocient: ${displaystyle operatorname {syq} (E, F) = {overline {E ^ {T} {ar {F}}}} cap {overline {{ar {E}} ^ {T} F}}}$

Podle Schröderových pravidel SEKERA ⊆ B je ekvivalentní k X ⊆ A${displaystyle ackslash}$B. Levý zbytek je tedy největší uspokojující vztah SEKERA ⊆ B. Podobně zahrnutí YC ⊆ D je ekvivalentní k Y ⊆ D/Ca správný zbytek je největší uspokojující vztah YC ⊆ D.^[2]:43–6

Připojte se: jiná forma složení

Byl zaveden operátor vidlice (<), který spojí dva vztahy C: H → A a d: H → B do C(<)d: H → A × BKonstrukce závisí na projekcích A: A × B → A a b: A × B → B, chápané jako vztahy, což znamená, že existují konverzní vztahy A^T a b^T. Pak Vidlička z C a d darováno

${displaystyle c (<) d: = c; a ^ {T} cap d; b ^ {T}.}$^[17]

Jiná forma složení vztahů, která platí pro obecné n-místní vztahy pro n ≥ 2, je připojit se provoz relační algebra. Obvyklé složení dvou binárních relací, jak je zde definováno, lze získat spojením, které vede k ternárnímu vztahu, po kterém následuje projekce, která odstraní střední komponentu. Například v dotazovacím jazyce SQL existuje operace Připojit se (SQL).

Viz také

• Démonické složení
• Přítel přítele

Poznámky

Reference

• M. Kilp, U. Knauer, A.V. Mikhalev (2000) Monoidy, akty a kategorie s aplikacemi na věnování produktů a grafů, De Gruyter Expositions in Mathematics sv. 29, Walter de Gruyter,ISBN  3-11-015248-7.