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

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

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

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

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

$n$-местным ($n$-арным) отношением $R$, заданным на множествах $M_1,M_2,\dots ,M_n$, называется подмножество декартова произведения этих множеств: $R\subseteq M_1\times M_2\times \dots M_n$. Факт связи $n$-ки элементов $⟨m_1\in M_1,m_2\in M_2,\dots m_n\in M_n⟩$ отношением $R$ обозначается $R(m_1,m_2,\dots ,m_n)$ или $(m_1,m_2,\dots ,m_n)\in R$.

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

Шаблон:ЯкорьУниверсальное отношение — это отношение, связывающее все элементы заданных множеств, то есть, совпадающее с декартовым произведением: $R=M_1\times M_2\times \dots M_n$.

Нуль-отношение — отношение, не связывающее никакие элементы, то есть пустое множество: $R=\varnothing \subset M_1\times M_2\times \dots M_n$.

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

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

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

• симметричностью ($aRb\Rightarrow bRa$) или антисимметричностью ($aRb\wedge bRa\Rightarrow a=b$),
• рефлексивностью ($aRa$) или антирефлексивностью $\mathrm{\neg }(aRa)$,
• транзитивностью ($aRb\wedge bRc\Rightarrow aRc$) или антитранзитивностью ($aRb\wedge bRc\Rightarrow \mathrm{\neg }aRc$),
• связностью ($a\ne b\Rightarrow aRb\vee bRa$).

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

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

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

Могут быть и другие комбинации свойств отношений, например, транзитивно и рефлексивно, но не обладает другими простыми свойствами, отношение делимости на множестве натуральных чисел, обычно обозначаемое символом $|$, оно состоит из пар вида $⟨x,y⟩$, где $x$ делит $y$ нацело. Пример тернарного отношения — образование пифагоровой тройки тремя числами, нахождение в отношении пифагоровой четвёрки — пример кватернарного отношения.

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

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

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

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

Литература

• Шаблон:Из
• Шаблон:Книга