Математическая логика, множества, функции

Отношение

Бинарным отношением  между множествами $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$

  1. $R$ (рефлексивность) $ \Leftrightarrow $ $(\forall a \in А)(a \rho a)$
  2. $AR$ (анитрефлексивность) $ \Leftrightarrow $ $(\forall a \in А) \neg (a \rho a)$
  3. $S$ (симметричность) $ \Leftrightarrow $ ${\text{(}}\forall a,b \in A){\text{ }}a\rho a \Rightarrow b\rho a$
  4. $AS$ (асимметричность) $ \Leftrightarrow $ ${\text{(}}\forall a,b \in A){\text{ (}}a\rho b \wedge b\rho a) \Rightarrow a = b$
  5. $Т$ (транзитивность) $ \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\}$$