Изменения

Композицией бинарных отношений <mathtex>R\subseteq A\times B</mathtex> и <mathtex>S\subseteq B\times C</mathtex> называется такое отношение <mathtex> (R \circ S) \subseteq A\times C</mathtex>, что:

<mathtex>\forall a\in A, c\in C : a(R\circ S)c \Leftrightarrow \exists b\in B\mid (aRba R b)\and wedge (bScb S c)</mathtex>.

Примером такого отношения может служить отношение на некотором множестве <mathtex>A</mathtex> населенных пунктов <mathtex>R\subseteq A\times A</mathtex> - отношение "можно доехать на поезде", а <mathtex>S\subseteq A\times A</mathtex> - отношение "можно доехать на автобусе". Тогда отношение <mathtex>R\circ S\subseteq A\times A</mathtex> - отношение "можно добраться из А в Б, сначала проехав на поезде, а потом на автобусе(только по одному разу)".

Степень отношения <mathtex>R^{n} \subseteq A\times A</mathtex>, определяется следующим образом:

<mathtex> R^{n} = R^{n-1} \circ R; </mathtex>

<mathtex> R^{1 } = R;</tex>

<tex> R^{0 } = \{ (x, x) \mid x\in A\}</mathtex>;

<mathtex> R^{+} = \bigcup\limits^{\infty}_{i=1} R^{i}; </mathtex>

<mathtex> R^{*} = \bigcup\limits^{\infty}_{i=0} R^{i} </mathtex> - [[Транзитивное замыкание]] множества отношения R

Отношение <mathtex>R^{-1} \subseteq B\times A</mathtex> называют ''обратным'' для отношения <mathtex> R \subseteq A\times B</mathtex>, если:

<mathtex> aR^{-1}b \Leftrightarrow bRa </mathtex>

''Ядром отношения'' R называется отношение <mathtex> R\circ R^{-1} </mathtex>

Оно симметрично: <mathtex> a(R\circ R^{-1})b \Rightarrow Leftrightarrow \exists c: (aRca R c)\andwedge (cRc R^{-1}b) \Rightarrow Leftrightarrow \exists c:(bRcb R c)\and wedge (cRc R^{-1}a) \Rightarrow Leftrightarrow b(R\circ R^{-1}) a</mathtex>