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