Отношение (теория множеств)

У этого термина существуют и другие значения, см. Отношение.

Не следует путать с (отношением чисел) — результатом деления одного числа на другое или стороной пропорции.

Отноше́ние — математическая структура, которая формально определяет свойства различных объектов и их взаимосвязи. Распространёнными примерами отношений в математике являются равенство (=), делимость, подобие, параллельность и многие другие.

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

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

Формальные определения и обозначения

${\displaystyle n}$-местным (${\displaystyle n}$-арным) отношением ${\displaystyle R}$, заданным на множествах ${\displaystyle M_{1},M_{2},\ldots ,M_{n}}$, называется подмножество декартова произведения этих множеств: ${\displaystyle R\subseteq M_{1}\times M_{2}\times \dots M_{n}}$. Факт связи ${\displaystyle n}$-ки элементов ${\displaystyle \langle m_{1}\in M_{1},m_{2}\in M_{2},\dots m_{n}\in M_{n}\rangle }$ отношением ${\displaystyle R}$ обозначается ${\displaystyle R(m_{1},m_{2},\dots ,m_{n})}$ или ${\displaystyle (m_{1},m_{2},\dots ,m_{n})\in R}$.

Факт связи объектов ${\displaystyle m_{1}\in M_{1}}$ и ${\displaystyle m_{2}\in M_{2}}$ бинарным отношением ${\displaystyle R\subset M_{1}\times M_{2}}$ обычно обозначают с помощью (инфиксной записи): ${\displaystyle m_{1}\,R\,m_{2}}$. Одноместные (унарные) отношения соответствуют свойствам или атрибутам, как правило, для таких случаев терминология отношений не используется. Иногда используются трёхместные отношения (тернарные), четырёхместные отношения (кватернарные); об отношениях неопределённо высокой арности говорят как о мультиарных («многоместных»).

Универсальное отношение — это отношение, связывающее все элементы заданных множеств, то есть, совпадающее с декартовым произведением: ${\displaystyle R=M_{1}\times M_{2}\times \dots M_{n}}$.

Нуль-отношение — отношение, не связывающее никакие элементы, то есть пустое множество: ${\displaystyle R=\varnothing \subset M_{1}\times M_{2}\times \dots M_{n}}$.

Функциональное отношение — отношение, образующее функцию: ${\displaystyle R\subseteq M_{1}\times M_{2}\times \dots M_{n}\dots M_{n+1}}$ является функциональным, если из выполнения ${\displaystyle R(m_{1},\dots ,m_{n},x)}$ и ${\displaystyle R(m_{1},\dots ,m_{n},y)}$ следует, что ${\displaystyle x=y}$ (обеспечивается единственность значения функции).

Общие свойства и виды бинарных отношений

Наиболее распространённые в языке математики отношения — бинарные над одним множеством (${\displaystyle R\subseteq M^{2}}$), наиболее часто используются обладающие некоторыми общими свойствами:

• (симметричностью) (${\displaystyle a\,R\,b\Rightarrow b\,R\,a}$) или (антисимметричностью) (${\displaystyle a\,R\,b\,\wedge \,b\,R\,a\Rightarrow a\,=\,b}$),
• (рефлексивностью) (${\displaystyle a\,R\,a}$) или (антирефлексивностью) ${\displaystyle \neg \,(a\,R\,a)}$,
• (транзитивностью) (${\displaystyle a\,R\,b\land b\,R\,c\Rightarrow a\,R\,c}$) или (антитранзитивностью) (${\displaystyle a\,R\,b\land b\,R\,c\Rightarrow \neg \,a\,R\,c}$),
• (${\displaystyle a\neq b\Rightarrow a\,R\,b\lor b\,R\,a}$).

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

• отношение эквивалентности — всякое (рефлексивное), (транзитивное) и (симметричное) отношение;
• (отношение предпорядка) — рефлексивное и транзитивное;
• (отношение частичного порядка) — рефлексивное, транзитивное и антисимметричное;
• (отношение строгого порядка) — антирефлексивное, транзитивное, антисимметричное;
• (отношение линейного порядка) — связное, рефлексивное, антисимметричное.

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

Могут быть и другие комбинации свойств отношений, например, транзитивно и рефлексивно, но не обладает другими простыми свойствами, отношение делимости на множестве натуральных чисел, обычно обозначаемое символом ${\displaystyle |}$, оно состоит из пар вида ${\displaystyle \langle x,y\rangle }$, где ${\displaystyle x}$ делит ${\displaystyle y}$ нацело. Пример тернарного отношения — образование (пифагоровой тройки) тремя числами, нахождение в отношении (пифагоровой четвёрки) — пример кватернарного отношения.

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

Алгебры отношений

Все ${\displaystyle n}$-арные отношения над декартовым произведением ${\displaystyle M_{1}\times \dots \times M_{n}}$ образуют булеву алгебру относительно теоретико-множественных операций (объединения), (пересечения) и дополнения.

(Реляционная алгебра) — замкнутая система операций над отношениями в реляционной модели данных.

Примечания

1. В формулах опущены кванторы всеобщности

Литература

• Отношение — статья из Математической энциклопедии. Д. М. Смирнов
• (Колмогоров А. Н.), (Драгалин А. Г.) Введение в математическую логику. — М.: Издательство Московского университета, 1982. — 120 с. — 29 500 экз.