Binární relace

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 22. srpna 2022; ověření vyžaduje 1 úpravu .

Binární ( dvoumístná ) relace (korespondence [1] [2] ) je relace mezi dvěma množinami a , tedy libovolnou podmnožinou kartézského součinu těchto množin: [3] . Binární relace na množině je jakákoli podmnožina , takové binární relace se nejčastěji používají v matematice, konkrétně jde o rovnost , nerovnost , ekvivalenci , relace pořadí . $A$ $B$ $R\subseteq A\times B$ $A$ $R\subseteq A^{2}=A\times A$

Související definice

Množina všech prvních složek párů z se nazývá definiční obor relace a označuje se jako . [čtyři] $R\subseteq A\times B$ $R$ ${\mathrm {Dom}}\,R$

{\mathrm {Dom}}\,R=\{x\mid \existuje y((x,\;y)\v R)\}.

Množina všech druhých složek párů z se nazývá definiční obor relace a označuje se jako . $R$ $R$ ${\mathrm {Im}}\,R$

{\mathrm {Im}}\,R=\{y\mid \existuje x((x,\;y)\v R)\}.

[čtyři]

Inverze ( inverzní vztah) je množina a označuje se jako . $R$ $\{(x,\;y)\mid (y,\;x)\v R\}$ $R^{{-1}}$
Složení(superpozice) binárních relací a je množina a označuje se jako . [5] [6] $R$ $S$ $\{(x,\;y)\mid \exists z(xRz\land zSy)\}$ $R\circ S$

Vlastnosti vztahu

Binární relace na určité množině může mít různé vlastnosti, například: $R$ $M$

reflexivita : , $\forall x\in M:(xRx)$
antireflexivita (nereflexivita): , $\forall x\in M:\neg (xRx)$
koreflexivita : , $\forall x,y\in M:(xRy\Rightarrow x=y)$
symetrie : , $\forall x,\;y\in M:(xRy\Rightarrow yRx)$
antisymetrie : , $\forall x,\;y\in M:(xRy\wedge yRx\Rightarrow x=y)$
asymetrie : , $\forall x,\;y\in M:(xRy\Rightarrow \neg (yRx))$
tranzitivita : , $\forall x,\;y,\;z\in M:(xRy\wedge yRz\Rightarrow xRz)$
euklidovský : , $\forall x,y,z\in M:(xRy\wedge xRz\Rightarrow yRz)$
úplnost (nebo propojenost [7] ): , $\forall x,y\in M:(xRy\lor yRx)$
propojenost(nebo slabé připojení [7] ): , $\forall x,y\in M:(x\neq y\Rightarrow xRy\lor yRx)$
trichotomie: právě jedno ze tří tvrzení je pravdivé: , nebo . $\forall x,y\in M$ $xRy$ $yRx$ $x=y$

Typy vztahů

Reflexivní tranzitivní relace se nazývá kvazi-řádová relace .
Reflexivní symetrická tranzitivní relace se nazývá relace ekvivalence .
Reflexivní antisymetrická tranzitivní relace se nazývá relace (částečného) řádu .
Antireflexivní antisymetrický tranzitivní vztah se nazývá relace striktního řádu .
Úplný antisymetrický (nebo platí pro jakýkoli ) tranzitivní vztah se nazývá relace lineárního řádu . $x, y$ $xRy$ $yRx$
Antireflexivní antisymetrický vztah se nazývá relace dominance .

Typy binárních relací

