Bináris reláció

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2022. augusztus 22-én felülvizsgált verziótól ; az ellenőrzéshez 1 szerkesztés szükséges .

A bináris ( kéthelyes ) reláció (megfelelés [1] [2] ) két halmaz és e halmazok derékszögű szorzatának bármely részhalmaza közötti reláció : [ 3] . A halmazon lévő bináris reláció bármely részhalmaz , az ilyen bináris relációkat leggyakrabban a matematikában használják, különösen ezek az egyenlőség , egyenlőtlenség , ekvivalencia , sorrendi reláció . $A$ $B$ $R\subseteq A\times B$ $A$ $R\subseteq A^{2}=A\szor A$

Kapcsolódó definíciók

Az innen származó párok összes első összetevőjének halmazát a reláció tartományának nevezzük , és jelölése . [négy] $R\subseteq A\times B$ $R$ ${\mathrm {Dom}}\,R$

{\mathrm {Dom}}\,R=\{x\mid \exists y((x,\;y)\in R)\}.

Az innen származó párok összes második komponensének halmazát a reláció tartományának nevezzük , és jelölése . $R$ $R$ ${\mathrm {Im}}\,R$

{\mathrm {Im}}\,R=\{y\mid \exists x((x,\;y)\in R)\}.

[négy]

Inverzió ( fordított reláció) egy halmaz , és jelölése . $R$ $\{(x,\;y)\mid (y,\;x)\in R\}$ $R^{{-1}}$
Fogalmazásbináris relációk (szuperpozíciója) és halmaz , és jelölése . [5] [6] $R$ $S$ $\{(x,\;y)\mid \exists z(xRz\land zSy)\}$ $R\circ S$

Kapcsolat tulajdonságai

Egy bizonyos halmazon lévő bináris relációnak különböző tulajdonságai lehetnek, például: $R$ $M$

reflexivitás : , $\forall x\in M:(xRx)$
antireflexivitás (irreflexivitás): , $\forall x\in M:\neg (xRx)$
coreflexivitás : , $\forall x,y\in M:(xRy\Rightarrow x=y)$
szimmetria :, _ $\forall x,\;y\in M:(xRy\Rightarrow yRx)$
antiszimmetria : , $\forall x,\;y\in M:(xRy\wedge yRx\Rightarrow x=y)$
aszimmetria : , $\forall x,\;y\in M:(xRy\Rightarrow \neg (yRx))$
tranzitivitás : , $\forall x,\;y,\;z\in M:(xRy\wedge yRz\Rightarrow xRz)$
euklideszi : , $\forall x,y,z\in M:(xRy\wedge xRz\Rightarrow yRz)$
teljesség (vagy összekapcsoltság [7] ): , $\forall x,y\in M:(xRy\vagy yRx)$
összekapcsoltság(vagy gyenge kapcsolat [7] ): , $\forall x,y\in M:(x\neq y\Rightarrow xRy\lor yRx)$
hármas felosztás: a három állítás közül pontosan egy igaz: , vagy . $\forall x,y\in M$ $xRy$ $yRx$ $x=y$

Kapcsolatok típusai

A reflexív tranzitív relációt kvázi-rendű relációnak nevezzük .
A reflexív szimmetrikus tranzitív relációt ekvivalenciarelációnak nevezzük .
A reflexív antiszimmetrikus tranzitív relációt (rész)rendű relációnak nevezzük .
Az antireflexív antiszimmetrikus tranzitív relációt szigorú rendű relációnak nevezzük .
A teljes antiszimmetrikus (vagy bármely ) tranzitív relációt lineáris sorrendű relációnak nevezzük . $x,y$ $xRy$ $yRx$
Az antireflexív antiszimmetrikus relációt dominancia relációnak nevezzük .

A bináris relációk típusai

