Binær relation

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 22. august 2022; verifikation kræver 1 redigering .

Binær ( to-steds ) relation (korrespondance [1] [2] ) er en relation mellem to mængder og , det vil sige enhver delmængde af det kartesiske produkt af disse mængder: [3] . En binær relation på et sæt er enhver delmængde , sådanne binære relationer bruges oftest i matematik, især disse er lighed , ulighed , ækvivalens , ordensrelation . $EN$ $B$ $R\subseteq A\ gange B$ $EN$ $R\subseteq A^{2}=A\ gange A$

Relaterede definitioner

Mættet af alle første komponenter af par fra kaldes relationens domæne og betegnes som . [fire] $R\subseteq A\ gange B$ $R$ ${\mathrm {Dom}}\,R$

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

Mættet af alle andre komponenter af par fra kaldes relationens domæne og betegnes som . $R$ $R$ ${\mathrm {Im}}\,R$

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

[fire]

Inversion ( omvendt relation) er et sæt og betegnes som . $R$ $\{(x,\;y)\midt (y,\;x)\i R\}$ $R^{{-1}}$
Sammensætning(superposition) af binære relationer og er et sæt og betegnes som . [5] [6] $R$ $S$ $\{(x,\;y)\midt \eksisterer z(xRz\land zSy)\}$ $R\cirkel S$

Relationsegenskaber

En binær relation på et bestemt sæt kan have forskellige egenskaber, for eksempel: $R$ $M$

refleksivitet : , $\forall x\in M:(xRx)$
antirefleksivitet (irrefleksivitet): , $\forall x\in M:\neg (xRx)$
coreflexivity :, _ $\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)$
euklidisk :, _ $\forall x,y,z\in M:(xRy\wedge xRz\Rightarrow yRz)$
fuldstændighed (eller forbundethed [7] ): , $\forall x,y\in M:(xRy\lor yRx)$
forbundethed(eller svag forbindelse [7] ): , $\forall x,y\in M:(x\neq y\Rightarrow xRy\lor yRx)$
trikotomi: præcis et af de tre udsagn er sandt: , eller . $\foralt x,y\i M$ $xRy$ $yRx$ $x=y$

Relationstyper

En refleksiv transitiv relation kaldes en kvasi-ordensrelation .
En refleksiv symmetrisk transitiv relation kaldes en ækvivalensrelation .
En refleksiv antisymmetrisk transitiv relation kaldes en (delvis) ordensrelation .
En antirefleksiv antisymmetrisk transitiv relation kaldes en streng ordensrelation .
En komplet antisymmetrisk (eller gælder for enhver ) transitiv relation kaldes en lineær ordensrelation . $x,y$ $xRy$ $yRx$
Den antirefleksive antisymmetriske relation kaldes dominansrelationen .

Typer af binære relationer