Reverzní vztah[ specifikovat ] (vztah inverzní k ) je dvoumístná relace sestávající z dvojic prvků získaných přeskupením dvojic prvků daného vztahu . Určeno: . Pro daný vztah a jeho inverzní platí rovnost: . $R$ $(y,x)$ $(x, y)$ $R$ $R^{{-1}}$ $(R^{{-1}})^{{-1}}=R$
Reciproční vztahy (reciproční vztahy) jsou vztahy, které jsou vzájemně inverzní. Rozsah jednoho z nich je doménou druhého a obor prvního je doménou druhého.
Reflexivní relace je dvoumístná relace , definovaná na určité množině a charakterizovaná tím, že pro kteroukoli z této množiny je prvek ve vztahu k sobě samému, tj. pro jakýkoli prvek této množiny, . Příklady reflexivních vztahů: rovnost , simultánnost , podobnost . $R$ $X$ $X$ $R$ $X$ $xRx$
Antireflexivní relace (reflexní relace; stejně jako antisymetrie se neshoduje s asymetrií, neshoduje se ireflexivita s nereflexivitou) je binární relace definovaná na určité množině a charakterizovaná tím , že pro žádný prvek této množiny neplatí, že je ve vztahu k sobě samému (není pravda, že ). $R$ $X$ $R$ $xRx$
Tranzitivní relace je dvoumístná relace definovaná na určité množině a lišící se v tom, že pro kteroukoli z a následuje ( ). Příklady tranzitivních vztahů: "větší", "méně", "rovný", "podobný", "vyšší", "severní". $R$ $x, y, z$ $xRy$ $yRz$ $xRz$ $xRy\wedge yRz\to xRz$
netranzitivní vztah[ objasnit ] - dvoumístná relace definovaná na určité množině a lišící se tím, že pro žádnou z této množiny nevyplývá z a ( ). Příklad netranzitivního vztahu: "x je otcem y" $R$ $x, y, z$ $xRy$ $yRz$ $xRz$ $\neg (xRy\wedge yRz\to xRz)$
Symetrická relace je binární relace , definovaná na určité množině a lišící se tím, že pro libovolné prvky a tuto množinu z toho, co je ve vztahu k , vyplývá, že a je ve stejném vztahu k - . Příkladem symetrických vztahů může být rovnost, vztah ekvivalence , podobnost , simultánnost. $R$ $X$ $y$ $X$ $y$ $R$ $y$ $X$ $xRy\to yRx$
Antisymetrická relace je binární relace definovaná na určité množině a lišící se tím, že pro libovolnou a od a z toho plyne (tedy a jsou prováděny současně pouze pro členy navzájem rovné). $R$ $X$ $y$ $xRy$ $yRx$ $x=y$ $R$ $R^{{-1}}$
Asymetrická relace je binární relace definovaná na určité množině a lišící se tím, že pro jakoukoli a vyplývá z . Příklad: vztahy větší než (>) a menší než (<). $R$ $X$ $y$ $xRy$ $\neg yRx$
Relace ekvivalence je binární vztah mezi objekty , který je reflexivní, symetrický a tranzitivní. Příklady: rovnost, ekvivalence dvou množin, podobnost , simultánnost . $R$ $X$ $y$
Relace řádu je relace, která má pouze některé ze tří vlastností vztahu ekvivalence: relace, která je reflexivní a tranzitivní, ale nesymetrická (například „ne více“) tvoří nepřísný řád, a relace to je tranzitivní, ale nereflexivní a nesymetrické (například „méně“) tvoří přísný řád.
Toleranční relace je binární relace, která splňuje vlastnosti reflexivity a symetrie, ale nemusí být nutně tranzitivní. Relace ekvivalence je tedy speciálním případem tolerance.
Funkce jedné proměnné je binární relace , definovaná na určité množině, lišící se tím, že každá hodnota relace odpovídá pouze jedné hodnotě . Vlastnost relace funkčnost je zapsána jako axiom: . $R$ $X$ $xRy$ $y$ $R$ $(xRy\wedge xRz)\to (y\ekviv z)$
Bijekce (relace jedna ku jedné) je binární relace definovaná na určité množině, vyznačující se tím, že v ní každá hodnota odpovídá jedné hodnotě a každá hodnota odpovídá jedné hodnotě . $R$ $X$ $y$ $y$ $X$

Operace se vztahy

Protože vztahy definované na pevné dvojici množin jsou podmnožinami množiny , pak souhrn všech těchto relací tvoří Booleovu algebru s ohledem na operace sjednocení, průnik a sčítání relací. Zejména pro svévolné : $A$ $B$ $A\krát B$ $v A$ $b\in B$

