x, y, z

Бинарные отношения

# 4 Авг 2018 20:04:14
Evgeniy

Бинарное отношение любви, к сожалению, не симметрично
Определение. Пусть $X, Y$ — множества. Множество упорядоченных пар $(x,y)$, где $x\in X$, $y\in Y$, называется декартовым произведением множеств и обозначается $X \times Y = \{(x,y)\colon x\in X, y\in Y\}$. Упорядоченных значит, что порядок в паре $(x,y)$ имеет значение.

Определение. Пусть $X, Y$ — множества. Бинарное отношение $\sigma$ на множествах $X$ и $Y$ задается выбором подмножества декартова произведения $M_{\sigma} \subseteq X\times Y$. Если пара $(x,y) \in M_{\sigma}$, то пишут $x\sigma y$.

Следующее определение получается из этого при $X=Y$.

Определение. Пусть $X$ — множество. Бинарное отношение на множестве $X$ задается выбором подмножества декартова произведения $M_{\sigma} \subseteq X\times X$. Если пара $(x,y) \in M_{\sigma}$, то также пишут $x\sigma y$.

Пример. Пусть $X$ — множество людей. Если $x$ влюблен в $y$, то это можно записать как бинарное отношение $x \heartsuit y$. Причем из того, что $x$ влюблен в $y$, вообще говоря, не следует, что $y$ влюблен в $x$. То есть может быть $x \heartsuit y$, но не быть $y \heartsuit x$. Важен порядок.

Некоторый элемент $x$ может ни с кем не быть в отношении $\heartsuit$. Как в качестве влюбленного (то есть не существует $z$ такого, что $x \heartsuit z$). Также в качестве того, в кого влюблены (не существует $z$ такого, что $z \heartsuit x$).

Какой-то $x$ может состоять в отношении $\heartsuit$ одновременно с несколькими. Как на первом месте ($x$ может быть влюблен сразу в нескольких людей, то есть имеет место $x \heartsuit y_1$ и $x \heartsuit y_2$). Так и на втором месте (в $x$ влюблены несколько человек: $y_1 \heartsuit x$ и $y_2 \heartsuit x$).

Также не исключено, что $x$ нарцисс и $x \heartsuit x$.

Бинарное отношение $\sigma$ на множестве $X$ может обладать различными свойствами, например:
$\forall x\in X \ x\sigma x$ — рефлексивность.
$\forall x,y\in X \ ( x\sigma y \Rightarrow y\sigma x )$ — симметричность.
$\forall x,y,z \in X \ ( x \sigma y \vee y \sigma z \Rightarrow x \sigma z)$ — транзитивность.
$\forall x,y\in X \ ( x\sigma y \vee y \sigma x \Rightarrow x=y )$ — антисимметричность.

Определение. Рефлексивное, симметричное, транзитивное бинарное отношение называют отношением эквивалентности. Обычно обозначают $x\sim y$.

Свойства отношения эквивалентности:
1) $\forall x\in X \ x\sim x$ — рефлексивность;
2) $\forall x,y\in X \ ( x\sim y \Rightarrow y\sim x )$ — симметричность;
3) $\forall x,y,z \in X \ ( x \sim y \vee y \sim z \Rightarrow x \sim z)$ — транзитивность.

Определение. Рефлексивное, антисимметричное, транзитивное бинарное отношение называют отношением порядка (частичного порядка). Обычно обозначают $x \le y$.

Свойства отношения порядка:
1) $\forall x\in X \ x \le x$ — рефлексивность;
2) $\forall x,y\in X \ ( x \le y \vee y \le x \Rightarrow x=y )$ — антисимметричность;
3) $\forall x,y,z \in X \ ( x \le y \vee y \le z \Rightarrow x \le z)$ — транзитивность.

Функцию $f\colon X \to Y$ также можно считать бинарным отношением на множествах $X$ и $Y$. Чтобы быть классической однозначной функцией, бинарное отношение $f$ должно удовлетворять следующему условию: $\forall x\in X$ найдется и единственный $y\in Y$ такой, что $x f y$. Заметим, что множество $M_f \subseteq X\times Y$ является ничем иным, как графиком функции $f$. С такой точки функция $f$ по сути задается своим графиком, или множеством пар $(x, f(x))$, где $x\in X$.

С другой стороны, бинарные отношение можно считать обобщением понятия функция (отображение).

Далее сформулируем и докажем свойства отношения эквивалентности.

Утверждение. Отношение эквивалентности $\sim$ на множестве $X$ разбивает множество $X$ на так непересекающиеся подмножества, называемые классами эквивалентности. Любые два элемента из класса эквивалентности эквивалентны друг другу.

Доказательство.

Рассмотрим множество $[a] = \{x \in X \colon x \sim a\}$, где $a \in X$. Покажем, что множество такого вида и будут искомыми классами эквивалентности.

Каждый элемент $a \in X$ лежит в множестве такого вида, а именно $a \in [a]$, поскольку $a\sim a$ ввиду рефлексивности. Из этого также следует, что множество $[a] \ne \varnothing$.

Так как любое $[a] \subseteq X$, то можно записать, что
$$X = \bigcup_{a\in X} [a]$$.
Покажем, что множества вида $[a]$ либо не пересекаются, либо совпадают.

Сначала покажем, что если $c \in [a]$, то $[c]=[a]$. Так как $c \in [a]$, то по определению $c\sim a$ и следовательно ввиду симметричности $a\sim c$.

Если $x \in [a]$, то по определению $x \sim a$. Ввиду транзитивности из $x \sim a$ и $a\sim c$ следует $x \sim c$, то есть $x\in [c]$. Следовательно, $[a] \subseteq [c]$.

Если $x \in [c]$, то по определению $x \sim c$. Ввиду транзитивности из $x \sim c$ и $c\sim a$ следует $x \sim a$, то есть $x\in [a]$. Следовательно, $[c] \subseteq [a]$.

Таким образом, $[c] = [a]$.

Допустим, что множества $[a]$ и $[b]$ пересекаются, то есть содержат какой-то общий элемент $c \in [a] \cap [b]$. Тогда по доказанному $c \in [a]$ и, следовательно, $[c]=[a]$. В то же время, $c \in [b]$ и, следовательно, $[c]=[b]$. В итоге $[a]=[c]=[b]$.
*Имя:
Заголовок:
[tex-clear] [tex-help] [ted]
  • formulas >

*Вычислите
Captcha
Отправляя данные, вы соглашаетесь с Правилами сайта.