Бинарна релация

Бинарната релация, наричана още двуместна релация или двучленна релация, е множество от наредени двойки елементи. Бинарните релации са обект на изучаване в теорията на множествата, теорията на наредбите, математическата логика и информатиката.

Означения и определения

Два елемента $x,y\,$ са в релация $R\,$, ако $(x,y)\in R$ и $(x,y)\neq (y,x)$, т.е. $(x,y)\,$ е наредена двойка. Записва се $xRy\,$ и се чете $y\,$ е $R\,$-свързано с $x\,$, например добре познатите $x<y,\,x\leq y,\,x=y,\,x\equiv y{\pmod {m}}$ и др.

Дефиниционна област $Dom(R)=\{x\,|\,\exists y,\,xRy\}$ на релация е множеството от всички първи елементи на релацията.

Аналогично множество от стойности $Cod(R)=\{y\,|\,\exists x,\,xRy\}$ е множеството от всички втори елементи на релацията.

Композиция $R_{1}\circ R_{2}$ на две релации $R_{1}\,$ и $R_{2}\,$ е множеството от всички двойки $\{(x,y)\,|\,\exists y,\,xR_{1}y,\,yR_{2}z\}$.

Идентитет или идентична релация $Id_{S}\,$ на множество $S\,$ e множеството от всички $(x,x),x\in S$.

Обратна релация $R^{-1}\,$ се получава при смяна на реда на всички двойки от $R\,$, или $R^{-1}=\{(x,y)\,|\,yRx\}$. Изпълено е също $Dom(R^{-1})=\,Cod(R)$ и $Cod(R^{-1})=\,Dom(R)$.

Видове бинарни релации

Рефлексивна релация е релация $R\,$, за която всеки елемент от дефиниционната област и от множеството от стойности е $R\,$-свързан със себе си, т.е. $\forall (x,y)\in (Dom(R),Cod(R))$ е в сила $xRx,\,yRy$.

Антирефлексивна релация е релация $R\,$, за която не съществува елемент $x\,$, който да е $R\,$-свързан със себе си.

Симетрична релация е релация $R\,$, такава че $xRy\Rightarrow yRx$, или още релация която съвпада с обратната си $R=R^{-1}\,$

Антисиметрична релация е налице когато е изпълнена една и само една от следните алтернативи: $xRy\,$ или $yRx\,$. Формулирано с помощта на обратна релация, условието се записва: $R\cap R^{-1}=\varnothing$.

Транзитиван релация се получава когато $xRy,\,yRz\Rightarrow xRz$. Формулирано с помощта на композиция, условието придобива вида: $R\circ R\subset R$

Кръгова релация на множество $S\,$ е налице, когато $xRy,\,yRz\Rightarrow zRx,\ x,y,z\in S$.

Наследник на релация $R\,$ в множество $S\,$ е най-малката транзитивна релация $Succ_{R}\,$, такава че $R\subset Succ_{R}$.

Една релация е релация на еквивалентност ако е едновременно рефлексивна, симетрична и транзитивна.

Частична наредба е релация която е рефлексивна, антисиметрична и транзитивна.