a\,(R\pohár S)\,b\Šipka doleva doprava a\,R\,b\vee a\,S\,b

a\,(R\cap S)\,b\Šipka doleva doprava a\,R\,b\klín a\,S\,b

a\,\overline {R}\,b\Šipka doleva \neg a\,R\,b

Často se místo sjednocení, průniku a sčítání vztahů hovoří o jejich disjunkci, konjunkci a negaci.

Například , , tj. spojení relace striktního řádu s relací rovnosti se shoduje s relací nepřísného řádu a jejich průsečík je prázdný. $({=})\pohár ({<})=({\leqslant })$ $({=})\cap ({<})=\varnothing$

Kromě výše uvedených jsou důležité také operace inverze a násobení vztahů, definované následovně. Jestliže , pak inverzní vztah je vztah definovaný na páru a sestávající z těch párů, pro které . Například . $R\subseteq A\times B$ $R^{{-1}}$ $B$ $A$ $(b,a)$ $a\,R\,b$ $({<})^{-1}=({>})$

Nechte ,. _ Složení (nebo produkt) vztahů je takový vztah , že: $R\subseteq A\times B$ $S\subseteq B\times 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

Například pro relace striktního řádu na množině přirozených čísel je její násobení samo o sobě definováno takto: . $a({<})({<})b\Šipka doleva doprava a+1<b$

Binární relace a jsou nazývány permutabilní if . Pro každou binární relaci definovanou dne existuje , kde symbol označuje rovnost definovanou dne . Rovnost však není vždy spravedlivá. $R$ $S$ $RS=SR$ $R$ $A$ $R{\mathsf {Id}}_{A}={\mathsf {Id}}_{A}R$ ${\mathsf {Id}}_{A}$ $A$ $RR^{{-1}}={\mathsf {Id}}$

Drží se následující identity:

$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$ .

Analogy posledních dvou identit pro průnik vztahů se nekonají.

Poznámky

↑ Tsalenko M. Sh . Korespondence // Matematická encyklopedie. - 1985. - V. 5 (Slu-Ya) . - S. 77 .
↑ Soulad . Velká ruská encyklopedie . (neurčitý)
↑ Kostrikin A. I. Úvod do algebry. Základy algebry. . - M .: Fizmatlit , 1994. - S. 47 -48. — 320 s. — ISBN 5-02-014644-7 .
↑ 1 2 Kulikov L.Ya. Kapitola dvě. Množiny a relace // Algebra a teorie čísel: Proc. manuál pro pedagogické ústavy. - M . : Vyšší škola , 1979. - S. 50. - 559 s.
↑ Yerusalimsky Ya.M. 4. Skládání binárních relací. Booleovský součin matic // Diskrétní matematika: teorie, problémy, aplikace. — 3. vydání. - M . : Kniha Vuzovskaja, 2000. - S. 112. - 280 s. — ISBN 5-89522-034-7 .
↑ Novikov F.A. 1.5.4. Složení vztahů // Diskrétní matematika pro programátory. - Petrohrad. : Peter , 2000. - S. 34. - 304 s. - ISBN 5-272-00183-4 .
↑ 1 2 Dubov Yu. A., Travkin SI., Yakimets V. N. Vícekriteriální modely pro tvorbu a výběr možností systému. — M.: Nauka, 1986. (str. 48)

Literatura

Maltsev, A. I. Algebraické systémy. — M .: Nauka , 1970. — 392 s. - 17 500 výtisků.

Aleskerov F.T., Khabina E.L., Schwartz D.A. Binární relace, grafy a kolektivní řešení. - M . : Učebnice Vysoké školy ekonomické, 2006. - 300 s.

Pukhnachev Yu. V., Popov Yu. P. Book. 1: Množiny, zobrazení, relace, posloupnosti, řady, funkce, vlastnosti funkcí, diferenciální a integrální počet, funkce mnoha proměnných // Matematika bez vzorců. - Ed. 6., rev. - M. : URSS, 2017. - 231 s. — ISBN 978-5-9710-3871-9 .