Binární relace - Binary relation

v matematika (konkrétně teorie množin ), a binární relace přes sady X a Y je podmnožina z kartézský součin X × Y; to znamená, že je to soubor objednané páry (X, y) skládající se z prvků X v X a y v Y.^[1] Kóduje informace o vztah: prvek X souvisí s prvkem y, kdyby a jen kdyby dvojice (X, y) patří do sady. Binární relace je nejvíce studovaným zvláštním případem n = 2 z n-ary vztah přes sady X₁, ..., X_n, což je podmnožina kartézského součinu X₁ × ... × X_n.^[1][2]

Příkladem binární relace je „rozděluje "vztah nad množinou prvočísla ${displaystyle mathbb {P}}$ a soubor celá čísla ${displaystyle mathbb {Z}}$, ve kterém každý prime p souvisí s každým celým číslem z to je násobek z p, ale ne na celé číslo, které není násobkem p. V tomto vztahu například prvočíslo 2 souvisí s čísly jako −4, 0, 6, 10, ale ne s 1 nebo 9, stejně jako prvočíslo 3 souvisí s 0, 6 a 9, ale ne na 4 nebo 13.

Binární vztahy se používají v mnoha oborech matematiky k modelování široké škály konceptů. Mezi ně patří mimo jiné:

• „je větší než ", "je rovný "a" rozdělí "vztahy v aritmetický;
• „je shodný s "vztah v geometrie;
• vztah "sousedí s" v teorie grafů;
• „je ortogonální vztah v lineární algebra.

A funkce lze definovat jako speciální druh binárního vztahu.^[3] Binární vztahy jsou také hojně využívány v počítačová věda.

Binární relace přes množiny X a Y je prvkem napájecí sada z X × Y. Vzhledem k tomu, že druhá sada je objednána zařazení (⊆), každý vztah má místo v mříž podskupin X × Y.

Vzhledem k tomu, že relace jsou sady, lze s nimi manipulovat pomocí operací sady, včetně svaz, průsečík, a doplňování a dodržování zákonů algebra množin. Kromě toho operace jako konverzovat vztahu a složení vztahů jsou k dispozici a splňují zákony a počet vztahů, pro které existují učebnice od Ernst Schröder,^[4] Clarence Lewis,^[5] a Gunther Schmidt.^[6] Hlubší analýza vztahů zahrnuje jejich rozložení na tzv. Podmnožiny konceptya jejich umístění do a úplná mříž.

V některých systémech axiomatická teorie množin, vztahy jsou rozšířeny na třídy, což jsou zevšeobecnění množin. Toto rozšíření je potřebné mimo jiné pro modelování konceptů „je prvek“ nebo „je podmnožinou“ v teorii množin, aniž by došlo k logickým nesrovnalostem, jako je Russellův paradox.

Podmínky korespondence,^[7] dyadický vztah a vztah dvou míst jsou synonyma pro binární relaci, ačkoli někteří autoři používají termín „binární relace“ pro jakoukoli podmnožinu kartézského produktu X × Y bez odkazu na X a Y, a vyhradit si termín „korespondence“ pro binární vztah s odkazem na X a Y.

Definice

Dané sady X a Y, kartézský součin X × Y je definován jako {(X, y) | X ∈ X ∧y ∈ Y}a jeho prvky se nazývají uspořádané páry.

A binární relace R přes sady X a Y je podmnožinou X × Y.^[1][8] Sada X se nazývá doména^[1] nebo sada odletu z Ra sada Y the codomain nebo soubor cíle z R. Za účelem upřesnění možností sad X a Y, někteří autoři definují a binární relace nebo korespondence jako objednaná trojka (X, Y, G), kde G je podmnožinou X × Y volal graf binárního vztahu. Prohlášení (X, y) ∈ R čte „X je R- související s y"a je označen xRy.^{[4][5][6][poznámka 1]} The doména definice nebo aktivní doména^[1] z R je množina všech X takhle xRy alespoň pro jednoho y. The doména definice, aktivní codomain,^[1] obraz nebo rozsah z R je množina všech y takhle xRy alespoň pro jednoho X. The pole z R je sjednocení její domény definice a její kodomény definice.^[10][11][12]

