Бинарные отношения и их классификация

Бинарные отношения предоставляют математический способ моделирования связей между элементами различных множеств и широко используются в различных областях математики (теория графов, логика, алгебра) и информатики.

Содержание

Понятие бинарного отношения
Классификация бинарных отношений
Примеры и задачи для самостоятельного решения

Понятие бинарного отношения

Бинарное отношение $\rho$ между двумя множествами $A$ и $B$ — это подмножество их декартова произведения $A \times B$ . То есть, для каждой упорядоченной пары $(a,b)$ из $A \times B$ , если $(a,b) \in \rho$ , то говорят, что $a$ находится в отношении $\rho$ с $b$ , что записывается как $a\rho b$ .

Пример. Пусть $A = \{1, 2, 3\}$ и $B = \{a, b\}$ . Бинарное отношение $\rho$ может быть определено как $\rho = \{(1,a),(2,b),(3,a)\}$ . В этом случае, $1\rho a$ , $2\rho b$ , и $3\rho a$ .

Далее будем рассматривать бинарные отношения на одном множестве, которые также имеют важное значение в теории отношений, теории множеств и могут использоваться для моделирования различных свойств элементов этого множества.

Бинарное отношение на одном множестве — это подмножество декартова произведения этого множества самого на себя. Таким образом, если у нас есть множество $A$ , то бинарное отношение на $A$ — это подмножество $A \times A$ .

Формальная запись бинарного отношения: $\rho = \left\{ (a,b),\ где\ (a,b) \in \rho \subseteq A \times A \right\}.$

Пример. Пусть $A = \{1, 2, 3\}$ . Бинарное отношение $\rho$ может быть представлено как подмножество декартова произведения $A \times A$ , например, $\rho = \{(1,2),(2,3)\}$ . В этом случае, $1\rho 2$ и $2\rho 3$ .

Примеры бинарных отношений

Отношение «больше» на множестве целых чисел:

— множество: $A = \mathbb{Z}$ ;

— отношение: $a > b$ .

Например, 5 больше 3 ( $5 > 3$ ).

Отношение «делится на» на множестве натуральных чисел:

— множество: $A = \mathbb{N}$ ;

— отношение: $a \mid b$ (читается как « $a$ делится на $b$ »).

Например, 6 делится на 3 ( $6 \mid 3$ ).

Отношение «является подмножеством» на множестве множеств:

— множество: $A = \mathcal{P}(X)$ (множество всех подмножеств множества $X$ );

— отношение: $A \subseteq B$ (читается как « $A$ является подмножеством $B$ »).

Например, $\{1, 2\} \subseteq \{1, 2, 3\}$ .

Классификация бинарных отношений

Бинарные отношения могут быть классифицированы по различным характеристикам.

Рефлексивность. Такие отношения, где каждый элемент связан с самим собой, называются рефлексивными отношениями. Формально, отношение $\rho$ на множестве $A$ называется рефлексивным, если для каждого $a \in A$ выполняется $(a,a) \in \rho$ .

Формальная запись: $\forall a \in A: (a,a) \in \rho.$

Пример. Дано множество $A$ , которое состоит из всех студентов университета. Рассмотрим отношение «учится в том же университете, что и». Это отношение рефлексивно, потому что каждый студент учится в том же университете, что и сам. То есть для любого студента $a$ из университета верно, что $(a,a) \in \rho$ , где $\rho$ — это рассматриваемое отношение.

Пример. Дано множество всех натуральных чисел $\mathbb{N} = \{1, 2, 3, \ldots\}$ . Отношение «больше или равно» ( $\geq$ ) является рефлексивным на этом множестве, так как каждое натуральное число всегда больше или равно самому себе. То есть для любого натурального числа $a$ , высказывание $a \geq a$ является истиной.

Формально это записывается как: $\forall a \in \mathbb{N}: (a,a) \in \rho,$ где $\rho$ — это отношение «больше или равно».

Симметричность. В симметричных отношениях, если элемент $a$ связан с элементом $b$ , то и элемент $b$ связан с элементом $a$ . Формально, отношение $\rho$ на множестве $A$ считается симметричным, если для всех $a, b \in A$ из $(a,b) \in \rho$ следует $(b,a) \in \rho$ .

Формальная запись: $\forall a,b \in A: (a,b) \in \rho \Rightarrow (b,a) \in \rho.$

Пример. Рассмотрим множество $A$ всех городов. Отношение «имеет прямой авиарейс» между городами является симметричным, если для любых городов $a$ и $b$ наличие прямого рейса из $a$ в $b$ всегда подразумевает наличие прямого рейса из $b$ в $a$ . Формально: $\forall a,b \in A: (a,b) \in \rho \Rightarrow (b,a) \in \rho.$

