Binär relation

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 22 augusti 2022; verifiering kräver 1 redigering .

Binär ( tvåställs ) relation (korrespondens [1] [2] ) är en relation mellan två mängder och , det vill säga vilken delmängd som helst av den kartesiska produkten av dessa mängder: [3] . En binär relation på en mängd är vilken delmängd som helst , sådana binära relationer används oftast i matematik, i synnerhet dessa är likhet , ojämlikhet , ekvivalens , ordningsrelation . $A$ $B$ $R\subseteq A\ gånger B$ $A$ $R\subseteq A^{2}=A\ gånger A$

Relaterade definitioner

Mängden av alla första komponenter av par från kallas domänen av relationen och betecknas som . [fyra] $R\subseteq A\ gånger B$ $R$ ${\mathrm {Dom}}\,R$

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

Uppsättningen av alla andra komponenter av par från kallas domänen av relationen och betecknas som . $R$ $R$ ${\mathrm {Im}}\,R$

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

[fyra]

Inversion ( omvänd relation) är en uppsättning och betecknas som . $R$ $\{(x,\;y)\mid (y,\;x)\i R\}$ $R^{{-1}}$
Sammansättning(superposition) av binära relationer och är en mängd och betecknas som . [5] [6] $R$ $S$ $\{(x,\;y)\mid \exists z(xRz\land zSy)\}$ $R\cirkel S$

Relationsegenskaper

En binär relation på en viss mängd kan ha olika egenskaper, till exempel: $R$ $M$

reflexivitet : , $\forall x\in M:(xRx)$
antireflexivitet (irreflexivitet): , $\forall x\in M:\neg (xRx)$
kärnflexibilitet : , $\forall x,y\in M:(xRy\Rightarrow x=y)$
symmetri : , $\forall x,\;y\in M:(xRy\Rightarrow yRx)$
antisymmetri : , $\forall x,\;y\in M:(xRy\wedge yRx\Rightarrow x=y)$
asymmetri : , $\forall x,\;y\in M:(xRy\Rightarrow \neg (yRx))$
transitivitet : , $\forall x,\;y,\;z\in M:(xRy\wedge yRz\Rightarrow xRz)$
euklidiskt : , $\forall x,y,z\in M:(xRy\wedge xRz\Rightarrow yRz)$
fullständighet (eller anknytning [7] ): , $\forall x,y\in M:(xRy\lor yRx)$
samhörighet(eller svag anslutning [7] ): , $\forall x,y\in M:(x\neq y\Rightarrow xRy\lor yRx)$
trikotomi: exakt ett av de tre påståendena är sant: , eller . $\forall x,y\i M$ $xRy$ $yRx$ $x=y$

Typer av relationer

En reflexiv transitiv relation kallas en kvasiordningsrelation .
En reflexiv symmetrisk transitiv relation kallas en ekvivalensrelation .
En reflexiv antisymmetrisk transitiv relation kallas en (partiell) ordningsrelation .
En antireflexiv antisymmetrisk transitiv relation kallas en strikt ordningsrelation .
En fullständig antisymmetrisk (eller gäller för någon ) transitiv relation kallas en linjär ordningsrelation . $x,y$ $xRy$ $yRx$
Den antireflexiva antisymmetriska relationen kallas dominansrelationen .

Typer av binära relationer