Když X = Y, binární relace se nazývá a homogenní vztah (nebo endorelace). Zdůraznit skutečnost, že X a Y se mohou lišit, binární relace se také nazývá a heterogenní vztah.^[13][14][15]

V binární relaci je důležité pořadí prvků; -li X ≠ y pak xRy, ale yRx může být pravda nebo nepravda nezávisle na xRy. Například 3 rozdělí 9, ale 9 nerozdělí 3.

Příklad

Následující příklad ukazuje, že výběr codomainu je důležitý. Předpokládejme, že existují čtyři objekty A = {míč, auto, panenka, pohár} a čtyři lidé B = {John, Mary, Ian, Venus}. Možný vztah na A a B je vztah "je ve vlastnictví", daný R = {(míč, John), (panenka, Mary), (auto, Venuše)}. To znamená, že John vlastní míč, Mary vlastní panenku a Venuši vlastní auto. Nikdo nevlastní pohár a Ian nevlastní nic. Jako sada R nezahrnuje Iana, a proto R mohl být viděn jako podmnožina A × {John, Mary, Venus}, tj. relace skončila A a {John, Mary, Venus}.

Speciální typy binárních relací

Příklady čtyř typů binárních vztahů nad reálná čísla: one-to-one (zeleně), one-to-many (modře), many-to-one (červeně), many-to-many (černě).

Některé důležité typy binárních vztahů R přes sady X a Y jsou uvedeny níže.

Vlastnosti jedinečnosti:

• Injekční (také zvaný levý-jedinečný^[16]): ∀X ∈ X ∧ ∀z ∈ X ∧ ∀y ∈ Y, pokud xRy ∧ zRy pak X = z. Pro takový vztah {Y} je nazýván A primární klíč z R.^[1] Například zelené a modré binární vztahy v diagramu jsou injektivní, ale červený není (protože se vztahuje k −1 a 1 až 1), ani černý (protože se vztahuje k −1 i 1 až 0) .
• Funkční (také zvaný pravý-jedinečný,^[16] správně-definitivní^[17] nebo jednomocný^[6]): ∀X ∈ X ∧ ∀y ∈ Y ∧ ∀z ∈ Y, pokud xRy a xRz pak y = z. Takový binární vztah se nazývá a částečná funkce. Pro takový vztah {X} je nazýván primární klíč z R.^[1] Například červená a zelená binární relace v diagramu jsou funkční, ale modrá není (protože se vztahuje 1 k oběma −1 a 1), ani černá (protože se vztahuje k 0 k oběma −1 a 1) .
• Jeden na jednoho: injektivní a funkční. Například zelená binární relace v diagramu je jedna k jedné, ale červená, modrá a černá nejsou.
• Jeden k mnoha: injekční a nefunkční. Například modrá binární relace v diagramu je jedna k mnoha, ale červená, zelená a černá nejsou.
• Mnoho k jednomu: funkční a ne injektivní. Například červená binární relace v diagramu je více ku jedné, ale zelená, modrá a černá nejsou.
• Mnoho k mnoha: není injekční ani funkční. Například černá binární relace v diagramu je mnoho k mnoha, ale červená, zelená a modrá nejsou.

Vlastnosti totality (definovatelné pouze v případě domény X a codomain Y jsou specifikovány):