Fordított összefüggés[ specifikáció ] (a reláció inverze ) egy kéthelyes reláció, amely az adott reláció elempárjainak átrendezésével kapott elempárokból áll . Kijelölve: . Adott relációra és inverzére igaz az egyenlőség: . $R$ $(y,x)$ $(x, y)$ $R$ $R^{{-1}}$ $(R^{{-1}})^{{-1}}=R$
A kölcsönös kapcsolatok (reciprok kapcsolatok) olyan kapcsolatok, amelyek egymással fordítottak. Az egyik tartománya a másiké, az elsőé pedig a másiké.
A reflexív reláció egy kéthelyes reláció , amely egy bizonyos halmazon van definiálva, és azzal jellemezve, hogy e halmaz bármelyikénél az elem önmagához, vagyis a halmaz bármely eleméhez viszonyítva van . Példák reflexív összefüggésekre: egyenlőség , egyidejűség , hasonlóság . $R$ $x$ $x$ $R$ $x$ $xRx$
Az antireflexív reláció (irreflexív reláció; ahogy az antiszimmetria nem esik egybe az aszimmetriával, az irreflexivitás nem esik egybe a nem-reflexivitással) egy bizonyos halmazon meghatározott bináris reláció, amelyre jellemző, hogy ennek a halmaznak egyetlen elemére sem igaz, hogy önmagához viszonyítva van (nem igaz, hogy ). $R$ $x$ $R$ $xRx$
A tranzitív reláció egy kéthelyes reláció, amely egy bizonyos halmazon van definiálva, és abban különbözik, hogy a és a következő ( ) bármelyikére vonatkozik . Példák tranzitív kapcsolatokra: "nagyobb", "kevésbé", "egyenlő", "hasonló", "magasabb", "északi". $R$ $x,y,z$ $xRy$ $yRz$ $xRz$ $xRy\ék yRz\to xRz$
nem tranzitív reláció[ tisztázni ] - egy kéthelyes reláció , amely egy bizonyos halmazon van definiálva, és abban különbözik, hogy ennek a halmaznak egyikére sem következik és ( ). Példa egy nem tranzitív relációra: "x az y apja" $R$ $x,y,z$ $xRy$ $yRz$ $xRz$ $\neg (xRy\ék yRz\–xRz)$
A szimmetrikus reláció egy bináris reláció , amely egy bizonyos halmazon van definiálva, és abban különbözik, hogy bármely elemre és erre a halmazra a relációban való mitől az következik, hogy és ugyanabban a relációban van - . A szimmetrikus összefüggésekre példa lehet az egyenlőség, az ekvivalenciareláció , a hasonlóság , az egyidejűség. $R$ $x$ $y$ $x$ $y$ $R$ $y$ $x$ $xRy\to yRx$
Az antiszimmetrikus reláció egy bizonyos halmazon definiált bináris reláció , amely abban különbözik, hogy a tetszőleges és az abból következik (vagyis csak az egymással egyenlő tagokra hajtják végre egyidejűleg). $R$ $x$ $y$ $xRy$ $yRx$ $x=y$ $R$ $R^{{-1}}$
Az aszimmetrikus reláció egy bináris reláció , amely egy bizonyos halmazon van definiálva, és abban különbözik bármelyikhez , és ebből következik . Példa: nagyobb, mint (>) és kisebb, mint (<) kapcsolatok. $R$ $x$ $y$ $xRy$ $\neg yRx$
Az ekvivalenciareláció az objektumok közötti bináris reláció , amely egyszerre reflexív, szimmetrikus és tranzitív. Példák: egyenlőség, két halmaz egyenértékűsége , hasonlóság , egyidejűség . $R$ $x$ $y$
A sorrendi reláció olyan reláció, amely az ekvivalenciareláció három tulajdonságának csak egy részét tartalmazza: egy reflexív és tranzitív, de nem szimmetrikus reláció (például „nincs többé”) nem szigorú sorrendet alkot, és egy reláció amely tranzitív, de nem reflexív és nem szimmetrikus (például „kevesebb”) szigorú rendet alkot.
A toleranciareláció olyan bináris reláció, amely kielégíti a reflexivitás és a szimmetria tulajdonságait, de nem feltétlenül tranzitív. Így az ekvivalenciareláció a tolerancia speciális esete.
Egy változó függvénye egy bináris reláció , amely egy bizonyos halmazon van definiálva, és abban különbözik, hogy a reláció minden értéke csak egyetlen értéknek felel meg . A relációs funkcionalitás tulajdonság axiómaként van felírva: . $R$ $x$ $xRy$ $y$ $R$ $(xRy\ék xRz)\to (y\equiv z)$
A bijekció (egy az egyhez reláció) egy bizonyos halmazon meghatározott bináris reláció, azzal jellemezve, hogy benne minden érték egyetlen értéknek , minden érték pedig egyetlen értéknek felel meg . $R$ $x$ $y$ $y$ $x$

Műveletek relációkon

Mivel egy rögzített halmazpáron definiált relációk a halmaz részhalmazai , így ezeknek a relációknak az összessége egy Boole-algebrát alkot a relációk egyesülési, metszésponti és összeadási műveletei tekintetében. Különösen az önkényes , : $A$ $B$ $A\-szer B$ $a\in A$ $b\in B$

a\,(R\cup S)\,b\bal jobbra nyíl a\,R\,b\vee a\,S\,b

a\,(R\cap S)\,b\balra jobbra nyíl a\,R\,b\ék a\,S\,b

a\,\overline {R}\,b\balra jobbra \neg a\,R\,b

A relációk egyesülése, metszéspontja és összeadása helyett gyakran diszjunkciójukról, konjunkciójukról és tagadásukról beszélünk.

