Отношение

Бинарным отношением между множествами $A$ и $B$ называется любое подмножество $\rho $ декартова произведения $A \times B$.

Если $A$=$B$ $\rho \subset {A^2}$, тогда $\rho $ бинарное отношение на множестве $A$.

Часто, чтобы обозначить принадлежность упорядоченной пары $ ({a,b}) $ к бинарному отношению $\rho $ вместо $\left( {a,b} \right) \in \rho $ используют обозначения $\rho ({a,b})$ или $a\rho b$. При этом говорят, что $a$ находится в отношении $\rho $ к $b$.

$\left( {a,b} \right) \in \rho \Leftrightarrow a\rho b$

Аналогно, $\left( {a,b} \right) \notin \Leftrightarrow \neg \left( {a\rho b} \right)$

Свойства бинарного отношения $\rho $ на множестве $A$

$R$ (рефлексивность) $ \Leftrightarrow $ $(\forall a \in А)(a \rho a)$
$AR$ (анитрефлексивность) $ \Leftrightarrow $ $(\forall a \in А) \neg (a \rho a)$
$S$ (симметричность) $ \Leftrightarrow $ ${\text{(}}\forall a,b \in A){\text{ }}a\rho a \Rightarrow b\rho a$
$AS$ (асимметричность) $ \Leftrightarrow $ ${\text{(}}\forall a,b \in A){\text{ (}}a\rho b \wedge b\rho a) \Rightarrow a = b$
$Т$ (транзитивность) $ \Leftrightarrow $ ${\text{(}}\forall a,b,c \in A){\text{ }}(a\rho b \wedge b\rho c) \Rightarrow {\text{ }}a\rho c$

Виды отношений

Рефлексивное симметричное транзитивное отношение называется отношением эквивалентности
Рефлексивное антисимметричное транзитивное отношение называется отношением (частичного) порядка
Антирефлексивное антисимметричное транзитивное отношение называется отношением строгого порядка

Класс эквивалентности

Классом эквивалентности, порождённым элементом $a$, называется множество: $$\left\{ {x\backslash x \in A \wedge x\rho a} \right\}.$$

Фактор-множество — множество всех классов эквивалентности заданного множества $А$ по заданному отношению $\rho $.

Отношение порядка на множестве $А$ называется отношением линейного порядка или линейным порядком на $А$, если $a\rho b \vee a = b \vee b\rho a$, для $a$ и $b \in A$.

Упорядоченное множество

Пусть $ \rho $ произвольное отношение порядка на непустом множестве $А$.

Упорядоченное множество — множество $А$ с заданным отношением порядка $ \rho $, обозначается $(A,\rho )$.

Если порядок $ \rho $ на $А$ линейный, то пара $(A,\rho )$ называется линейно упорядоченным множеством.

Операция порядка обозначается $ \leqslant $, а операция строгого порядка $ < $.

Пусть $(A, \leqslant)$ — упорядоченное множество,

$a \in A$	минимальный элемент	$ \Leftrightarrow \neg {\text{(}}\exists x \in A)(x \ne a \wedge x \leqslant a)$
$a \in A$	наименьший элемент	$ \Leftrightarrow {\text{(}}\forall x \in A)(a \leqslant x)$
$a \in A$	максимальный элемент	$\neg (\exists x \in A)(x \ne a \wedge a \leqslant x)$
$a \in A$	наибольший элемент	$\left( {\forall x \in A} \right)\left( {x \leqslant a} \right)$

Обратное отношение

Обратным отношением отношения $\rho $ называется отношение:

$${\rho ^{ — 1}} = \left\{ {\left( {b,a} \right)\backslash \left( {a,b} \right) \in \rho } \right\}$$

Композиция

Композицией (произведнием) двух бинарных отношений ${\rho _1} \subset A \times B$ и ${\rho _2} \subset B \times C$ называется отношение:

$${\rho _1}^\circ {\rho _2} = \left\{ {\left( {x,y} \right)\backslash \left( {\exists z} \right)\left( {x{\rho _1}z \wedge z{\rho _2}y} \right)} \right\}$$