• Seriál (také zvaný celkem vlevo^[16]): pro všechny X v X existuje a y v Y takhle xRy. Jinými slovy, doména definice R je rovný X. Tato vlastnost, i když se také označuje jako celkový některými autory,^{[Citace je zapotřebí ]} se liší od definice Connex (také zvaný celkový někteří autoři)^{[Citace je zapotřebí ]} v sekci Vlastnosti. Takový binární vztah se nazývá a funkce s více hodnotami. Například červené a zelené binární vztahy v diagramu jsou sériové, ale modrý není (protože se nevztahuje −1 k žádnému reálnému číslu), ani černý (protože se nevztahuje 2 k žádnému reálnému číslu) ).
• Surjective (také zvaný celkem správně^[16] nebo na): pro všechny y v Y, existuje X v X takhle xRy. Jinými slovy, codomain definice R je rovný Y. Například zelené a modré binární vztahy v diagramu jsou surjektivní, ale červený není (protože nesouvisí žádné reálné číslo s −1), ani černý (protože nevztahuje žádné reálné číslo na 2 ).

Jedinečnost a souhrnné vlastnosti (definovatelné pouze v případě domény X a codomain Y jsou specifikovány):

• A funkce: binární relace, která je funkční a sériová. Například červené a zelené binární vztahy v diagramu jsou funkce, ale modré a černé nikoli.
• An injekce: funkce, která je injektivní. Například zelený binární vztah v diagramu je injekce, ale červený, modrý a černý nejsou.
• A surjection: funkce surjektivní. Například zelená binární relace v diagramu je surjekce, ale červená, modrá a černá nejsou.
• A bijekce: funkce, která je injektivní a surjektivní. Například zelená binární relace v diagramu je bijekce, ale červená, modrá a černá nejsou.

Operace s binárními vztahy

svaz

Li R a S jsou binární vztahy přes množiny X a Y pak R ∪ S = {(X, y) | xRy ∨ xSy} je odborový vztah z R a S přes X a Y.

Prvek identity je prázdný vztah. Například ≤ je sjednocení a =.

Průsečík

Li R a S jsou binární vztahy přes množiny X a Y pak R ∩ S = {(X, y) | xRy ∧ xSy} je křižovatkový vztah z R a S přes X a Y.

Prvkem identity je univerzální vztah. Například vztah „je dělitelný 6“ je průsečík vztahů „je dělitelný 3“ a „je dělitelný 2“.

Složení

Li R je binární vztah přes množiny X a Y, a S je binární vztah přes množiny Y a Z pak S ∘ R = {(X, z) | tam ∃ y ∈ Y takhle xRy ∧ ySz} (také označeno R; S) je vztah složení z R a S přes X a Z.

Prvek identity je vztah identity. Pořadí R a S v zápisu S ∘ R, použitý zde, souhlasí se standardním notovým řádem pro složení funkcí. Například skladba „je matkou„ ∘ “je rodičem„ výnosů “je prarodičem z matčiny strany„, zatímco skladba „je matkou„ ∘ “je matkou„ výtěžků “je babičkou„.

Konverzovat

Li R je binární vztah přes množiny X a Y pak R^T = {(y, X) | xRy} je konverzní vztah z R přes Y a X.

Například = je konverzace sama o sobě, stejně jako ≠, a jsou vzájemné konverzace, stejně jako ≤ a ≥. Binární relace se rovná jeho konverzaci, právě když je symetrický.

Doplněk

Li R je binární vztah přes množiny X a Y pak R = {(X, y) | ¬xRy} (také označeno R nebo ¬R) je doplňkový vztah z R přes X a Y.

Například = a ≠ jsou navzájem doplňkem, stejně jako ⊆ a ⊈, ⊇ a ⊉, ∈ a ∉, a, pro celkový počet objednávek, také a ≤.

Doplněk konverzní vztah R^T je opakem doplňku: ${displaystyle {overline {R ^ {mathsf {T}}}} = {ar {R}} ^ {mathsf {T}}.}$

Li X = Y, doplněk má následující vlastnosti:

• Pokud je relace symetrická, pak i komplement.
• Doplněk reflexivního vztahu je irreflexivní - a naopak.
• Doplněk a přísný slabý řád je úplná předobjednávka - a naopak.

Omezení

Li R je binární vztah přes množinu X a S je podmnožinou X pak R_|S = {(X, y) | xRy ∧ X ∈ S ∧ y ∈ S} je omezující vztah z R na S přes X.

