Отношения

Определение. Пусть $X$ и $Y$ - два произвольных множества. Если какому-либо элементу $x \in X$ по некоторому правилу сопостовляется элемент $y \in Y$ (один или более), то говорят, что между элементами множеств $X$ и $Y$ установлено отношение (соответствие).

Не исключено, что $X=Y$, тогда говорят, что отношение установлено между элементами множества $X$. Отношения могут обозначаться символами: $R$, $P$, $f$ (специальные элементы ~, =, >, $\le$ и т.д.).

$x\;R\;y$, $x \in X$, $y \in Y$ - x и y находятся в отношении R.

$x\; \overline{R} \;y$, $x \in X$, $y \in Y$ - x и y не находятся в отношении R.

Пример. $X=Y=N$, $R$ - отношение делимости: $12\;R\; 6$, $15 \; \overline{R} \; 7$.

Рассмотрим отношение $R$ между множествами $X$ и $Y$. Графиком отношения $R$ называется множество $\Gamma=\{(x,y) \; | \; x\ \in X, y \in Y, x\;R\;y \} \supseteq X \times Y$.

Определение. Декартовым произведением множеств $X$ и $Y$ называется множество всевозможных упорядоченных пар, первая компонента которых является элементов множества $X$, вторая - множества $Y$.

Пример.

а) $X=\{1,2,4\}$, $Y=\{3,5\}$.

$X \times Y = \{(1,3), (1,5), (2, 3), (2, 5), (4, 3), (4, 5) \}$.

Декартово произведение множества X на множество Y. График - точки.

$Y \times X = \{(3, 1), (3, 2), (3, 4), (5, 1), (5, 2), (5, 4) \}$.

б) $X=[1, 4]$, $Y=[3, 5]$.

Декартово произведение множества X на множество Y. График - область.

Всякое отношение имеет график - некоторое подмножество декартового произведения $X$ и $Y$, и наоборот, всякое подмножество $R \subset X \times Y$ задаёт некоторое отношение $x\;R\;y$. В связи с этим получаем следующее определение.

Определение.  Отношением между элементами множеств $X$ и $Y$ называется подмножество $R \subset X \times Y$.

Наиболее употребимы два вида отношений: отношение эквивалентности и отношение порядка.