Omvänt förhållande[ specificera ] (relationen invers till ) är en tvåplatsrelation som består av par av element som erhålls genom att omordna elementparen i den givna relationen . Utsedda: . För en given relation och dess invers är likheten sann: . $R$ $(y,x)$ $(x, y)$ $R$ $R^{{-1}}$ $(R^{{-1}})^{{-1}}=R$
Ömsesidiga förhållanden (ömsesidiga förhållanden) är förhållanden som är omvända till varandra. Räckvidden för en av dem är den andras domän, och den förstas domän är den andras domän.
En reflexiv relation är en tvåplatsrelation , definierad på en viss mängd och kännetecknad av att för vilken som helst av denna mängd är elementet i förhållande till sig självt, det vill säga för vilket element som helst i denna mängd, . Exempel på reflexiva relationer: jämlikhet , samtidighet , likhet . $R$ $x$ $x$ $R$ $x$ $xRx$
Antireflexiv relation (irreflexiv relation; precis som antisymmetri inte sammanfaller med asymmetri, sammanfaller inte irreflexivitet med icke-reflexivitet) är en binär relation definierad på en viss mängd och kännetecknad av att det inte är sant för något element i denna mängd som det är i förhållande till sig själv (det är inte sant att ). $R$ $x$ $R$ $xRx$
En transitiv relation är en tvåställsrelation definierad på en viss mängd och som skiljer sig i den för någon av och följer ( ). Exempel på transitiva relationer: "större", "mindre", "lika", "liknande", "högre", "norr". $R$ $x,y,z$ $xRy$ $yRz$ $xRz$ $xRy\kil yRz\till xRz$
icke-transitiv relation[ klargöra ] - en tvåställsrelation definierad på en viss mängd och som skiljer sig genom att den för någon av denna mängd inte följer av och ( ). Ett exempel på en icke-transitiv relation: "x är fadern till y" $R$ $x,y,z$ $xRy$ $yRz$ $xRz$ $\neg (xRy\kil yRz\till xRz)$
En symmetrisk relation är en binär relation , definierad på en viss mängd och skiljer sig i att för alla element och denna mängd, från vad som är till i relation , det följer att och är i samma relation till - . Ett exempel på symmetriska samband kan vara likhet, ekvivalensrelation , likhet , simultanitet. $R$ $x$ $y$ $x$ $y$ $R$ $y$ $x$ $xRy\till yRx$
En antisymmetrisk relation är en binär relation definierad på en viss uppsättning och som skiljer sig i den för någon och från och den följer (det vill säga och utförs samtidigt endast för medlemmar lika med varandra). $R$ $x$ $y$ $xRy$ $yRx$ $x=y$ $R$ $R^{{-1}}$
En asymmetrisk relation är en binär relation definierad på en viss mängd och som skiljer sig åt i det för någon och den följer av . Exempel: relationer större än (>) och mindre än (<). $R$ $x$ $y$ $xRy$ $\neg yRx$
En ekvivalensrelation är en binär relation mellan objekten och som är både reflexiv, symmetrisk och transitiv. Exempel: likhet, likvärdighet av två uppsättningar, likhet , samtidighet . $R$ $x$ $y$
En ordningsrelation är en relation som bara har några av de tre egenskaperna hos en ekvivalensrelation: en relation som är reflexiv och transitiv, men icke-symmetrisk (till exempel "inte mer") bildar en icke-strikt ordning, och en relation som är transitiv, men icke-reflexiv och icke-symmetrisk (till exempel "mindre") bildar en strikt ordningsföljd.
En toleransrelation är en binär relation som uppfyller egenskaperna för reflexivitet och symmetri, men som inte nödvändigtvis är transitiv. Således är ekvivalensrelationen ett specialfall av tolerans.
En funktion av en variabel är en binär relation , definierad på en viss uppsättning, som skiljer sig åt genom att varje värde av relationen endast motsvarar ett enda värde . Relationsfunktionalitetsegenskapen skrivs som ett axiom: . $R$ $x$ $xRy$ $y$ $R$ $(xRy\wedge xRz)\to (y\equiv z)$
En bijektion (en-till-en-relation) är en binär relation definierad på en viss mängd, kännetecknad av att varje värde i den motsvarar ett enda värde och varje värde motsvarar ett enda värde . $R$ $x$ $y$ $y$ $x$

Operationer på relationer

Eftersom relationerna som definieras på ett fast par av mängder är delmängder av mängden , bildar helheten av alla dessa relationer en boolesk algebra med avseende på operationerna av förening, skärning och addition av relationer. I synnerhet, för godtyckliga , : $A$ $B$ $A\ gånger B$ $a\i A$ $b\i B$

a\,(R\cup S)\,b\vänsterhögerpil a\,R\,b\vee a\,S\,b

a\,(R\cap S)\,b\vänsterhögerpil a\,R\,b\kil a\,S\,b

a\,\overline {R}\,b\Leftrightarrow \neg a\,R\,b

Ofta talar man om deras disjunktion, konjunktion och negation istället för förening, skärning och addition av relationer.