Például , , vagyis a szigorú rendű reláció uniója egy egyenlőségi relációval egybeesik egy nem szigorú rendű relációval, és a metszéspontjuk üres. $({=})\kupa ({<})=({\leqslant })$ $({=})\cap ({<})=\varnothing$

A felsoroltakon kívül fontosak a relációk inverziós és szorzási műveletei is, amelyeket az alábbiak szerint definiálunk. Ha , akkor az inverz reláció a páron meghatározott reláció , amely azokból a párokból áll , amelyekre . Például, . $R\subseteq A\times B$ $R^{{-1}}$ $B$ $A$ $(b,a)$ $a\,R\,b$ $({<})^{-1}=({>})$

Hagyjuk , . A relációk összetétele (vagy terméke) olyan reláció , amely: $R\subseteq A\times B$ $S\subseteq B\x C$ $R$ $S$ $R\circ S\subseteq A\times C$

a\,(R\circ S)\,c\balra jobbra \exists b\in B:\,a\,(R)\,b\wedge b\,(S)\,c

Például a természetes számok halmazán lévő szigorú sorrendű reláció esetén annak önmagával való szorzását a következőképpen határozzuk meg: . $a({<})({<})b\Baljobbra nyíl a+1<b$

A és bináris relációkat permutálhatónak nevezzük, ha . Bármely -n definiált bináris relációhoz létezik , ahol a szimbólum a -n definiált egyenlőséget jelöli . Az egyenlőség azonban nem mindig igazságos. $R$ $S$ $RS=SR$ $R$ $A$ $R{\mathsf {Id}}_{A}={\mathsf {Id}}_{A}R$ ${\mathsf {Id}}_{A}$ $A$ $RR^{{-1}}={\mathsf {Id}}$

A következő személyazonosságok érvényesek:

$R(ST)=(RS)T$ ,
$(RS)^{{-1}}=S^{{-1}}R^{{-1}}$ ,
$\overline {R^{{-1}}}={\overline {R}}^{{-1}}$ ,
$(R\kupa S)^{{-1}}=R^{{-1}}\csésze S^{{-1}}$ ,
$(R\cap S)^{{-1}}=R^{{-1}}\cap S^{{-1}}$ ,
$R(S\cup T)=RS\cup RT$ ,
$(R\kupa S)T=RT\csésze ST$ .

Az utolsó két identitás analógjai a relációk metszéspontjára nem jönnek létre.

Jegyzetek

↑ Tsalenko M. Sh . Levelezés // Mathematical Encyclopedia. - 1985. - V. 5 (Slu-Ya) . - S. 77 .
↑ Megfelelés . Nagy Orosz Enciklopédia . (határozatlan)
↑ Kostrikin A. I. Bevezetés az algebrába. Az algebra alapjai. . - M .: Fizmatlit , 1994. - S. 47 -48. — 320 s. — ISBN 5-02-014644-7 .
↑ 1 2 Kulikov L.Ya. Második fejezet. Halmazok és relációk // Algebra és számelmélet: Proc. kézikönyv a pedagógiai intézetek számára. - M . : Felsőiskola , 1979. - S. 50. - 559 p.
↑ Yerusalimsky Ya.M. 4. Bináris relációk összetétele. Mátrixok logikai szorzata // Diszkrét matematika: elmélet, problémák, alkalmazások. — 3. kiadás. - M . : Vuzovskaya könyv, 2000. - S. 112. - 280 p. — ISBN 5-89522-034-7 .
↑ Novikov F.A. 1.5.4. Relációk összetétele // Diszkrét matematika programozóknak. - Szentpétervár. : Péter , 2000. - S. 34. - 304 p. - ISBN 5-272-00183-4 .
↑ 1 2 Dubov Yu. A., Travkin SI., Yakimets V. N. Többszempontú modellek a rendszerlehetőségek kialakításához és kiválasztásához. — M.: Nauka, 1986. (48. o.)

Irodalom

Maltsev, A. I. Algebrai rendszerek. — M .: Nauka , 1970. — 392 p. - 17 500 példány.

Aleskerov F.T., Khabina E.L., Schwartz D.A. Bináris relációk, gráfok és kollektív megoldások. - M . : Közgazdasági Felsőoktatási Iskola Tankönyvei, 2006. - 300 p.

Pukhnachev Yu. V., Popov Yu. P. könyv. 1: Halmazok, leképezések, relációk, sorozatok, sorozatok, függvények, függvények tulajdonságai, differenciál- és integrálszámítás, sok változó függvényei // Matematika képletek nélkül. - Szerk. 6., rev. - M. : URSS, 2017. - 231 p. — ISBN 978-5-9710-3871-9 .