Отношение (теория множеств)
Отноше́ние — математическая структура, которая формально определяет свойства различных объектов и их взаимосвязи. Распространёнными примерами отношений в математике являются равенство (=), делимость, подобие, параллельность и многие другие.
Понятие отношения как подмножества декартова произведения формализовано в теории множеств и получило широкое распространение в языке математики во всех её ветвях. Теоретико-множественный взгляд на отношение характеризует его с точки зрения объёма — какими комбинациями элементов оно наполнено; содержательный подход рассматривается в математической логике, где отношение — пропозициональная функция, то есть выражение с неопределёнными переменными, подстановка конкретных значений для которых делает его истинным или ложным. Важную роль отношения играют в универсальной алгебре, где базовый объект изучения раздела — множество с произвольным набором операций и отношений. Одно из самых ярких применений техники математических отношений в приложениях — реляционные системы управления базами данных, методологически основанные на формальной алгебре отношений.
Отношения обычно классифицируются по количеству связываемых объектов (арность) и собственным свойствам, таким как симметричность, транзитивность, рефлексивность.
Формальные определения и обозначения
[math]\displaystyle{ n }[/math]-местным ([math]\displaystyle{ n }[/math]-арным) отношением [math]\displaystyle{ R }[/math], заданным на множествах [math]\displaystyle{ M_1,M_2,\ldots,M_n }[/math], называется подмножество декартова произведения этих множеств: [math]\displaystyle{ R \subseteq M_1 \times M_2 \times \dots M_n }[/math]. Факт связи [math]\displaystyle{ n }[/math]-ки элементов [math]\displaystyle{ \langle m_1 \in M_1, m_2 \in M_2, \dots m_n \in M_n \rangle }[/math] отношением [math]\displaystyle{ R }[/math] обозначается [math]\displaystyle{ R (m_1, m_2, \dots, m_n) }[/math] или [math]\displaystyle{ (m_1, m_2, \dots, m_n) \in R }[/math].
Факт связи объектов [math]\displaystyle{ m_1 \in M_1 }[/math] и [math]\displaystyle{ m_2 \in M_2 }[/math] бинарным отношением [math]\displaystyle{ R \subset M_1 \times M_2 }[/math] обычно обозначают с помощью инфиксной записи: [math]\displaystyle{ m_1 \, R \, m_2 }[/math]. Одноместные (унарные) отношения соответствуют свойствам или атрибутам, как правило, для таких случаев терминология отношений не используется. Иногда используются трёхместные отношения (тернарные), четырёхместные отношения (кватернарные); об отношениях неопределённо высокой арности говорят как о «мультиарных», «многоместных».
Универсальное отношение — это отношение, связывающее все элементы заданных множеств, то есть, совпадающее с декартовым произведением: [math]\displaystyle{ R = M_1 \times M_2 \times \dots M_n }[/math]. Нуль-отношение — отношение, не связывающее никакие элементы, то есть пустое множество: [math]\displaystyle{ R = \varnothing \subset M_1 \times M_2 \times \dots M_n }[/math].
Функциональное отношение — отношение, образующее функцию: [math]\displaystyle{ R \subseteq M_1 \times M_2 \times \dots M_n \dots M_{n+1} }[/math] является функциональным, если из выполнения [math]\displaystyle{ R (m_1, \dots, m_n, x) }[/math] и [math]\displaystyle{ R (m_1, \dots, m_n, y) }[/math] следует, что [math]\displaystyle{ x=y }[/math] (обеспечивается единственность значения функции).
Общие свойства и виды бинарных отношений
Наиболее распространённые в языке математики отношения — бинарные над одним множеством ([math]\displaystyle{ R \subseteq M^2 }[/math]), наиболее часто используются обладающие некоторыми общими свойствами[1]:
- симметричностью ([math]\displaystyle{ a\, R\, b \Rightarrow b\, R\, a }[/math]) или антисимметричностью ([math]\displaystyle{ a\, R\, b \, \wedge \, b\, R\, a \Rightarrow a \, = \, b }[/math]),
- рефлексивностью ([math]\displaystyle{ a\, R\, a }[/math]) или антирефлексивностью [math]\displaystyle{ \neg \, ( a\, R\, a ) }[/math],
- транзитивностью ([math]\displaystyle{ a\, R\, b \land b\, R\, c \Rightarrow a\, R\, c }[/math]) или антитранзитивностью ([math]\displaystyle{ a\, R\, b \land b\, R\, c \Rightarrow \neg \, a\, R\, c }[/math]),
- связностью ([math]\displaystyle{ a \neq b \Rightarrow a\, R\, b \lor b\, R\, a }[/math]).
В зависимости от набора свойств бинарных отношений формируются некоторые широко используемые их виды:
- отношение эквивалентности — всякое рефлексивное, транзитивное и симметричное отношение;
- отношение предпорядка — рефлексивное и транзитивное;
- отношение частичного порядка — рефлексивное, транзитивное и антисимметричное;
- отношение строгого порядка — антирефлексивное, транзитивное, антисимметричное;
- отношение линейного порядка — связное, рефлексивное, антисимметричное.
Важную роль играет отношение равенства — отношение эквивалентности, выполненное только для двух совпадающих элементов.
Могут быть и другие комбинации свойств отношений, например, транзитивно и рефлексивно, но не обладает другими простыми свойствами, отношение делимости на множестве натуральных чисел, обычно обозначаемое символом [math]\displaystyle{ | }[/math], оно состоит из пар вида [math]\displaystyle{ \langle x, y\rangle }[/math], где [math]\displaystyle{ x }[/math] делит [math]\displaystyle{ y }[/math] нацело. Пример тернарного отношения — образование пифагоровой тройки тремя числами, нахождение в отношении пифагоровой четвёрки — пример кватернарного отношения.
Более свободный набор свойств бинарных отношений применяется в теории графов: неориентированный граф может быть определён как множество вершин с симметричным бинарным отношением над ним, а ориентированный граф — как множество вершин с произвольным бинарным отношением над ним.
Алгебры отношений
Все [math]\displaystyle{ n }[/math]-арные отношения над декартовым произведением [math]\displaystyle{ M_1 \times \dots \times M_n }[/math] образуют булеву алгебру относительно теоретико-множественных операций объединения, пересечения и дополнения.
Реляционная алгебра — замкнутая система операций над отношениями в реляционной модели данных.
Примечания
- ↑ В формулах опущены кванторы всеобщности
Литература
- Отношение — статья из Математической энциклопедии. Д. М. Смирнов
- Колмогоров А. Н., Драгалин А. Г. Введение в математическую логику. — М.: Издательство Московского университета, 1982. — 120 с. — 29 500 экз.