Omvendt forhold[ specificer ] (relationen omvendt til ) er en to-steds relation bestående af par af elementer opnået ved at omarrangere elementparrene i den givne relation . Udpeget :. For en given relation og dens inverse er ligheden sand: . $R$ $(y,x)$ $(x, y)$ $R$ $R^{{-1}}$ $(R^{{-1}})^{{-1}}=R$
Gensidige relationer (gensidige relationer) er relationer, der er omvendte til hinanden. Rækkevidden for den ene af dem er den andens domæne, og den førstes domæne er den andens domæne.
En refleksiv relation er en to-steds relation , defineret på et bestemt sæt og karakteriseret ved, at for et hvilket som helst af dette sæt, er elementet i forhold til sig selv, det vil sige for ethvert element i dette sæt, . Eksempler på refleksive relationer: lighed , samtidighed , lighed . $R$ $x$ $x$ $R$ $x$ $xRx$
Anti-refleksiv relation (irrefleksiv relation; ligesom antisymmetri ikke falder sammen med asymmetri, falder irrefleksivitet ikke sammen med ikke-refleksivitet) er en binær relation defineret på et bestemt sæt og karakteriseret ved , at det ikke er sandt for noget element i dette sæt, at det er i forhold til sig selv (det er ikke rigtigt at ). $R$ $x$ $R$ $xRx$
En transitiv relation er en to-stedsrelation defineret på et bestemt sæt og adskiller sig i det for enhver af og følger ( ). Eksempler på transitive relationer: "større", "mindre", "lige", "lignende", "højere", "nord". $R$ $x,y,z$ $xRy$ $yRz$ $xRz$ $xRy\kile yRz\til xRz$
ikke-transitiv relation[ klargør ] - en to-stedsrelation defineret på et bestemt sæt og adskiller sig ved, at det for nogen af dette sæt ikke følger af og ( ). Et eksempel på en ikke-transitiv relation: "x er faderen til y" $R$ $x,y,z$ $xRy$ $yRz$ $xRz$ $\neg (xRy\kile yRz\til xRz)$
En symmetrisk relation er en binær relation , defineret på et bestemt sæt og adskiller sig ved, at for alle elementer og dette sæt, fra hvad der er til i relation , følger det og er i samme forhold til - . Et eksempel på symmetriske relationer kan være lighed, ækvivalensrelation , lighed , samtidighed. $R$ $x$ $y$ $x$ $y$ $R$ $y$ $x$ $xRy\til yRx$
En antisymmetrisk relation er en binær relation defineret på et bestemt sæt og adskiller sig i den for enhver og fra og den følger (dvs. og udføres kun samtidigt for medlemmer, der er lig med hinanden). $R$ $x$ $y$ $xRy$ $yRx$ $x=y$ $R$ $R^{{-1}}$
En asymmetrisk relation er en binær relation defineret på et bestemt sæt og adskiller sig i det for enhver, og det følger af . Eksempel: større end (>) og mindre end (<) relationer. $R$ $x$ $y$ $xRy$ $\neg yRx$
En ækvivalensrelation er en binær relation mellem objekterne, og som er både refleksiv, symmetrisk og transitiv. Eksempler: lighed, ækvivalens af to sæt, lighed , samtidighed . $R$ $x$ $y$
En ordensrelation er en relation, der kun har nogle af de tre egenskaber ved en ækvivalensrelation: en relation, der er refleksiv og transitiv, men ikke-symmetrisk (f.eks. "ikke mere") danner en ikke-streng orden, og en relation der er transitiv, men ikke-refleksiv og ikke-symmetrisk (for eksempel "mindre") danner en streng rækkefølge.
En tolerancerelation er en binær relation, der tilfredsstiller egenskaberne refleksivitet og symmetri, men som ikke nødvendigvis er transitiv. Ækvivalensforholdet er således et særligt tilfælde af tolerance.
En funktion af en variabel er en binær relation , defineret på et bestemt sæt, der adskiller sig ved, at hver værdi af relationen kun svarer til en enkelt værdi . Relationsfunktionalitetsegenskaben skrives som et aksiom: . $R$ $x$ $xRy$ $y$ $R$ $(xRy\wedge xRz)\to (y\equiv z)$
En bijektion (en-til-en-relation) er en binær relation defineret på et bestemt sæt, kendetegnet ved, at hver værdi i den svarer til en enkelt værdi , og hver værdi svarer til en enkelt værdi . $R$ $x$ $y$ $y$ $x$

Operationer på relationer

Da relationerne defineret på et fast sæt sæt er delmængder af mængden , danner helheden af alle disse relationer en boolsk algebra med hensyn til operationerne af forening, skæring og addition af relationer. Især for vilkårlige : $EN$ $B$ $A\ gange B$ $a\i A$ $b\i B$

a\,(R\kop S)\,b\venstrepil a\,R\,b\vee a\,S\,b

a\,(R\cap S)\,b\venstrehøjrepil a\,R\,b\kile a\,S\,b

a\,\overline {R}\,b\venstrehøjrepil \neg a\,R\,b

Ofte taler man i stedet for forening, skæring og tilføjelse af relationer om deres disjunktion, konjunktion og negation.

