Heterogenní vztah - Heterogeneous relation
v matematika, a heterogenní vztah je binární relace, a podmnožina a kartézský součin A × B, kde A a B jsou odlišné sady.[1] Předpona hetero pochází z řečtiny ἕτερος (heteros„jiný, jiný, jiný“).
Heterogenní vztah byl nazýván a obdélníkový vztah,[2] což naznačuje, že nemá čtvercovou symetrii a homogenní vztah na množině kde A = B. V komentáři k vývoji binárních vztahů nad rámec homogenních vztahů vědci napsali: „... vyvinula se varianta teorie, která od počátku zachází se vztahy jako heterogenní nebo obdélníkový, tj. jako vztahy, kde je normální případ, že se jedná o vztahy mezi různými množinami. “[3]
Vývoj v roce 2006 algebraická logika usnadnily použití binárních vztahů. The počet vztahů zahrnuje algebra množin, rozšířeno o složení vztahů a použití konverzní vztahy. Zahrnutí R ⊆ S, znamenající, že aRb naznačuje aSb, nastavuje scénu v a mříž vztahů. Ale od symbol zařazení je nadbytečný. Složení vztahů a manipulace operátorů podle Schröder vládne, poskytuje kalkul pro práci v napájecí sada z A × B.
Na rozdíl od homogenních vztahů složení vztahů operace je pouze a částečná funkce. Nutnost přizpůsobení rozsahu doméně složených vztahů vedla k domněnce, že studium heterogenních vztahů je kapitolou teorie kategorií jako v kategorie sad kromě toho, že morfismy této kategorie jsou vztahy. The předměty kategorie Rel jsou množiny a relační morfismy se skládají podle požadavků v a kategorie.
Příklady

NA | SA | AF | EU | TAK JAKO | OC | AA | |
---|---|---|---|---|---|---|---|
indický | 0 | 0 | 1 | 0 | 1 | 1 | 1 |
Arktický | 1 | 0 | 0 | 1 | 1 | 0 | 0 |
Atlantik | 1 | 1 | 1 | 1 | 0 | 0 | 1 |
Pacifik | 1 | 1 | 0 | 0 | 1 | 1 | 1 |
1) Nechte A = {Indický, arktický, atlantický, tichomořský}, oceány zeměkoule a B = {NA, SA, AF, EU, AS, OC, AA}, kontinenty. Nechat aRb představují ten oceán A hranice kontinent b. Pak logická matice pro tento vztah je:
Na konektivitu planety Země lze nahlížet skrz R RT a RT R, přičemž první je relací 4 × 4 A, což je univerzální vztah (A × A nebo logická matice všech). Tento univerzální vztah odráží skutečnost, že každý oceán je oddělen od ostatních nejvýše jedním kontinentem. Na druhou stranu, RT R je vztah na B × B který selže být univerzální, protože z cesty musí být překonány alespoň dva oceány Evropa na Oceánie.
2) Vizualizace vztahů se opírá o teorie grafů: Pro vztahy na množině (homogenní vztahy), a řízený graf ilustruje vztah a graf symetrický vztah. Pro heterogenní vztahy a hypergraf má hrany pravděpodobně s více než dvěma uzly a může být ilustrováno a bipartitní graf.
Stejně jako klika je nedílnou součástí vztahů na množině, takže bicliques jsou používány k popisu heterogenních vztahů; ve skutečnosti jsou to „koncepty“, které generují mřížku spojenou s relací.

