Connex vztah - Connex relation
Binární vztahy | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
A✓"označuje, že vlastnost sloupce je vyžadována v definici řádku." Například definice vztahu ekvivalence vyžaduje, aby byl symetrický. Všechny definice mlčky vyžadují tranzitivita a reflexivita. |
V matematice, a homogenní vztah se nazývá a konexe relace,[1] nebo vztah mající vlastnost souvislost, pokud nějakým způsobem souvisí se všemi dvojicemi prvků. Formálněji homogenní vztah R na setu X je connectx, když pro všechny X a y v X,
Homogenní vztah se nazývá a relace semiconnex,[1] nebo vztah mající vlastnost polokonkurence, pokud platí stejná vlastnost pro všechny páry odlišný elementy X ≠ y, nebo ekvivalentně, když pro všechny X a y v X,
Několik autorů definuje pouze vlastnost semiconnex a volá ji Connex spíše než semiconnex.[2][3][4]
Vlastnosti connectx pocházejí z teorie objednávek: Pokud částečná objednávka je také relací Conex, pak je celková objednávka. Proto se ve starších zdrojích říkalo, že souvislost relace má celek vlastnictví;[Citace je zapotřebí ] tato terminologie je však nevýhodná, protože může vést k záměně například s nesouvisejícím pojmem pravá totalita, také známý jako surjectivity. Někteří autoři nazývají vlastnost connectx relace úplnost.[Citace je zapotřebí ]
Charakterizace
Nechat R být homogenní vztah.
- R je spojení ↔ U ⊆ R ∪ RT ↔ R ⊆ RT ↔ R je asymetrický,
- kde U je univerzální vztah a RT je konverzní vztah z R.[1]
- R je semiconnex ↔ Já ⊆ R ∪ RT ↔ R ⊆ RT ∪ Já ↔ R je antisymetrický,
- kde Já je doplňkový vztah z vztah identity Já a RT je konverzní vztah z R.[1]
Vlastnosti
- The okraj vztah[5] E a turnaj graf G je vždy semiconnexový vztah na množině G's vrcholy.
- Relace Connex nemůže být symetrický, s výjimkou univerzálního vztahu.
- Relace je konexe tehdy a jen tehdy, je-li semiconnexní a reflexivní.[6]
- Semiconnex relace na množině X nemůže být antitransitivní, za předpokladu X má alespoň 4 prvky.[7] Na 3-prvkové sadě {A, b, C}, např. vztah {(A, b), (b, C), (C, A)} má obě vlastnosti.
- Li R je semiconnex vztah na X, pak všechny nebo všechny kromě jednoho, prvky X jsou v rozsah z R.[8] Podobně všechny nebo všechny kromě jednoho prvky prvku X jsou v doméně R.
Reference
- ^ A b C d Schmidt & Ströhlein 1993, str. 12.
- ^ Bram van Heuveln. "Sady, vztahy, funkce" (PDF). Troy, NY. Citováno 2018-05-28.[trvalý mrtvý odkaz ] Strana 4.
- ^ Carl Pollard. "Vztahy a funkce" (PDF). Ohio State University. Citováno 2018-05-28. Strana 7.
- ^ Felix Brandt; Markus Brill; Paul Harrenstein (2016). „Turnajová řešení“ (PDF). Ve Felix Brandt; Vincent Conitzer; Ulle Endriss; Jérôme Lang; Ariel D. Procaccia (eds.). Příručka výpočetní sociální volby. Cambridge University Press. ISBN 978-1-107-06043-2. Archivováno (PDF) z původního dne 8. prosince 2017. Citováno 22. ledna 2019. Strana 59, poznámka pod čarou 1.
- ^ formálně definováno vEw pokud hrana grafu vede od vrcholu proti na vrchol w
- ^ Pro jen když směru, obě vlastnosti následují triviálně. - Pro -li směr: kdy X≠y, pak xRy ∨ yRx vyplývá z vlastnosti semiconnex; když X=y, dokonce xRy vyplývá z reflexivity.
- ^ Jochen Burghardt (červen 2018). Jednoduché zákony o neprominentních vlastnostech binárních vztahů (technická zpráva). arXiv:1806.05036. Bibcode:2018arXiv180605036B. Lemma 8.2, str.8.
- ^ Li X, y∈Xěžel(R), pak xRy a yRx jsou nemožné, takže X=y vyplývá z vlastnosti semiconnex.
- Schmidt, Gunther; Ströhlein, Thomas (1993). Vztahy a grafy: Diskrétní matematika pro počítačové vědce. Berlín: Springer-Verlag. ISBN 978-3-642-77970-1.