Li R je binární vztah přes množiny X a Y a S je podmnožinou X pak R_|S = {(X, y) | xRy ∧ X ∈ S} je vztah omezení vlevo z R na S přes X a Y.

Li R je binární vztah přes množiny X a Y a S je podmnožinou Y pak R^|S = {(X, y) | xRy ∧ y ∈ S} je vztah pravého omezení z R na S přes X a Y.

Pokud je vztah reflexní, nereflexivní, symetrický, antisymetrický, asymetrický, tranzitivní, celkový, trichotomický, a částečná objednávka, celková objednávka, přísný slabý řád, celková předobjednávka (slabý řád), nebo vztah ekvivalence, pak také platí jeho omezení.

Přechodné uzavření omezení je však podmnožinou omezení přechodného uzavření, tj. Obecně není stejné. Například omezení vztahu „X je rodičem y„ženám se získá vztah“X je matkou ženy y"; jeho přechodné uzavření se nevztahuje na ženu s babičkou z otcovy strany. Na druhou stranu, přechodné uzavření výrazu" je rodičem "je" je předchůdcem "; jeho omezení na ženy se týká ženy s babičkou z otcovy strany.

Také různé koncepty úplnost (nezaměňujte s tím, že jste „celkem“) nepřenášejte omezení. Například přes reálná čísla vlastnost vztahu ≤ je, že každý neprázdný podmnožina S z R s horní hranice v R má nejmenší horní mez (nazývané také supremum) v R. Pro racionální čísla však toto supremum nemusí být nutně racionální, takže stejná vlastnost neplatí pro omezení vztahu ≤ k racionálním číslům.

Binární relace R přes sady X a Y se říká, že je obsažené ve vztahu S přes X a Y, psaný R ⊆ S, pokud R je podmnožinou S, to znamená, ∀X ∈ X ∧ y ∈ Y, pokud xRy, pak xSy. Li R je obsažen v S a S je obsažen v R, pak R a S jsou nazývány rovnat se psaný R = S. Li R je obsažen v S ale S není obsažen v R, pak R se říká, že je menší než S, psaný R ⊊ S. Například na racionální čísla, vztah> je menší než ≥ a roven složení > ∘ >.

Maticová reprezentace

Binární vztahy přes množiny X a Y může být algebraicky reprezentováno pomocí logické matice indexováno podle X a Y se záznamy v Booleovský semiring (doplnění odpovídá OR a násobení AND) kde přidání matice odpovídá unii vztahů, násobení matic odpovídá složení vztahů (vztahu nad X a Y a vztah skončil Y a Z),^[18] the Produkt Hadamard odpovídá průniku vztahů, nulová matice odpovídá prázdné relaci a matice jedniček odpovídá univerzálnímu vztahu. Homogenní vztahy (když X = Y) tvoří a maticový semiring (opravdu, a maticová semiagebra přes booleovský semiring), kde matice identity odpovídá vztahu identity.^[19]

Sady versus třídy

Určité matematické „vztahy“, například „rovná se“, „podmnožina“ a „člen“, nelze chápat jako binární vztahy, jak jsou definovány výše, protože jejich domény a domény nelze považovat za množiny v obvyklých systémech z axiomatická teorie množin. Pokud se například pokusíme modelovat obecný koncept „rovnosti“ jako binárního vztahu =, musíme doménu a codomain považovat za „třídu všech množin“, což není množina v obvyklé teorii množin.

Ve většině matematických kontextů jsou odkazy na vztahy rovnosti, členství a podmnožiny neškodné, protože je lze implicitně chápat tak, že jsou omezeny na určitou množinu v kontextu. Obvyklým řešením tohoto problému je výběr „dostatečně velké“ sady A, který obsahuje všechny objekty zájmu a pracuje s omezením =_A místo =. Podobně je třeba omezit „podmnožinu“ vztahu ⊆, aby měla doménu a doménu P (A) (výkonová sada konkrétní sady A): výsledný množinový vztah lze označit by_A. Rovněž vztah „člen“ musí být omezen, aby měl doménu A a codomain P (A) k získání binárního vztahu ∈_A to je sada. Bertrand Russell ukázal, že za předpokladu, že ∈ bude definováno ve všech množinách, vede k a rozpor v naivní teorii množin.