Till exempel, , , det vill säga föreningen av en strikt ordningsrelation med en likhetsrelation sammanfaller med en icke-strikt ordningsrelation, och deras skärningspunkt är tom. $({=})\kopp ({<})=({\leqslant })$ $({=})\cap ({<})=\varnothing$

Utöver de listade är operationerna inversion och multiplikation av relationer, definierade enligt följande, också viktiga. Om , då är den omvända relationen den relation som definieras på paret och består av de par som . Till exempel . $R\subseteq A\ gånger B$ $R^{{-1}}$ $B$ $A$ $(b,a)$ $a\,R\,b$ $({<})^{-1}=({>})$

Låt , . En sammansättning (eller produkt) av relationer är en relation sådan att: $R\subseteq A\ gånger B$ $S\subseteq B\ gånger C$ $R$ $S$ $R\circ S\subseteq A\times C$

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

Till exempel, för en strikt ordningsrelation på mängden naturliga tal, definieras dess multiplikation med sig själv enligt följande: . $a({<})({<})b\Leftrightarrow a+1<b$

Binära relationer och kallas permuterbara om . För alla binära relationer som definieras på , finns det , där symbolen anger likhet definierad på . Men jämställdhet är inte alltid rättvist. $R$ $S$ $RS=SR$ $R$ $A$ $R{\mathsf {Id}}_{A}={\mathsf {Id}}_{A}R$ ${\mathsf {Id}}_{A}$ $A$ $RR^{{-1}}={\mathsf {Id}}$

Följande identiteter gäller:

$R(ST)=(RS)T$ ,
$(RS)^{{-1}}=S^{{-1}}R^{{-1}}$ ,
$\overline {R^{{-1}}}={\overline {R}}^{{-1}}$ ,
$(R\kopp S)^{{-1}}=R^{{-1}}\kopp S^{{-1}}$ ,
$(R\cap S)^{{-1}}=R^{{-1}}\cap S^{{-1}}$ ,
$R(S\kopp T)=RS\kopp RT$ ,
$(R\kopp S)T=RT\kopp ST$ .

Analoger av de två sista identiteterna för korsningen av relationer äger inte rum.

Anteckningar

↑ Tsalenko M. Sh . Korrespondens // Mathematical Encyclopedia. - 1985. - V. 5 (Slu-Ya) . - S. 77 .
↑ Överensstämmelse . Stora ryska encyklopedin . (obestämd)
↑ Kostrikin A. I. Introduktion till algebra. Grunderna i algebra. . - M .: Fizmatlit , 1994. - S. 47 -48. — 320 s. — ISBN 5-02-014644-7 .
↑ 1 2 Kulikov L.Ya. Kapitel två. Mängder och relationer // Algebra och talteori: Proc. handbok för pedagogiska institut. - M . : Högre skola , 1979. - S. 50. - 559 sid.
↑ Yerusalimsky Ya.M. 4. Sammansättning av binära relationer. Boolesk produkt av matriser // Diskret matematik: teori, problem, tillämpningar. — 3:e upplagan. - M . : Vuzovskaya bok, 2000. - S. 112. - 280 sid. — ISBN 5-89522-034-7 .
↑ Novikov F.A. 1.5.4. Sammansättning av relationer // Diskret matematik för programmerare. - St Petersburg. : Peter , 2000. - S. 34. - 304 sid. - ISBN 5-272-00183-4 .
↑ 1 2 Dubov Yu. A., Travkin SI., Yakimets V. N. Multikriteriemodeller för bildning och val av systemalternativ. — M.: Nauka, 1986. (s. 48)

Litteratur

Maltsev, A. I. Algebraiska system. — M .: Nauka , 1970. — 392 sid. - 17 500 exemplar.

Aleskerov F.T., Khabina E.L., Schwartz D.A. Binära relationer, grafer och kollektiva lösningar. - M . : Läroböcker från Högre Handelshögskolan, 2006. - 300 sid.

Pukhnachev Yu. V., Popov Yu. P. Bok. 1: Mängder, avbildningar, relationer, sekvenser, serier, funktioner, funktioners egenskaper, differential- och integralkalkyl, funktioner av många variabler // Matematik utan formler. - Ed. 6:e, rev. - M. : URSS, 2017. - 231 sid. — ISBN 978-5-9710-3871-9 .