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

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

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

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

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

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

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

Идентитет или идентична релация $I{d}_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$-свързан със себе си, т.е. $\mathrm{\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$ е най-малката транзитивна релация $Suc{c}_R$, такава че $R\subset Suc{c}_R$.

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

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