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

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

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

Два елемента $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_1y,\, yR_2z \}$.

Идентитет или идентична релация $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$.

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

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