Dalším řešením tohoto problému je použití teorie množin se správnými třídami, například NBG nebo Morseova-Kelleyova teorie množin a umožňují doménu a doménu (a tedy i graf) správné třídy: v takové teorii jsou rovnost, členství a podmnožina binárními vztahy bez zvláštního komentáře. (Je třeba provést menší modifikaci konceptu objednané trojky (X, Y, G), protože běžná třída obvykle nemůže být členem uspořádané n-tice; nebo samozřejmě lze v tomto kontextu identifikovat binární vztah s jeho grafem.)^[20] S touto definicí lze například definovat binární vztah přes každou sadu a její výkonovou sadu.

Homogenní vztah

A homogenní vztah (také zvaný endorelace) přes sadu X je binární relace X a sama o sobě, tj. je podmnožinou karteziánského součinu X × X.^[15][21][22] Rovněž se jednoduše nazývá binární relace X. Příkladem homogenního vztahu je vztah příbuzenství kde je vztah nad lidmi.

Homogenní vztah R přes sadu X lze identifikovat pomocí a řízený jednoduchý graf umožňující smyčky, nebo pokud ano symetrický, s neorientovaný jednoduchý graf umožňující smyčky, kde X je sada vrcholů a R je množina hran (existuje hrana z vrcholu X na vrchol y kdyby a jen kdyby xRy). Říká se tomu vztah sousedství grafu.

Soubor všech homogenních vztahů ${displaystyle {mathcal {B}} (X)}$ přes sadu X je sada 2^{X × X} což je Booleova algebra rozšířený o involuce mapování vztahu k ní konverzní vztah. S ohledem na složení vztahů jako binární operace na ${displaystyle {mathcal {B}} (X)}$, tvoří inverzní poloskupina.

Zvláštní homogenní vztahy

Některé důležité konkrétní homogenní vztahy v množině X jsou:

• the prázdný vztah E = ∅ ⊆ X × X;
• the univerzální vztah U = X × X;
• the vztah identity Já = {(X, X) | X ∈ X}.

Pro libovolné prvky X a y z X:

• xEy drží nikdy;
• xUy drží vždy;
• xIy platí právě tehdy X = y.

Vlastnosti

Některé důležité vlastnosti, které mají homogenní vztah R přes sadu X mohou mít:

Reflexní

∀X ∈ X, xRx. Například ≥ je reflexivní vztah, ale> není.

Nereagující (nebo přísný)

∀X ∈ X, ¬xRx. Například> je ireflexivní vztah, ale ≥ není.

Coreflexive

∀X ∈ X ∧ ∀y ∈ X, pokud xRy pak X = y.^[23] Například vztah přes celá čísla, ve kterém je každé liché číslo vztaženo k sobě, je koreflexivní vztah. Vztah rovnosti je jediným příkladem reflexivního i koreflexivního vztahu a jakýkoli koreflexivní vztah je podmnožinou vztahu identity.

Kvazi-reflexivní

∀X ∈ X ∧ ∀y ∈ X, pokud xRy pak xRx ∧ yRy.

Předchozí 4 alternativy zdaleka nejsou vyčerpávající; např. červený binární vztah y = X² uvedené v části Speciální typy binárních relací není ani irreflexivní, ani coreflexivní, ani reflexivní, protože obsahuje dvojici (0, 0), a (2, 4), ale ne (2, 2), resp. Poslední dvě skutečnosti rovněž vylučují kvazi-reflexivitu.

Symetrický