3) Hyperbolická ortogonalita: Čas a prostor jsou různé kategorie a časové vlastnosti jsou oddělené od prostorových vlastností. Myšlenka simultánní události je jednoduchý v absolutní čas a prostor od pokaždé t určuje současně nadrovina v té kosmologii. Herman Minkowski to změnil, když vyslovil představu relativní simultánnost, který existuje, když jsou prostorové události „normální“ pro čas charakterizovaný rychlostí. Použil neurčitý vnitřní součin a určil, že časový vektor je normální vůči vesmírnému vektoru, když je tento součin nulový. Neurčitý vnitřní produkt v a složení algebra darováno
- kde overbar označuje konjugaci.
Jako vztah mezi některými časovými událostmi a některými prostorovými událostmi hyperbolická ortogonalita (jak je uvedeno v rozdělená komplexní čísla ) je heterogenní vztah.[4]
4) A geometrická konfigurace lze považovat za vztah mezi jeho body a liniemi. Vztah je vyjádřen jako výskyt. Zahrnuty jsou konečné a nekonečné projektivní a afinní roviny. Jakob Steiner propagoval katalogizaci konfigurací s Steinerovy systémy S (t, k, n), které mají sadu n-prvků S a sada podmnožin k-prvků s názvem bloky, takže podmnožina s t prvky leží v jediném bloku. Tyto struktury dopadu byly zobecněny na blokové vzory. The matice výskytu použitý v těchto geometrických kontextech odpovídá logické matici používané obecně s binárními vztahy.
- Struktura výskytu je trojnásobná D = (PROTI, B, Já) kde PROTI a B jsou libovolné dvě disjunktní sady a Já je binární vztah mezi PROTI a B, tj. Já ⊆ PROTI × B. Prvky PROTI bude volána bodů, ti z B bloky a ty z I vlajky.[5]
Indukovaná koncepce mříž
Heterogenní vztahy byly popsány prostřednictvím jejich indukce koncepční mřížky:A pojem C ⊂ R splňuje dvě vlastnosti: (1) Logická matice C je vnější produkt logických vektorů
- logické vektory. (2) C je maximální, není obsažen v žádném jiném vnějším produktu. Tím pádem C je popsán jako nezvětšitelný obdélník.
Pro daný vztah R: X → Y, sada pojmů, rozšířená o jejich spojení a setkávání, tvoří „indukovanou mřížku pojmů“ se zahrnutím formování a předobjednávka.
The MacNeilleova věta o dokončení (1937) (že jakýkoli dílčí řád může být vložen do a úplná mříž ) je citován v článku z roku 2013 „Rozklad vztahů na koncepčních mřížkách“.[6] Rozklad je
- kde F a G jsou funkce, volala mapování nebo levý součet, univalentní vztahy v tomto kontextu. „Mřížka indukovaného konceptu je izomorfní s dokončením řezu částečného řádu E který patří k minimálnímu rozkladu (f, g, E.) vztahu R."
Zvláštní případy jsou zvažovány níže: E celková objednávka odpovídá typu Ferrers a E identita odpovídá difunkční, zobecnění vztah ekvivalence na setu.
Vztahy mohou být řazeny podle Scheinova hodnost který počítá počet konceptů nezbytných k pokrytí vztahu.[7] Strukturální analýza vztahů s pojmy poskytuje přístup k dolování dat.[8]
Zvláštní vztahy
- Tvrzení: Pokud R je celkový vztah a R.T je tedy jeho transpozice kde jsem m × m vztah identity.
- Tvrzení: Pokud R je surjektivní vztah, pak kde jsem n × n vztah identity.
Difunkční
Mezi homogenními vztahy na množině je ekvivalenční vztahy se vyznačují schopností rozdělit sadu. U heterogenních vztahů je myšlenka rozdělit objekty rozlišením atributů. Jedním ze způsobů, jak toho lze dosáhnout, je intervenující sada Z = {x, y, z, ...} z ukazatele. Rozdělení R = F GT je složení vztahů použitím jednomocný vztahy F ⊆ A × Z a G ⊆ B × Z.
The logická matice takového vztahu R lze znovu uspořádat jako bloková matice s bloky jedniček podél úhlopříčky. Pokud jde o počet vztahů, v roce 1950 Jacques Riguet ukázaly, že tyto vztahy uspokojují začlenění
Pojmenoval tyto vztahy funkční od složení F GT zahrnuje univalentní vztahy, běžně nazývané funkce.
Použití notace {y: xRy} = xR, difunkční vztah lze také charakterizovat jako vztah R tak, že kdekoli X1R a X2R mít neprázdnou křižovatku, pak se tyto dvě množiny shodují; formálně X1R ∩ X2R ≠ ∅ naznačuje X1R = X2R.[10]
V roce 1997 vědci zjistili "užitečnost binárního rozkladu založeného na difunkčních závislostech v databáze řízení."[11] Kromě toho jsou ve studiu základů difunkční vztahy bisimulace.[12]
V kontextu homogenních vztahů, a vztah částečné ekvivalence je funkční.
v teorie automatů, termín obdélníkový vztah byl také použit k označení difunkčního vztahu. Tato terminologie připomíná skutečnost, že když jsou reprezentovány jako logická matice, sloupce a řádky difunkčního vztahu mohou být uspořádány jako bloková diagonální matice s obdélníkovými bloky true na (asymetrické) hlavní diagonále.[13]
Ferrersův typ
A přísný řád na množině je homogenní vztah vznikající v teorie objednávek V roce 1951 Jacques Riguet přijal rozkaz a rozdělit celého čísla, nazývaného a Ferrersův diagram, rozšířit objednávání na heterogenní vztahy.[14]
Odpovídající logická matice heterogenního vztahu má řádky, které končí nerostoucí posloupností těch. Tak se body Ferrerova diagramu změní na ty a zarovnají se vpravo v matici.
Algebraický výrok požadovaný pro vztah typu Ferrers R je
Pokud některý ze vztahů je typu Ferrers, pak jsou všechny.[1]
Kontakt
Předpokládat B je napájecí sada z Asoubor všech podmnožiny z A. Pak kontaktní vztah G splňuje tři vlastnosti: (1) ∀ X v A, Y = {X} naznačuje x g Y. (2) Y ⊆ Z a x g Y naznačuje x g Z.. (3) ∀ y v Y, y g Z a x g Y naznačuje x g Z.. The nastavit členství relace, ε = "je prvek", splňuje tyto vlastnosti, takže ε je kontaktní relace. Pojem obecného kontaktního vztahu zavedl Georg Aumann ve své knize Kontakt-Relationen (1970).[15]
Z hlediska počtu vztahů zahrnují dostatečné podmínky pro kontaktní vztah
- kde je obrácenou množinou členství (∈).[16]:280
Předobjednat R R
Každý vztah R generuje a předobjednávka R R který je zbylé zbytky.[17] Pokud jde o konverzaci a doplňky, Tvoří úhlopříčku , odpovídající řádek RT a sloupec bude mít opačné logické hodnoty, takže úhlopříčka je nulová. Pak
- aby R R je reflexivní vztah.
Ukázat tranzitivita, jeden to vyžaduje (R R)(R R) ⊂ R R. Odvolej to X = R R je největší vztah takový, že R X ⊂ R. Pak
- (opakovat)
- (Schröderovo pravidlo)
- (doplnění)
- (definice)
The zařazení vztah Ω na napájecí sada z U lze získat tímto způsobem z členský vztah ∈ u podmnožin U:
- [16]:283
Okraj vztahu
Vzhledem k vztahu R, dílčí vztah zvaný jeho třásně je definován jako
Když R je dílčí vztah identity, difunkční nebo blokový diagonální vztah, pak okraj (R) = R. Jinak operátor okrajů vybere hraniční dílčí vztah popsaný v podmínkách jeho logické matice: okraj (R) je boční úhlopříčka, pokud R je trojúhelník vpravo nahoře lineární pořadí nebo přísný řád. Fringe (R) je okraj bloku, pokud je R irreflexivní () nebo trojúhelníkový blok vpravo nahoře. Fringe (R) je posloupnost hraničních obdélníků, když R je typu Ferrers.
Na druhou stranu, Fringe (R) = ∅ když R je hustý, lineární, přísné pořadí.[16]
Matematické hromady
Vzhledem k tomu, dvě sady A a B, množina binárních vztahů mezi nimi mohou být vybaveny a ternární provoz kde bT označuje konverzní vztah z b. V roce 1953 Viktor Wagner vlastnosti této ternární operace byly použity k definování polohrobů, hromad a generalizovaných hromad.[18][19] Kontrast heterogenních a homogenních vztahů je zvýrazněn těmito definicemi:
- Ve Wagnerově práci existuje příjemná symetrie mezi hromadami, polohřebeny a generalizovanými hromadami na jedné straně a skupinami, poloskupinami a zobecněnými skupinami na straně druhé. V zásadě se různé typy polohvězd objevují vždy, když uvažujeme binární vztahy (a částečné mapování jedna k jedné) mezi odlišný sady A a B, zatímco v případě, že se objeví různé typy poloskupin A = B.[20]
Viz také
Reference
- ^ A b Schmidt, Gunther; Ströhlein, Thomas (2012). Vztahy a grafy: Diskrétní matematika pro počítačové vědce. Springer Science & Business Media. str. 77. ISBN 978-3-642-77968-8.
- ^ Michael Winter (2007). Kategorie Goguen: Kategorický přístup k L-fuzzy vztahům. Springer. str. x – xi. ISBN 978-1-4020-6164-6.
- ^ G. Schmidt, Claudia Haltensperger a Michael Winter (1997) „Heterogenní relační algebra“, kapitola 3 (strany 37 až 53) v Relační metody v informaticePokroky v informatice, Springer knihy ISBN 3-211-82971-7
- ^
Relativní simultánnost na Wikibooks
- ^ Beth, Thomas; Jungnickel, Dieter; Lenz, Hanfried (1986). Teorie designu. Cambridge University Press. str. 15.. 2. vyd. (1999) ISBN 978-0-521-44432-3
- ^ R. Berghammer & M. Winter (2013) „Decomposition of relations on concept lattices“, Fundamenta Informaticae 126(1): 37–82 doi:10.3233 / FI-2013-871
- ^ Ki Hang Kim (1982) Teorie a aplikace booleovské maticestrana 37, Marcel Dekker ISBN 0-8247-1788-0
- ^ Ali Jaoua, Rehab Duwairi, Samir Elloumi a Sadok Ben Yahia (2009) „Dolování dat, uvažování a získávání přírůstkových informací prostřednictvím nezvětšitelného pokrytí pravoúhlých vztahů“, strany 199 až 210 v Vztahy a Kleeneovy algebry v informatice, Přednášky z informatiky 5827, Springer PAN2781235
- ^ Jacques Riguet (1950) „Quelques proprietes des relations difonctionelles“, Comptes Rendus 230: 1999–2000
- ^ Chris Brink; Wolfram Kahl; Gunther Schmidt (1997). Relační metody v informatice. Springer Science & Business Media. str. 200. ISBN 978-3-211-82971-4.
- ^ Ali Jaoua, Nadin Belkhiter, Habib Ounalli a Theodore Moukam (1997) „Databáze“, strany 197–210 v Relační metody v informatice, editovali Chris Brink, Wolfram Kahl a Gunther Schmidt, Springer Science & Business Media ISBN 978-3-211-82971-4
- ^ Gumm, H. P .; Zarrad, M. (2014). "Coalgebraické simulace a kongruence". Coalgebraické metody v informatice. Přednášky z informatiky. 8446. str. 118. doi:10.1007/978-3-662-44124-4_7. ISBN 978-3-662-44123-7.
- ^ Julius Richard Büchi (1989). Konečné automaty, jejich algebry a gramatiky: Směrem k teorii formálních výrazů. Springer Science & Business Media. str. 35–37. ISBN 978-1-4613-8853-1.
- ^ J. Riguet (1951) „Les relations de Ferrers“, Comptes Rendus 232: 1729,30
- ^ Anne K. Steiner (1970) Posouzení:Kontakt = Relationen z Matematické recenze
- ^ A b C Gunther Schmidt (2011) Relační matematika, strany 211−15, Cambridge University Press ISBN 978-0-521-76268-7
- ^ V této souvislosti symbol „"neznamená" nastavený rozdíl ".
- ^ Viktor Wagner (1953) „Teorie zobecněných hromad a zobecněných skupin“, Matematicheskii Sbornik 32 (74): 545 až 632 PAN0059267
- ^ CD. Hollings & M.V. Lawson (2017) Wagnerova teorie generalizovaných hromad, Springer knihy ISBN 978-3-319-63620-7 PAN3729305
- ^ Christopher Hollings (2014) Matematika za železnou oponou: historie algebraické teorie poloskupin, strana 265, Dějiny matematiky 41, Americká matematická společnost ISBN 978-1-4704-1493-1
- Schmidt, Gunther; Ströhlein, Thomas (2012). „Kapitola 3: Heterogenní vztahy“. Vztahy a grafy: Diskrétní matematika pro počítačové vědce. Springer Science & Business Media. ISBN 978-3-642-77968-8.
- Ernst Schröder (1895) Algebra der Logik, skupina III, přes Internetový archiv