Relație binară

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 22 august 2022; verificarea necesită 1 editare .

Relația binară ( cu două locuri ) (corespondența [1] [2] ) este o relație între două mulțimi și , adică orice submulțime a produsului cartezian al acestor mulțimi: [3] . O relație binară pe o mulțime este orice submulțime , astfel de relații binare sunt cel mai adesea folosite în matematică, în special, acestea sunt egalitatea , inegalitatea , echivalența , relația de ordine . $A$ $B$ $R\subseteq A\time B$ $A$ $R\subseteq A^{2}=A\ori A$

Definiții înrudite

Mulțimea tuturor primelor componente ale perechilor din se numește domeniul relației și se notează ca . [patru] $R\subseteq A\time B$ $R$ ${\mathrm {Dom}}\,R$

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

Mulțimea tuturor componentelor secunde ale perechilor din se numește domeniul relației și se notează ca . $R$ $R$ ${\mathrm {Im}}\,R$

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

[patru]

Inversare ( relație inversă) este o mulțime și se notează ca . $R$ $\{(x,\;y)\mid (y,\;x)\în R\}$ $R^{{-1}}$
Compoziţie(suprapunerea) relațiilor binare și este o mulțime și se notează ca . [5] [6] $R$ $S$ $\{(x,\;y)\mid \exists z(xRz\land zSy)\}$ $R\circ S$

Proprietăți ale relației

O relație binară pe o anumită mulțime poate avea proprietăți diferite, de exemplu: $R$ $M$

reflexivitate : , $\forall x\in M:(xRx)$
antireflexivitate (ireflexivitate): , $\forall x\in M:\neg (xRx)$
coreflexivitate : , $\forall x,y\in M:(xRy\Rightarrow x=y)$
simetrie :, _ $\forall x,\;y\in M:(xRy\Rightarrow yRx)$
antisimetrie : , $\forall x,\;y\in M:(xRy\wedge yRx\Rightarrow x=y)$
asimetrie :, _ $\forall x,\;y\in M:(xRy\Rightarrow \neg (yRx))$
tranzitivitate : , $\forall x,\;y,\;z\in M:(xRy\wedge yRz\Rightarrow xRz)$
euclidian : , $\forall x,y,z\in M:(xRy\wedge xRz\Rightarrow yRz)$
completitudine (sau conexiune [7] ): , $\forall x,y\in M:(xRy\lor yRx)$
conexiunea(sau conexiune slabă [7] ): , $\forall x,y\in M:(x\neq y\Rightarrow xRy\lor yRx)$
tricotomie: exact una dintre cele trei afirmații este adevărată: , sau . $\forall x,y\în M$ $xRy$ $yRx$ $x=y$

Tipuri de relații

O relație tranzitivă reflexivă se numește relație de cvasi-ordin .
O relație tranzitivă simetrică reflexivă se numește relație de echivalență .
O relație tranzitivă antisimetrică reflexivă se numește relație de ordin (parțial) .
O relație tranzitivă antireflexivă antisimetrică se numește relație de ordine strictă .
O relație tranzitivă completă antisimetrică (sau valabilă pentru orice ) se numește relație de ordin liniar . $X y$ $xRy$ $yRx$
Relația antisimetrică antireflexivă se numește relație de dominanță .

Tipuri de relații binare