∀X ∈ X ∧ ∀y ∈ X, pokud xRy pak yRx. Například „je pokrevním příbuzným z“ je symetrický vztah, protože X je pokrevní příbuzný y kdyby a jen kdyby y je pokrevní příbuzný X.

Antisymetrický

∀X ∈ X ∧ ∀y ∈ X, pokud xRy ∧ yRx pak X = y. Například ≥ je antisymetrický vztah; tak je>, ale vakuově (podmínka v definici je vždy nepravdivá).^[24]

Asymetrický

∀X ∈ X ∧ ∀y ∈ X, pokud xRy pak ¬yRx. Relace je asymetrická právě tehdy, je-li jak antisymetrická, tak i nereflexivní.^[25] Například> je asymetrický vztah, ale ≥ není.

Předchozí 3 alternativy nejsou zdaleka vyčerpávající; jako příklad nad přirozenými čísly, relací xRy definován X > 2 není symetrický ani antisymetrický, natož asymetrický.

Tranzitivní

∀X ∈ X ∧ ∀y ∈ X ∧ ∀z ∈ X, pokud xRy ∧ yRz pak xRz. Přechodný vztah je ireflexivní, právě když je asymetrický.^[26] Například „je předkem“ je přechodný vztah, zatímco „je rodičem“ není.

Antitransitivní

∀X ∈ X ∧ ∀y ∈ X ∧ ∀z ∈ X, pokud xRy a yRz pak nikdy xRz.

Ko-tranzitivní

pokud doplněk R je tranzitivní. To znamená ∀X ∈ X ∧ ∀y ∈ X ∧ ∀z ∈ X, pokud xRz, pak xRy ∨ yRz. Toto se používá v pseudobjednávky v konstruktivní matematice.

Kvazitranzitivní

∀X ∈ X ∧ ∀y ∈ X ∧ ∀z ∈ X, pokud xRy ∧ yRz ale ani jeden yRx ani zRy, pak xRz ale ¬zRx.

Přechodnost nesrovnatelnosti

∀X ∈ X ∧ ∀y ∈ X ∧ ∀z ∈ X, pokud X,y jsou nesrovnatelné w.r.t. R a y,z tedy jsou X,z jsou také. Toto se používá v slabé objednávky.

Předcházejících 5 alternativ opět není vyčerpávající. Například vztah xRy pokud (y = 0 nebo y = X+1) nevyhovuje žádné z těchto vlastností. Na druhou stranu prázdný vztah všechny triviálně uspokojuje.

Hustý

∀X ∈ X ∧ ∀y ∈ X takhle xRy, někteří z ∈ X lze najít takové, že xRz ∧ zRy. Toto se používá v husté objednávky.

Connex

∀X ∈ X ∧ ∀y ∈ X, xRy ∨ yRx. Tato vlastnost se někdy nazývá „celkem“, což je odlišné od definic „celkem“ uvedených v této části Speciální typy binárních vztahů.

Semiconnex

∀X ∈ X ∧ ∀y ∈ X, pokud X ≠ y pak xRy ∨ yRx. Tato vlastnost se někdy nazývá „celkem“, což je odlišné od definic „celkem“ uvedených v této části Speciální typy binárních vztahů.

Trichotomický

∀X ∈ X ∧ ∀y ∈ X, přesně jeden z xRy, yRx nebo X = y drží. Například> je trichotomický vztah, zatímco vztah „rozdělí“ nad přirozená čísla není.^[27]

Správně euklidovský (nebo prostě Euklidovský)

∀X ∈ X ∧ ∀y ∈ X ∧ ∀z ∈ X, pokud xRy ∧ xRz pak yRz. Například = je euklidovský vztah, protože pokud X = y a X = z pak y = z.

Levá euklidovská

∀X ∈ X ∧ ∀y ∈ X ∧ ∀z ∈ X, pokud yRx ∧ zRx pak yRz.

Seriál (nebo celkem vlevo)