Пример. Для иллюстрации симметричного отношения на множестве чисел можно использовать отношение «равенства» на множестве всех целых чисел $\mathbb{Z} = \{\ldots, -3, -2, -1, 0, 1, 2, 3, \ldots\}$ . Отношение «равно» является симметричным, поскольку если какое-либо целое число $a$ равно другому целому числу $b$ , то и $b$ равно $a$ . Формально это выражается следующим образом: $\forall a,b \in Z: (a,b) \in \rho \Rightarrow (b,a) \in \rho$ , где $\rho$ обозначает отношение «равно».

Примером может служить соотношение чисел 2 и 2: если 2 = 2, то очевидно, что 2 = 2, что демонстрирует симметричность этого отношения.

Транзитивность. В транзитивных отношениях, если элемент $a$ связан с элементом $b$ , и элемент $b$ связан с элементом $c$ , то элемент $a$ также связан с элементом $c$ . Формально, отношение $\rho$ на множестве $A$ транзитивно, если для всех $a, b, c \in A$ из $(a,b) \in \rho$ и $(b,c) \in \rho$ следует $(a,c) \in \rho$ .

Формальная запись: $\forall a,b,c \in A: (a,b) \in \rho$ и $(b,c) \in \rho \Rightarrow (a,c) \in \rho.$

Пример. Представим, что множество $A$ — это множество чисел. Отношение «меньше» является транзитивным, потому что если $a$ меньше $b$ , и $b$ меньше $c$ , то $a$ также меньше $c.$

Например, для чисел 3, 7 и 9, если $3 < 7$ и $7 < 9$ , то $3 < 9$ .

Пример. В качестве примера транзитивного отношения из реальной жизни можно использовать отношение «предок-потомок» в семейных связях.

Предположим, множество $A$ состоит из всех людей. Отношение «является предком» является транзитивным. Это означает, что если человек $a$ является предком человека $b$ , и человек $b$ является предком человека $c$ , то человек $a$ также является предком человека $c$ .

Представим, что Мария — бабушка Елены, а Елена — мама Анны. Тогда, согласно транзитивности, Мария также является предком Анны (в данном случае, прабабушкой).

Формально это выражается определяется как: $\forall a,b,c \in A: (a,b) \in \rho$ и $(b,c) \in \rho \Rightarrow (a,c) \in \rho$ , где $\rho$ обозначает отношение «является предком».

Антисимметричность. В антисимметричных отношениях, если элемент $a$ связан с элементом $b$ и элемент $b$ связан с элементом $a$ , то $a$ и $b$ — это один и тот же элемент. Формально, отношение $\rho$ на множестве $A$ считается антисимметричным, если для всех $a, b \in A$ из $(a,b) \in \rho$ и $(b,a) \in \rho$ следует, что $a = b$ .

Формальная запись: $\forall a,b \in A: (a,b) \in \rho$ и $(b,a) \in \rho \Rightarrow a = b.$

Пример. Рассмотрим отношение «меньше или равно» ( $\leq$ ) на множестве всех целых чисел $\mathbb{Z} = \{\ldots, -2, -1, 0, 1, 2, \ldots\}$ .

Отношение «меньше или равно» является антисимметричным, потому что если целое число $a$ меньше или равно целому числу $b$ и одновременно $b$ меньше или равно $a$ , то $a$ и $b$ обязательно равны. Это следует из определения порядка на числовой прямой.

Например, если у нас есть числа 3 и 3, то $3 \leq 3$ и $3 \leq 3$ . Так как оба условия выполняются, то по определению антисимметричности, $3 = 3$ .

Формально это выражается как $\forall a,b \in \mathbb{Z}: (a,b) \in \rho$ и $(b,a) \in \rho \Rightarrow a = b$ , где $\rho$ обозначает отношение «меньше или равно».

Пример. Рассмотрим пример антисимметричного отношения в иерархии организационной структуры.

Предположим, множество $A$ состоит из всех должностей в компании. Отношение «подчиняется» является антисимметричным. Это означает, что если сотрудник на должности $a$ подчиняется сотруднику на должности $b$ , и одновременно сотрудник на должности $b$ подчиняется сотруднику на должности $a$ , то на самом деле $a$ и $b$ — это одна и та же должность.

«Менеджер проекта» подчиняется «Директору по проектам», но «Директор по проектам» не может подчиняться «Менеджеру проекта». Если обнаруживается, что обе должности подчиняются друг другу, это означает, что на самом деле это одна и та же роль или должность в организационной структуре.

Формально это выражается как $\forall a,b \in A: (a,b) \in \rho$ и $(b,a) \in \rho \Rightarrow a = b$ , где $\rho$ обозначает отношение «подчиняется».

Эквивалентность. Эквивалентные отношения объединяют свойства рефлексивности, симметричности и транзитивности. Отношение, которое является рефлексивным, симметричным и транзитивным, называется отношением эквивалентности.

Пример. Примером отношения эквивалентности на множестве чисел может служить отношение "иметь одинаковый остаток при делении на $n$ " на множестве всех целых чисел. В данном случае $n$ — это фиксированное натуральное число, например 3.