Relație inversă[ precizați ] (relația inversă cu ) este o relație de două locuri formată din perechi de elemente obținute prin rearanjarea perechilor de elemente ale relației date . Desemnat: . Pentru o relație dată și inversul ei, egalitatea este adevărată: . $R$ $(y,x)$ $(X y)$ $R$ $R^{{-1}}$ $(R^{{-1}})^{{-1}}=R$
Relațiile reciproce (relațiile reciproce) sunt relații care sunt inverse unele față de altele. Domeniul unuia dintre ele este domeniul celuilalt, iar domeniul primului este domeniul celuilalt.
O relație reflexivă este o relație de două locuri , definită pe o anumită mulțime și caracterizată prin aceea că pentru oricare din această mulțime, elementul este în raport cu el însuși, adică pentru orice element din această mulțime, . Exemple de relații reflexive: egalitate , simultaneitate , similitudine . $R$ $X$ $X$ $R$ $X$ $xRx$
Relația anti-reflexivă (relația ireflexivă; la fel cum antisimetria nu coincide cu asimetria, ireflexivitatea nu coincide cu non-reflexivitate) este o relație binară definită pe o anumită mulțime și caracterizată prin aceea că nu este adevărată pentru niciun element din această mulțime care este în raport cu sine (nu este adevărat că ). $R$ $X$ $R$ $xRx$
O relație tranzitivă este o relație cu două locuri definită pe o anumită mulțime și care diferă prin aceea pentru oricare dintre și urmează ( ). Exemple de relații tranzitive: „mai mare”, „mai puțin”, „egal”, „asemănător”, „mai mare”, „nord”. $R$ $x,y,z$ $xRy$ $yRz$ $xRz$ $xRy\wedge yRz\la xRz$
relație netranzitivă[ clarifica ] - o relație cu două locuri definită pe o anumită mulțime și care diferă prin aceea că pentru niciuna dintre această mulțime nu rezultă din și ( ). Un exemplu de relație netranzitivă: „x este tatăl lui y” $R$ $x,y,z$ $xRy$ $yRz$ $xRz$ $\neg (xRy\wedge yRz\to xRz)$
O relație simetrică este o relație binară , definită pe o anumită mulțime și care diferă prin aceea că pentru orice elemente și această mulțime, din ceea ce este în relație , rezultă că și este în aceeași relație cu - . Un exemplu de relații simetrice poate fi egalitatea, relația de echivalență , similaritatea , simultaneitatea. $R$ $X$ $y$ $X$ $y$ $R$ $y$ $X$ $xRy\la yRx$
O relație antisimetrică este o relație binară definită pe o anumită mulțime și care diferă prin aceea că pentru oricare și de la și urmează (adică și sunt efectuate simultan numai pentru membri egali între ei). $R$ $X$ $y$ $xRy$ $yRx$ $x=y$ $R$ $R^{{-1}}$
O relație asimetrică este o relație binară definită pe o anumită mulțime și care diferă prin aceea că pentru oricare și rezultă din . Exemplu: relații mai mari decât (>) și mai mici decât (<). $R$ $X$ $y$ $xRy$ $\neg yRx$
O relație de echivalență este o relație binară între obiecte și care este atât reflexivă, simetrică, cât și tranzitivă. Exemple: egalitate, echivalență a două mulțimi, similaritate , simultaneitate . $R$ $X$ $y$
O relație de ordine este o relație care are doar unele dintre cele trei proprietăți ale unei relații de echivalență: o relație care este reflexivă și tranzitivă, dar nesimetrică (de exemplu, „nu mai mult”) formează o ordine non-strict, iar o relație adică tranzitiv, dar non-reflexiv și nesimetric (de exemplu, „mai puțin”) formează o ordine strictă.
O relație de toleranță este o relație binară care satisface proprietățile reflexivității și simetriei, dar nu este neapărat tranzitivă. Astfel, relația de echivalență este un caz special de toleranță.
O funcție a unei variabile este o relație binară , definită pe o anumită mulțime, care diferă prin aceea că fiecare valoare a relației corespunde doar unei singure valori . Proprietatea funcționalității relației se scrie ca axiomă: . $R$ $X$ $xRy$ $y$ $R$ $(xRy\wedge xRz)\la (y\equiv z)$
O bijecție (relație unu-la-unu) este o relație binară definită pe o anumită mulțime, caracterizată prin aceea că în ea fiecare valoare corespunde unei singure valori , iar fiecarei valori îi corespunde o singură valoare . $R$ $X$ $y$ $y$ $X$

Operațiuni pe relații

Deoarece relațiile definite pe o pereche fixă de mulțimi sunt submulțimi ale mulțimii , atunci totalitatea tuturor acestor relații formează o algebră booleană cu privire la operațiile de unire, intersecție și adăugare de relații. În special , pentru arbitrare ,: $A$ $B$ $A\ori B$ $a\în A$ $b\în B$

a\,(R\cup S)\,b\Săgeată stânga la dreapta a\,R\,b\vee a\,S\,b