∀X ∈ X, tam ∃ y ∈ X takhle xRy. Například> je sériový vztah přes celá čísla. Není to však sériový vztah nad kladnými celými čísly, protože žádný neexistuje y v kladných celých číslech taková 1 > y.^[28] X, Vybrat y = X.

Set-like^{[Citace je zapotřebí ]} (nebo místní)

^{[Citace je zapotřebí ]} ∀X ∈ X, třída ze všech y takhle yRx je sada. (To dává smysl, pouze pokud jsou povoleny vztahy nad správnými třídami.) Například obvyklé řazení řadové číslovky je relace podobná množině, zatímco její inverzní> není.

Opodstatněné

každá neprázdná podmnožina S z X obsahuje a minimální prvek s ohledem na R. Opodstatněnost znamená sestupný stav řetězu (to znamená, že žádný nekonečný řetězec ... X_nR...Rx₃Rx₂Rx₁ může existovat). Pokud axiom závislé volby Předpokládá se, že obě podmínky jsou rovnocenné.^[29][30]

A předobjednávka je vztah, který je reflexivní a tranzitivní. A celková předobjednávka, také zvaný předobjednávka connectx nebo slabý řád, je vztah, který je reflexivní, tranzitivní a konexe.

A částečná objednávka, také zvaný objednat,^{[Citace je zapotřebí ]} je vztah, který je reflexivní, antisymetrický a tranzitivní. A přísné částečné pořadí, také zvaný přísný řád,^{[Citace je zapotřebí ]} je vztah, který je ireflexivní, antisymetrický a tranzitivní. A celková objednávka, také zvaný connectx objednávka, lineární pořadí, jednoduchá objednávkanebo řetěz, je vztah, který je reflexivní, antisymetrický, tranzitivní a konexe.^[31] A přísná celková objednávka, také zvaný přísná semiconnex objednávka, přísné lineární pořadí, přísná jednoduchá objednávkanebo přísný řetězec, je vztah, který je ireflexivní, antisymetrický, tranzitivní a semiconnex.

A vztah částečné ekvivalence je vztah, který je symetrický a tranzitivní. An vztah ekvivalence je vztah, který je reflexivní, symetrický a tranzitivní. Je to také vztah, který je symetrický, tranzitivní a sériový, protože tyto vlastnosti znamenají reflexivitu.

Důsledky a konflikty mezi vlastnostmi homogenních binárních vztahů
Implikace (modrá) a konflikty (červená) mezi vlastnostmi (žlutá) homogenních binárních vztahů. Například každý asymetrický vztah je ireflexivní ("ASym ⇒ Irrefl") a žádný vztah na neprázdné množině nemůže být irreflexivní i reflexivní ("Irrefl # Refl"). Vynechání červených okrajů má za následek a Hasseův diagram.

Operace

Li R je homogenní vztah k množině X pak každý z následujících je homogenní vztah X:

• Reflexní uzávěr: R⁼, definováno jako R⁼ = {(X, X) | X ∈ X} ∪ R nebo nejmenší reflexivní vztah X obsahující R. Lze prokázat, že se rovná průsečík všech reflexivních vztahů obsahujících R.
• Reflexní redukce: R^≠, definováno jako R^≠ = R {(X, X) | X ∈ X} nebo největší nereagující vztah skončil X obsaženo v R.
• Přechodné uzavření: R⁺, definovaný jako nejmenší přechodný vztah přes X obsahující R. To lze považovat za rovné průsečíku všech tranzitivních vztahů obsahujících R.
• Reflexní přechodné uzavření: R*, definováno jako R* = (R⁺)⁼, nejmenší předobjednávka obsahující R.
• Reflexní přechodný symetrický uzávěr: R^≡, definovaný jako nejmenší vztah ekvivalence přes X obsahující R.

Všechny operace definované v sekci Operace s binárními vztahy platí také pro homogenní vztahy.

Homogenní majetkové vztahy

	Reflexivita	Symetrie	Přechodnost	Souvislost	Symbol	Příklad