For eksempel, , , det vil sige, at foreningen af en streng ordensrelation med en lighedsrelation falder sammen med en ikke-streng ordensrelation, og deres skæringspunkt er tom. $({=})\kop ({<})=({\leqslant })$ $({=})\cap ({<})=\varnothing$

Ud over de nævnte er operationerne med inversion og multiplikation af relationer, defineret som følger, også vigtige. Hvis , så er den omvendte relation relationen defineret på parret og består af de par som . For eksempel . $R\subseteq A\ gange B$ $R^{{-1}}$ $B$ $EN$ $(b,a)$ $a\,R\,b$ $({<})^{-1}=({>})$

Lad ,. _ En sammensætning (eller et produkt) af relationer er en relation sådan, at: $R\subseteq A\ gange B$ $S\subseteq B\ gange C$ $R$ $S$ $R\circ S\subseteq A\times C$

a\,(R\circ S)\,c\Leftrightarrow \eksisterer b\i B:\,a\,(R)\,b\wedge b\,(S)\,c

For eksempel, for en streng ordensrelation på mængden af naturlige tal, er dens multiplikation af sig selv defineret som følger: . $a({<})({<})b\venstrehøjrepil a+1<b$

Binære relationer og kaldes permutable hvis . For enhver binær relation defineret på , er der , hvor symbolet angiver lighed defineret på . Men ligestilling er ikke altid retfærdig. $R$ $S$ $RS=SR$ $R$ $EN$ $R{\mathsf {Id}}_{A}={\mathsf {Id}}_{A}R$ ${\mathsf {Id}}_{A}$ $EN$ $RR^{{-1}}={\mathsf {Id}}$

Følgende identiteter gælder:

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

Analoger af de sidste to identiteter til skæringspunktet mellem relationer finder ikke sted.

Noter

↑ Tsalenko M. Sh . Korrespondance // Mathematical Encyclopedia. - 1985. - V. 5 (Slu-Ya) . - S. 77 .
↑ Overholdelse . Stor russisk encyklopædi . (ubestemt)
↑ Kostrikin A. I. Introduktion til algebra. Grundlæggende om algebra. . - M .: Fizmatlit , 1994. - S. 47 -48. - 320 sek. — ISBN 5-02-014644-7 .
↑ 1 2 Kulikov L.Ya. Kapitel to. Mængder og relationer // Algebra og talteori: Proc. manual for pædagogiske institutioner. - M . : Højere skole , 1979. - S. 50. - 559 s.
↑ Yerusalimsky Ya.M. 4. Sammensætning af binære relationer. Boolesk produkt af matricer // Diskret matematik: teori, problemer, anvendelser. — 3. udgave. - M . : Vuzovskaya bog, 2000. - S. 112. - 280 s. — ISBN 5-89522-034-7 .
↑ Novikov F.A. 1.5.4. Sammensætning af relationer // Diskret matematik for programmører. - Sankt Petersborg. : Peter , 2000. - S. 34. - 304 s. - ISBN 5-272-00183-4 .
↑ 1 2 Dubov Yu. A., Travkin SI., Yakimets V. N. Multikriteriemodeller til dannelse og valg af systemmuligheder. — M.: Nauka, 1986. (s. 48)

Litteratur

Maltsev, A. I. Algebraiske systemer. — M .: Nauka , 1970. — 392 s. - 17.500 eksemplarer.

Aleskerov F.T., Khabina E.L., Schwartz D.A. Binære relationer, grafer og kollektive løsninger. - M . : Lærebøger fra den højere økonomiskole, 2006. - 300 s.

Pukhnachev Yu. V., Popov Yu. P. Bog. 1: Mængder, afbildninger, relationer, sekvenser, serier, funktioner, funktioners egenskaber, differential- og integralregning, funktioner af mange variable // Matematik uden formler. - Ed. 6. rev. - M. : URSS, 2017. - 231 s. — ISBN 978-5-9710-3871-9 .