a\,(R\cap S)\,b\Săgeată stânga a\,R\,b\pană a\,S\,b

a\,\overline {R}\,b\Săgeată stânga la dreapta \neg a\,R\,b

Adesea, în loc de unire, intersecție și adăugare de relații, se vorbește despre disjuncția, conjuncția și negația lor.

De exemplu, , , adică unirea unei relații de ordine strictă cu o relație de egalitate coincide cu o relație de ordine non-strict, iar intersecția lor este goală. $({=})\cup ({<})=({\leqslant })$ $({=})\cap ({<})=\varnothing$

Pe lângă cele enumerate, sunt importante și operațiile de inversare și multiplicare a relațiilor, definite astfel. Dacă , atunci relația inversă este relația definită pe pereche și constând din acele perechi pentru care . De exemplu, . $R\subseteq A\time B$ $R^{{-1}}$ $B$ $A$ $(b,a)$ $a\,R\,b$ $({<})^{-1}=({>})$

Să , . O compoziție (sau produs) de relații este o relație astfel încât: $R\subseteq A\time B$ $S\subseteq B\time 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

De exemplu, pentru o relație de ordine strictă pe mulțimea numerelor naturale, înmulțirea ei prin ea însăși este definită astfel: . $a({<})({<})b\Săgeată stânga-dreapta a+1<b$

Relațiile binare și se numesc permutabile dacă . Pentru orice relație binară definită pe , există , unde simbolul denotă egalitatea definită pe . Cu toate acestea, egalitatea nu este întotdeauna corectă. $R$ $S$ $RS=SR$ $R$ $A$ $R{\mathsf {Id}}_{A}={\mathsf {Id}}_{A}R$ ${\mathsf {Id}}_{A}$ $A$ $RR^{{-1}}={\mathsf {Id}}$

Următoarele identități dețin:

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

Nu au loc analogii ultimelor două identități pentru intersecția relațiilor.

Note

↑ Tsalenko M. Sh . Corespondență // Enciclopedia matematică. - 1985. - V. 5 (Slu-Ya) . - S. 77 .
↑ Conformitate . Marea Enciclopedie Rusă . (nedefinit)
↑ Kostrikin A. I. Introducere în algebră. Fundamentele algebrei. . - M .: Fizmatlit , 1994. - S. 47 -48. — 320 s. — ISBN 5-02-014644-7 .
↑ 1 2 Kulikov L.Ya. Capitolul doi. Mulțimi și relații // Algebră și teoria numerelor: Proc. manual pentru institutele pedagogice. - M . : Şcoala superioară , 1979. - S. 50. - 559 p.
↑ Yerusalimsky Ya.M. 4. Compunerea relaţiilor binare. Produsul boolean al matricelor // Matematică discretă: teorie, probleme, aplicații. — ediția a 3-a. - M . : Cartea Vuzovskaya, 2000. - S. 112. - 280 p. — ISBN 5-89522-034-7 .
↑ Novikov F.A. 1.5.4. Compoziția relațiilor // Matematică discretă pentru programatori. - Sankt Petersburg. : Peter , 2000. - S. 34. - 304 p. - ISBN 5-272-00183-4 .
↑ 1 2 Dubov Yu. A., Travkin SI., Yakimets V. N. Modele cu mai multe criterii pentru formarea și selectarea opțiunilor de sistem. — M.: Nauka, 1986. (p. 48)

Literatură

Maltsev, A. I. Sisteme algebrice. — M .: Nauka , 1970. — 392 p. - 17.500 de exemplare.

Aleskerov F.T., Khabina E.L., Schwartz D.A. Relații binare, grafice și soluții colective. - M . : Manuale Școlii Superioare de Științe Economice, 2006. - 300 p.

Puhnachev Yu. V., Popov Yu. P. Cartea. 1: Mulțimi, mapări, relații, secvențe, serii, funcții, proprietăți ale funcțiilor, calcul diferențial și integral, funcții ale multor variabile // Matematică fără formule. - Ed. al 6-lea, rev. - M. : URSS, 2017. - 231 p. — ISBN 978-5-9710-3871-9 .