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

Бинарное отношение — это математическое понятие, описывающее связь между двумя элементами одного или разных множеств. Формально бинарным отношением на множестве \( A \) называется любое подмножество декартова произведения \( A \times A \), то есть множество упорядоченных пар \((a, b)\), где \( a, b \in A \). В более общем случае бинарное отношение между множествами \( A \) и \( B \) — это подмножество \( A \times B \). Бинарные отношения являются фундаментальным инструментом для формализации таких понятий, как равенство, порядок, эквивалентность, зависимость и функция, и широко используются в алгебре, теории множеств, логике, информатике и других областях.

История

Понятие отношения в неявном виде использовалось с древности в логике и философии (например, Аристотель в «Категориях» выделял категорию «отношения»). Однако строгое математическое оформление бинарные отношения получили в XIX веке в рамках развития теории множеств. Основоположником современной теории отношений считается американский логик Чарльз Сандерс Пирс, который в 1870-х годах ввёл понятие «относительной логики» и разработал нотацию для обозначения отношений. В 1880-х годах немецкий математик Георг Кантор, создавая теорию множеств, использовал упорядоченные пары для описания соответствий. В 1908 году Эрнст Цермело в аксиоматической теории множеств формализовал понятие упорядоченной пары, что позволило строго определить отношение как множество пар. Дальнейшее развитие теория отношений получила в работах Альфреда Тарского, Гарета Биркгофа и других математиков XX века, особенно в контексте универсальной алгебры и теории решёток.

Определение и основные понятия

Пусть заданы два множества \( A \) и \( B \). Бинарным отношением \( R \) между \( A \) и \( B \) называется подмножество декартова произведения \( A \times B \). Если \( (a, b) \in R \), то говорят, что элемент \( a \) находится в отношении \( R \) к элементу \( b \), и записывают \( aRb \). Если \( A = B \), то говорят о бинарном отношении на множестве \( A \).

Область определения и область значений

• Область определения (или левая область) отношения \( R \) — это множество всех \( a \in A \), для которых существует \( b \in B \) такой, что \( (a, b) \in R \). Обозначается \( \text{dom}(R) \).
• Область значений (или правая область) — это множество всех \( b \in B \), для которых существует \( a \in A \) такой, что \( (a, b) \in R \). Обозначается \( \text{ran}(R) \).

Способы задания

Бинарное отношение может быть задано:

1. Перечислением пар — для конечных множеств.
2. Характеристическим свойством — например, отношение «меньше» на множестве натуральных чисел: \( a < b \).
3. Матрицей — для конечных множеств строится матрица смежности, где строки соответствуют элементам \( A \), столбцы — элементам \( B \), а на пересечении ставится 1, если пара принадлежит отношению, и 0 в противном случае.
4. Графом — для отношения на одном множестве строится ориентированный граф, вершины которого — элементы множества, а дуги — пары отношения.

Свойства бинарных отношений

Для бинарного отношения \( R \) на множестве \( A \) (то есть \( R \subseteq A \times A \)) рассматриваются следующие основные свойства:

Виды бинарных отношений

На основе комбинаций свойств выделяют несколько фундаментальных типов бинарных отношений.

Отношение эквивалентности

Отношение \( R \) на множестве \( A \) называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно. Оно разбивает множество \( A \) на непересекающиеся классы эквивалентности — подмножества элементов, попарно находящихся в данном отношении. Классическим примером является отношение равенства: \( a = b \). Другой пример — отношение «иметь одинаковый остаток при делении на \( n \)» (сравнение по модулю \( n \)) на множестве целых чисел.

Отношение порядка

Отношение \( R \) называется отношением частичного порядка, если оно рефлексивно, антисимметрично и транзитивно. Примеры: отношение «меньше или равно» (\( \le \)) на множестве действительных чисел, отношение «быть подмножеством» (\( \subseteq \)) на множестве всех подмножеств некоторого множества. Если дополнительно выполняется свойство полноты, то отношение называется отношением линейного (полного) порядка. Пример: \( \le \) на множестве натуральных чисел.

Отношение строгого порядка

Отношение \( R \) называется отношением строгого порядка, если оно антирефлексивно, антисимметрично и транзитивно. Пример: отношение «меньше» (\( < \)) на множестве действительных чисел.

Отношение толерантности

Отношение \( R \) называется отношением толерантности, если оно рефлексивно и симметрично, но не обязательно транзитивно. Пример: отношение «быть знакомым» (если \( a \) знаком с \( b \), то \( b \) знаком с \( a \), и каждый знаком с собой, но знакомство не обязательно транзитивно).

Функциональное отношение

Бинарное отношение \( R \) называется функциональным (или однозначным), если каждому элементу из области определения соответствует не более одного элемента из области значений. Формально: \( \forall a \in A, \forall b_1, b_2 \in B: (aRb_1 \land aRb_2) \Rightarrow b_1 = b_2 \). Такое отношение является частичной функцией. Если область определения совпадает со всем множеством \( A \), то отношение является функцией.

Операции над бинарными отношениями

Поскольку бинарные отношения являются множествами, над ними можно выполнять все стандартные теоретико-множественные операции: объединение, пересечение, разность, дополнение. Кроме того, существуют специфические операции:

• Обратное отношение \( R^{-1} \): \( (b, a) \in R^{-1} \iff (a, b) \in R \).
• Композиция (произведение) отношений: если \( R \subseteq A \times B \) и \( S \subseteq B \times C \), то их композиция \( S \circ R \) (или \( R; S \)) определяется как \( \{(a, c) \in A \times C \mid \exists b \in B: (a,b) \in R \land (b,c) \in S \} \). Композиция ассоциативна.
• Замыкание отношения: для заданного свойства (например, рефлексивности, симметричности, транзитивности) замыканием отношения \( R \) называется наименьшее отношение, содержащее \( R \) и обладающее данным свойством. Например, транзитивное замыкание \( R^+ \) — это отношение, полученное добавлением всех пар, которые можно получить последовательным применением \( R \).

Применение

В математике

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

В информатике

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

В других науках

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

См. также

• Отношение (теория множеств)
• Функция (математика)
• Реляционная алгебра
• Теория графов

Источники

1. Куратовский К., Мостовский А. Теория множеств. — М.: Мир, 1970.
2. Мальцев А. И. Алгебраические системы. — М.: Наука, 1970.
3. Биркгоф Г., Барти Т. Современная прикладная алгебра. — М.: Мир, 1976.
4. Шрейдер Ю. А. Равенство, сходство, порядок. — М.: Наука, 1971.
5. Халмош П. Теория множеств. — М.: Мир, 1966.