Směrovaný graf					→
Neusměrněný graf		Symetrický
Závislost	Reflexní	Symetrický
Turnaj	Nereagující	Antisymetrický				Pokyn na objednávku
Předobjednávka	Reflexní		Ano		≤	Přednost
Celková předobjednávka	Reflexní		Ano	Connex	≤
Částečná objednávka	Reflexní	Antisymetrický	Ano		≤	Podmnožina
Přísná částečná objednávka	Nereagující	Antisymetrický	Ano		<	Přísná podmnožina
Celková objednávka	Reflexní	Antisymetrický	Ano	Connex	≤	Abecední pořadí
Přísná celková objednávka	Nereagující	Antisymetrický	Ano	Semiconnex	<	Přísné abecední pořadí
Vztah částečné ekvivalence		Symetrický	Ano
Vztah ekvivalence	Reflexní	Symetrický	Ano		∼, ≡	Rovnost

Výčet

Počet zřetelných homogenních vztahů nad n- sada prvků je 2ⁿ² (sekvence A002416 v OEIS ):

Poznámky:

• Počet irreflexivních vztahů je stejný jako počet reflexivních vztahů.
• Počet přísné dílčí objednávky (irreflexivní tranzitivní vztahy) je stejný jako u částečných objednávek.
• Počet přísně slabých objednávek je stejný jako počet celkových předobjednávek.
• Celkové objednávky jsou dílčí objednávky, které jsou také celkovými předobjednávkami. Počet předobjednávek, které nejsou ani částečnou objednávkou, ani celkovou předobjednávkou, je tedy počet předobjednávek, minus počet částečných objednávek, minus počet celkových objednávek, plus počet celkových objednávek: 0, 0, 0, 3, respektive 85.
• Počet relací ekvivalence je počet oddíly, který je Bell číslo.

Homogenní vztahy lze seskupit do dvojic (relace, doplněk ), kromě toho pro n = 0 vztah je jeho vlastním doplňkem. Nesymetrické lze seskupit do čtyřnásobky (vztah, doplněk, inverzní, inverzní doplněk).

Příklady

• Objednávkové vztahy, počítaje v to přísné rozkazy:
  • Větší než
  • Větší nebo rovno
  • Méně než
  • Méně než nebo rovno
  • Rozdělí (rovnoměrně)
  • Podmnožina z
• Rovnocenné vztahy:
  • Rovnost
  • Paralelní s (pro afinní prostory )
  • Je v bijekce s
  • Izomorfní
• Toleranční vztah, reflexivní a symetrický vztah:
  • Závislostní vztah, vztah konečné tolerance
  • Vztah nezávislosti, doplněk nějakého vztahu závislosti
• Příbuzenské vztahy

Viz také

Poznámky

Reference

Bibliografie

• Codd, Edgar Frank (1990). Relační model pro správu databáze: verze 2 (PDF). Boston: Addison-Wesley. ISBN  978-0201141924.
• Enderton, Herbert (1977). Prvky teorie množin. Boston: Akademický tisk. ISBN  978-0-12-238440-0.
• Kilp, Mati; Knauer, Ulrich; Mikhalev, Alexander (2000). Monoidy, akty a kategorie: s aplikacemi na produkty a grafy věnců. Berlín: De Gruyter. ISBN  978-3-11-015248-7.
• Peirce, Charles Sanders (1873). „Popis notace pro logiku příbuzných, vyplývající ze zesílení koncepcí Booleova logického počtu“. Monografie Americké akademie umění a věd. 9 (2): 317–178. doi:10.2307/25058006. hdl:2027 / hvd.32044019561034. JSTOR  25058006. Citováno 2020-05-05.
• Schmidt, Gunther (2010). Relační matematika. Cambridge: Cambridge University Press. ISBN  978-0-521-76268-7.

externí odkazy

• Média související s Binární vztahy na Wikimedia Commons
• "Binární relace", Encyclopedia of Mathematics, Stiskněte EMS, 2001 [1994]