Пусть $\mathbb{Z}$ — множество всех целых чисел, тогда можно определить отношение $\rho$ следующим образом: для любых чисел $a$ и $b$ из $\mathbb{Z}$ , $(a,b) \in \rho$ , если $a$ и $b$ дают одинаковый остаток при делении на 3.

Это отношение эквивалентности, потому что оно рефлексивно, симметрично и транзитивно.

Рефлексивность. Любое число $a$ дает одинаковый остаток при делении на 3 с самим собой. То есть $(a,a) \in \rho$ .
Симметричность. Если $(a,b) \in \rho$ , то и $(b,a) \in \rho$ , так как если $a$ и $b$ имеют одинаковый остаток при делении на 3, то и $b,$ и $a$ имеют одинаковый остаток.
Транзитивность. Если $(a,b) \in \rho$ и $(b,c) \in \rho$ , то $(a,c) \in \rho.$ Это означает, что если $a$ и $b$ имеют одинаковый остаток при делении на 3, и $b,$ и $c$ имеют одинаковый остаток, то и $a,$ и $c$ имеют одинаковый остаток при делении на 3.

Таким образом, это отношение удовлетворяет всем трем условиям эквивалентности.

Рассмотрим конкретный пример отношения эквивалентности «иметь одинаковый остаток при делении на 3» на множестве целых чисел.

Возьмем числа 5, 8 и 11. Проверим, удовлетворяют ли они условиям рефлексивности, симметричности и транзитивности.

Рефлексивность. Каждое из этих чисел имеет одинаковый остаток при делении на 3 с самим собой. Например, «5 делится на 3 с остатком 2», находится в отношении рефлексии с «5 делится на 3 с остатком 2», т. е. $(5, 5) \in \rho.$
Симметричность. 5 и 8 имеют одинаковый остаток при делении на 3 (остаток 2), таким образом, если $(5,8) \in \rho$ , то и $(8,5) \in \rho$ . То же самое справедливо для пары чисел 8 и 11, которые также имеют остаток 2 при делении на 3.
Транзитивность. Поскольку 5 и 8 имеют одинаковый остаток (2), а 8 и 11 тоже имеют одинаковый остаток (2), следовательно, 5 и 11 тоже имеют одинаковый остаток при делении на 3.

Таким образом, эти числа удовлетворяют всем трем условиям эквивалентности для отношения «иметь одинаковый остаток при делении на 3».

Пример. Для иллюстрации отношения эквивалентности в жизненном контексте можно использовать пример с группировкой людей по месяцам рождения.

Предположим, множество $A$ состоит из всех людей. Мы можем определить отношение $\rho$ так: люди находятся в отношении $\rho$ , если они родились в одном и том же месяце.

Это отношение является отношением эквивалентности, так как оно удовлетворяет трем условиям.

Рефлексивность. Каждый человек родился в каком-то месяце, так что он или она находится в отношении $\rho$ с самим собой.
Симметричность. Если человек $a$ родился в том же месяце, что и человек $b$ , то и человек $b$ родился в том же месяце, что и человек $a$ .
Транзитивность. Если человек $a$ родился в том же месяце, что и человек $b$ , и человек $b$ родился в том же месяце, что и человек $c$ , то человек $a$ также родился в том же месяце, что и человек $c$ .

Примеры и задачи для самостоятельного решения

1.5.1. Дано множество планет. Исследовать отношение «иметь одну и ту же среднюю температуру поверхности» на предмет следующих свойств: рефлексивность, симметричность, антисимметричность, транзитивность.

Решение.

Отношение рефлексивно, так как каждая планета имеет одну и ту же среднюю температуру сама с собой.

Отношение симметрично, так как если одна планета имеет ту же среднюю температуру, что и другая, то и наоборот.

Отношение не антисимметрично, так как разные планеты могут иметь одну и ту же среднюю температуру.

Отношение транзитивно, так как если две планеты имеют одну и ту же среднюю температуру, и одна из них имеет ту же температуру, что и третья, то все три планеты имеют одну и ту же температуру.

1.5.2. Дано множество компьютерных программ. Исследовать отношение «быть написанным на одном и том же языке программирования» на предмет следующих свойств: рефлексивность, симметричность, антисимметричность, транзитивность.

1.5.3. Дано множество университетов. Исследовать отношение «находиться в одном городе» на предмет следующих свойств: рефлексивность, симметричность, антисимметричность, транзитивность.

1.5.4. Дано множество рек. Исследовать отношение «впадать в одно и то же море» на предмет следующих свойств: рефлексивность, симметричность, антисимметричность, транзитивность.

1.6.37. Дано множество писателей. Исследовать отношение «писать в одном жанре» на предмет следующих свойств: рефлексивность, симметричность, антисимметричность, транзитивность.

1.6.38. Дано множество видов птиц. Исследовать отношение «иметь одинаковую среду обитания» на предмет следующих свойств: рефлексивность, симметричность, антисимметричность, транзитивность.

1.6.39. Дано множество фильмов. Исследовать отношение «быть снятым одним режиссером» на предмет следующих свойств: рефлексивность, симметричность, антисимметричность, транзитивность.